On Sat, Apr 13, 2019 at 11:50 PM Pierre Bourdon <delr...@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 <delr...@gmail.com> Software Engineer @ Zürich, Switzerland https://delroth.net/ _______________________________________________ U-Boot mailing list U-Boot@lists.denx.de https://lists.denx.de/listinfo/u-boot