aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJoe Thornber <ejt@redhat.com>2015-10-21 13:36:49 -0400
committerMike Snitzer <snitzer@redhat.com>2015-10-23 14:02:55 -0400
commit2871c69e025e8bc507651d5a9cf81a8a7da9d24b (patch)
treee1101ed40df4065187db2cde572f449ff708bb67
parentba30670f4d5292c4e7f7980bbd5071f7c4794cdd (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.c17
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];