diff options
author | Joe Thornber <ejt@redhat.com> | 2015-10-21 13:36:49 -0400 |
---|---|---|
committer | Mike Snitzer <snitzer@redhat.com> | 2015-10-23 14:02:55 -0400 |
commit | 2871c69e025e8bc507651d5a9cf81a8a7da9d24b (patch) | |
tree | e1101ed40df4065187db2cde572f449ff708bb67 | |
parent | ba30670f4d5292c4e7f7980bbd5071f7c4794cdd (diff) |
dm btree remove: fix a bug when rebalancing nodes after removal
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
-rw-r--r-- | drivers/md/persistent-data/dm-btree-remove.c | 17 |
1 files changed, 11 insertions, 6 deletions
diff --git a/drivers/md/persistent-data/dm-btree-remove.c b/drivers/md/persistent-data/dm-btree-remove.c index 421a36c593e3..2e4c4cb79e4d 100644 --- a/drivers/md/persistent-data/dm-btree-remove.c +++ b/drivers/md/persistent-data/dm-btree-remove.c | |||
@@ -301,11 +301,16 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent, | |||
301 | { | 301 | { |
302 | int s; | 302 | int s; |
303 | uint32_t max_entries = le32_to_cpu(left->header.max_entries); | 303 | uint32_t max_entries = le32_to_cpu(left->header.max_entries); |
304 | unsigned target = (nr_left + nr_center + nr_right) / 3; | 304 | unsigned total = nr_left + nr_center + nr_right; |
305 | BUG_ON(target > max_entries); | 305 | unsigned target_right = total / 3; |
306 | unsigned remainder = (target_right * 3) != total; | ||
307 | unsigned target_left = target_right + remainder; | ||
308 | |||
309 | BUG_ON(target_left > max_entries); | ||
310 | BUG_ON(target_right > max_entries); | ||
306 | 311 | ||
307 | if (nr_left < nr_right) { | 312 | if (nr_left < nr_right) { |
308 | s = nr_left - target; | 313 | s = nr_left - target_left; |
309 | 314 | ||
310 | if (s < 0 && nr_center < -s) { | 315 | if (s < 0 && nr_center < -s) { |
311 | /* not enough in central node */ | 316 | /* not enough in central node */ |
@@ -316,10 +321,10 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent, | |||
316 | } else | 321 | } else |
317 | shift(left, center, s); | 322 | shift(left, center, s); |
318 | 323 | ||
319 | shift(center, right, target - nr_right); | 324 | shift(center, right, target_right - nr_right); |
320 | 325 | ||
321 | } else { | 326 | } else { |
322 | s = target - nr_right; | 327 | s = target_right - nr_right; |
323 | if (s > 0 && nr_center < s) { | 328 | if (s > 0 && nr_center < s) { |
324 | /* not enough in central node */ | 329 | /* not enough in central node */ |
325 | shift(center, right, nr_center); | 330 | shift(center, right, nr_center); |
@@ -329,7 +334,7 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent, | |||
329 | } else | 334 | } else |
330 | shift(center, right, s); | 335 | shift(center, right, s); |
331 | 336 | ||
332 | shift(left, center, nr_left - target); | 337 | shift(left, center, nr_left - target_left); |
333 | } | 338 | } |
334 | 339 | ||
335 | *key_ptr(parent, c->index) = center->keys[0]; | 340 | *key_ptr(parent, c->index) = center->keys[0]; |