* Thomas Neumann:
> +#ifndef HIDE_EXPORTS
> +#pragma GCC visibility push(default)
> +#endif
All defined functions are static, right? Then this isn't necessary.
> +// 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.
> +// 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.
> +// 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.
> +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.
> +// 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-(
> +// 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).
> diff --git a/libgcc/unwind-dw2-fde.c b/libgcc/unwind-dw2-fde.c
> index 8ee55be5675..56be596713b 100644
> --- a/libgcc/unwind-dw2-fde.c
> +++ b/libgcc/unwind-dw2-fde.c
> @@ -42,15 +42,34 @@ see the files COPYING3 and COPYING.RUNTIME respectively.
> If not, see
> #endif
> #endif
>
> +#ifdef ATOMIC_FDE_FAST_PATH
> +#include "unwind-dw2-btree.h"
> +
> +static struct btree registered_frames;
> +
> +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.
> +#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?
> /* 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.
I don't know much about B-trees, so I can't really tell if the
implementation is correct. I don't see any obvious problems, though.
I'm not a GCC reviewer. If the project wants to adopt the patch, we'll
need to fix a few minor style issues. But let's wait for the GCC
developers first.
Thanks,
Florian
