+// Common logic for version locks
+struct version_lock
+{
+ // The lock itself
+ uintptr_t version_lock;
+};
version_lock must not overflow, right? This means we need a wider
counter on 32-bit, too. glibc contains a 62-bit counter that it uses
for its own data structure.
an overflow is not a problem per se, it is only problematic if we hit
exactly the same value again between lock_optimistic and validate. Note
that these ranges are usually a handful of assembler instructions, and
we would have to see 4 billion frame registrations in that short time
span. I don't think that is a problem in practice. But I can switch to
64bit, of course, if you think the risk is too high.
+// Lock the node exclusive, blocking as needed
+static void
+version_lock_lock_exclusive (struct version_lock *vl)
+{
+ // We should virtually never get contention here, as frame
+ // changes are rare. Thus we use a simple spinlock
Isn't this problematic if there are multiple compiler threads that race
to register their output with the unwinder?
If updates are rare, is per-node locking really needed?
What can we do to make this async-signal-safe, so that a call into the
unwinder from a signal handler does not spin endlessly if the receiving
thread is currently registering or deregistering a frame? Is simply
calling sigprocmask around the register and unregister operations
enough? (These operations don't need to be async-signal-safe, only
lookup should be.) This can be a future change if we feel confident
that it's possible to rectify this later if needed.
we need the locking bit because a concurrent unwinder must recognize
that the node is currently being modified. But we could eliminate the
spinlock aspect by using a global mutex, which would guarantee us that
nothing is locked exclusively and thus no spinning is required. That
would also allow us to fix the async-signal-safety at the same time if
needed by blocking signals globally during updates.
Note that the current code is not async-signal-safe either, it simply
grabs a mutex. If a signal happens while calling __register_frame, and
that handler tries to unwind, the current code will deadlock, too.
+// Validate a previously acquire lock
+static inline bool
+version_lock_validate (const struct version_lock *vl, uintptr_t lock)
+{
+ // Check that the node is still in the same state
+ uintptr_t state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST);
+ return (state == lock);
+}
I think an acquire fence is missing before the __atomic_load_n. We
learned this the hard way in the glibc implementation. The reference
that Szabolcs found is:
Hans Boehm, Can Seqlocks Get Along with Programming Language
Memory Models?, Section 4.
thanks for the pointer, I will look at this more carefully. When I read
the text correctly we need a __atomic_thread_fence(__ATOMIC_ACQUIRE)
before the load, but I will double check that.
+static void
+btree_release_tree_recursively (struct btree *t, struct btree_node *n);
+
+// Destroy a tree and release all nodes. Not used currently, but could be
called
+// at shutdown to destroy the frame lookup
+static void
+btree_destroy (struct btree *t)
+{
The comment seems to be incorrect, it is used? Otherwise there should
be a compiler warning.
sorry for that, I initially wanted to keep the tree alive forever, but
then decided to destroy it at shutdown. I will update the comment.
+// Allocate a node. This node will be returned in locked exclusive state
+static struct btree_node *
+btree_allocate_node (struct btree *t, bool inner)
+{
+ // No free page available, allocate a new one
+ struct btree_node *new_node
+ = (struct btree_node *) (malloc (sizeof (struct btree_node)));
+ version_lock_initialize_locked_exclusive (
+ &(new_node->version_lock)); // initialize the node in locked state
+ new_node->entry_count = 0;
+ new_node->type = inner ? btree_node_inner : btree_node_leaf;
+ return new_node;
+ }
+}
This needs some form of error checking for malloc. But I see the
existing code does not have that, either. 8-(
and I do not see how we can really handle a malloc failure here. What
should we do except die? And, as you pointed out, that is fundamental in
the surrounding code, too, it allocates an struct object via malloc, and
will crash if that fails.
+// Find the corresponding entry the given address
+static struct object *
+btree_lookup (const struct btree *t, uintptr_t target_addr)
+{
+ if (type == btree_node_inner)
+ {
+ // We cannot call find_inner_slot here because we can only trust our
+ // validated entries
+ unsigned slot = 0;
+ while (((slot + 1) < entry_count)
+ && (iter->content.children[slot].separator < target_addr))
+ ++slot;
+ struct btree_node *child = iter->content.children[slot].child;
+ if (!btree_node_validate (iter, lock))
+ goto restart;
I don't understand the comment about not using find_inner_slot.
I think if you use separate free lists for inner nodes and leaf nodes,
you never need to structurally modify the data. Then you can avoid
validating on every level (with proper relaxed MO everywhere; right now
GCC might turn some of the array copies into memcpy, which may use
weaker-than-relaxed MO on some targets and actually produce
out-of-thin-air values).
the problem is that, at least conceptually, we can read arbitrary
garbage while a concurrent change is ongoing. In particular the
n->element_case within find_inner_slot might return anything, including
torn writes etc. The btree_lookup defends against that by using only
validated values as loop limits, but the regular code does not. And
instead of uglyfying the regular lookup_*_slot functions I preferred to
duplicate that code with additional validate checks instead, that are
only 3 lines anyway.
+
+static void
+release_registered_frames (void) __attribute__ ((destructor (110)));
+static void
+release_registered_frames (void)
+{
+ /* Release the b-tree and all frames. Frame releases that happen later are
+ * silently ignored */
+ btree_destroy (®istered_frames);
+}
Is the comment correct? Won't a subsequent frame release necessarily
involve a use-after-free bug? btree_destroy is only safe to call from a
quiesced process. Deallocating these data structure is mainly relevant
for mtrace and valgrind --show-reachable=yes. We could teach them to
call a new freeres hook in libgcc_s.
a subsequent frame release is safe, it will perform a btree lookup (on
an empty btree), find nothing, and stop. Even frame registrations would
be safe, they will just leads to leaked memory because the new nodes
would not be released.
The only dangerous thing would be to require unwinding through frames
that have been released by release_registered_frames, we would not find
the exception handler. (And unwinding in concurrent threads would be
racy, but I think they must not occur at shutdown anyway).
But if you want I can remove that destructor call, I just thought it
would be nicer to release all memory.
+#ifdef ATOMIC_FDE_FAST_PATH
+/* Get the PC range from FDEs */
+static void
+get_pc_range_from_fdes (const struct object *ob, const fde *this_fde,
+ uintptr_t *range)
+{
Would it be possible to share the bulk of the implementation with
classify_object_over_fdes?
unfortunately classify_object_over_fdes modifies the struct object, and
we must not do that. I thought about reusing the code, but it is not
trivial to do. I can try harder if you want, but it will make the other
code path uglier.
/* A linear search through a set of FDEs for the given PC. This is
used when there was insufficient memory to allocate and sort an
array. */
@@ -1033,17 +1154,12 @@ _Unwind_Find_FDE (void *pc, struct dwarf_eh_bases
*bases)
const fde *f = NULL;
#ifdef ATOMIC_FDE_FAST_PATH
- /* For targets where unwind info is usually not registered through these
- APIs anymore, avoid taking a global lock.
- Use relaxed MO here, it is up to the app to ensure that the library
- loading/initialization happens-before using that library in other
- threads (in particular unwinding with that library's functions
- appearing in the backtraces). Calling that library's functions
- without waiting for the library to initialize would be racy. */
- if (__builtin_expect (!__atomic_load_n (&any_objects_registered,
- __ATOMIC_RELAXED), 1))
+ ob = btree_lookup (®istered_frames, (uintptr_t) pc);
+ if (!ob)
return NULL;
-#endif
+
+ f = search_object (ob, pc);
+#else
I think we should keep any_objects_registered, to avoid the SEQ_CST
fences in btree_lookup. There might be some interest from the
maintainers of weakly ordered architectures to move away from SEQ_CST to
something else, but I assume that could be a follow-up change.
We can get the same effect by putting a
if (__builtin_expect(!__atomic_load_n (&(t->root),__ATOMIC_RELAXED), 1))
return NULL;
at the beginning of btree_lookup. I can do that if you want. Note,
though, that this requires some kind of application-level
synchronization between threads using unwinding and threads calling
__register_frame. Just as the existing code, the comment mentions that.
Best
Thomas
