On Sun, Apr 14, 2019 at 12:05 AM Pierre Bourdon delroth@gmail.com wrote:
A more practical example in case the explanation isn't clear:
root tree node 122216448 level 1 items 6 free 115 generation 12246 owner ROOT_TREE fs uuid b516974e-a94e-469c-a9ff-d237ce96b03b chunk uuid ecfa1e4e-8832-49c1-bb0c-2f08b95586a0 key (EXTENT_TREE ROOT_ITEM 0) block 122810368 gen 12246 key (ROOT_TREE_DIR INODE_REF 6) block 122339328 gen 12246 key (344 ROOT_ITEM 9422) block 209317888 gen 12115 key (344 ROOT_BACKREF 5) block 226222080 gen 12126 key (368 ROOT_ITEM 11665) block 114966528 gen 12127 key (375 ROOT_ITEM 12127) block 122949632 gen 12246
If you look for (375 ROOT_ITEM) then using (375 ROOT_ITEM 0) as the search key will end up walking to block 114966528 (because (375 ROOT_ITEM 0) < (375 ROOT_ITEM 12127)). Using instead (375 ROOT_ITEM -1) will go to the right leaf, return the first item after (375 ROOT_ITEM 12127), and we can then walk back one slot to get the item we wanted.
So turns out there's a very similar bug when iterating DIR_INDEX entries -- but that one isn't using btrfs_search_tree_key_type. It's doing its own thing with offset = 0 to enumerate multiple items of the same oid/type.
Looking back at this, I think there's a much better way to fix both issues. Currently, btrfs_search_tree will return an invalid path if it's asked to look for an item between end of leaf N and beginning of leaf N+1. Invalid, as in, accessing the element at this path reads past the end of an array... This seems like a very broken behavior given that callers have no way of knowing the path is invalid without dereferencing it.
Instead, btrfs_search_tree should be fixed so that it always returns either: 1. The first element >= searched element. 2. An error if no such element exists.
This can be done with a fairly trivial change to btrfs_search_tree: if we're about to return something that's past the end of the leaf (slot
= nritems), call btrfs_next_slot on the path. If btrfs_next_slot
works return that, otherwise return an error.
I'll send another patch which implements that instead. I've verified it fixes both the root lookup issue I was originally looking for + the DIR_INDEX issue as well. Please disregard the patch I originally sent.
-- Pierre Bourdon delroth@gmail.com Software Engineer @ Zürich, Switzerland https://delroth.net/