Valgrind không hợp lệ miễn phí, rò rỉ bộ nhớ

Question

Tôi bị lỗi không hợp lệ và bị rò rỉ bộ nhớ. Đây là mã của tôi:

/*============================================================================= 
    | 
    | 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); 
    } 
} 

không hợp lệ miễn phí tại các điểm:

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

và:

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

chương trình của tôi trong hành động:

➜ 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 đầu ra (với cùng một đầu vào "người dùng"):

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) 

Chính xác tôi có nên dán không phải toàn bộ chương trình hay không, nhưng các phần chính của nó, hoặc một số nguyên mẫu làm việc. Tuy nhiên, các chi tiết chính ở đây là các dòng chứa từ khóa "malloc" và "miễn phí".

UPDATE: Phụ thêm hai chức năng từ thư viện, được sử dụng ở đây: "get_pos_num" và "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

Vâng vấn đề rõ ràng là ở đây:

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

bạn phân bổ bộ nhớ cho freq->word và ghi đè nó bằng words[i].

Sau này, bạn miễn phí words và sau đó giải phóng nhiều số freq bạn đã gán vào cấu trúc histogram.

Nếu bạn muốn sao chép words[i] bạn nên thể sử dụng

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

hoặc

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

Cũng nhận thấy bạn làm điều tương tự ở đây quá

duplicated[i] = words[i]; 

cả sẽ làm bạn bộ nhớ bị rò rỉ khi bạn đang mất dấu vết của bộ nhớ được cấp phát.

Và một điều (Tôi dường như Columbo ngày nay) là bạn phải

sizeof(MAX_STRING * sizeof(char)) trong malloc trên đó nên chỉ MAX_STRING * sizeof(char). Không chắc chắn hoàn toàn kết quả bạn sẽ nhận được, nhưng nó sẽ là 4 hoặc 8 byte.