How do I avoid memory leak when concat string pointers in C

Question

I am working on a parser for a programming languages class and am having a memory leak issue while turning my expression tree to a string in the preorder arrangement. Before i had it that when allocating memory to string in exprToString it was 100 * sizeof(char), however the mem leakage results were far greater. So, i got rid of the 100 * but i still get non ascii printouts and the odd recurring "retu"...

char* concat(const char *s1, const char *s2)
{
    char *result = malloc(strlen(s1)+strlen(s2)+1);//+1 for the null-
    terminator
    //free(result);
    //in real code you would check for errors in malloc here
    strcpy(result, s1);
    strcat(result, s2);
    return result;
}

char* exprToString(Expr* ex){
    char *string = (char*)malloc(sizeof(char));
    //free(string);
    if(strcmp(ex->value,"18killstreak") == 0){
        return " ";
    }
    string = concat(string,ex->value);
    string = concat(string,exprToString(ex->a));
    string = concat(string,exprToString(ex->b));
    return string;
}

here is a sample expression: z / ( x + 2 * x ) here is the printout : 0etur/z +x *2 x

Whats happening?

Answer 1

There are (at least) two serious bugs in the current code in the question:

char* exprToString(Expr* ex){
    char *string = (char*)malloc(sizeof(char));
    //free(string);
    if(strcmp(ex->value,"18killstreak") == 0){
        return " ";
    }
    string = concat(string,ex->value);
    string = concat(string,exprToString(ex->a));
    string = concat(string,exprToString(ex->b));
    return string;
}

First, and most subtle, is that you sometimes (mostly) return pointer to allocated memory, but sometimes return a pointer to a constant string. That means the calling code cannot reliably call free() on the returned value, which either leads to subtle (or maybe not so subtle) memory corruption when the returned pointer is freed or it leads to leaks because the returned pointer is never freed. Neither is satisfactory. Make sure that if you return a pointer, it can uniformly be released. Consider returning a NULL pointer instead of the single-blank string, but if you must return the single-blank string, make sure you allocate it. Note that the early return leaks memory too, completely unnecessarily.

Second, and more serious, you have to preserve pointers to the memory returned by concat so you can free all except the value returned to the caller.

The first problem is at:

char *string = (char*)malloc(sizeof(char));

You don't check the memory allocation succeeded. You don't ensure that you have a string. You need *string = '\0'; to be safe.

Then you have:

string = concat(string, ex->value);

After this, you've lost the only pointer to the memory allocated by the first malloc() — which is the very definition of a memory leak. The next two lines make the same mistake; you've leaked 3 blocks of memory before you return.

One solution to this is:

char* exprToString(Expr* ex){
    if (strcmp(ex->value, "18killstreak") == 0){
        return 0;
    }
    char *string = (char*)malloc(sizeof(char));
    if (string == 0)
        return 0;
    *string = '\0';
    char *t1 = concat(string, ex->value);
    free(string);
    string = t1;
    t1 = concat(string, exprToString(ex->a));
    free(string);
    string = t1;
    string = concat(string, exprToString(ex->b));
    free(string);
    string = t1;
    return string;
}

That begins to look unpleasantly repetitive. An alternative solution changes concat() — both the code and the semantics. If you demand that the first pointer be a pointer to freeable (reallocatable) memory, you can use:

char *concat(char *s1, const char *s2)
{
    if (s1 == 0)
        return 0;
    size_t len_1 = strlen(s1);
    size_t len_2 = strlen(s2);
    char *result = realloc(s1, len_1 + len_2 + 1);
    if (result == 0)
    {
        free(s1);
        return 0;
    }
    strcat(result, s2);
    return result;
}

Now you can use a slightly modified version of your original code:

  char* exprToString(Expr* ex){
    if (strcmp(ex->value, "18killstreak") == 0){
        return 0;
    }
    char *string = (char*)malloc(sizeof(char));
    if (string == 0)
        return 0;
    *string = '\0';
    string = concat(string, ex->value);
    string = concat(string, exprToString(ex->a));
    string = concat(string, exprToString(ex->b));
    return string;
}

Now there are only options on more leaks because exprToString() returns a pointer to allocated memory that you never free. There are multiple ways to deal with that, too. One such is for concat() to be redefined to take two pointers to freeable (reallocatable) memory and free the second pointer before returning. You then have to worry about the call string = concat(string, ex->value); — one safe alternative would be string = concat(string, strdup(ex->value));, for example. (At least, it's safe if the concat() function checks for null pointers.)

There may be other problems I've not spotted yet. The suggested code has not been past a compiler — there could be bugs in it. In particular, I've not fully tracked what happens after every possible explicit allocation failure; there could be issues in the error recovery code.

There are those who are adamantly opposed to casting the result of malloc(). I'm not adamant about it if you guarantee that you compile with options that ensure that malloc() is declared before it is used. I followed the original code in leaving the casts in place.

Answer 2

Here's where the memory leak is coming from:

char *string = (char*)malloc(sizeof(char));
...
string = concat(string,ex->value);
string = concat(string,exprToString(ex->a));
string = concat(string,exprToString(ex->b));

Every time you call concat, you overwrite the current value of string, which contains a pointer to malloc'ed memory, with a new pointer value, discarding the old value.

You should change concat to use realloc on the first parameter if it is not NULL. That way you can grow the buffer as needed. On the initial call to concat, you would set the first parameter to NULL.

So modify concat to use realloc:

char* concat(const char *s1, const char *s2)
{
    char *result;
    if (s1) {
        result = realloc(s1, strlen(s1)+strlen(s2)+1);
        if (!result) {
            perror("realloc failed");
            free(s1);
            return NULL;
        }
        strcpy(result, s2);
    } else {
        result = malloc(strlen(s2)+1);
        if (!result) {
            perror("malloc failed");
            return NULL;
        }
        strcat(result, s2);
    }
    return result;
}

Then you change exprToString to :

char* exprToString(Expr* ex){
    if(strcmp(ex->value,"18killstreak") == 0){
        return strdup(" ");
    }
    char *string = concat(NULL,ex->value);
    char *a_str = exprToString(ex->a);
    char *b_str = exprToString(ex->b);
    string = concat(string,a_str);
    string = concat(string,b_str);
    free(a_str);
    free(b_str);
    return string;
}

Note that because this function is expected to return dynamically allocated memory that the base case cannot return a string literal directly. Whoever calls this function is responsible for freeing the buffer that was returned.

Answer 3

your concat function is okay but the start of exprToString is wrong:

    char *string = (char*)malloc(sizeof(char));    
    string = concat(string,ex->value);

you're allocating only a 1 byte string, and it's not even nul-terminated, so further call to concat concatenates some string with undefined length with ex->value.

If what you want is initialize string with a copy of ex-value, just replace the above with:

char *string = strdup(ex->value);

The next problem is a memory leak when doing this:

string = concat(string,exprToString(ex->a));

you're overwriting the previous value of string, so it works but you get a memory leak because you don't have a chance to free the input.

You could change concat so it frees the first argument by calling:

free(s1);

just before returning the result. Or use realloc on s1 so it frees then resizes.

But both are not very handy. What if some caller doesn't read the docs, needs the string for something else, of if you're passing a literal as first argument ? That would make your concat function not so useful and error prone (unless it's called with a very special name for this very special purpose)

The simplest way is to decompose your concat call:

char *temp = concat(string,ex->value);
free(string);
string = temp;

C language doesn't have a lot of magic behind the scenes, like operator overloading or garbage collection, so everything must be written explicitly.