diff mbox series

[v5,5/5] maple_tree: add a test checking storing null

Message ID 20241031231627.14316-6-richard.weiyang@gmail.com (mailing list archive)
State New
Headers show
Series refine storing null | expand

Commit Message

Wei Yang Oct. 31, 2024, 11:16 p.m. UTC 
Add a test to assert that, when storing null to am empty tree or a
single entry tree it will not result into:

  * a root node with range [0, ULONG_MAX] set to NULL
  * a root node with consecutive slot set to NULL

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
CC: Sidhartha Kumar <sidhartha.kumar@oracle.com>
CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

---
v3: move test into lib/test_maple_tree.c
v5: fix a build warning on xa_is_node()
---
 lib/test_maple_tree.c | 90 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 90 insertions(+)

Comments

Andrew Morton Nov. 1, 2024, 3:37 a.m. UTC | #1 
On Thu, 31 Oct 2024 23:16:27 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:

> Add a test to assert that, when storing null to am empty tree or a
> single entry tree it will not result into:
> 
>   * a root node with range [0, ULONG_MAX] set to NULL
>   * a root node with consecutive slot set to NULL
> 

I don't get it.

> --- a/lib/test_maple_tree.c
> +++ b/lib/test_maple_tree.c
> @@ -1387,6 +1387,92 @@ static noinline void __init check_prev_entry(struct maple_tree *mt)
>  	mas_unlock(&mas);
>  }
>  
> +static noinline void __init check_store_null(struct maple_tree *mt)
> +{
> +	MA_STATE(mas, mt, 0, ULONG_MAX);
> +
>
> ...
>
> +	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
> ...
>

mas_root() is private to lib/maple_tree.c.  I'll do this for now:

--- a/lib/test_maple_tree.c~maple_tree-add-a-test-checking-storing-null-fix
+++ a/lib/test_maple_tree.c
@@ -1453,7 +1453,7 @@ static noinline void __init check_store_
 	mas_set_range(&mas, 2, 5);
 	mas_store_gfp(&mas, NULL, GFP_KERNEL);
 	MT_BUG_ON(mt, mtree_empty(mt));
-	MT_BUG_ON(mt, xa_is_node(mas_root(&mas)));
+//	MT_BUG_ON(mt, xa_is_node(mas_root(&mas)));
 	mas_unlock(&mas);
 	mtree_destroy(mt);
 
@@ -1465,7 +1465,7 @@ static noinline void __init check_store_
 	mas_lock(&mas);
 	mas_set_range(&mas, 1, 3);
 	mas_store_gfp(&mas, &mas, GFP_KERNEL);
-	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
+//	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
 	mas_set_range(&mas, 0, ULONG_MAX);
 	mas_store_gfp(&mas, NULL, GFP_KERNEL);
 	MT_BUG_ON(mt, !mtree_empty(mt));
Wei Yang Nov. 3, 2024, 10:46 p.m. UTC | #2 
On Thu, Oct 31, 2024 at 08:37:57PM -0700, Andrew Morton wrote:
>On Thu, 31 Oct 2024 23:16:27 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:
>
>> Add a test to assert that, when storing null to am empty tree or a
>> single entry tree it will not result into:
>> 
>>   * a root node with range [0, ULONG_MAX] set to NULL
>>   * a root node with consecutive slot set to NULL
>> 
>
>I don't get it.
>

For example, if we store NULL to [3, 10] currently, we will have a root node
like this.

maple_tree(0x7fff2b797170) flags 5, height 1 root 0x615000000d0e
0-18446744073709551615: node 0x615000000d00 depth 0 type 1 parent 0x7fff2b797171 contents: (nil) 2 (nil) 10 (nil) 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0x2
  0-2: (nil)
  3-10: (nil)
  11-18446744073709551615: (nil)

Slot 0, 1 is consecutively set to NULL. This is not expected.

>> --- a/lib/test_maple_tree.c
>> +++ b/lib/test_maple_tree.c
>> @@ -1387,6 +1387,92 @@ static noinline void __init check_prev_entry(struct maple_tree *mt)
>>  	mas_unlock(&mas);
>>  }
>>  
>> +static noinline void __init check_store_null(struct maple_tree *mt)
>> +{
>> +	MA_STATE(mas, mt, 0, ULONG_MAX);
>> +
>>
>> ...
>>
>> +	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
>> ...
>>
>
>mas_root() is private to lib/maple_tree.c.  I'll do this for now:

Oh, thanks.

>
>--- a/lib/test_maple_tree.c~maple_tree-add-a-test-checking-storing-null-fix
>+++ a/lib/test_maple_tree.c
>@@ -1453,7 +1453,7 @@ static noinline void __init check_store_
> 	mas_set_range(&mas, 2, 5);
> 	mas_store_gfp(&mas, NULL, GFP_KERNEL);
> 	MT_BUG_ON(mt, mtree_empty(mt));
>-	MT_BUG_ON(mt, xa_is_node(mas_root(&mas)));
>+//	MT_BUG_ON(mt, xa_is_node(mas_root(&mas)));
> 	mas_unlock(&mas);
> 	mtree_destroy(mt);
> 
>@@ -1465,7 +1465,7 @@ static noinline void __init check_store_
> 	mas_lock(&mas);
> 	mas_set_range(&mas, 1, 3);
> 	mas_store_gfp(&mas, &mas, GFP_KERNEL);
>-	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
>+//	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
> 	mas_set_range(&mas, 0, ULONG_MAX);
> 	mas_store_gfp(&mas, NULL, GFP_KERNEL);
> 	MT_BUG_ON(mt, !mtree_empty(mt));
>_
diff mbox series

Patch

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 31561e0e1a0d..6f76093170bb 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -1387,6 +1387,92 @@  static noinline void __init check_prev_entry(struct maple_tree *mt)
 	mas_unlock(&mas);
 }
 
+static noinline void __init check_store_null(struct maple_tree *mt)
+{
+	MA_STATE(mas, mt, 0, ULONG_MAX);
+
+	/*
+	 * Store NULL at range [0, ULONG_MAX] to an empty tree should result
+	 * in an empty tree
+	 */
+	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+	mas_lock(&mas);
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	MT_BUG_ON(mt, !mtree_empty(mt));
+	mas_unlock(&mas);
+	mtree_destroy(mt);
+
+	/*
+	 * Store NULL at any range to an empty tree should result in an empty
+	 * tree
+	 */
+	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+	mas_lock(&mas);
+	mas_set_range(&mas, 3, 10);
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	MT_BUG_ON(mt, !mtree_empty(mt));
+	mas_unlock(&mas);
+	mtree_destroy(mt);
+
+	/*
+	 * Store NULL at range [0, ULONG_MAX] to a single entry tree should
+	 * result in an empty tree
+	 */
+	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+	mas_lock(&mas);
+	mas_set(&mas, 0);
+	mas_store_gfp(&mas, &mas, GFP_KERNEL);
+	mas_set_range(&mas, 0, ULONG_MAX);
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	MT_BUG_ON(mt, !mtree_empty(mt));
+	mas_unlock(&mas);
+	mtree_destroy(mt);
+
+	/*
+	 * Store NULL at range [0, n] to a single entry tree should
+	 * result in an empty tree
+	 */
+	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+	mas_lock(&mas);
+	mas_set(&mas, 0);
+	mas_store_gfp(&mas, &mas, GFP_KERNEL);
+	mas_set_range(&mas, 0, 5);
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	MT_BUG_ON(mt, !mtree_empty(mt));
+	mas_unlock(&mas);
+	mtree_destroy(mt);
+
+	/*
+	 * Store NULL at range [m, n] where m > 0 to a single entry tree
+	 * should still be a single entry tree
+	 */
+	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+	mas_lock(&mas);
+	mas_set(&mas, 0);
+	mas_store_gfp(&mas, &mas, GFP_KERNEL);
+	mas_set_range(&mas, 2, 5);
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	MT_BUG_ON(mt, mtree_empty(mt));
+	MT_BUG_ON(mt, xa_is_node(mas_root(&mas)));
+	mas_unlock(&mas);
+	mtree_destroy(mt);
+
+	/*
+	 * Store NULL at range [0, ULONG_MAX] to a tree with node should
+	 * result in an empty tree
+	 */
+	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+	mas_lock(&mas);
+	mas_set_range(&mas, 1, 3);
+	mas_store_gfp(&mas, &mas, GFP_KERNEL);
+	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
+	mas_set_range(&mas, 0, ULONG_MAX);
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	MT_BUG_ON(mt, !mtree_empty(mt));
+	mas_unlock(&mas);
+	mtree_destroy(mt);
+}
+
 static noinline void __init check_root_expand(struct maple_tree *mt)
 {
 	MA_STATE(mas, mt, 0, 0);
@@ -3710,6 +3796,10 @@  static int __init maple_tree_seed(void)
 	goto skip;
 #endif
 
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+	check_store_null(&tree);
+	mtree_destroy(&tree);
+
 	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
 	check_root_expand(&tree);
 	mtree_destroy(&tree);