https://gcc.gnu.org/bugzilla/show_bug.cgi?id=119151
--- Comment #18 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The releases/gcc-13 branch has been updated by Jakub Jelinek <ja...@gcc.gnu.org>: https://gcc.gnu.org/g:bfdd0e68a045d206c6053ddcdb18290d61b949dd commit r13-9596-gbfdd0e68a045d206c6053ddcdb18290d61b949dd Author: Jakub Jelinek <ja...@redhat.com> Date: Mon Mar 10 10:34:00 2025 +0100 libgcc: Fix up unwind-dw2-btree.h [PR119151] The following testcase shows a bug in unwind-dw2-btree.h. In short, the header provides lock-free btree data structure (so no parent link on nodes, both insertion and deletion are done in top-down walks with some locking of just a few nodes at a time so that lookups can notice concurrent modifications and retry, non-leaf (inner) nodes contain keys which are initially the base address of the left-most leaf entry of the following child (or all ones if there is none) minus one, insertion ensures balancing of the tree to ensure [d/2, d] entries filled through aggressive splitting if it sees a full tree while walking, deletion performs various operations like merging neighbour trees, merging into parent or moving some nodes from neighbour to the current one). What differs from the textbook implementations is mostly that the leaf nodes don't include just address as a key, but address range, address + size (where we don't insert any ranges with zero size) and the lookups can be performed for any address in the [address, address + size) range. The keys on inner nodes are still just address-1, so the child covers all nodes where addr <= key unless it is covered already in children to the left. The user (static executables or JIT) should always ensure there is no overlap in between any of the ranges. In the testcase a bunch of insertions are done, always followed by one removal, followed by one insertion of a range slightly different from the removed one. E.g. in the first case [&code[0x50], &code[0x59]] range is removed and then we insert [&code[0x4c], &code[0x53]] range instead. This is valid, it doesn't overlap anything. But the problem is that some non-leaf (inner) one used the &code[0x4f] key (after the 11 insertions completely correctly). On removal, nothing adjusts the keys on the parent nodes (it really can't in the top-down only walk, the keys could be many nodes above it and unlike insertion, removal only knows the start address, doesn't know the removed size and so will discover it only when reaching the leaf node which contains it; plus even if it knew the address and size, it still doesn't know what the second left-most leaf node will be (i.e. the one after removal)). And on insertion, if nodes aren't split at a level, nothing adjusts the inner keys either. If a range is inserted and is either fully bellow key (keys are - 1, so having address + size - 1 being equal to key is fine) or fully after key (i.e. address > key), it works just fine, but if the key is in a middle of the range like in this case, &code[0x4f] is in the middle of the [&code[0x4c], &code[0x53]] range, then insertion works fine (we only use size on the leaf nodes), and lookup of the addresses below the key work fine too (i.e. [&code[0x4c], &code[0x4f]] will succeed). The problem is with lookups after the key (i.e. [&code[0x50, &code[0x53]]), the lookup looks for them in different children of the btree and doesn't find an entry and returns NULL. As users need to ensure non-overlapping entries at any time, the following patch fixes it by adjusting keys during insertion where we know not just the address but also size; if we find during the top-down walk a key which is in the middle of the range being inserted, we simply increase the key to be equal to address + size - 1 of the range being inserted. There can't be any existing leaf nodes overlapping the range in correct programs and the btree rebalancing done on deletion ensures we don't have any empty nodes which would also cause problems. The patch adjusts the keys in two spots, once for the current node being walked (the last hunk in the header, with large comment trying to explain it) and once during inner node splitting in a parent node if we'd otherwise try to add that key in the middle of the range being inserted into the parent node (in that case it would be missed in the last hunk). The testcase covers both of those spots, so succeeds with GCC 12 (which didn't have btrees) and fails with vanilla GCC trunk and also fails if either the if (fence < base + size - 1) fence = iter->content.children[slot].separator = base + size - 1; or if (left_fence >= target && left_fence < target + size - 1) left_fence = target + size - 1; hunk is removed (of course, only with the current node sizes, i.e. up to 15 children of inner nodes and up to 10 entries in leaf nodes). 2025-03-10 Jakub Jelinek <ja...@redhat.com> Michael Leuchtenburg <mich...@slashhome.org> PR libgcc/119151 * unwind-dw2-btree.h (btree_split_inner): Add size argument. If left_fence is in the middle of [target,target + size - 1] range, increase it to target + size - 1. (btree_insert): Adjust btree_split_inner caller. If fence is smaller than base + size - 1, increase it and separator of the slot to base + size - 1. * gcc.dg/pr119151.c: New test. (cherry picked from commit 21109b37e8585a7a1b27650fcbf1749380016108)
