Patch "dm btree remove: fix a bug when rebalancing nodes after removal" has been added to the 4.2-stable tree

This is a note to let you know that I've just added the patch titled

dm btree remove: fix a bug when rebalancing nodes after removal

to the 4.2-stable tree which can be found at:
http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary

The filename of the patch is:
dm-btree-remove-fix-a-bug-when-rebalancing-nodes-after-removal.patch
and it can be found in the queue-4.2 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree, please let <[email protected]> know about it.

From: Joe Thornber <[email protected]>
Date: Wed, 21 Oct 2015 18:36:49 +0100
Subject: dm btree remove: fix a bug when rebalancing nodes after removal

From: Joe Thornber <[email protected]>

commit 2871c69e025e8bc507651d5a9cf81a8a7da9d24b upstream.

Commit 4c7e309340ff ("dm btree remove: fix bug in redistribute3") wasn't a complete fix for redistribute3().

The redistribute3 function takes 3 btree nodes and shares out the entries evenly between them. If the three nodes in total contained (MAX_ENTRIES * 3) - 1 entries between them then this was erroneously getting rebalanced as (MAX_ENTRIES - 1) on the left and right, and (MAX_ENTRIES + 1) in the center.

Fix this issue by being more careful about calculating the target number of entries for the left and right nodes.

Unit tested in userspace using this program:
https://github.com/jthornber/redistribute3-test/blob/master/redistribute3_t.c

---
 drivers/md/persistent-data/dm-btree-remove.c |   17 +++++++++++------
 1 file changed, 11 insertions(+), 6 deletions(-)

@@ -301,11 +301,16 @@ static void redistribute3(struct dm_btre
 {
 	int s;
 	uint32_t max_entries = le32_to_cpu(left->header.max_entries);
-	unsigned target = (nr_left + nr_center + nr_right) / 3;
-	BUG_ON(target > max_entries);
+	unsigned total = nr_left + nr_center + nr_right;
+	unsigned target_right = total / 3;
+	unsigned remainder = (target_right * 3) != total;
+	unsigned target_left = target_right + remainder;
+
+	BUG_ON(target_left > max_entries);
+	BUG_ON(target_right > max_entries);
 
 	if (nr_left < nr_right) {
-		s = nr_left - target;
+		s = nr_left - target_left;
 
 		if (s < 0 && nr_center < -s) {
 			/* not enough in central node */

@@ -316,10 +321,10 @@ static void redistribute3(struct dm_btre
 		} else
 			shift(left, center, s);
 
-		shift(center, right, target - nr_right);
+		shift(center, right, target_right - nr_right);
 
 	} else {
-		s = target - nr_right;
+		s = target_right - nr_right;
 		if (s > 0 && nr_center < s) {
 			/* not enough in central node */
 			shift(center, right, nr_center);

@@ -329,7 +334,7 @@ static void redistribute3(struct dm_btre
 		} else
 			shift(center, right, s);
 
-		shift(left, center, nr_left - target);
+		shift(left, center, nr_left - target_left);
 	}
 
 	*key_ptr(parent, c->index) = center->keys[0];

Patches currently in stable-queue which might be from [email protected] are

queue-4.2/dm-btree-remove-fix-a-bug-when-rebalancing-nodes-after-removal.patch queue-4.2/dm-cache-the-clean_shutdown-flag-was-not-being-set.patch