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

[Mark Wielaard]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: no-compare-find-val.diff
Type: text/x-patch
Size: 5627 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/elfutils-devel/attachments/20191025/2b4f75d7/attachment.bin>