Valgrind doesn't like my pop() function for a linked list

I'm working on a terminal snake game in c using ncurses, and I have the snake set up as a doubly linked list using the following code:

typedef struct {
    int y; 
    int x;
} coordinates;

bool coordsequal(coordinates c1, coordinates c2);

typedef struct {
    coordinates coords;
    char attire;
} object;

typedef object part;

/* Snake: Doubly Linked list of Parts */
typedef struct dllsnake {
    part part;
    struct dllsnake *prev;
    struct dllsnake *next;
} snake;

With this, I defined a function that pops the last element off of the snake linked list:

snake *pop(snake *head) {
    if (head == NULL) {
        // List is empty, nothing to pop
        return NULL;
    }

    snake *ptr; // line 84
    for (ptr = head; ptr->next != NULL; ptr = ptr->next); // line 85

    snake *new_tail = ptr->prev; // line 87
    new_tail->next = NULL;
    free(ptr);

    return new_tail;
}

This function works as intended in the snake game, deleting the snake's tail when prompted to. However, when I run my snake game with valgrind, valgrind has many complaints about this function, including:

Invalid read of size 8 at lines 84, 85, and 87
Invalid free() / delete / delete[] / realloc() at line 87
Addresses 0x4b52d10, 0x4b52d20, and 0x4b52d28 are 0 bytes inside a block of size 32 free'd, line 87

What's more, when the snake game is run with valgrind, the pop() function stops working entirely.

I don't know what to do with these messages! For the first one, it isn't apparent how I'm reading any memory that I'm not supposed to be reading. For the second, why would it be pointing at line 87 if the free statement is two lines later? And I don't know what the last point is. Any help would be much appreciated.

Solution

pop() will segfault on new_tail->next if head->prev==NULL when the list contains 1 node.
pop() usually transfer ownership to caller which frees the node when done. This means pop() should not free it.
If you want to be able to free the head node then you need to (preferred) pass in snake **head so you can update it, return the new head (probably not suitable here as you want return the last ) or have caller keep track.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int y;
    int x;
} coordinates;

bool coordsequal(coordinates c1, coordinates c2);

typedef struct {
    coordinates coords;
    char attire;
} object;

typedef object part;

/* Snake: Doubly Linked list of Parts */
typedef struct dllsnake {
    part part;
    struct dllsnake *prev;
    struct dllsnake *next;
} snake;

snake *create(snake *prev) {
    snake *n = malloc(sizeof *n);
    if(!n) {
        fprintf(stderr, "malloc failed\n");
        exit(1);
    }
    n->prev = prev;
    if(prev) prev->next = n;
    n->next = NULL;
    return n;
}

snake *pop(snake **head) {
    if (!head || !*head) return NULL;
    snake *ptr;
    for (ptr = *head; ptr->next != NULL; ptr = ptr->next);
    if(ptr->prev)
        ptr->prev->next = NULL;
    else
        *head = NULL;
    ptr->prev= NULL;
    ptr->next = NULL;
    return ptr;
}

void print(const char *prefix, snake *head) {
    printf("%s:\n", prefix);
    for(; head; head=head->next)
        printf("\tnode=%p prev=%p next=%p\n", (void *) head, (void *) head->prev, (void *) head->next);
}
int main(void) {
    snake *head = create(NULL);
    create(head);
    print("head with two nodes", head);

    snake *node = pop(&head);
    print("head after first pop", head);
    print("node first pop", node);
    free(node);

    snake *node2 = pop(&head);
    print("head after 2nd pop", head);
    print("node after 2nd pop", node2);
    free(node2);
}

and example run:

head with two nodes:
        node=0x557bc52bd2a0 prev=(nil) next=0x557bc52bd2d0
        node=0x557bc52bd2d0 prev=0x557bc52bd2a0 next=(nil)
head after first pop:
        node=0x557bc52bd2a0 prev=(nil) next=(nil)
node first pop:
        node=0x557bc52bd2d0 prev=(nil) next=(nil)
head after 2nd pop:
node after 2nd pop:
        node=0x557bc52bd2a0 prev=(nil) next=(nil)

and valgrind seems to be happy:

==98314== HEAP SUMMARY:
==98314==     in use at exit: 0 bytes in 0 blocks
==98314==   total heap usage: 3 allocs, 3 frees, 1,088 bytes allocated
==98314== 
==98314== All heap blocks were freed -- no leaks are possible

If you want to do the free within pop() you could do this:

int pop(snake **head, part *result) {
    if (!head || !*head || !result) return 1;
    snake *ptr;
    for (ptr = *head; ptr->next != NULL; ptr = ptr->next);
    if(ptr->prev)
        ptr->prev->next = NULL;
    else
        *head = NULL;
    *result = ptr->part;
    free(ptr);
    return 0;
}

// ...

int main(void) {

   // ...

    part part;
    if(pop(&head, &part)) {
        // handle underflow
    }

    // ...