Skip to contentSkip to conversation

maple_tree: add test to replicate low memory race conditions

PATCH In review Sidhartha Kumar 3 participants 6 messages Aug 8, 2024

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

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

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.

---
 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(-)
lib/maple_tree.c +12 -0
index aa3a5df15b8e..65fba37ef999 100644
@@ -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)
 {
tools/testing/radix-tree/maple.c +60 -0

72 lines not on this page · raw message

tools/testing/shared/linux.c +25 -1
index 4eb442206d01..17263696b5d8 100644
@@ -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;
 }
 
Signature · 1 line
2.46.0
#1 lore raw

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

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.

---
 lib/maple_tree.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)
lib/maple_tree.c +12 -3
index 65fba37ef999..6ba95a278326 100644
@@ -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);
Signature · 1 line
2.46.0
#2 lore raw

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

Quoted 47 lines · 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.

---
 lib/maple_tree.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)
lib/maple_tree.c +2 -0
index 65fba37ef999..6ba95a278326 100644
@@ -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);

lib/maple_tree.c EXPORT_SYMBOL_GPL(mas_store); · line 5465

Quoted 10 lines
lib/maple_tree.c +4 -1
 
 	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);

Quoted 10 lines
lib/maple_tree.c +2 -0
+		}
 		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;

lib/maple_tree.c EXPORT_SYMBOL_GPL(mas_find_range_rev); · line 6263

Quoted 10 lines
lib/maple_tree.c +4 -1
+	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.

Quoted 11 lines
lib/maple_tree.c +0 -1
 	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);
Signature · 1 line
2.46.0
#3 lore raw
In reply to Sidhartha Kumar
Quoted 6 lines · 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

^- please remove that quote

Quoted 1 line

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.

Quoted 39 lines
---
 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(-)
lib/maple_tree.c +12 -0
index aa3a5df15b8e..65fba37ef999 100644
@@ -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)
 {
tools/testing/radix-tree/maple.c +0 -0
index cd1cf05503b4..0e699feb71b8 100644
@@ -36224,6 +36224,61 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt)
 
 extern void test_kmem_cache_bulk(void);
 

tools/testing/radix-tree/maple.c static noinline void __init check_mtree_dup(struct maple_tree *mt) · line 36236

Quoted 10 lines
tools/testing/radix-tree/maple.c +10 -0
+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?

tools/testing/radix-tree/maple.c static noinline void __init check_mtree_dup(struct maple_tree *mt) · line 36239

Quoted 3 lines
tools/testing/radix-tree/maple.c +3 -0
+}
+
+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?

Quoted 6 lines
tools/testing/radix-tree/maple.c +6 -0
+{
+	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);

tools/testing/radix-tree/maple.c static noinline void __init check_mtree_dup(struct maple_tree *mt) · line 36255

Quoted 10 lines
tools/testing/radix-tree/maple.c +10 -0
+	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

tools/testing/radix-tree/maple.c static noinline void __init check_mtree_dup(struct maple_tree *mt) · line 36257

Quoted 2 lines
tools/testing/radix-tree/maple.c +2 -0
+	mas.index = 0;
+	mas.last = 5;

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

Quoted 4 lines
tools/testing/radix-tree/maple.c +4 -0
+	mas_erase(&mas);
+
+	/* index 6-10 should retain the value from writer 2*/
+	check_load(mt, 6, xa_mk_value(0xC));

tools/testing/radix-tree/maple.c static noinline void __init check_mtree_dup(struct maple_tree *mt) · line 36271

Quoted 10 lines
tools/testing/radix-tree/maple.c +10 -0
+	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?

tools/testing/radix-tree/maple.c static noinline void __init check_mtree_dup(struct maple_tree *mt) · line 36278

Quoted 7 lines
tools/testing/radix-tree/maple.c +7 -0
+	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?

Quoted 7 lines
tools/testing/radix-tree/maple.c +3 -0
+	mtree_unlock(mt);
+}
+
 void farmer_tests(void)
 {
 	struct maple_node *node;

tools/testing/radix-tree/maple.c void farmer_tests(void) · line 36305

Quoted 8 lines
tools/testing/radix-tree/maple.c +5 -0
@@ -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?

Quoted 60 lines
tools/testing/radix-tree/maple.c +0 -0
 	node->parent = ma_parent_ptr(node);
 	ma_free_rcu(node);
tools/testing/shared/linux.c +25 -1
index 4eb442206d01..17263696b5d8 100644
@@ -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;
 }
 
Signature · 1 line
2.46.0
maintainer
#4 lore raw
In reply to Sidhartha Kumar
Quoted 13 lines · Sidhartha Kumar
lib/maple_tree.c +5 -0
index aa3a5df15b8e..65fba37ef999 100644
@@ -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);
+}

lib/maple_tree.c void mt_set_non_kernel(unsigned int val) · line 7014

Quoted 10 lines
lib/maple_tree.c +7 -0
+
+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 ...

#5 lore raw
Quoted 18 lines · Matthew Wilcox
Quoted 17 lines · Sidhartha Kumar
lib/maple_tree.c +9 -0
index aa3a5df15b8e..65fba37ef999 100644
@@ -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)
+{
Quoted 9 lines

lib/maple_tree.c void mt_set_non_kernel(unsigned int val) · line 7014

Quoted 6 lines
lib/maple_tree.c +3 -0
+	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.