From: Marek Behun Date: Mon, 15 Apr 2019 04:58:31 +0200 Subject: [U-Boot] [PATCH] fs: btrfs: fix btrfs_search_tree invalid results In-Reply-To: <20190415013032.17983-1-delroth@gmail.com> References: <20190415013032.17983-1-delroth@gmail.com> Message-ID: <20190415045831.17ed0044@nic.cz> List-Id: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: u-boot@lists.denx.de Hi Pierre On Mon, 15 Apr 2019 03:30:32 +0200 Pierre Bourdon wrote: > btrfs_search_tree should return the first item in the tree that is > greater or equal to the searched item. > > The search algorithm did not properly handle the edge case where the > searched item is higher than the last item of the node but lower than > the first item of the next node. Instead of properly returning the first > item of the next node, it was returning an invalid path pointer > (pointing to a non-existent item after the last item of the node + 1). > > This fixes two issues in the btrfs driver: > - Looking for a ROOT_ITEM could fail if it was the first item of its > leaf node. > - Iterating through DIR_INDEX entries (for readdir) could fail if the > first DIR_INDEX entry was the first item of a leaf node. > > Signed-off-by: Pierre Bourdon > Cc: Marek Behun > --- > fs/btrfs/ctree.c | 7 ++++++- > 1 file changed, 6 insertions(+), 1 deletion(-) > > diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c > index d248d79932..55246ea0fc 100644 > --- a/fs/btrfs/ctree.c > +++ b/fs/btrfs/ctree.c > @@ -187,8 +187,13 @@ int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key, > > if (lvl) > logical = buf->node.ptrs[slot].blockptr; > - else > + else { > + /* cur leaf max < searched value < next leaf min */ > + if (slot >= buf->header.nritems) > + if (btrfs_next_slot(p) < 0) > + goto err; > break; > + } Hi Pierre, if you are adding { } braces to else, please add them to the if also. Also comment that you are correcting for invalid slot value. if (lvl) { logical = buf->node.ptrs[slot].blockptr; } else { /* * Slot can have invalid value if * current leaf max < searched value < next leaf min. * Jump to next in this case. */ if (slot >= buf->header.nritems) if (btrfs_next_slot(p) < 0) goto err; break; } Otherwise thanks, I encountered some problems a once or twice but didn't have time to investigate. Marek