From 7ac00163a31c6664e150511e2562ec7ac15dbe0c Mon Sep 17 00:00:00 2001 From: Philippe Waroquiers Date: Sat, 15 Oct 2016 09:30:39 +0000 Subject: [PATCH] fix 369468 Remove quadratic metapool alg. using VG_(HT_remove_at_Iter)(VgHashTable *table) Based on a patch from Ruurd Beerstra but reworked VG_(HT_remove_at_Iter) so that the function is implemented without touching the rest of m_hashtable.c to ensure no performance impact on other hash table usages. Testing with for f in 1 2 3 4 5 6 7 8 9; do echo $f; time ./vg-in-place -q ./memcheck/tests/leak-autofreepool 2 $(expr $f \* 100000); done|&grep user With the patch : user 0m0.524s user 0m0.660s user 0m0.784s user 0m0.916s user 0m1.064s user 0m1.192s user 0m1.316s user 0m1.496s user 0m1.632s Without the patch, the same gives: user 0m4.464s user 0m16.776s user 0m24.472s user 1m5.544s user 1m21.168s user 1m40.500s user 1m54.884s user 4m58.308s user 5m34.060s git-svn-id: svn://svn.valgrind.org/valgrind/trunk@16041 --- NEWS | 7 +- coregrind/m_hashtable.c | 35 +++++++- include/pub_tool_hashtable.h | 8 ++ memcheck/mc_malloc_wrappers.c | 26 +++--- memcheck/tests/Makefile.am | 1 + memcheck/tests/leak-autofreepool-6.stderr.exp | 10 +++ memcheck/tests/leak-autofreepool-6.vgtest | 4 + memcheck/tests/leak-autofreepool.c | 83 ++++++++++++++++++- 8 files changed, 151 insertions(+), 23 deletions(-) create mode 100644 memcheck/tests/leak-autofreepool-6.stderr.exp create mode 100644 memcheck/tests/leak-autofreepool-6.vgtest diff --git a/NEWS b/NEWS index b2f34c98a2..2049bc789b 100644 --- a/NEWS +++ b/NEWS @@ -179,6 +179,7 @@ where XXXXXX is the bug number as listed below. 369000 AMD64 fma4 instructions unsupported. 361253 [s390x] ex_clone.c:42: undefined reference to `pthread_create' 369169 ppc64 fails jm_int_isa_2_07 test +369175 jm_vec_isa_2_07 test crashes on ppc64 369209 valgrind loops and eats up all memory if cwd doesn't exist. 369356 pre_mem_read_sockaddr syscall wrapper can crash with bad sockaddr 369359 msghdr_foreachfield can crash when handling bad iovec @@ -190,12 +191,14 @@ where XXXXXX is the bug number as listed below. 369441 bad lvec argument crashes process_vm_readv/writev syscall wrappers 369446 valgrind crashes on unknown fcntl command 369439 S390x: Unhandled insns RISBLG/RISBHG and LDE/LDER -369175 jm_vec_isa_2_07 test crashes on ppc64 +369468 Remove quadratic metapool alg. using VG_(HT_remove_at_Iter) + (VgHashTable *table) 370265 ISA 3.0 HW cap stuff needs updating n-i-bz Fix incorrect (or infinite loop) unwind on RHEL7 x86 and amd64 n-i-bz massif --pages-as-heap=yes does not report peak caused by mmap+munmap -n-i-bz false positive leaks due to aspacemgr merging non heap segments with heap segments. +n-i-bz false positive leaks due to aspacemgr merging non heap segments + with heap segments. n-i-bz Fix ppoll_alarm exclusion on OS X n-i-bz Document brk segment limitation, reference manual in limit reached msg. n-i-bz Fix clobber list in none/tests/amd64/xacq_xrel.c [valgrind r15737] diff --git a/coregrind/m_hashtable.c b/coregrind/m_hashtable.c index fd6bb4230b..20910036b9 100644 --- a/coregrind/m_hashtable.c +++ b/coregrind/m_hashtable.c @@ -365,7 +365,9 @@ void* VG_(HT_Next)(VgHashTable *table) vg_assert(table); /* See long comment on HT_Next prototype in pub_tool_hashtable.h. In short if this fails, it means the caller tried to modify the - table whilst iterating over it, which is a bug. */ + table whilst iterating over it, which is a bug. + One exception: HT_remove_at_Iter can remove the current entry and + leave the iterator in a valid state for HT_Next. */ vg_assert(table->iterOK); if (table->iterNode && table->iterNode->next) { @@ -383,6 +385,37 @@ void* VG_(HT_Next)(VgHashTable *table) return NULL; } +void VG_(HT_remove_at_Iter)(VgHashTable *table) +{ + vg_assert(table); + vg_assert(table->iterOK); + vg_assert(table->iterNode); + + const UInt curChain = table->iterChain - 1; // chain of iterNode. + + + if (table->chains[curChain] == table->iterNode) { + /* iterNode is the first of its chain -> remove it from the chain. */ + table->chains[curChain] = table->iterNode->next; + /* Setup the iterator to visit first node of curChain: */ + table->iterNode = NULL; + table->iterChain = curChain; + } else { + /* iterNode is somewhere inside curChain chain */ + VgHashNode* prev = table->chains[curChain]; + + while (prev->next != table->iterNode) + prev = prev->next; + /* Remove iterNode from the chain. */ + prev->next = table->iterNode->next; + /* Setup the iterator to visit prev->next, which is the node + that was after the deleted node. */ + table->iterNode = prev; + } + + table->n_elements--; +} + void VG_(HT_destruct)(VgHashTable *table, void(*freenode_fn)(void*)) { UInt i; diff --git a/include/pub_tool_hashtable.h b/include/pub_tool_hashtable.h index e5c41cc1df..a6cbe1cc3d 100644 --- a/include/pub_tool_hashtable.h +++ b/include/pub_tool_hashtable.h @@ -121,6 +121,14 @@ extern void VG_(HT_ResetIter) ( VgHashTable *table ); assurance. */ extern void* VG_(HT_Next) ( VgHashTable *table ); +/* Remove the element pointed to by the iterator and leave the iterator + in a state where VG_(HT_Next) will return the element just after the removed + node. + This allows removing elements from the table whilst iterating over it. + Note that removing an entry does not resize the hash table, making this + safe. */ +extern void VG_(HT_remove_at_Iter)( VgHashTable *table ); + /* Destroy a table and deallocates the memory used by the nodes using freenode_fn.*/ extern void VG_(HT_destruct) ( VgHashTable *table, void(*freenode_fn)(void*) ); diff --git a/memcheck/mc_malloc_wrappers.c b/memcheck/mc_malloc_wrappers.c index e1c7b18c72..8259401c95 100644 --- a/memcheck/mc_malloc_wrappers.c +++ b/memcheck/mc_malloc_wrappers.c @@ -681,7 +681,6 @@ static void free_mallocs_in_mempool_block (MC_Mempool* mp, { MC_Chunk *mc; ThreadId tid; - Bool found; tl_assert(mp->auto_free); @@ -693,23 +692,18 @@ static void free_mallocs_in_mempool_block (MC_Mempool* mp, tid = VG_(get_running_tid)(); - do { - found = False; - - VG_(HT_ResetIter)(MC_(malloc_list)); - while (!found && (mc = VG_(HT_Next)(MC_(malloc_list))) ) { - if (mc->data >= StartAddr && mc->data + mc->szB <= EndAddr) { - if (VG_(clo_verbosity) > 2) { - VG_(message)(Vg_UserMsg, "Auto-free of 0x%lx size=%lu\n", - mc->data, (mc->szB + 0UL)); - } + VG_(HT_ResetIter)(MC_(malloc_list)); + while ( (mc = VG_(HT_Next)(MC_(malloc_list))) ) { + if (mc->data >= StartAddr && mc->data + mc->szB <= EndAddr) { + if (VG_(clo_verbosity) > 2) { + VG_(message)(Vg_UserMsg, "Auto-free of 0x%lx size=%lu\n", + mc->data, (mc->szB + 0UL)); + } - mc = VG_(HT_remove) ( MC_(malloc_list), (UWord) mc->data); - die_and_free_mem(tid, mc, mp->rzB); - found = True; - } + VG_(HT_remove_at_Iter)(MC_(malloc_list)); + die_and_free_mem(tid, mc, mp->rzB); } - } while (found); + } } void MC_(create_mempool)(Addr pool, UInt rzB, Bool is_zeroed, diff --git a/memcheck/tests/Makefile.am b/memcheck/tests/Makefile.am index 616e3f0364..02888cb4cd 100644 --- a/memcheck/tests/Makefile.am +++ b/memcheck/tests/Makefile.am @@ -162,6 +162,7 @@ EXTRA_DIST = \ leak-autofreepool-3.vgtest leak-autofreepool-3.stderr.exp \ leak-autofreepool-4.vgtest leak-autofreepool-4.stderr.exp \ leak-autofreepool-5.vgtest leak-autofreepool-5.stderr.exp \ + leak-autofreepool-6.vgtest leak-autofreepool-6.stderr.exp \ leak-tree.vgtest leak-tree.stderr.exp \ leak-segv-jmp.vgtest leak-segv-jmp.stderr.exp \ lks.vgtest lks.stdout.exp lks.supp lks.stderr.exp \ diff --git a/memcheck/tests/leak-autofreepool-6.stderr.exp b/memcheck/tests/leak-autofreepool-6.stderr.exp new file mode 100644 index 0000000000..4178c4e263 --- /dev/null +++ b/memcheck/tests/leak-autofreepool-6.stderr.exp @@ -0,0 +1,10 @@ + + +HEAP SUMMARY: + in use at exit: ... bytes in ... blocks + total heap usage: ... allocs, ... frees, ... bytes allocated + +All heap blocks were freed -- no leaks are possible + +For counts of detected and suppressed errors, rerun with: -v +ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) diff --git a/memcheck/tests/leak-autofreepool-6.vgtest b/memcheck/tests/leak-autofreepool-6.vgtest new file mode 100644 index 0000000000..f81007ce10 --- /dev/null +++ b/memcheck/tests/leak-autofreepool-6.vgtest @@ -0,0 +1,4 @@ +prog: leak-autofreepool +vgopts: --leak-check=full --show-possibly-lost=no --track-origins=yes +args: 6 +stderr_filter: filter_overlaperror diff --git a/memcheck/tests/leak-autofreepool.c b/memcheck/tests/leak-autofreepool.c index 44da9ebe5c..f918fee324 100644 --- a/memcheck/tests/leak-autofreepool.c +++ b/memcheck/tests/leak-autofreepool.c @@ -43,16 +43,22 @@ static struct pool _MetaPool, *MetaPool = &_MetaPool; #define N 10 #define POOL_BLOCK_SIZE 4096 +#define NOISE_SIZE 256 + // For easy testing, the plain mempool uses N allocations, the // metapool 2 * N (so 10 reported leaks are from the plain pool, 20 must be -// from the metapool. +// from the metapool). static int MetaPoolFlags = 0; static int CleanupBeforeExit = 0; +static int GenerateNoise = 0; +static int NoiseCounter = 0; static struct cell *cells_plain[2 * N]; static struct cell *cells_meta[2 * N]; +static unsigned char *noise[3 * N]; + static char PlainBlock[POOL_BLOCK_SIZE]; static char MetaBlock[POOL_BLOCK_SIZE]; @@ -106,7 +112,7 @@ static void *allocate_plain_style (struct pool *p, size_t n) void *a = p->buf + p->used; assert(p->used + n < p->allocated); - // And this is custom allocator that knows what it is allocating from a pool. + // And this is custom allocator that knows that it is allocating from a pool. VALGRIND_MEMPOOL_ALLOC(p, a, n); p->used += n; @@ -172,11 +178,49 @@ static void set_flags ( int n ) CleanupBeforeExit = 0; break; + case 6: + // Test the VG_(HT_remove_at_Iter)() function, which removes a chunk + // from a hashlist without the need to reset the iterator. The pool + // is auto_freed, and the best test for the function (besides the ones + // already done above) is by allocating lots of other chunks that are + // NOT part of the pool so the MC_Alloc lists contain other stuff. + // That will make the iterator find stuff AND skip stuff. + MetaPoolFlags = VALGRIND_MEMPOOL_AUTO_FREE | VALGRIND_MEMPOOL_METAPOOL; + CleanupBeforeExit = 1; + GenerateNoise = 1; + break; + default: assert(0); } } +static void GenerateNoisyBit (void) +{ + // In case the HT_remove_at_Iter messes up the administration, the wrong + // blocks may be deleted from the list, making access to these noise-blocks + // invalid. So fill 256-byte blocks with easily tested contents. + + noise[NoiseCounter] = malloc(NOISE_SIZE); + assert(noise[NoiseCounter] != NULL); + memset(noise[NoiseCounter],(unsigned char) (NoiseCounter % 256), NOISE_SIZE); + NoiseCounter++; +} + +static void CheckNoiseContents (void) +{ + int i; + + for (i = 0; i < NoiseCounter; i++) { + unsigned char Check = (unsigned char) ( i % 256); + int j; + + for (j = 0; j < NOISE_SIZE; j++) { + assert(noise[i][j] == Check); + } + } +} + int main( int argc, char** argv ) { int arg; @@ -195,11 +239,17 @@ int main( int argc, char** argv ) // N plain allocs for (i = 0; i < N; ++i) { cells_plain[i] = allocate_plain_style(PlainPool,sizeof(struct cell)); + + if (GenerateNoise) + GenerateNoisyBit(); } // 2*N meta allocs for (i = 0; i < 2 * N; ++i) { cells_meta[i] = allocate_meta_style(MetaPool,sizeof(struct cell)); + + if (GenerateNoise) + GenerateNoisyBit(); } // Leak the memory from the pools by losing the pointers. @@ -211,18 +261,43 @@ int main( int argc, char** argv ) cells_meta[i] = NULL; } + if (GenerateNoise) + CheckNoiseContents(); + // This must free MALLOCLIKE allocations from the pool when // VALGRIND_MEMPOOL_AUTO_FREE // is set for the pool and report leaks when not. + if (CleanupBeforeExit) { VALGRIND_MEMPOOL_FREE(MetaPool, MetaBlock); - VALGRIND_DESTROY_MEMPOOL(MetaPool); + + if (GenerateNoise) + CheckNoiseContents(); + + VALGRIND_DESTROY_MEMPOOL(MetaPool); + + if (GenerateNoise) + CheckNoiseContents(); + } // Cleanup. VALGRIND_DESTROY_MEMPOOL(PlainPool); - // Perf test + if (GenerateNoise) + CheckNoiseContents(); + + // Try to trigger an error in the bookkeeping by freeing the noise bits. + // Valgrind should report no leaks, and zero memory in use. If the + // new HT_remove_at_Iter function would corrupt the bookkeeping in any + // way, this should bring it out! + if (GenerateNoise) { + for (i = 0; i < NoiseCounter; i++) + free(noise[i]); + } + + + // Perf test if (argc == 3) { struct pool perf_plain_pool; void *perf_plain_block; -- 2.47.2