C - Memory leak troubleshooting

Question

So I'm making a code that reads matrices and then does some counting with them.

I allocate memory to store the matrices in and fill it with more allocated arrays and free everything in the end, but Valgrind tells me I have a memory leak when I allocate a memory and then don't free it but when I do free it, the program doesn't work and I get SIGSEGV. It goes as follows:

int main() {
    int ***arrMatrices= (int***) calloc(100, sizeof(int**));
    char *operations = (char*) calloc(100, sizeof(char));

    int heights[100], widths[100];
    int noOfMatrices= 0, output = 0;

    ...

    output = readMatrix(arrMatrices, &noOfMatrices, heights, widths);

    ...

    freeEverything(arrMatrices,noOfMatrices,heights,widths,operations);
    return (0);
}

int readMatrix(int ***arrMatrices, int *noOfMatrices, int *heights, int *widths){
    int height, width;
    int output = scanf("%d %d",&height, &width);
    int result = 1;

    ...

    int **matrix = (int**) calloc(height, sizeof(int*));

    for(int i = 0; i < height; i++){
        int *row = (int*) calloc(width, sizeof(int));
        for(int y = 0; y < width; y++){
            output = scanf("%d",(row+y));
            if(output < 1) result = -1;
        }
        matrix[i] = row;
    }

    arrMatrices[*noOfMatrices] = matrix;

    heights[*noOfMatrices] = height;
    widths[*noOfMatrices] = width;
    *noOfMatrices+=1;

    return result;
}

void freeEverything(int ***arrMatrices, int noOfMatrices, int *heights, int *widths, char *operations){
    for(int i = 0; i < noOfMatrices; i++){
        for(int row = 0; row < heights[i]; row++){
            free(arrMatrices[i][row]);
        }
        printf("%d\n",i);
        free(arrMatrices[i]);
    }
    free(arrMatrices);
    free(operations);
}

So the thing is I read the matrix, load it into my array and return. If I try to free it, I get an error, and apparently freeing it all in the end - row by row and matrix by matrix followed my the whole array - isn't enough. Valgrind specifically says that it's the matrix alloc in readMatrix.

Can anyone tell me just how to do it right?

EDIT (added code + edits as per suggestions):

Here is another snippet of my code - of a following function that multiplies the matrices. There I declare the matrix the same way but I get no memory leak.

int multiply(int ***arrOfMatrices, int firstIndex, int secondIndex, int *heights, int *widths){
    if(widths[firstIndex] != heights[secondIndex]) return -1;

    int **matrix = (int**) calloc(heights[firstIndex],sizeof(int*));

    for(int i = 0; i < heights[firstIndex]; i++){
        int *row = (int*) calloc(widths[secondIndex], sizeof(int));
        for(int y = 0; y < widths[secondIndex]; y++){
            int sum = 0;
            for(int j = 0; j < widths[firstIndex]; j++){
                sum = sum + (arrOfMatrices[firstIndex][i][j] * arrOfMatrices[secondIndex][j][y]);
            }
            row[y] = sum;
        }
        matrix[i] = row;
    }

    arrOfMatrices[secondIndex] = matrix;
    heights[secondIndex] = heights[firstIndex];

    return 1;
}

EDIT 2 (posting the whole code):

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

void printMatrix(int ***arrOfMatrices, int index, int *heights, int *widths){
    int height = heights[index];
    int width = widths[index];

    printf("%d %d\n",height, width);
    for(int i = 0; i < height; i++){
        printf("%d",arrOfMatrices[index][i][0]);
        for(int y = 1; y < width; y++){
            printf(" %d",arrOfMatrices[index][i][y]);
        }
        printf("\n");
    }
}

int readMatrix(int ***arrOfMatrices, int *noOfMatrices, int *heights, int *widths){
    int height, width;
    int output = scanf("%d %d",&height, &width);
    int result = 1;

    if(output < 2){
        fprintf(stderr,"Error\n"); return 100;
    }

    int **matrix = (int**) calloc(height, sizeof(int*));

    for(int i = 0; i < height; i++){
        int *row = (int*) calloc(width, sizeof(int));
        for(int y = 0; y < width; y++){
            output = scanf("%d",(row+y));
            if(output < 1) result = -1;
        }
        matrix[i] = row;
    }

    if(result == -1){
        for(int i = 0; i < height; i++){
            free(matrix[i]);
        }
        free(matrix);
        return result;
    }

    arrOfMatrices[*noOfMatrices] = matrix;

    heights[*noOfMatrices] = height;
    widths[*noOfMatrices] = width;
    *noOfMatrices+=1;

    return result;
}

int multiply(int ***arrOfMatrices, int firstIndex, int secondIndex, int *heights, int *widths){
    if(widths[firstIndex] != heights[secondIndex]) return -1;

    int **matrix = (int**) calloc(heights[firstIndex],sizeof(int*));

    for(int i = 0; i < heights[firstIndex]; i++){
        int *row = (int*) calloc(widths[secondIndex], sizeof(int));
        for(int y = 0; y < widths[secondIndex]; y++){
            int sum = 0;
            for(int j = 0; j < widths[firstIndex]; j++){
                sum = sum + (arrOfMatrices[firstIndex][i][j] * arrOfMatrices[secondIndex][j][y]);
            }
            row[y] = sum;
        }
        matrix[i] = row;
    }

    arrOfMatrices[secondIndex] = matrix;
    heights[secondIndex] = heights[firstIndex];

    //free(matrix);
    return 1;
}

int addSubstract(int ***arrOfMatrices, int firstIndex, int secondIndex, int *heights, int *widths, int modificator){
    if(heights[firstIndex] != heights[secondIndex] || widths[firstIndex] != widths[secondIndex]) return -1;

    for(int i = 0; i < heights[firstIndex]; i++){
        for(int y = 0; y < widths[secondIndex]; y++){
            arrOfMatrices[secondIndex][i][y] = (modificator * arrOfMatrices[secondIndex][i][y]) + arrOfMatrices[firstIndex][i][y];
        }
    }    

    return 1;
}

int countPriorityOperations(int ***arrOfMatrices, char *operations, int noOfMatrices, int *heights, int *widths){
    /*
        Picks all multiplications and counts 'em first
    */
    int output;
    for(int i = 0; i < noOfMatrices-1;i++){
        if(operations[i] == '*'){
            output = multiply(arrOfMatrices,i,i+1,heights,widths);
            if(output == -1) return -1;
        }
    }
    return 1;
}

int countRemainingOperations(int ***arrOfMatrices, char *operations, int noOfMatrices, int *heights, int *widths){
    /*
        Does all the other operations that aren't of the multiply masterrace
        Skips matrices that have already been multiplied
    */
    for(int i = 0; i < noOfMatrices-1;i++){
        if(operations[i] == '*') continue;
        if(operations[i] == '+' || operations[i] == '-'){
            int modificator = 0;
            if(operations[i] == '+') modificator = 1; else modificator = -1;
            if(operations[i+1] != '*'){
                if(addSubstract(arrOfMatrices,i, i+1, heights, widths, modificator) == -1) return -1;
            }else{
                if(addSubstract(arrOfMatrices,i, i+2, heights, widths, modificator) == -1) return -1;
                ++i;
            }
        }
    }
    return 1;
}

void freeEverything(int ***arrOfMatrices, int noOfMatrices, int *heights, int *widths, char *operations){
    for(int i = 0; i < noOfMatrices; i++){
        for(int row = 0; row < heights[i]; row++){
            free(arrOfMatrices[i][row]);
        }
        free(arrOfMatrices[i]);
    }
    free(arrOfMatrices);
    free(operations);
}

int main() {
    int ***arrOfMatrices = (int***) calloc(100, sizeof(int**));
    char *operations = (char*) calloc(100, sizeof(char));
    int heights[100], widths[100];
    int noOfMatrices = 0, output = 0;

    while(output != EOF){
        output = readMatrix(arrOfMatrices, &noOfMatrices, heights, widths);
        if(output == -1){
            fprintf(stderr,"Error\n"); return 100;
        }
        char temp;
        output = scanf(" %c",&temp);
        if(temp != '+' && temp != '-' && temp != '*' && output != EOF){
            fprintf(stderr,"Error\n"); return 100;
        }
        if(output == EOF) break;
        operations[noOfMatrices-1] = temp;      
    }

    if(countPriorityOperations(arrOfMatrices,operations,noOfMatrices, heights, widths) == -1){
        fprintf(stderr,"Error\n"); return 100;
    }

    if(countRemainingOperations(arrOfMatrices,operations,noOfMatrices, heights, widths) == -1){
        fprintf(stderr,"Error\n"); return 100;        
    }

    printMatrix(arrOfMatrices,noOfMatrices-1,heights,widths);
    freeEverything(arrOfMatrices,noOfMatrices,heights,widths,operations);
    return (0);
}

Valgrind output when all the inputs are correct and the program finishes correctly:

==24== HEAP SUMMARY:
==24==     in use at exit: 72 bytes in 4 blocks
==24==   total heap usage: 21 allocs, 17 frees, 1,244 bytes allocated
==24==
==24== 72 (24 direct, 48 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==24==    at 0x4C2C9B4: calloc (vg_replace_malloc.c:711)
==24==    by 0x400896: readMatrix (in [path])
==24==    by 0x40109C: main (in [path])
==24==
==24== LEAK SUMMARY:
==24==    definitely lost: 24 bytes in 1 blocks
==24==    indirectly lost: 48 bytes in 3 blocks
==24==      possibly lost: 0 bytes in 0 blocks
==24==    still reachable: 0 bytes in 0 blocks
==24==         suppressed: 0 bytes in 0 blocks
==24==
==24== For counts of detected and suppressed errors, rerun with: -v
==24== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

[don't cast malloc in C](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) — Barmar, Nov 18 '16 at 23:43

ad absurdum · Accepted Answer · 2016-11-19T17:25:37.257

It is generally a bad idea to edit the code in your question to match suggestions in the answers. It is better to add updates so that the original code is still easily available for inspection. In this case, your original code was working fine, so long as all of the elements of the matrices were entered.

The problems that you describe seem to occur only when a non-numeric value is entered for a matrix element. This makes me think that your intention is to provide a means of escaping from a matrix in the event of a mistake, and entering the values for that matrix again.

As @Mox pointed out, you fail to deallocate some memory here. It isn't entirely clear to me how your segfault is arising, and I have been unable to replicate this behavior.

I made a few changes in readMatrix(). When non-numeric input is encountered (e.g., 'q'), all allocations associated with the current matrix must be freed. Of course, the current row and matrix must be freed, but you also have to free the rows that you have already stored in matrix. The loop accomplishes this, and this must be done before freeing matrix. There is no need to clear the input stream, since the program exits with an error in the case of non-numeric input. Finally, -1 is returned to the calling function.

int readMatrix(int ***arrOfMatrices, int *noOfMatrices, int *heights, int *widths){
    int height, width;
    int output = scanf("%d %d",&height, &width);

    if(output < 2){
        fprintf(stderr,"Error\n"); return 100;
    }

    int **matrix = (int**) calloc(height, sizeof(int*));

    for(int i = 0; i < height; i++){
        int *row = (int*) calloc(width, sizeof(int));
        for(int y = 0; y < width; y++){
            output = scanf("%d",(row+y));
            if(output < 1) {
                for (int j = 0; j < i; j++)  // free previous rows
                    free(matrix[j]);
                free(row);
                free(matrix);
                return -1;
            }
        }
        matrix[i] = row;
    }

    arrOfMatrices[*noOfMatrices] = matrix;

    heights[*noOfMatrices] = height;
    widths[*noOfMatrices] = width;
    *noOfMatrices+=1;

    return 1;
}

There is another source of memory leaks here. Every error exit point must free all malloced memory before returning:

while(output != EOF){
        output = readMatrix(arrOfMatrices, &noOfMatrices, heights, widths);
        if(output == -1){
            freeEverything(arrOfMatrices,noOfMatrices,heights,widths,operations);
            fprintf(stderr,"Error\n"); return 100;
        }
        char temp;
        output = scanf(" %c",&temp);
        if(temp != '+' && temp != '-' && temp != '*' && output != EOF){
            freeEverything(arrOfMatrices,noOfMatrices,heights,widths,operations);           
            fprintf(stderr,"Error\n"); return 100;
        }
        if(output == EOF) break;
        operations[noOfMatrices-1] = temp;      
    }

    if(countPriorityOperations(arrOfMatrices,operations,noOfMatrices, heights, widths) == -1){
        freeEverything(arrOfMatrices,noOfMatrices,heights,widths,operations);           
        fprintf(stderr,"Error\n"); return 100;
    }

    if(countRemainingOperations(arrOfMatrices,operations,noOfMatrices, heights, widths) == -1){
        freeEverything(arrOfMatrices,noOfMatrices,heights,widths,operations);           
        fprintf(stderr,"Error\n"); return 100;        
    }

Having made these changes, I see no further leaks, and Valgrind agrees:

With correct input:

3 3
1 1 1
1 1 1
1 1 1
+
3 3
1 1 1
1 1 1
1 1 1
3 3
2 2 2
2 2 2
2 2 2
==5049== 
==5049== HEAP SUMMARY:
==5049==     in use at exit: 0 bytes in 0 blocks
==5049==   total heap usage: 10 allocs, 10 frees, 1,020 bytes allocated
==5049== 
==5049== All heap blocks were freed -- no leaks are possible
==5049== 
==5049== For counts of detected and suppressed errors, rerun with: -v
==5049== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

With non-numeric input:

3 3
1 1 1
1 1 1
1 1 1
+
3 3
1 1 1
1 q
Error
==5050== 
==5050== HEAP SUMMARY:
==5050==     in use at exit: 0 bytes in 0 blocks
==5050==   total heap usage: 9 allocs, 9 frees, 1,008 bytes allocated
==5050== 
==5050== All heap blocks were freed -- no leaks are possible
==5050== 
==5050== For counts of detected and suppressed errors, rerun with: -v
==5050== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

On another note, triple indirection is almost never the right answer. In this case, I would consider using a struct to store the matrix information:

struct Matrix {
    int **arr;
    size_t rows;
    size_t cols;
};

// ...

struct Matrix *matrices;

This has the advantage of storing the number of rows and columns with the matrix elements, so that you no longer need the heights[] and widths[] arrays. Your function prototypes would also be simplified:

int readMatrix(struct Matrix *matrices, int *noOfMatrices);
void freeEverything(struct Matrix *matrices, int noOfMatrices, char *operations);

EDIT

When you provided the complete code, you should have provided the original code, not the code with changes based on the mistaken assumptions that we have been making. But that is OK; I changed the readMatrix() function back to its original form (I think!) before fixing things. I think that one of the problems you were having is that you had combined elements of the solution provided by @Mox with elements of my original solution. Neither of these solutions were working with the complete picture, and the combination just confused things.

It appears that there is also a problem in your multiply() function. Here you allocate for a new matrix to hold the result of a multiplication, then you replace a matrix in arrOfMatrices[] with this new matrix. But you have to free the old one before you replace it, or you will leak that memory, as you are losing the reference to it. Here is how you can change multiply() to stop leaking memory:

int multiply(int ***arrOfMatrices, int firstIndex, int secondIndex, int *heights, int *widths){
    if(widths[firstIndex] != heights[secondIndex]) return -1;

    int **matrix = (int**) calloc(heights[firstIndex],sizeof(int*));

    for(int i = 0; i < heights[firstIndex]; i++){
        int *row = (int*) calloc(widths[secondIndex], sizeof(int));
        for(int y = 0; y < widths[secondIndex]; y++){
            int sum = 0;
            for(int j = 0; j < widths[firstIndex]; j++){
                sum = sum + (arrOfMatrices[firstIndex][i][j] * arrOfMatrices[secondIndex][j][y]);
            }
            row[y] = sum;
        }
        matrix[i] = row;
    }

    /* Free old allocated memory */
    for (int j = 0; j < heights[secondIndex]; j++)
        free(arrOfMatrices[secondIndex][j]);
    free(arrOfMatrices[secondIndex]);

    arrOfMatrices[secondIndex] = matrix;
    heights[secondIndex] = heights[firstIndex];

    //free(matrix);
    return 1;
}

Maybe I'm dense but running the code normally never causes segfault or any other error - should I input everything correctly or not. Only Valgrind tells me I don't free enough times. For example: I input 4 matrices that I multiply or add/substract, code runs ok but Valgrind says I freed 4 times less than I should, because of the 4 matrices. And it points to that alloc in `readMatrix`. I tried to run the code with the edits you suggested (not the struct but the freeing after returning -1), but it didn't change a thing as far as I could check. — Kešu, Nov 19 '16 at 12:47
I thought that in your original question you reported a segfault when you `free`d the allocations. I never got any segfaults. The code in my answer runs, and Valgrind reports "All heap blocks were freed -- no leaks are possible." The code that you provided is incomplete; it does not allow the input of 4 matrices, only one. If you provide an example of the actual code that has the memory leak (and your posted code did have memory leaks), then maybe we can fix it. — ad absurdum, Nov 19 '16 at 13:31
1) When I return -1 the whole program (from main) `returns 100` as error and prints error into stderr. 2) I didn't think it would be useful to post all 180 lines of code, though I guess I could. But if it helps - from main I call `readMatrix` until there's no operation input after a matrix (+/-/*) → until EOF. I save all matrices into `arrOfMatrices` in the `readMatrix` and the only other time I allocate anything other than what's in `main` or `readMatrix` is in `multiply` where there's no problem in Valgrind. — Kešu, Nov 19 '16 at 14:22
This is why you need to provide a [mcve]. It is ok to post the whole program if that is what it takes to make the issue manifest. I gather that the purpose of the `-1` is not to allow the user to re-enter a matrix, but rather to signal that one of `+`, `-`, or `*` was encountered? This information does change things. You say that there is no issue in `multiply()`, but how is this allocation `free`d? We probably need to see the whole thing. — ad absurdum, Nov 19 '16 at 14:44
The `-1` is to tell `main` that the reading was unsuccessful, for example a letter was provided instead of a number, and to exit the program with `return` value of `100`. I will post the whole code and Valgrind message that I get running it with correct input. — Kešu, Nov 19 '16 at 14:51
It only works for me when there is no multiplication between the matrices ? Valgrind still marks the `readMatrix` allocation as the culprit even though the only thing I change is that I multiply. When I try the input you sent but change the operation to multiplying (*) I get `4` allocs too little. So I guess the problem is not what Valgrind leads me to believe.. — Kešu, Nov 19 '16 at 16:35
I had to switch `for (int j = 0; j < widths[secondIndex]; j++)` for `heights' but the code really does work now and Valgrind is satisfied :) Thanks so much for your extensive help. I really am in over my head with all the asterisks. — Kešu, Nov 19 '16 at 17:15
No problem. You appear to be right about the switch to `heights`. Sorry about that... there is a lot to keep track of in this code. I do think that if you looked into using structs as I was suggesting, you might like the simplification. Just don't break your now-working code! ;) — ad absurdum, Nov 19 '16 at 17:24

Mox · Answer 2 · 2016-11-19T06:51:29.037

Ok the mistake is happening due to your multiple exit point in a function. Let me point it out to you where that is.

int readMatrix(int ***arrMatrices, int *noOfMatrices, int *heights, int *widths){
    int height, width;
    int output = scanf("%d %d",&height, &width);

    ...

    int **matrix = (int**) malloc(height * sizeof(int*));

    for(int i = 0; i < height; i++){
        int *row = (int*) malloc(width * sizeof(int));
        for(int y = 0; y < width; y++){
            output = scanf("%d",(row+y));
            if(output < 1) return -1; // <---- this is the problematic line
        }
        matrix[i] = row;
    }

    arrMatrices[*noOfMatrices] = matrix;

    heights[*noOfMatrices] = height;
    widths[*noOfMatrices] = width;
    *noOfMatrices+=1;

    return 1;
}

The issue comes from your readMatrix function at if(output < 1) return -1;. Think about what actually happens if the code were to exit at this point? the memory allocated for int *row is not freed which cause a memory leak issue.

The solution to this is that you will need to free the row before returning -1. In software engineering, multiple exit points is highly discouraged.

The recommended code change:

int readMatrix(int ***arrMatrices, int *noOfMatrices, int *heights, int *widths){
    int result = 1;
    int height, width;
    int output = scanf("%d %d",&height, &width);

    ...

    int **matrix = (int**) malloc(height * sizeof(int*));

    for(int i = 0; i < height && result; i++){
       int *row = (int*) malloc(width * sizeof(int));
       for(int y = 0; y < width && result; y++){
           output = scanf("%d",(row+y));
           if(output < 1) result =0; // <---- this is the problematic line
       }
       if(result) matrix[i] = row;
       else free(row);
    }

    arrMatrices[*noOfMatrices] = matrix;

    heights[*noOfMatrices] = height;
    widths[*noOfMatrices] = width;
    *noOfMatrices+=1;

    return result;
}

So how is this related to the segfault that you are seeing? Based on the code that I have seen, you have actually initialized the number of rows before hand. Now because of that return statement in the original code, not all your rows are been allocated with a memory location. So in other parts of your code, you tried to access those rows with invalid memory location which leads to a segfault. So you may want to check out those part of the code. =)

Well I tried what you advised but it didn't help. Again - Valgrind points to the other alloc in the function specifically. To the `int **matrix = (int**) malloc(height * sizeof(int*));` — Kešu, Nov 19 '16 at 00:25
@keashi, oh well I can only advice on what I can see, I cant tell you the answer for what is not shown to me. I do hope u know my limitation here. — Mox, Nov 19 '16 at 00:26
@Mox I updated the question a bit but I don't know what more to provide — Kešu, Nov 19 '16 at 00:44
@Mox-- Valgrind reports errors with your code because, when non-numeric input aborts entry, some memory is left uninitialized. We can't tell what the OP wants to do when entry is aborted. In my solution, such an abort starts entry again, so all matrix rows are initialized in the end. In your solution, some rows may not be initialized, even though space has been allocated for them. The simplest way to fix your solution is to change the `malloc` in the allocation of `matrix` to `calloc(height, sizeof(int*))`. — ad absurdum, Nov 19 '16 at 11:56

C - Memory leak troubleshooting

2 Answers2

EDIT