From edc1398169ee77d058886c5733b8a9e015932480 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 26 Aug 2020 10:34:48 -0400 Subject: [PATCH] maple_tree: Fix direct destroy Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 164 +++++++++++++++++++++++------------------- lib/test_maple_tree.c | 28 ++++---- 2 files changed, 106 insertions(+), 86 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6fd5aca425350..228e1753c4180 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -629,6 +629,68 @@ static inline struct maple_enode *mas_get_rcu_slot(const struct ma_state *mas, { return mte_get_rcu_slot(mas->node, slot, mas->tree); } + +/* + * ma_set_rcu_slot() - Set a nodes rcu slot. + * + * @mn - the maple node for the operation + * @slot - the slot number to set + * @type - the maple node type + * @val - the value to store + */ +static inline void ma_set_rcu_slot(struct maple_node *mn, + unsigned char slot, enum maple_type type, void *val) +{ + BUG_ON(slot >= mt_slots[type]); + + switch (type) { + default: + case maple_dense: + rcu_assign_pointer(mn->slot[slot], val); + break; + case maple_sparse_6: + rcu_assign_pointer(mn->ms6.slot[slot], val); + break; + case maple_sparse_9: + rcu_assign_pointer(mn->ms9.slot[slot], val); + break; + case maple_sparse_16: + rcu_assign_pointer(mn->ms16.slot[slot], val); + break; + case maple_sparse_21: + rcu_assign_pointer(mn->ms21.slot[slot], val); + break; + case maple_sparse_32: + rcu_assign_pointer(mn->ms32.slot[slot], val); + break; + case maple_sparse_64: + rcu_assign_pointer(mn->ms64.slot[slot], val); + break; + case maple_range_16: + case maple_leaf_16: + rcu_assign_pointer(mn->mr16.slot[slot], val); + break; + case maple_range_32: + case maple_leaf_32: + rcu_assign_pointer(mn->mr32.slot[slot], val); + break; + case maple_range_64: + case maple_leaf_64: + rcu_assign_pointer(mn->mr64.slot[slot], val); + break; + case maple_arange_64: + rcu_assign_pointer(mn->ma64.slot[slot], val); + break; + } +} +/* + * mte_set_rcu_slot() - Set an encoded nodes rcu slot. + */ +static inline void mte_set_rcu_slot(const struct maple_enode *mn, + unsigned char slot, void *val) +{ + ma_set_rcu_slot(mte_to_node(mn), slot, mte_node_type(mn), val); +} /* * mte_destroy_walk() - Free the sub-tree from @mn and below. * @@ -638,36 +700,54 @@ static inline struct maple_enode *mas_get_rcu_slot(const struct ma_state *mas, void _mte_destroy_walk(struct maple_enode *mn, struct maple_tree *mtree, bool rcu) { - struct maple_enode *child, *end_child; + struct maple_enode *end_child; unsigned char slot_cnt = mt_slot_count(mn); int end; if (mte_is_leaf(mn)) return; - child = mte_get_rcu_slot(mn, 0, mtree); for (end = 0; end < slot_cnt; end++) { end_child = mte_get_rcu_slot(mn, end, mtree); - if (!end_child) { - end--; + if (!end_child) break; - } if (!mte_is_leaf(end_child)) _mte_destroy_walk(end_child, mtree, rcu); if (rcu) ma_free_rcu(mte_to_node(end_child)); + else + mte_set_rcu_slot(mn, end, mte_to_node(end_child)); + } + if (!rcu) { + void **slot_array; + struct maple_node *node = mte_to_node(mn); + + switch (mte_node_type(mn)) { + default: + case maple_arange_64: + slot_array = node->ma64.slot; + break; + case maple_range_64: + slot_array = node->mr64.slot; + break; + case maple_range_32: + slot_array = node->mr32.slot; + break; + case maple_range_16: + slot_array = node->mr16.slot; + break; + } + kmem_cache_free_bulk(maple_node_cache, end, slot_array); } - if (!rcu) - kmem_cache_free_bulk(maple_node_cache, end + 1, - (void **)(&child)); } void mte_destroy_walk(struct maple_enode *mn, struct maple_tree *mtree, bool rcu) { + struct maple_node *node = mte_to_node(mn); _mte_destroy_walk(mn, mtree, rcu); - rcu ? ma_free_rcu(mte_to_node(mn)) : kmem_cache_free(maple_node_cache, mn); + rcu ? ma_free_rcu(node) : kmem_cache_free(maple_node_cache, node); } /* * mat_add() - Add a @dead_enode to the ma_topiary of a list of dead nodes. @@ -712,68 +792,6 @@ static inline void mat_free(struct ma_topiary *mat, bool recursive) mat->head = next; } } - -/* - * ma_set_rcu_slot() - Set a nodes rcu slot. - * - * @mn - the maple node for the operation - * @slot - the slot number to set - * @type - the maple node type - * @val - the value to store - */ -static inline void ma_set_rcu_slot(struct maple_node *mn, - unsigned char slot, enum maple_type type, void *val) -{ - BUG_ON(slot >= mt_slots[type]); - - switch (type) { - default: - case maple_dense: - rcu_assign_pointer(mn->slot[slot], val); - break; - case maple_sparse_6: - rcu_assign_pointer(mn->ms6.slot[slot], val); - break; - case maple_sparse_9: - rcu_assign_pointer(mn->ms9.slot[slot], val); - break; - case maple_sparse_16: - rcu_assign_pointer(mn->ms16.slot[slot], val); - break; - case maple_sparse_21: - rcu_assign_pointer(mn->ms21.slot[slot], val); - break; - case maple_sparse_32: - rcu_assign_pointer(mn->ms32.slot[slot], val); - break; - case maple_sparse_64: - rcu_assign_pointer(mn->ms64.slot[slot], val); - break; - case maple_range_16: - case maple_leaf_16: - rcu_assign_pointer(mn->mr16.slot[slot], val); - break; - case maple_range_32: - case maple_leaf_32: - rcu_assign_pointer(mn->mr32.slot[slot], val); - break; - case maple_range_64: - case maple_leaf_64: - rcu_assign_pointer(mn->mr64.slot[slot], val); - break; - case maple_arange_64: - rcu_assign_pointer(mn->ma64.slot[slot], val); - break; - } -} -/* - * mte_set_rcu_slot() - Set an encoded nodes rcu slot. - */ -static inline void mte_set_rcu_slot(const struct maple_enode *mn, - unsigned char slot, void *val) -{ - ma_set_rcu_slot(mte_to_node(mn), slot, mte_node_type(mn), val); -} /* * mas_dup_state() - duplicate the internal state of a ma_state. * @@ -4702,10 +4720,10 @@ void mtree_direct_destroy(struct maple_tree *mt) mt->ma_flags = 0; mt->ma_height = 0; - rcu_assign_pointer(mt->ma_root, NULL); + mt->ma_root = NULL; mtree_unlock(mt); } -/* mtree_direct_destroy is unsafe to export for readers. */ +/* mtree_direct_destroy is unsafe to export as it is not rcu safe. */ void mtree_destroy(struct maple_tree *mt) { diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index dad1655cd00c7..1dcdc4e7864c3 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -32107,19 +32107,21 @@ static void check_dup_tree(struct maple_tree *oldmt) mtree_destroy(oldmt); - max = 254; - mas_reset(&mas); - mas_reset(&oldmas); - mtree_init(oldmt, 0); - mtree_init(&mt, 0); - check_seq(oldmt, max, false); - mas_dup_tree(&oldmas, &mas); - for (i = 0; i <= max; i++) - check_index_load(&mt, i); - - check_load(&mt, max + 1, NULL); - mtree_destroy(&mt); - mtree_destroy(oldmt); + for (max = 257; max > 0; max--) { + mas_reset(&mas); + mas_reset(&oldmas); + mtree_init(oldmt, 0); + mtree_init(&mt, 0); + check_seq(oldmt, max, false); + mas_dup_tree(&oldmas, &mas); + for (i = 0; i <= max; i++) + check_index_load(&mt, i); + + check_load(&mt, max + 1, NULL); + mt_dump(&mt); + mtree_direct_destroy(&mt); + mtree_destroy(oldmt); + } max = 5000; // for depth of 3 on 256 nodes. mas_reset(&mas); -- 2.50.1