From 1921276f5c8cf7025505243c0308449de827ec48 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Thu, 24 Sep 2020 21:58:53 -0400
Subject: [PATCH] maple_tree: wip for fast path

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
 include/linux/maple_tree.h |   3 +
 lib/maple_tree.c           | 494 ++++++++++++++++++++++++++++---------
 lib/test_maple_tree.c      |  58 ++++-
 3 files changed, 437 insertions(+), 118 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index e4e8a24b9911..3b3eec60dd3e 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -11,6 +11,9 @@
 #include <linux/kernel.h>
 #include <linux/rcupdate.h>
 #include <linux/spinlock.h>
+#define CONFIG_MAPLE_RCU_DISABLED
+//#define CONFIG_DEBUG_MAPLE_TREE
+//#define CONFIG_DEBUG_MAPLE_TREE_VERBOSE
 
 /*
  * Allocated nodes are mutable until they have been inserted into the tree,
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 763108325ed0..5d6c69aae610 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -21,7 +21,6 @@
 #define ma_parent_ptr(x) ((struct maple_pnode *)(x))
 #define ma_mnode_ptr(x) ((struct maple_node *)(x))
 #define ma_enode_ptr(x) ((struct maple_enode *)(x))
-
 static struct kmem_cache *maple_node_cache;
 
 unsigned long mt_max[] = {
@@ -529,9 +528,9 @@ static inline unsigned long mte_pivot(const struct maple_enode *mn,
 	}
 }
 
-static inline unsigned long _mas_safe_pivot(const struct ma_state *mas,
-					    unsigned long *pivots,
-					    unsigned char piv, enum maple_type type)
+static inline unsigned long
+_mas_safe_pivot(const struct ma_state *mas, unsigned long *pivots,
+		unsigned char piv, enum maple_type type)
 {
 	if (piv >= mt_pivots[type])
 		return mas->max;
@@ -546,8 +545,8 @@ static inline unsigned long _mas_safe_pivot(const struct ma_state *mas,
  *
  * Return: The pivot (including mas->max for the final piv)
  */
-static inline unsigned long mas_safe_pivot(const struct ma_state *mas,
-					 unsigned char piv)
+static inline unsigned long
+mas_safe_pivot(const struct ma_state *mas, unsigned char piv)
 {
 	enum maple_type type = mte_node_type(mas->node);
 	unsigned long *pivots = ma_pivots(mas_mn(mas), type);
@@ -559,9 +558,8 @@ static inline unsigned long mas_safe_pivot(const struct ma_state *mas,
  * mas_safe_min() - Return the minimum for a given offset.
  *
  */
-static inline unsigned long mas_safe_min(struct ma_state *mas,
-					 unsigned long *pivots,
-					 unsigned char piv)
+static inline unsigned long
+mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char piv)
 {
 	if (!piv)
 		return mas->min;
@@ -569,6 +567,15 @@ static inline unsigned long mas_safe_min(struct ma_state *mas,
 	return pivots[piv - 1] + 1;
 }
 
+static inline unsigned long
+mas_logical_pivot(struct ma_state *mas, unsigned long *pivots,
+		  unsigned char piv, enum maple_type type)
+{
+	unsigned long lpiv = _mas_safe_pivot(mas, pivots, piv, type);
+	if (!lpiv && piv)
+		return mas->max;
+	return lpiv;
+}
 static inline void ma_set_pivot(struct maple_node *mn, unsigned char piv,
 		enum maple_type type, unsigned long val)
 {
@@ -1022,7 +1029,7 @@ done:
  *
  * Returns: The zero indexed last slot with data (may be null).
  */
-static inline unsigned char mas_data_end(const struct ma_state *mas)
+static inline unsigned char mas_data_end(struct ma_state *mas)
 {
 	enum maple_type type = mte_node_type(mas->node);
 	unsigned char offset = mt_min_slots[type];
@@ -1030,9 +1037,10 @@ static inline unsigned char mas_data_end(const struct ma_state *mas)
 
 	if (pivots[offset]) {
 		while (offset < mt_slots[type]) {
-			piv = _mas_safe_pivot(mas, pivots, offset, type);
-			if ((!piv && offset) || piv >= mas->max)
+			piv = mas_logical_pivot(mas, pivots, offset, type);
+			if (piv >= mas->max)
 				break;
+
 			offset++;
 		}
 	} else {
@@ -1055,10 +1063,9 @@ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas)
 {
 	enum maple_type mt = mte_node_type(mas->node);
 	unsigned long *pivots = ma_pivots(mas_mn(mas), mt);
+	unsigned long pstart, pend, gap = 0, max_gap = 0;
 	void **slots = ma_slots(mas_mn(mas), mt);
-	unsigned long gap = 0, max_gap = 0;
-	unsigned long pstart, pend;
-	int i;
+	unsigned char i;
 
 	if (ma_is_dense(mt)) {
 		for (i = 0; i < mt_slot_count(mas->node); i++) {
@@ -1072,57 +1079,69 @@ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas)
 		}
 		if (gap > max_gap)
 			max_gap = gap;
-		goto done;
+		return max_gap;
 	}
 
-	pstart = mas->min;
-	for (i = 0; i < mt_slots[mt]; i++) {
-		pend = _mas_safe_pivot(mas, pivots, i, mt);
-		if (!pend && i)
-			pend = mas->max;
+       pstart = mas->min;
+       for (i = 0; i < mt_slots[mt]; i++) {
+               pend = mas_logical_pivot(mas, pivots, i, mt);
 
-		if (mas_slot_protected(mas, slots, i))
-			goto next;
+               if (slots[i])
+                       goto next;
 
-		gap = pend - pstart + 1;
-		if (gap > max_gap)
-			max_gap = gap;
+               gap = pend - pstart + 1;
+               if (gap > max_gap)
+                       max_gap = gap;
 
 next:
-		if (pend >= mas->max)
-			break;
-
-		pstart = pend + 1;
-	}
-done:
-	return max_gap;
-
-}
+               if (pend >= mas->max)
+                       break;
+               pstart = pend + 1;
+       }
+        return max_gap;
+ }
 
 /*
  * mas_max_gap() - find the largest gap in a non-leaf node and set the slot.
  */
 static inline unsigned long mas_max_gap(struct ma_state *mas)
 {
-	enum maple_type mt = mte_node_type(mas->node);
-	unsigned long *gaps = ma_gaps(mas_mn(mas), mt);
-	unsigned long *pivots = ma_pivots(mas_mn(mas), mt);
-	unsigned long max_gap = 0;
+	unsigned long *gaps, *pivots;
+	unsigned long max_gap;
+	enum maple_type mt;
 	unsigned char i;
 
-	for (i = 0; i < mt_slots[mt]; i++) {
-		unsigned long gap;
-
-		gap = gaps[i];
-		if (gap >  max_gap)
-			max_gap = gap;
+	mt = mte_node_type(mas->node);
+	gaps = ma_gaps(mas_mn(mas), mt);
+	pivots = ma_pivots(mas_mn(mas), mt);
+	i = mt_slots[mt] - 1;
+	max_gap = gaps[i--];
+	do {
+		if (!pivots[i])
+			continue;
 
-		if (i < mt_pivots[mt] && !pivots[i])
-			break;
-	}
+		if (gaps[i] > max_gap)
+			max_gap = gaps[i];
+	} while(i--);
 
 	return max_gap;
 }
+static inline unsigned long mas_tree_gap(struct ma_state *mas)
+{
+	struct maple_node *pnode;
+	unsigned long *gaps;
+	enum maple_type mt;
+
+	if (!mte_is_root(mas->node)) {
+
+		pnode = mte_parent(mas->node);
+		mt = mas_parent_enum(mas, mas->node);
+		gaps = ma_gaps(pnode, mt);
+		return gaps[mte_parent_slot(mas->node)];
+
+	}
+	return mas_max_gap(mas);
+}
 
 static inline unsigned long mas_find_gap(struct ma_state *mas)
 {
@@ -1134,7 +1153,7 @@ static inline unsigned long mas_find_gap(struct ma_state *mas)
 static inline void mas_parent_gap(struct ma_state *mas, unsigned char slot,
 		unsigned long new)
 {
-	unsigned long old_max_gap;
+	unsigned long old_max_gap = 0;
 
 	/* Don't mess with mas state, use a new state */
 	MA_STATE(gaps, mas->tree, mas->index, mas->last);
@@ -1144,7 +1163,9 @@ ascend:
 	/* Go to the parent node. */
 	gaps.node = mt_mk_node(mte_parent(gaps.node),
 			mas_parent_enum(&gaps, gaps.node));
-	old_max_gap = mas_max_gap(&gaps);
+	//old_max_gap = mas_max_gap(&gaps);
+	if (!mte_is_root(gaps.node))
+		old_max_gap = mas_tree_gap(&gaps);
 	mte_set_gap(gaps.node, slot, new);
 	if (mte_is_root(gaps.node))
 		return;
@@ -1174,11 +1195,7 @@ static inline void mas_update_gap(struct ma_state *mas)
 	if (mte_is_root(mas->node))
 		return;
 
-	if (mte_is_leaf(mas->node))
-		max_gap = mas_leaf_max_gap(mas);
-	else
-		max_gap = mas_max_gap(mas);
-
+	max_gap = mas_find_gap(mas);
 	/* Get the gap reported in the parent */
 	pslot = mte_parent_slot(mas->node);
 	p_gap = ma_gaps(mte_parent(mas->node),
@@ -1336,8 +1353,8 @@ static inline void mab_shift_right(struct maple_big_node *b_node,
 {
 	unsigned long size = b_node->b_end * sizeof(unsigned long);
 
-	memmove(b_node->pivot +shift, b_node->pivot, size);
-	memmove(b_node->slot +shift, b_node->slot, size);
+	memmove(b_node->pivot + shift, b_node->pivot, size);
+	memmove(b_node->slot + shift, b_node->slot, size);
 	memmove(b_node->gap + shift, b_node->gap, size);
 }
 
@@ -1446,24 +1463,28 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start,
 	void **slots = ma_slots(node, mt);
 	unsigned long *pivots = ma_pivots(node, mt);
 	unsigned long *gaps = NULL;
-	int i, j;
-
-	if (!mte_is_leaf(mas->node) && mt_is_alloc(mas->tree))
-		gaps = ma_gaps(node, mt);
+	int i = mas_start, j = mab_start;
 
 	for (i = mas_start, j = mab_start; i <= mas_end; i++, j++) {
-		b_node->slot[j] = mas_slot_protected(mas, slots, i);
 		b_node->pivot[j] = _mas_safe_pivot(mas, pivots, i, mt);
 
-		if (gaps)
-			b_node->gap[j] = gaps[i];
-
 		if ((mas->max == b_node->pivot[j]) ||
 		    (j && !b_node->pivot[j])) {       // end of node.
 			j++;
 			break;
 		}
 	}
+
+	memcpy(b_node->slot + mab_start,
+	       slots + mas_start,
+	       sizeof(void*) * (j - mab_start));
+
+	if (!mte_is_leaf(mas->node) && mt_is_alloc(mas->tree)) {
+		gaps = ma_gaps(node, mt);
+		memcpy(b_node->gap + mab_start,
+		       gaps + mas_start,
+		       sizeof(unsigned long) * (j - mab_start));
+	}
 	b_node->b_end = j;
 }
 
@@ -1485,19 +1506,21 @@ static inline void mab_mas_cp(struct maple_big_node *b_node,
 	unsigned long *pivots = ma_pivots(node, mt);
 	unsigned long *gaps = NULL;
 
-	if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree))
-		gaps = ma_gaps(mas_mn(mas), mt);
-
 	for (i = mab_start; i <= mab_end; i++, j++) {
 		if (j && !b_node->pivot[i])
 			break;
 
-		rcu_assign_pointer(slots[j], b_node->slot[i]);
 		if (j < mt_pivots[mt])
 			pivots[j] = b_node->pivot[i];
+	}
 
-		if (gaps)
-			gaps[j] = b_node->gap[i];
+	memcpy(slots, b_node->slot + mab_start,
+	       sizeof(void*) * (i - mab_start));
+
+	if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) {
+		gaps = ma_gaps(mas_mn(mas), mt);
+		memcpy(gaps, b_node->gap + mab_start,
+		       sizeof(unsigned long) * (i - mab_start));
 	}
 	mas->max = b_node->pivot[--i];
 }
@@ -2191,8 +2214,8 @@ static inline void mast_setup_bnode_for_split(struct maple_subtree_state *mast)
  * Returns the number of elements in b_node during the last loop.
  */
 static inline int mas_spanning_rebalance(struct ma_state *mas,
-					    struct maple_subtree_state *mast,
-					    unsigned char count)
+					 struct maple_subtree_state *mast,
+					 unsigned char count)
 {
 	unsigned char split, mid_split;
 	unsigned char slot = 0;
@@ -2733,7 +2756,7 @@ static inline bool mas_node_walk(struct ma_state *mas, enum maple_type type,
 {
 	unsigned long *pivots = ma_pivots(mas_mn(mas), type);
 	unsigned long min = mas->min, pivot = 0;
-	unsigned char i;
+	unsigned char i = mas_offset(mas);
 	bool ret = true;
 
 	if (ma_is_dense(type)) {
@@ -2744,7 +2767,7 @@ static inline bool mas_node_walk(struct ma_state *mas, enum maple_type type,
 		goto dense;
 	}
 
-	for (i = mas_offset(mas); i < mt_slots[type]; i++) {
+	while(i < mt_slots[type]) {
 		pivot = _mas_safe_pivot(mas, pivots, i, type);
 
 		if (!pivot && i) {
@@ -2760,6 +2783,7 @@ static inline bool mas_node_walk(struct ma_state *mas, enum maple_type type,
 			break;
 
 		min = pivot + 1;
+		i++;
 	}
 
 dense:
@@ -2784,7 +2808,6 @@ bool mas_wr_walk(struct ma_state *mas, unsigned long *range_min,
 		unsigned long *range_max, void *entry)
 {
 	enum maple_type type;
-	bool ret = false;
 
 	mas->span_enode = NULL;
 	mas->depth = 0;
@@ -2807,7 +2830,7 @@ bool mas_wr_walk(struct ma_state *mas, unsigned long *range_min,
 		mas->node = mas_get_slot(mas, mas_offset(mas));
 		mas_set_offset(mas, 0);
 	}
-	return ret;
+	return false;
 }
 
 static inline void mas_extend_null(struct ma_state *l_mas, struct ma_state *r_mas)
@@ -2973,34 +2996,295 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry)
 	return mas_spanning_rebalance(mas, &mast, height + 1);
 }
 
-static inline bool mas_can_append(struct ma_state *mas,
-				  struct maple_big_node *bn,
-				  unsigned char slot_cnt,
-				  unsigned char end)
+#if 0
+static inline bool mas_append(struct ma_state *mas, void **slots,
+			      unsigned long *pivots, unsigned char offset,
+			      unsigned char slot_cnt, void *entry, void *content)
+{
+	/* Offset is where this data will go, aka the old end slot. */
+	unsigned long min = mas_safe_min(mas, pivots, offset);
+	unsigned long max = mas_logical_pivot(mas, pivots, offset,
+					      mte_node_type(mas->node));
+
+	mt_dump(mas->tree);
+	printk("%s Insert %lu-%lu\n", __func__, mas->index, mas->last);
+	printk("slot %u is %lu-%lu\n", offset, min, max);
+	printk("slot_cnt %u\n", slot_cnt);
+	if (max != mas->last) {
+		slots[slot_cnt] = content;
+		printk("Set slot %u to contents of slot %u\n", slot_cnt, offset);
+		pivots[slot_cnt] = pivots[offset];
+		slot_cnt--;
+	}
+
+	printk("Set slot %u to new value\n", slot_cnt);
+	slots[slot_cnt] = entry;
+	pivots[slot_cnt] = mas->last;
+
+	if (min != mas->index)
+		pivots[offset] = mas->index - 1;
+
+	mas_update_gap(mas);
+	return true;
+}
+
+static inline void
+mas_truncate(struct ma_state *mas, void **slots, unsigned long *pivots,
+	     unsigned char offset, char shift, void *entry, unsigned char end)
+{
+	enum maple_type mt = mte_node_type(mas->node);
+	unsigned char size;
+	unsigned long r_min;
+	int src;
+
+	mt_dump(mas->tree);
+	printk("%s Insert %lu-%lu\n", __func__, mas->index, mas->last);
+
+	r_min = mas_safe_min(mas, pivots, offset);
+	if (r_min != mas->index)
+		pivots[offset++] = mas->index - 1;
+
+	slots[offset] = entry;
+	pivots[offset] = mas->last;
+
+	if (offset > shift + end)
+		return;
+
+	// Now we are at offset, we have to skip -shift amount.
+	printk("src = %u - %d\n", offset, shift);
+	src = offset - shift;
+	size = end - offset;
+	printk("Insert cp offset %u => src %u size %u\n", offset, src, size);
+	memmove(pivots + offset, pivots + src, sizeof(unsigned long) * size);
+	memset(pivots+src+1, 0, sizeof(unsigned long) * (mt_slots[mt] - src));
+	memmove(slots + offset, slots + src, sizeof(void *) * size);
+	memset(slots + src + 1, 0, sizeof(void *) * (mt_slots[mt] - src));
+}
+
+static inline void
+mas_expand(struct ma_state *mas, void **slots, unsigned long *pivots,
+	   unsigned char offset, char shift, void *entry, unsigned char end)
 {
-	if (bn->b_end >= slot_cnt)
-		return false; // no room.
+	enum maple_type mt = mte_node_type(mas->node);
+	unsigned char size = end + shift - offset;
+	unsigned long r_min, r_max;
+	int dst = offset + shift;
+	int src = offset;
+	mt_dump(mas->tree);
+	printk("%s Insert %lu-%lu\n", __func__, mas->index, mas->last);
+	printk("dst is %u + %u\n", offset, shift);
 
-	if (bn->b_end <= end)
-		return false; // truncated data.
+	r_max = mas_logical_pivot(mas, pivots, offset, mt);
+	if (r_max > mas->last)
+		src += 1;
 
-	if (!mas->last)
-		return false; // zero cannot be an append.
+	printk("Expand: dst %u src %u size %u\n", dst, src, size);
+	printk("Expand: shift %u src %u size %u\n", shift, src, size);
+	printk("r_max = %lu\n", r_max);
 
-	if (bn->pivot[bn->b_end] == mas->last)
-		return true; // last entry is the insert.
+	memmove(pivots + dst, pivots + src,
+		sizeof(unsigned long) * min(size, (unsigned char)(mt_pivots[mt] - 1)));
+	memmove(slots + dst, slots + src, sizeof(void *) * size);
 
-	if ((bn->pivot[bn->b_end - 1] == mas->last) && !bn->slot[bn->b_end])
-		return true; // inserting second last entry and last is NULL.
+	r_min = mas_safe_min(mas, pivots, offset);
+	if (r_min != mas->index)
+		pivots[offset++] = mas->index - 1;
+
+	slots[offset] = entry;
+	pivots[offset] = mas->last;
+}
+
+static inline bool _mas_med_path(struct ma_state *mas, void *entry,
+				   unsigned char end, void *content)
+{
+	enum maple_type mt = mte_node_type(mas->node);
+	struct maple_node *node = mte_to_node(mas->node);
+	unsigned char offset = mas_offset(mas); //may have changed on extend null.
+	unsigned char slot_max = mt_slots[mt];
+	unsigned char slot_cnt, new_end;
+	char shift;
+	unsigned long r_min, r_max, *pivots = ma_pivots(node, mt);
+	void **slots = ma_slots(node, mt);
+
+	if (end < mt_pivots[mt] - 1 && pivots[end] < mas->max)
+		end++;
+
+	slot_cnt = end;
+
+	if (offset >= slot_max)
+		offset = end;
+
+	/* Cannot use mas_safe_min due to piv + 1 below */
+	r_min = mas->min - 1;
+	if (offset)
+		r_min = pivots[offset - 1];
+
+	if (r_min + 1 < mas->index) // insert starts later than this range.
+		slot_cnt++;
+
+	r_min++;
+	r_max = mas_logical_pivot(mas, pivots, offset, mt);
+	if (r_max > mas->last) { // insert ends before this range.
+		slot_cnt++;
+	} else if (r_max < mas->last) { // insert overwrites a range of data.
+		unsigned char overwrite = offset;
+		unsigned long npiv;
+
+		do {
+			npiv = mas_logical_pivot(mas, pivots, ++overwrite, mt);
+		} while (npiv < mas->last);
+
+		if (npiv > mas->last)
+			overwrite--;
+
+		slot_cnt -= (overwrite - offset);
+	}
+	if (slot_cnt >= slot_max) // not enough room for new data.
+		return false;
+
+	if (slot_cnt < mt_min_slots[mt]) // Not enough data for a node.
+		return false;
+
+	// Can use fast path.
+	new_end = slot_cnt;
+	// copy data further out on shift right.
+	if (slot_cnt > end)
+		return false;
+		//mas_shift_right(mas, offset, slot_cnt, end);
+
+	if (r_max > mas->last) {
+
+	}
+
+
+	if (new_end < end) { // Zero new_end -> end.
+		if (end == mt_pivots[mt])
+			slots[end--] = NULL;
+
+		while(end > new_end) {
+			slots[end] = NULL;
+			pivots[end--] = 0;
+		}
+	}
+
+
+
+
+#if 0
+	printk("\n");
+	shift = slot_cnt - end;
+	printk("end is %u slot_cnt is %u shift %d\n", end, slot_cnt, shift);
+	// Check if this is an append operation.
+	if (offset == end)
+		return mas_append(mas, slots, pivots, offset, slot_cnt, entry, content);
+	if (shift < 0)
+		mas_truncate(mas, slots, pivots, offset, shift, entry, end);
+	if (shift >= 0)
+		mas_expand(mas, slots, pivots, offset, shift, entry, end);
+#endif
+	mas_update_gap(mas);
+	return true;
+}
+static inline bool mas_medium_store(struct ma_state *mas, void *entry,
+				unsigned long min, unsigned char end,
+				void *content)
+{
+	enum maple_type mt = mte_node_type(mas->node);
+	struct maple_node *node = mte_to_node(mas->node);
+	void **slots = ma_slots(node, mt);
+	unsigned long *pivots = ma_pivots(node, mt);
+	struct maple_node new_node;
+	void **nslots = ma_slots(&new_node, mt);
+	unsigned long *npivots = ma_pivots(&new_node, mt);
+	unsigned char offset = mas_offset(mas); //may have changed on extend null.
+	unsigned char size, noffset = offset;
+
+	memset(&new_node, 0, sizeof(struct maple_node));
+	if (offset) {
+		memcpy(nslots, slots, sizeof(void*) * offset);
+		memcpy(npivots, pivots, sizeof(unsigned long) * offset);
+
+	}
+
+	if (min != mas->index)
+		noffset++;
+
+	nslots[noffset] = entry;
+	npivots[noffset++] = mas->last;
+
+	if (mas->last < pivots[offset]) {
+		nslots[noffset] = content;
+		npivots[noffset++] = pivots[offset];
+	}
+
+	while (offset < mt_slots[mt] && pivots[offset] <= mas->last) {
+		offset++;
+	}
+
+	size = mt_slots[mt] - 1 - offset;
+	memcpy(nslots + noffset, slots + offset, sizeof(void*) * size);
+	size = min(size, (unsigned char) (mt_pivots[mt] - 1));
+	memcpy(npivots + noffset, pivots + offset, sizeof(unsigned long) * size);
+	memcpy(node, &new_node, sizeof(struct maple_node));
+	return true;
+}
+
+#endif
+static inline bool mas_fast_store(struct ma_state *mas, void *entry,
+				  unsigned long min, unsigned long max,
+				  unsigned char end, void *content)
+{
+	enum maple_type mt = mte_node_type(mas->node);
+	struct maple_node *node = mte_to_node(mas->node);
+	void **slots = ma_slots(node, mt);
+	unsigned long *pivots = ma_pivots(node, mt);
+	unsigned char offset = mas_offset(mas); //may have changed on extend null.
+
+	if (min == mas->index && max == mas->last) { // exact fit.
+		slots[offset] = entry;
+		goto done;
+	}
+
+	if (offset + 1 >= mt_slots[mt]) // out of room.
+		return false;
+
+	if (max > mas->last) // going to split a single entry.
+		return false;
+
+	max = mas_logical_pivot(mas, pivots, offset + 1, mt);
+	if (max < mas->last) // going to overwrite too many slots.
+		return false;
+
+	if (min == mas->index) {
+		if (max <= mas->last) // overwriting two slots with one.
+			return false;
+
+		slots[offset] = entry;
+		pivots[offset] = mas->last;
+		goto done;
+	} else if (min < mas->index) {
+		if (max != mas->last)
+			return false;
+
+		if (offset + 1 < mt_pivots[mt])
+			pivots[offset + 1] = mas->last;
+		slots[offset + 1] = entry;
+		pivots[offset] = mas->index - 1;
+		goto done;
+	}
 
 	return false;
+
+
+done:
+	mas_update_gap(mas);
+	return true;
 }
 
 static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite)
 {
 	unsigned long r_max, r_min;
 	unsigned char end, offset;
-	unsigned char slot_cnt;
 	void *content = NULL;
 	struct maple_big_node b_node;
 
@@ -3039,23 +3323,15 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite
 		mas_extend_null(mas, mas);
 
 	end = mas_data_end(mas);
+	if (mas_fast_store(mas, entry, r_min, r_max, end, content))
+		return content;
+
+	/* Slow path. */
 	memset(&b_node, 0, sizeof(struct maple_big_node));
 	b_node.type = mte_node_type(mas->node);
 	b_node.b_end = mas_store_b_node(mas, &b_node, entry, end);
 	b_node.min = mas->min;
 
-	// Check if this is an append operation.
-	slot_cnt = mt_slot_count(mas->node);
-	if (mas_can_append(mas, &b_node, slot_cnt, end)) {
-		offset = b_node.b_end;
-		do {
-			mte_set_slot(mas->node, offset, b_node.slot[offset]);
-			if (offset < slot_cnt - 1)
-				mte_set_pivot(mas->node, offset, b_node.pivot[offset]);
-		} while(offset && offset-- >= end);
-		mas_update_gap(mas);
-		goto append;
-	}
 
 	if (!mas_commit_b_node(mas, &b_node, end))
 		return NULL;
@@ -3063,7 +3339,6 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite
 complete_at_root:
 	if (ret > 2)
 		return NULL;
-append:
 spanning_store:
 	return content;
 }
@@ -4898,6 +5173,7 @@ void mas_validate_gaps(struct ma_state *mas)
 	unsigned long p_end, p_start = mas->min;
 	unsigned char p_slot;
 	unsigned long *gaps = NULL;
+	unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte));
 	int i;
 
 	if (ma_is_dense(mte_node_type(mte))) {
@@ -4918,9 +5194,7 @@ void mas_validate_gaps(struct ma_state *mas)
 
 
 	for (i = 0; i < mt_slot_count(mte); i++) {
-		p_end = mas_safe_pivot(mas, i);
-		if (!p_end && i)
-			p_end = mas->max;
+		p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte));
 
 		if (!gaps) {
 			if (mas_get_slot(mas, i)) {
@@ -5051,8 +5325,8 @@ void mas_validate_limits(struct ma_state *mas)
 {
 	int i;
 	unsigned long prev_piv = 0;
-	void **slots = ma_get_slots(mte_to_node(mas->node),
-				    mte_node_type(mas->node));
+	void **slots = ma_slots(mte_to_node(mas->node),
+				mte_node_type(mas->node));
 
 	if (mte_is_root(mas->node))
 		return; // all limits are fine here.
diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index ae13a3c4aae4..c83017e2ca3b 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -87,7 +87,8 @@ static noinline void check_load(struct maple_tree *mt, unsigned long index,
 				void *ptr)
 {
 	void *ret = mtree_test_load(mt, index);
-//	printk("Load %lu returned %p expect %p\n", index, ret, ptr);
+	if (ret != ptr)
+		printk("Load %lu returned %p expect %p\n", index, ret, ptr);
 	MT_BUG_ON(mt, ret != ptr);
 }
 
@@ -331,10 +332,10 @@ static noinline void check_rev_seq(struct maple_tree *mt, unsigned long max,
 			check_index_load(mt, j);
 
 		check_load(mt, i - 1, NULL);
-	mt_set_in_rcu(mt);
-	MT_BUG_ON(mt, !mt_height(mt));
-	mt_clear_in_rcu(mt);
-	MT_BUG_ON(mt, !mt_height(mt));
+		mt_set_in_rcu(mt);
+		MT_BUG_ON(mt, !mt_height(mt));
+		mt_clear_in_rcu(mt);
+		MT_BUG_ON(mt, !mt_height(mt));
 		i--;
 	}
 	check_load(mt, max + 1, NULL);
@@ -775,8 +776,11 @@ static noinline void check_erase_testset(struct maple_tree *mt)
 	check_load(mt, 999, NULL);
 	check_load(mt, 1001, NULL);
 	erase_check_load(mt, 4);
-	// Should be a new node.
-	MT_BUG_ON(mt, root_node == mt->ma_root);
+	if (mt_in_rcu(mt))
+		MT_BUG_ON(mt, root_node == mt->ma_root);
+	else
+		MT_BUG_ON(mt, root_node != mt->ma_root);
+
 	// Should not have split.
 	MT_BUG_ON(mt, !mte_is_leaf(mt->ma_root));
 
@@ -32378,7 +32382,7 @@ static noinline void check_node_overwrite(struct maple_tree *mt)
 	}
 
 	mtree_test_store_range(mt, 319951, 367950, NULL);
-	mt_dump(mt);
+	//mt_dump(mt);
 	mt_validate(mt);
 }
 
@@ -32394,6 +32398,7 @@ static void check_dfs_preorder(struct maple_tree *mt)
 		mas_dfs_preorder(&mas);
 	} while(!mas_is_none(&mas));
 	// 68 + MAS_START = 69
+	printk("count %u\n", count);
 	MT_BUG_ON(mt, count != 69);
 	mtree_destroy(mt);
 
@@ -32405,6 +32410,7 @@ static void check_dfs_preorder(struct maple_tree *mt)
 		count++;
 		mas_dfs_preorder(&mas);
 	} while(!mas_is_none(&mas));
+	printk("count %u\n", count);
 	// 71 + MAS_START = 72
 	MT_BUG_ON(mt, count != 72);
 	mtree_destroy(mt);
@@ -32418,6 +32424,7 @@ static void check_dfs_preorder(struct maple_tree *mt)
 		mas_dfs_preorder(&mas);
 	} while(!mas_is_none(&mas));
 	// 71 + MAS_START = 72
+	printk("count %u\n", count);
 	MT_BUG_ON(mt, count != 72);
 }
 
@@ -32478,6 +32485,28 @@ static void check_dup_tree(struct maple_tree *oldmt)
 	mtree_destroy(&mt);
 }
 
+static void jitters(struct maple_tree *mt)
+{
+	unsigned long i, max = 300;
+
+	for (i = max; i > 0; i--) {
+		mtree_test_store_range(mt, i*10, i*10 + 9, xa_mk_value(i*10));
+	}
+
+	i = 272;
+	mtree_test_store_range(mt, i*10 + 4, i*10 + 9, NULL);
+	i = 274;
+	mtree_test_store_range(mt, i*10, i*10 + 9, NULL);
+	i = 273;
+	max = 10000000;
+	while(max--) {
+		mtree_test_store_range(mt, i*10, i*10 + 12, xa_mk_value(i*10));
+		mtree_test_store_range(mt, i*10+10, i*10 + 12, NULL);
+	}
+	return;
+}
+
+
 static DEFINE_MTREE(tree);
 
 static int maple_tree_seed(void)
@@ -32488,6 +32517,15 @@ static int maple_tree_seed(void)
 	void *ptr = &set;
 
 	pr_info("\nTEST STARTING\n\n");
+//	goto skip1;
+#if 1
+	mtree_init(&tree, MAPLE_ALLOC_RANGE);
+	jitters(&tree);
+	mtree_destroy(&tree);
+
+
+	goto skip;
+#endif
 
 	mtree_init(&tree, 0);
 	check_new_node(&tree);
@@ -32506,6 +32544,7 @@ static int maple_tree_seed(void)
 	check_ranges(&tree);
 	mtree_destroy(&tree);
 
+skip1:
 	mtree_init(&tree, MAPLE_ALLOC_RANGE);
 	check_alloc_range(&tree);
 	mtree_destroy(&tree);
@@ -32569,9 +32608,11 @@ static int maple_tree_seed(void)
 	/* Clear out the tree */
 	mtree_destroy(&tree);
 
+//skip:
 	mtree_init(&tree, 0);
 	check_erase_testset(&tree);
 	mtree_destroy(&tree);
+//	exit(0);
 
 	mtree_init(&tree, 0);
 /*
@@ -32663,6 +32704,7 @@ static int maple_tree_seed(void)
 	check_node_overwrite(&tree);
 	mtree_destroy(&tree);
 
+skip:
 	rcu_barrier();
 	pr_info("maple_tree: %u of %u tests passed\n", maple_tree_tests_passed,
 			maple_tree_tests_run);
-- 
2.50.1