[PATCH] lib + libdw: Add and use a concurrent version of the dynamic-size hash table.

[Jonathon Anderson]

On Thu, Nov 7, 2019 at 12:07, Mark Wielaard <mark@klomp.org> wrote:
> Hi,
> 
> On Mon, 2019-11-04 at 10:39 -0600, Jonathon Anderson wrote:
>>  Apologies, I talked with Srdan in person and forgot to relay the
>>  message. He gave me an updated version of the hash table that 
>> handles
>>  that issue (and another previously harmless typo).
> 
> This looks good. I am about to commit this, but would like to confirm
> that the fixes in this change are as intended.
> 
> Looking at the difference between the previous version and this one, 
> it
> incorporates my simplification of FIND and lookup functions. And fixes
> it by making insert_helper consistently return -1 when the value was
> already inserted (hash == hval). And it fixes an issue where we were
> using the the table entry val_ptr instead of the hashval as hash (was
> that the typo? it didn't look harmless).

Yep, those are the changes (plus the Sig8 patch). That typo was 
harmless because hash would be overwritten before its next use (or just 
unused), now with the (hash == hval) clause its always read so the typo 
is fixed.

> 
> Sorry for being pedantic about this. But it is really tricky code, so 
> I
> want to be 100% sure all the above changes were intended.

No worries, I would be worried if you weren't.

Regarding the Sig8 table: I took a close look, and at the moment its 
use is in an area that isn't thread-safe anyway (in particular, 
__libdw_intern_next_unit). Depending on how that is parallelized there 
might be an issue (if its just wrapped with a separate mutex a thread 
might "miss" a CU if its not already in the table), but since that 
region would need inspection at that time anyway I'm fine with either 
option.

This isn't an issue for Dwarf_Abbrev, the worst that can happen there 
is a duplicate alloc and parsing (as long as the DWARF doesn't have 
erroneous abbrev entries, if it does we would need to thread-safe the 
error handling too).

-Jonathon

> 
> Thanks,
> 
> Mark