766 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * Copyright (C) 2011 Red Hat, Inc.4 *5 * This file is released under the GPL.6 */7 8#include "dm-btree.h"9#include "dm-btree-internal.h"10#include "dm-transaction-manager.h"11 12#include <linux/export.h>13#include <linux/device-mapper.h>14 15#define DM_MSG_PREFIX "btree"16 17/*18 * Removing an entry from a btree19 * ==============================20 *21 * A very important constraint for our btree is that no node, except the22 * root, may have fewer than a certain number of entries.23 * (MIN_ENTRIES <= nr_entries <= MAX_ENTRIES).24 *25 * Ensuring this is complicated by the way we want to only ever hold the26 * locks on 2 nodes concurrently, and only change nodes in a top to bottom27 * fashion.28 *29 * Each node may have a left or right sibling. When decending the spine,30 * if a node contains only MIN_ENTRIES then we try and increase this to at31 * least MIN_ENTRIES + 1. We do this in the following ways:32 *33 * [A] No siblings => this can only happen if the node is the root, in which34 * case we copy the childs contents over the root.35 *36 * [B] No left sibling37 * ==> rebalance(node, right sibling)38 *39 * [C] No right sibling40 * ==> rebalance(left sibling, node)41 *42 * [D] Both siblings, total_entries(left, node, right) <= DEL_THRESHOLD43 * ==> delete node adding it's contents to left and right44 *45 * [E] Both siblings, total_entries(left, node, right) > DEL_THRESHOLD46 * ==> rebalance(left, node, right)47 *48 * After these operations it's possible that the our original node no49 * longer contains the desired sub tree. For this reason this rebalancing50 * is performed on the children of the current node. This also avoids51 * having a special case for the root.52 *53 * Once this rebalancing has occurred we can then step into the child node54 * for internal nodes. Or delete the entry for leaf nodes.55 */56 57/*58 * Some little utilities for moving node data around.59 */60static void node_shift(struct btree_node *n, int shift)61{62 uint32_t nr_entries = le32_to_cpu(n->header.nr_entries);63 uint32_t value_size = le32_to_cpu(n->header.value_size);64 65 if (shift < 0) {66 shift = -shift;67 BUG_ON(shift > nr_entries);68 BUG_ON((void *) key_ptr(n, shift) >= value_ptr(n, shift));69 memmove(key_ptr(n, 0),70 key_ptr(n, shift),71 (nr_entries - shift) * sizeof(__le64));72 memmove(value_ptr(n, 0),73 value_ptr(n, shift),74 (nr_entries - shift) * value_size);75 } else {76 BUG_ON(nr_entries + shift > le32_to_cpu(n->header.max_entries));77 memmove(key_ptr(n, shift),78 key_ptr(n, 0),79 nr_entries * sizeof(__le64));80 memmove(value_ptr(n, shift),81 value_ptr(n, 0),82 nr_entries * value_size);83 }84}85 86static int node_copy(struct btree_node *left, struct btree_node *right, int shift)87{88 uint32_t nr_left = le32_to_cpu(left->header.nr_entries);89 uint32_t value_size = le32_to_cpu(left->header.value_size);90 91 if (value_size != le32_to_cpu(right->header.value_size)) {92 DMERR("mismatched value size");93 return -EILSEQ;94 }95 96 if (shift < 0) {97 shift = -shift;98 99 if (nr_left + shift > le32_to_cpu(left->header.max_entries)) {100 DMERR("bad shift");101 return -EINVAL;102 }103 104 memcpy(key_ptr(left, nr_left),105 key_ptr(right, 0),106 shift * sizeof(__le64));107 memcpy(value_ptr(left, nr_left),108 value_ptr(right, 0),109 shift * value_size);110 } else {111 if (shift > le32_to_cpu(right->header.max_entries)) {112 DMERR("bad shift");113 return -EINVAL;114 }115 116 memcpy(key_ptr(right, 0),117 key_ptr(left, nr_left - shift),118 shift * sizeof(__le64));119 memcpy(value_ptr(right, 0),120 value_ptr(left, nr_left - shift),121 shift * value_size);122 }123 return 0;124}125 126/*127 * Delete a specific entry from a leaf node.128 */129static void delete_at(struct btree_node *n, unsigned int index)130{131 unsigned int nr_entries = le32_to_cpu(n->header.nr_entries);132 unsigned int nr_to_copy = nr_entries - (index + 1);133 uint32_t value_size = le32_to_cpu(n->header.value_size);134 135 BUG_ON(index >= nr_entries);136 137 if (nr_to_copy) {138 memmove(key_ptr(n, index),139 key_ptr(n, index + 1),140 nr_to_copy * sizeof(__le64));141 142 memmove(value_ptr(n, index),143 value_ptr(n, index + 1),144 nr_to_copy * value_size);145 }146 147 n->header.nr_entries = cpu_to_le32(nr_entries - 1);148}149 150static unsigned int merge_threshold(struct btree_node *n)151{152 return le32_to_cpu(n->header.max_entries) / 3;153}154 155struct child {156 unsigned int index;157 struct dm_block *block;158 struct btree_node *n;159};160 161static int init_child(struct dm_btree_info *info, struct dm_btree_value_type *vt,162 struct btree_node *parent,163 unsigned int index, struct child *result)164{165 int r, inc;166 dm_block_t root;167 168 result->index = index;169 root = value64(parent, index);170 171 r = dm_tm_shadow_block(info->tm, root, &btree_node_validator,172 &result->block, &inc);173 if (r)174 return r;175 176 result->n = dm_block_data(result->block);177 178 if (inc)179 inc_children(info->tm, result->n, vt);180 181 *((__le64 *) value_ptr(parent, index)) =182 cpu_to_le64(dm_block_location(result->block));183 184 return 0;185}186 187static void exit_child(struct dm_btree_info *info, struct child *c)188{189 dm_tm_unlock(info->tm, c->block);190}191 192static int shift(struct btree_node *left, struct btree_node *right, int count)193{194 int r;195 uint32_t nr_left = le32_to_cpu(left->header.nr_entries);196 uint32_t nr_right = le32_to_cpu(right->header.nr_entries);197 uint32_t max_entries = le32_to_cpu(left->header.max_entries);198 uint32_t r_max_entries = le32_to_cpu(right->header.max_entries);199 200 if (max_entries != r_max_entries) {201 DMERR("node max_entries mismatch");202 return -EILSEQ;203 }204 205 if (nr_left - count > max_entries) {206 DMERR("node shift out of bounds");207 return -EINVAL;208 }209 210 if (nr_right + count > max_entries) {211 DMERR("node shift out of bounds");212 return -EINVAL;213 }214 215 if (!count)216 return 0;217 218 if (count > 0) {219 node_shift(right, count);220 r = node_copy(left, right, count);221 if (r)222 return r;223 } else {224 r = node_copy(left, right, count);225 if (r)226 return r;227 node_shift(right, count);228 }229 230 left->header.nr_entries = cpu_to_le32(nr_left - count);231 right->header.nr_entries = cpu_to_le32(nr_right + count);232 233 return 0;234}235 236static int __rebalance2(struct dm_btree_info *info, struct btree_node *parent,237 struct child *l, struct child *r)238{239 int ret;240 struct btree_node *left = l->n;241 struct btree_node *right = r->n;242 uint32_t nr_left = le32_to_cpu(left->header.nr_entries);243 uint32_t nr_right = le32_to_cpu(right->header.nr_entries);244 /*245 * Ensure the number of entries in each child will be greater246 * than or equal to (max_entries / 3 + 1), so no matter which247 * child is used for removal, the number will still be not248 * less than (max_entries / 3).249 */250 unsigned int threshold = 2 * (merge_threshold(left) + 1);251 252 if (nr_left + nr_right < threshold) {253 /*254 * Merge255 */256 node_copy(left, right, -nr_right);257 left->header.nr_entries = cpu_to_le32(nr_left + nr_right);258 delete_at(parent, r->index);259 260 /*261 * We need to decrement the right block, but not it's262 * children, since they're still referenced by left.263 */264 dm_tm_dec(info->tm, dm_block_location(r->block));265 } else {266 /*267 * Rebalance.268 */269 unsigned int target_left = (nr_left + nr_right) / 2;270 271 ret = shift(left, right, nr_left - target_left);272 if (ret)273 return ret;274 *key_ptr(parent, r->index) = right->keys[0];275 }276 return 0;277}278 279static int rebalance2(struct shadow_spine *s, struct dm_btree_info *info,280 struct dm_btree_value_type *vt, unsigned int left_index)281{282 int r;283 struct btree_node *parent;284 struct child left, right;285 286 parent = dm_block_data(shadow_current(s));287 288 r = init_child(info, vt, parent, left_index, &left);289 if (r)290 return r;291 292 r = init_child(info, vt, parent, left_index + 1, &right);293 if (r) {294 exit_child(info, &left);295 return r;296 }297 298 r = __rebalance2(info, parent, &left, &right);299 300 exit_child(info, &left);301 exit_child(info, &right);302 303 return r;304}305 306/*307 * We dump as many entries from center as possible into left, then the rest308 * in right, then rebalance2. This wastes some cpu, but I want something309 * simple atm.310 */311static int delete_center_node(struct dm_btree_info *info, struct btree_node *parent,312 struct child *l, struct child *c, struct child *r,313 struct btree_node *left, struct btree_node *center, struct btree_node *right,314 uint32_t nr_left, uint32_t nr_center, uint32_t nr_right)315{316 uint32_t max_entries = le32_to_cpu(left->header.max_entries);317 unsigned int shift = min(max_entries - nr_left, nr_center);318 319 if (nr_left + shift > max_entries) {320 DMERR("node shift out of bounds");321 return -EINVAL;322 }323 324 node_copy(left, center, -shift);325 left->header.nr_entries = cpu_to_le32(nr_left + shift);326 327 if (shift != nr_center) {328 shift = nr_center - shift;329 330 if ((nr_right + shift) > max_entries) {331 DMERR("node shift out of bounds");332 return -EINVAL;333 }334 335 node_shift(right, shift);336 node_copy(center, right, shift);337 right->header.nr_entries = cpu_to_le32(nr_right + shift);338 }339 *key_ptr(parent, r->index) = right->keys[0];340 341 delete_at(parent, c->index);342 r->index--;343 344 dm_tm_dec(info->tm, dm_block_location(c->block));345 return __rebalance2(info, parent, l, r);346}347 348/*349 * Redistributes entries among 3 sibling nodes.350 */351static int redistribute3(struct dm_btree_info *info, struct btree_node *parent,352 struct child *l, struct child *c, struct child *r,353 struct btree_node *left, struct btree_node *center, struct btree_node *right,354 uint32_t nr_left, uint32_t nr_center, uint32_t nr_right)355{356 int s, ret;357 uint32_t max_entries = le32_to_cpu(left->header.max_entries);358 unsigned int total = nr_left + nr_center + nr_right;359 unsigned int target_right = total / 3;360 unsigned int remainder = (target_right * 3) != total;361 unsigned int target_left = target_right + remainder;362 363 BUG_ON(target_left > max_entries);364 BUG_ON(target_right > max_entries);365 366 if (nr_left < nr_right) {367 s = nr_left - target_left;368 369 if (s < 0 && nr_center < -s) {370 /* not enough in central node */371 ret = shift(left, center, -nr_center);372 if (ret)373 return ret;374 375 s += nr_center;376 ret = shift(left, right, s);377 if (ret)378 return ret;379 380 nr_right += s;381 } else {382 ret = shift(left, center, s);383 if (ret)384 return ret;385 }386 387 ret = shift(center, right, target_right - nr_right);388 if (ret)389 return ret;390 } else {391 s = target_right - nr_right;392 if (s > 0 && nr_center < s) {393 /* not enough in central node */394 ret = shift(center, right, nr_center);395 if (ret)396 return ret;397 s -= nr_center;398 ret = shift(left, right, s);399 if (ret)400 return ret;401 nr_left -= s;402 } else {403 ret = shift(center, right, s);404 if (ret)405 return ret;406 }407 408 ret = shift(left, center, nr_left - target_left);409 if (ret)410 return ret;411 }412 413 *key_ptr(parent, c->index) = center->keys[0];414 *key_ptr(parent, r->index) = right->keys[0];415 return 0;416}417 418static int __rebalance3(struct dm_btree_info *info, struct btree_node *parent,419 struct child *l, struct child *c, struct child *r)420{421 struct btree_node *left = l->n;422 struct btree_node *center = c->n;423 struct btree_node *right = r->n;424 425 uint32_t nr_left = le32_to_cpu(left->header.nr_entries);426 uint32_t nr_center = le32_to_cpu(center->header.nr_entries);427 uint32_t nr_right = le32_to_cpu(right->header.nr_entries);428 429 unsigned int threshold = merge_threshold(left) * 4 + 1;430 431 if ((left->header.max_entries != center->header.max_entries) ||432 (center->header.max_entries != right->header.max_entries)) {433 DMERR("bad btree metadata, max_entries differ");434 return -EILSEQ;435 }436 437 if ((nr_left + nr_center + nr_right) < threshold) {438 return delete_center_node(info, parent, l, c, r, left, center, right,439 nr_left, nr_center, nr_right);440 }441 442 return redistribute3(info, parent, l, c, r, left, center, right,443 nr_left, nr_center, nr_right);444}445 446static int rebalance3(struct shadow_spine *s, struct dm_btree_info *info,447 struct dm_btree_value_type *vt, unsigned int left_index)448{449 int r;450 struct btree_node *parent = dm_block_data(shadow_current(s));451 struct child left, center, right;452 453 /*454 * FIXME: fill out an array?455 */456 r = init_child(info, vt, parent, left_index, &left);457 if (r)458 return r;459 460 r = init_child(info, vt, parent, left_index + 1, ¢er);461 if (r) {462 exit_child(info, &left);463 return r;464 }465 466 r = init_child(info, vt, parent, left_index + 2, &right);467 if (r) {468 exit_child(info, &left);469 exit_child(info, ¢er);470 return r;471 }472 473 r = __rebalance3(info, parent, &left, ¢er, &right);474 475 exit_child(info, &left);476 exit_child(info, ¢er);477 exit_child(info, &right);478 479 return r;480}481 482static int rebalance_children(struct shadow_spine *s,483 struct dm_btree_info *info,484 struct dm_btree_value_type *vt, uint64_t key)485{486 int i, r, has_left_sibling, has_right_sibling;487 struct btree_node *n;488 489 n = dm_block_data(shadow_current(s));490 491 if (le32_to_cpu(n->header.nr_entries) == 1) {492 struct dm_block *child;493 dm_block_t b = value64(n, 0);494 495 r = dm_tm_read_lock(info->tm, b, &btree_node_validator, &child);496 if (r)497 return r;498 499 memcpy(n, dm_block_data(child),500 dm_bm_block_size(dm_tm_get_bm(info->tm)));501 502 dm_tm_dec(info->tm, dm_block_location(child));503 dm_tm_unlock(info->tm, child);504 return 0;505 }506 507 i = lower_bound(n, key);508 if (i < 0)509 return -ENODATA;510 511 has_left_sibling = i > 0;512 has_right_sibling = i < (le32_to_cpu(n->header.nr_entries) - 1);513 514 if (!has_left_sibling)515 r = rebalance2(s, info, vt, i);516 517 else if (!has_right_sibling)518 r = rebalance2(s, info, vt, i - 1);519 520 else521 r = rebalance3(s, info, vt, i - 1);522 523 return r;524}525 526static int do_leaf(struct btree_node *n, uint64_t key, unsigned int *index)527{528 int i = lower_bound(n, key);529 530 if ((i < 0) ||531 (i >= le32_to_cpu(n->header.nr_entries)) ||532 (le64_to_cpu(n->keys[i]) != key))533 return -ENODATA;534 535 *index = i;536 537 return 0;538}539 540/*541 * Prepares for removal from one level of the hierarchy. The caller must542 * call delete_at() to remove the entry at index.543 */544static int remove_raw(struct shadow_spine *s, struct dm_btree_info *info,545 struct dm_btree_value_type *vt, dm_block_t root,546 uint64_t key, unsigned int *index)547{548 int i = *index, r;549 struct btree_node *n;550 551 for (;;) {552 r = shadow_step(s, root, vt);553 if (r < 0)554 break;555 556 /*557 * We have to patch up the parent node, ugly, but I don't558 * see a way to do this automatically as part of the spine559 * op.560 */561 if (shadow_has_parent(s)) {562 __le64 location = cpu_to_le64(dm_block_location(shadow_current(s)));563 564 memcpy(value_ptr(dm_block_data(shadow_parent(s)), i),565 &location, sizeof(__le64));566 }567 568 n = dm_block_data(shadow_current(s));569 570 if (le32_to_cpu(n->header.flags) & LEAF_NODE)571 return do_leaf(n, key, index);572 573 r = rebalance_children(s, info, vt, key);574 if (r)575 break;576 577 n = dm_block_data(shadow_current(s));578 if (le32_to_cpu(n->header.flags) & LEAF_NODE)579 return do_leaf(n, key, index);580 581 i = lower_bound(n, key);582 583 /*584 * We know the key is present, or else585 * rebalance_children would have returned586 * -ENODATA587 */588 root = value64(n, i);589 }590 591 return r;592}593 594int dm_btree_remove(struct dm_btree_info *info, dm_block_t root,595 uint64_t *keys, dm_block_t *new_root)596{597 unsigned int level, last_level = info->levels - 1;598 int index = 0, r = 0;599 struct shadow_spine spine;600 struct btree_node *n;601 struct dm_btree_value_type le64_vt;602 603 init_le64_type(info->tm, &le64_vt);604 init_shadow_spine(&spine, info);605 for (level = 0; level < info->levels; level++) {606 r = remove_raw(&spine, info,607 (level == last_level ?608 &info->value_type : &le64_vt),609 root, keys[level], (unsigned int *)&index);610 if (r < 0)611 break;612 613 n = dm_block_data(shadow_current(&spine));614 if (level != last_level) {615 root = value64(n, index);616 continue;617 }618 619 BUG_ON(index < 0 || index >= le32_to_cpu(n->header.nr_entries));620 621 if (info->value_type.dec)622 info->value_type.dec(info->value_type.context,623 value_ptr(n, index), 1);624 625 delete_at(n, index);626 }627 628 if (!r)629 *new_root = shadow_root(&spine);630 exit_shadow_spine(&spine);631 632 return r;633}634EXPORT_SYMBOL_GPL(dm_btree_remove);635 636/*----------------------------------------------------------------*/637 638static int remove_nearest(struct shadow_spine *s, struct dm_btree_info *info,639 struct dm_btree_value_type *vt, dm_block_t root,640 uint64_t key, int *index)641{642 int i = *index, r;643 struct btree_node *n;644 645 for (;;) {646 r = shadow_step(s, root, vt);647 if (r < 0)648 break;649 650 /*651 * We have to patch up the parent node, ugly, but I don't652 * see a way to do this automatically as part of the spine653 * op.654 */655 if (shadow_has_parent(s)) {656 __le64 location = cpu_to_le64(dm_block_location(shadow_current(s)));657 658 memcpy(value_ptr(dm_block_data(shadow_parent(s)), i),659 &location, sizeof(__le64));660 }661 662 n = dm_block_data(shadow_current(s));663 664 if (le32_to_cpu(n->header.flags) & LEAF_NODE) {665 *index = lower_bound(n, key);666 return 0;667 }668 669 r = rebalance_children(s, info, vt, key);670 if (r)671 break;672 673 n = dm_block_data(shadow_current(s));674 if (le32_to_cpu(n->header.flags) & LEAF_NODE) {675 *index = lower_bound(n, key);676 return 0;677 }678 679 i = lower_bound(n, key);680 681 /*682 * We know the key is present, or else683 * rebalance_children would have returned684 * -ENODATA685 */686 root = value64(n, i);687 }688 689 return r;690}691 692static int remove_one(struct dm_btree_info *info, dm_block_t root,693 uint64_t *keys, uint64_t end_key,694 dm_block_t *new_root, unsigned int *nr_removed)695{696 unsigned int level, last_level = info->levels - 1;697 int index = 0, r = 0;698 struct shadow_spine spine;699 struct btree_node *n;700 struct dm_btree_value_type le64_vt;701 uint64_t k;702 703 init_le64_type(info->tm, &le64_vt);704 init_shadow_spine(&spine, info);705 for (level = 0; level < last_level; level++) {706 r = remove_raw(&spine, info, &le64_vt,707 root, keys[level], (unsigned int *) &index);708 if (r < 0)709 goto out;710 711 n = dm_block_data(shadow_current(&spine));712 root = value64(n, index);713 }714 715 r = remove_nearest(&spine, info, &info->value_type,716 root, keys[last_level], &index);717 if (r < 0)718 goto out;719 720 n = dm_block_data(shadow_current(&spine));721 722 if (index < 0)723 index = 0;724 725 if (index >= le32_to_cpu(n->header.nr_entries)) {726 r = -ENODATA;727 goto out;728 }729 730 k = le64_to_cpu(n->keys[index]);731 if (k >= keys[last_level] && k < end_key) {732 if (info->value_type.dec)733 info->value_type.dec(info->value_type.context,734 value_ptr(n, index), 1);735 736 delete_at(n, index);737 keys[last_level] = k + 1ull;738 739 } else740 r = -ENODATA;741 742out:743 *new_root = shadow_root(&spine);744 exit_shadow_spine(&spine);745 746 return r;747}748 749int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root,750 uint64_t *first_key, uint64_t end_key,751 dm_block_t *new_root, unsigned int *nr_removed)752{753 int r;754 755 *nr_removed = 0;756 do {757 r = remove_one(info, root, first_key, end_key, &root, nr_removed);758 if (!r)759 (*nr_removed)++;760 } while (!r);761 762 *new_root = root;763 return r == -ENODATA ? 0 : r;764}765EXPORT_SYMBOL_GPL(dm_btree_remove_leaves);766