Hi Aaron, Going through this now. I skipped it before because I don't feel comfortable reviewing the valgrind annotations. For now I am ignoring them.
On Wed, Sep 30, 2026 at 03:05:38PM -0400, Aaron Merey wrote: > libdw's concurrent hash tables currently take an rwlock for every > FIND operation, adding significant overhead for FIND-heavy workloads. > > Modify FIND to avoid taking a lock when the hash table isn't being > resized. To ensure that table pointers always remain valid for all > threads, do not free the prior table when allocating a new one during > resize. All tables are freed during the hash table FREE operation. > Excess memory consumed by old tables is always less than the size > of the current table. > > dwflst_tracker_end now calls hash table FREE to ensure that all > tables are freed. Previously it manually freed the hash table. I am not sure I understand why dwflst_tracker_end wasn't doing that before. Why was it taking the lock and do a manual free? Is this change independent of the rest of the patch? If so just make this change separately first. > To facilitate this lock-free design, entry 0 of a hash table now > stores its size and a pointer to the hash table used before the > last resize (if any). I don't love this. It feels like double bookkeeping (the htab already has a size, old_size and old_table). And I would like to have this as just two fields before the actual table. But it seems to work because the hash functions skip zero. So this slot was always empty otherwise (and zero means not found). Do we still need the old_size and old_table fields in this scheme? In the old scheme we always tried to get the resize lock while finding. In the new we (atomically) check the resizing state (after we already atomically got the table) and if it is not in resizing state do the lookup without taking the lock. The penalty is that given there could always be someone still "finding" in the old table we can never free it. I wonder if we can somehow register the number of currently "finding" threads and drop the old table if it goes to zero? > Also add valgrind annotations to the lock-free path. Add > ANNOTATE_HAPPENS_BEFORE before atomic store/fetch operations and > ANNOTATE_HAPPENS_AFTER after the corresponding atomic loads. > > VALGRIND_HG_DISABLE_CHECKING is used on htab->table before its > __atomic_store_n call to prevent helgrind false positives since there > is no definite order to whether lock-free loads of this pointer occur > before or after this store. So going to ignore this for now. It might be completely correct, but I am not sure I fully understand it. > Signed-off-by: Aaron Merey <[email protected]> > --- > lib/dynamicsizehash_concurrent.c | 104 +++++++++++++++----- > lib/dynamicsizehash_concurrent.h | 5 +- > libdwfl_stacktrace/dwflst_process_tracker.c | 6 +- > 3 files changed, 85 insertions(+), 30 deletions(-) > > diff --git a/lib/dynamicsizehash_concurrent.c > b/lib/dynamicsizehash_concurrent.c > index ba57405f..71357140 100644 > --- a/lib/dynamicsizehash_concurrent.c > +++ b/lib/dynamicsizehash_concurrent.c > @@ -38,37 +38,45 @@ > TYPE data type of the hash table entries > */ > > +/* Name of the table entry type. */ > +#define ENTRY(name) _ENTRY (name) > +#define _ENTRY(name) \ > + name##_ent OK, that is the name/type of an DYNHASHENTTYPE? > static size_t > -lookup (NAME *htab, HASHTYPE hval) > +lookup (ENTRY(NAME) *table, size_t size, HASHTYPE hval) > { OK, we now get passed a table directly (so we don't have to derefence through htab) and the (current) size. > /* First hash function: simply take the modulus 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); > + size_t idx = 1 + (hval < size ? hval : hval % size); OK, so we prevent zero here. So idx zero is free. > HASHTYPE hash; > > - hash = atomic_load_explicit(&htab->table[idx].hashval, > - memory_order_acquire); > + hash = atomic_load_explicit(&table[idx].hashval, memory_order_acquire); > if (hash == hval) ACK. No more dereferencing. Use table and size directly. > - return idx; > + { > + ANNOTATE_HAPPENS_AFTER (&table[idx].hashval); > + return idx; > + } > else if (hash == 0) > return 0; Ignoring. > /* Second hash function as suggested in [Knuth]. */ > - HASHTYPE second_hash = 1 + hval % (htab->size - 2); > + HASHTYPE second_hash = 1 + hval % (size - 2); OK, avoid zero here too. > for(;;) > { > if (idx <= second_hash) > - idx = htab->size + idx - second_hash; > + idx = size + idx - second_hash; > else > idx -= second_hash; > > - hash = atomic_load_explicit(&htab->table[idx].hashval, > - memory_order_acquire); > + hash = atomic_load_explicit(&table[idx].hashval, memory_order_acquire); > if (hash == hval) ACK. No more dereferencing. Use table and size directly. > - return idx; > + { > + ANNOTATE_HAPPENS_AFTER (&table[idx].hashval); > + return idx; > + } > else if (hash == 0) > return 0; > } Ignoring. > @@ -267,7 +275,7 @@ static void resize_helper(NAME *htab, int blocking) > > /* Called by the main thread holding the htab->resize_rwl lock to > coordinate the moving of hash table data. Allocates the new hash > - table and frees the old one when moving all data is done. */ > + table. */ > static void > resize_coordinator(NAME *htab) > { > @@ -277,8 +285,19 @@ resize_coordinator(NAME *htab) > htab->old_table = htab->table; > > htab->size = next_prime(htab->size * 2); > - htab->table = malloc((1 + htab->size) * sizeof(htab->table[0])); > - assert(htab->table); > + > + ENTRY(NAME) *table = malloc((1 + htab->size) * sizeof(htab->table[0])); > + assert(table); Urgh. Existing issue. But meh, so malloc cannot fail. > + /* Store this table's size with the table itself. */ > + atomic_init (&table[0].hashval, htab->size); > + > + /* Preserve old_table in case other threads are reading it. */ > + atomic_init (&table[0].val_ptr, (uintptr_t) htab->old_table); > + > + ANNOTATE_HAPPENS_BEFORE (&htab->table); > + VALGRIND_HG_DISABLE_CHECKING (&htab->table, sizeof (htab->table)); Ignoring. > + __atomic_store_n(&htab->table, table, __ATOMIC_RELEASE); OK, atomicly setting table to match the atomically getting of the table. > /* Change state from ALLOCATING_MEMORY to MOVING_DATA */ > ANNOTATE_HAPPENS_BEFORE (&htab->resizing_state); > @@ -305,12 +324,11 @@ resize_coordinator(NAME *htab) > atomic_store_explicit(&htab->next_move_block, 0, memory_order_relaxed); > atomic_store_explicit(&htab->num_moved_blocks, 0, memory_order_relaxed); > > - free(htab->old_table); Meh, we don't know who is using it, so can never free (till destroy). > /* Change state to NO_RESIZING */ > + ANNOTATE_HAPPENS_BEFORE (&htab->resizing_state); Ignoring (this isn't new code, so was this missing before?) > atomic_fetch_xor_explicit(&htab->resizing_state, CLEANING ^ NO_RESIZING, > - memory_order_relaxed); > - > + memory_order_release); > } Suprious whitespace change. > /* Called by any thread that wants to do an insert or find operation > @@ -388,7 +406,12 @@ INIT(NAME) (NAME *htab, size_t init_size) > if (htab->table == NULL) > return -1; > > - for (size_t i = 0; i <= init_size; i++) > + /* Entry zero stores the size of this table as well as the previous table > + used prior to the last resize (NULL in this case). */ > + atomic_init(&htab->table[0].hashval, (uintptr_t) init_size); > + atomic_init(&htab->table[0].val_ptr, (uintptr_t) NULL); > + > + for (size_t i = 1; i <= init_size; i++) > { > atomic_init(&htab->table[i].hashval, (uintptr_t) NULL); > atomic_init(&htab->table[i].val_ptr, (uintptr_t) NULL); OK. > @@ -407,7 +430,16 @@ name##_free > FREE(NAME) (NAME *htab) > { > pthread_rwlock_destroy(&htab->resize_rwl); > - free (htab->table); > + > + ENTRY(NAME) *cur = htab->table; > + while (cur != NULL) > + { > + ENTRY(NAME) *t = cur; > + cur = (ENTRY(NAME) *) atomic_load_explicit(&cur[0].val_ptr, > + memory_order_relaxed); > + free (t); > + } > + > return 0; > } OK. > > @@ -491,17 +523,41 @@ TYPE > name##_find > FIND(NAME) (NAME *htab, HASHTYPE hval) > { > - /* If we cannot get the resize_rwl lock someone is resizing > - the hash table, try to help out by moving table data. */ > - while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0) > - resize_worker(htab); OK. > + size_t idx = 0; > > - size_t idx; Why is it necessary to init to zero now? > + /* Snapshot of the current table. This pointer stays valid even if a > + new table is allocated during resize. */ > + ENTRY(NAME) *table = __atomic_load_n(&htab->table, __ATOMIC_ACQUIRE); OK. > + ANNOTATE_HAPPENS_AFTER (&htab->table); Ignoring. > /* Make the hash data nonzero. */ > hval = hval ?: 1; > - idx = lookup(htab, hval); > > + /* Make sure the current table isn't in the middle of a resize with > + uninitialized entries present. */ > + if (atomic_load_explicit(&htab->resizing_state, memory_order_acquire) > + == NO_RESIZING) > + { > + ANNOTATE_HAPPENS_AFTER (&htab->resizing_state); > + > + size_t size = atomic_load_explicit(&table[0].hashval, > + memory_order_acquire); > + > + /* Lock-free check for whether the entry is present. */ > + idx = lookup(table, size, hval); > + > + if (idx == 0) > + return NULL; I think this is wrong. It might not be in this table, but it might be in the new table. So this should fallthrough to the code below that does take that lock. > + return (TYPE) atomic_load_explicit(&table[idx].val_ptr, > + memory_order_acquire); > + } OK. > + /* If we cannot get the resize_rwl lock someone is resizing > + the hash table, try to help out by moving table data. */ > + while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0) > + resize_worker(htab); > + > + idx = lookup(htab->table, htab->size, hval); > if (idx == 0) > { > pthread_rwlock_unlock(&htab->resize_rwl); OK. But see above, if not found in old table (and there is now a new table) we do need to recheck. > diff --git a/lib/dynamicsizehash_concurrent.h > b/lib/dynamicsizehash_concurrent.h > index be7e98f0..7dba72b9 100644 > --- a/lib/dynamicsizehash_concurrent.h > +++ b/lib/dynamicsizehash_concurrent.h > @@ -54,8 +54,9 @@ > /* Defined separately. */ > extern size_t next_prime (size_t seed); > > - > -/* Table entry type. */ > +/* Table entry type. Entry 0 does not hold data and is instead used > + to store the table size and a pointer to the previous table (if a > + resize has occurred). */ > #define _DYNHASHCONENTTYPE(name) \ > typedef struct name##_ent \ > { \ Maybe explicitly add that the hash functions avoid zero as idx? > diff --git a/libdwfl_stacktrace/dwflst_process_tracker.c > b/libdwfl_stacktrace/dwflst_process_tracker.c > index 967c51ec..0e359e86 100644 > --- a/libdwfl_stacktrace/dwflst_process_tracker.c > +++ b/libdwfl_stacktrace/dwflst_process_tracker.c > @@ -168,7 +168,6 @@ void dwflst_tracker_end (Dwflst_Process_Tracker *tracker) > /* HACK to allow iteration of dynamicsizehash_concurrent. */ > /* XXX Based on lib/dynamicsizehash_concurrent.c free(). */ > rwlock_fini (tracker->elftab_lock); > - pthread_rwlock_destroy(&tracker->elftab.resize_rwl); > for (idx = 1; idx <= tracker->elftab.size; idx++) > { > dwflst_tracker_elftab_ent *ent = &tracker->elftab.table[idx]; > @@ -184,11 +183,10 @@ void dwflst_tracker_end (Dwflst_Process_Tracker > *tracker) > elf_end(t->elf); > free(t); /* TODO: Check necessity. */ > } > - free (tracker->elftab.table); > + dwflst_tracker_elftab_free (&tracker->elftab); > > /* XXX Based on lib/dynamicsizehash_concurrent.c free(). */ > rwlock_fini (tracker->dwfltab_lock); > - pthread_rwlock_destroy(&tracker->dwfltab.resize_rwl); > for (idx = 1; idx <= tracker->dwfltab.size; idx++) > { > dwflst_tracker_dwfltab_ent *ent = &tracker->dwfltab.table[idx]; > @@ -201,7 +199,7 @@ void dwflst_tracker_end (Dwflst_Process_Tracker *tracker) > INTUSE(dwfl_end) (t->dwfl); > free(t); > } > - free (tracker->dwfltab.table); > + dwflst_tracker_dwfltab_free (&tracker->dwfltab); > > free (tracker); > } This looks like a change that should be done anyway. Thanks, Mark
