I wrote a small program to print a complete permutation of a given set of alphabets. It works well when the set was less than 26, and failed for 26 or more. emergency log said:
*** Error in `./a.out': malloc(): memory corruption (fast): 0x0000000000cd56a0 ***
The debugging hours worked, still do not know the reason.
PS: if I delete these 2 lines that will release tmp_done and tmp_todo, this will not work, but the result still looks strange, unexpected "!" occurs as a result.
abcdefghijklmnopqtyuzxwr!sv abcdefghijklmnopqtyuzxwr!vs abcdefghijklmnopqtyuzxws!rv abcdefghijklmnopqtyuzxws!vr abcdefghijklmnopqtyuzxwv!rs
Here is 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)
source share