On Fri, Nov 8, 2019 at 15:07, Mark Wielaard <m...@klomp.org> wrote:
Hi,
On Thu, 2019-11-07 at 09:24 -0600, Jonathon Anderson wrote:
On Thu, Nov 7, 2019 at 12:07, Mark Wielaard <m...@klomp.org
<mailto:m...@klomp.org>> wrote:
> 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.
Thanks for explaining. I have now finally pushed this to master.
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.
I still kept the code to handle the Sig8 table with the new
concurrent-
safe code, since I think it is better if we use the new code always
(even in the single threaded case).
So to fix this we do need some mutex to protect the binary search tree
when calling tsearch/tfind? Or do you see other issues too?
The search tree can be handled with a mutex, the issue is with
next_{tu,cu}_offset and the general logic of the function. As an
example: suppose two threads look up in the Sig8 for A and see that its
not currently present. They'll both use __libdw_intern_next_unit to
load CUs (or units, I suppose) until they either find it or run out of
units.
If the entirety of intern_next_unit is wrapped in a mutex, one of the
two will load in the missing entry and finish, while the other has
"missed" it and will keep going until no units remain. The easy
solution is to have the threads check the table again on next_unit
failure for whether the entry has been added, but that incurs a
large-ish overhead for the constant reprobing. The easiest way around
that is to add an interface on the Sig8 table that returns a "probe" on
lookup failure that can be continued with only a handful of atomics
(essentially saving state from the first find). The downside to this
approach is that unit parsing is fully serialized.
If the next_*_offset is handled with a separate mutex or as an atomic
(say, using fetch_add), the same issue occurs but without the mutex
there's no guarantee that another thread isn't currently parsing and
will write the entry soon, so the easy solution doesn't work. Since the
Sig8 key is only known after the parsing is complete, we can't even
insert a "in progress" entry. One solution is to allow for duplicate
parsing (but then next_*_offset would have to be updated *after*
Sig8_Hash_insert), another is to use a condition variable on whether
all the units have been parsed (so threads that don't find what they're
looking for would block until its certain that it doesn't exist).
Both are viable directions, but neither are trivial.
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).
Unfortunately we don't always control the data, so bad abbrev entries
could happen. The extra alloc wouldn't really "leak" because it would
be freed with the Dwarf. So I am not too concerned about that. Is that
the worse that can happen in __libdw_getabbrev? When we goto invalid
the Dwarf_Abbrev would indeed "leak", but it isn't really lost, it
will
get cleaned up when the Dwarf is destroyed.
It wouldn't "leak," but it would be taking up space until the
dwarf_end. Not that I mind (they're really small).
I'm thinking more of the case where the Abbrev_insert returns -1 (entry
collision), in that case the new Abbrev would stick around until the
dwarf_end.
Thanks,
Makr
