From 8562014a57b92fb53566b5c4d77eaeebce532482 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 27 Aug 2020 16:36:39 -0400 Subject: [PATCH] maple_tree: Fix range calc on slot 0 and clean up empty_alloc. add rev_seq test Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 28 ++++++++------------------ lib/test_maple_tree.c | 47 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 55 insertions(+), 20 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index eeb508867233..a2e9918f13e4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -13,7 +13,6 @@ #include #include #include -//#include // for task_size #define CREATE_TRACE_POINTS #include @@ -990,28 +989,16 @@ list_failed: } // Free the allocations. -static inline void ma_free_rcu_alloc(struct maple_node *node) +static inline void mas_empty_alloc(struct ma_state *mas) { - int alloc = 0; + struct maple_node *node; - while (alloc < MAPLE_NODE_SLOTS && node->slot[alloc]) { - if (ma_mnode_ptr(node->slot[alloc])->slot[0]) - ma_free_rcu_alloc(node->slot[alloc]); - else - kfree(node->slot[alloc]); - alloc++; + while (mas_get_alloc(mas)) { + node = mas_next_alloc(mas); + kmem_cache_free(maple_node_cache, node); } - kfree(node); } -void mas_empty_alloc(struct ma_state *mas) -{ - struct maple_node *node = mas_get_alloc(mas); - - if (node) - ma_free_rcu_alloc(node); - mas->alloc = NULL; -} /* * Check if there was an error allocating and do the allocation if necessary * If there are allocations, then free them. @@ -1675,7 +1662,8 @@ static inline unsigned char mas_store_b_node(struct ma_state *mas, unsigned char end = mas_data_end(mas); void *contents = mas_get_rcu_slot(mas, slot); unsigned char b_end = 0; - unsigned long piv = mas->min; + // Possible underflow of piv will wrap back to 0 before use. + unsigned long piv = mas->min - 1; if (slot) { mas_mab_cp(mas, 0, slot - 1, b_node, 0); @@ -1683,7 +1671,7 @@ static inline unsigned char mas_store_b_node(struct ma_state *mas, piv = b_node->pivot[b_end - 1]; } - if (mas->index && piv < mas->index - 1) { + if (piv + 1 < mas->index) { b_node->slot[b_end] = contents; if (!contents) b_node->gap[b_end] = mas->index - 1 - piv; diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index e88481c8f560..2dedc13a008d 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -231,6 +231,8 @@ static noinline void check_new_node(struct maple_tree *mt) MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != 0); ma_free_rcu(mn); + mas.node = MAS_START; + mas_nomem(&mas, GFP_KERNEL); // Allocate 3 nodes, will fail. mas_node_cnt(&mas, 3); // Drop the lock and allocate 3 nodes. @@ -311,6 +313,34 @@ static noinline void check_new_node(struct maple_tree *mt) mtree_unlock(mt); mtree_destroy(mt); } + +static noinline void check_rev_seq(struct maple_tree *mt, unsigned long max, + bool verbose) +{ + unsigned long i = max, j; + + MT_BUG_ON(mt, !mtree_empty(mt)); + + nr_tallocated = 0; + while (i) { + MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL)); + for (j = i; j <= max; j++) + check_index_load(mt, j); + + check_load(mt, i - 1, NULL); + i--; + } + check_load(mt, max + 1, NULL); + + if (verbose) { + rcu_barrier(); + mt_dump(mt); + pr_info(" %s test of 0-%lu %luK in %d active (%d total)\n", + __func__, max, mt_get_alloc_size()/1024, nr_allocated, + nr_tallocated); + } +} + static noinline void check_seq(struct maple_tree *mt, unsigned long max, bool verbose) { @@ -32150,6 +32180,21 @@ static int maple_tree_seed(void) check_new_node(&tree); mtree_destroy(&tree); + mtree_init(&tree, MAPLE_ALLOC_RANGE); + check_rev_seq(&tree, 10, true); + mtree_destroy(&tree); + mtree_init(&tree, 0); + check_seq(&tree, 10, true); + mtree_destroy(&tree); + + mtree_init(&tree, 0); + check_dfs_preorder(&tree); + mtree_destroy(&tree); + + mtree_init(&tree, 0); + check_dup_tree(&tree); + mtree_destroy(&tree); + mtree_init(&tree, 0); check_dfs_preorder(&tree); mtree_destroy(&tree); @@ -32283,8 +32328,10 @@ static int maple_tree_seed(void) mtree_destroy(&tree); check_nomem(&tree); + mtree_init(&tree, 0); check_seq(&tree, 16, false); mtree_destroy(&tree); + mtree_init(&tree, 0); check_seq(&tree, 1000, true); mtree_destroy(&tree); -- 2.50.1