From e867931cc2ae3e2e8b9a878927479c6bbff8bb5f Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Thu, 16 Jan 2020 10:59:08 -0500
Subject: [PATCH] maple_tree: Fix prev_node, change split balancing during
 inactive.

Also change the real world testcases to use an alloc tree.

Note: set9 fails due to attempt to get 140 nodes allocated.

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 7cb11bb4521c..73e310c0a70f 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -654,6 +654,8 @@ static inline void ma_set_rcu_slot(struct maple_node *mn,
 		RCU_INIT_POINTER(mn->mr64.slot[slot], val);
 		break;
 	case maple_arange_64:
+		if (slot >= 5)
+			BUG();
 		RCU_INIT_POINTER(mn->ma64.slot[slot], val);
 		break;
 	}
@@ -1213,7 +1215,7 @@ static inline void mas_ma_cp_store(struct maple_node *mn,
 }
 
 static inline unsigned char mas_cp_calc_split(struct ma_state *mas,
-		enum maple_type mas_type, bool append)
+		enum maple_type mas_type, bool append, bool active)
 {
 	unsigned char max = 7, ret = 7;
 	unsigned char slot;
@@ -1221,10 +1223,16 @@ static inline unsigned char mas_cp_calc_split(struct ma_state *mas,
 	unsigned long half;
 	unsigned long piv = 0;
 	if (mas_type == maple_arange_64)
-		max = 3;
+		max = 5;
 
-	if (mas->min == 0)
-		max = 7;
+	if (!active) {
+		if (ma_is_leaf(mas_type))
+			return max;
+		return max - 2;
+	}
+
+	//if (mas->min == 0)
+	//	max = 7;
 
 	half = max / 2;
 	if (ma_is_leaf(mas_type)) {
@@ -1248,11 +1256,13 @@ static inline unsigned char mas_cp_calc_split(struct ma_state *mas,
 
 		}
 	} else
+
 	return half;
 
 done:
 	if (ret < max && (append || piv == ULONG_MAX))
 		ret++;
+
 	return ret;
 }
 static inline unsigned long mas_leaf_max_gap(struct ma_state *mas);
@@ -1301,7 +1311,8 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas,
 		unsigned char p_slot, struct ma_state *left,
 		struct ma_state *right, struct maple_node *mn,
 		enum maple_type mn_type, unsigned long mn_min,
-		int entry_cnt, void *entry, unsigned char dst_start)
+		int entry_cnt, void *entry, unsigned char dst_start,
+		bool active)
 {
 	enum maple_type mas_type = mte_node_type(mas->node);
 	struct maple_node *parent = mte_to_node(mas->node);
@@ -1332,9 +1343,8 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas,
 	if (ma_is_leaf(mas_type))
 		attempt_insert = true;
 
-
 	if (right)
-		split = mas_cp_calc_split(mas, mas_type, append);
+		split = mas_cp_calc_split(mas, mas_type, append, active);
 
 	if (left) {
 		mas_dup_state(&cp, left);
@@ -1345,7 +1355,7 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas,
 		mn_type = mte_node_type(cp.node);
 		p_slot = mte_parent_slot(left->node);
 		parent = mte_parent(left->node);
-		mas_type = mas_parent_enum(mas, left->node);
+		mas_type = mas_parent_enum(left, left->node);
 	}
 
 	if (!entry_cnt)
@@ -1402,14 +1412,14 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas,
 
 		if (!appending) {
 			if (mt_will_coalesce(existing)) {
-				if (prev_null) {
+				if (prev_null && piv[2] < cp.index) {
 					if (slot &&
 					    slot - 1 < mt_pivots[mas_type]) {
 						ma_set_pivot(mn, slot - 1,
 							     mas_type, piv[2]);
 						written_piv = piv[2];
 					}
-					if (update_gaps) {
+					if (update_gaps && entry_cnt >= 0) {
 						mas_ma_update_gap(mas, mas_type,
 							mn, mn_type, piv[2],
 							written_piv, src_slot,
@@ -1427,13 +1437,11 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas,
 				goto skip_src_slot;
 		}
 
-		if (ma_is_leaf(mn_type) &&
-		    (append || (attempt_insert && cp.index <= piv[2]))) {
+		if ((append || (attempt_insert && cp.index <= piv[2]))) {
 			i = 0;
 			if (written_piv == cp.index - 1) {
 				i = 1; // previous pivot matches exactly.
-			}
-			else if (!src_slot && written_piv == cp.index)
+			} else if (!src_slot && written_piv == cp.index)
 				i = 1;
 
 			if (appending)
@@ -1501,7 +1509,7 @@ skip_src_slot:
 		src_slot++;
 	} while ((entry_cnt-- > 0) || attempt_insert);
 
-	if (right && update_gaps)
+	if (right && update_gaps && p_slot < mt_slots[mas_type])
 		parent->ma64.gap[p_slot] = max_gap;
 	else if (!right)
 		ret = slot - 1;
@@ -2119,7 +2127,7 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot,
 		mas_dup_state(&parent, mas);
 		mas_ascend(&parent);
 		old_parent = parent.node;
-		ptype = mte_node_type(parent.node);
+		ptype = mas_parent_enum(mas, mas->node);
 		p_end = mas_data_end(&parent, ptype, &last_pivot, &coalesce);
 		if (p_end - coalesce >= mt_slots[ptype] - 1) {
 			/* Must split the parent */
@@ -2130,13 +2138,13 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot,
 				return 0;
 
 			mas_dup_state(&parent, mas);
-			if (split < p_slot)
+			if (split <= p_slot)
 				p_slot -= split;
 			// Split will return the parent.
 			old_parent = parent.node;
 			mas_set_slot(&parent, p_slot);
 		}
-		ptype = mte_node_type(parent.node);
+		ptype = mas_parent_enum(mas, mas->node);
 		p_end = mas_data_end(&parent, ptype, &last_pivot, &coalesce);
 		mas_dup_state(mas, &parent);
 		mas_set_slot(mas, p_slot);
@@ -2155,17 +2163,17 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot,
 	left.node = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), type);
 	right.node  = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), type);
 
-	mte_set_parent(left.node, mte_to_node(new_parent), p_slot);
-	mte_set_parent(right.node, mte_to_node(new_parent), p_slot+1);
+	mte_set_parent(left.node, new_parent, p_slot);
+	mte_set_parent(right.node, new_parent, p_slot+1);
 	// split the data into left & right and do the insert.
 	split = mas_ma_cp(mas, p_slot, &left, &right, NULL, type, 0, entry_cnt,
-			entry, 0);
+			entry, 0, active);
 
 	// Copy the parents information
 	if (!mte_is_root(full)) {
-		MA_CP(cp, old_parent, new_parent, 0, p_slot - 1);
 		unsigned char skip = 1;
 
+		MA_CP(cp, old_parent, new_parent, 0, p_slot - 1);
 
 		// Copy the parent data up to p_slot - 1.
 		if (p_slot)
@@ -2213,8 +2221,8 @@ static inline int mas_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 (!mt_is_alloc(mas->tree)) // FIXME: citation needed.
-		p_slot = slot - p_slot;
+//	if (!mt_is_alloc(mas->tree)) // FIXME: Something to do with leaf size
+//		p_slot = slot - p_slot;
 
 	if (mas->index <= left.max) {
 		mas_dup_state(mas, &left);
@@ -2225,13 +2233,14 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot,
 	}
 
 	// Free the full node, this may have happened in _mas_replace
-	if (old_parent != full) {
+	if (old_parent != full) {  // not root?
 		if (!active)
 			mas_push_node(mas, full);
 		else
 			mte_free(full);
 	}
 
+	//mt_dump(mas->tree);
 	return split;
 }
 
@@ -2394,7 +2403,7 @@ static inline int __mas_add(struct ma_state *mas, void *entry,
 	}
 
 	ret = mas_ma_cp(mas, 0, &cp, NULL, mn, mas_type, mn_min, entry_cnt, entry,
-			append ? entry_cnt : 0);
+			append ? entry_cnt : 0, active);
 
 	mn->parent = mas_mn(mas)->parent;
 	// FIXME: Propagate gaps.
@@ -2481,13 +2490,19 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite,
 	// At this point, the we can perform the add.
 
 	// spans node means we will replace the tree.
-	if (mas->last > mas->max)
+	if (mas->last > mas->max) {
+		//printk("Spans node %p (%lu - %lu) vs %lu - %lu\n", mas_mn(mas),
+		//		mas->min, mas->max, mas->index, mas->last);
 		return mas_replace_tree(mas, entry);
+	}
 
 	if (!mte_is_leaf(mas->node)) {
 		// An allocation failed previously during a rebalance.  There
 		// is no way to know how broken things are, so try to rebuild
 		// the tree.
+		printk("Allocation failed previously\n");
+		printk("%ld-%ld landed at %p[%u]\n", mas->index, mas->last,
+				mas_mn(mas), mas_get_slot(mas));
 		mas_reset(mas);
 		mas_first_node(mas, ULONG_MAX);
 		return mas_replace_tree(mas, entry);
@@ -2504,9 +2519,9 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite,
 	new_end = _mas_add_slot_cnt(mas, slot, min, max) - coalesce;
 	if (new_end > slot_cnt) {
 		mas_split(mas, slot, active, old_end, entry);
-		if (mas_is_err(mas)) {
+		if (mas_is_err(mas))
 			return 0;
-		}
+
 		return old_end - new_end;
 	}
 
@@ -2542,7 +2557,7 @@ static inline void ma_inactive_insert(struct ma_state *mas, void *entry)
 	// Restart search for where to insert.
 	mas->node = MAS_START;
 	mas_start(mas);
-	mas_add(mas, entry, false, false);
+	mas_add(mas, entry, true, false);
 }
 static inline void mas_insert(struct ma_state *mas, void *entry)
 {
@@ -2601,8 +2616,7 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)
 	rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
 }
 
-static inline int mas_safe_slot(struct ma_state *mas, unsigned char *slot,
-		int delta);
+static inline int mas_safe_slot(struct ma_state *mas, int *slot, int delta);
 static inline int mas_dead_node(struct ma_state *mas, unsigned long index);
 
 static inline void mas_next_slot(struct ma_state *mas, unsigned long max)
@@ -2734,7 +2748,7 @@ no_entry:
 static inline void mas_prev_node(struct ma_state *mas, unsigned long limit)
 {
 	int level;
-	unsigned char slot;
+	int slot;
 	unsigned long start_piv;
 
 	slot = mas_get_slot(mas);
@@ -2794,7 +2808,7 @@ restart_prev_node:
 			level--;
 			mas->node = mn;
 			slot = mas_data_end(mas, mte_node_type(mn), &last_pivot,
-					&coalesce);
+					&coalesce) + 1;
 		} while (slot-- > 0);
 
 ascend:
@@ -2823,7 +2837,8 @@ static inline unsigned long mas_next_node(struct ma_state *mas,
 restart_next_node:
 	level = 0;
 	while (1) {
-		unsigned char count, slot;
+		unsigned char count;
+		int slot;
 		struct maple_enode *mn;
 		unsigned long prev_piv;
 
@@ -2835,12 +2850,10 @@ restart_next_node:
 		start_piv = mas_get_safe_pivot(mas, slot);
 		level++;
 		mas_ascend(mas);
+		//printk("Ascend to %p[%u]\n", mas_mn(mas), slot);
 
-		if (!mas_safe_slot(mas, &slot, 1)) {
-			if (mte_is_root(mas->node))
-				goto no_entry;
-			goto restart_next_node;
-		}
+		if (!mas_safe_slot(mas, &slot, 1))
+			goto ascend;
 
 		if (mas_dead_node(mas, start_piv))
 			goto restart_next_node;
@@ -2848,9 +2861,11 @@ restart_next_node:
 		count = mt_slot_count(mas->node);
 
 		prev_piv = mas_get_safe_pivot(mas, slot);
+		//printk("while with %p[%u]\n", mas_mn(mas), slot);
 
 		while (++slot < count) {
 			unsigned long pivot = mas_get_safe_pivot(mas, slot);
+			//printk("Checking %p[%u]\n", mas_mn(mas), slot);
 
 			if (prev_piv > max)
 				goto no_entry;
@@ -2881,9 +2896,11 @@ restart_next_node:
 			count = mt_slot_count(mas->node);
 		}
 
+ascend:
 		if (mte_is_root(mas->node))
 			goto no_entry;
 		mas_set_slot(mas, mte_parent_slot(mas->node));
+		//printk("Set parent slot to %u from %p\n", mas_get_slot(mas), mas_mn(mas));
 	}
 
 no_entry:
@@ -3044,6 +3061,7 @@ retry:
 			goto next_node;
 
 		if (!mte_is_leaf(mas->node) || !mas_get_slot(mas)) {
+			//printk("Get first entry\n");
 			*range_start = mas_first_entry(mas, limit);
 			if (mas_is_none(mas)) {
 				mas->node = last_node;
@@ -3058,9 +3076,11 @@ retry:
 			return NULL;
 
 next_node:
+		//printk("Next node from %p\n", mas_mn(mas));
 		p_slot = mte_parent_slot(mas->node);
 		mas_set_slot(mas, p_slot);
 		mas_next_node(mas, limit);
+		//printk("Next node is %p\n", mas->node);
 		mas_set_slot(mas, 0);
 	}
 
@@ -3091,13 +3111,16 @@ static inline void *_mas_next(struct ma_state *mas, unsigned long limit,
 		return NULL;
 
 	if (!mas->node || mas_is_start(mas)) {// First run.
+		//printk("First run\n");
 		*range_start = 0;
 		mas_start(mas);
+		//printk("start returned %p %p\n", mas->node, mas_mn(mas));
 		entry = mas_range_load(mas, range_start, &range_max);
 	}
 
 	if (entry)
 		return entry;
+	//printk("__mas_next with %p\n", mas_mn(mas));
 
 	return __mas_next(mas, limit, range_start);
 }
@@ -3261,6 +3284,8 @@ static inline int mas_cp_append(struct ma_state *mas, struct ma_state *src,
 	dst.index = src->min;
 	dst.max = src->max;
 	while (slot <= count ) {
+//		printk("\t%s: %p[%u]/%u to %p[%u]\n", __func__, mas_mn(src),
+//			slot, count, mas_mn(&dst), dst_cnt);
 		void *entry = mte_get_rcu_slot(src->node, slot);
 		dst.last = mas_get_safe_pivot(src, slot);
 		if (mt_is_empty(entry) && dst.last != ULONG_MAX)
@@ -3270,9 +3295,9 @@ static inline int mas_cp_append(struct ma_state *mas, struct ma_state *src,
 
 		dst_cnt = mas_ma_cp(src, 0, &dst, NULL, mas_mn(&dst), mas_type,
 				dst.min, slot,
-				entry, dst_cnt);
+				entry, dst_cnt, false);
 next:
-		dst.index = dst.last+1;
+		dst.index = dst.last + 1;
 		slot++;
 	}
 	if (retry) {
@@ -3299,27 +3324,22 @@ static inline bool mas_coalesce(struct ma_state *mas, unsigned char l_end_slot,
 		struct ma_cp *cp)
 {
 	struct maple_node *mn;
-	bool ret = false;
+	bool free_left = false;
 
 	MA_STATE(dst, mas->tree, mas->index, mas->last);
 	// it is possible that all of the right node can be appended to the
-	// left
-	if (total_slots + 1 - l_end_slot < mt_slots[l_type] - l_end_slot) {
-		mas_cp_append(mas, r_mas, p_mas, l_end_slot, r_end_slot, false);
-		mte_set_rcu_slot(p_mas->node, mte_parent_slot(r_mas->node),
-				XA_SKIP_ENTRY);
-		mte_free(r_mas->node);
-		goto done;
-	}
+	// left.
+	if (total_slots + 1 - l_end_slot < mt_slots[l_type] - l_end_slot)
+		goto use_left;
 
-	mas_node_cnt(mas, 1); // Try to allocate.
+	mas_node_cnt(mas, 1); // ensure we have a node, or allocate one.
 	if (mas_is_err(mas)) {
 		// Allocation failed, we could try to append as much
 		// as possible here?
 		return false;
 	}
 
-
+	free_left = true;
 	mn = mas_next_alloc(mas);
 	mas_dup_state(&dst, mas);
 	mn->parent = mas_mn(mas)->parent;
@@ -3330,15 +3350,18 @@ static inline bool mas_coalesce(struct ma_state *mas, unsigned char l_end_slot,
 		l_end_slot++;
 	}
 	mas->node = dst.node;
-	// FIXME: Broken.
-	mas_cp_append(mas, r_mas, p_mas, l_end_slot, r_end_slot, true);
-	ret = true;
-done:
+
+use_left:
+	mas_cp_append(mas, r_mas, p_mas, l_end_slot, r_end_slot, false);
+
 	if (!mte_is_leaf(mas->node))
 		mte_adopt_children(mas->node);
 
 	mte_set_pivot(p_mas->node, mte_parent_slot(mas->node), r_mas->max);
-	return ret;
+	mte_set_rcu_slot(p_mas->node, mte_parent_slot(r_mas->node),
+			XA_SKIP_ENTRY);
+	mte_free(r_mas->node);
+	return free_left;
 }
 
 /** Private
@@ -3464,6 +3487,7 @@ done:
 		mte_adopt_children(mas->node);
 	if (free)
 		mas_replace(mas);
+	//mt_dump(mas->tree);
 	// Check parent for rebalancing.
 	mas_dup_state(mas, &p_mas);
 	goto start;
@@ -3844,7 +3868,7 @@ static inline bool _mas_walk(struct ma_state *mas)
  * Skip any slots that have special values.
  * If the limit of the slot is hit, then return false.
  */
-static inline int mas_safe_slot(struct ma_state *mas, unsigned char *slot,
+static inline int mas_safe_slot(struct ma_state *mas, int *slot,
 		int delta)
 {
 	unsigned char max = mt_slot_count(mas->node);
@@ -3852,7 +3876,14 @@ static inline int mas_safe_slot(struct ma_state *mas, unsigned char *slot,
 	if (0 > delta)
 		limit = 0;
 	while (*slot != limit) {
-		if (!mt_is_empty(mte_get_rcu_slot(mas->node, *slot + delta)))
+		void *entry;
+		//printk("Checking safe slot %d\n", *slot + delta);
+		if (!mas_get_safe_pivot(mas, (*slot) + delta))
+			return false;
+
+		entry = mte_get_rcu_slot(mas->node, (*slot) + delta);
+		//printk("slot type %u %p[%u] has %p\n", mte_node_type(mas->node), mas_mn(mas), *slot + delta, entry);
+		if (!mt_is_empty(entry))
 			return true;
 		*slot += delta;
 	}
@@ -3992,9 +4023,9 @@ static inline int mas_build_replacement(struct ma_state *mas, void *new_entry,
 	struct maple_enode *last = NULL;
 	unsigned long new_index, new_last;
 	unsigned long r_index, r_last;
+	struct maple_tree new_tree = MTREE_INIT(name, mas->tree->ma_flags);
 	void *entry;
 
-	DEFINE_MTREE(new_tree);
 	MA_STATE(new_mas, &new_tree, 0, 0);
 
 
@@ -4002,6 +4033,7 @@ static inline int mas_build_replacement(struct ma_state *mas, void *new_entry,
 		return 0;
 	node_cnt += 3; // Room for an extra split.
 
+	//printk("Getting %ld nodes\n", node_cnt);
 	mas_node_cnt(mas, node_cnt);
 	if (mas_is_err(mas))
 		return 0;
@@ -4021,6 +4053,7 @@ static inline int mas_build_replacement(struct ma_state *mas, void *new_entry,
 	mas_reset(mas);
 	mas->index = 0;
 	mas->last = 0;
+	//printk("Start left\n");
 	mas_for_each(mas, entry, new_index - 1) {
 		new_mas.index = mas->index;
 		new_mas.last = mas_get_safe_pivot(mas, mas_get_slot(mas));
@@ -4028,9 +4061,11 @@ static inline int mas_build_replacement(struct ma_state *mas, void *new_entry,
 			BUG_ON(1);
 		ma_inactive_insert(&new_mas, entry);
 		if (mas_is_err(&new_mas)) {
+			//mt_dump(new_mas.tree);
 			goto error;
 		}
 	}
+	//printk("Done\n");
 
 	// Insert the new value.
 	new_mas.index = new_index;
@@ -4045,12 +4080,12 @@ static inline int mas_build_replacement(struct ma_state *mas, void *new_entry,
 	 * - new_mas.last goes beyond anything right now (no entries)
 	 * - new_mas.last cuts a range
 	 * - new_mas.last ends in a null
-	 * - new_mas.last has a sequentially next value (48)
+	 * - new_mas.last has a sequentially next value
 	 */
 
 	mas_reset(mas);
-	mas->index = new_last+1;
-	mas->last = new_last+1;
+	mas->index = new_last + 1;
+	mas->last = new_last + 1;
 	_mas_range_walk(mas, &r_index, &r_last);
 
 	if (mas_get_slot(mas) == MAPLE_NODE_SLOTS)
@@ -4069,6 +4104,8 @@ static inline int mas_build_replacement(struct ma_state *mas, void *new_entry,
 		}
 	}
 
+	//printk("Start right from %lu\n", mas->index);
+	//mt_dump(new_mas.tree);
 	mas_for_each(mas, entry, ULONG_MAX) {
 		if (mas->index < new_index)
 			continue;
@@ -4079,6 +4116,7 @@ static inline int mas_build_replacement(struct ma_state *mas, void *new_entry,
 		if (mas_is_err(&new_mas))
 			goto error;
 	}
+	//printk("Done\n");
 
 skip_right:
 
@@ -4094,7 +4132,7 @@ skip_right:
 error:
 	if (new_mas.tree)
 		mte_destroy_walk(new_mas.tree->ma_root);
-	printk("Failed on %lu-%lu\n", mas->index, mas->last);
+	//printk("Failed on %lu-%lu\n", mas->index, mas->last);
 	mt_dump(mas->tree);
 	BUG_ON(1);
 	return 0;
@@ -4928,6 +4966,8 @@ void mt_dump_arange64(void *entry, unsigned long min, unsigned long max,
 			mt_dump_entry(node->slot[i], first, last, depth + 1);
 		else if (xa_is_skip(node->slot[i]))
 			mt_dump_entry(node->slot[i], first, last, depth + 1);
+		else if (xa_is_retry(node->slot[i]))
+			mt_dump_entry(node->slot[i], first, last, depth + 1);
 		else if (node->slot[i])
 			mt_dump_node(node->slot[i], first, last, depth + 1);
 
-- 
2.50.1