[U-Boot] [PATCH] fs: btrfs: fix btrfs_search_tree invalid results

[Marek Behun]

Hi Pierre

On Mon, 15 Apr 2019 03:30:32 +0200
Pierre Bourdon <delroth at gmail.com> 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 <delroth at gmail.com>
> Cc: Marek Behun <marek.behun at nic.cz>
> ---
>  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