Why does this introduce a memory leak?

Question

I am implementing an Ant Colony Optimization for the Set Covering Problem in C. In my code, I have found a function that causes a memory leak. I am pretty sure this function is the cause of the memory leak, since I have ruled out other functions by testing. Only, I don't understand why this function introduces a memory leak.

To understand this function, I'll describe the Ant struct first. The Ant struct looks like this:

struct Ant {
    int* x;
    int* y;
    int fx;
    int** col_cover;
    int* ncol_cover;
    int un_rows;
    double* pheromone;
}

typedef struct Ant ant_t;

The pointers in this struct (such as x, y, col_cover, etc.) are initialized using malloc and freed at the end of the program. Now, the function causing the memory leak is the following:

void localSearch(ant_t* ant) {
    int improvement = 1;
    ant_t* antcpy = (ant_t*) malloc(sizeof(ant_t));
    initAnt(antcpy);
    copyAnt(ant, antcpy);
    while (improvement) {
        improvement = 0;
        for (int i = 0; i < inst->n; i++) {
            if (antcpy->x[i]) {
                removeSet(inst, antcpy, i);
                while (!isSolution(antcpy)) {
                    constructSolution(antcpy);
                }
                if (antcpy->fx < ant->fx) {
                    copyAnt(antcpy, ant);
                    improvement = 1;
                    eliminate(ant);
                } else {
                    copyAnt(ant, antcpy);
                }
            }
        }
    }
    free((void*) antcpy);
}

First, I create another instance of the Ant struct (antcpy), using the initAnt function. The copyAnt function does a deep copy of one Ant struct to another Ant struct. My reason for doing a deep copy is the following; I am changing the antcpy and then comparing it to ant. If it turns out better (antcpy->fx < ant->fx), ant is replaced by antcpy. If it turns out worse, antcpy is restored to the values of ant.

These functions are given below:

void initAnt(ant_t* ant) {
    ant->x = (int*) malloc(inst->n * sizeof(int));
    ant->y = (int*) malloc(inst->m * sizeof(int));
    ant->col_cover = (int**) malloc(inst->m * sizeof(int*));
    ant->ncol_cover = (int*) malloc(inst->m * sizeof(int));
    ant->pheromone = (double*) malloc(inst->n * sizeof(double));
    for (int i = 0; i < inst->m; i++) {
        ant->col_cover[i] = (int*) malloc(inst->ncol[i] * sizeof(int));
    }
}

void copyAnt(ant_t* from, ant_t* to) {
    to->fx = from->fx;
    to->un_rows = from->un_rows;
    for (int i = 0; i < inst->n; i++) {
        to->x[i] = from->x[i];
        to->pheromone[i] = from->pheromone[i];
    }
    for (int i = 0; i < inst->m; i++) {
        to->y[i] = from->y[i];
        to->ncol_cover[i] = from->ncol_cover[i];
        for (int j = 0; j < inst->ncol[i]; j++) {
            to->col_cover[i][j] = from->col_cover[i][j];
        }
    }
}

I don't really see why this code causes a memory leak, since I free antcpy at the end of the localSearch function. So, why does this code introduce a memory leak and how can I fix it?

Where do you release the memory allocated in initAnt? I suppose mymalloc does some sort of alloc... — Adrian Roman, Apr 14 '16 at 17:47
@AdrianRoman `mymalloc` is just a wrapper around `malloc`. Is the memory allocated in `initAnt` not freed by freeing `antcpy` at the end of the `localSearch` function? — JNevens, Apr 14 '16 at 17:49
there's this ongoing battle: http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc — yano, Apr 14 '16 at 17:49

score 2 · Accepted Answer · edited Apr 14 '16 at 17:58

2

You will have to implement a function freeAnt that before free((void*) antcpy); will release all memory that was allocated in initAnt.

void freeAnt(ant_t* ant) {
    for (int i = 0; i < inst->m; i++) {
        free(ant->col_cover[i]);
    }
    free(ant->pheromone);
    free(ant->ncol_cover);
    free(ant->col_cover);
    free(ant->y);
    free(ant->x);
}

edited Apr 14 '16 at 17:58

ikegami

367,544
15
269
518

answered Apr 14 '16 at 17:51

Adrian Roman

534
4
8

So basically a function that does `free(antcpy->x)` for each element of the `Ant` struct? Then what about `col_cover`, since it is an array of arrays. Do I need to free each array inside `col_cover` also, or does `free(antcpy->col_cover)` take care of this? – JNevens Apr 14 '16 at 17:53
2

For each `malloc`, there should be a corresponding `free`, so no, `free(antcpy->col_cover)`, won't be sufficient. – ikegami Apr 14 '16 at 17:55
Yes, each of the pointers that point to allocated memory. That includes col_cover. First you do a `for (int i = 0; i < inst->m; i++) { free(ant->col_cover[i]); }` only after that `free(ant->col_cover);`. `free(ant)` comes last. That is, in reverse than at allocation. – Adrian Roman Apr 14 '16 at 17:55
2

In general (of course there are exceptions) I think it's good practice to `free` memory as a mirror image of how it was `malloc`ed. But yes, every `malloc` should have a corresponding `free` (again there can be [exceptions](http://stackoverflow.com/questions/36584062/should-i-free-memory-before-exit) – yano Apr 14 '16 at 17:58

Why does this introduce a memory leak?

1 Answers1