malloc() crashes, saying corrupted double-linked list

Question

Edit Full source is here:

http://code.seanwoods.com/reynard.fossil.cgi/artifact/0cc9cbfbe021c2ba86dcb4d0cf6ada52f0a80063

Calling program here:

http://code.seanwoods.com/reynard.fossil.cgi/artifact/891405e62c95349aaf461dfb8ba82259f77fac9b

I've got a relatively simple memory allocation that's failing. The application is not particularly complicated although it does allocate memory in a few places. It's C, not C++. I'm positive this is an issue allocating memory, not freeing memory.

Here's the code:

printf(":2 %d %d\n", initial_len, initial_len * sizeof(char));
o->data = (char*) malloc(initial_len * sizeof(char));
printf(":3 \n");

Upon execution, I get:

:1
:2 1024 1024
*** glibc detected *** ./menv: corrupted double-linked list: 0x0000000001d14400 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x76d76)[0x7f680cfc4d76]
/lib/x86_64-linux-gnu/libc.so.6(+0x771ed)[0x7f680cfc51ed]
/lib/x86_64-linux-gnu/libc.so.6(+0x794d4)[0x7f680cfc74d4]
/lib/x86_64-linux-gnu/libc.so.6(__libc_malloc+0x70)[0x7f680cfc9b90]
./menv[0x403971]
./menv[0x40391d]
./menv[0x4030ec]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xfd)[0x7f680cf6cead]
./menv[0x401369]
======= Memory map: ========
00400000-00405000 r-xp 00000000 08:03 2621441                            /home/swoods/code/reynard/modules/stdlib/menv
00605000-00606000 rw-p 00005000 08:03 2621441                            /home/swoods/code/reynard/modules/stdlib/menv
00606000-00706000 rw-p 00000000 00:00 0 
01cfd000-01d3d000 rw-p 00000000 00:00 0                                  [heap]
7f6808000000-7f6808021000 rw-p 00000000 00:00 0 
7f6808021000-7f680c000000 ---p 00000000 00:00 0 
7f680cd38000-7f680cd4d000 r-xp 00000000 08:05 10354962                   /lib/x86_64-linux-gnu/libgcc_s.so.1
7f680cd4d000-7f680cf4d000 ---p 00015000 08:05 10354962                   /lib/x86_64-linux-gnu/libgcc_s.so.1
7f680cf4d000-7f680cf4e000 rw-p 00015000 08:05 10354962                   /lib/x86_64-linux-gnu/libgcc_s.so.1
7f680cf4e000-7f680d0ce000 r-xp 00000000 08:05 10354980                   /lib/x86_64-linux-gnu/libc-2.13.so
7f680d0ce000-7f680d2ce000 ---p 00180000 08:05 10354980                   /lib/x86_64-linux-gnu/libc-2.13.so
7f680d2ce000-7f680d2d2000 r--p 00180000 08:05 10354980                   /lib/x86_64-linux-gnu/libc-2.13.so
7f680d2d2000-7f680d2d3000 rw-p 00184000 08:05 10354980                   /lib/x86_64-linux-gnu/libc-2.13.so
7f680d2d3000-7f680d2d8000 rw-p 00000000 00:00 0 
7f680d2d8000-7f680d2da000 r-xp 00000000 08:05 10354973                   /lib/x86_64-linux-gnu/libdl-2.13.so
7f680d2da000-7f680d4da000 ---p 00002000 08:05 10354973                   /lib/x86_64-linux-gnu/libdl-2.13.so
7f680d4da000-7f680d4db000 r--p 00002000 08:05 10354973                   /lib/x86_64-linux-gnu/libdl-2.13.so
7f680d4db000-7f680d4dc000 rw-p 00003000 08:05 10354973                   /lib/x86_64-linux-gnu/libdl-2.13.so
7f680d4dc000-7f680d4fc000 r-xp 00000000 08:05 10354984                   /lib/x86_64-linux-gnu/ld-2.13.so
7f680d6df000-7f680d6e2000 rw-p 00000000 00:00 0 
7f680d6f8000-7f680d6fb000 rw-p 00000000 00:00 0 
7f680d6fb000-7f680d6fc000 r--p 0001f000 08:05 10354984                   /lib/x86_64-linux-gnu/ld-2.13.so
7f680d6fc000-7f680d6fd000 rw-p 00020000 08:05 10354984                   /lib/x86_64-linux-gnu/ld-2.13.so
7f680d6fd000-7f680d6fe000 rw-p 00000000 00:00 0 
7ffff3bd6000-7ffff3bf7000 rw-p 00000000 00:00 0                          [stack]
7ffff3bff000-7ffff3c00000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Aborted

• The code compiles without issue.
• When I run it "standalone," it crashes with the error above. I see :2 but I don't see :3, which tells me it's an error within malloc. (I hope I'm wrong.)
• When I run the same binary through valgrind, it works as expected.
• It does not appear to be an issue with the variable declaration o->data, which is a char*. If I declare char* A; A = instead of o->data = it still crashes.

I would greatly appreciate any ideas as to how to troubleshoot/why this happens.

Thanks!

Answer 1

So, I think I found it. We may need to file this under "Sean needs to learn basic Valgrind skills." Here's how I solved it for any future observers.

1. Okay, we're dealing with a really strange error thrown by a tried and tested library function, so it must be something specific to my setup. The algorithm is the same, so it must be the data.
2. The dynamic memory implementation has an underlying data structure to track allocated memory, which happens to be a doubly linked list -- thus the message.
3. So, there must be a memory operation somewhere that corrupts this data structure in a subtle way.
4. Okay, what tools do we have at our disposal? Valgrind is highly praised, let's try that. Strange, it works in Valgrind. Hmm.
5. Actually read what Valgrind is telling you. (This is where I didn't do my part.) It flags you with errors such as "Invalid write of size 1" along with a trace of the various labels/symbols where this shows up. Look for possible errors and adjust as necessary.
6. In this case, it was pointing me to an invocation of memcpy() in the hashtable_put function of hashtable.c. The subtle hint is that I was passing the first argument to memcpy using the address-of operator &, which caused the corruption.
7. When I fixed that, Valgrind no longer complained.

The moral of the story:

• Don't ignore feedback from the tools. No news is [usually] good news, so if Valgrind spits out lots of info their is an increased likelihood of a problem.
• Dynamic memory allocation bugs are subtle (dynamic in the true sense of the word) and can be affected by many variables. Valgrind puts things in the middle of your program and the memory library so it knows what's going on, so I think these affected the program's operation somehow.

The commit that has so far fixed the issue:

http://code.seanwoods.com/reynard.fossil.cgi/ci/bd6a5a23c1?sbs=0