Dynamic growing string array memory issues

Question

I'm working on a crosswords program in which a word dictionary is necessary. I'm trying load a jspell dictionary file into an dynamic string array but i keep getting the

error malloc(): mismatching next->prev_size (unsorted)

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include "dictionary.h"


void dict_init(Dictionary * dict, char * dict_dir, size_t w_len)
{

    printf("dictionary.c (dict_init): initializing dictionary.\n");

    /*Adjust this value to control the initial array size*/
    size_t init_size = 1000;

    /*initialize dictionary file directory*/
    dict->dir = malloc(strlen(dict_dir) * sizeof(char) + 1);
    strcpy(dict->dir, dict_dir);

    /*create memory for words array*/
    dict->words = malloc(init_size * sizeof(char *));

    /*initialize array size*/
    dict->size = init_size;

    /*initilize word length*/
    dict->w_len = w_len;

    /*initialize word counter*/
    dict->counter = 0;

    /*load words into dictionary*/
    dict_load(dict);

    printf("dictionary.c (dict_init): dictionary initialized.\n");
}


void dict_add(Dictionary * dict, char * word)
{
    char ** dictionary = dict->words;

    /*check if word array is full*/
    if(dict->counter == dict->size)
    {
        /*increrase size of dictionary*/
        dict->size *= 1.5;
        dict->words = realloc(dict->words, dict->size * sizeof(char *));
    }

    /*add word to dictionary*/
    dictionary[dict->counter] = malloc(strlen(word) * sizeof(char) + 1);
    strcpy(dictionary[dict->counter], word);
    dict->counter++;

    free(word);
}


void dict_free(Dictionary * dict) 
{
    free(dict->words);
}


void dict_load(Dictionary * dict)
{
    FILE * fp;

    char * line = NULL;
    char * word = NULL;

    size_t len = 0;
    ssize_t read;

    fp = fopen(dict->dir, "r");

    /*check if file exists*/
    if (fp == NULL)
    {
        perror("ERROR: File not found.");
        exit(EXIT_FAILURE);
    }

    /*discard first line*/
    if(strstr(dict->dir, ".dic"))
        getline(&line, &len, fp);

    /*read file lines*/
    while ((read = getline(&line, &len, fp)) != -1) 
    {
        if(((strstr(line, "[CAT=punct") == NULL) && (word = parse_line(line, dict->w_len)) != NULL)) {
            dict_add(dict, word);
        }
    }

    fclose(fp);
    free(line);

    printf("dictionary.c (dict_load): dictionary loaded %ld words.\n", dict->counter);
}


char * parse_line(char * line, size_t w_len)
{
    int i;
    char s_tmp[101] = "";
    char * dlm_slash, * dlm_space, * dlm_tab , *substring;

    /*get delimiter pointer*/
    dlm_slash = strchr(line, '/');
    dlm_space = strchr(line, ' ');
    dlm_tab = strchr(line, '\t');

    /*check if delimiter exists in line*/
    if(dlm_slash != NULL)
        i = (int)(dlm_slash - line);

    else if(dlm_space != NULL)
        i = (int)(dlm_space - line);

    else if(dlm_tab != NULL)
        i = (int)(dlm_tab - line);

    else
    {
        /*replace '\n' with '\0'*/
        line[strcspn(line, "\n")] = '\0';
    
        i = strlen(line);
    }

    strncpy(s_tmp, line, i);

    substring = malloc(sizeof(char) * strlen(s_tmp) + 1);
    strncpy(substring, s_tmp, strlen(s_tmp));

    /*lowercase word*/
    lower_case(substring);

    if((is_valid(substring) == 0) && (strlen(substring) <= w_len))
        return substring;

    free(substring);
    return NULL;
}

Answer 1

Here's the basic problem, I think:

void dict_add(Dictionary * dict, char * word) {
char ** dictionary = dict->words;       /* **** 1 **** */

/*check if word array is full*/
if(dict->counter == dict->size)
{
    /*increrase size of dictionary*/
    dict->size *= 1.5;                  /* **** 2 **** */
    dict->words = realloc(dict->words, dict->size * sizeof(char *));
                                        /* **** 3 **** */
}

/*add word to dictionary*/

This one is the problem:

dictionary[dict->counter] = malloc(strlen(word) * sizeof(char) + 1);
strcpy(dictionary[dict->counter], word);
dict->counter++;

free(word);                            /* **** 4 **** */
}

The problem is that dictionary was saved before you called realloc. realloc might make a brand-new memory allocation, in which case it will automatically free() the old one after copying its contents into the new one. So any copy of the pointer which you made before calling realloc might end up pointing to unallocated memory. Writing to unallocated memory is a big no-no; in this particular case, you're probably overwriting malloc's bookkeeping information about the unallocated block, which is why it detects the problem and complains. Count yourself lucky: lots of memory corruption problems go undetected for quite a while until the factory explodes.

Some other issues which I noticed while writing this, with numbered comments in the source:

1. There's actually no need for the variable dictionary at all.

2. dict->size is an integer. Forcing conversion to a floating point number and then truncating back to an integer is not very useful. Prefer dict->size += dict->size/2;. Even better would be to first make sure that dict->size isn't so big that increasing it will cause integer wraparound. (This is not undefined behaviour on unsigned types like size_t, but it's not going to produce correct results.)

3. Here you could actually use a temporary, because realloc might return NULL indicating a memory allocation failure. If that happens, the original allocation is not automatically freed, and you don't have a way to free it. (Actually you do, since you have a variable confusingly called dictionary, but in point 1 I recommended that you get rid of it.) A more idiomatic call would be:

   if(dict->counter == dict->size) {
       /*increrase size of dictionary*/
       dict->size += dict->size / 2;   /* See point 2, above */
       char** new_words = realloc(dict->words, dict->size * sizeof(*new_words));
       if (new_words == NULL) {
           /* Report allocation error and free all the memory you've allocated */
           /* Then probably exit(1) but if this were a library function, just
            * return some kind of failure indication so that the caller can do
            * their own clean-up.
            */
       }
       dict->words = new_words;
   }
   dict->words[dict->counter] = word; /* See point 4, below */
   

4. You're freeing word here because it was allocated in parse_line(). But if you know you're going to free it anyway, there wasn't much point making a copy of it first. You might as well just use it. (But you need to document the fact that this function takes ownership of the word passed as an argument.)

   It might be considered cleaner to do the copy as you do but then not free the argument, leaving it for the caller to do that. That would have the advantage of allowing the caller to provide a word which hadn't been dynamically allocated, or use the word for some other purpose.

5. (Not indicated in this snippet, but nonetheless important). Every block of allocated memory must be freed. So your program should execute free exactly as many times as it executed malloc. But you don't do that; you just free the array of word pointers, and let the words pointed to in that array leak. You should fix that. (Note that you don't need an extra call to free for a call to realloc, since realloc itself frees the old block if it allocates a new one. You only need to match the initial malloc with a free.)