From 44bbf3d7e2b3ea87517e0d3d7dd571fca56cf129 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Wed, 13 Feb 2019 11:12:02 -0500
Subject: [PATCH] maple_tree: Dense node support & nulls in tree.

Support dense node types.  The reduces the space required for sequential
indexes a lot.
Splitting now decides between usign the parent type and the dense node
type for left/right independently.
Fixes had to be made to pivot lookups.
A few static inline additions to speed things up.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
 lib/maple_tree.c | 375 +++++++++++++++++++++++++++++++++++------------
 1 file changed, 282 insertions(+), 93 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 39deb426693e..13f0c38344d6 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -49,6 +49,22 @@ unsigned char mt_slots[] = {
 	[maple_range_64]	= MAPLE_RANGE64_SLOTS,
 };
 #define mt_slot_count(x) mt_slots[mt_node_type(x)]
+unsigned char mt_pivots[] = {
+	[maple_dense]		= 0,
+	[maple_sparse_6]	= 1,
+	[maple_sparse_9]	= MAPLE_SPARSE9_SLOTS - 1,
+	[maple_sparse_16]	= MAPLE_SPARSE16_SLOTS - 1,
+	[maple_sparse_21]	= MAPLE_SPARSE21_SLOTS - 1,
+	[maple_sparse_32]	= MAPLE_SPARSE32_SLOTS - 1,
+	[maple_sparse_64]	= MAPLE_SPARSE64_SLOTS - 1,
+	[maple_leaf_16]		= MAPLE_RANGE16_SLOTS - 1,
+	[maple_leaf_32]		= MAPLE_RANGE32_SLOTS - 1,
+	[maple_leaf_64]		= MAPLE_RANGE64_SLOTS - 1,
+	[maple_range_16]	= MAPLE_RANGE16_SLOTS - 1,
+	[maple_range_32]	= MAPLE_RANGE32_SLOTS - 1,
+	[maple_range_64]	= MAPLE_RANGE64_SLOTS - 1,
+};
+#define mt_pivot_count(x) mt_pivots[mt_node_type(x)]
 // Functions
 static struct maple_node *mt_alloc_one(gfp_t gfp)
 {
@@ -545,7 +561,7 @@ static inline struct maple_node *ma_next_alloc(struct ma_state *ms)
 	return mn;
 }
 
-static void ma_new_node(struct ma_state *ms, gfp_t gfp)
+static inline void ma_new_node(struct ma_state *ms, gfp_t gfp)
 {
 	struct maple_node *mn, *smn;
 	int req = ma_get_alloc_req(ms);
@@ -615,7 +631,7 @@ bool mas_nomem(struct ma_state *ms, gfp_t gfp)
 	ms->node = MAS_START;
 	return true;
 }
-static struct maple_node *mas_node_cnt(struct ma_state *ms, int count)
+static inline struct maple_node *mas_node_cnt(struct ma_state *ms, int count)
 {
 	int allocated = ma_get_alloc_cnt(ms);
 
@@ -628,7 +644,7 @@ static struct maple_node *mas_node_cnt(struct ma_state *ms, int count)
 	return ms->alloc;
 }
 
-static void *mas_start(struct ma_state *mas)
+static inline void *mas_start(struct ma_state *mas)
 {
 	void *entry;
 
@@ -653,7 +669,7 @@ static void *mas_start(struct ma_state *mas)
 	return entry;
 }
 
-unsigned char ma_data_end(const struct maple_node *mn,
+static inline unsigned char ma_data_end(const struct maple_node *mn,
 		const enum maple_type type)
 {
 	unsigned char data_end = 0;
@@ -673,44 +689,116 @@ unsigned char ma_data_end(const struct maple_node *mn,
 	return data_end;
 }
 
-static int ma_calc_split(struct ma_state *mas)
+static inline unsigned char ma_calc_split(struct ma_state *mas,
+		struct maple_node **left, struct maple_node **right)
 {
-	int i;
+	unsigned char i, j;
 	unsigned long min = mas->min;
 	unsigned long max = min;
+	enum maple_type type = mt_node_type(mas->node);
+	unsigned long pivot_cnt = mt_pivots[type];
+	unsigned char data_end = ma_data_end(mas->node, type);
 
-	for (i = 3; i < mt_slot_count(mas->node) - 1; i++) {
+	*left = ma_next_alloc(mas);
+	for (i = 0; i < data_end; i++) {
 		max = ma_get_pivot(mas->node, i);
-		if ((max - min) >= 8)
+		if ((max - min) > 15) {
+			if (i)
+				i--;
+			break;
+		}
+	}
+
+	if (i >= data_end) {
+		*left = mt_mk_node(*left, maple_dense);
+		return i;
+	}
+
+	*right = ma_next_alloc(mas);
+	if (i >= 4) {
+		*left = mt_mk_node(*left, maple_dense);
+		*right = mt_mk_node(*right, type);
+		return i;
+	}
+
+	if (data_end < pivot_cnt)
+		max = ma_get_pivot(mas->node, data_end);
+	else
+		max = mas->max;
+
+	for (j = data_end - 1; j >= 0; j--) {
+		min = ma_get_pivot(mas->node, j);
+		if ((max - min) > 15) {
+			j++;
 			break;
+		}
+	}
+	if (data_end - j >= 4) {
+		*left = mt_mk_node(*left, type);
+		*right = mt_mk_node(*right, maple_dense);
+		return j;
+	} else {
+		*left = mt_mk_node(*left, type);
+		*right = mt_mk_node(*right, type);
 	}
-	return i;
+
+	return i > 2 ? i : 3;
 }
-void ma_copy(struct ma_state *mas, struct ma_cp *cp)
+static inline void ma_linear_cp(struct ma_state *mas, struct ma_cp *cp)
+{
+	unsigned char sloc = cp->src_start; // src location
+	unsigned char pivot_cnt = mt_pivot_count(cp->src);
+	unsigned char slot;
+	unsigned long min = ma_get_pivot(cp->src, sloc);
+
+	while (sloc <= cp->src_end) {
+		unsigned long piv;
+		if (sloc < pivot_cnt) {
+			piv = ma_get_pivot(cp->src, sloc);
+			if (sloc != 0 && !piv)
+				break;
+			slot = piv - min;
+		} else {
+			// Last slot.
+			slot = mas->max - min;
+			if (!ma_get_rcu_slot(cp->src, sloc))
+				break;
+		}
+		ma_cp_rcu_slot(cp->dst, slot, cp->src, sloc);
+		sloc++;
+	}
+}
+static inline void ma_copy(struct ma_state *mas, struct ma_cp *cp)
 {
 	unsigned char sloc = cp->src_start; // src location
 	unsigned char dloc = cp->dst_start; // dst location
-	unsigned char slot_cnt = mt_slot_count(mas->node);
+	enum maple_type type = mt_node_type(cp->src);
+	unsigned char pivot_cnt = mt_pivots[type];
 
-	if (!cp->dst) {
+	if (cp->dst) {
+		if (!mt_pivot_count(cp->dst)) {
+			ma_linear_cp(mas, cp);
+			return;
+		}
+	} else {
 		/* Allocate a new node */
 
 		mas_node_cnt(mas, 1);
 		if (mas_is_err(mas))
 			return;
 		cp->dst = ma_next_alloc(mas);
-		cp->dst = mt_mk_node(cp->dst, mt_node_type(cp->src));
+		cp->dst = mt_mk_node(cp->dst, type);
 	}
 
 	while (sloc <= cp->src_end &&
 		dloc <= cp->dst_end) {
 
-		if (sloc != 0 && sloc < slot_cnt - 1 &&
+		if (sloc != 0 && sloc < pivot_cnt &&
 		    ma_get_pivot(cp->src, sloc) == 0)
 			break;
 
-		if (dloc < slot_cnt - 1) {
-			if (sloc < slot_cnt - 1)
+		if (dloc < pivot_cnt) {
+			if (sloc < pivot_cnt)
 				ma_cp_pivot(cp->dst, dloc, cp->src, sloc);
 			else if (dloc > 0 &&
 			   ma_get_pivot(cp->dst, dloc - 1) != mas->max)
@@ -721,23 +809,26 @@ void ma_copy(struct ma_state *mas, struct ma_cp *cp)
 	}
 	cp->dst_start = dloc;
 }
-static int ma_split_data(struct ma_state *mas, struct maple_node *left,
-			 struct maple_node *right)
+static inline int ma_split_data(struct ma_state *mas, struct maple_node *left,
+			 struct maple_node *right, unsigned char split)
 {
 
-	int split = ma_calc_split(mas);
-
 	MA_CP(cp, mas->node, left, 0, split);
+	if (!ma_get_rcu_slot(mas->node, split))
+		cp.src_end--;
+
 	ma_copy(mas, &cp);
 	cp.src_start = split + 1;
 	cp.src_end = mt_slot_count(mas->node) - 1;
-	cp.dst = right;
-	cp.dst_start = 0;
-	ma_copy(mas, &cp);
+	if (right) {
+		cp.dst = right;
+		cp.dst_start = 0;
+		ma_copy(mas, &cp);
+	}
 	return split;
 }
 
-static void ma_adopt_children(struct maple_node *parent)
+static inline void ma_adopt_children(struct maple_node *parent)
 {
 
 	struct maple_node *child;
@@ -759,7 +850,7 @@ static void ma_adopt_children(struct maple_node *parent)
 /* Private
  * Replace mn with mas->node in the tree
  */
-void mt_replace(struct ma_state *mas)
+static inline void mt_replace(struct ma_state *mas)
 {
 	struct maple_node *mn = mt_to_node(mas->node);
 	struct maple_node *parent;
@@ -799,7 +890,7 @@ void mt_replace(struct ma_state *mas)
  *       This isn't safe to use to copy the last slot as it doesn't check the
  *       pivot.
  */
-static void mas_partial_copy(struct ma_state *mas,
+static inline void mas_partial_copy(struct ma_state *mas,
 					       unsigned char end)
 {
 	MA_CP(cp, mas->node, NULL, 0, end);
@@ -812,27 +903,41 @@ static void mas_partial_copy(struct ma_state *mas,
 	return;
 }
 
-static void ma_link(struct maple_node *new, struct maple_node *parent,
+static inline void ma_link(struct maple_node *new, struct maple_node *parent,
 		unsigned char slot, unsigned long pivot, enum maple_type type)
 {
-	struct maple_node *new_enc = mt_mk_node(new, type);
-	unsigned char slot_cnt = mt_slots[type];
+	unsigned char pivot_cnt = mt_pivots[type];
 
 	mt_set_parent(new, parent, slot);
-	if (slot < slot_cnt - 1)
+	if (slot < pivot_cnt)
 		ma_set_pivot(parent, slot, pivot);
 
-	ma_set_rcu_slot(parent, slot, new_enc);
-	if (!mt_is_leaf(new_enc))
-		ma_adopt_children(new_enc);
+	ma_set_rcu_slot(parent, slot, new);
+	if (!mt_is_leaf(new))
+		ma_adopt_children(new);
 
 }
-static int ma_split(struct ma_state *mas, unsigned char slot)
+/*
+ * split late, that is to say.. the parent may be full and need to be split.
+ * Once we know there is space (we need only a single location), then we can
+ * continue.
+ *
+ * 1. Allocate 3 nodes: left, right, parent
+ * 2. If it's not root, copy all data from the old parent to the new one and
+ *    leave a hole.
+ * 3. Calculate the location to split the nodes.
+ * 4. Figure out the type of the node
+ * 5. Copy the data to the new nodes
+ * 6. Link in the nodes
+ * 7. replace old_parent
+ * 8. set up ma_state for return.
+ *
+ */
+static inline int ma_split(struct ma_state *mas, unsigned char slot)
 {
 	struct maple_node *full = (mas->node);
 	unsigned char split, p_slot = 0, p_end = 0;
-	struct maple_node *old_parent, *new_parent, *left, *right;
-	enum maple_type ctype; // Child type.
+	struct maple_node *old_parent, *new_parent, *left = NULL, *right = NULL;
 	enum maple_type ptype; // parent type.
 	unsigned long pivot;
 	unsigned char slot_cnt = mt_slot_count(mas->node);
@@ -869,23 +974,12 @@ static int ma_split(struct ma_state *mas, unsigned char slot)
 		return 0;
 
 	// Allocations.
-	right = ma_next_alloc(mas);
-	left = ma_next_alloc(mas);
-	new_parent = ma_next_alloc(mas);
-
-	// the node type for the children types.
-	ctype = mt_node_type(mas->node);
+	new_parent = mt_mk_node(ma_next_alloc(mas), ptype);
 
-	right = mt_mk_node(right, ctype);
-	left = mt_mk_node(left, ctype);
-	new_parent = mt_mk_node(new_parent, ptype);
-
-
-	// copy the data and calculate the split location.
-	split = ma_split_data(mas, left, right);
 
 	// Copy the parents information
 	if (!ma_is_root(full)) {
+		// FIXME: Optimize this to avoid setting a slot/pivot twice.
 		// Copy the parent data and leave a hole.
 		MA_CP(cp, old_parent, new_parent, 0, p_slot);
 		ma_copy(mas, &cp);
@@ -893,28 +987,43 @@ static int ma_split(struct ma_state *mas, unsigned char slot)
 		cp.src_start = p_slot + 1;
 		cp.src_end = p_end + 1;
 		ma_copy(mas, &cp);
-		// Update encoded slots in children
-		ma_adopt_children(new_parent);
 	}
 
-	// Copy grand parent to the parent, including slot encoding.
-	mt_to_node(new_parent)->parent = mt_to_node(old_parent)->parent;
-	// Set up the link to the right in the new parent
-	if (ma_is_root(full))
-		pivot = mt_node_max(mas->node);
-	else
-		pivot = ma_get_pivot(old_parent, p_slot);
+	// calculate the split location.
+	split = ma_calc_split(mas, &left, &right);
+
+	// the node type for the children types.
+	// Node types must be set to copy data into them.
+	ma_split_data(mas, left, right, split);
+
 
-	ma_link(right, new_parent, p_slot + 1, pivot, ctype);
 
+	if (right) {
+		// Set up the link to the right in the new parent
+		if (mt_node_type(right) == maple_dense)
+			pivot = ma_get_pivot(mas->node, split)
+				+ mt_node_max(right) - 1;
+		else if (ma_is_root(full))
+			pivot = mt_node_max(mas->node);
+		else
+			pivot = ma_get_pivot(old_parent, p_slot);
+
+		ma_link(right, new_parent, p_slot + 1, pivot, ptype);
+	}
 	// Set up the link to the left in the new parent
-	if (split < slot_cnt - 1)
+	if (!right)
+		pivot = mt_node_max(left) - 1;
+	else if (split < slot_cnt - 1)
 		pivot = ma_get_pivot(mas->node, split);
 	else
 		pivot = ma_get_pivot(left, split - 1);
 
-	ma_link(left, new_parent, p_slot, pivot, ctype);
+	ma_link(left, new_parent, p_slot, pivot, ptype);
 
+	// Copy grand parent to the parent, including slot encoding.
+	mt_to_node(new_parent)->parent = mt_to_node(old_parent)->parent;
+	// Update encoded slots in children
+	ma_adopt_children(new_parent);
 	// Set up maple state to replace the parent node in the grandparent.
 	mas->node = new_parent;
 	// Replace the parent node & free the old parent.
@@ -922,10 +1031,18 @@ static int ma_split(struct ma_state *mas, unsigned char slot)
 
 	// Set up the ma_state for the return.  Point to the correct node for
 	// the insert or subsequent split.
-	if (mas->index <= pivot)
+	if (mas->index <= pivot) {
 		mas->node = left;
-	else
+		p_slot = slot - p_slot + 1;
+	} else {
 		mas->node = right;
+		p_slot = slot - p_slot + 2;
+	}
+
+	if (mas->index > mt_node_max(mas->node) + mas->min) {
+		mas->node = new_parent;
+		split = p_slot;
+	}
 
 	// Free the full node.
 	mt_free(mt_to_node(full));
@@ -945,7 +1062,8 @@ static int ma_split(struct ma_state *mas, unsigned char slot)
  * 4. Write the entry.
  *
  */
-static int _ma_insert(struct ma_state *mas, void *entry, unsigned char slot)
+static inline int _ma_insert(struct ma_state *mas, void *entry,
+		unsigned char slot)
 {
 	struct maple_node *p_mn;
 	int o_end = ma_data_end(mas->node, mt_node_type(mas->node)); // Old end
@@ -953,10 +1071,25 @@ static int _ma_insert(struct ma_state *mas, void *entry, unsigned char slot)
 	unsigned long max = mas->max;
 	unsigned long min = mas->min;
 	int ret = 1;
-	unsigned char slot_cnt = mt_slot_count(mas->node);
+	enum maple_type type = mt_node_type(mas->node);
+	unsigned char slot_cnt = mt_slots[type];
+	unsigned char pivot_cnt = mt_pivots[type];
+
+	/* Linear node type */
+	if (!pivot_cnt) {
+		min = mas->index - mas->min;
+		if (mas->min)
+			min--;
+		max = mas->last - mas->min;
+		do
+			ma_update_rcu_slot(mas->node, min++, entry);
+		while(min < max);
+
+		return max - min;
+	}
 
 	/* Calculate the range of the slot */
-	if (slot < slot_cnt - 1 &&  ma_get_pivot(mas->node, slot) != 0)
+	if (slot < pivot_cnt &&  ma_get_pivot(mas->node, slot) != 0)
 		max = ma_get_pivot(mas->node, slot);
 
 	if (slot == MAPLE_NODE_SLOTS)
@@ -973,7 +1106,7 @@ static int _ma_insert(struct ma_state *mas, void *entry, unsigned char slot)
 		n_end++;
 
 	if (n_end > slot_cnt - 1 ||
-	    (n_end == slot_cnt - 1 && mas->max == mt_node_max(mas->node))){
+	    (n_end == slot_cnt - 1 && mas->max != mas->last)){
 		unsigned char split = ma_split(mas, slot);
 		if (mas_is_err(mas))
 			return 0;
@@ -981,12 +1114,46 @@ static int _ma_insert(struct ma_state *mas, void *entry, unsigned char slot)
 		if (split <= slot)
 			slot -= split;
 
-		n_end -= split;
-		o_end -= split;
+		return _ma_insert(mas, entry, slot);
 	}
+
 	/* Save the node in case we are not appending. */
 	p_mn = mas->node;
 
+	if (!mt_is_leaf(mas->node)) {
+		struct maple_node *leaf, *sibling;
+		unsigned char sibling_slot = slot;
+		enum maple_type mt = maple_leaf_64;
+		unsigned long o_min = mas->min;
+		unsigned long o_max = mas->max;
+
+		mas_node_cnt(mas, 1);
+		if (mas_is_err(mas))
+			return 0;
+
+		if (slot > 0)
+			sibling_slot -= 1;
+		else
+			sibling_slot += 1;
+
+		sibling = ma_get_rcu_slot(mas->node, sibling_slot);
+		if (sibling)
+			mt = mt_node_type(sibling);
+
+		leaf = mt_mk_node(ma_next_alloc(mas), mt);
+		mt_set_parent(leaf, mas->node, slot);
+		mas->node = leaf;
+		mas->min = min;
+		mas->max = max;
+		_ma_insert(mas, entry, 0);
+		mas->min = o_min;
+		mas->max = o_max;
+		mas->node = p_mn;
+		entry = leaf;
+		if (mt == maple_dense)
+			mas->last = mas->index + mt_max[mt] - 1;
+	}
+
 	/* Figure out if this is an append or not.
 	 * Appending does not need to create a new node. */
 	if (slot - 1 == o_end) {
@@ -1001,13 +1168,16 @@ static int _ma_insert(struct ma_state *mas, void *entry, unsigned char slot)
 		o_end = slot;
 	}
 
+
+
 	if (mas->index && min != mas->index - 1) {
 		/* When writing a NULL entry, the order must be reversed to
 		 * ensure readers don't get incorrect data on appends
 		 */
 		/* Write the entry */
 		ma_set_rcu_slot(mas->node, ++slot, entry);
-		ma_set_pivot(mas->node, slot, mas->last);
+		if (slot < pivot_cnt)
+			ma_set_pivot(mas->node, slot, mas->last);
 		/* Write NULL entry */
 		ma_set_rcu_slot(mas->node, --slot, NULL);
 		if (o_end == n_end + 1) // Append.
@@ -1022,7 +1192,7 @@ static int _ma_insert(struct ma_state *mas, void *entry, unsigned char slot)
 		if (o_end == n_end + 1) // Append.
 			wmb();
 
-		if (slot < mt_slot_count(mas->node) - 1)
+		if (slot < pivot_cnt)
 			ma_set_pivot(mas->node, slot++, mas->last);
 	}
 
@@ -1031,7 +1201,7 @@ static int _ma_insert(struct ma_state *mas, void *entry, unsigned char slot)
 		o_end++;
 
 	/* Copy remainder of node if this isn't an append */
-	MA_CP(cp, p_mn, mas->node, o_end, mt_slot_count(p_mn) - 1);
+	MA_CP(cp, p_mn, mas->node, o_end, slot_cnt - 1);
 	cp.dst_start = slot;
 	cp.dst_end = n_end;
 	ma_copy(mas, &cp);
@@ -1042,7 +1212,7 @@ static int _ma_insert(struct ma_state *mas, void *entry, unsigned char slot)
 	return ret;
 }
 
-static void ma_root_expand(struct ma_state *ms, void *entry)
+static inline void ma_root_expand(struct ma_state *ms, void *entry)
 {
 	void *r_entry = rcu_dereference(ms->tree->ma_root);  // root entry
 	struct maple_node *mn;
@@ -1073,18 +1243,23 @@ static void ma_root_expand(struct ma_state *ms, void *entry)
  * Note: The mas->node will most likely be changed, so keep track of the old
  * mas->node to free it.
  */
-static int mas_coalesce(struct ma_state *mas)
+static inline int mas_coalesce(struct ma_state *mas)
 {
 	struct maple_node *src = mas->node;
 	struct maple_node *dst = NULL;
 	unsigned char s_slot, d_slot = 0;
 	unsigned long last = 0;
 	int ret = 0;
-	unsigned char slot_cnt = mt_slot_count(mas->node);
+	enum maple_type type = mt_node_type(mas->node);
+	unsigned char slot_cnt = mt_slots[type];
+	unsigned char pivot_cnt = mt_pivots[type];
+
+	if (!pivot_cnt)
+		return 0;
 
 
 	for (s_slot = 0; s_slot < slot_cnt; s_slot++) {
-		if (s_slot < slot_cnt - 1) {
+		if (s_slot < pivot_cnt) {
 			if (s_slot != 0 && last == ma_get_pivot(src, s_slot)) {
 				if (!dst) {
 					// Skip this duplicate slot
@@ -1121,18 +1296,25 @@ done:
 	return ret;
 }
 
-static bool mas_search_slots(struct ma_state *ms, unsigned long val,
+static inline bool mas_search_slots(struct ma_state *mas, unsigned long val,
 		enum maple_type type)
 {
 	int i;
 	bool ret = false;
-	unsigned char slot_cnt = mt_slots[type];
+	unsigned char pivot_cnt = mt_pivots[type];
 	unsigned long pivot = 0;
 
-	for (i = 0; i < slot_cnt - 1; i++) {
-		pivot = _ma_get_pivot(ms->node, i, type);
+	if (!pivot_cnt) {
+		i = val - mas->min;
+		if (mas->min)
+			i--;
+		goto linear_node;
+	}
+
+	for (i = 0; i < pivot_cnt; i++) {
+		pivot = _ma_get_pivot(mas->node, i, type);
 		if (i != 0 && pivot == 0) {
-			ma_set_slot(ms, MAPLE_NODE_SLOTS);
+			ma_set_slot(mas, MAPLE_NODE_SLOTS);
 			return ret;
 		}
 
@@ -1140,19 +1322,20 @@ static bool mas_search_slots(struct ma_state *ms, unsigned long val,
 			break;
 	}
 
-	if (i == slot_cnt - 2) {
+	if (i == pivot_cnt - 1) {
 		if (val > pivot)
 			i++;
 	}
 
-	if (_ma_get_rcu_slot(ms->node, i, type))
+linear_node:
+	if (_ma_get_rcu_slot(mas->node, i, type))
 		ret = true;
 
-	ma_set_slot(ms, i);
+	ma_set_slot(mas, i);
 	return ret;
 }
 
-bool mas_traverse(struct ma_state *mas, enum maple_type type)
+static inline bool mas_traverse(struct ma_state *mas, enum maple_type type)
 {
 	unsigned char slot = ma_get_slot(mas);
 
@@ -1163,7 +1346,7 @@ bool mas_traverse(struct ma_state *mas, enum maple_type type)
 	return true;
 }
 
-bool _mas_walk(struct ma_state *mas)
+static inline bool _mas_walk(struct ma_state *mas)
 {
 	mas->node = mas_start(mas);
 	enum maple_type type;
@@ -1176,7 +1359,7 @@ bool _mas_walk(struct ma_state *mas)
 	return true;
 }
 
-void ma_insert(struct ma_state *mas, void *entry)
+static inline void ma_insert(struct ma_state *mas, void *entry)
 {
 	unsigned char slot = MAPLE_NODE_SLOTS;
 	bool leaf;
@@ -1266,7 +1449,9 @@ void *mas_walk(struct ma_state *mas)
  */
 int ma_erase(struct ma_state *mas)
 {
-	unsigned char slot_cnt = mt_slot_count(mas->node);
+	enum maple_type type = mt_node_type(mas->node);
+	unsigned char slot_cnt = mt_slots[type];
+	unsigned char pivot_cnt = mt_pivots[type];
 	unsigned long piv_val;
 	int cnt = -EINVAL;
 	int slot;
@@ -1278,10 +1463,15 @@ int ma_erase(struct ma_state *mas)
 		return cnt;
 
 	ma_update_rcu_slot(mas->node, slot, NULL);
+	cnt = 1;
+
 	if ((slot >= slot_cnt - 1))
-		return 1;
+		return cnt;
 
-	if ((slot < slot_cnt - 2) &&
+	if (!pivot_cnt)
+		return cnt;
+
+	if ((slot < pivot_cnt) &&
 	    ((ma_get_pivot(mas->node, slot + 1) == 0) ||
 	     (ma_get_rcu_slot(mas->node, slot + 1) == NULL))) {
 		piv_val = ma_get_pivot(mas->node, ++slot);
@@ -1289,7 +1479,6 @@ int ma_erase(struct ma_state *mas)
 		piv_val = ma_get_pivot(mas->node, slot);
 	}
 
-	cnt = 1;
 	/* Walk down and set all the previous pivots with NULLs to piv_val */
 	while(--slot >= 0 && ma_get_rcu_slot(mas->node, slot) == NULL) {
 		ma_set_pivot(mas->node, slot, piv_val);
@@ -1461,7 +1650,7 @@ void mt_dump_range64(void *entry, unsigned long min, unsigned long max,
 			break;
 		if (leaf)
 			mt_dump_entry(node->slot[i], first, last);
-		else
+		else if (node->slot[i])
 			mt_dump_node(node->slot[i], first, last, depth + 1);
 
 		if (last == max)
@@ -1512,7 +1701,7 @@ void mt_dump(const struct maple_tree *mt)
 		 mt, mt->ma_flags, entry);
 	if (!xa_is_node(entry))
 		mt_dump_entry(entry, 0, 0);
-	else
+	else if (entry)
 		mt_dump_node(entry, 0, mt_max[mt_node_type(entry)], 0);
 }
 extern void kmem_cache_set_non_kernel(struct kmem_cache *, unsigned int);
-- 
2.50.1