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

[Pierre Bourdon]

On Sat, Apr 13, 2019 at 11:50 PM Pierre Bourdon <delroth at gmail.com> wrote:
>
> ROOT_ITEMs in btrfs are referenced without knowing their actual "offset"
> value. To perform these searches using only two items from the key, the
> btrfs driver uses a special "btrfs_search_tree_key_type" function.
>
> The algorithm used by that function to transform a 3-tuple search into a
> 2-tuple search was subtly broken, leading to items not being found if
> they were the first in their tree node.
>
> This commit fixes btrfs_search_tree_key_type to properly behave in these
> situations.

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.

-- 
Pierre Bourdon <delroth at gmail.com>
Software Engineer @ Zürich, Switzerland
https://delroth.net/