From c61b3a2b2d9bb36698f8c2f65aa41ba183815264 Mon Sep 17 00:00:00 2001 From: Liam Howlett Date: Wed, 26 Oct 2022 15:13:29 +0000 Subject: maple_tree: remove pointer to pointer use in mas_alloc_nodes() There is a more direct and cleaner way of implementing the same functional code. Remove the confusing and unnecessary use of pointers here. Link: https://lkml.kernel.org/r/20221026151241.4031117-1-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Suggested-by: Lukas Bulwahn Signed-off-by: Andrew Morton --- lib/maple_tree.c | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) (limited to 'lib/maple_tree.c') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index fbde494444b8..72e3b6a9c021 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1209,7 +1209,6 @@ done: static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) { struct maple_alloc *node; - struct maple_alloc **nodep = &mas->alloc; unsigned long allocated = mas_allocated(mas); unsigned long success = allocated; unsigned int requested = mas_alloc_req(mas); @@ -1263,8 +1262,7 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) node->node_count--; success += count; - nodep = &node->slot[0]; - node = *nodep; + node = node->slot[0]; requested -= count; } mas->alloc->total = success; -- cgit v1.2.3 From 9a887877ef981e5a185a84339603300cf2eb1900 Mon Sep 17 00:00:00 2001 From: Liam Howlett Date: Wed, 26 Oct 2022 15:14:31 +0000 Subject: maple_tree: mas_anode_descend() clang-analyzer cleanup clang-analyzer reported some Dead Stores in mas_anode_descend(). Upon inspection, there were a few clean ups that would make the code cleaner: The count variable was set from the mt_slots array and then updated but never used again. Just use the array reference directly. Also stop updating the type since it isn't used after the update. Stop setting the gaps pointer to NULL at the start since it is always set before the loop begins. Link: https://lkml.kernel.org/r/20221026151413.4032730-1-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Suggested-by: Lukas Bulwahn Signed-off-by: Andrew Morton --- lib/maple_tree.c | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) (limited to 'lib/maple_tree.c') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 72e3b6a9c021..4c7eef927f1a 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4968,8 +4968,9 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size) { enum maple_type type = mte_node_type(mas->node); unsigned long pivot, min, gap = 0; - unsigned char count, offset; - unsigned long *gaps = NULL, *pivots = ma_pivots(mas_mn(mas), type); + unsigned char offset; + unsigned long *gaps; + unsigned long *pivots = ma_pivots(mas_mn(mas), type); void __rcu **slots = ma_slots(mas_mn(mas), type); bool found = false; @@ -4980,9 +4981,8 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size) gaps = ma_gaps(mte_to_node(mas->node), type); offset = mas->offset; - count = mt_slots[type]; min = mas_safe_min(mas, pivots, offset); - for (; offset < count; offset++) { + for (; offset < mt_slots[type]; offset++) { pivot = mas_safe_pivot(mas, pivots, offset, type); if (offset && !pivot) break; @@ -5008,8 +5008,6 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size) mas->min = min; mas->max = pivot; offset = 0; - type = mte_node_type(mas->node); - count = mt_slots[type]; break; } } -- cgit v1.2.3 From 120b116208a0877227fc82e3f0df81e7a3ed4ab1 Mon Sep 17 00:00:00 2001 From: Liam Howlett Date: Fri, 28 Oct 2022 18:04:30 +0000 Subject: maple_tree: reorganize testing to restore module testing Along the development cycle, the testing code support for module/in-kernel compiles was removed. Restore this functionality by moving any internal API tests to the userspace side, as well as threading tests. Fix the lockdep issues and add a way to reduce memory usage so the tests can complete with KASAN + memleak detection. Make the tests work on 32 bit hosts where possible and detect 32 bit hosts in the radix test suite. [akpm@linux-foundation.org: fix module export] [akpm@linux-foundation.org: fix it some more] [liam.howlett@oracle.com: fix compile warnings on 32bit build in check_find()] Link: https://lkml.kernel.org/r/20221107203816.1260327-1-Liam.Howlett@oracle.com Link: https://lkml.kernel.org/r/20221028180415.3074673-1-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Signed-off-by: Andrew Morton --- lib/maple_tree.c | 38 ++++++++++++++++++++++++++++++++------ 1 file changed, 32 insertions(+), 6 deletions(-) (limited to 'lib/maple_tree.c') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 4c7eef927f1a..f23f11da4113 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -183,10 +183,6 @@ static void ma_free_rcu(struct maple_node *node) call_rcu(&node->rcu, mt_free_rcu); } -static unsigned int mt_height(const struct maple_tree *mt) -{ - return (mt->ma_flags & MT_FLAGS_HEIGHT_MASK) >> MT_FLAGS_HEIGHT_OFFSET; -} static void mas_set_height(struct ma_state *mas) { @@ -5061,6 +5057,7 @@ retry: return entry; } +EXPORT_SYMBOL_GPL(mas_walk); static inline bool mas_rewind_node(struct ma_state *mas) { @@ -5272,6 +5269,7 @@ int mas_empty_area(struct ma_state *mas, unsigned long min, mas->last = mas->index + size - 1; return 0; } +EXPORT_SYMBOL_GPL(mas_empty_area); /* * mas_empty_area_rev() - Get the highest address within the range that is @@ -5335,6 +5333,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, mas->index = mas->last - size + 1; return 0; } +EXPORT_SYMBOL_GPL(mas_empty_area_rev); static inline int mas_alloc(struct ma_state *mas, void *entry, unsigned long size, unsigned long *index) @@ -5656,6 +5655,7 @@ void *mas_store(struct ma_state *mas, void *entry) mas_wr_store_entry(&wr_mas); return wr_mas.content; } +EXPORT_SYMBOL_GPL(mas_store); /** * mas_store_gfp() - Store a value into the tree. @@ -5682,6 +5682,7 @@ retry: return 0; } +EXPORT_SYMBOL_GPL(mas_store_gfp); /** * mas_store_prealloc() - Store a value into the tree using memory @@ -5699,6 +5700,7 @@ void mas_store_prealloc(struct ma_state *mas, void *entry) BUG_ON(mas_is_err(mas)); mas_destroy(mas); } +EXPORT_SYMBOL_GPL(mas_store_prealloc); /** * mas_preallocate() - Preallocate enough nodes for a store operation @@ -5768,6 +5770,7 @@ void mas_destroy(struct ma_state *mas) } mas->alloc = NULL; } +EXPORT_SYMBOL_GPL(mas_destroy); /* * mas_expected_entries() - Set the expected number of entries that will be inserted. @@ -5829,6 +5832,7 @@ int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries) return ret; } +EXPORT_SYMBOL_GPL(mas_expected_entries); /** * mas_next() - Get the next entry. @@ -6009,6 +6013,7 @@ void *mas_find(struct ma_state *mas, unsigned long max) /* Retries on dead nodes handled by mas_next_entry */ return mas_next_entry(mas, max); } +EXPORT_SYMBOL_GPL(mas_find); /** * mas_find_rev: On the first call, find the first non-null entry at or below @@ -6055,7 +6060,7 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min) /* Retries on dead nodes handled by mas_next_entry */ return mas_prev_entry(mas, min); } -EXPORT_SYMBOL_GPL(mas_find); +EXPORT_SYMBOL_GPL(mas_find_rev); /** * mas_erase() - Find the range in which index resides and erase the entire @@ -6537,8 +6542,27 @@ static inline int mas_dead_node(struct ma_state *mas, unsigned long index) mas_rewalk(mas, index); return 1; } -#endif /* not defined __KERNEL__ */ +void mt_cache_shrink(void) +{ +} +#else +/* + * mt_cache_shrink() - For testing, don't use this. + * + * Certain testcases can trigger an OOM when combined with other memory + * debugging configuration options. This function is used to reduce the + * possibility of an out of memory even due to kmem_cache objects remaining + * around for longer than usual. + */ +void mt_cache_shrink(void) +{ + kmem_cache_shrink(maple_node_cache); + +} +EXPORT_SYMBOL_GPL(mt_cache_shrink); + +#endif /* not defined __KERNEL__ */ /* * mas_get_slot() - Get the entry in the maple state node stored at @offset. * @mas: The maple state @@ -6812,6 +6836,7 @@ void mt_dump(const struct maple_tree *mt) else if (entry) mt_dump_node(mt, entry, 0, mt_max[mte_node_type(entry)], 0); } +EXPORT_SYMBOL_GPL(mt_dump); /* * Calculate the maximum gap in a node and check if that's what is reported in @@ -7122,5 +7147,6 @@ done: rcu_read_unlock(); } +EXPORT_SYMBOL_GPL(mt_validate); #endif /* CONFIG_DEBUG_MAPLE_TREE */ -- cgit v1.2.3 From 9bbba5633488ee3e2903647c3484c4390ff39ea7 Mon Sep 17 00:00:00 2001 From: Liam Howlett Date: Mon, 7 Nov 2022 16:38:35 +0000 Subject: maple_tree: fix depth tracking in maple_state It is possible to confuse the depth tracking in the maple state by searching the same node for values. Fix the depth tracking by moving where the depth is incremented closer to where the node changes level. Also change the initial depth setting when using the root node. Link: https://lkml.kernel.org/r/20221107163814.866612-1-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Signed-off-by: Andrew Morton --- lib/maple_tree.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'lib/maple_tree.c') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f23f11da4113..59d0cebc774b 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1351,6 +1351,7 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) root = mas_root(mas); /* Tree with nodes */ if (likely(xa_is_node(root))) { + mas->depth = 1; mas->node = mte_safe_root(root); return NULL; } @@ -3727,7 +3728,6 @@ static bool mas_is_span_wr(struct ma_wr_state *wr_mas) static inline void mas_wr_walk_descend(struct ma_wr_state *wr_mas) { - wr_mas->mas->depth++; wr_mas->type = mte_node_type(wr_mas->mas->node); mas_wr_node_walk(wr_mas); wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type); @@ -3739,6 +3739,7 @@ static inline void mas_wr_walk_traverse(struct ma_wr_state *wr_mas) wr_mas->mas->min = wr_mas->r_min; wr_mas->mas->node = wr_mas->content; wr_mas->mas->offset = 0; + wr_mas->mas->depth++; } /* * mas_wr_walk() - Walk the tree for a write. -- cgit v1.2.3 From 7dc5ba6254bb242a9f45e43549171a2d84d25e6a Mon Sep 17 00:00:00 2001 From: Liam Howlett Date: Mon, 7 Nov 2022 16:39:02 +0000 Subject: maple_tree: don't set a new maximum on the node when not reusing nodes In RCU mode, the node limits were being updated to the last pivot which may not be correct and would cause the metadata to be set when it shouldn't. Fix this by not setting a new limit in this case. Link: https://lkml.kernel.org/r/20221107163857.867377-1-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Signed-off-by: Andrew Morton --- lib/maple_tree.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'lib/maple_tree.c') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 59d0cebc774b..df352f6ccc24 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3603,8 +3603,7 @@ static inline int mas_commit_b_node(struct ma_wr_state *wr_mas, node = mas_pop_node(wr_mas->mas); node->parent = mas_mn(wr_mas->mas)->parent; wr_mas->mas->node = mt_mk_node(node, b_type); - mab_mas_cp(b_node, 0, b_end, wr_mas->mas, true); - + mab_mas_cp(b_node, 0, b_end, wr_mas->mas, false); mas_replace(wr_mas->mas, false); reuse_node: mas_update_gap(wr_mas->mas); -- cgit v1.2.3