Hi Mark, On Fri, Oct 30, 2026 at 9:47 PM Mark Wielaard <[email protected]> wrote: > > 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.
I'll remove annotations from this patch and post those changes separately after I've taken another look at 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. I will separate this change into its own patch. As discussed on IRC dwflst_tracker_end should have already been using FREE. > > > 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? I will benchmark this approach and compare it to the approach I used in this patch. > > > 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? That's right. > > > 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. Will remove in v2. > > > /* 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? Not necessary, apologies for the spurious change. On Sat, Oct 31, 2026 at 10:21 AM Mark Wielaard <[email protected]> wrote: > [...] > > > > 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. > > Sleeping on it I now think this is actually OK. An insert could race > our lookup. But that isn't really a problem. It could also not have > raced. If we need the key/value to be inserted we can try to insert it > ourselves (it will return -1 if it [now] is there already). > > Falling through every time we don't find something will make us try to > take the lock, which kind of defeats the purpose of this patch. Agreed. Aaron > > > > + 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. > > So we don't need to do a recheck. Just let the caller deal with it. > > Cheers, > > Mark >
