From 11020754df47e783aa3908c2fbf33318b05b744e Mon Sep 17 00:00:00 2001 From: Joe Thornber Date: Wed, 21 Oct 2015 18:36:49 +0100 Subject: [PATCH] dm btree remove: fix a bug when rebalancing nodes after removal 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 Signed-off-by: Joe Thornber Signed-off-by: Mike Snitzer Signed-off-by: Ben Hutchings --- Reading git-format-patch failed