On Mon, Nov 11, 2019 at 00:23, Mark Wielaard <m...@klomp.org> wrote:
Hi Jonathon,
On Fri, 2019-11-08 at 09:28 -0600, Jonathon Anderson wrote:
> 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.
Thanks, I missed that completely. We do need to fix this, but I might
take a look at it after the next release (which I really would like to
do in about a week). It is indeed not completely trivial. Luckily
debug_types aren't widely used. But if they are used, it would be bad
if it would break a concurrent DIE reader.
> 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.
Since the memblocks are per thread, it seems we could easily back out
an allocation we don't need as long as the thread hasn't done any
other
allocation from the memblock. What do you think of the attached patch?
Looks good to me.
It is a bit hard to test without a massively parallel testcase where
things collide a lot. Since you have one, could you try this out?
Everything seems to work fine on this end.
(Plus, if you replace the `Abbrev_find == NULL` with `1`, you can make
everything collide. Which I did too, and it still works fine.)
Thanks,
Mark
