Currently when a free() of an area that exceeds the freelist-vol amount -- 10^7 bytes by default -- is encountered, the freelist is completely emptied. A better (==more helpful) behaviour would be to keep the freelist and just release the large block. That way, more accesses to freed memory could get caught. This could be taken a bit further: Purify allows setting an threshold beyond which allocations are not put on the equivalent of the freelist. Such an option, with a default in the neighbourhood of 5% of the freelist volume, would keep more useful stuff in the freelist. Relatedly, if a realloc is enountered and the old size is such that the old block will not end up on the freelist, then realloc should not insist on "reallocate and copy" because doing so will use up to twice as much memory as it needs to.
Created attachment 64139 [details] freelist handling improvement This patch provides two improvements in the way the free list is handled in memcheck. (regression tested on f12/x86 and deb5/amd64) First improvement: a new command line option --freelist-big-blocks (default 1000000) specifies the size of "free list big blocks". Such big blocks will be put on the free list, but will be re-cycled first (i.e. in preference to block having a smaller size). This fixes the bug https://bugs.kde.org/show_bug.cgi?id=250065. Technically, the freed list is divided in two lists : small and big blocks. Blocks are first released from the big block list. Note that the above solution was chosen rather than the 'purify inspired solution' suggested in the patch : this solution will still find dangling pointers in big blocks and/or give better error msg). Giving 0 as --freelist-big-blocks gives a behaviour similar to the current trunk Valgrind. Second improvement: the blocks of the freed list are re-cycled before a new block is malloc-ed, not after a block is freed. This gives better error messages for dangling pointer errors when doing many frees without doing malloc between the frees. (this does not uses more memory). Results of the improvements below, with the new regression test memcheck/test/big_blocks_freed_list. Trunk untouched (with --freelist-vol=1000000) ==27630== Invalid read of size 1 ==27630== at 0x804843F: main (big_blocks_freed_list.c:19) ==27630== Address 0x4028410 is not stack'd, malloc'd or (recently) free'd ==27630== ==27630== Invalid read of size 1 ==27630== at 0x8048492: main (big_blocks_freed_list.c:30) ==27630== Address 0x4028032 is not stack'd, malloc'd or (recently) free'd ==27630== ==27630== Invalid read of size 1 ==27630== at 0x80484A5: main (big_blocks_freed_list.c:35) ==27630== Address 0x402a772 is not stack'd, malloc'd or (recently) free'd Patched (with --freelist-vol=1000000 --freelist-big-blocks=50000) Better error messages (improvement 2) + one more dangling pointer error found (improvement 1) ==27640== Invalid read of size 1 ==27640== at 0x804843F: main (big_blocks_freed_list.c:19) ==27640== Address 0x4028410 is 1,000 bytes inside a block of size 1,000,001 free'd ==27640== at 0x4006C8E: free (vg_replace_malloc.c:427) ==27640== by 0x8048435: main (big_blocks_freed_list.c:18) ==27640== ==27640== Invalid read of size 1 ==27640== at 0x8048492: main (big_blocks_freed_list.c:30) ==27640== Address 0x411c2aa is 10 bytes inside a block of size 10,000 free'd ==27640== at 0x4006C8E: free (vg_replace_malloc.c:427) ==27640== by 0x804846E: main (big_blocks_freed_list.c:25) ==27640== ==27640== Invalid read of size 1 ==27640== at 0x80484A5: main (big_blocks_freed_list.c:35) ==27640== Address 0x411e9ea is 10 bytes inside a block of size 1,000,001 free'd ==27640== at 0x4006C8E: free (vg_replace_malloc.c:427) ==27640== by 0x804848A: main (big_blocks_freed_list.c:29) ==27640== ==27640== Invalid read of size 1 ==27640== at 0x8048502: main (big_blocks_freed_list.c:44) ==27640== Address 0x411c2aa is 10 bytes inside a block of size 10,000 free'd ==27640== at 0x4006C8E: free (vg_replace_malloc.c:427) ==27640== by 0x804846E: main (big_blocks_freed_list.c:25)
Created attachment 64336 [details] memcheck freelist handling improvement when large allocation This patch provides three improvements in the way the free list is handled in memcheck. First improvement: a new command line option --freelist-big-blocks (default 1000000) specifies the size of "free list big blocks". Such big blocks will be put on the free list, but will be re-cycled first (i.e. in preference to block having a smaller size). This fixes the bug https://bugs.kde.org/show_bug.cgi?id=250065. Technically, the freed list is divided in two lists : small and big blocks. Blocks are first released from the big block list. Note that the above solution was chosen rather than the 'purify inspired solution' suggested in the bug : this solution will still find dangling pointers in big blocks and/or give better error msg). Giving 0 as --freelist-big-blocks gives a behaviour similar to the current trunk Valgrind. Two alternatives were not retained for --freelist-big-blocks: * specify a percentage of freelist vol (rather than an absolute size) * specific both percentage and (minimum) absolute value (I think these alternatives are more complex to explain/understand without significant advantages). The default value is chosen to be 5% of the default freelist vol size. A default of 0 could have been chosen (this would give the same behaviour for big blocks as the current behaviour). Not too sure it is good to keep the same past behaviour => default of 1000000 instead. Second improvement: the blocks of the freed list are re-cycled before a new block is malloc-ed, not after a block is freed. This gives better error messages for dangling pointer errors when doing many frees without doing malloc between the frees. (this does not uses more memory). Third improvement: a block bigger than the free list volume will be put in the free list (till a malloc is done, so as the needed memory is not bigger than before) but will be put at the beginning of the free list, rather than at the end. So, allocating then freeing such a block does not cause any blocks in the free list to be released. Results of the improvements below, with the new regression test memcheck/test/big_blocks_freed_list : with the patch, 7 errors are detected, 6 are giving the (correct) allocation stack. Without the patch, only 6 errors are detected, 5 errors without allocation stack, 1 with a (wrong) allocation stack. Trunk untouched (with --freelist-vol=1000000) ../trunk_untouched/vg-in-place --freelist-vol=1000000 memcheck/tests/big_blocks_freed_list ... ==8945== ==8945== Invalid read of size 1 ==8945== at 0x8048463: main (big_blocks_freed_list.c:22) ==8945== Address 0x4103fe0 is not stack'd, malloc'd or (recently) free'd ==8945== ==8945== Invalid read of size 1 ==8945== at 0x8048478: main (big_blocks_freed_list.c:23) ==8945== Address 0x4028410 is not stack'd, malloc'd or (recently) free'd ==8945== ==8945== Invalid read of size 1 ==8945== at 0x80484A9: main (big_blocks_freed_list.c:33) ==8945== Address 0x41043c8 is not stack'd, malloc'd or (recently) free'd ==8945== ==8945== Invalid read of size 1 ==8945== at 0x80484BE: main (big_blocks_freed_list.c:34) ==8945== Address 0x40287f8 is 2,000 bytes inside a block of size 10,000 free'd ==8945== at 0x4006C8E: free (vg_replace_malloc.c:427) ==8945== by 0x804849F: main (big_blocks_freed_list.c:28) ==8945== ==8945== Invalid read of size 1 ==8945== at 0x80484F5: main (big_blocks_freed_list.c:41) ==8945== Address 0x4028032 is not stack'd, malloc'd or (recently) free'd ==8945== ==8945== Invalid read of size 1 ==8945== at 0x8048508: main (big_blocks_freed_list.c:46) ==8945== Address 0x402a772 is not stack'd, malloc'd or (recently) free'd ==8945== ==8945== ==8945== HEAP SUMMARY: ... Patched (with --freelist-vol=1000000 --freelist-big-blocks=50000) ==8949== Invalid read of size 1 ==8949== at 0x8048463: main (big_blocks_freed_list.c:22) ==8949== Address 0x4103fe0 is 1,000 bytes inside a block of size 1,000,001 free'd ==8949== at 0x4006C8E: free (vg_replace_malloc.c:427) ==8949== by 0x8048459: main (big_blocks_freed_list.c:21) ==8949== ==8949== Invalid read of size 1 ==8949== at 0x8048478: main (big_blocks_freed_list.c:23) ==8949== Address 0x4028410 is 1,000 bytes inside a block of size 900,000 free'd ==8949== at 0x4006C8E: free (vg_replace_malloc.c:427) ==8949== by 0x804844D: main (big_blocks_freed_list.c:20) ==8949== ==8949== Invalid read of size 1 ==8949== at 0x80484A9: main (big_blocks_freed_list.c:33) ==8949== Address 0x41043c8 is not stack'd, malloc'd or (recently) free'd ==8949== ==8949== Invalid read of size 1 ==8949== at 0x80484BE: main (big_blocks_freed_list.c:34) ==8949== Address 0x40287f8 is 2,000 bytes inside a block of size 900,000 free'd ==8949== at 0x4006C8E: free (vg_replace_malloc.c:427) ==8949== by 0x804844D: main (big_blocks_freed_list.c:20) ==8949== ==8949== Invalid read of size 1 ==8949== at 0x80484F5: main (big_blocks_freed_list.c:41) ==8949== Address 0x41f7e7a is 10 bytes inside a block of size 10,000 free'd ==8949== at 0x4006C8E: free (vg_replace_malloc.c:427) ==8949== by 0x804849F: main (big_blocks_freed_list.c:28) ==8949== ==8949== Invalid read of size 1 ==8949== at 0x8048508: main (big_blocks_freed_list.c:46) ==8949== Address 0x41fa5ba is 10 bytes inside a block of size 1,000,001 free'd ==8949== at 0x4006C8E: free (vg_replace_malloc.c:427) ==8949== by 0x80484ED: main (big_blocks_freed_list.c:40) ==8949== ==8949== Invalid read of size 1 ==8949== at 0x8048565: main (big_blocks_freed_list.c:55) ==8949== Address 0x41f7e7a is 10 bytes inside a block of size 10,000 free'd ==8949== at 0x4006C8E: free (vg_replace_malloc.c:427) ==8949== by 0x804849F: main (big_blocks_freed_list.c:28) ==8949== ==8949== ==8949== HEAP SUMMARY:
Committed, r12202. Thanks!