* Thomas Neumann:
>>> +// 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.
This is more of a GCC policy question, which I cannot answer.
At least it needs a comment explaining the decision to ignore overflows.
> 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.
Again, I don't know if people consider the spinning a problem. In
glibc, we would use that mutex.
> 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.
Yes, understood.
>>> +// 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.
The equivalent glibc function looks like this:
/* Return true if the read was successful, given the start
version. */
static inline bool
_dlfo_read_success (uint64_t start_version)
{
/* See Hans Boehm, Can Seqlocks Get Along with Programming Language
Memory Models?, Section 4. This is necessary so that loads in
the TM region are not ordered past the version check below. */
atomic_thread_fence_acquire ();
/* Synchronizes with the fences in _dlfo_mappings_begin_update,
_dlfo_mappings_end_update. It is important that all stores from
the last update have become visible, and stores from the next
update to this version are not before the version number is
updated.
Unlike with seqlocks, there is no check for odd versions here
because we have read the unmodified copy (confirmed to be
unmodified by the unchanged version). */
return _dlfo_read_start_version () == start_version;
}
>>> +// 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?
We may have to add a new interface. In some other cases, I've seen
errno being used for error reporting, but that requires changes in
applications to recognize the error. It's probably better to crash here
than to fail mysteriously later.
Out of curiosity, how many times do you call the registration functions
from your application? Would a batch registration interface help? It
could address error reporting as well.
>>> +// 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.
Technically the data races are still invalid, you cannot retroactively
undo them using the version check.
>>> +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.
Okay.
>>> +#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.
I see, please add a comment (on both copies of the code), as a hint to
keep it in sync.
>> 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.
That's fine. I want to make it obvious to architecture maintainers that
performance for the common case (no dynamic frames) does not change.
> 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.
Isn't that comment misleading? Some synchronization is needed even with
the full locking to make sure that unwind data has been registered
before unwinding. The main locking ensures that the data read is
consistent, but not that the data is there.
Thanks,
Florian
