On Sun, Apr 14, 2019 at 12:05 AM Pierre Bourdon <[email protected]> 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 <[email protected]> Software Engineer @ Zürich, Switzerland https://delroth.net/ _______________________________________________ U-Boot mailing list [email protected] https://lists.denx.de/listinfo/u-boot
