Message-ID: <cec2dec7-818a-b32c-3ad4-8b23fc1351f3@bytedance.com>
Date:   Tue, 7 Mar 2023 21:05:46 +0800
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0)
 Gecko/20100101 Thunderbird/102.8.0
Subject: Re: [PATCH 1/2] maple_tree: Fix mas_skip_node() end slot detection
To:     "Liam R. Howlett" <Liam.Howlett@oracle.com>
Cc:     Stable@vger.kernel.org, maple-tree@lists.infradead.org,
        linux-mm@kvack.org, linux-kernel@vger.kernel.org,
        Andrew Morton <akpm@linux-foundation.org>,
        Snild Dolkow <snild@sony.com>
References: <20230303021540.1056603-1-Liam.Howlett@oracle.com>
From:   Peng Zhang <zhangpeng.00@bytedance.com>
In-Reply-To: <20230303021540.1056603-1-Liam.Howlett@oracle.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk

Hi, Liam,
> mas_skip_node() is used to move the maple state to the node with a
> higher limit.  It does this by walking up the tree and increasing the
> slot count.  Since slot count may not be able to be increased, it may
> need to walk up multiple times to find room to walk right to a higher
> limit node.  The limit of slots that was being used was the node limit
> and not the last location of data in the node.  This would cause the
> maple state to be shifted outside actual data and enter an error state,
> thus returning -EBUSY.
> 
> The result of the incorrect error state means that mas_awalk() would
> return an error instead of finding the allocation space.
> 
> The fix is to use mas_data_end() in mas_skip_node() to detect the nodes
> data end point and continue walking the tree up until it is safe to move
> to a node with a higher limit.
> 
> mas_skip_node() may also be passed a maple state in an error state from
> mas_anode_descend() when no allocations are available.  Return on such
> an error state immediately.
> 
> Reported-by: Snild Dolkow <snild@sony.com>
> Link: https://lore.kernel.org/linux-mm/cb8dc31a-fef2-1d09-f133-e9f7b9f9e77a@sony.com/
> Cc: <Stable@vger.kernel.org>
> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reviewed-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>   lib/maple_tree.c | 25 ++++++++++---------------
>   1 file changed, 10 insertions(+), 15 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 2be86368237d..2efe854946d6 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5188,34 +5188,29 @@ static inline bool mas_rewind_node(struct ma_state *mas)
>    */
>   static inline bool mas_skip_node(struct ma_state *mas)
>   {
> -	unsigned char slot, slot_count;
>   	unsigned long *pivots;
>   	enum maple_type mt;
>   
> -	mt = mte_node_type(mas->node);
> -	slot_count = mt_slots[mt] - 1;
> +	if (mas_is_err(mas))
> +		return false;
> +
>   	do {
>   		if (mte_is_root(mas->node)) {
> -			slot = mas->offset;
> -			if (slot > slot_count) {
> +			if (mas->offset >= mas_data_end(mas)) {
>   				mas_set_err(mas, -EBUSY);
>   				return false;
>   			}
>   		} else {
>   			mas_ascend(mas);
> -			slot = mas->offset;
> -			mt = mte_node_type(mas->node);
> -			slot_count = mt_slots[mt] - 1;
>   		}
> -	} while (slot > slot_count);
> +	} while (mas->offset >= mas_data_end(mas));
>   
> -	mas->offset = ++slot;
> +	mt = mte_node_type(mas->node);
>   	pivots = ma_pivots(mas_mn(mas), mt);
> -	if (slot > 0)
> -		mas->min = pivots[slot - 1] + 1;
> -
> -	if (slot <= slot_count)
> -		mas->max = pivots[slot];
> +	mas->min = pivots[mas->offset] + 1;
> +	mas->offset++;
> +	if (mas->offset < mt_slots[mt])
> +		mas->max = pivots[mas->offset];
There is a bug here, the assignment of mas->min and mas->max is wrong.
The assignment will make them represent the range of a child node, but 
it should represent the range of the current node. After mas_ascend() 
returns, mas-min and mas->max already represent the range of the current 
node, so we should delete these assignments of mas->min and mas->max.
>   
>   	return true;
>   }

Sincerely yours,
Peng.