Skip to contentSkip to conversation

Clean up and refinement for maple tree

PATCH Applied Vernon Yang 2 participants 9 messages Dec 21, 2022

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

v2 cover Clean up and refinement for maple tree

Hello,

This patchset clean up and refinement some maple tree code, a few small changes make the code easier to understand and for better readability.

v2 changes:
- Add Reviewed-by Liam R. Howlett to all patches besides 6 & 8.
- Remove patch 6.
- Add an unlikely() to the if statement for patch 8.

v1: https://lore.kernel.org/linux-mm/[email protected]/

Vernon Yang (7):
maple_tree: remove extra space and blank line
maple_tree: remove extra return statement
maple_tree: use mt_node_max() instead of direct operations mt_max[]
maple_tree: use macro MA_ROOT_PARENT instead of number
maple_tree: remove the redundant code
maple_tree: refine ma_state init from mas_start()
maple_tree: refine mab_calc_split function

 include/linux/maple_tree.h |  6 ------
 lib/maple_tree.c           | 35 ++++++++++++-----------------------
 2 files changed, 12 insertions(+), 29 deletions(-)

--
2.34.1

#1 lore raw

PATCH v2 1/7 maple_tree: remove extra space and blank line

These extra space and blank line is unnecessary, so drop it.

---
 include/linux/maple_tree.h |  2 --
 lib/maple_tree.c           | 14 ++++----------
 2 files changed, 4 insertions(+), 12 deletions(-)
include/linux/maple_tree.h +0 -2
index e594db58a0f1..4ee5a969441c 100644
@@ -517,7 +517,6 @@ static inline void mas_reset(struct ma_state *mas)
  * entry.
  *
  * Note: may return the zero entry.
- *
  */
 #define mas_for_each(__mas, __entry, __max) \
 	while (((__entry) = mas_find((__mas), (__max))) != NULL)
@@ -639,7 +638,6 @@ static inline void mt_set_in_rcu(struct maple_tree *mt)
 }
 
 static inline unsigned int mt_height(const struct maple_tree *mt)
-
 {
 	return (mt->ma_flags & MT_FLAGS_HEIGHT_MASK) >> MT_FLAGS_HEIGHT_OFFSET;
 }
lib/maple_tree.c +4 -10
index fe3947b80069..8ace65a5eea5 100644
@@ -183,7 +183,6 @@ static void ma_free_rcu(struct maple_node *node)
 	call_rcu(&node->rcu, mt_free_rcu);
 }
 
-
 static void mas_set_height(struct ma_state *mas)
 {
 	unsigned int new_flags = mas->tree->ma_flags;
@@ -468,7 +467,7 @@ static inline
 void mte_set_parent(struct maple_enode *enode, const struct maple_enode *parent,
 		    unsigned char slot)
 {
-	unsigned long val = (unsigned long) parent;
+	unsigned long val = (unsigned long)parent;
 	unsigned long shift;
 	unsigned long type;
 	enum maple_type p_type = mte_node_type(parent);
@@ -502,7 +501,7 @@ void mte_set_parent(struct maple_enode *enode, const struct maple_enode *parent,
  */
 static inline unsigned int mte_parent_slot(const struct maple_enode *enode)
 {
-	unsigned long val = (unsigned long) mte_to_node(enode)->parent;
+	unsigned long val = (unsigned long)mte_to_node(enode)->parent;
 
 	/* Root. */
 	if (val & 1)
@@ -1278,7 +1277,6 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)
 		mas->alloc->total = success;
 	mas_set_err(mas, -ENOMEM);
 	return;
-
 }
 
 /*
@@ -2946,7 +2944,7 @@ static inline void *mtree_range_walk(struct ma_state *mas)
 	mas->min = prev_min;
 	mas->max = prev_max;
 	mas->node = last;
-	return (void *) next;
+	return (void *)next;
 
 dead_node:
 	mas_reset(mas);
@@ -3464,7 +3462,6 @@ static inline bool mas_push_data(struct ma_state *mas, int height,
  */
 static int mas_split(struct ma_state *mas, struct maple_big_node *b_node)
 {
-
 	struct maple_subtree_state mast;
 	int height = 0;
 	unsigned char mid_split, split = 0;
@@ -3890,7 +3887,7 @@ static inline void *mtree_lookup_walk(struct ma_state *mas)
 			goto dead_node;
 	} while (!ma_is_leaf(type));
 
-	return (void *) next;
+	return (void *)next;
 
 dead_node:
 	mas_reset(mas);
@@ -4708,7 +4705,6 @@ static inline void *mas_next_nentry(struct ma_state *mas,
 
 static inline void mas_rewalk(struct ma_state *mas, unsigned long index)
 {
-
 retry:
 	mas_set(mas, index);
 	mas_state_walk(mas);
@@ -4716,7 +4712,6 @@ static inline void mas_rewalk(struct ma_state *mas, unsigned long index)
 		goto retry;
 
 	return;
-
 }
 
 /*
@@ -5618,7 +5613,6 @@ static void mas_wr_store_setup(struct ma_wr_state *wr_mas)
 				mas_reset(wr_mas->mas);
 		}
 	}
-
 }
 
 /* Interface */
Signature · 1 line
2.34.1
#2 lore raw

PATCH v2 2/7 maple_tree: remove extra return statement

In reply to Vernon Yang

For functions with a return type of void, it is unnecessary to add a reurn statement at the end of the function, so drop it.

---
 lib/maple_tree.c | 3 ---
 1 file changed, 3 deletions(-)
lib/maple_tree.c +0 -3
index 8ace65a5eea5..34aa93c85d6e 100644
@@ -1276,7 +1276,6 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)
 	if (mas->alloc && !(((unsigned long)mas->alloc & 0x1)))
 		mas->alloc->total = success;
 	mas_set_err(mas, -ENOMEM);
-	return;
 }
 
 /*
@@ -4710,8 +4709,6 @@ static inline void mas_rewalk(struct ma_state *mas, unsigned long index)
 	mas_state_walk(mas);
 	if (mas_is_start(mas))
 		goto retry;
-
-	return;
 }
 
 /*
Signature · 1 line
2.34.1
#3 lore raw

PATCH v2 3/7 maple_tree: use mt_node_max() instead of direct operations mt_max[]

In reply to Vernon Yang

Use mt_node_max() to get the maximum number of slots for a node, rather than direct operations mt_max[], makes it better portability.

---
 lib/maple_tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
lib/maple_tree.c +2 -2
index 34aa93c85d6e..3d45c515ed42 100644
@@ -6723,7 +6723,7 @@ static void mt_dump_range64(const struct maple_tree *mt, void *entry,
 
 		if (i < (MAPLE_RANGE64_SLOTS - 1))
 			last = node->pivot[i];
-		else if (!node->slot[i] && max != mt_max[mte_node_type(entry)])
+		else if (!node->slot[i] && max != mt_node_max(entry))
 			break;
 		if (last == 0 && i > 0)
 			break;
@@ -6830,7 +6830,7 @@ void mt_dump(const struct maple_tree *mt)
 	if (!xa_is_node(entry))
 		mt_dump_entry(entry, 0, 0, 0);
 	else if (entry)
-		mt_dump_node(mt, entry, 0, mt_max[mte_node_type(entry)], 0);
+		mt_dump_node(mt, entry, 0, mt_node_max(entry), 0);
 }
 EXPORT_SYMBOL_GPL(mt_dump);
 
Signature · 1 line
2.34.1
#4 lore raw

PATCH v2 4/7 maple_tree: use macro MA_ROOT_PARENT instead of number

In reply to Vernon Yang

When you need to compare whether node->parent is parent of the root node, using macro MA_ROOT_PARENT is easier to understand and for better readability.

---
 lib/maple_tree.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
lib/maple_tree.c +1 -2
index 3d45c515ed42..b3a215dd961e 100644
@@ -503,8 +503,7 @@ static inline unsigned int mte_parent_slot(const struct maple_enode *enode)
 {
 	unsigned long val = (unsigned long)mte_to_node(enode)->parent;
 
-	/* Root. */
-	if (val & 1)
+	if (val & MA_ROOT_PARENT)
 		return 0;
 
 	/*
Signature · 1 line
2.34.1
#5 lore raw

PATCH v2 5/7 maple_tree: remove the redundant code

In reply to Vernon Yang

The macros CONFIG_DEBUG_MAPLE_TREE_VERBOSE no one uses, functions mas_dup_tree() and mas_dup_store() are not implemented, just function declaration, so drop it.

---
 include/linux/maple_tree.h | 4 ----
 1 file changed, 4 deletions(-)
include/linux/maple_tree.h +0 -4
index 4ee5a969441c..815a27661517 100644
@@ -12,7 +12,6 @@
 #include <linux/rcupdate.h>
 #include <linux/spinlock.h>
 /* #define CONFIG_MAPLE_RCU_DISABLED */
-/* #define CONFIG_DEBUG_MAPLE_TREE_VERBOSE */
 
 /*
  * Allocated nodes are mutable until they have been inserted into the tree,
@@ -483,9 +482,6 @@ static inline bool mas_is_paused(struct ma_state *mas)
 	return mas->node == MAS_PAUSE;
 }
 
-void mas_dup_tree(struct ma_state *oldmas, struct ma_state *mas);
-void mas_dup_store(struct ma_state *mas, void *entry);
-
 /*
  * This finds an empty area from the highest address to the lowest.
  * AKA "Topdown" version,
Signature · 1 line
2.34.1
#6 lore raw

PATCH v2 6/7 maple_tree: refine ma_state init from mas_start()

In reply to Vernon Yang

If mas->node is an MAS_START, there are three cases, and they all assign different values to mas->node and mas->offset. So there is no need to set them to a default value before updating.

Update them directly to make them easier to understand and for better readability.

---
 lib/maple_tree.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
lib/maple_tree.c +3 -3
index b3a215dd961e..5911211c8557 100644
@@ -1329,7 +1329,7 @@ static void mas_node_count(struct ma_state *mas, int count)
  * mas_start() - Sets up maple state for operations.
  * @mas: The maple state.
  *
- * If mas->node == MAS_START, then set the min, max, depth, and offset to
+ * If mas->node == MAS_START, then set the min, max and depth to
  * defaults.
  *
  * Return:
@@ -1343,22 +1343,22 @@ static inline struct maple_enode *mas_start(struct ma_state *mas)
 	if (likely(mas_is_start(mas))) {
 		struct maple_enode *root;
 
-		mas->node = MAS_NONE;
 		mas->min = 0;
 		mas->max = ULONG_MAX;
 		mas->depth = 0;
-		mas->offset = 0;
 
 		root = mas_root(mas);
 		/* Tree with nodes */
 		if (likely(xa_is_node(root))) {
 			mas->depth = 1;
 			mas->node = mte_safe_root(root);
+			mas->offset = 0;
 			return NULL;
 		}
 
 		/* empty tree */
 		if (unlikely(!root)) {
+			mas->node = MAS_NONE;
 			mas->offset = MAPLE_NODE_SLOTS;
 			return NULL;
 		}
Signature · 1 line
2.34.1
#7 lore raw

PATCH v2 7/7 maple_tree: refine mab_calc_split function

In reply to Vernon Yang

Invert the conditional judgment of the mid_split, to focus the return statement in the last statement, which is easier to understand and for better readability.

---
 lib/maple_tree.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)
lib/maple_tree.c +2 -3
index 5911211c8557..5e1a9d39b330 100644
@@ -1882,10 +1882,9 @@ static inline int mab_calc_split(struct ma_state *mas,
 
 	/* Avoid ending a node on a NULL entry */
 	split = mab_no_null_split(bn, split, slot_count);
-	if (!(*mid_split))
-		return split;
 
-	*mid_split = mab_no_null_split(bn, *mid_split, slot_count);
+	if (unlikely(*mid_split))
+		*mid_split = mab_no_null_split(bn, *mid_split, slot_count);
 
 	return split;
 }
Signature · 1 line
2.34.1
Reviewed-by on the v2 series
#8 lore raw
In reply to Vernon Yang
Quoted 11 lines · Vernon Yang

Hello,

This patchset clean up and refinement some maple tree code, a few small changes make the code easier to understand and for better readability.

v2 changes:
- Add Reviewed-by Liam R. Howlett to all patches besides 6 & 8.
- Remove patch 6.
- Add an unlikely() to the if statement for patch 8.

v1: https://lore.kernel.org/linux-mm/[email protected]/

Quoted 17 lines

Vernon Yang (7):
maple_tree: remove extra space and blank line
maple_tree: remove extra return statement
maple_tree: use mt_node_max() instead of direct operations mt_max[]
maple_tree: use macro MA_ROOT_PARENT instead of number
maple_tree: remove the redundant code
maple_tree: refine ma_state init from mas_start()
maple_tree: refine mab_calc_split function

 include/linux/maple_tree.h |  6 ------
 lib/maple_tree.c           | 35 ++++++++++++-----------------------
 2 files changed, 12 insertions(+), 29 deletions(-)

--
2.34.1