Hi,
Sorry this took so long to review. But it is pretty complex code.
I think I got how it works mostly. It is hard to proof correct though.
How did you convince yourself that the code is correct?
For example I am not sure I can proof that in resize_worker() this
always holds: assert(GET_STATE(resize_state) != NO_RESIZING);
In general the handling of the resizing_state field is pretty tricky.
What is the maximum number of concurrent threads it can handle?
I tried to simplify the code a little. You already observed that
COMPARE can be zero. But it always is. We never try comparing values.
So all the COMPARE and value passing to the find functions can simply
be removed. So if you agree I would like to merge the attached
simplification diff into this patch.
The other dynamic size hash is Dwarf_Sig8_Hash. This also doesn't use
COMPARE (nor ITERATE and REVERSE). I haven't tried to replace that one
with the concurrent version, but I think we should. It is only used
when there are debug type units in the Dwarf. Which is not the default
(and some gcc hackers really don't like them) so you will probably not
encounter them normally. But we should probably make looking them up
also concurrent safe as a followup patch.
I only tested the single-threaded case. It is slightly slower, but not
very much. The previous patch made the code slightly faster, that
slight speed increase is gone now. But that also means it is about on
par with the old version without any concurrent improvements.
It does use a bit more memory though. For each CU the abbrev table
structure is 112 bytes larger. Given that there can be several 1000 CUs
in a (large) Dwarf that means a couple of hundred K of extra memory
use. It is probably acceptable since such files contain 100 MBs of DIE
data.
But I was wondering whether next_init_block and num_initialized_blocks
could be shared with next_move_block and num_moved_blocks. If I
understand the code in resize_helper() correctly then all threads are
either initializing or all threads are moving. So can't we just use one
next_block and one num_blocks field?
I do think the code itself is good. The above are mostly just nitpicks.
But if you could reply and give your thoughts on them that would be
appreciated.
Thanks,
Mark
diff --git a/lib/dynamicsizehash_concurrent.c b/lib/dynamicsizehash_concurrent.c
index d645b143..5fa38713 100644
--- a/lib/dynamicsizehash_concurrent.c
+++ b/lib/dynamicsizehash_concurrent.c
@@ -36,46 +36,24 @@
NAME name of the hash table structure.
TYPE data type of the hash table entries
- COMPARE comparison function taking two pointers to TYPE objects
-
- The following macros if present select features:
-
- ITERATE iterating over the table entries is possible
- REVERSE iterate in reverse order of insert
*/
static size_t
-lookup (NAME *htab, HASHTYPE hval, TYPE val __attribute__ ((unused)))
+lookup (NAME *htab, HASHTYPE hval)
{
/* First hash function: simply take the modul but prevent zero. Small values
can skip the division, which helps performance when this is common. */
size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
-#if COMPARE != 0 /* A handful of tables don't actually compare the entries in
- the table, they instead rely on the hash. In that case, we
- can skip parts that relate to the value. */
- TYPE val_ptr;
-#endif
HASHTYPE hash;
hash = atomic_load_explicit(&htab->table[idx].hashval,
memory_order_acquire);
if (hash == hval)
- {
-#if COMPARE == 0
- return idx;
-#else
- val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
- memory_order_acquire);
- if (COMPARE(val_ptr, val) == 0)
- return idx;
-#endif
- }
+ return idx;
else if (hash == 0)
- {
- return 0;
- }
+ return 0;
/* Second hash function as suggested in [Knuth]. */
HASHTYPE second_hash = 1 + hval % (htab->size - 2);
@@ -90,20 +68,9 @@ lookup (NAME *htab, HASHTYPE hval, TYPE val __attribute__ ((unused)))
hash = atomic_load_explicit(&htab->table[idx].hashval,
memory_order_acquire);
if (hash == hval)
- {
-#if COMPARE == 0
- return idx;
-#else
- val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
- memory_order_acquire);
- if (COMPARE(val_ptr, val) == 0)
- return idx;
-#endif
- }
+ return idx;
else if (hash == 0)
- {
- return 0;
- }
+ return 0;
}
}
@@ -123,8 +90,6 @@ insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
{
val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
memory_order_acquire);
- if (COMPARE(val_ptr, val) != 0)
- return -1;
}
else if (hash == 0)
{
@@ -168,8 +133,6 @@ insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
{
val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
memory_order_acquire);
- if (COMPARE(val_ptr, val) != 0)
- return -1;
}
else if (hash == 0)
{
@@ -495,7 +458,7 @@ TYPE
#define FIND(name) _FIND (name)
#define _FIND(name) \
name##_find
-FIND(NAME) (NAME *htab, HASHTYPE hval, TYPE val)
+FIND(NAME) (NAME *htab, HASHTYPE hval)
{
while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
resize_worker(htab);
@@ -504,7 +467,7 @@ FIND(NAME) (NAME *htab, HASHTYPE hval, TYPE val)
/* Make the hash data nonzero. */
hval = hval ?: 1;
- idx = lookup(htab, hval, val);
+ idx = lookup(htab, hval);
if (idx == 0)
{
diff --git a/lib/dynamicsizehash_concurrent.h b/lib/dynamicsizehash_concurrent.h
index a137cbd0..73e66e91 100644
--- a/lib/dynamicsizehash_concurrent.h
+++ b/lib/dynamicsizehash_concurrent.h
@@ -97,7 +97,7 @@ extern int name##_free (name *htab); \
extern int name##_insert (name *htab, HASHTYPE hval, TYPE data); \
\
/* Find entry in hash table. */ \
-extern TYPE name##_find (name *htab, HASHTYPE hval, TYPE val);
+extern TYPE name##_find (name *htab, HASHTYPE hval);
#define FUNCTIONS(name) _FUNCTIONS (name)
FUNCTIONS (NAME)
diff --git a/libdw/dwarf_abbrev_hash.h b/libdw/dwarf_abbrev_hash.h
index bc3d62c7..a368c598 100644
--- a/libdw/dwarf_abbrev_hash.h
+++ b/libdw/dwarf_abbrev_hash.h
@@ -32,7 +32,6 @@
#define NAME Dwarf_Abbrev_Hash
#define TYPE Dwarf_Abbrev *
-#define COMPARE(a, b) (0)
#include <dynamicsizehash_concurrent.h>
diff --git a/libdw/dwarf_getabbrev.c b/libdw/dwarf_getabbrev.c
index 6a7e981b..7e767fc1 100644
--- a/libdw/dwarf_getabbrev.c
+++ b/libdw/dwarf_getabbrev.c
@@ -83,7 +83,7 @@ __libdw_getabbrev (Dwarf *dbg, struct Dwarf_CU *cu, Dwarf_Off offset,
bool foundit = false;
Dwarf_Abbrev *abb = NULL;
if (cu == NULL
- || (abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL)) == NULL)
+ || (abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code)) == NULL)
{
if (result == NULL)
abb = libdw_typed_alloc (dbg, Dwarf_Abbrev);
diff --git a/libdw/dwarf_tag.c b/libdw/dwarf_tag.c
index 331eaa0d..d784970c 100644
--- a/libdw/dwarf_tag.c
+++ b/libdw/dwarf_tag.c
@@ -45,7 +45,7 @@ __libdw_findabbrev (struct Dwarf_CU *cu, unsigned int code)
return DWARF_END_ABBREV;
/* See whether the entry is already in the hash table. */
- abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code, NULL);
+ abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code);
if (abb == NULL)
while (cu->last_abbrev_offset != (size_t) -1l)
{
