This is the mail archive of the
elfutils-devel@sourceware.org
mailing list for the elfutils project.
Re: [PATCH] lib + libdw: Add and use a concurrent version of the dynamic-size hash table.
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?
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?
Thanks,
Mark
From 24db17a8616883b553c1deffea7950b58ba780cb Mon Sep 17 00:00:00 2001
From: Mark Wielaard <mark@klomp.org>
Date: Mon, 11 Nov 2019 00:15:55 +0100
Subject: [PATCH] libdw: Introduce libdw_unalloc to stop Dwarf_Abbrev leaks.
In the case of reading an invalid abbrev or when reading an abbrev
concurrently the Dwarf_Abbrev just created might leak because it isn't
needed after all. Introduce libdw_unalloc and libdw_typed_unalloc to
unallocate such Dwarf_Abbrevs so they don't leak.
Signed-off-by: Mark Wielaard <mark@klomp.org>
---
libdw/ChangeLog | 9 +++++++++
libdw/dwarf_getabbrev.c | 10 +++++++++-
libdw/libdwP.h | 13 +++++++++++++
libdw/libdw_alloc.c | 12 ++++++++++++
4 files changed, 43 insertions(+), 1 deletion(-)
diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index d308172b..95ac28a7 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,12 @@
+2019-11-10 Mark Wielaard <mark@klomp.org>
+
+ * libdwP.h (libdw_unalloc): New define.
+ (libdw_typed_unalloc): Likewise.
+ (__libdw_thread_tail): New function declaration.
+ * libdw_alloc.c (__libdw_thread_tail): New function.
+ * dwarf_getabbrev.c (__libdw_getabbrev): Call libdw_typed_unalloc
+ when reading invalid data or when hash collission detected.
+
2019-10-28 Jonathon Anderson <jma14@rice.edu>
* libdw_alloc.c: Added __libdw_alloc_tail.
diff --git a/libdw/dwarf_getabbrev.c b/libdw/dwarf_getabbrev.c
index 7e767fc1..13bee493 100644
--- a/libdw/dwarf_getabbrev.c
+++ b/libdw/dwarf_getabbrev.c
@@ -99,6 +99,8 @@ __libdw_getabbrev (Dwarf *dbg, struct Dwarf_CU *cu, Dwarf_Off offset,
/* A duplicate abbrev code at a different offset,
that should never happen. */
invalid:
+ if (! foundit)
+ libdw_typed_unalloc (dbg, Dwarf_Abbrev);
__libdw_seterrno (DWARF_E_INVALID_DWARF);
return NULL;
}
@@ -148,7 +150,13 @@ __libdw_getabbrev (Dwarf *dbg, struct Dwarf_CU *cu, Dwarf_Off offset,
/* Add the entry to the hash table. */
if (cu != NULL && ! foundit)
- (void) Dwarf_Abbrev_Hash_insert (&cu->abbrev_hash, abb->code, abb);
+ if (Dwarf_Abbrev_Hash_insert (&cu->abbrev_hash, abb->code, abb) == -1)
+ {
+ /* The entry was already in the table, remove the one we just
+ created and get the one already inserted. */
+ libdw_typed_unalloc (dbg, Dwarf_Abbrev);
+ abb = Dwarf_Abbrev_Hash_find (&cu->abbrev_hash, code);
+ }
out:
return abb;
diff --git a/libdw/libdwP.h b/libdw/libdwP.h
index 3e1ef59b..36c2acd9 100644
--- a/libdw/libdwP.h
+++ b/libdw/libdwP.h
@@ -599,10 +599,23 @@ extern void __libdw_seterrno (int value) internal_function;
#define libdw_typed_alloc(dbg, type) \
libdw_alloc (dbg, type, sizeof (type), 1)
+/* Can only be used to undo the last libdw_alloc. */
+#define libdw_unalloc(dbg, type, tsize, cnt) \
+ ({ struct libdw_memblock *_tail = __libdw_thread_tail (dbg); \
+ size_t _required = (tsize) * (cnt); \
+ /* We cannot know the padding, it is lost. */ \
+ _tail->remaining += _required; }) \
+
+#define libdw_typed_unalloc(dbg, type) \
+ libdw_unalloc (dbg, type, sizeof (type), 1)
+
/* Callback to choose a thread-local memory allocation stack. */
extern struct libdw_memblock *__libdw_alloc_tail (Dwarf* dbg)
__nonnull_attribute__ (1);
+extern struct libdw_memblock *__libdw_thread_tail (Dwarf* dbg)
+ __nonnull_attribute__ (1);
+
/* Callback to allocate more. */
extern void *__libdw_allocate (Dwarf *dbg, size_t minsize, size_t align)
__attribute__ ((__malloc__)) __nonnull_attribute__ (1);
diff --git a/libdw/libdw_alloc.c b/libdw/libdw_alloc.c
index 0eb02c34..e0281a3d 100644
--- a/libdw/libdw_alloc.c
+++ b/libdw/libdw_alloc.c
@@ -97,6 +97,18 @@ __libdw_alloc_tail (Dwarf *dbg)
return result;
}
+/* Can only be called after a allocation for this thread has already
+ been done, to possibly undo it. */
+struct libdw_memblock *
+__libdw_thread_tail (Dwarf *dbg)
+{
+ struct libdw_memblock *result;
+ pthread_rwlock_rdlock (&dbg->mem_rwl);
+ result = dbg->mem_tails[thread_id];
+ pthread_rwlock_unlock (&dbg->mem_rwl);
+ return result;
+}
+
void *
__libdw_allocate (Dwarf *dbg, size_t minsize, size_t align)
{
--
2.18.1