a small c program causes "memory corruption"

Question

I wrote a small program to print full permutation of given alphabet set. It run well when the set was smaller than 26, and crash on 26 or more. the crash log said:

*** Error in `./a.out': malloc(): memory corruption (fast): 0x0000000000cd56a0 ***

Tried hours of debugging, still not know the root cause.

PS: if i remove these 2 lines that free tmp_done and tmp_todo, it won't crash, but still the result looks weird, an unexpected "!" occurs in the result.

abcdefghijklmnopqtyuzxwr!sv
abcdefghijklmnopqtyuzxwr!vs
abcdefghijklmnopqtyuzxws!rv
abcdefghijklmnopqtyuzxws!vr
abcdefghijklmnopqtyuzxwv!rs

Here's the source:

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


static void __permutation1(char * done, char * todo)
{
    int i = 0;

    for(i=0; i<strlen(todo); i++)
    {
        if (1 == strlen(todo))
        {
            printf("%s%s\n", done, todo); break;
        }
        char * tmp_todo = strdup(todo);
        char * tmp_done = strdup(done);
        char s[2] = {todo[i], 0};

        strcat(tmp_done, s);
        memmove(tmp_todo+i, tmp_todo+i+1, strlen(tmp_todo)-i); // null termincated!
        __permutation1(tmp_done, tmp_todo);
        free((void*)tmp_done); # if i remove these 2 lines, it won't crash
        free((void*)tmp_todo); # if i remove these 2 lines, it won't crash
    }
}


void permutation1(char * str)
{
    char * done = (char *)calloc(1, strlen(str)+1);
    char * todo = strdup(str);

    __permutation1(done, todo);

    free((void *)done);
    free((void *)todo);
}

int main(int argc, char const *argv[])
{
    permutation1("abcdefghijklmnopqrstuvwxyz");
    return 0;
}

Here's the full crash log:

[xxxx@xxxx]$ ./a.out
abcdefghijklmnopqrstuvwx!yz
abcdefghijklmnopqrstuvwx!zy
*** Error in `./a.out': malloc(): memory corruption (fast): 0x0000000000cd56a0 ***
======= Backtrace: =========
/lib64/libc.so.6(+0x7ada4)[0x7f4397621da4]
/lib64/libc.so.6(+0x7ddc7)[0x7f4397624dc7]
/lib64/libc.so.6(__libc_malloc+0x4c)[0x7f4397626fbc]
/lib64/libc.so.6(__strdup+0x1a)[0x7f439762d88a]
./a.out[0x40078e]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x40081f]
./a.out[0x4008ad]
./a.out[0x4008ea]
/lib64/libc.so.6(__libc_start_main+0xf5)[0x7f43975c8b35]
./a.out[0x400669]
======= Memory map: ========
00400000-00401000 r-xp 00000000 fd:02 268801967                          /home/shello/workspace/oss/pincode/c_cpp/interview/a.    out
00600000-00601000 r--p 00000000 fd:02 268801967                          /home/shello/workspace/oss/pincode/c_cpp/interview/a.    out
00601000-00602000 rw-p 00001000 fd:02 268801967                          /home/shello/workspace/oss/pincode/c_cpp/interview/a.    out
00cd5000-00cf6000 rw-p 00000000 00:00 0                                  [heap]
7f4390000000-7f4390021000 rw-p 00000000 00:00 0
7f4390021000-7f4394000000 ---p 00000000 00:00 0
7f4397391000-7f43973a6000 r-xp 00000000 fd:01 201330443                  /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f43973a6000-7f43975a5000 ---p 00015000 fd:01 201330443                  /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f43975a5000-7f43975a6000 r--p 00014000 fd:01 201330443                  /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f43975a6000-7f43975a7000 rw-p 00015000 fd:01 201330443                  /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f43975a7000-7f439775d000 r-xp 00000000 fd:01 201333865                  /usr/lib64/libc-2.17.so
7f439775d000-7f439795d000 ---p 001b6000 fd:01 201333865                  /usr/lib64/libc-2.17.so
7f439795d000-7f4397961000 r--p 001b6000 fd:01 201333865                  /usr/lib64/libc-2.17.so
7f4397961000-7f4397963000 rw-p 001ba000 fd:01 201333865                  /usr/lib64/libc-2.17.so
7f4397963000-7f4397968000 rw-p 00000000 00:00 0
7f4397968000-7f4397988000 r-xp 00000000 fd:01 201327199                  /usr/lib64/ld-2.17.so
7f4397b66000-7f4397b69000 rw-p 00000000 00:00 0
7f4397b84000-7f4397b87000 rw-p 00000000 00:00 0
7f4397b87000-7f4397b88000 r--p 0001f000 fd:01 201327199                  /usr/lib64/ld-2.17.so
7f4397b88000-7f4397b89000 rw-p 00020000 fd:01 201327199                  /usr/lib64/ld-2.17.so
7f4397b89000-7f4397b8a000 rw-p 00000000 00:00 0
7ffca2b33000-7ffca2b54000 rw-p 00000000 00:00 0                          [stack]
7ffca2bb3000-7ffca2bb5000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Aborted (core dumped)

Answer 1

The problem is strdup(). First you have:

char * done = (char *)calloc(1, strlen(str)+1);

This allocates a string of, in your case, 27 bytes and sets them all to the nul character, so you have \0\0\0...\0\0\0.

Next you do:

char * tmp_done = strdup(done);

This is effectively shorthand for:

char * tmp_done = malloc(strlen(done)+1);
strcpy(tmp_done, done);

Unfortunately, the strlen of 27 \0 characters is zero, not 27, so you end up with a one-byte memory allocation, and everything goes downhill from there.