Segmentation Fault with invalid read of size 8 in C with Valgrind

Question

I am writing a program for a school project that uses A* search to traverse through a list of possible states and select the next best one to proceed to a solution.

I want to be clear that I am not looking for a solution to my homework but help on solving these errors. I have looked at many other questions online and found that at some point the address 0x0 means I am trying to access NULL because the memory no longer exists. I don't understand where or how this is happening in my program.

I have run into errors that I cannot seem to track down or understand using gdb and valgrind on my program.

Can someone take a look at these errors and my code and maybe shed light on why the program segfaults? I have been stuck on this portion of it for quite a while.

Results from running Valgrind:

==80117== Invalid read of size 8
==80117==    at 0x4011AB: freeList (AST.c:403)

==80117==    by 0x401E24: main (main.c:129)
==80117==  Address 0x51a8dd8 is 24 bytes inside a block of size 32 free'd
==80117==    at 0x4C2701C: free (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==80117==    by 0x400E58: removeFringe (AST.c:267)
==80117==    by 0x401DB4: main (main.c:104)
==80117==
==80117== Invalid read of size 8
==80117==    at 0x4011B7: freeList (AST.c:404)
==80117==    by 0x401E24: main (main.c:129)
==80117==  Address 0x51a8dc0 is 0 bytes inside a block of size 32 free'd
==80117==    at 0x4C2701C: free (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==80117==    by 0x400E58: removeFringe (AST.c:267)
==80117==    by 0x401DB4: main (main.c:104)
==80117==
==80117== Invalid read of size 8
==80117==    at 0x401511: freeDiscs (discs.c:140)
==80117==    by 0x4011C1: freeList (AST.c:404)
==80117==    by 0x401E24: main (main.c:129)
==80117==  Address 0x51a8e30 is 16 bytes inside a block of size 24 free'd
==80117==    at 0x4C2701C: free (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==80117==    by 0x401521: freeDiscs (discs.c:141)
==80117==    by 0x400E4F: removeFringe (AST.c:266)
==80117==    by 0x401DB4: main (main.c:104)
==80117==
==80117== Invalid free() / delete / delete[] / realloc()
==80117==    at 0x4C2701C: free (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==80117==    by 0x401521: freeDiscs (discs.c:141)
==80117==    by 0x4011C1: freeList (AST.c:404)
==80117==    by 0x401E24: main (main.c:129)
==80117==  Address 0x51a8e20 is 0 bytes inside a block of size 24 free'd
==80117==    at 0x4C2701C: free (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==80117==    by 0x401521: freeDiscs (discs.c:141)
==80117==    by 0x400E4F: removeFringe (AST.c:266)
==80117==    by 0x401DB4: main (main.c:104)
==80117==
==80117== Invalid free() / delete / delete[] / realloc()
==80117==    at 0x4C2701C: free (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==80117==    by 0x4011CA: freeList (AST.c:405)
==80117==    by 0x401E24: main (main.c:129)
==80117==  Address 0x51a8dc0 is 0 bytes inside a block of size 32 free'd
==80117==    at 0x4C2701C: free (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==80117==    by 0x400E58: removeFringe (AST.c:267)
==80117==    by 0x401DB4: main (main.c:104)
==80117==
==80117==
==80117== HEAP SUMMARY:
==80117==     in use at exit: 0 bytes in 0 blocks
==80117==   total heap usage: 128 allocs, 134 frees, 3,112 bytes allocated
==80117==
==80117== All heap blocks were freed -- no leaks are possible
==80117==
==80117== For counts of detected and suppressed errors, rerun with: -v
==80117== ERROR SUMMARY: 13 errors from 5 contexts (suppressed: 4 from 4)

Results from running GDB:

Program received signal SIGSEGV, Segmentation fault.
0x0000000000401511 in freeDiscs (discs=0x0, MAX_SLOTS=5) at discs.c:140
140         discs = discs->next;
(gdb) backtrace
#0  0x0000000000401511 in freeDiscs (discs=0x0, MAX_SLOTS=5) at discs.c:140
#1  0x00000000004011c2 in freeList (list=0x604220, MAX_SLOTS=5) at AST.c:404
#2  0x0000000000401e25 in main (argc=2, argv=0x7fffffffe048) at main.c:129
(gdb)

Function that removes multiple nodes that have the same state from the fringe:

/* removes nodes from the fringe and then returns the fringe */
struct AST_Node * removeFringe(struct AST_Node * fringe, struct AST_Node * remove, int MAX_SLOTS) {
  struct AST_Node * head, * current, * prev, * delete;
  int remove_switch = 0;
  head = fringe;
  current = fringe;
  prev = fringe;

  /* traverse the fringe until the end */
  while (current != NULL) {
    /* when the current node has the same state as the one for removal */
    if (isSame(current->state, remove->state, MAX_SLOTS)) {
      /* when removing from the head */
      if (current == head) {
        head = current->parent;
        delete = current;
        current = head;
        freeDiscs(delete->state, MAX_SLOTS);
        free(delete);
        delete = NULL;
        remove_switch = 1;
      }
      /* when the node to be removed is at the end of the list */
      else if (current->parent == NULL && current != NULL) {
        delete = current;
        current = NULL;
        freeDiscs(delete->state, MAX_SLOTS);
        free(delete);
        delete = NULL;
        remove_switch = 1;
      }
      /* when the node to be removed is in the middle of the list */
      else {
        delete = current;
        current = current->parent;
        prev->parent = current;
        /* ---- line 266 and 267 below ---- */
        freeDiscs(delete->state, MAX_SLOTS);
        free(delete);
        delete = NULL;
        remove_switch = 1;
      }
    }
    if (remove_switch == 0) {
      prev = current;
      current = current->parent;
    }
    remove_switch = 0;
  }
  return head;
}

Free List function:

/* free's an AST_Node list */
void freeList(struct AST_Node * list, int MAX_SLOTS) {
  struct AST_Node * current, * prev;
  current = list;
  /* when a list must be free'd, free it */
  if (current != NULL) {
    /* traverse and free until the last node */
    while (current != NULL) {
      prev = current;
      current = current->parent;
      /* ---- line 404 below ---- */
      freeDiscs(prev->state, MAX_SLOTS);
      free(prev);
      prev = NULL;
    }    
  }
}

Free Discs Function:

/* frees's a discs_slot list */
void freeDiscs(struct discs_slot * discs, int MAX_SLOTS) {
  int i = 0;
  struct discs_slot * temp;

  while (i < MAX_SLOTS) {
    temp = discs;
    discs = discs->next;
    /* ---- line 141 below ---- */
    free(temp);
    i++;
  }

}

Relevant Code from the main:

  /* until reaching a solution or the maximum traversals allowed */
  while (!isGoal(best_current->state) && Towards_Solution < Solution_Count) {
    /* when the best current node has not already been expanded */
    if (!inClosed(closed_list, best_current, Max_Slots)) {
      /* expand it and add the nodes to the fringe */
      fringe_list = addFringe(fringe_list, best_current, goal_state, Max_Slots);
      /* add the expanded node to the closed list */
      closed_list = addClosed(closed_list, best_current);
    }
    /* when the best node is in the closed list */
    else {
      /* do nothing */
    }

    printSmallDiscs(best_current->state, Max_Slots);

    /* get a new best node to evaluate and remove it from the fringe */
    best_current = fringeTraverse(fringe_list, best_current, goal_state, Max_Slots);
    /* ---- line 104 below ---- */
    fringe_list = removeFringe(fringe_list, best_current, Max_Slots);

    Towards_Solution++;

    /* when all possible nodes have been expanded and no solution exists */
    if (fringe_list == NULL) {
      printf("No solution\n");
      break;
    }
  }



  /* return memory */
  freeDiscs(discs_list, Max_Slots);
  freeDiscs(goal_state, Max_Slots);

  freeList(best_current, Max_Slots);
  /* ---- line 129 below ---- */
  freeList(fringe_list, Max_Slots);
  freeList(closed_list, Max_Slots);

  return 0;

}

This is the add fringe function:

/* creates new nodes from the best current state and adds those nodes to the fringe */
struct AST_Node * addFringe(struct AST_Node * list, struct AST_Node * best, struct discs_slot * goal, int MAX_SLOTS) {
  struct AST_Node * move_LCW, * move_LCCW, * move_ACW, * move_ACCW;
  struct AST_Node * current, * head, * prev;
  current = list;
  head = list;

  /* break apart the current best state for a possible solution */
    move_LCW = largeCW(best, goal, MAX_SLOTS);
    move_LCCW = largeCCW(best, goal, MAX_SLOTS);
    move_ACW = adjacentCW(best, goal, MAX_SLOTS);
    move_ACCW = adjacentCCW(best, goal, MAX_SLOTS);


  /* store these new nodes in the fringe */
  /* when storing in the fringe for the first time */
  if (current == NULL) {
    //printf("Empty Fringe:\n\n");
    current = move_LCW;
    current->parent = move_LCCW;
    current->parent->parent = move_ACW;
    current->parent->parent->parent = move_ACCW;
    current->parent->parent->parent->parent = NULL;
    //printf("List Start --------------------\n");
    //printList(current, MAX_SLOTS);
    //printf("List End --------------------\n");

  }
  /* when storing in a partially filled fringe */
  else {
    /* traverse to the end and start adding nodes from there */
    while (current != NULL) {
      prev = current;
      current = current->parent;
      //printf("*\n");
    }
    //printf("Fringe not empty new nodes added:\n\n");
    current = move_LCW;
    current->parent = move_LCCW;
    current->parent->parent = move_ACW;
    current->parent->parent->parent = move_ACCW;
    current->parent->parent->parent->parent = NULL;
    //printf("List Start --------------------\n");
    //printList(current, MAX_SLOTS);
    //printf("List End  --------------------\n");
    prev->parent = current;
    current = head;
  }

  //printf("Entire Fringe: \n\n");
  //printList(head, MAX_SLOTS);
  //printf("____________________\n");
  return current;
}

This is the function that copys a discs list of size MAX_SLOTS (it eventually reads as NULL)

/* creates a copy of a disc slot list */
struct discs_slot * copy_dlist(struct discs_slot * discs, int MAX_SLOTS) {

  struct discs_slot * head, * current;

  current = malloc(sizeof(struct discs_slot));
  if (current == NULL) {
    printf("\nAn error ocurred when trying to allocate memory.\n");
    exit(0);
  }

  head = current;

  /* traverse for as many disc slots that exist and copy the data from
     the disc slot list passed in to the new one */
  for (int i = 0; i < MAX_SLOTS; i++) {
    current->large = discs->large;
    current->small = discs->small;
    current->position = discs->position;

    if (i < (MAX_SLOTS - 1)) {
      struct discs_slot * new_dslot;
      new_dslot = malloc(sizeof(struct discs_slot));
      if (new_dslot == NULL) {
    printf("\nAn error ocurred when trying to allocate memory.\n");
    exit(0);
      }

      current->next = new_dslot;
      current = new_dslot;
    }
    discs = discs->next;
  }

  current->next = head;
  current = head;

  return current;
}

Answer 1

By symptom of the problem, your program experiencing some sort of invalid heap memory read. This typically occurs whenever our program tries to read after we have free the memory or free the memory twice. If we see the Valgrind report summary, we get the following information:

total heap usage: 128 allocs, 134 frees, 3,112 bytes allocated

Your program has allocated 128 allocations and trying to free 134 time. This indicates double free scenario in your program. As you have assign your pointer with NULL after freeing the memory, somewhere later your programs encounter the segmentation fault while program tries to access NULL pointer.

Looking at the stack trace, it would be almost impossible to find out the what could be the root cause of this as these segmentation fault would be after effect of something real bad(set the pointer to NULL after freeing the memory) done by program in early execution.

The best way to identify these memory corruption is to use GDB and Valgrind together. For that You may want to attach your program(a.out) in Valgrind/GDB.

$ valgrind --tool=memcheck --db-attach=yes ./a.out

This way Valgrind would attach your program in the debugger when your first memory error is detected so that you can do live debugging(GDB). This should be the best possible way to understand and resolve your problem. Once you are able to figure it out your first error, fix it and rerun it and see what are other errors you are getting.This steps should be done till no error is getting reported by Valgrind.