[PATCH 1/2] maple_tree: add test to replicate low memory race conditions

[PATCH 1/2] maple_tree: add test to replicate low memory race conditions

[Sidhartha Kumar]

Add new callback fields to the userspace implementation of struct
kmem_cache. This allows for executing callback functions in order to
further test low memory scenarios where node allocation is retried.

This callback can help test race conditions by calling a function when a
low memory event is tested". This exposes a race condition that is
addressed in a subsequent patch.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c                 | 12 +++++++
 tools/testing/radix-tree/maple.c | 60 ++++++++++++++++++++++++++++++++
 tools/testing/shared/linux.c     | 26 +++++++++++++-
 3 files changed, 97 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index aa3a5df15b8e..65fba37ef999 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -6997,6 +6997,18 @@ void mt_set_non_kernel(unsigned int val)
 	kmem_cache_set_non_kernel(maple_node_cache, val);
 }
 
+extern void kmem_cache_set_callback(struct kmem_cache *cachep, void (*callback)(void *));
+void mt_set_callback(void (*callback)(void *))
+{
+	kmem_cache_set_callback(maple_node_cache, callback);
+}
+
+extern void kmem_cache_set_private(struct kmem_cache *cachep, void *private);
+void mt_set_private(void *private)
+{
+	kmem_cache_set_private(maple_node_cache, private);
+}
+
 extern unsigned long kmem_cache_get_alloc(struct kmem_cache *);
 unsigned long mt_get_alloc_size(void)
 {
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index cd1cf05503b4..0e699feb71b8 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -36224,6 +36224,61 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt)
 
 extern void test_kmem_cache_bulk(void);
 
+static void writer2(void *maple_tree)
+{
+	struct maple_tree *mt = (struct maple_tree *)maple_tree;
+	MA_STATE(mas, mt, 0, 0);
+
+	mtree_lock(mas.tree);
+	__mas_set_range(&mas, 6, 10);
+	mas_store(&mas, xa_mk_value(0xC));
+	mas_destroy(&mas);
+	mtree_unlock(mas.tree);
+}
+
+static void check_data_race(struct maple_tree *mt)
+{
+	MA_STATE(mas, mt, 0, 0);
+
+	mt_set_non_kernel(0);
+	/* setup root with 2 values with NULL in between */
+	mtree_store_range(mt, 0, 5, xa_mk_value(0xA), GFP_KERNEL);
+	mtree_store_range(mt, 6, 10, NULL, GFP_KERNEL);
+	mtree_store_range(mt, 11, 15, xa_mk_value(0xB), GFP_KERNEL);
+
+	/* setup writer 2 that will trigger the race condition */
+	mt_set_private(mt);
+	mt_set_callback(writer2);
+
+	mtree_lock(mt);
+	/* erase 0-5 */
+	mas_reset(&mas);
+	mas.index = 0;
+	mas.last = 5;
+	mas_erase(&mas);
+
+	/* index 6-10 should retain the value from writer 2*/
+	check_load(mt, 6, xa_mk_value(0xC));
+	mtree_unlock(mt);
+
+	/* test for the same race but with mas_store_gfp */
+	mtree_store_range(mt, 0, 5, xa_mk_value(0xA), GFP_KERNEL);
+	mtree_store_range(mt, 6, 10, NULL, GFP_KERNEL);
+
+	mtree_lock(mt);
+	mas_reset(&mas);
+	mas.index = 0;
+	mas.last = 5;
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+
+	check_load(mt, 6, xa_mk_value(0xC));
+
+	mt_set_private(NULL);
+	mt_set_callback(NULL);
+	mas_destroy(&mas);
+	mtree_unlock(mt);
+}
+
 void farmer_tests(void)
 {
 	struct maple_node *node;
@@ -36243,6 +36298,11 @@ void farmer_tests(void)
 	node->mr64.pivot[2] = 0;
 	tree.ma_root = mt_mk_node(node, maple_leaf_64);
 	mt_dump(&tree, mt_dump_dec);
+	mtree_destroy(&tree);
+
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_USE_RCU);
+	check_data_race(&tree);
+	mtree_destroy(&tree);
 
 	node->parent = ma_parent_ptr(node);
 	ma_free_rcu(node);
diff --git a/tools/testing/shared/linux.c b/tools/testing/shared/linux.c
index 4eb442206d01..17263696b5d8 100644
--- a/tools/testing/shared/linux.c
+++ b/tools/testing/shared/linux.c
@@ -26,8 +26,21 @@ struct kmem_cache {
 	unsigned int non_kernel;
 	unsigned long nr_allocated;
 	unsigned long nr_tallocated;
+	bool exec_callback;
+	void (*callback)(void *);
+	void *private;
 };
 
+void kmem_cache_set_callback(struct kmem_cache *cachep, void (*callback)(void *))
+{
+	cachep->callback = callback;
+}
+
+void kmem_cache_set_private(struct kmem_cache *cachep, void *private)
+{
+	cachep->private = private;
+}
+
 void kmem_cache_set_non_kernel(struct kmem_cache *cachep, unsigned int val)
 {
 	cachep->non_kernel = val;
@@ -58,9 +71,17 @@ void *kmem_cache_alloc_lru(struct kmem_cache *cachep, struct list_lru *lru,
 {
 	void *p;
 
+	if (cachep->exec_callback) {
+		if (cachep->callback)
+			cachep->callback(cachep->private);
+		cachep->exec_callback = false;
+	}
+
 	if (!(gfp & __GFP_DIRECT_RECLAIM)) {
-		if (!cachep->non_kernel)
+		if (!cachep->non_kernel) {
+			cachep->exec_callback = true;
 			return NULL;
+		}
 
 		cachep->non_kernel--;
 	}
@@ -223,6 +244,9 @@ kmem_cache_create(const char *name, unsigned int size, unsigned int align,
 	ret->objs = NULL;
 	ret->ctor = ctor;
 	ret->non_kernel = 0;
+	ret->exec_callback = false;
+	ret->callback = NULL;
+	ret->private = NULL;
 	return ret;
 }
 
-- 
2.46.0

[PATCH 2/2] maple_tree: reset mas->index and mas->last on write retries

[Sidhartha Kumar]

The following scenario can result in a race condition:

Consider a node with the following indices and values

	a<------->b<----------->c<--------->d
	    0xA        NULL          0xB

	CPU 1			  CPU 2
      ---------        		---------
	mas_set_range(a,b)
	mas_erase()
		-> range is expanded (a,c) because of null expansion

	mas_nomem()
	mas_unlock()
				mas_store_range(b,c,0xC)

The node now looks like:

	a<------->b<----------->c<--------->d
	    0xA        0xC          0xB

	mas_lock()
	mas_erase() <------ range of erase is still (a,c)

The node is now NULL from (a,c) but the write from CPU 2 should have been
retained and range (b,c) should still have 0xC as its value. We can fix
this by re-intializing to the original index and last. This does not need
a cc: Stable as there are no users of the maple tree which use internal
locking and this condition is only possible with internal locking.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 65fba37ef999..6ba95a278326 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5451,14 +5451,21 @@ EXPORT_SYMBOL_GPL(mas_store);
  */
 int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp)
 {
+	unsigned long index = mas->index;
+	unsigned long last = mas->last;
 	MA_WR_STATE(wr_mas, mas, entry);
 
 	mas_wr_store_setup(&wr_mas);
 	trace_ma_write(__func__, mas, 0, entry);
 retry:
 	mas_wr_store_entry(&wr_mas);
-	if (unlikely(mas_nomem(mas, gfp)))
+	if (unlikely(mas_nomem(mas, gfp))) {
+		if (!entry) {
+			mas->index = index;
+			mas->last = last;
+		}
 		goto retry;
+	}
 
 	if (unlikely(mas_is_err(mas)))
 		return xa_err(mas->node);
@@ -6245,17 +6252,19 @@ EXPORT_SYMBOL_GPL(mas_find_range_rev);
 void *mas_erase(struct ma_state *mas)
 {
 	void *entry;
+	unsigned long index = mas->index;
 	MA_WR_STATE(wr_mas, mas, NULL);
 
 	if (!mas_is_active(mas) || !mas_is_start(mas))
 		mas->status = ma_start;
 
-	/* Retry unnecessary when holding the write lock. */
+write_retry:
+	/* reset mas->index and mas->last in case range of entry changed */
+	mas->index = mas->last = index;
 	entry = mas_state_walk(mas);
 	if (!entry)
 		return NULL;
 
-write_retry:
 	/* Must reset to ensure spanning writes of last slot are detected */
 	mas_reset(mas);
 	mas_wr_store_setup(&wr_mas);
-- 
2.46.0

Re: [PATCH 2/2] maple_tree: reset mas->index and mas->last on write retries

[Liam R. Howlett]

* Sidhartha Kumar <sidhartha.kumar@oracle.com> [240808 12:30]:
> The following scenario can result in a race condition:
> 
> Consider a node with the following indices and values
> 
> 	a<------->b<----------->c<--------->d
> 	    0xA        NULL          0xB
> 
> 	CPU 1			  CPU 2
>       ---------        		---------
> 	mas_set_range(a,b)
> 	mas_erase()
> 		-> range is expanded (a,c) because of null expansion
> 
> 	mas_nomem()
> 	mas_unlock()
> 				mas_store_range(b,c,0xC)
> 
> The node now looks like:
> 
> 	a<------->b<----------->c<--------->d
> 	    0xA        0xC          0xB
> 
> 	mas_lock()
> 	mas_erase() <------ range of erase is still (a,c)
> 
> The node is now NULL from (a,c) but the write from CPU 2 should have been
> retained and range (b,c) should still have 0xC as its value. We can fix
> this by re-intializing to the original index and last. This does not need
> a cc: Stable as there are no users of the maple tree which use internal
> locking and this condition is only possible with internal locking.
> 
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
>  lib/maple_tree.c | 15 ++++++++++++---
>  1 file changed, 12 insertions(+), 3 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 65fba37ef999..6ba95a278326 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5451,14 +5451,21 @@ EXPORT_SYMBOL_GPL(mas_store);
>   */
>  int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp)
>  {
> +	unsigned long index = mas->index;
> +	unsigned long last = mas->last;
>  	MA_WR_STATE(wr_mas, mas, entry);
>  
>  	mas_wr_store_setup(&wr_mas);
>  	trace_ma_write(__func__, mas, 0, entry);
>  retry:
>  	mas_wr_store_entry(&wr_mas);
> -	if (unlikely(mas_nomem(mas, gfp)))
> +	if (unlikely(mas_nomem(mas, gfp))) {
> +		if (!entry) {
> +			mas->index = index;
> +			mas->last = last;

__mas_set_range(mas, index, last);

> +		}
>  		goto retry;
> +	}
>  
>  	if (unlikely(mas_is_err(mas)))
>  		return xa_err(mas->node);
> @@ -6245,17 +6252,19 @@ EXPORT_SYMBOL_GPL(mas_find_range_rev);
>  void *mas_erase(struct ma_state *mas)
>  {
>  	void *entry;
> +	unsigned long index = mas->index;
>  	MA_WR_STATE(wr_mas, mas, NULL);
>  
>  	if (!mas_is_active(mas) || !mas_is_start(mas))
>  		mas->status = ma_start;
>  
> -	/* Retry unnecessary when holding the write lock. */
> +write_retry:
> +	/* reset mas->index and mas->last in case range of entry changed */
> +	mas->index = mas->last = index;

it might make sense to re-init in the mas_nomem() case only, to avoid
extra instructions in the fast path.

>  	entry = mas_state_walk(mas);
>  	if (!entry)
>  		return NULL;
>  
> -write_retry:
>  	/* Must reset to ensure spanning writes of last slot are detected */
>  	mas_reset(mas);
>  	mas_wr_store_setup(&wr_mas);
> -- 
> 2.46.0
> 

Re: [PATCH 1/2] maple_tree: add test to replicate low memory race conditions

[Liam R. Howlett]

* Sidhartha Kumar <sidhartha.kumar@oracle.com> [240808 12:30]:
> Add new callback fields to the userspace implementation of struct
> kmem_cache. This allows for executing callback functions in order to
> further test low memory scenarios where node allocation is retried.
> 
> This callback can help test race conditions by calling a function when a
> low memory event is tested". This exposes a race condition that is
                            ^- please remove that quote

> addressed in a subsequent patch.

Please reverse the patch order so that the test cases pass for all
commit ids.  It's good to have the test prove that the problem exists
and then fix it, but if bots verify the test cases, then they will see
it as failing on this commit.

> 
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
>  lib/maple_tree.c                 | 12 +++++++
>  tools/testing/radix-tree/maple.c | 60 ++++++++++++++++++++++++++++++++
>  tools/testing/shared/linux.c     | 26 +++++++++++++-
>  3 files changed, 97 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index aa3a5df15b8e..65fba37ef999 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -6997,6 +6997,18 @@ void mt_set_non_kernel(unsigned int val)
>  	kmem_cache_set_non_kernel(maple_node_cache, val);
>  }
>  
> +extern void kmem_cache_set_callback(struct kmem_cache *cachep, void (*callback)(void *));
> +void mt_set_callback(void (*callback)(void *))
> +{
> +	kmem_cache_set_callback(maple_node_cache, callback);
> +}
> +
> +extern void kmem_cache_set_private(struct kmem_cache *cachep, void *private);
> +void mt_set_private(void *private)
> +{
> +	kmem_cache_set_private(maple_node_cache, private);
> +}
> +
>  extern unsigned long kmem_cache_get_alloc(struct kmem_cache *);
>  unsigned long mt_get_alloc_size(void)
>  {
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index cd1cf05503b4..0e699feb71b8 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -36224,6 +36224,61 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt)
>  
>  extern void test_kmem_cache_bulk(void);
>  
> +static void writer2(void *maple_tree)
> +{
> +	struct maple_tree *mt = (struct maple_tree *)maple_tree;
> +	MA_STATE(mas, mt, 0, 0);
> +
> +	mtree_lock(mas.tree);
> +	__mas_set_range(&mas, 6, 10);
> +	mas_store(&mas, xa_mk_value(0xC));
> +	mas_destroy(&mas);
> +	mtree_unlock(mas.tree);

This can be simplified by setting the MA_STATE to 6, 10 to begin with,
and I don't think the destroy is necessary?

> +}
> +
> +static void check_data_race(struct maple_tree *mt)

Which data race?  check_nomem_writer_race() maybe?  It might be worth a
block comment about what's going on here?

> +{
> +	MA_STATE(mas, mt, 0, 0);
> +
> +	mt_set_non_kernel(0);
> +	/* setup root with 2 values with NULL in between */
> +	mtree_store_range(mt, 0, 5, xa_mk_value(0xA), GFP_KERNEL);
> +	mtree_store_range(mt, 6, 10, NULL, GFP_KERNEL);
> +	mtree_store_range(mt, 11, 15, xa_mk_value(0xB), GFP_KERNEL);
> +
> +	/* setup writer 2 that will trigger the race condition */
> +	mt_set_private(mt);
> +	mt_set_callback(writer2);
> +
> +	mtree_lock(mt);
> +	/* erase 0-5 */
> +	mas_reset(&mas);

reset isn't needed as this is the first use

> +	mas.index = 0;
> +	mas.last = 5;

These values can be passed to the init MA_STATE() too.

> +	mas_erase(&mas);
> +
> +	/* index 6-10 should retain the value from writer 2*/
> +	check_load(mt, 6, xa_mk_value(0xC));
> +	mtree_unlock(mt);
> +
> +	/* test for the same race but with mas_store_gfp */
> +	mtree_store_range(mt, 0, 5, xa_mk_value(0xA), GFP_KERNEL);
> +	mtree_store_range(mt, 6, 10, NULL, GFP_KERNEL);
> +
> +	mtree_lock(mt);
> +	mas_reset(&mas);
> +	mas.index = 0;
> +	mas.last = 5;

mas_set_range() will do these three things, maybe do it outside the
lock?

> +	mas_store_gfp(&mas, NULL, GFP_KERNEL);
> +
> +	check_load(mt, 6, xa_mk_value(0xC));
> +
> +	mt_set_private(NULL);
> +	mt_set_callback(NULL);
> +	mas_destroy(&mas);

is this destroy needed?

> +	mtree_unlock(mt);
> +}
> +
>  void farmer_tests(void)
>  {
>  	struct maple_node *node;
> @@ -36243,6 +36298,11 @@ void farmer_tests(void)
>  	node->mr64.pivot[2] = 0;
>  	tree.ma_root = mt_mk_node(node, maple_leaf_64);
>  	mt_dump(&tree, mt_dump_dec);
> +	mtree_destroy(&tree);
> +
> +	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_USE_RCU);
> +	check_data_race(&tree);
> +	mtree_destroy(&tree);


The lack of mtree_destroy() before this test makes me think that you
should move your test lower in the sequence - maybe the previous code
was still using that tree?

>  
>  	node->parent = ma_parent_ptr(node);
>  	ma_free_rcu(node);
> diff --git a/tools/testing/shared/linux.c b/tools/testing/shared/linux.c
> index 4eb442206d01..17263696b5d8 100644
> --- a/tools/testing/shared/linux.c
> +++ b/tools/testing/shared/linux.c
> @@ -26,8 +26,21 @@ struct kmem_cache {
>  	unsigned int non_kernel;
>  	unsigned long nr_allocated;
>  	unsigned long nr_tallocated;
> +	bool exec_callback;
> +	void (*callback)(void *);
> +	void *private;
>  };
>  
> +void kmem_cache_set_callback(struct kmem_cache *cachep, void (*callback)(void *))
> +{
> +	cachep->callback = callback;
> +}
> +
> +void kmem_cache_set_private(struct kmem_cache *cachep, void *private)
> +{
> +	cachep->private = private;
> +}
> +
>  void kmem_cache_set_non_kernel(struct kmem_cache *cachep, unsigned int val)
>  {
>  	cachep->non_kernel = val;
> @@ -58,9 +71,17 @@ void *kmem_cache_alloc_lru(struct kmem_cache *cachep, struct list_lru *lru,
>  {
>  	void *p;
>  
> +	if (cachep->exec_callback) {
> +		if (cachep->callback)
> +			cachep->callback(cachep->private);
> +		cachep->exec_callback = false;
> +	}
> +
>  	if (!(gfp & __GFP_DIRECT_RECLAIM)) {
> -		if (!cachep->non_kernel)
> +		if (!cachep->non_kernel) {
> +			cachep->exec_callback = true;
>  			return NULL;
> +		}
>  
>  		cachep->non_kernel--;
>  	}
> @@ -223,6 +244,9 @@ kmem_cache_create(const char *name, unsigned int size, unsigned int align,
>  	ret->objs = NULL;
>  	ret->ctor = ctor;
>  	ret->non_kernel = 0;
> +	ret->exec_callback = false;
> +	ret->callback = NULL;
> +	ret->private = NULL;
>  	return ret;
>  }
>  
> -- 
> 2.46.0

Re: [PATCH 1/2] maple_tree: add test to replicate low memory race conditions

[Matthew Wilcox]

On Thu, Aug 08, 2024 at 12:29:59PM -0400, Sidhartha Kumar wrote:
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index aa3a5df15b8e..65fba37ef999 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -6997,6 +6997,18 @@ void mt_set_non_kernel(unsigned int val)
>  	kmem_cache_set_non_kernel(maple_node_cache, val);
>  }
>  
> +extern void kmem_cache_set_callback(struct kmem_cache *cachep, void (*callback)(void *));
> +void mt_set_callback(void (*callback)(void *))
> +{
> +	kmem_cache_set_callback(maple_node_cache, callback);
> +}
> +
> +extern void kmem_cache_set_private(struct kmem_cache *cachep, void *private);
> +void mt_set_private(void *private)
> +{
> +	kmem_cache_set_private(maple_node_cache, private);
> +}
> +
>  extern unsigned long kmem_cache_get_alloc(struct kmem_cache *);
>  unsigned long mt_get_alloc_size(void)
>  {

This should surely not be in lib/maple_tree.c ...

Re: [PATCH 1/2] maple_tree: add test to replicate low memory race conditions

[Liam R. Howlett]

* Matthew Wilcox <willy@infradead.org> [240808 15:15]:
> On Thu, Aug 08, 2024 at 12:29:59PM -0400, Sidhartha Kumar wrote:
> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > index aa3a5df15b8e..65fba37ef999 100644
> > --- a/lib/maple_tree.c
> > +++ b/lib/maple_tree.c
> > @@ -6997,6 +6997,18 @@ void mt_set_non_kernel(unsigned int val)
> >  	kmem_cache_set_non_kernel(maple_node_cache, val);
> >  }
> >  
> > +extern void kmem_cache_set_callback(struct kmem_cache *cachep, void (*callback)(void *));
> > +void mt_set_callback(void (*callback)(void *))
> > +{
> > +	kmem_cache_set_callback(maple_node_cache, callback);
> > +}
> > +
> > +extern void kmem_cache_set_private(struct kmem_cache *cachep, void *private);
> > +void mt_set_private(void *private)
> > +{
> > +	kmem_cache_set_private(maple_node_cache, private);
> > +}
> > +
> >  extern unsigned long kmem_cache_get_alloc(struct kmem_cache *);
> >  unsigned long mt_get_alloc_size(void)
> >  {
> 
> This should surely not be in lib/maple_tree.c ...
> 

It has to be as it uses the kmem_cache maple_node_cache reference.

It is located in an ifndef __KERNEL__ and an ifdef
CONFIG_DEBUG_MAPLE_TREE, so it won't be in any kernel builds.