dm btree remove: fix a bug when rebalancing nodes after removal
authorJoe Thornber <ejt@redhat.com>
Wed, 21 Oct 2015 17:36:49 +0000 (18:36 +0100)
committerGreg Kroah-Hartman <gregkh@linuxfoundation.org>
Mon, 9 Nov 2015 18:12:58 +0000 (10:12 -0800)
commit9d194973fc99e5a5bbc556a4bd0085d3a17ac687
tree0be72df8c436fa6c8349290a9cd9e8d347a708d0
parentd0ecd78fd2f4c324ac2da272b76276bf970ccd51
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 <ejt@redhat.com>
Signed-off-by: Mike Snitzer <snitzer@redhat.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
drivers/md/persistent-data/dm-btree-remove.c