maple_tree: add test to replicate low memory race conditions
Subsystems (4)
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
@@ -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
@@ -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
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
@@ -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
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
0xCas 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 <[email protected]>--- lib/maple_tree.c | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-)lib/maple_tree.c +2
-0@@ -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
-1mas_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
-1entry =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
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
Signed-off-by Sidhartha Kumar <[email protected]>--- 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@@ -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@@ -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
-0node->parent =ma_parent_ptr (node);ma_free_rcu (node);tools/testing/shared/linux.c +25
-1@@ -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
Matthew Wilcox
maintainerQuoted 13 lines · Sidhartha Kumar
lib/maple_tree.c +5
-0@@ -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 ...
Quoted 18 lines · Matthew Wilcox
Quoted 17 lines · Sidhartha Kumar
lib/maple_tree.c +9
-0@@ -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.