Heap corruption while freeing memory

Question

I'm struggling with this piece of code. As the name suggests, function should return array of strings that represents all rotations of a string given as a parameter.

char **str_all_rotations(const char *data) 
{
    int i = 0; /* Loop counter */ 
    len = strlen(data); /* Len of input */ 

    /******************/
    /*  malloc memory */

    char **all_rotations = (char**)malloc(sizeof(char*)* len);
    char *double_data = (char*)malloc(len * 2 * sizeof(char));

    for (i = 0; i < len; i++) 
    {
         all_rotations[i] = (char*)malloc(sizeof(char)* len);
    }

    /*******************/
    /*  Rotations part */

    strcpy(double_data, data);
    strcpy(double_data + len, data);

    for (i = 0; i < len; i++) 
    {
        strncpy(all_rotations[i], double_data + i, len);
        all_rotations[i][len] = '\0';
    }

    free(double_data); /* Release memory */

    return all_rotations;
}

It works fine from algorithmic perspective, but a simple call of this function

char *str = "omgillsetyouonfire";
char **asdf = str_all_rotations(str);

for (int i = 0; i < strlen(str); i++) 
{
    free(asdf[i]);
}

free(asdf);

fails, because of heap corruption. I can't see whats wrong. How does one even debug this kind of errors ?

include the complete minimal program. compile with debug ( -g ) and run gdb to find the point of segfault. and add these details to the question — amdixon, May 31 '15 at 12:13
1. [Do not cast the return value of `malloc()`](http://stackoverflow.com/a/605858/1983495_), 2. Do not use `strlen()` like `for (int i = 0; i < strlen(str); i++)`, it suggests that you don't understand c strings, the length of the string is computed on each iteration. 3. Again you don't understand c strings, your second `strcpy()` is writing one byte after the end of the buffer. 4. `sizeof(char)` is 1 bu definition. — Iharob Al Asimi, May 31 '15 at 12:21
The main suspects are your dynamic allocations, concentrate on them when debugging. — Noam M, May 31 '15 at 12:30

score 2 · Accepted Answer · edited May 23 '17 at 11:51

There are some problems with your code

When you use
```
strcpy(double_data + len, data);
```
you copy one extra byte to double_data, the nul terminator which you didn't allocate space for, so you should allocate space like this
```
char *double_data = malloc(2 * len + 1));
```

The same applies for the allocation in the for loop, namely

all_rotations[i] = (char*)malloc(sizeof(char)* len);

and of course the fix would be

all_rotations[i] = malloc(1 + len);

You never check if malloc() returns NULL, that is bad practice.
Do not cast the return value of malloc()
Do not use strlen() as the condition of a loop unless the length of the string changes inside the loop, because strlen() computes the length of the string on each call, so you are making an O(n) algorithm O(n²).
The standard requires that sizeof(char) == 1, so it's just cluttering your code.

This is your own code fixed to address the issues mentioned above

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

char **
str_all_rotations(const char *const data)
 {
    int    index;
    char **all_rotations;
    char  *double_data;
    int    length;

    if (data == NULL)
        return NULL;
    length        = strlen(data);
    index         = 0;
    all_rotations = malloc(length * sizeof(*all_rotations));
    if (all_rotations == NULL)
        return NULL;
    double_data = malloc(2 * length + 1);
    if (double_data == NULL)
        goto cleanup;
    for (index = 0 ; index < length ; index++)
     {
        all_rotations[index] = malloc(1 + length);
        if (all_rotations[index] != NULL && index < 4)
            continue;
        goto cleanup;
     }
    memcpy(double_data, data, length);
    memcpy(double_data + length, data, length);

    double_data[2 * length] = '\0';
    for (index = 0 ; index < length ; index++)
     {
        memcpy(all_rotations[index], double_data + index, length);
        all_rotations[index][length] = '\0';
     }
    free(double_data);

    return all_rotations;

cleanup:
    while (index >= 0)
        free(all_rotations[index--]);
    free(all_rotations);
    free(double_data);

    return NULL;
 }

int
main(void)
 {
    char  *str  = "omgillsetyouonfire";
    char **asdf = str_all_rotations(str);

    if (asdf != NULL)
     {
        for (int i = 0 ; str[i] != '\0' ; i++)
         {
            printf("%s\n", asdf[i]);
            free(asdf[i]);
         }
        free(asdf);
     }

    return 0;
 }

You made a mistake `char *double_data = malloc(2 * ( 1 + len));` should be `char *double_data = malloc(2 * len + 1 + );` — Ed Heal, May 31 '15 at 12:46
@EdHeal Oops I am allocating the `'\0'` twice!, thanks for pointing it out! — Iharob Al Asimi, May 31 '15 at 13:07
Thanks for the detailed explanation. Your suggestions are great, thank You :) Edit : I'm sorry for including strlen in loop condition and for not checking the return value of malloc, it's just a consequence of editing my original code to be less boilerplate for the actual question. — Nikola Ninkovic, May 31 '15 at 20:34
@NikolaNinkovic never edit the original code if it introduces this kind of things, because it might generate this kind of answer. And though it is good to minimize the sample code, remembert that it must reproduce the problematic behavior. — Iharob Al Asimi, May 31 '15 at 20:52

Heap corruption while freeing memory

1 Answers1