Pset5 Accessing 8 Byte Outside An Array

Question

I'm working on pset5 right now and I've met this problem that has taken me hours yet no luck to crack. This is how I defined my struct, containing a next[] array of 27 elements.

// define the trie data type
typedef struct trie
{
    bool presence;
    struct trie* next[27];
} trie;

Valgrind is reporting that I accessed 8 bytes of memory inaccessible to me, but I checked the Ascii table and [any lowercase alphabet - 96] should give a number between 1~26, which, since I assign the apostrophe to index 0 of the "next" array, should fit a~z perfectly into index 1~26. I am attaching my code below:

 /**
 * Implements a dictionary's functionality.
 */

 #include <stdbool.h>
 #include <ctype.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include "dictionary.h"

 int dict_size = 0;

 // define the function that creates a new node
 trie* create(void)
 {
     trie* node = calloc(1, sizeof(trie));
     if (node == NULL)
     {
         unload();
         return 0;
     }
     trie* temp = node;
     free(node);
     return temp;
 }
 trie* root;
 trie* pointer;
 /**
  * Returns true if word is in dictionary else false.
  */
 bool check(const char *word)
 {
     // TODO
     return false;
 }

 /**
  * Loads dictionary into memory. Returns true if successful else false.
  */
 bool load(const char *dictionary)
 {
     // open the dictionary and check for error
     FILE *fp = fopen(dictionary, "r");
     if (fp == NULL)
     {
         printf("Could not open %s.\n", dictionary);
         unload();
         return false;
     }

     // initialize the root of the trie
     root = create();
     pointer = root;
     for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
     {
         if (c == '\'')
         {
             if (pointer->next[0] == NULL)
             {
                 pointer->next[0] = create();
             }
             pointer = pointer->next[0];
         }
         else if (isalpha(c))
         {
             int index = c - 96;
             if (pointer->next[index] == NULL) [LINE 67]
             {
                 pointer->next[index] = create();
             }
             pointer = pointer->next[index];
         }
         else if (c == '\n')
         {
             pointer->presence = true;
             dict_size++;
             pointer = root;
         }
     }
     pointer = root;

     // check whether there was an error
     if (ferror(fp))
     {
         fclose(fp);
         printf("Error reading %s.\n", dictionary);
         unload();
         return false;
     }

     // close text and return true for success
     fclose(fp);
     return true;
 }

 unsigned int size(void)
 {
     return dict_size;
 }

 bool unload(void)
 {
     trie* temp = pointer;
     for (int i = 0; i < 27; i++)
     {
         if (temp->next[i] != 0)
         {
             pointer = pointer->next[i];
             unload();
             pointer = temp;
         }
     }
     free(temp);
     return true;
     }

Above is my code, and the valgrind promt is: Looks like you're trying to access 8 bytes of memory that isn't yours? Did you try to index into an array beyond its bounds? Take a closer look at line 67 of dictionary.c. (which I marked with [LINE 67]). Any insight would be appreciated, thank you!

Answer 1

The 8 bytes are a 64 bit pointer. You dereference pointer, which at this time is pointing into unallocated memory, and access its next[index], which is 8 bytes long.

 trie* temp = node;
 free(node);
 return temp;

First of these lines lets temp point to the same memory as node. Second line frees the space. Now, both temp and node point to some memory address that's not allocated any more. Third line returns this address.

You'd better just return node; without those three lines.

While it is not obviously doing something wrong by itself, I don't like this one:

 if (node == NULL)
 {
     unload();
     return 0;
 }

This return 0; is essentially return NULL;, you're returning a null pointer. I have no clear idea how to exit gracefully, but checking here and still returning a NULL pointer makes you handle the case on multiple layers. Maybe you could exit instead of returning, or handle it in the calling layer.

Your unload function does not what you want it to. For a trie, you might want to consider a recursive function to do the actual clean-up, and call it from your unload function, passing the address of the root node.

This recursive function then should call itself for all non-NULL children, and after that free the node itself.