https://github.com/torvalds/linux
Revision 2871c69e025e8bc507651d5a9cf81a8a7da9d24b authored by Joe Thornber on 21 October 2015, 17:36:49 UTC, committed by Mike Snitzer on 23 October 2015, 18:02:55 UTC
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>
Cc: stable@vger.kernel.org
1 parent ba30670
History
Tip revision: 2871c69e025e8bc507651d5a9cf81a8a7da9d24b authored by Joe Thornber on 21 October 2015, 17:36:49 UTC
dm btree remove: fix a bug when rebalancing nodes after removal
Tip revision: 2871c69
File Mode Size
Documentation
arch
block
certs
crypto
drivers
firmware
fs
include
init
ipc
kernel
lib
mm
net
samples
scripts
security
sound
tools
usr
virt
.get_maintainer.ignore -rw-r--r-- 31 bytes
.gitignore -rw-r--r-- 1.2 KB
.mailmap -rw-r--r-- 5.3 KB
COPYING -rw-r--r-- 18.3 KB
CREDITS -rw-r--r-- 94.9 KB
Kbuild -rw-r--r-- 2.6 KB
Kconfig -rw-r--r-- 252 bytes
MAINTAINERS -rw-r--r-- 319.7 KB
Makefile -rw-r--r-- 53.2 KB
README -rw-r--r-- 18.2 KB
REPORTING-BUGS -rw-r--r-- 7.3 KB

README

back to top