1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 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 btree 19 * ============================== 20 * 21 * A very important constraint for our btree is that no node, except the 22 * 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 the 26 * locks on 2 nodes concurrently, and only change nodes in a top to bottom 27 * 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 at 31 * 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 which 34 * case we copy the children contents over the root. 35 * 36 * [B] No left sibling 37 * ==> rebalance(node, right sibling) 38 * 39 * [C] No right sibling 40 * ==> rebalance(left sibling, node) 41 * 42 * [D] Both siblings, total_entries(left, node, right) <= DEL_THRESHOLD 43 * ==> delete node adding it's contents to left and right 44 * 45 * [E] Both siblings, total_entries(left, node, right) > DEL_THRESHOLD 46 * ==> rebalance(left, node, right) 47 * 48 * After these operations it's possible that the our original node no 49 * longer contains the desired sub tree. For this reason this rebalancing 50 * is performed on the children of the current node. This also avoids 51 * having a special case for the root. 52 * 53 * Once this rebalancing has occurred we can then step into the child node 54 * for internal nodes. Or delete the entry for leaf nodes. 55 */ 56 57 /* 58 * Some little utilities for moving node data around. 59 */ 60 static 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 86 static 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 */ 129 static 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 150 static unsigned int merge_threshold(struct btree_node *n) 151 { 152 return le32_to_cpu(n->header.max_entries) / 3; 153 } 154 155 struct child { 156 unsigned int index; 157 struct dm_block *block; 158 struct btree_node *n; 159 }; 160 161 static 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 187 static void exit_child(struct dm_btree_info *info, struct child *c) 188 { 189 dm_tm_unlock(info->tm, c->block); 190 } 191 192 static 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 236 static 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 greater 246 * than or equal to (max_entries / 3 + 1), so no matter which 247 * child is used for removal, the number will still be not 248 * 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 * Merge 255 */ 256 ret = node_copy(left, right, -nr_right); 257 if (unlikely(ret)) 258 return ret; 259 left->header.nr_entries = cpu_to_le32(nr_left + nr_right); 260 delete_at(parent, r->index); 261 262 /* 263 * We need to decrement the right block, but not it's 264 * children, since they're still referenced by left. 265 */ 266 dm_tm_dec(info->tm, dm_block_location(r->block)); 267 } else { 268 /* 269 * Rebalance. 270 */ 271 unsigned int target_left = (nr_left + nr_right) / 2; 272 273 ret = shift(left, right, nr_left - target_left); 274 if (ret) 275 return ret; 276 *key_ptr(parent, r->index) = right->keys[0]; 277 } 278 return 0; 279 } 280 281 static int rebalance2(struct shadow_spine *s, struct dm_btree_info *info, 282 struct dm_btree_value_type *vt, unsigned int left_index) 283 { 284 int r; 285 struct btree_node *parent; 286 struct child left, right; 287 288 parent = dm_block_data(shadow_current(s)); 289 290 r = init_child(info, vt, parent, left_index, &left); 291 if (r) 292 return r; 293 294 r = init_child(info, vt, parent, left_index + 1, &right); 295 if (r) { 296 exit_child(info, &left); 297 return r; 298 } 299 300 r = __rebalance2(info, parent, &left, &right); 301 302 exit_child(info, &left); 303 exit_child(info, &right); 304 305 return r; 306 } 307 308 /* 309 * We dump as many entries from center as possible into left, then the rest 310 * in right, then rebalance2. This wastes some cpu, but I want something 311 * simple atm. 312 */ 313 static int delete_center_node(struct dm_btree_info *info, struct btree_node *parent, 314 struct child *l, struct child *c, struct child *r, 315 struct btree_node *left, struct btree_node *center, struct btree_node *right, 316 uint32_t nr_left, uint32_t nr_center, uint32_t nr_right) 317 { 318 uint32_t max_entries = le32_to_cpu(left->header.max_entries); 319 unsigned int shift = min(max_entries - nr_left, nr_center); 320 int ret; 321 322 if (nr_left + shift > max_entries) { 323 DMERR("node shift out of bounds"); 324 return -EINVAL; 325 } 326 327 ret = node_copy(left, center, -shift); 328 if (unlikely(ret)) 329 return ret; 330 left->header.nr_entries = cpu_to_le32(nr_left + shift); 331 332 if (shift != nr_center) { 333 shift = nr_center - shift; 334 335 if ((nr_right + shift) > max_entries) { 336 DMERR("node shift out of bounds"); 337 return -EINVAL; 338 } 339 340 node_shift(right, shift); 341 ret = node_copy(center, right, shift); 342 if (unlikely(ret)) 343 return ret; 344 right->header.nr_entries = cpu_to_le32(nr_right + shift); 345 } 346 *key_ptr(parent, r->index) = right->keys[0]; 347 348 delete_at(parent, c->index); 349 r->index--; 350 351 dm_tm_dec(info->tm, dm_block_location(c->block)); 352 return __rebalance2(info, parent, l, r); 353 } 354 355 /* 356 * Redistributes entries among 3 sibling nodes. 357 */ 358 static int redistribute3(struct dm_btree_info *info, struct btree_node *parent, 359 struct child *l, struct child *c, struct child *r, 360 struct btree_node *left, struct btree_node *center, struct btree_node *right, 361 uint32_t nr_left, uint32_t nr_center, uint32_t nr_right) 362 { 363 int s, ret; 364 uint32_t max_entries = le32_to_cpu(left->header.max_entries); 365 unsigned int total = nr_left + nr_center + nr_right; 366 unsigned int target_right = total / 3; 367 unsigned int remainder = (target_right * 3) != total; 368 unsigned int target_left = target_right + remainder; 369 370 BUG_ON(target_left > max_entries); 371 BUG_ON(target_right > max_entries); 372 373 if (nr_left < nr_right) { 374 s = nr_left - target_left; 375 376 if (s < 0 && nr_center < -s) { 377 /* not enough in central node */ 378 ret = shift(left, center, -nr_center); 379 if (ret) 380 return ret; 381 382 s += nr_center; 383 ret = shift(left, right, s); 384 if (ret) 385 return ret; 386 387 nr_right += s; 388 } else { 389 ret = shift(left, center, s); 390 if (ret) 391 return ret; 392 } 393 394 ret = shift(center, right, target_right - nr_right); 395 if (ret) 396 return ret; 397 } else { 398 s = target_right - nr_right; 399 if (s > 0 && nr_center < s) { 400 /* not enough in central node */ 401 ret = shift(center, right, nr_center); 402 if (ret) 403 return ret; 404 s -= nr_center; 405 ret = shift(left, right, s); 406 if (ret) 407 return ret; 408 nr_left -= s; 409 } else { 410 ret = shift(center, right, s); 411 if (ret) 412 return ret; 413 } 414 415 ret = shift(left, center, nr_left - target_left); 416 if (ret) 417 return ret; 418 } 419 420 *key_ptr(parent, c->index) = center->keys[0]; 421 *key_ptr(parent, r->index) = right->keys[0]; 422 return 0; 423 } 424 425 static int __rebalance3(struct dm_btree_info *info, struct btree_node *parent, 426 struct child *l, struct child *c, struct child *r) 427 { 428 struct btree_node *left = l->n; 429 struct btree_node *center = c->n; 430 struct btree_node *right = r->n; 431 432 uint32_t nr_left = le32_to_cpu(left->header.nr_entries); 433 uint32_t nr_center = le32_to_cpu(center->header.nr_entries); 434 uint32_t nr_right = le32_to_cpu(right->header.nr_entries); 435 436 unsigned int threshold = merge_threshold(left) * 4 + 1; 437 438 if ((left->header.max_entries != center->header.max_entries) || 439 (center->header.max_entries != right->header.max_entries)) { 440 DMERR("bad btree metadata, max_entries differ"); 441 return -EILSEQ; 442 } 443 444 if ((nr_left + nr_center + nr_right) < threshold) { 445 return delete_center_node(info, parent, l, c, r, left, center, right, 446 nr_left, nr_center, nr_right); 447 } 448 449 return redistribute3(info, parent, l, c, r, left, center, right, 450 nr_left, nr_center, nr_right); 451 } 452 453 static int rebalance3(struct shadow_spine *s, struct dm_btree_info *info, 454 struct dm_btree_value_type *vt, unsigned int left_index) 455 { 456 int r; 457 struct btree_node *parent = dm_block_data(shadow_current(s)); 458 struct child left, center, right; 459 460 /* 461 * FIXME: fill out an array? 462 */ 463 r = init_child(info, vt, parent, left_index, &left); 464 if (r) 465 return r; 466 467 r = init_child(info, vt, parent, left_index + 1, ¢er); 468 if (r) { 469 exit_child(info, &left); 470 return r; 471 } 472 473 r = init_child(info, vt, parent, left_index + 2, &right); 474 if (r) { 475 exit_child(info, &left); 476 exit_child(info, ¢er); 477 return r; 478 } 479 480 r = __rebalance3(info, parent, &left, ¢er, &right); 481 482 exit_child(info, &left); 483 exit_child(info, ¢er); 484 exit_child(info, &right); 485 486 return r; 487 } 488 489 static int rebalance_children(struct shadow_spine *s, 490 struct dm_btree_info *info, 491 struct dm_btree_value_type *vt, uint64_t key) 492 { 493 int i, r, has_left_sibling, has_right_sibling; 494 struct btree_node *n; 495 496 n = dm_block_data(shadow_current(s)); 497 498 if (le32_to_cpu(n->header.nr_entries) == 1) { 499 struct dm_block *child; 500 int is_shared; 501 dm_block_t b = value64(n, 0); 502 503 r = dm_tm_block_is_shared(info->tm, b, &is_shared); 504 if (r) 505 return r; 506 507 r = dm_tm_read_lock(info->tm, b, &btree_node_validator, &child); 508 if (r) 509 return r; 510 511 if (is_shared) 512 inc_children(info->tm, dm_block_data(child), vt); 513 514 memcpy(n, dm_block_data(child), 515 dm_bm_block_size(dm_tm_get_bm(info->tm))); 516 517 dm_tm_dec(info->tm, dm_block_location(child)); 518 dm_tm_unlock(info->tm, child); 519 return 0; 520 } 521 522 i = lower_bound(n, key); 523 if (i < 0) 524 return -ENODATA; 525 526 has_left_sibling = i > 0; 527 has_right_sibling = i < (le32_to_cpu(n->header.nr_entries) - 1); 528 529 if (!has_left_sibling) 530 r = rebalance2(s, info, vt, i); 531 532 else if (!has_right_sibling) 533 r = rebalance2(s, info, vt, i - 1); 534 535 else 536 r = rebalance3(s, info, vt, i - 1); 537 538 return r; 539 } 540 541 static int do_leaf(struct btree_node *n, uint64_t key, unsigned int *index) 542 { 543 int i = lower_bound(n, key); 544 545 if ((i < 0) || 546 (i >= le32_to_cpu(n->header.nr_entries)) || 547 (le64_to_cpu(n->keys[i]) != key)) 548 return -ENODATA; 549 550 *index = i; 551 552 return 0; 553 } 554 555 /* 556 * Prepares for removal from one level of the hierarchy. The caller must 557 * call delete_at() to remove the entry at index. 558 */ 559 static int remove_raw(struct shadow_spine *s, struct dm_btree_info *info, 560 struct dm_btree_value_type *vt, dm_block_t root, 561 uint64_t key, unsigned int *index) 562 { 563 int i = *index, r; 564 struct btree_node *n; 565 566 for (;;) { 567 r = shadow_step(s, root, vt); 568 if (r < 0) 569 break; 570 571 /* 572 * We have to patch up the parent node, ugly, but I don't 573 * see a way to do this automatically as part of the spine 574 * op. 575 */ 576 if (shadow_has_parent(s)) { 577 __le64 location = cpu_to_le64(dm_block_location(shadow_current(s))); 578 579 memcpy(value_ptr(dm_block_data(shadow_parent(s)), i), 580 &location, sizeof(__le64)); 581 } 582 583 n = dm_block_data(shadow_current(s)); 584 585 if (le32_to_cpu(n->header.flags) & LEAF_NODE) 586 return do_leaf(n, key, index); 587 588 r = rebalance_children(s, info, vt, key); 589 if (r) 590 break; 591 592 n = dm_block_data(shadow_current(s)); 593 if (le32_to_cpu(n->header.flags) & LEAF_NODE) 594 return do_leaf(n, key, index); 595 596 i = lower_bound(n, key); 597 598 /* 599 * We know the key is present, or else 600 * rebalance_children would have returned 601 * -ENODATA 602 */ 603 root = value64(n, i); 604 } 605 606 return r; 607 } 608 609 int dm_btree_remove(struct dm_btree_info *info, dm_block_t root, 610 uint64_t *keys, dm_block_t *new_root) 611 { 612 unsigned int level, last_level = info->levels - 1; 613 int index = 0, r = 0; 614 struct shadow_spine spine; 615 struct btree_node *n; 616 struct dm_btree_value_type le64_vt; 617 618 init_le64_type(info->tm, &le64_vt); 619 init_shadow_spine(&spine, info); 620 for (level = 0; level < info->levels; level++) { 621 r = remove_raw(&spine, info, 622 (level == last_level ? 623 &info->value_type : &le64_vt), 624 root, keys[level], (unsigned int *)&index); 625 if (r < 0) 626 break; 627 628 n = dm_block_data(shadow_current(&spine)); 629 if (level != last_level) { 630 root = value64(n, index); 631 continue; 632 } 633 634 BUG_ON(index < 0 || index >= le32_to_cpu(n->header.nr_entries)); 635 636 if (info->value_type.dec) 637 info->value_type.dec(info->value_type.context, 638 value_ptr(n, index), 1); 639 640 delete_at(n, index); 641 } 642 643 if (!r) 644 *new_root = shadow_root(&spine); 645 exit_shadow_spine(&spine); 646 647 return r; 648 } 649 EXPORT_SYMBOL_GPL(dm_btree_remove); 650 651 /*----------------------------------------------------------------*/ 652 653 static int remove_nearest(struct shadow_spine *s, struct dm_btree_info *info, 654 struct dm_btree_value_type *vt, dm_block_t root, 655 uint64_t key, int *index) 656 { 657 int i = *index, r; 658 struct btree_node *n; 659 660 for (;;) { 661 r = shadow_step(s, root, vt); 662 if (r < 0) 663 break; 664 665 /* 666 * We have to patch up the parent node, ugly, but I don't 667 * see a way to do this automatically as part of the spine 668 * op. 669 */ 670 if (shadow_has_parent(s)) { 671 __le64 location = cpu_to_le64(dm_block_location(shadow_current(s))); 672 673 memcpy(value_ptr(dm_block_data(shadow_parent(s)), i), 674 &location, sizeof(__le64)); 675 } 676 677 n = dm_block_data(shadow_current(s)); 678 679 if (le32_to_cpu(n->header.flags) & LEAF_NODE) { 680 *index = lower_bound(n, key); 681 return 0; 682 } 683 684 r = rebalance_children(s, info, vt, key); 685 if (r) 686 break; 687 688 n = dm_block_data(shadow_current(s)); 689 if (le32_to_cpu(n->header.flags) & LEAF_NODE) { 690 *index = lower_bound(n, key); 691 return 0; 692 } 693 694 i = lower_bound(n, key); 695 696 /* 697 * We know the key is present, or else 698 * rebalance_children would have returned 699 * -ENODATA 700 */ 701 root = value64(n, i); 702 } 703 704 return r; 705 } 706 707 static int remove_one(struct dm_btree_info *info, dm_block_t root, 708 uint64_t *keys, uint64_t end_key, 709 dm_block_t *new_root, unsigned int *nr_removed) 710 { 711 unsigned int level, last_level = info->levels - 1; 712 int index = 0, r = 0; 713 struct shadow_spine spine; 714 struct btree_node *n; 715 struct dm_btree_value_type le64_vt; 716 uint64_t k; 717 718 init_le64_type(info->tm, &le64_vt); 719 init_shadow_spine(&spine, info); 720 for (level = 0; level < last_level; level++) { 721 r = remove_raw(&spine, info, &le64_vt, 722 root, keys[level], (unsigned int *) &index); 723 if (r < 0) 724 goto out; 725 726 n = dm_block_data(shadow_current(&spine)); 727 root = value64(n, index); 728 } 729 730 r = remove_nearest(&spine, info, &info->value_type, 731 root, keys[last_level], &index); 732 if (r < 0) 733 goto out; 734 735 n = dm_block_data(shadow_current(&spine)); 736 737 if (index < 0) 738 index = 0; 739 740 if (index >= le32_to_cpu(n->header.nr_entries)) { 741 r = -ENODATA; 742 goto out; 743 } 744 745 k = le64_to_cpu(n->keys[index]); 746 if (k >= keys[last_level] && k < end_key) { 747 if (info->value_type.dec) 748 info->value_type.dec(info->value_type.context, 749 value_ptr(n, index), 1); 750 751 delete_at(n, index); 752 keys[last_level] = k + 1ull; 753 754 } else 755 r = -ENODATA; 756 757 out: 758 *new_root = shadow_root(&spine); 759 exit_shadow_spine(&spine); 760 761 return r; 762 } 763 764 int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root, 765 uint64_t *first_key, uint64_t end_key, 766 dm_block_t *new_root, unsigned int *nr_removed) 767 { 768 int r; 769 770 *nr_removed = 0; 771 do { 772 r = remove_one(info, root, first_key, end_key, &root, nr_removed); 773 if (!r) 774 (*nr_removed)++; 775 } while (!r); 776 777 *new_root = root; 778 return r == -ENODATA ? 0 : r; 779 } 780 EXPORT_SYMBOL_GPL(dm_btree_remove_leaves); 781