tree 9dd34ec6f4563b78ac454f3691757dece46c1926
parent 6f94a4c45a6f744383f9f695dde019998db3df55
author Joe Thornber <ejt@redhat.com> 1332956483 +0100
committer Alasdair G Kergon <agk@redhat.com> 1332956483 +0100

dm persistent data: fix btree rebalancing after remove

When we remove an entry from a node we sometimes rebalance with it's
two neighbours.  This wasn't being done correctly; in some cases
entries have to move all the way from the right neighbour to the left
neighbour, or vice versa.  This patch pretty much re-writes the
balancing code to fix it.

This code is barely used currently; only when you delete a thin
device, and then only if you have hundreds of them in the same pool.
Once we have discard support, which removes mappings, this will be used
much more heavily.

Signed-off-by: Joe Thornber <ejt@redhat.com>
Cc: stable@kernel.org
Signed-off-by: Mike Snitzer <snitzer@redhat.com>
Signed-off-by: Alasdair G Kergon <agk@redhat.com>