History log of /external/valgrind/coregrind/m_hashtable.c
Revision Date Author Comments (<<< Hide modified files) (Show modified files >>>)
b3a1e4bffbdbbf38304f216af405009868f43628 21-Aug-2015 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates, to include 2015. No functional change.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@15577 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
a5e06c36bf9d93461bc8c4351e960888020ea1c4 05-Aug-2015 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> Fix printf format inconsistencies as pointed out by gcc -Wformat-signedness.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@15499 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
a6a6d9247ac4b1ba7f8dc28000cfcadb8feee85b 05-Aug-2015 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> The number of elements in a hash table cannot be negative.
Let the return type of VG_(HT_count_nodes) reflect that.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@15490 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
6debd8596cb5558b4f33f76434e35154da7fb4ba 22-May-2015 philippe <philippe@a5019735-40e9-0310-863c-91ae7b9d1cf9> Also compare keys before calling cmp in the hash table stats printing


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@15268 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
e437427c93a605ac907137b3307f1f63a1462524 20-May-2015 philippe <philippe@a5019735-40e9-0310-863c-91ae7b9d1cf9> Have the hash table 'gen' functions comparing the key instead of the
cmp function.
Document this in the cmp function comment in pub_tool_hashtable.h



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@15263 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
47124e91145f71f6db7d0a60031fe49a6b6ea141 25-Apr-2015 philippe <philippe@a5019735-40e9-0310-863c-91ae7b9d1cf9> Give statistics about RCEC helgrind hash table chains.
Improve statistic in coregrind hash table


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@15141 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
09a4c794458cdb9dea743fa40e450150a2725257 18-Oct-2014 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> Change the definition of VgHashTable to not have pointer type.
This is (a) consistent with how the other containers are defined
and, more importantly, (b) allows the constification of the hash table API.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@14639 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
64ba574d833e2f78ed1f7fdef4fc926420bcfc8a 19-Jun-2014 philippe <philippe@a5019735-40e9-0310-863c-91ae7b9d1cf9> Improve/fix hash table collision statistics + remove useless space in gdbsrv hostvisibility keywork


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@14053 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
7293d2530f8c60c1060f9f003e214cc341d35266 14-Jun-2014 philippe <philippe@a5019735-40e9-0310-863c-91ae7b9d1cf9> This patch adds a 'de-duplicating memory pool allocator':
include/pub_tool_deduppoolalloc.h
coregrind/pub_core_deduppoolalloc.h
coregrind/m_deduppoolalloc.c
and uses it (currently only) for the strings in m_debuginfo/storage.c
The idea is that such ddup pool allocator will also be used for other
highly duplicated information (e.g. the DiCFSI information), where
significant gains can also be achieved.
The dedup pool for strings also decreases significantly the memory
needed by the read inline information (patch still to be committed,
see bug 278972).

When testing with a big executable (tacot_process),
this reduces the size of the dinfo arena from
trunk: 158941184/109760512 max/curr mmap'd, 156775944/107882728 max/curr,
to
ddup: 157892608/106614784 max/curr mmap'd, 156362160/101414712 max/curr

(so 3Mb less mmap-ed once debug info is read, 1Mb less mmap-ed in peak,
6Mb less allocated once debug info is read).

This is all gained due to the string which changes from:
trunk: 17,434,704 in 266: di.storage.addStr.1
to
ddup: 10,966,608 in 750: di.storage.addStr.1
(6.5Mb less memory used by strings)
The gain in mmap-ed memory is smaller due to fragmentation.
Probably one could decrease the fragmentation by using bigger
size for the dedup pool, but then we would lose memory on the last
allocated pool (and for small libraries, we often do not use much
of a big pool block).
Solution might be to increase the pool size but have a "shrink_block"
operation. To be looked at in the future.

In terms of performance, startup of a big executable (on an old pentium)
is not influenced significantly (something like 0.1 seconds on 15 seconds
startup for a big executable, on a slow pentium).

The dedup pool uses a hash table. The hash function used currently
is the VG_(adler32) check sum. It is reported (and visible also here)
that this checksum is not a very good hash function (many collisions).

To have statistics about collisions, use --stats -v -v -v

As an example of the collisions, on the strings in debug info of memcheck tool on x86,
one obtain:
--4789-- dedupPA:di.storage.addStr.1 9983 allocs (8174 uniq) 11 pools (4820 bytes free in last pool)
--4789-- nr occurences of chains of len N, N-plicated keys, N-plicated elts
--4789-- N: 0 : nr chain 6975, nr keys 0, nr elts 0
--4789-- N: 1 : nr chain 3670, nr keys 6410, nr elts 8174
--4789-- N: 2 : nr chain 1070, nr keys 226, nr elts 0
--4789-- N: 3 : nr chain 304, nr keys 100, nr elts 0
--4789-- N: 4 : nr chain 104, nr keys 84, nr elts 0
--4789-- N: 5 : nr chain 72, nr keys 42, nr elts 0
--4789-- N: 6 : nr chain 44, nr keys 34, nr elts 0
--4789-- N: 7 : nr chain 18, nr keys 13, nr elts 0
--4789-- N: 8 : nr chain 17, nr keys 8, nr elts 0
--4789-- N: 9 : nr chain 4, nr keys 6, nr elts 0
--4789-- N:10 : nr chain 9, nr keys 4, nr elts 0
--4789-- N:11 : nr chain 1, nr keys 0, nr elts 0
--4789-- N:13 : nr chain 1, nr keys 1, nr elts 0
--4789-- total nr of unique chains: 12289, keys 6928, elts 8174
which shows that on 8174 different strings, we have only 6410 strings which have
a unique hash value. As other examples, N:13 line shows we have 13 strings
mapping to the same key. N:14 line shows we have 4 groups of 10 strings mapping to the
same key, etc.
So, adler32 is definitely a bad hash function.
Trials have been done with another hash function, giving a much lower
collision rate. So, a better (but still fast) hash function would probably
be beneficial. To be looked at ...




git-svn-id: svn://svn.valgrind.org/valgrind/trunk@14029 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
0f157ddb404bcde7815a1c5bf2d7e41c114f3d73 18-Oct-2013 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates (20XY-2012 ==> 20XY-2013)


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@13658 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
dbb3584f591710a15a437918c0fc27e300993566 27-Oct-2012 florian <florian@a5019735-40e9-0310-863c-91ae7b9d1cf9> More Char/HChar fixes and constification.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@13088 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
03f8d3fc25f5a45c5826259d1b33b7f310117279 05-Aug-2012 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates to include 2012.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@12843 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
6643e96a72e8530a7c8830c02ffb2fb4aee74c88 17-Jan-2012 philippe <philippe@a5019735-40e9-0310-863c-91ae7b9d1cf9> Fixes 282230 group allocator for small fixed size, use it for MC_Chunk/SEc vbit

* new files include/pub_tool_groupalloc.h and coregrind/m_groupalloc.c
implementing a group allocator (based on helgrind group alloc).
* include/Makefile.am coregrind/Makefile.am : added pub_tool_groupalloc.h
and m_groupalloc.c
* helgrind/libhb_core.c : use pub_tool_groupalloc.h/m_groupalloc.c
instead of the local implementation.
* include/pub_tool_oset.h coregrind/m_oset.c : new function
allowing to create an oset that will use a pool allocator.
new function allowing to clone an oset (so as to share the pool alloc)
* memcheck/tests/unit_oset.c drd/tests/unit_bitmap.c : modified
so that it compiles with the new m_oset.c
* memcheck/mc_main.c : use group alloc for MC_Chunk
memcheck/mc_include.h : declare the MC_Chunk group alloc
* memcheck/mc_main.c : use group alloc for the nodes of the secVBitTable OSet
* include/pub_tool_hashtable.h coregrind/m_hashtable.c : pass the free node
function in the VG_(HT_destruct).
(needed as the hashtable user can allocate a node with its own alloc,
the hash table destroy must be able to free the nodes with the user
own free).
* coregrind/m_gdbserver/m_gdbserver.c : pass free function to VG_(HT_destruct)
* memcheck/mc_replace_strmem.c memcheck/mc_machine.c
memcheck/mc_malloc_wrappers.c memcheck/mc_leakcheck.c
memcheck/mc_errors.c memcheck/mc_translate.c : new include needed
due to group alloc.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@12341 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
ec062e8d96a361af9905b5447027819dfbfee01a 23-Oct-2011 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update all copyright dates, from 20xy-2010 to 20xy-2011.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@12206 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
9eecbbb9a9cbbd30b903c09a9e04d8efc20bda33 03-May-2010 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates to 2010.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@11121 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
b965efb4990bdedc3215ffcca8ea566d25874d26 10-Aug-2009 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Allow custom blocks to overlap with malloc blocks. Fixes bug 100628.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@10765 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
29a5c01528ca7cffe17880a038b4563de920f08d 06-May-2009 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Fix bug #191182, where printing the leak checker results was really slow if
there were a lot of loss records.

The fix was:
- Avoid the O(m * n) looping over the chunks when creating the loss
records, by putting loss records into an OSet instead of a list, which
makes duplicate detection for each chunk an O(log n) operation instead of
an O(n) operation.
- Avoid the looping over loss records which was used to do a poor
man's sort, but was O(n^2). Instead copy pointers to the loss records
from the OSet into an array and sort it normally with VG_(ssort) (n log n,
usually) before printing.

This approach was similar to that used in the patch Philippe attached to the
bug report.

Other changes:
- Added Philippe's test programs in the new memcheck/perf directory. It
used to take 57s on my machine, now it takes 1.6s.
- Cleaned up massif/perf/Makefile.am to be consistent with other Makefiles.
- Improved some comments relating to VgHashTable and OSet.
- Avoided a redundant traversal of the hash table in VG_(HT_to_array), also
identified by Philippe..
- Made memcheck/tests/mempool's results independent of the pointer size, and
thus was able to remove its .stderr.exp64 file.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@9781 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
9f207460d70d38c46c9e81996a3dcdf90961c6db 10-Mar-2009 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Updated copyright years.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@9344 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
9c606bd8634cd6b67bb41fa645b5c639668cfa2d 18-Sep-2008 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Merge all remaining changes from branches/PTRCHECK. These are some
relatively minor extensions to m_debuginfo, a major overhaul of
m_debuginfo/readdwarf3.c to get its space usage under control, and
changes throughout the system to enable heap-use profiling.

The majority of the merged changes were committed into
branches/PTRCHECK as the following revs: 8591 8595 8598 8599 8601 and
8161.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@8621 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
4d474d086188fd1f29fa97dbd84d8ea2e589a9b8 11-Feb-2008 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates ("200X-2007" --> "200X-2008").


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@7398 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
3f94a7d39676262e70c768e5a20a225f1ca36b29 25-Aug-2007 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Changes to m_hashtable:

Allow hashtables to dynamically resize (patch from Christoph
Bartoschek). Results in the following interface changes:

* HT_construct: no need to supply an initial table size.
Instead, supply a text string used to "name" the table, so
that debugging messages ("resizing the table") can say which
one they are resizing.

* Remove VG_(HT_get_node). This exposes the chain structure to
callers (via the next_ptr parameter), which is a problem since
callers could get some info about the chain structure which then
changes when the table is resized. Fortunately is not used.

* Remove VG_(HT_first_match) and VG_(HT_apply_to_all_nodes) as
they are unused.

* Make the iteration mechanism more paranoid, so any adding or
deleting of nodes part way through an iteration causes VG_(HT_next)
to assert.

* Fix the comment on VG_(HT_to_array) so it no longer speaks
specifically about MC's leak detector.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@6778 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
9ebd6e0c607fa30301b1325874eb8de871c21cc5 08-Jan-2007 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@6488 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
0c24f8abab8d8a0862767b0b7101d5d3e46d3b50 17-Oct-2006 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Change authorship.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@6293 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
e4b0bf07b0ee0a18eacc5aba91686ab5fc1d327b 06-Jun-2006 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Update copyright dates.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@5954 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
755e1261257dd5fa9cadfb82cebe95d95d50d2a9 24-Dec-2005 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> Fix read-after-free in VG_(HT_destruct). This fixes
memcheck/tests/mempools. Thanks to Jeroen Witmond for tracking it
down.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@5429 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
1af7972c4bfecc5254556915ce011002a26a69a5 14-Aug-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Added an iterator to VgHashTable.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4407 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
246a9d2e0c66b3f69d7a23f370205a48368843b7 14-Aug-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Changed many, but not all, of the VgHashNode* parameters and return
types in m_hashtable.c to void*. This requires no changes to code
already using VgHashTables, but it allows some previously-required casts
to be removed. I also changed Memcheck and Massif by removing some of
these now-unnecessary casts.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4404 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
34582fb5d483f8f0c426ad24f81bb758400bf3da 11-Aug-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Give variable a better name.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4378 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
f69f945020cbcc35fe0c98c3b223d96c7322a95a 03-Jul-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Changed m_hashtable.c to allow the size of the hash table to be specified
when it is created. Fortunately this didn't affect code outside this
module except for the calls to VG_(HT_construct)().

As a result, we save some memory because not all tables have to be as big
as the ones needed for malloc/free tracking.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4100 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
b882402acf34540effc0fe0020898453459db0b5 03-Jul-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> whoops



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@4099 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
c7561b931e249acf3768ead77638545b0ccaa8f1 19-Jun-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Final commit for the initial modularisation pass:

- Broke part of m_scheduler off into a new module m_threadstate. It
contains ThreadState, VG_(threads)[] and some basic operations on the
thread table. All simple stuff, the complex stuff stays in m_scheduler.
This avoids lots of circular dependencies between m_scheduler and other
modules.

- Managed to finally remove core.h and tool.h, double hurrah!

- Introduced pub_tool_basics.h and pub_core_basics.h, one of which is
include by every single C file.

- Lots of little cleanups and changes related to the above.

- I even did a small amount of documentation updating.




git-svn-id: svn://svn.valgrind.org/valgrind/trunk@3944 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
af1d7dfc9412c09d24ea10118f3fd1082f92e49d 11-Jun-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Having moved VG_(arena_strdup)() out of core.h, core.h no longer
needs to #include pub_core_mallocfree.h. As a result, we need
to #include it explicitly everywhere else.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@3881 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
132bfccd21960e462352175f8553a5bdce8a210c 04-Jun-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Modularised assertions and panics in m_libcassert.

As part of this, killed the VG_STRINGIFY macro, which was used to expand
out names like "VG_(foo)" and "vgPlain_foo" in assertion failure
messages. This is good since we actually want the "VG_(foo)" form used
in these messages.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@3842 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
b326a1a4c126216b1c6c8832f6e97ccbb3153aa4 17-May-2005 sewardj <sewardj@a5019735-40e9-0310-863c-91ae7b9d1cf9> A 4999 entry hashtable is too small when there are a huge number (500k
ish) of blocks simultaneously live, and the client is doing intensive
malloc/frees. Increase the table size 16-fold.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@3752 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
02bc4b8f54227320aa2b9ac4805173e0e2e3eeae 15-May-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Don't mix backticks and apostrophes when quoting words -- eg. use 'foo'
rather than `foo', as www.cl.cam.ac.uk/~mgk25/ucs/quotes.html explains
we should (in more detail than you'd imagine was possible). I did this
both in output messages and in some comments, for consistency.


git-svn-id: svn://svn.valgrind.org/valgrind/trunk@3723 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c
81c00df9ac724e898179dd90e52b2e15deb11fd8 14-May-2005 njn <njn@a5019735-40e9-0310-863c-91ae7b9d1cf9> Modularised vg_hashtable.c as m_hashtable.



git-svn-id: svn://svn.valgrind.org/valgrind/trunk@3710 a5019735-40e9-0310-863c-91ae7b9d1cf9
/external/valgrind/coregrind/m_hashtable.c