Why valgrind complains about Invalid reads of size 8 on single linked list node removal?

Question

I have written a small implementation of single linked list with a functionality of removing nodes with given values, based on the following articles/SO questions:

http://grisha.org/blog/2013/04/02/linus-on-understanding-pointers/

How do pointer to pointers work in C?

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

typedef struct node
{
  int val;
  struct node* next;
} node;

node* newNode(int val)
{
  node* n = (node*)malloc(sizeof(node));
  n->val = val;
  n->next = NULL;
  return n;
}

void clean(node* head)
{
  while (head)
  {
    node* curr = head;
    head = head->next;
    free(curr);
  }
}

void append(node* head, int val)
{
  if(head == NULL)
  {
    head = newNode(val);
    return;
  }

  while (head->next)
    head = head->next;
  head->next = newNode(val);
}

void removeIf(node** head, int val)
{
  //node **curr = head;
  //while (*curr != NULL) {
  //  if ((*curr)->val == val) {
  //    node *next = (*curr)->next;
  //    free(*curr);
  //    *curr = next;
  //  } else {
  //    curr = &((*curr)->next);
  //  }
  //}

  node **pp = head; /* pointer to a pointer */
  node *entry = *head;

  while (entry) {
      if (entry->val == val)
      {
        node* tmp = *pp;
        *pp = entry->next;
        free(tmp);
      }
      else
        pp = &entry->next;

      entry = entry->next;
  }
}

int size(node* head)
{
  int sz = 0;
  while (head)
  {
    head = head->next;
    ++sz;
  }

  return sz;
}

void tests();

int main()
{
  tests();
  return 0;
}

/*
 * Here are the tests for lists functionalities
 */
void tests()
{
  {
    node* root = newNode(1);
    append(root, 1);
    append(root, 1);
    append(root, 1);
    append(root, 2);
    append(root, 3);
    append(root, 5);
    assert(size(root) == 7);
    removeIf(&root, 1);
    assert(size(root) == 3);
    clean(root);
  }
}

The problem lies with the removeIf() function on last line (main.c:68):

entry = entry->next;

The commented works and valgrind does not complain about it whereas the uncommented code works but valgrind complains as follows:

==31665== Memcheck, a memory error detector
==31665== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==31665== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==31665== Command: ./a.out
==31665== 
==31665== Invalid read of size 8
==31665==    at 0x40067C: removeIf (main.c:68)
==31665==    by 0x400785: tests (main.c:106)
==31665==    by 0x4006C7: main (main.c:88)
==31665==  Address 0x4c33048 is 8 bytes inside a block of size 16 free'd
==31665==    at 0x4A06430: free (vg_replace_malloc.c:446)
==31665==    by 0x400669: removeIf (main.c:63)
==31665==    by 0x400785: tests (main.c:106)
==31665==    by 0x4006C7: main (main.c:88)
==31665== 
==31665== 
==31665== HEAP SUMMARY:
==31665==     in use at exit: 0 bytes in 0 blocks
==31665==   total heap usage: 7 allocs, 7 frees, 112 bytes allocated
==31665== 
==31665== All heap blocks were freed -- no leaks are possible
==31665== 
==31665== For counts of detected and suppressed errors, rerun with: -v
==31665== ERROR SUMMARY: 4 errors from 1 contexts (suppressed: 6 from 6)

Can someone comment on what might be the problem?

Answer 1

I think I know what is going on. Let's review the flow step by step and assume that we encountered the very first node to remove (we will call it ENTRY). From your code that means the following state:

-- pp contains the address of an ENTRY pointer obvoiusly, since it's the first found, because pp was updated to the addresses of entry iterator all the time (we always had 'else' case).

What happens next? We assign ENTRY to tmp and pp to the next of ENTRY and then free tmp, essentially freeing memory of ENTRY since both tmp and ENTRY contain same address. This introduces two problems:

1) The previous node's next pointer (which is NODE->NEXT == ENTRY) becomes a dangling pointer since it has never been reassigned and current implementation of your function has no means to do it.

2) After you freed memory of ENTRY, you access the member 'next' to move your entry iterator forward. I assume that this is exact place and case where valgrind tells you that you accessed memory you have no ownership of.

Answer 2

As per debugging with GDB

1. removeif(head=0x7fffffffdee0,...)
2. (gdb) p &entry $11 = (node )**0x7fffffffdec0
3. Could you please check the entry and the head addresses? Am suspecting that 8 bytes is because of this.

Answer 3

This is your code fixed:

void removeIf(node** head, int val)
{
  node** last_next_pointer = head;
  node* entry = *head;

  while (entry != NULL) {
    if (entry->val == val) {
      node* tmp = entry;
      *last_next_pointer = entry->next;
      entry = entry->next;
      free(tmp);
    } else {
      last_next_pointer = &(entry->next);
      entry = entry->next;
    }
  }
}

Variable dd was not needed because it wasn't tracking previous node, so you can't relink previous one to next one and then free current node.

Your problem was the else brackets.