[PATCH 1/4] maple_tree: current split may result in deficient node

[Wei Yang]

Current split would result in deficient node in rare case.

For example:

	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE)
	for (count = 0; count < 10; count++) {
		mas_set(&mas, count);
		mas_store(&mas, xa_mk_value(count));
	}

	for (count = 20; count < 39; count++) {
		mas_set(&mas, count);
		mas_store(&mas, xa_mk_value(count));
	}

	for (count = 10; count < 12; count++) {
		mas_set(&mas, count);
		mas_store(&mas, xa_mk_value(count));
	}
	mt_validate(mt);

The validation would report deficient node.

The reason is we don't leave enough room for the right node.

The deficient check is (end < mt_min_slot[]), which means a node must
have at least (mt_min_slot[] + 1) number of data. The right node's index
range is [split + 1, b_end], which means the number of data in right
node is (b_end - (split + 1) + 1) = (b_end - split).

Then the check between the number of data and (mt_min_slot[] + 1) is
(b_end - split) > (mt_min_slot[] + 1), which leads to
(b_end - split - 1) > (mt_min_slot[]).

Signed-off-by: Wei Yang <richard.weiyang at gmail.com>
CC: Liam R. Howlett <Liam.Howlett at Oracle.com>
CC: Sidhartha Kumar <sidhartha.kumar at oracle.com>
CC: Lorenzo Stoakes <lorenzo.stoakes at oracle.com>
---
 lib/maple_tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 1205a5208cfe..894dc5e9436e 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1831,7 +1831,7 @@ static inline int mab_no_null_split(struct maple_big_node *b_node,
 		 * still be sufficient, then increment the split on NULL.
 		 */
 		if ((split < slot_count - 1) &&
-		    (b_node->b_end - split) > (mt_min_slots[b_node->type]))
+		    (b_node->b_end - split - 1) > (mt_min_slots[b_node->type]))
 			split++;
 		else
 			split--;
@@ -1896,7 +1896,7 @@ static inline int mab_calc_split(struct ma_state *mas,
 		 */
 		while ((split < slot_count - 1) &&
 		       ((bn->pivot[split] - min) < slot_count - 1) &&
-		       (b_end - split > slot_min))
+		       (b_end - split - 1 > slot_min))
 			split++;
 	}
 
-- 
2.34.1