一个小的c程序导致"内存损坏"

Question

我写了一个小程序来打印给定字母集的完整排列.当集合小于26时它运行良好,并且在26或更多时崩溃.崩溃日志说:

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

经过几个小时的调试,仍然不知道根本原因.

PS:如果我删除了释放tmp_done和tmp_todo的这两行,它就不会崩溃,但结果仍然很奇怪,一个意外的"!" 发生在结果中.

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

这是来源:

#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;
}

这是完整的崩溃日志:

[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

问题是strdup().首先你有:

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

这样就分配了一个字符串,在你的情况下是27个字节,并将它们全部设置为nul字符,所以你有\0\0\0...\0\0\0.

接下来你做:

char * tmp_done = strdup(done);

这实际上是简写:

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

不幸的是,strlen27个\0字符是零,而不是27,所以你最终得到一个字节的内存分配,一切都从那里开始走下坡路.