Menu
▾
▴
[Valgrind-developers] Valgrind: r16041 - in /trunk: ./ coregrind/ include/ memcheck/ memcheck/tests/
|
From: <sv...@va...> - 2016-10-15 09:30:47
|
Author: philippe
Date: Sat Oct 15 10:30:39 2016
New Revision: 16041
Log:
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
Added:
trunk/memcheck/tests/leak-autofreepool-6.stderr.exp
trunk/memcheck/tests/leak-autofreepool-6.vgtest
Modified:
trunk/NEWS
trunk/coregrind/m_hashtable.c
trunk/include/pub_tool_hashtable.h
trunk/memcheck/mc_malloc_wrappers.c
trunk/memcheck/tests/Makefile.am
trunk/memcheck/tests/leak-autofreepool.c
Modified: trunk/NEWS
==============================================================================
--- trunk/NEWS (original)
+++ trunk/NEWS Sat Oct 15 10:30:39 2016
@@ -179,6 +179,7 @@
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 @@
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]
Modified: trunk/coregrind/m_hashtable.c
==============================================================================
--- trunk/coregrind/m_hashtable.c (original)
+++ trunk/coregrind/m_hashtable.c Sat Oct 15 10:30:39 2016
@@ -365,7 +365,9 @@
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 @@
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;
Modified: trunk/include/pub_tool_hashtable.h
==============================================================================
--- trunk/include/pub_tool_hashtable.h (original)
+++ trunk/include/pub_tool_hashtable.h Sat Oct 15 10:30:39 2016
@@ -121,6 +121,14 @@
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*) );
Modified: trunk/memcheck/mc_malloc_wrappers.c
==============================================================================
--- trunk/memcheck/mc_malloc_wrappers.c (original)
+++ trunk/memcheck/mc_malloc_wrappers.c Sat Oct 15 10:30:39 2016
@@ -681,7 +681,6 @@
{
MC_Chunk *mc;
ThreadId tid;
- Bool found;
tl_assert(mp->auto_free);
@@ -693,23 +692,18 @@
tid = VG_(get_running_tid)();
- do {
- found = False;
+ 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));
+ }
- 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));
- }
-
- 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,
Modified: trunk/memcheck/tests/Makefile.am
==============================================================================
--- trunk/memcheck/tests/Makefile.am (original)
+++ trunk/memcheck/tests/Makefile.am Sat Oct 15 10:30:39 2016
@@ -162,6 +162,7 @@
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 \
Added: trunk/memcheck/tests/leak-autofreepool-6.stderr.exp
==============================================================================
--- trunk/memcheck/tests/leak-autofreepool-6.stderr.exp (added)
+++ trunk/memcheck/tests/leak-autofreepool-6.stderr.exp Sat Oct 15 10:30:39 2016
@@ -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)
Added: trunk/memcheck/tests/leak-autofreepool-6.vgtest
==============================================================================
--- trunk/memcheck/tests/leak-autofreepool-6.vgtest (added)
+++ trunk/memcheck/tests/leak-autofreepool-6.vgtest Sat Oct 15 10:30:39 2016
@@ -0,0 +1,4 @@
+prog: leak-autofreepool
+vgopts: --leak-check=full --show-possibly-lost=no --track-origins=yes
+args: 6
+stderr_filter: filter_overlaperror
Modified: trunk/memcheck/tests/leak-autofreepool.c
==============================================================================
--- trunk/memcheck/tests/leak-autofreepool.c (original)
+++ trunk/memcheck/tests/leak-autofreepool.c Sat Oct 15 10:30:39 2016
@@ -43,16 +43,22 @@
#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 @@
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 @@
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 @@
// 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 @@
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;
|
