Утечка памяти после выделения многомерного массива

Question

Я написал простую программу для чтения любой квадратной матрицы и вычисления ее определителя. Однако, по словам Вальгринда, это, по-видимому, утечка памяти.

Пример сеанса:

./det 
4 23 4 
2 -5 2 
45 2 40 
330.000000 

Вот Valgrind выход:

valgrind --leak-check=full --track-origins=yes ./det                         ⏎ 
==5586== Memcheck, a memory error detector 
==5586== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al. 
==5586== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info 
==5586== Command: ./det 
==5586== 
4 23 4 
==5586== Conditional jump or move depends on uninitialised value(s) 
==5586== at 0x4C2D1CA: strcat (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400EE6: readline (det.c:132) 
==5586== by 0x400B13: parse_into (det.c:53) 
==5586== by 0x40084D: main (det.c:20) 
==5586== Uninitialised value was created by a heap allocation 
==5586== at 0x4C29F90: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x4C2C33F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400EB4: readline (det.c:127) 
==5586== by 0x400B13: parse_into (det.c:53) 
==5586== by 0x40084D: main (det.c:20) 
==5586== 
2 -5 2 
==5586== Conditional jump or move depends on uninitialised value(s) 
==5586== at 0x4C2D1CA: strcat (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400EE6: readline (det.c:132) 
==5586== by 0x400C66: parse_into (det.c:79) 
==5586== by 0x40084D: main (det.c:20) 
==5586== Uninitialised value was created by a heap allocation 
==5586== at 0x4C29F90: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x4C2C33F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400EB4: readline (det.c:127) 
==5586== by 0x400C66: parse_into (det.c:79) 
==5586== by 0x40084D: main (det.c:20) 
==5586== 
45 2 40 
==5586== Invalid read of size 8 
==5586== at 0x400929: determinant (det.c:37) 
==5586== by 0x400864: main (det.c:21) 
==5586== Address 0x51d9040 is 0 bytes inside a block of size 64 free'd 
==5586== at 0x4C2C29E: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400D39: allocate_matrix (det.c:95) 
==5586== by 0x400BFB: parse_into (det.c:72) 
==5586== by 0x40084D: main (det.c:20) 
==5586== 
==5586== Conditional jump or move depends on uninitialised value(s) 
==5586== at 0x400945: determinant (det.c:37) 
==5586== by 0x400864: main (det.c:21) 
==5586== Uninitialised value was created by a heap allocation 
==5586== at 0x4C29F90: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x4C2C33F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400DBD: allocate_matrix (det.c:102) 
==5586== by 0x40083D: main (det.c:19) 
==5586== 
==5586== Conditional jump or move depends on uninitialised value(s) 
==5586== at 0x40094F: determinant (det.c:37) 
==5586== by 0x400864: main (det.c:21) 
==5586== Uninitialised value was created by a heap allocation 
==5586== at 0x4C29F90: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x4C2C33F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400DBD: allocate_matrix (det.c:102) 
==5586== by 0x40083D: main (det.c:19) 
==5586== 
0.000000 
==5586== Invalid read of size 8 
==5586== at 0x400E24: free_matrix (det.c:113) 
==5586== by 0x40087F: main (det.c:22) 
==5586== Address 0x51d9040 is 0 bytes inside a block of size 64 free'd 
==5586== at 0x4C2C29E: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400D39: allocate_matrix (det.c:95) 
==5586== by 0x400BFB: parse_into (det.c:72) 
==5586== by 0x40084D: main (det.c:20) 
==5586== 
==5586== Invalid free()/delete/delete[]/realloc() 
==5586== at 0x4C2B200: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400E4B: free_matrix (det.c:114) 
==5586== by 0x40087F: main (det.c:22) 
==5586== Address 0x51d9040 is 0 bytes inside a block of size 64 free'd 
==5586== at 0x4C2C29E: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400D39: allocate_matrix (det.c:95) 
==5586== by 0x400BFB: parse_into (det.c:72) 
==5586== by 0x40084D: main (det.c:20) 
==5586== 
==5586== 
==5586== HEAP SUMMARY: 
==5586==  in use at exit: 624 bytes in 14 blocks 
==5586== total heap usage: 17 allocs, 4 frees, 761 bytes allocated 
==5586== 
==5586== 8 bytes in 1 blocks are definitely lost in loss record 1 of 6 
==5586== at 0x4C29F90: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x4C2C33F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400EB4: readline (det.c:127) 
==5586== by 0x400B13: parse_into (det.c:53) 
==5586== by 0x40084D: main (det.c:20) 
==5586== 
==5586== 8 bytes in 1 blocks are definitely lost in loss record 2 of 6 
==5586== at 0x4C29F90: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x4C2C33F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400EB4: readline (det.c:127) 
==5586== by 0x400C66: parse_into (det.c:79) 
==5586== by 0x40084D: main (det.c:20) 
==5586== 
==5586== 64 bytes in 1 blocks are definitely lost in loss record 3 of 6 
==5586== at 0x4C29F90: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400B41: parse_into (det.c:59) 
==5586== by 0x40084D: main (det.c:20) 
==5586== 
==5586== 96 (24 direct, 72 indirect) bytes in 1 blocks are definitely lost in loss record 5 of 6 
==5586== at 0x4C2C29E: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400D39: allocate_matrix (det.c:95) 
==5586== by 0x400BFB: parse_into (det.c:72) 
==5586== by 0x40084D: main (det.c:20) 
==5586== 
==5586== 448 bytes in 7 blocks are definitely lost in loss record 6 of 6 
==5586== at 0x4C29F90: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x4C2C33F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==5586== by 0x400DBD: allocate_matrix (det.c:102) 
==5586== by 0x40083D: main (det.c:19) 
==5586== 
==5586== LEAK SUMMARY: 
==5586== definitely lost: 552 bytes in 11 blocks 
==5586== indirectly lost: 72 bytes in 3 blocks 
==5586==  possibly lost: 0 bytes in 0 blocks 
==5586== still reachable: 0 bytes in 0 blocks 
==5586==   suppressed: 0 bytes in 0 blocks 
==5586== 
==5586== For counts of detected and suppressed errors, rerun with: -v 
==5586== ERROR SUMMARY: 13 errors from 12 contexts (suppressed: 0 from 0) 

Я не знаю, почему, но во время сессии Valgrind результат не так! Как он может выводить 330 и 0 с тем же входом? Нужно ли доверять ошибкам Valgrind?

Вот полный код. Как вы можете видеть, я всегда звоню free() после использования кучи.

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

#define MATRIX 8 
#define CHUNK 32 

double determinant(double **, size_t); 
size_t parse_into(double **); 
double **allocate_matrix(double **, size_t); 
void free_matrix(double **); 
char *readline(); 


int main(int argc, char *argv[]) { 
    double **matrix = NULL; 
    size_t N; 
    matrix = allocate_matrix(matrix, MATRIX); 
    N = parse_into(matrix); 
    printf("%lf\n", determinant(matrix, N)); 
    free_matrix(matrix); 
    return 0; 
} 


double determinant(double **matrix, size_t side) { 
    if (side == 1) { 
     return matrix[0][0]; 
    } else if (side == 2) { 
     return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]; 
    } 

    // Make the matrix triangular 
    int i, j, t, r = 1; 
    for (j = 0; j < side; j++) { 
     if (!matrix[j][j]) return 0; 
     for (i = j + 1; i < side; i++) { 
      double ratio = matrix[i][j]/matrix[j][j]; 
      for (t = 0; t < side; t++) { 
       matrix[i][t] -= ratio * matrix[j][t]; 
      } 
     } 
    } 
    for (i = 0; i < side; i++) { 
     r *= matrix[i][i]; 
    } 
    return r; 
} 


size_t parse_into(double **matrix) { 
    char *row = readline(); 
    size_t t; 
    size_t N = 0, M = 0; 
    size_t i = 1, j = 0; 

    int *first_row; 
    if (!(first_row = malloc(MATRIX * sizeof(first_row)))) { 
     puts("Could not allocate memory."); 
     exit(EXIT_FAILURE); 
    } 
    char *number = strtok(row, " "); 
    while (number) { 
     if (N == MATRIX) { 
      first_row = realloc(first_row, 2 * N * sizeof(first_row)); 
     } 
     first_row[N++] = atoi(number); 
     number = strtok(NULL, " "); 
    } 
    M = N; 
    matrix = allocate_matrix(matrix, N); 
    for (t = 0; t < N; t++) { 
     matrix[0][t] = first_row[t]; 
    } 

    while (--M) { 
     j = 0; 
     row = readline(); 
     char *number = strtok(row, " "); 
     while (number) { 
      matrix[i][j++] = atoi(number); 
      number = strtok(NULL, " "); 
     } 
     i++; 
    } 
    free(row); 
    return N; 
} 


double **allocate_matrix(double **matrix, size_t side) { 
    size_t i; 

    if (!(matrix = realloc(matrix, sizeof(*matrix) * side))) { 
     puts("Could not allocate memory."); 
     exit(EXIT_FAILURE); 
    } 

    for (i = 0; i < side; i++) { 
     matrix[i] = NULL; 
     if (!(matrix[i] = realloc(matrix[i], sizeof(matrix[i]) * side))) { 
      puts("Could not allocate memory."); 
      exit(EXIT_FAILURE); 
     } 
    } 
    return matrix; 
} 


void free_matrix(double **matrix) { 
    size_t length = sizeof(matrix[0])/sizeof(matrix[0][0]); 
    while (length--) free(matrix[length]); 
    free(matrix); 
} 


char *readline() { 
    char *input = NULL; 
    char tmpbuf[CHUNK]; 
    size_t inputlen = 0, tmplen = 0; 

    do { 
     fgets(tmpbuf, CHUNK, stdin); 
     tmplen = strlen(tmpbuf); 
     inputlen += tmplen; 
     input = realloc(input, inputlen + 1); 
     if (!input) { 
      puts("Could not allocate memory."); 
      exit(EXIT_FAILURE); 
     } 
     strcat(input, tmpbuf); 
    } while (tmplen == CHUNK - 1 && tmpbuf[CHUNK - 2] != '\n'); 

    return input; 
} 

EDIT Вот правильный и рабочий код, в случае, если кому-то интересно: https://codereview.stackexchange.com/questions/85769/reading-a-matrix-and-computing-the-determinant

Answer 1

С вашим кодом много проблем.

Во-первых, вы неправильно инициализируете указатели, которые вы передаете, на realloc. Вы должны убедиться, что все они либо действительны, либо NULL.Это не так, и в разных местах.

В вашей функции allocate_matrix вы потеряете указатели при перераспределении на меньший размер.

В вашей функции free_matrix, sizeof(matrix[0]) означает sizeof(double*), который является постоянным. Это определенно не то, что вы хотите. То же самое для sizeof(matrix[i]) в allocate_matrix.

В вашем parse_into вы переписываете указатель matrix, но это изменение теряется после вызова, и матрица не будет освобождена.

В той же функции вы звоните только free(row), несмотря на то, что звоните readline несколько раз. readline будет выделять новый буфер при каждом вызове, так как для функции input установлено значение NULL.

Снова в parse_into, вы никогда не освобождаете first_row.

Answer 2

Вы знаете, что вы называете allocate_matrixдважды? Один раз в функции main и снова в функции parse_into. Проблема в том, что выделение, сделанное в parse_into, сделано только для локальной копии аргумента matrix, это изменение не будет передано вызывающей функции.

Это, конечно же, приведет к утечке памяти, а также данные, которые вы читаете, не будут находиться в матрице, выделенной из функции main.

Чтобы решить эту проблему вам необходимо либо пройти matrixпо ссылке (или по крайней мере подражать ему), чтобы parse_into, или придумать другой способ передачи этой новой матрицы обратно main.

Answer 3

Вы выделяете память для matrix в main()

matrix = allocate_matrix(matrix, MATRIX); 
N = parse_into(matrix); 

, но затем в parse_into() выбросить этот указатель (и его память), когда вы делаете

matrix = allocate_matrix(matrix, N); 

У вас также есть потенциальная ошибка. Вы выделяете память, передавая указатель NULL на realloc(). Это будет работать, но когда вы будете free() памяти, вы не сбросите указатель на NULL. Поэтому, если вы повторно использовали этот указатель, скажем, в другой итерации, realloc() не удастся.

Answer 4

Кроме того, обратите внимание, что:

if (!(matrix[i] = realloc(matrix[i], sizeof(matrix[i]) * side))) 

неправильно. sizeof (matrix [i]) - размер указателя, но здесь вы хотите размер double