title: Segmentation Fault with invalid read of size 8 in C with Valgrind
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>I have run into errors that I cannot seem to track down or understand using gdb and valgrind on my program. </p>
  
  <p>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.</p>
  
  <p>Results from running Valgrind:</p>
  
  <pre><code>==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)
  </code></pre>
  
  <p>Results from running GDB:</p>
  
  <pre><code>Program received signal SIGSEGV, Segmentation fault.
  0x0000000000401511 in freeDiscs (discs=0x0, MAX_SLOTS=5) at discs.c:140
  140         discs = discs-&gt;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)
  </code></pre>
  
  <p>Function that removes multiple nodes that have the same state from the fringe:</p>
  
  <pre><code>/* 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-&gt;state, remove-&gt;state, MAX_SLOTS)) {
        /* when removing from the head */
        if (current == head) {
          head = current-&gt;parent;
          delete = current;
          current = head;
          freeDiscs(delete-&gt;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-&gt;parent == NULL &amp;&amp; current != NULL) {
          delete = current;
          current = NULL;
          freeDiscs(delete-&gt;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-&gt;parent;
          prev-&gt;parent = current;
          /* ---- line 266 and 267 below ---- */
          freeDiscs(delete-&gt;state, MAX_SLOTS);
          free(delete);
          delete = NULL;
          remove_switch = 1;
        }
      }
      if (remove_switch == 0) {
        prev = current;
        current = current-&gt;parent;
      }
      remove_switch = 0;
    }
    return head;
  }
  </code></pre>
  
  <p>Free List function:</p>
  
  <pre><code>/* 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-&gt;parent;
        /* ---- line 404 below ---- */
        freeDiscs(prev-&gt;state, MAX_SLOTS);
        free(prev);
        prev = NULL;
      }    
    }
  }
  </code></pre>
  
  <p>Free Discs Function:</p>
  
  <pre><code>/* frees's a discs_slot list */
  void freeDiscs(struct discs_slot * discs, int MAX_SLOTS) {
    int i = 0;
    struct discs_slot * temp;
  
    while (i &lt; MAX_SLOTS) {
      temp = discs;
      discs = discs-&gt;next;
      /* ---- line 141 below ---- */
      free(temp);
      i++;
    }
  
  }
  </code></pre>
  
  <p>Relevant Code from the main:</p>
  
  <pre><code>  /* until reaching a solution or the maximum traversals allowed */
    while (!isGoal(best_current-&gt;state) &amp;&amp; Towards_Solution &lt; 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-&gt;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;
  
  }
  </code></pre>
  
  <p>This is the add fringe function:</p>
  
  <pre><code>/* 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-&gt;parent = move_LCCW;
      current-&gt;parent-&gt;parent = move_ACW;
      current-&gt;parent-&gt;parent-&gt;parent = move_ACCW;
      current-&gt;parent-&gt;parent-&gt;parent-&gt;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-&gt;parent;
        //printf("*\n");
      }
      //printf("Fringe not empty new nodes added:\n\n");
      current = move_LCW;
      current-&gt;parent = move_LCCW;
      current-&gt;parent-&gt;parent = move_ACW;
      current-&gt;parent-&gt;parent-&gt;parent = move_ACCW;
      current-&gt;parent-&gt;parent-&gt;parent-&gt;parent = NULL;
      //printf("List Start --------------------\n");
      //printList(current, MAX_SLOTS);
      //printf("List End  --------------------\n");
      prev-&gt;parent = current;
      current = head;
    }
  
    //printf("Entire Fringe: \n\n");
    //printList(head, MAX_SLOTS);
    //printf("____________________\n");
    return current;
  }
  </code></pre>
  
  <p>This is the function that copys a discs list of size MAX_SLOTS (it eventually reads as NULL)</p>
  
  <pre><code>/* 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 &lt; MAX_SLOTS; i++) {
      current-&gt;large = discs-&gt;large;
      current-&gt;small = discs-&gt;small;
      current-&gt;position = discs-&gt;position;
  
      if (i &lt; (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-&gt;next = new_dslot;
        current = new_dslot;
      }
      discs = discs-&gt;next;
    }
  
    current-&gt;next = head;
    current = head;
  
    return current;
  }
  </code></pre>