diff options
Diffstat (limited to 'drivers/md/persistent-data/dm-btree-remove.c')
-rw-r--r-- | drivers/md/persistent-data/dm-btree-remove.c | 92 |
1 files changed, 27 insertions, 65 deletions
diff --git a/drivers/md/persistent-data/dm-btree-remove.c b/drivers/md/persistent-data/dm-btree-remove.c index 9836c0ae897c..21ea537bd55e 100644 --- a/drivers/md/persistent-data/dm-btree-remove.c +++ b/drivers/md/persistent-data/dm-btree-remove.c @@ -165,9 +165,9 @@ static int init_child(struct dm_btree_info *info, struct dm_btree_value_type *vt return 0; } -static int exit_child(struct dm_btree_info *info, struct child *c) +static void exit_child(struct dm_btree_info *info, struct child *c) { - return dm_tm_unlock(info->tm, c->block); + dm_tm_unlock(info->tm, c->block); } static void shift(struct btree_node *left, struct btree_node *right, int count) @@ -249,13 +249,10 @@ static int rebalance2(struct shadow_spine *s, struct dm_btree_info *info, __rebalance2(info, parent, &left, &right); - r = exit_child(info, &left); - if (r) { - exit_child(info, &right); - return r; - } + exit_child(info, &left); + exit_child(info, &right); - return exit_child(info, &right); + return 0; } /* @@ -301,11 +298,16 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent, { int s; uint32_t max_entries = le32_to_cpu(left->header.max_entries); - unsigned target = (nr_left + nr_center + nr_right) / 3; - BUG_ON(target > max_entries); + unsigned total = nr_left + nr_center + nr_right; + unsigned target_right = total / 3; + unsigned remainder = (target_right * 3) != total; + unsigned target_left = target_right + remainder; + + BUG_ON(target_left > max_entries); + BUG_ON(target_right > max_entries); if (nr_left < nr_right) { - s = nr_left - target; + s = nr_left - target_left; if (s < 0 && nr_center < -s) { /* not enough in central node */ @@ -316,10 +318,10 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent, } else shift(left, center, s); - shift(center, right, target - nr_right); + shift(center, right, target_right - nr_right); } else { - s = target - nr_right; + s = target_right - nr_right; if (s > 0 && nr_center < s) { /* not enough in central node */ shift(center, right, nr_center); @@ -329,7 +331,7 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent, } else shift(center, right, s); - shift(left, center, nr_left - target); + shift(left, center, nr_left - target_left); } *key_ptr(parent, c->index) = center->keys[0]; @@ -389,49 +391,18 @@ static int rebalance3(struct shadow_spine *s, struct dm_btree_info *info, __rebalance3(info, parent, &left, ¢er, &right); - r = exit_child(info, &left); - if (r) { - exit_child(info, ¢er); - exit_child(info, &right); - return r; - } - - r = exit_child(info, ¢er); - if (r) { - exit_child(info, &right); - return r; - } - - r = exit_child(info, &right); - if (r) - return r; + exit_child(info, &left); + exit_child(info, ¢er); + exit_child(info, &right); return 0; } -static int get_nr_entries(struct dm_transaction_manager *tm, - dm_block_t b, uint32_t *result) -{ - int r; - struct dm_block *block; - struct btree_node *n; - - r = dm_tm_read_lock(tm, b, &btree_node_validator, &block); - if (r) - return r; - - n = dm_block_data(block); - *result = le32_to_cpu(n->header.nr_entries); - - return dm_tm_unlock(tm, block); -} - static int rebalance_children(struct shadow_spine *s, struct dm_btree_info *info, struct dm_btree_value_type *vt, uint64_t key) { int i, r, has_left_sibling, has_right_sibling; - uint32_t child_entries; struct btree_node *n; n = dm_block_data(shadow_current(s)); @@ -446,9 +417,7 @@ static int rebalance_children(struct shadow_spine *s, memcpy(n, dm_block_data(child), dm_bm_block_size(dm_tm_get_bm(info->tm))); - r = dm_tm_unlock(info->tm, child); - if (r) - return r; + dm_tm_unlock(info->tm, child); dm_tm_dec(info->tm, dm_block_location(child)); return 0; @@ -458,10 +427,6 @@ static int rebalance_children(struct shadow_spine *s, if (i < 0) return -ENODATA; - r = get_nr_entries(info->tm, value64(n, i), &child_entries); - if (r) - return r; - has_left_sibling = i > 0; has_right_sibling = i < (le32_to_cpu(n->header.nr_entries) - 1); @@ -544,14 +509,6 @@ static int remove_raw(struct shadow_spine *s, struct dm_btree_info *info, return r; } -static struct dm_btree_value_type le64_type = { - .context = NULL, - .size = sizeof(__le64), - .inc = NULL, - .dec = NULL, - .equal = NULL -}; - int dm_btree_remove(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, dm_block_t *new_root) { @@ -559,12 +516,14 @@ int dm_btree_remove(struct dm_btree_info *info, dm_block_t root, int index = 0, r = 0; struct shadow_spine spine; struct btree_node *n; + struct dm_btree_value_type le64_vt; + init_le64_type(info->tm, &le64_vt); init_shadow_spine(&spine, info); for (level = 0; level < info->levels; level++) { r = remove_raw(&spine, info, (level == last_level ? - &info->value_type : &le64_type), + &info->value_type : &le64_vt), root, keys[level], (unsigned *)&index); if (r < 0) break; @@ -654,11 +613,13 @@ static int remove_one(struct dm_btree_info *info, dm_block_t root, int index = 0, r = 0; struct shadow_spine spine; struct btree_node *n; + struct dm_btree_value_type le64_vt; uint64_t k; + init_le64_type(info->tm, &le64_vt); init_shadow_spine(&spine, info); for (level = 0; level < last_level; level++) { - r = remove_raw(&spine, info, &le64_type, + r = remove_raw(&spine, info, &le64_vt, root, keys[level], (unsigned *) &index); if (r < 0) goto out; @@ -689,6 +650,7 @@ static int remove_one(struct dm_btree_info *info, dm_block_t root, value_ptr(n, index)); delete_at(n, index); + keys[last_level] = k + 1ull; } else r = -ENODATA; |