Valgrind invalid free, memory leak

Question

I get invalid free, and memory leak. Here is my code:

/*=============================================================================
  |
  |  Assignment:  Test #2

  |        Class:  Programming Basics
  |         Date:  December 20th, 2017
  |
  |     Language:  GNU C (using gcc), OS: Arch Linux x86_64)
  |     Version:   0.0
  |   To Compile:  gcc -Wall -xc -g -std=c99 kontrolinis2.c -o kontrolinis_2
  |
  +-----------------------------------------------------------------------------
  |
  |  Description:  The program which gets the input number, which indicates how
  |                many words there will be, then prompts the user to enter
  |                those words, and then displays a histogram in descending 
  |                order by times the word is repeated. The words with the 
  |                same duplicate count are sorted in lexicographical order
  |
  +===========================================================================*/

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

#include "dbg.h"
#include "lib_riddle.h"

#define MAX_STRING 50

// Frequency structure. Contains the word and the times
// it is repeated
typedef struct Freq {
    char* word;
    int times;
} Freq;

// Histogram structure. Contains the list of frequencies (struct)
// and the size of the list.
typedef struct Histogram {
    Freq** freqs;
    int size;
} Histogram;

// sort the portion of the given array of frequency structs
// in lexicographically reverse order (from z to a) by Freq->word attribute.
//
// ::params: target - array continaing frequency structs
// ::params: first - first index of the portion of the array
// ::params: last - last index of the portion of the array
// ::return: Array of frequency structs (portion of which is
// sorted in lexicographically reverse order)
Freq** sort_rlexicographical(Freq** target, int first, int last);

// sort the frequency structs array by their Freq->times
// attribute, using quicksort
//
// ::params: target - the frequency array
// ::params: first - first index of the array
// ::params: first - last index of the array
// ::return: Sorted array of frequency structs
Freq** quicksort_freqs(Freq** target, int first, int last);

// print Frequency array in reverse order, which displays
// the data as in historgram (from bigger to smaller)
//
// ::params: target - the frequency array
// ::params: size - size of the array
void print_reverse(Freq** target, int size);



int main(int argc, char* argv[])
{

    // get number from the user
    int size = get_pos_num("Please enter a number of words > ", 0);

    Histogram* histogram = malloc(sizeof(Histogram));
    histogram->freqs = malloc(size * sizeof(Freq*));
    histogram->size = 0;

    char** words = (char**)malloc(size * sizeof(char*));
    for (int i = 0; i < size; i++) {
        words[i] = (char*)malloc(MAX_STRING * sizeof(char));
    }

    // get words from the user
    for (int i = 0; i < size; i++) {
        words[i] = get_word("Enter word > ", words[i]);
    }

    int duplicates;
    int is_duplicate;
    int hist_size = 0;

    // initialize the array of duplicates
    char** duplicated = (char**)malloc(size * sizeof(char*));
    for (int i = 0; i < size; i++) {
        duplicated[i] = (char*)calloc(MAX_STRING+1, sizeof(char));
        /*duplicated[i] = (char*)malloc(MAX_STRING);*/
        /*duplicated[i] = (char*)calloc(MAX_STRING + 1, sizeof(char));*/
    }

    // count the duplicates of each word and add the word with its duplicate count
    // to the frequency array, and then - to the histogram struct. Each word is
    // writtern once, without duplication.
    for (int i = 0; i < size; i++) { 
        is_duplicate = 0;

        // if the word is already added to the duplicate list, 
        // it means that its duplicates are already counted,
        // so the loop iteration is skipped
        for (int k = 0; k < size; k++) {
            if (strcmp(duplicated[k], words[i]) == 0) {
                is_duplicate = 1;
            }
        }

        // skipping the loop iteration
        if (is_duplicate) {
            continue;
        }

        // found the word about which we are not yet sure
        // whether it has any duplicates.
        duplicates = 1;
        Freq* freq = malloc(sizeof(Freq));
        freq->word = (char*)malloc(sizeof(MAX_STRING * sizeof(char)));
        freq->word = words[i];
        // searching for the duplicates
        for (int j = i + 1; j < size; j++) {
            if (strcmp(words[i], words[j]) == 0) {
                // in case of a duplicate
                // put word in duplicates array
                // and increase its duplicates count
                duplicated[i] = words[i];
                duplicates++;
            }
        }
        freq->times = duplicates;
        histogram->freqs[histogram->size++] = freq;
        hist_size++;
    }

    debug("Frequency table:");
    for (int i = 0; i < hist_size; i++) {
        debug("%s %d", histogram->freqs[i]->word, histogram->freqs[i]->times);
    }
    debug("-----------------------");

    histogram->freqs = quicksort_freqs(histogram->freqs, 0, hist_size - 1);

    debug("Sorted frequency table:");
    for (int i = hist_size - 1; i >= 0; i--) {
        debug("%s %d", histogram->freqs[i]->word, histogram->freqs[i]->times);
    }
    debug("-----------------------");

    int max_count = histogram->freqs[hist_size - 1]->times;
    int index = hist_size - 1;
    int index_max;

    // partition the frequency array by the same duplicate times, and
    // pass the partitioned array to reverse lexicographical sort
    // on the go.
    for (int i = max_count; i > 0 && index >= 0; i--) {
        index_max = index;
        if (histogram->freqs[index]->times == i) {
            while (index - 1 >= 0 && histogram->freqs[index - 1]->times == i) {
                index--;
            }
            if (index != index_max) {
                histogram->freqs = sort_rlexicographical(
                    histogram->freqs, index, index_max);
            }
            index--;
        }
    }

    printf("\nLexicographically sorted frequency table:\n");
    print_reverse(histogram->freqs, hist_size);




    for (int i = 0; i < size; i++) {
        free(duplicated[i]);
    }
    free(duplicated);

    for (int i = 0; i < size; i++) {
        free(words[i]);
    }
    free(words);

    for (int i = 0; i < hist_size; i++) {
        free(histogram->freqs[i]->word);
    }

    for (int i = 0; i < hist_size; i++) {
        free(histogram->freqs[i]);
    }
    free(histogram->freqs);
    free(histogram);


    return 0;
}

Freq** quicksort_freqs(Freq** target, int first, int last)
{
    Freq* temp;
    int pivot, j, i;

    if (first < last) {
        pivot = first;
        i = first;
        j = last;

        while (i < j) {
            while (target[i]->times <= target[pivot]->times && i < last) {
                i++;
            }
            while (target[j]->times > target[pivot]->times) {
                j--;
            }
            if (i < j) {
                temp = target[i];
                target[i] = target[j];
                target[j] = temp;
            }
        }
        temp = target[pivot];
        target[pivot] = target[j];
        target[j] = temp;

        quicksort_freqs(target, first, j - 1);
        quicksort_freqs(target, j + 1, last);
    }
    return target;
}

Freq** sort_rlexicographical(Freq** target, int first, int last) 
{
    int i, j;
    Freq* temp;

    for (i = first; i < last; ++i)

        for (j = i + 1; j < last + 1; ++j) {

            if (strcmp(target[i]->word, target[j]->word) < 0) {
                temp = target[i];
                target[i] = target[j];
                target[j] = temp;
            }
        }

    debug("In lexicographical reverse order:");
    for (i = 0; i < last + 1; ++i) {
        debug("%s", target[i]->word);
    }
    debug("-----------------------");

    return target;
}

void print_reverse(Freq** target, int size) {
    for (int i = size - 1; i >= 0; i--) {
        printf("%s ", target[i]->word);
        printf("%d \n", target[i]->times);
    }
}

Invalid free at points:

196    for (int i = 0; i < size; i++) {
197        free(words[i]);
198    }

and:

201    for (int i = 0; i < hist_size; i++) {
202        free(histogram->freqs[i]->word);
203    }

My program in action:

➜  tmp1 ./kontrolinis2
Please enter a number of words > 4
Enter word > test1
Enter word > test1
Enter word > test2
Enter word > test2
DEBUG kontrolinis2.c:150: Frequency table:
DEBUG kontrolinis2.c:152: test1 2
DEBUG kontrolinis2.c:152: test2 2
DEBUG kontrolinis2.c:154: -----------------------
DEBUG kontrolinis2.c:158: Sorted frequency table:
DEBUG kontrolinis2.c:160: test1 2
DEBUG kontrolinis2.c:160: test2 2
DEBUG kontrolinis2.c:162: -----------------------
DEBUG kontrolinis2.c:264: In lexicographical reverse order:
DEBUG kontrolinis2.c:266: test2
DEBUG kontrolinis2.c:266: test1
DEBUG kontrolinis2.c:268: -----------------------

Lexicographically sorted frequency table:
test1 2
test2 2

Valgrind output (with the same "user" input):

Lexicographically sorted frequency table:
test1 2
test2 2
==9430== Invalid free() / delete / delete[] / realloc()
==9430==    at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x1091D4: main (kontrolinis2.c:197)
==9430==  Address 0x51f19d0 is 0 bytes inside a block of size 50 free'd
==9430==    at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x109194: main (kontrolinis2.c:192)
==9430==  Block was alloc'd at
==9430==    at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x108C77: main (kontrolinis2.c:89)
==9430==
==9430== Invalid free() / delete / delete[] / realloc()
==9430==    at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x109217: main (kontrolinis2.c:202)
==9430==  Address 0x51f1ad0 is 0 bytes inside a block of size 50 free'd
==9430==    at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x109194: main (kontrolinis2.c:192)
==9430==  Block was alloc'd at
==9430==    at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x108C77: main (kontrolinis2.c:89)
==9430==
==9430==
==9430== HEAP SUMMARY:
==9430==     in use at exit: 118 bytes in 4 blocks
==9430==   total heap usage: 18 allocs, 18 frees, 2,612 bytes allocated
==9430==
==9430== 16 bytes in 2 blocks are definitely lost in loss record 1 of 2
==9430==    at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x108DC7: main (kontrolinis2.c:133)
==9430==
==9430== 102 bytes in 2 blocks are definitely lost in loss record 2 of 2
==9430==    at 0x4C2EF35: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x108D23: main (kontrolinis2.c:104)
==9430==
==9430== LEAK SUMMARY:
==9430==    definitely lost: 118 bytes in 4 blocks
==9430==    indirectly lost: 0 bytes in 0 blocks
==9430==      possibly lost: 0 bytes in 0 blocks
==9430==    still reachable: 0 bytes in 0 blocks
==9430==         suppressed: 0 bytes in 0 blocks
==9430==
==9430== For counts of detected and suppressed errors, rerun with: -v
==9430== ERROR SUMMARY: 6 errors from 4 contexts (suppressed: 0 from 0)

Correct me whether I should have pasted not the whole program, but the main parts of it, or some kind of working prototype. However, the main details here are lines containing keywords "malloc" and "free".

UPDATE: Appending two functions from the library, that are used here: "get_pos_num" and "get_word":

char* get_word(char* message, char* output)
{

    while (1) {
        printf("%s", message);
        if (scanf("%s", output) == 1 && getchar() == '\n') {
            break;
        } else {
            while (getchar() != '\n')
                ;
            printf("Error: not a string, or too many arguments\n");
        }
    }

    return output;
}

int get_pos_num(char* message, int zero_allowed)
{
    int num;
    int margin;

    if (zero_allowed) {
        margin = 0;
    } else {
        margin = 1;
    }

    while (1) {
        printf("%s", message);
        if (scanf("%d", &num) == 1 && getchar() == '\n') {
            if (num >= margin) {
                break;
            } else {
                printf("Error: number is not positive");
                if (zero_allowed) {
                    printf(" or zero");
                }
                printf("\n");
            }
        } else {
            while (getchar() != '\n')
                ;
            printf("Error: not a number\n");
        }
    }

    return num;
}

Answer 1

Well the obvious problem is here:

freq->word = (char*)malloc(sizeof(MAX_STRING * sizeof(char)));
freq->word = words[i];

you allocate memory for freq->word and the overwrite it with words[i].

You later on free the words and then free the many freq you've assigned into the histogram structures.

If you want to copy words[i] you should either use

freq->word = strdup(words[i]);

or

freq->word = malloc(strlen(words[i])+1);
strcpy(freq->word,words[i]);

Also noticed you do the same thing here too

duplicated[i] = words[i];

both will cause you to leak memory as you're losing track of the allocated memory.

And another thing (I seem to be Columbo today) is that you have

sizeof(MAX_STRING * sizeof(char)) in the malloc above which should be just MAX_STRING * sizeof(char). Not sure entirely what result you'd get, but it'd be either 4 or 8 bytes.