[U-Boot] [PATCH] fs: btrfs: fix false negatives in ROOT_ITEM search

[Pierre Bourdon]

On Sun, Apr 14, 2019 at 12:05 AM Pierre Bourdon <delroth at 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 at gmail.com>
Software Engineer @ Zürich, Switzerland
https://delroth.net/