From 6e80a1d164d1f996ad08a512c000025a7c2ca893 Mon Sep 17 00:00:00 2001 From: Thomas Neumann Date: Tue, 1 Mar 2022 21:57:35 +0100 Subject: eliminate mutex in fast path of __register_frame The __register_frame/__deregister_frame functions are used to register unwinding frames from JITed code in a sorted list. That list itself is protected by object_mutex, which leads to terrible performance in multi-threaded code and is somewhat expensive even if single-threaded. There was already a fast-path that avoided taking the mutex if no frame was registered at all. This commit eliminates both the mutex and the sorted list from the atomic fast path, and replaces it with a btree that uses optimistic lock coupling during lookup. This allows for fully parallel unwinding and is essential to scale exception handling to large core counts. libgcc/ChangeLog: * unwind-dw2-fde.c (release_registered_frames): Cleanup at shutdown. (__register_frame_info_table_bases): Use btree in atomic fast path. (__deregister_frame_info_bases): Likewise. (_Unwind_Find_FDE): Likewise. (base_from_object): Make parameter const. (classify_object_over_fdes): Add query-only mode. (get_pc_range): Compute PC range for lookup. * unwind-dw2-fde.h (last_fde): Make parameter const. * unwind-dw2-btree.h: New file. --- libgcc/unwind-dw2-btree.h | 953 ++++++++++++++++++++++++++++++++++++++++++++++ libgcc/unwind-dw2-fde.c | 194 +++++++--- libgcc/unwind-dw2-fde.h | 2 +- 3 files changed, 1098 insertions(+), 51 deletions(-) create mode 100644 libgcc/unwind-dw2-btree.h (limited to 'libgcc') diff --git a/libgcc/unwind-dw2-btree.h b/libgcc/unwind-dw2-btree.h new file mode 100644 index 0000000..8853f0e --- /dev/null +++ b/libgcc/unwind-dw2-btree.h @@ -0,0 +1,953 @@ +/* Lock-free btree for manually registered unwind frames. */ +/* Copyright (C) 2022 Free Software Foundation, Inc. + Contributed by Thomas Neumann + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +Under Section 7 of GPL version 3, you are granted additional +permissions described in the GCC Runtime Library Exception, version +3.1, as published by the Free Software Foundation. + +You should have received a copy of the GNU General Public License and +a copy of the GCC Runtime Library Exception along with this program; +see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +. */ + +#ifndef GCC_UNWIND_DW2_BTREE_H +#define GCC_UNWIND_DW2_BTREE_H + +#include + +// Common logic for version locks. +struct version_lock +{ + // The lock itself. The lowest bit indicates an exclusive lock, + // the second bit indicates waiting threads. All other bits are + // used as counter to recognize changes. + // Overflows are okay here, we must only prevent overflow to the + // same value within one lock_optimistic/validate + // range. Even on 32 bit platforms that would require 1 billion + // frame registrations within the time span of a few assembler + // instructions. + uintptr_t version_lock; +}; + +#ifdef __GTHREAD_HAS_COND +// We should never get contention within the tree as it rarely changes. +// But if we ever do get contention we use these for waiting. +static __gthread_mutex_t version_lock_mutex = __GTHREAD_MUTEX_INIT; +static __gthread_cond_t version_lock_cond = __GTHREAD_COND_INIT; +#endif + +// Initialize in locked state. +static inline void +version_lock_initialize_locked_exclusive (struct version_lock *vl) +{ + vl->version_lock = 1; +} + +// Try to lock the node exclusive. +static inline bool +version_lock_try_lock_exclusive (struct version_lock *vl) +{ + uintptr_t state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); + if (state & 1) + return false; + return __atomic_compare_exchange_n (&(vl->version_lock), &state, state | 1, + false, __ATOMIC_SEQ_CST, + __ATOMIC_SEQ_CST); +} + +// Lock the node exclusive, blocking as needed. +static void +version_lock_lock_exclusive (struct version_lock *vl) +{ +#ifndef __GTHREAD_HAS_COND +restart: +#endif + + // We should virtually never get contention here, as frame + // changes are rare. + uintptr_t state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); + if (!(state & 1)) + { + if (__atomic_compare_exchange_n (&(vl->version_lock), &state, state | 1, + false, __ATOMIC_SEQ_CST, + __ATOMIC_SEQ_CST)) + return; + } + + // We did get contention, wait properly. +#ifdef __GTHREAD_HAS_COND + __gthread_mutex_lock (&version_lock_mutex); + state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); + while (true) + { + // Check if the lock is still held. + if (!(state & 1)) + { + if (__atomic_compare_exchange_n (&(vl->version_lock), &state, + state | 1, false, __ATOMIC_SEQ_CST, + __ATOMIC_SEQ_CST)) + { + __gthread_mutex_unlock (&version_lock_mutex); + return; + } + else + { + continue; + } + } + + // Register waiting thread. + if (!(state & 2)) + { + if (!__atomic_compare_exchange_n (&(vl->version_lock), &state, + state | 2, false, __ATOMIC_SEQ_CST, + __ATOMIC_SEQ_CST)) + continue; + } + + // And sleep. + __gthread_cond_wait (&version_lock_cond, &version_lock_mutex); + state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); + } +#else + // Spin if we do not have condition variables available. + // We expect no contention here, spinning should be okay. + goto restart; +#endif +} + +// Release a locked node and increase the version lock. +static void +version_lock_unlock_exclusive (struct version_lock *vl) +{ + // increase version, reset exclusive lock bits + uintptr_t state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); + uintptr_t ns = (state + 4) & (~((uintptr_t) 3)); + state = __atomic_exchange_n (&(vl->version_lock), ns, __ATOMIC_SEQ_CST); + +#ifdef __GTHREAD_HAS_COND + if (state & 2) + { + // Wake up waiting threads. This should be extremely rare. + __gthread_mutex_lock (&version_lock_mutex); + __gthread_cond_broadcast (&version_lock_cond); + __gthread_mutex_unlock (&version_lock_mutex); + } +#endif +} + +// Acquire an optimistic "lock". Note that this does not lock at all, it +// only allows for validation later. +static inline bool +version_lock_lock_optimistic (const struct version_lock *vl, uintptr_t *lock) +{ + uintptr_t state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); + *lock = state; + + // Acquiring the lock fails when there is currently an exclusive lock. + return !(state & 1); +} + +// Validate a previously acquired "lock". +static inline bool +version_lock_validate (const struct version_lock *vl, uintptr_t lock) +{ + // Prevent the reordering of non-atomic loads behind the atomic load. + // Hans Boehm, Can Seqlocks Get Along with Programming Language Memory + // Models?, Section 4. + __atomic_thread_fence (__ATOMIC_ACQUIRE); + + // 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); +} + +// The largest possible separator value. +static const uintptr_t max_separator = ~((uintptr_t) (0)); + +struct btree_node; + +// Inner entry. The child tree contains all entries <= separator. +struct inner_entry +{ + uintptr_t separator; + struct btree_node *child; +}; + +// Leaf entry. Stores an object entry. +struct leaf_entry +{ + uintptr_t base, size; + struct object *ob; +}; + +// Node types. +enum node_type +{ + btree_node_inner, + btree_node_leaf, + btree_node_free +}; + +// Node sizes. Chosen such that the result size is roughly 256 bytes. +#define max_fanout_inner 15 +#define max_fanout_leaf 10 + +// A btree node. +struct btree_node +{ + // The version lock used for optimistic lock coupling. + struct version_lock version_lock; + // The number of entries. + unsigned entry_count; + // The type. + enum node_type type; + // The payload. + union + { + // The inner nodes have fence keys, i.e., the right-most entry includes a + // separator. + struct inner_entry children[max_fanout_inner]; + struct leaf_entry entries[max_fanout_leaf]; + } content; +}; + +// Is an inner node? +static inline bool +btree_node_is_inner (const struct btree_node *n) +{ + return n->type == btree_node_inner; +} + +// Is a leaf node? +static inline bool +btree_node_is_leaf (const struct btree_node *n) +{ + return n->type == btree_node_leaf; +} + +// Should the node be merged? +static inline bool +btree_node_needs_merge (const struct btree_node *n) +{ + return n->entry_count < (btree_node_is_inner (n) ? (max_fanout_inner / 2) + : (max_fanout_leaf / 2)); +} + +// Get the fence key for inner nodes. +static inline uintptr_t +btree_node_get_fence_key (const struct btree_node *n) +{ + // For inner nodes we just return our right-most entry. + return n->content.children[n->entry_count - 1].separator; +} + +// Find the position for a slot in an inner node. +static unsigned +btree_node_find_inner_slot (const struct btree_node *n, uintptr_t value) +{ + for (unsigned index = 0, ec = n->entry_count; index != ec; ++index) + if (n->content.children[index].separator >= value) + return index; + return n->entry_count; +} + +// Find the position for a slot in a leaf node. +static unsigned +btree_node_find_leaf_slot (const struct btree_node *n, uintptr_t value) +{ + for (unsigned index = 0, ec = n->entry_count; index != ec; ++index) + if (n->content.entries[index].base + n->content.entries[index].size > value) + return index; + return n->entry_count; +} + +// Try to lock the node exclusive. +static inline bool +btree_node_try_lock_exclusive (struct btree_node *n) +{ + return version_lock_try_lock_exclusive (&(n->version_lock)); +} + +// Lock the node exclusive, blocking as needed. +static inline void +btree_node_lock_exclusive (struct btree_node *n) +{ + version_lock_lock_exclusive (&(n->version_lock)); +} + +// Release a locked node and increase the version lock. +static inline void +btree_node_unlock_exclusive (struct btree_node *n) +{ + version_lock_unlock_exclusive (&(n->version_lock)); +} + +// Acquire an optimistic "lock". Note that this does not lock at all, it +// only allows for validation later. +static inline bool +btree_node_lock_optimistic (const struct btree_node *n, uintptr_t *lock) +{ + return version_lock_lock_optimistic (&(n->version_lock), lock); +} + +// Validate a previously acquire lock. +static inline bool +btree_node_validate (const struct btree_node *n, uintptr_t lock) +{ + return version_lock_validate (&(n->version_lock), lock); +} + +// Insert a new separator after splitting. +static void +btree_node_update_separator_after_split (struct btree_node *n, + uintptr_t old_separator, + uintptr_t new_separator, + struct btree_node *new_right) +{ + unsigned slot = btree_node_find_inner_slot (n, old_separator); + for (unsigned index = n->entry_count; index > slot; --index) + n->content.children[index] = n->content.children[index - 1]; + n->content.children[slot].separator = new_separator; + n->content.children[slot + 1].child = new_right; + n->entry_count++; +} + +// A btree. Suitable for static initialization, all members are zero at the +// beginning. +struct btree +{ + // The root of the btree. + struct btree_node *root; + // The free list of released node. + struct btree_node *free_list; + // The version lock used to protect the root. + struct version_lock root_lock; +}; + +// Initialize a btree. Not actually used, just for exposition. +static inline void +btree_init (struct btree *t) +{ + t->root = NULL; + t->free_list = NULL; + t->root_lock.version_lock = 0; +}; + +static void +btree_release_tree_recursively (struct btree *t, struct btree_node *n); + +// Destroy a tree and release all nodes. +static void +btree_destroy (struct btree *t) +{ + // Disable the mechanism before cleaning up. + struct btree_node *old_root + = __atomic_exchange_n (&(t->root), NULL, __ATOMIC_SEQ_CST); + if (old_root) + btree_release_tree_recursively (t, old_root); + + // Release all free nodes. + while (t->free_list) + { + struct btree_node *next = t->free_list->content.children[0].child; + free (t->free_list); + t->free_list = next; + } +} + +// Allocate a node. This node will be returned in locked exclusive state. +static struct btree_node * +btree_allocate_node (struct btree *t, bool inner) +{ + while (true) + { + // Try the free list first. + struct btree_node *next_free + = __atomic_load_n (&(t->free_list), __ATOMIC_SEQ_CST); + if (next_free) + { + if (!btree_node_try_lock_exclusive (next_free)) + continue; + // The node might no longer be free, check that again after acquiring + // the exclusive lock. + if (next_free->type == btree_node_free) + { + struct btree_node *ex = next_free; + if (__atomic_compare_exchange_n ( + &(t->free_list), &ex, next_free->content.children[0].child, + false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) + { + next_free->entry_count = 0; + next_free->type = inner ? btree_node_inner : btree_node_leaf; + return next_free; + } + } + btree_node_unlock_exclusive (next_free); + continue; + } + + // No free node 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; + } +} + +// Release a node. This node must be currently locked exclusively and will +// be placed in the free list. +static void +btree_release_node (struct btree *t, struct btree_node *node) +{ + // We cannot release the memory immediately because there might still be + // concurrent readers on that node. Put it in the free list instead. + node->type = btree_node_free; + struct btree_node *next_free + = __atomic_load_n (&(t->free_list), __ATOMIC_SEQ_CST); + do + { + node->content.children[0].child = next_free; + } while (!__atomic_compare_exchange_n (&(t->free_list), &next_free, node, + false, __ATOMIC_SEQ_CST, + __ATOMIC_SEQ_CST)); + btree_node_unlock_exclusive (node); +} + +// Recursively release a tree. The btree is by design very shallow, thus +// we can risk recursion here. +static void +btree_release_tree_recursively (struct btree *t, struct btree_node *node) +{ + btree_node_lock_exclusive (node); + if (btree_node_is_inner (node)) + { + for (unsigned index = 0; index < node->entry_count; ++index) + btree_release_tree_recursively (t, node->content.children[index].child); + } + btree_release_node (t, node); +} + +// Check if we are splitting the root. +static void +btree_handle_root_split (struct btree *t, struct btree_node **node, + struct btree_node **parent) +{ + // We want to keep the root pointer stable to allow for contention + // free reads. Thus, we split the root by first moving the content + // of the root node to a new node, and then split that new node. + if (!*parent) + { + // Allocate a new node, this guarantees us that we will have a parent + // afterwards. + struct btree_node *new_node + = btree_allocate_node (t, btree_node_is_inner (*node)); + struct btree_node *old_node = *node; + new_node->entry_count = old_node->entry_count; + new_node->content = old_node->content; + old_node->content.children[0].separator = max_separator; + old_node->content.children[0].child = new_node; + old_node->entry_count = 1; + old_node->type = btree_node_inner; + + *parent = old_node; + *node = new_node; + } +} + +// Split an inner node. +static void +btree_split_inner (struct btree *t, struct btree_node **inner, + struct btree_node **parent, uintptr_t target) +{ + // Check for the root. + btree_handle_root_split (t, inner, parent); + + // Create two inner node. + uintptr_t right_fence = btree_node_get_fence_key (*inner); + struct btree_node *left_inner = *inner; + struct btree_node *right_inner = btree_allocate_node (t, true); + unsigned split = left_inner->entry_count / 2; + right_inner->entry_count = left_inner->entry_count - split; + for (unsigned index = 0; index < right_inner->entry_count; ++index) + right_inner->content.children[index] + = left_inner->content.children[split + index]; + left_inner->entry_count = split; + uintptr_t left_fence = btree_node_get_fence_key (left_inner); + btree_node_update_separator_after_split (*parent, right_fence, left_fence, + right_inner); + if (target <= left_fence) + { + *inner = left_inner; + btree_node_unlock_exclusive (right_inner); + } + else + { + *inner = right_inner; + btree_node_unlock_exclusive (left_inner); + } +} + +// Split a leaf node. +static void +btree_split_leaf (struct btree *t, struct btree_node **leaf, + struct btree_node **parent, uintptr_t fence, uintptr_t target) +{ + // Check for the root. + btree_handle_root_split (t, leaf, parent); + + // Create two leaf nodes. + uintptr_t right_fence = fence; + struct btree_node *left_leaf = *leaf; + struct btree_node *right_leaf = btree_allocate_node (t, false); + unsigned split = left_leaf->entry_count / 2; + right_leaf->entry_count = left_leaf->entry_count - split; + for (unsigned index = 0; index != right_leaf->entry_count; ++index) + right_leaf->content.entries[index] + = left_leaf->content.entries[split + index]; + left_leaf->entry_count = split; + uintptr_t left_fence = right_leaf->content.entries[0].base - 1; + btree_node_update_separator_after_split (*parent, right_fence, left_fence, + right_leaf); + if (target <= left_fence) + { + *leaf = left_leaf; + btree_node_unlock_exclusive (right_leaf); + } + else + { + *leaf = right_leaf; + btree_node_unlock_exclusive (left_leaf); + } +} + +// Merge (or balance) child nodes. +static struct btree_node * +btree_merge_node (struct btree *t, unsigned child_slot, + struct btree_node *parent, uintptr_t target) +{ + // Choose the emptiest neighbor and lock both. The target child is already + // locked. + unsigned left_slot; + struct btree_node *left_node, *right_node; + if ((child_slot == 0) + || (((child_slot + 1) < parent->entry_count) + && (parent->content.children[child_slot + 1].child->entry_count + < parent->content.children[child_slot - 1].child->entry_count))) + { + left_slot = child_slot; + left_node = parent->content.children[left_slot].child; + right_node = parent->content.children[left_slot + 1].child; + btree_node_lock_exclusive (right_node); + } + else + { + left_slot = child_slot - 1; + left_node = parent->content.children[left_slot].child; + right_node = parent->content.children[left_slot + 1].child; + btree_node_lock_exclusive (left_node); + } + + // Can we merge both nodes into one node? + unsigned total_count = left_node->entry_count + right_node->entry_count; + unsigned max_count + = btree_node_is_inner (left_node) ? max_fanout_inner : max_fanout_leaf; + if (total_count <= max_count) + { + // Merge into the parent? + if (parent->entry_count == 2) + { + // Merge children into parent. This can only happen at the root. + if (btree_node_is_inner (left_node)) + { + for (unsigned index = 0; index != left_node->entry_count; ++index) + parent->content.children[index] + = left_node->content.children[index]; + for (unsigned index = 0; index != right_node->entry_count; + ++index) + parent->content.children[index + left_node->entry_count] + = right_node->content.children[index]; + } + else + { + parent->type = btree_node_leaf; + for (unsigned index = 0; index != left_node->entry_count; ++index) + parent->content.entries[index] + = left_node->content.entries[index]; + for (unsigned index = 0; index != right_node->entry_count; + ++index) + parent->content.entries[index + left_node->entry_count] + = right_node->content.entries[index]; + } + parent->entry_count = total_count; + btree_release_node (t, left_node); + btree_release_node (t, right_node); + return parent; + } + else + { + // Regular merge. + if (btree_node_is_inner (left_node)) + { + for (unsigned index = 0; index != right_node->entry_count; + ++index) + left_node->content.children[left_node->entry_count++] + = right_node->content.children[index]; + } + else + { + for (unsigned index = 0; index != right_node->entry_count; + ++index) + left_node->content.entries[left_node->entry_count++] + = right_node->content.entries[index]; + } + parent->content.children[left_slot].separator + = parent->content.children[left_slot + 1].separator; + for (unsigned index = left_slot + 1; index + 1 < parent->entry_count; + ++index) + parent->content.children[index] + = parent->content.children[index + 1]; + parent->entry_count--; + btree_release_node (t, right_node); + btree_node_unlock_exclusive (parent); + return left_node; + } + } + + // No merge possible, rebalance instead. + if (left_node->entry_count > right_node->entry_count) + { + // Shift from left to right. + unsigned to_shift + = (left_node->entry_count - right_node->entry_count) / 2; + if (btree_node_is_inner (left_node)) + { + for (unsigned index = 0; index != right_node->entry_count; ++index) + { + unsigned pos = right_node->entry_count - 1 - index; + right_node->content.children[pos + to_shift] + = right_node->content.children[pos]; + } + for (unsigned index = 0; index != to_shift; ++index) + right_node->content.children[index] + = left_node->content + .children[left_node->entry_count - to_shift + index]; + } + else + { + for (unsigned index = 0; index != right_node->entry_count; ++index) + { + unsigned pos = right_node->entry_count - 1 - index; + right_node->content.entries[pos + to_shift] + = right_node->content.entries[pos]; + } + for (unsigned index = 0; index != to_shift; ++index) + right_node->content.entries[index] + = left_node->content + .entries[left_node->entry_count - to_shift + index]; + } + left_node->entry_count -= to_shift; + right_node->entry_count += to_shift; + } + else + { + // Shift from right to left. + unsigned to_shift + = (right_node->entry_count - left_node->entry_count) / 2; + if (btree_node_is_inner (left_node)) + { + for (unsigned index = 0; index != to_shift; ++index) + left_node->content.children[left_node->entry_count + index] + = right_node->content.children[index]; + for (unsigned index = 0; index != right_node->entry_count - to_shift; + ++index) + right_node->content.children[index] + = right_node->content.children[index + to_shift]; + } + else + { + for (unsigned index = 0; index != to_shift; ++index) + left_node->content.entries[left_node->entry_count + index] + = right_node->content.entries[index]; + for (unsigned index = 0; index != right_node->entry_count - to_shift; + ++index) + right_node->content.entries[index] + = right_node->content.entries[index + to_shift]; + } + left_node->entry_count += to_shift; + right_node->entry_count -= to_shift; + } + uintptr_t left_fence; + if (btree_node_is_leaf (left_node)) + { + left_fence = right_node->content.entries[0].base - 1; + } + else + { + left_fence = btree_node_get_fence_key (left_node); + } + parent->content.children[left_slot].separator = left_fence; + btree_node_unlock_exclusive (parent); + if (target <= left_fence) + { + btree_node_unlock_exclusive (right_node); + return left_node; + } + else + { + btree_node_unlock_exclusive (left_node); + return right_node; + } +} + +// Insert an entry. +static bool +btree_insert (struct btree *t, uintptr_t base, uintptr_t size, + struct object *ob) +{ + // Sanity check. + if (!size) + return false; + + // Access the root. + struct btree_node *iter, *parent = NULL; + { + version_lock_lock_exclusive (&(t->root_lock)); + iter = t->root; + if (iter) + { + btree_node_lock_exclusive (iter); + } + else + { + t->root = iter = btree_allocate_node (t, false); + } + version_lock_unlock_exclusive (&(t->root_lock)); + } + + // Walk down the btree with classic lock coupling and eager splits. + // Strictly speaking this is not performance optimal, we could use + // optimistic lock coupling until we hit a node that has to be modified. + // But that is more difficult to implement and frame registration is + // rare anyway, we use simple locking for now. + + uintptr_t fence = max_separator; + while (btree_node_is_inner (iter)) + { + // Use eager splits to avoid lock coupling up. + if (iter->entry_count == max_fanout_inner) + btree_split_inner (t, &iter, &parent, base); + + unsigned slot = btree_node_find_inner_slot (iter, base); + if (parent) + btree_node_unlock_exclusive (parent); + parent = iter; + fence = iter->content.children[slot].separator; + iter = iter->content.children[slot].child; + btree_node_lock_exclusive (iter); + } + + // Make sure we have space. + if (iter->entry_count == max_fanout_leaf) + btree_split_leaf (t, &iter, &parent, fence, base); + if (parent) + btree_node_unlock_exclusive (parent); + + // Insert in node. + unsigned slot = btree_node_find_leaf_slot (iter, base); + if ((slot < iter->entry_count) && (iter->content.entries[slot].base == base)) + { + // Duplicate entry, this should never happen. + btree_node_unlock_exclusive (iter); + return false; + } + for (unsigned index = iter->entry_count; index > slot; --index) + iter->content.entries[index] = iter->content.entries[index - 1]; + struct leaf_entry *e = &(iter->content.entries[slot]); + e->base = base; + e->size = size; + e->ob = ob; + iter->entry_count++; + btree_node_unlock_exclusive (iter); + return true; +} + +// Remove an entry. +static struct object * +btree_remove (struct btree *t, uintptr_t base) +{ + // Access the root. + version_lock_lock_exclusive (&(t->root_lock)); + struct btree_node *iter = t->root; + if (iter) + btree_node_lock_exclusive (iter); + version_lock_unlock_exclusive (&(t->root_lock)); + if (!iter) + return NULL; + + // Same strategy as with insert, walk down with lock coupling and + // merge eagerly. + while (btree_node_is_inner (iter)) + { + unsigned slot = btree_node_find_inner_slot (iter, base); + struct btree_node *next = iter->content.children[slot].child; + btree_node_lock_exclusive (next); + if (btree_node_needs_merge (next)) + { + // Use eager merges to avoid lock coupling up. + iter = btree_merge_node (t, slot, iter, base); + } + else + { + btree_node_unlock_exclusive (iter); + iter = next; + } + } + + // Remove existing entry. + unsigned slot = btree_node_find_leaf_slot (iter, base); + if ((slot >= iter->entry_count) || (iter->content.entries[slot].base != base)) + { + // Not found, this should never happen. + btree_node_unlock_exclusive (iter); + return NULL; + } + struct object *ob = iter->content.entries[slot].ob; + for (unsigned index = slot; index + 1 < iter->entry_count; ++index) + iter->content.entries[index] = iter->content.entries[index + 1]; + iter->entry_count--; + btree_node_unlock_exclusive (iter); + return ob; +} + +// Find the corresponding entry for the given address. +static struct object * +btree_lookup (const struct btree *t, uintptr_t target_addr) +{ + // Within this function many loads are relaxed atomic loads. + // Use a macro to keep the code reasonable. +#define RLOAD(x) __atomic_load_n (&(x), __ATOMIC_RELAXED) + + // For targets where unwind info is usually not registered through these + // APIs anymore, avoid any sequential consistent atomics. + // 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 (!RLOAD (t->root), 1)) + return NULL; + + // The unwinding tables are mostly static, they only change when + // frames are added or removed. This makes it extremely unlikely that they + // change during a given unwinding sequence. Thus, we optimize for the + // contention free case and use optimistic lock coupling. This does not + // require any writes to shared state, instead we validate every read. It is + // important that we do not trust any value that we have read until we call + // validate again. Data can change at arbitrary points in time, thus we always + // copy something into a local variable and validate again before acting on + // the read. In the unlikely event that we encounter a concurrent change we + // simply restart and try again. + +restart: + struct btree_node *iter; + uintptr_t lock; + { + // Accessing the root node requires defending against concurrent pointer + // changes Thus we couple rootLock -> lock on root node -> validate rootLock + if (!version_lock_lock_optimistic (&(t->root_lock), &lock)) + goto restart; + iter = RLOAD (t->root); + if (!version_lock_validate (&(t->root_lock), lock)) + goto restart; + if (!iter) + return NULL; + uintptr_t child_lock; + if ((!btree_node_lock_optimistic (iter, &child_lock)) + || (!version_lock_validate (&(t->root_lock), lock))) + goto restart; + lock = child_lock; + } + + // Now we can walk down towards the right leaf node. + while (true) + { + enum node_type type = RLOAD (iter->type); + unsigned entry_count = RLOAD (iter->entry_count); + if (!btree_node_validate (iter, lock)) + goto restart; + if (!entry_count) + return NULL; + + if (type == btree_node_inner) + { + // We cannot call find_inner_slot here because we need (relaxed) + // atomic reads here. + unsigned slot = 0; + while ( + ((slot + 1) < entry_count) + && (RLOAD (iter->content.children[slot].separator) < target_addr)) + ++slot; + struct btree_node *child = RLOAD (iter->content.children[slot].child); + if (!btree_node_validate (iter, lock)) + goto restart; + + // The node content can change at any point in time, thus we must + // interleave parent and child checks. + uintptr_t child_lock; + if (!btree_node_lock_optimistic (child, &child_lock)) + goto restart; + if (!btree_node_validate (iter, lock)) + goto restart; // make sure we still point to the correct node after + // acquiring the optimistic lock. + + // Go down + iter = child; + lock = child_lock; + } + else + { + // We cannot call find_leaf_slot here because we need (relaxed) + // atomic reads here. + unsigned slot = 0; + while (((slot + 1) < entry_count) + && (RLOAD (iter->content.entries[slot].base) + + RLOAD (iter->content.entries[slot].size) + <= target_addr)) + ++slot; + struct leaf_entry entry; + entry.base = RLOAD (iter->content.entries[slot].base); + entry.size = RLOAD (iter->content.entries[slot].size); + entry.ob = RLOAD (iter->content.entries[slot].ob); + if (!btree_node_validate (iter, lock)) + goto restart; + + // Check if we have a hit. + if ((entry.base <= target_addr) + && (target_addr < entry.base + entry.size)) + { + return entry.ob; + } + return NULL; + } + } +#undef RLOAD +} + +#endif /* unwind-dw2-btree.h */ diff --git a/libgcc/unwind-dw2-fde.c b/libgcc/unwind-dw2-fde.c index 8ee55be..000ee69 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); +} + +static void +get_pc_range (const struct object *ob, uintptr_t *range); +static void +init_object (struct object *ob); + +#else + /* The unseen_objects list contains objects that have been registered but not yet categorized in any way. The seen_objects list has had its pc_begin and count fields initialized at minimum, and is sorted by decreasing value of pc_begin. */ static struct object *unseen_objects; static struct object *seen_objects; -#ifdef ATOMIC_FDE_FAST_PATH -static int any_objects_registered; -#endif #ifdef __GTHREAD_MUTEX_INIT static __gthread_mutex_t object_mutex = __GTHREAD_MUTEX_INIT; @@ -78,6 +97,7 @@ init_object_mutex_once (void) static __gthread_mutex_t object_mutex; #endif #endif +#endif /* Called from crtbegin.o to register the unwind info for an object. */ @@ -99,23 +119,23 @@ __register_frame_info_bases (const void *begin, struct object *ob, ob->fde_end = NULL; #endif +#ifdef ATOMIC_FDE_FAST_PATH + // Initialize eagerly to avoid locking later + init_object (ob); + + // And register the frame + uintptr_t range[2]; + get_pc_range (ob, range); + btree_insert (®istered_frames, range[0], range[1] - range[0], ob); +#else init_object_mutex_once (); __gthread_mutex_lock (&object_mutex); ob->next = unseen_objects; unseen_objects = ob; -#ifdef ATOMIC_FDE_FAST_PATH - /* Set flag that at least one library has registered FDEs. - 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 (!any_objects_registered) - __atomic_store_n (&any_objects_registered, 1, __ATOMIC_RELAXED); -#endif __gthread_mutex_unlock (&object_mutex); +#endif } void @@ -153,23 +173,23 @@ __register_frame_info_table_bases (void *begin, struct object *ob, ob->s.b.from_array = 1; ob->s.b.encoding = DW_EH_PE_omit; +#ifdef ATOMIC_FDE_FAST_PATH + // Initialize eagerly to avoid locking later + init_object (ob); + + // And register the frame + uintptr_t range[2]; + get_pc_range (ob, range); + btree_insert (®istered_frames, range[0], range[1] - range[0], ob); +#else init_object_mutex_once (); __gthread_mutex_lock (&object_mutex); ob->next = unseen_objects; unseen_objects = ob; -#ifdef ATOMIC_FDE_FAST_PATH - /* Set flag that at least one library has registered FDEs. - 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 (!any_objects_registered) - __atomic_store_n (&any_objects_registered, 1, __ATOMIC_RELAXED); -#endif __gthread_mutex_unlock (&object_mutex); +#endif } void @@ -200,16 +220,33 @@ __register_frame_table (void *begin) void * __deregister_frame_info_bases (const void *begin) { - struct object **p; struct object *ob = 0; /* If .eh_frame is empty, we haven't registered. */ if ((const uword *) begin == 0 || *(const uword *) begin == 0) return ob; +#ifdef ATOMIC_FDE_FAST_PATH + // Find the corresponding PC range + struct object lookupob; + lookupob.tbase = 0; + lookupob.dbase = 0; + lookupob.u.single = begin; + lookupob.s.i = 0; + lookupob.s.b.encoding = DW_EH_PE_omit; +#ifdef DWARF2_OBJECT_END_PTR_EXTENSION + lookupob.fde_end = NULL; +#endif + uintptr_t range[2]; + get_pc_range (&lookupob, range); + + // And remove + ob = btree_remove (®istered_frames, range[0]); +#else init_object_mutex_once (); __gthread_mutex_lock (&object_mutex); + struct object **p; for (p = &unseen_objects; *p ; p = &(*p)->next) if ((*p)->u.single == begin) { @@ -241,6 +278,8 @@ __deregister_frame_info_bases (const void *begin) out: __gthread_mutex_unlock (&object_mutex); +#endif + gcc_assert (ob); return (void *) ob; } @@ -264,7 +303,7 @@ __deregister_frame (void *begin) instead of an _Unwind_Context. */ static _Unwind_Ptr -base_from_object (unsigned char encoding, struct object *ob) +base_from_object (unsigned char encoding, const struct object *ob) { if (encoding == DW_EH_PE_omit) return 0; @@ -628,13 +667,17 @@ end_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count) } } - -/* Update encoding, mixed_encoding, and pc_begin for OB for the - fde array beginning at THIS_FDE. Return the number of fdes - encountered along the way. */ +/* Inspect the fde array beginning at this_fde. This + function can be used either in query mode (RANGE is + not null, OB is const), or in update mode (RANGE is + null, OB is modified). In query mode the function computes + the range of PC values and stores it in RANGE. In + update mode it updates encoding, mixed_encoding, and pc_begin + for OB. Return the number of fdes encountered along the way. */ static size_t -classify_object_over_fdes (struct object *ob, const fde *this_fde) +classify_object_over_fdes (struct object *ob, const fde *this_fde, + uintptr_t *range) { const struct dwarf_cie *last_cie = 0; size_t count = 0; @@ -660,14 +703,18 @@ classify_object_over_fdes (struct object *ob, const fde *this_fde) if (encoding == DW_EH_PE_omit) return -1; base = base_from_object (encoding, ob); - if (ob->s.b.encoding == DW_EH_PE_omit) - ob->s.b.encoding = encoding; - else if (ob->s.b.encoding != encoding) - ob->s.b.mixed_encoding = 1; + if (!range) + { + if (ob->s.b.encoding == DW_EH_PE_omit) + ob->s.b.encoding = encoding; + else if (ob->s.b.encoding != encoding) + ob->s.b.mixed_encoding = 1; + } } - read_encoded_value_with_base (encoding, base, this_fde->pc_begin, - &pc_begin); + const unsigned char *p; + p = read_encoded_value_with_base (encoding, base, this_fde->pc_begin, + &pc_begin); /* Take care to ignore link-once functions that were removed. In these cases, the function address will be NULL, but if @@ -683,8 +730,29 @@ classify_object_over_fdes (struct object *ob, const fde *this_fde) continue; count += 1; - if ((void *) pc_begin < ob->pc_begin) - ob->pc_begin = (void *) pc_begin; + if (range) + { + _Unwind_Ptr pc_range, pc_end; + read_encoded_value_with_base (encoding & 0x0F, 0, p, &pc_range); + pc_end = pc_begin + pc_range; + if ((!range[0]) && (!range[1])) + { + range[0] = pc_begin; + range[1] = pc_end; + } + else + { + if (pc_begin < range[0]) + range[0] = pc_begin; + if (pc_end > range[1]) + range[1] = pc_end; + } + } + else + { + if ((void *) pc_begin < ob->pc_begin) + ob->pc_begin = (void *) pc_begin; + } } return count; @@ -769,7 +837,7 @@ init_object (struct object* ob) fde **p = ob->u.array; for (count = 0; *p; ++p) { - size_t cur_count = classify_object_over_fdes (ob, *p); + size_t cur_count = classify_object_over_fdes (ob, *p, NULL); if (cur_count == (size_t) -1) goto unhandled_fdes; count += cur_count; @@ -777,7 +845,7 @@ init_object (struct object* ob) } else { - count = classify_object_over_fdes (ob, ob->u.single); + count = classify_object_over_fdes (ob, ob->u.single, NULL); if (count == (size_t) -1) { static const fde terminator; @@ -821,6 +889,32 @@ init_object (struct object* ob) ob->s.b.sorted = 1; } +#ifdef ATOMIC_FDE_FAST_PATH +/* Get the PC range for lookup */ +static void +get_pc_range (const struct object *ob, uintptr_t *range) +{ + // It is safe to cast to non-const object* here as + // classify_object_over_fdes does not modify ob in query mode. + struct object *ncob = (struct object *) (uintptr_t) ob; + range[0] = range[1] = 0; + if (ob->s.b.sorted) + { + classify_object_over_fdes (ncob, ob->u.sort->orig_data, range); + } + else if (ob->s.b.from_array) + { + fde **p = ob->u.array; + for (; *p; ++p) + classify_object_over_fdes (ncob, *p, range); + } + else + { + classify_object_over_fdes (ncob, ob->u.single, range); + } +} +#endif + /* 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. */ @@ -985,6 +1079,9 @@ binary_search_mixed_encoding_fdes (struct object *ob, void *pc) static const fde * search_object (struct object* ob, void *pc) { + /* The fast path initializes objects eagerly to avoid locking. + * On the slow path we initialize them now */ +#ifndef ATOMIC_FDE_FAST_PATH /* If the data hasn't been sorted, try to do this now. We may have more memory available than last time we tried. */ if (! ob->s.b.sorted) @@ -997,6 +1094,7 @@ search_object (struct object* ob, void *pc) if (pc < ob->pc_begin) return NULL; } +#endif if (ob->s.b.sorted) { @@ -1033,17 +1131,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 init_object_mutex_once (); __gthread_mutex_lock (&object_mutex); @@ -1081,6 +1174,7 @@ _Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases) fini: __gthread_mutex_unlock (&object_mutex); +#endif if (f) { diff --git a/libgcc/unwind-dw2-fde.h b/libgcc/unwind-dw2-fde.h index 8a011c3..77c2caa 100644 --- a/libgcc/unwind-dw2-fde.h +++ b/libgcc/unwind-dw2-fde.h @@ -166,7 +166,7 @@ next_fde (const fde *f) extern const fde * _Unwind_Find_FDE (void *, struct dwarf_eh_bases *); static inline int -last_fde (struct object *obj __attribute__ ((__unused__)), const fde *f) +last_fde (const struct object *obj __attribute__ ((__unused__)), const fde *f) { #ifdef DWARF2_OBJECT_END_PTR_EXTENSION return f == (const fde *) obj->fde_end || f->length == 0; -- cgit v1.1 From 7ee0fa100f0f28d7b88237d520131e07b7b49f0a Mon Sep 17 00:00:00 2001 From: GCC Administrator Date: Sat, 17 Sep 2022 00:17:20 +0000 Subject: Daily bump. --- libgcc/ChangeLog | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 'libgcc') diff --git a/libgcc/ChangeLog b/libgcc/ChangeLog index e0deb15..d07fc9c 100644 --- a/libgcc/ChangeLog +++ b/libgcc/ChangeLog @@ -1,3 +1,15 @@ +2022-09-16 Thomas Neumann + + * unwind-dw2-fde.c (release_registered_frames): Cleanup at shutdown. + (__register_frame_info_table_bases): Use btree in atomic fast path. + (__deregister_frame_info_bases): Likewise. + (_Unwind_Find_FDE): Likewise. + (base_from_object): Make parameter const. + (classify_object_over_fdes): Add query-only mode. + (get_pc_range): Compute PC range for lookup. + * unwind-dw2-fde.h (last_fde): Make parameter const. + * unwind-dw2-btree.h: New file. + 2022-08-31 Martin Liska * config.host: Remove hppa. -- cgit v1.1 From d458f806afe07d1e06bdf275e94d05a716f41bf6 Mon Sep 17 00:00:00 2001 From: Thomas Neumann Date: Sun, 18 Sep 2022 11:31:01 +0200 Subject: Remove dependency on uintptr_t in libgcc uintptr_t is no available for all targets, use __UINTPTR_TYPE__ instead. libgcc/ChangeLog: * unwind-dw2-fde.c: Replace uintptr_t with typedef for __UINTPTR_TYPE__. * unwind-dw2-btree.h: Likewise. --- libgcc/unwind-dw2-btree.h | 69 ++++++++++++++++++++++++----------------------- libgcc/unwind-dw2-fde.c | 18 +++++++------ 2 files changed, 45 insertions(+), 42 deletions(-) (limited to 'libgcc') diff --git a/libgcc/unwind-dw2-btree.h b/libgcc/unwind-dw2-btree.h index 8853f0e..ace507d 100644 --- a/libgcc/unwind-dw2-btree.h +++ b/libgcc/unwind-dw2-btree.h @@ -39,7 +39,7 @@ struct version_lock // range. Even on 32 bit platforms that would require 1 billion // frame registrations within the time span of a few assembler // instructions. - uintptr_t version_lock; + uintptr_type version_lock; }; #ifdef __GTHREAD_HAS_COND @@ -60,7 +60,7 @@ version_lock_initialize_locked_exclusive (struct version_lock *vl) static inline bool version_lock_try_lock_exclusive (struct version_lock *vl) { - uintptr_t state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); + uintptr_type state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); if (state & 1) return false; return __atomic_compare_exchange_n (&(vl->version_lock), &state, state | 1, @@ -78,7 +78,7 @@ restart: // We should virtually never get contention here, as frame // changes are rare. - uintptr_t state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); + uintptr_type state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); if (!(state & 1)) { if (__atomic_compare_exchange_n (&(vl->version_lock), &state, state | 1, @@ -134,8 +134,8 @@ static void version_lock_unlock_exclusive (struct version_lock *vl) { // increase version, reset exclusive lock bits - uintptr_t state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); - uintptr_t ns = (state + 4) & (~((uintptr_t) 3)); + uintptr_type state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); + uintptr_type ns = (state + 4) & (~((uintptr_type) 3)); state = __atomic_exchange_n (&(vl->version_lock), ns, __ATOMIC_SEQ_CST); #ifdef __GTHREAD_HAS_COND @@ -152,9 +152,9 @@ version_lock_unlock_exclusive (struct version_lock *vl) // Acquire an optimistic "lock". Note that this does not lock at all, it // only allows for validation later. static inline bool -version_lock_lock_optimistic (const struct version_lock *vl, uintptr_t *lock) +version_lock_lock_optimistic (const struct version_lock *vl, uintptr_type *lock) { - uintptr_t state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); + uintptr_type state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); *lock = state; // Acquiring the lock fails when there is currently an exclusive lock. @@ -163,7 +163,7 @@ version_lock_lock_optimistic (const struct version_lock *vl, uintptr_t *lock) // Validate a previously acquired "lock". static inline bool -version_lock_validate (const struct version_lock *vl, uintptr_t lock) +version_lock_validate (const struct version_lock *vl, uintptr_type lock) { // Prevent the reordering of non-atomic loads behind the atomic load. // Hans Boehm, Can Seqlocks Get Along with Programming Language Memory @@ -171,26 +171,26 @@ version_lock_validate (const struct version_lock *vl, uintptr_t lock) __atomic_thread_fence (__ATOMIC_ACQUIRE); // Check that the node is still in the same state. - uintptr_t state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); + uintptr_type state = __atomic_load_n (&(vl->version_lock), __ATOMIC_SEQ_CST); return (state == lock); } // The largest possible separator value. -static const uintptr_t max_separator = ~((uintptr_t) (0)); +static const uintptr_type max_separator = ~((uintptr_type) (0)); struct btree_node; // Inner entry. The child tree contains all entries <= separator. struct inner_entry { - uintptr_t separator; + uintptr_type separator; struct btree_node *child; }; // Leaf entry. Stores an object entry. struct leaf_entry { - uintptr_t base, size; + uintptr_type base, size; struct object *ob; }; @@ -248,7 +248,7 @@ btree_node_needs_merge (const struct btree_node *n) } // Get the fence key for inner nodes. -static inline uintptr_t +static inline uintptr_type btree_node_get_fence_key (const struct btree_node *n) { // For inner nodes we just return our right-most entry. @@ -257,7 +257,7 @@ btree_node_get_fence_key (const struct btree_node *n) // Find the position for a slot in an inner node. static unsigned -btree_node_find_inner_slot (const struct btree_node *n, uintptr_t value) +btree_node_find_inner_slot (const struct btree_node *n, uintptr_type value) { for (unsigned index = 0, ec = n->entry_count; index != ec; ++index) if (n->content.children[index].separator >= value) @@ -267,7 +267,7 @@ btree_node_find_inner_slot (const struct btree_node *n, uintptr_t value) // Find the position for a slot in a leaf node. static unsigned -btree_node_find_leaf_slot (const struct btree_node *n, uintptr_t value) +btree_node_find_leaf_slot (const struct btree_node *n, uintptr_type value) { for (unsigned index = 0, ec = n->entry_count; index != ec; ++index) if (n->content.entries[index].base + n->content.entries[index].size > value) @@ -299,14 +299,14 @@ btree_node_unlock_exclusive (struct btree_node *n) // Acquire an optimistic "lock". Note that this does not lock at all, it // only allows for validation later. static inline bool -btree_node_lock_optimistic (const struct btree_node *n, uintptr_t *lock) +btree_node_lock_optimistic (const struct btree_node *n, uintptr_type *lock) { return version_lock_lock_optimistic (&(n->version_lock), lock); } // Validate a previously acquire lock. static inline bool -btree_node_validate (const struct btree_node *n, uintptr_t lock) +btree_node_validate (const struct btree_node *n, uintptr_type lock) { return version_lock_validate (&(n->version_lock), lock); } @@ -314,8 +314,8 @@ btree_node_validate (const struct btree_node *n, uintptr_t lock) // Insert a new separator after splitting. static void btree_node_update_separator_after_split (struct btree_node *n, - uintptr_t old_separator, - uintptr_t new_separator, + uintptr_type old_separator, + uintptr_type new_separator, struct btree_node *new_right) { unsigned slot = btree_node_find_inner_slot (n, old_separator); @@ -474,13 +474,13 @@ btree_handle_root_split (struct btree *t, struct btree_node **node, // Split an inner node. static void btree_split_inner (struct btree *t, struct btree_node **inner, - struct btree_node **parent, uintptr_t target) + struct btree_node **parent, uintptr_type target) { // Check for the root. btree_handle_root_split (t, inner, parent); // Create two inner node. - uintptr_t right_fence = btree_node_get_fence_key (*inner); + uintptr_type right_fence = btree_node_get_fence_key (*inner); struct btree_node *left_inner = *inner; struct btree_node *right_inner = btree_allocate_node (t, true); unsigned split = left_inner->entry_count / 2; @@ -489,7 +489,7 @@ btree_split_inner (struct btree *t, struct btree_node **inner, right_inner->content.children[index] = left_inner->content.children[split + index]; left_inner->entry_count = split; - uintptr_t left_fence = btree_node_get_fence_key (left_inner); + uintptr_type left_fence = btree_node_get_fence_key (left_inner); btree_node_update_separator_after_split (*parent, right_fence, left_fence, right_inner); if (target <= left_fence) @@ -507,13 +507,14 @@ btree_split_inner (struct btree *t, struct btree_node **inner, // Split a leaf node. static void btree_split_leaf (struct btree *t, struct btree_node **leaf, - struct btree_node **parent, uintptr_t fence, uintptr_t target) + struct btree_node **parent, uintptr_type fence, + uintptr_type target) { // Check for the root. btree_handle_root_split (t, leaf, parent); // Create two leaf nodes. - uintptr_t right_fence = fence; + uintptr_type right_fence = fence; struct btree_node *left_leaf = *leaf; struct btree_node *right_leaf = btree_allocate_node (t, false); unsigned split = left_leaf->entry_count / 2; @@ -522,7 +523,7 @@ btree_split_leaf (struct btree *t, struct btree_node **leaf, right_leaf->content.entries[index] = left_leaf->content.entries[split + index]; left_leaf->entry_count = split; - uintptr_t left_fence = right_leaf->content.entries[0].base - 1; + uintptr_type left_fence = right_leaf->content.entries[0].base - 1; btree_node_update_separator_after_split (*parent, right_fence, left_fence, right_leaf); if (target <= left_fence) @@ -540,7 +541,7 @@ btree_split_leaf (struct btree *t, struct btree_node **leaf, // Merge (or balance) child nodes. static struct btree_node * btree_merge_node (struct btree *t, unsigned child_slot, - struct btree_node *parent, uintptr_t target) + struct btree_node *parent, uintptr_type target) { // Choose the emptiest neighbor and lock both. The target child is already // locked. @@ -693,7 +694,7 @@ btree_merge_node (struct btree *t, unsigned child_slot, left_node->entry_count += to_shift; right_node->entry_count -= to_shift; } - uintptr_t left_fence; + uintptr_type left_fence; if (btree_node_is_leaf (left_node)) { left_fence = right_node->content.entries[0].base - 1; @@ -718,7 +719,7 @@ btree_merge_node (struct btree *t, unsigned child_slot, // Insert an entry. static bool -btree_insert (struct btree *t, uintptr_t base, uintptr_t size, +btree_insert (struct btree *t, uintptr_type base, uintptr_type size, struct object *ob) { // Sanity check. @@ -747,7 +748,7 @@ btree_insert (struct btree *t, uintptr_t base, uintptr_t size, // But that is more difficult to implement and frame registration is // rare anyway, we use simple locking for now. - uintptr_t fence = max_separator; + uintptr_type fence = max_separator; while (btree_node_is_inner (iter)) { // Use eager splits to avoid lock coupling up. @@ -790,7 +791,7 @@ btree_insert (struct btree *t, uintptr_t base, uintptr_t size, // Remove an entry. static struct object * -btree_remove (struct btree *t, uintptr_t base) +btree_remove (struct btree *t, uintptr_type base) { // Access the root. version_lock_lock_exclusive (&(t->root_lock)); @@ -838,7 +839,7 @@ btree_remove (struct btree *t, uintptr_t base) // Find the corresponding entry for the given address. static struct object * -btree_lookup (const struct btree *t, uintptr_t target_addr) +btree_lookup (const struct btree *t, uintptr_type target_addr) { // Within this function many loads are relaxed atomic loads. // Use a macro to keep the code reasonable. @@ -867,7 +868,7 @@ btree_lookup (const struct btree *t, uintptr_t target_addr) restart: struct btree_node *iter; - uintptr_t lock; + uintptr_type lock; { // Accessing the root node requires defending against concurrent pointer // changes Thus we couple rootLock -> lock on root node -> validate rootLock @@ -878,7 +879,7 @@ restart: goto restart; if (!iter) return NULL; - uintptr_t child_lock; + uintptr_type child_lock; if ((!btree_node_lock_optimistic (iter, &child_lock)) || (!version_lock_validate (&(t->root_lock), lock))) goto restart; @@ -910,7 +911,7 @@ restart: // The node content can change at any point in time, thus we must // interleave parent and child checks. - uintptr_t child_lock; + uintptr_type child_lock; if (!btree_node_lock_optimistic (child, &child_lock)) goto restart; if (!btree_node_validate (iter, lock)) diff --git a/libgcc/unwind-dw2-fde.c b/libgcc/unwind-dw2-fde.c index 000ee69..919abfe 100644 --- a/libgcc/unwind-dw2-fde.c +++ b/libgcc/unwind-dw2-fde.c @@ -42,6 +42,8 @@ see the files COPYING3 and COPYING.RUNTIME respectively. If not, see #endif #endif +typedef __UINTPTR_TYPE__ uintptr_type; + #ifdef ATOMIC_FDE_FAST_PATH #include "unwind-dw2-btree.h" @@ -58,7 +60,7 @@ release_registered_frames (void) } static void -get_pc_range (const struct object *ob, uintptr_t *range); +get_pc_range (const struct object *ob, uintptr_type *range); static void init_object (struct object *ob); @@ -124,7 +126,7 @@ __register_frame_info_bases (const void *begin, struct object *ob, init_object (ob); // And register the frame - uintptr_t range[2]; + uintptr_type range[2]; get_pc_range (ob, range); btree_insert (®istered_frames, range[0], range[1] - range[0], ob); #else @@ -178,7 +180,7 @@ __register_frame_info_table_bases (void *begin, struct object *ob, init_object (ob); // And register the frame - uintptr_t range[2]; + uintptr_type range[2]; get_pc_range (ob, range); btree_insert (®istered_frames, range[0], range[1] - range[0], ob); #else @@ -237,7 +239,7 @@ __deregister_frame_info_bases (const void *begin) #ifdef DWARF2_OBJECT_END_PTR_EXTENSION lookupob.fde_end = NULL; #endif - uintptr_t range[2]; + uintptr_type range[2]; get_pc_range (&lookupob, range); // And remove @@ -677,7 +679,7 @@ end_fde_sort (struct object *ob, struct fde_accumulator *accu, size_t count) static size_t classify_object_over_fdes (struct object *ob, const fde *this_fde, - uintptr_t *range) + uintptr_type *range) { const struct dwarf_cie *last_cie = 0; size_t count = 0; @@ -892,11 +894,11 @@ init_object (struct object* ob) #ifdef ATOMIC_FDE_FAST_PATH /* Get the PC range for lookup */ static void -get_pc_range (const struct object *ob, uintptr_t *range) +get_pc_range (const struct object *ob, uintptr_type *range) { // It is safe to cast to non-const object* here as // classify_object_over_fdes does not modify ob in query mode. - struct object *ncob = (struct object *) (uintptr_t) ob; + struct object *ncob = (struct object *) (uintptr_type) ob; range[0] = range[1] = 0; if (ob->s.b.sorted) { @@ -1131,7 +1133,7 @@ _Unwind_Find_FDE (void *pc, struct dwarf_eh_bases *bases) const fde *f = NULL; #ifdef ATOMIC_FDE_FAST_PATH - ob = btree_lookup (®istered_frames, (uintptr_t) pc); + ob = btree_lookup (®istered_frames, (uintptr_type) pc); if (!ob) return NULL; -- cgit v1.1 From 0990a778376b63b789a8ff5aa949325ba375c025 Mon Sep 17 00:00:00 2001 From: GCC Administrator Date: Mon, 19 Sep 2022 00:17:27 +0000 Subject: Daily bump. --- libgcc/ChangeLog | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'libgcc') diff --git a/libgcc/ChangeLog b/libgcc/ChangeLog index d07fc9c..7c434c9 100644 --- a/libgcc/ChangeLog +++ b/libgcc/ChangeLog @@ -1,3 +1,9 @@ +2022-09-18 Thomas Neumann + + * unwind-dw2-fde.c: Replace uintptr_t with typedef + for __UINTPTR_TYPE__. + * unwind-dw2-btree.h: Likewise. + 2022-09-16 Thomas Neumann * unwind-dw2-fde.c (release_registered_frames): Cleanup at shutdown. -- cgit v1.1 From 0b5b8ac5cb7fe92dd17ae8bd7de84640daa59e84 Mon Sep 17 00:00:00 2001 From: Georg-Johann Lay Date: Mon, 19 Sep 2022 09:46:58 +0200 Subject: Fix PR target/99184: Wrong cast from double to 16-bit and 32-bit ints this patch fixed PR target/99184 which incorrectly rounded during 64-bit (long) double to 16-bit and 32-bit integers. The patch just removes the respective roundings from libf7-asm.sx::to_integer and ::to_unsigned. Luckily, LibF7 does nowhere use respective functions internally, the only user is in libf7.c::f7_exp which reads f7_round (qq, qq); int16_t q = f7_get_s16 (qq); so that f7_get_s16() operates on an already rounded value, and therefore this code works unaltered with or without rounding in to_integer. PR target/99184 libgcc/config/avr/libf7/ * libf7-asm.sx (to_integer, to_unsigned): Don't round 16-bit and 32-bit integers. --- libgcc/config/avr/libf7/libf7-asm.sx | 50 ------------------------------------ 1 file changed, 50 deletions(-) (limited to 'libgcc') diff --git a/libgcc/config/avr/libf7/libf7-asm.sx b/libgcc/config/avr/libf7/libf7-asm.sx index cfdbecd..752a939 100644 --- a/libgcc/config/avr/libf7/libf7-asm.sx +++ b/libgcc/config/avr/libf7/libf7-asm.sx @@ -601,9 +601,6 @@ DEFUN to_integer tst C6 brmi .Lsaturate.T ; > INTxx_MAX => saturate - rcall .Lround - brmi .Lsaturate.T ; > INTxx_MAX => saturate - brtc 9f ; >= 0 => return sbrc Mask, 5 .global __negdi2 @@ -658,30 +655,6 @@ DEFUN to_integer .global __clr_8 XJMP __clr_8 -.Lround: - ;; C6.7 is known to be 0 here. - ;; Return N = 1 iff we have to saturate. - cpi Mask, 0xf - breq .Lround16 - cpi Mask, 0x1f - breq .Lround32 - - ;; For now, no rounding in the 64-bit case. This rounding - ;; would have to be integrated into the right-shift. - cln - ret - -.Lround32: - rol C2 - adc C3, ZERO - adc C4, ZERO - rjmp 2f - -.Lround16: - rol C4 -2: adc C5, ZERO - adc C6, ZERO - ret ENDF to_integer #endif /* F7MOD_to_integer_ */ @@ -725,29 +698,6 @@ DEFUN to_unsigned clr CA F7call lshrdi3 POP r16 - - ;; Rounding - ;; ??? C6.7 is known to be 0 here. - cpi Mask, 0xf - breq .Lround16 - cpi Mask, 0x1f - breq .Lround32 - - ;; For now, no rounding in the 64-bit case. This rounding - ;; would have to be integrated into the right-shift. - ret - -.Lround32: - rol C2 - adc C3, ZERO - adc C4, ZERO - rjmp 2f - -.Lround16: - rol C4 -2: adc C5, ZERO - adc C6, ZERO - brcs .Lset_0xffff ; Rounding overflow => saturate ret .Lset_0xffff: -- cgit v1.1 From 43be56c4c6fb6b7f059df832eefb1cd049ff02de Mon Sep 17 00:00:00 2001 From: GCC Administrator Date: Tue, 20 Sep 2022 00:17:49 +0000 Subject: Daily bump. --- libgcc/config/avr/libf7/ChangeLog | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'libgcc') diff --git a/libgcc/config/avr/libf7/ChangeLog b/libgcc/config/avr/libf7/ChangeLog index d24215e..026dafd 100644 --- a/libgcc/config/avr/libf7/ChangeLog +++ b/libgcc/config/avr/libf7/ChangeLog @@ -1,3 +1,9 @@ +2022-09-19 Georg-Johann Lay + + PR target/99184 + * libf7-asm.sx (to_integer, to_unsigned): Don't round 16-bit + and 32-bit integers. + 2020-06-23 David Edelsohn * t-libf7: Use -include. -- cgit v1.1