When collecting old nodes for destruction, the dead range check uses
tmp_next->index and tmp_next->last, which implicitly dereferences
tmp_next[0] rather than the intended dead range. This means children
at indices n=1 or n=2 are compared against the first child's state
instead of the replacement range [mas->index, mas->last].

This currently produces correct results by coincidence -- mas_find_child()
copies the parent state and mas_descend() preserves index/last, so the
values always equal mas->index/last. Fix it to use the canonical source
directly, as documented: "Nodes within [index, last] are dead subtrees".

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Josh Law <objecting@objecting.org>
---
 lib/maple_tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 1eaaa5f964e9..64ba117ec254 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1874,8 +1874,8 @@ static inline void mas_topiary_replace(struct ma_state *mas,
 				if (!mas_find_child(&tmp[i], &tmp_next[n]))
 					break;
 
-				if ((tmp_next[n].min >= tmp_next->index) &&
-				    (tmp_next[n].max <= tmp_next->last)) {
+				if ((tmp_next[n].min >= mas->index) &&
+				    (tmp_next[n].max <= mas->last)) {
 					mat_add(&subtrees, tmp_next[n].node);
 					tmp_next[n].status = ma_none;
 				} else {
-- 
2.34.1

* Josh Law <objecting@objecting.org> [260317 18:29]:
> When collecting old nodes for destruction, the dead range check uses
> tmp_next->index and tmp_next->last, which implicitly dereferences
> tmp_next[0] rather than the intended dead range. This means children
> at indices n=1 or n=2 are compared against the first child's state
> instead of the replacement range [mas->index, mas->last].
> 
> This currently produces correct results by coincidence -- mas_find_child()
> copies the parent state and mas_descend() preserves index/last, so the
> values always equal mas->index/last. Fix it to use the canonical source
> directly, as documented: "Nodes within [index, last] are dead subtrees".

NACK

I'd rather reference the same struct if we're going to fix this and I'm
not wasting more time on any patches from objecting.


> 
> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> Signed-off-by: Josh Law <objecting@objecting.org>
> ---
>  lib/maple_tree.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 1eaaa5f964e9..64ba117ec254 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -1874,8 +1874,8 @@ static inline void mas_topiary_replace(struct ma_state *mas,
>  				if (!mas_find_child(&tmp[i], &tmp_next[n]))
>  					break;
>  
> -				if ((tmp_next[n].min >= tmp_next->index) &&
> -				    (tmp_next[n].max <= tmp_next->last)) {
> +				if ((tmp_next[n].min >= mas->index) &&
> +				    (tmp_next[n].max <= mas->last)) {
>  					mat_add(&subtrees, tmp_next[n].node);
>  					tmp_next[n].status = ma_none;
>  				} else {
> -- 
> 2.34.1
> 
> 
> -- 
> maple-tree mailing list
> maple-tree@lists.infradead.org
> https://lists.infradead.org/mailman/listinfo/maple-tree