1638 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-internal.h"9#include "dm-space-map.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 *--------------------------------------------------------------19 * Array manipulation20 *--------------------------------------------------------------21 */22static void memcpy_disk(void *dest, const void *src, size_t len)23 __dm_written_to_disk(src)24{25 memcpy(dest, src, len);26 __dm_unbless_for_disk(src);27}28 29static void array_insert(void *base, size_t elt_size, unsigned int nr_elts,30 unsigned int index, void *elt)31 __dm_written_to_disk(elt)32{33 if (index < nr_elts)34 memmove(base + (elt_size * (index + 1)),35 base + (elt_size * index),36 (nr_elts - index) * elt_size);37 38 memcpy_disk(base + (elt_size * index), elt, elt_size);39}40 41/*----------------------------------------------------------------*/42 43/* makes the assumption that no two keys are the same. */44static int bsearch(struct btree_node *n, uint64_t key, int want_hi)45{46 int lo = -1, hi = le32_to_cpu(n->header.nr_entries);47 48 while (hi - lo > 1) {49 int mid = lo + ((hi - lo) / 2);50 uint64_t mid_key = le64_to_cpu(n->keys[mid]);51 52 if (mid_key == key)53 return mid;54 55 if (mid_key < key)56 lo = mid;57 else58 hi = mid;59 }60 61 return want_hi ? hi : lo;62}63 64int lower_bound(struct btree_node *n, uint64_t key)65{66 return bsearch(n, key, 0);67}68 69static int upper_bound(struct btree_node *n, uint64_t key)70{71 return bsearch(n, key, 1);72}73 74void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,75 struct dm_btree_value_type *vt)76{77 uint32_t nr_entries = le32_to_cpu(n->header.nr_entries);78 79 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE)80 dm_tm_with_runs(tm, value_ptr(n, 0), nr_entries, dm_tm_inc_range);81 82 else if (vt->inc)83 vt->inc(vt->context, value_ptr(n, 0), nr_entries);84}85 86static int insert_at(size_t value_size, struct btree_node *node, unsigned int index,87 uint64_t key, void *value)88 __dm_written_to_disk(value)89{90 uint32_t nr_entries = le32_to_cpu(node->header.nr_entries);91 uint32_t max_entries = le32_to_cpu(node->header.max_entries);92 __le64 key_le = cpu_to_le64(key);93 94 if (index > nr_entries ||95 index >= max_entries ||96 nr_entries >= max_entries) {97 DMERR("too many entries in btree node for insert");98 __dm_unbless_for_disk(value);99 return -ENOMEM;100 }101 102 __dm_bless_for_disk(&key_le);103 104 array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le);105 array_insert(value_base(node), value_size, nr_entries, index, value);106 node->header.nr_entries = cpu_to_le32(nr_entries + 1);107 108 return 0;109}110 111/*----------------------------------------------------------------*/112 113/*114 * We want 3n entries (for some n). This works more nicely for repeated115 * insert remove loops than (2n + 1).116 */117static uint32_t calc_max_entries(size_t value_size, size_t block_size)118{119 uint32_t total, n;120 size_t elt_size = sizeof(uint64_t) + value_size; /* key + value */121 122 block_size -= sizeof(struct node_header);123 total = block_size / elt_size;124 n = total / 3; /* rounds down */125 126 return 3 * n;127}128 129int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root)130{131 int r;132 struct dm_block *b;133 struct btree_node *n;134 size_t block_size;135 uint32_t max_entries;136 137 r = new_block(info, &b);138 if (r < 0)139 return r;140 141 block_size = dm_bm_block_size(dm_tm_get_bm(info->tm));142 max_entries = calc_max_entries(info->value_type.size, block_size);143 144 n = dm_block_data(b);145 memset(n, 0, block_size);146 n->header.flags = cpu_to_le32(LEAF_NODE);147 n->header.nr_entries = cpu_to_le32(0);148 n->header.max_entries = cpu_to_le32(max_entries);149 n->header.value_size = cpu_to_le32(info->value_type.size);150 151 *root = dm_block_location(b);152 unlock_block(info, b);153 154 return 0;155}156EXPORT_SYMBOL_GPL(dm_btree_empty);157 158/*----------------------------------------------------------------*/159 160/*161 * Deletion uses a recursive algorithm, since we have limited stack space162 * we explicitly manage our own stack on the heap.163 */164#define MAX_SPINE_DEPTH 64165struct frame {166 struct dm_block *b;167 struct btree_node *n;168 unsigned int level;169 unsigned int nr_children;170 unsigned int current_child;171};172 173struct del_stack {174 struct dm_btree_info *info;175 struct dm_transaction_manager *tm;176 int top;177 struct frame spine[MAX_SPINE_DEPTH];178};179 180static int top_frame(struct del_stack *s, struct frame **f)181{182 if (s->top < 0) {183 DMERR("btree deletion stack empty");184 return -EINVAL;185 }186 187 *f = s->spine + s->top;188 189 return 0;190}191 192static int unprocessed_frames(struct del_stack *s)193{194 return s->top >= 0;195}196 197static void prefetch_children(struct del_stack *s, struct frame *f)198{199 unsigned int i;200 struct dm_block_manager *bm = dm_tm_get_bm(s->tm);201 202 for (i = 0; i < f->nr_children; i++)203 dm_bm_prefetch(bm, value64(f->n, i));204}205 206static bool is_internal_level(struct dm_btree_info *info, struct frame *f)207{208 return f->level < (info->levels - 1);209}210 211static int push_frame(struct del_stack *s, dm_block_t b, unsigned int level)212{213 int r;214 uint32_t ref_count;215 216 if (s->top >= MAX_SPINE_DEPTH - 1) {217 DMERR("btree deletion stack out of memory");218 return -ENOMEM;219 }220 221 r = dm_tm_ref(s->tm, b, &ref_count);222 if (r)223 return r;224 225 if (ref_count > 1)226 /*227 * This is a shared node, so we can just decrement it's228 * reference counter and leave the children.229 */230 dm_tm_dec(s->tm, b);231 232 else {233 uint32_t flags;234 struct frame *f = s->spine + ++s->top;235 236 r = dm_tm_read_lock(s->tm, b, &btree_node_validator, &f->b);237 if (r) {238 s->top--;239 return r;240 }241 242 f->n = dm_block_data(f->b);243 f->level = level;244 f->nr_children = le32_to_cpu(f->n->header.nr_entries);245 f->current_child = 0;246 247 flags = le32_to_cpu(f->n->header.flags);248 if (flags & INTERNAL_NODE || is_internal_level(s->info, f))249 prefetch_children(s, f);250 }251 252 return 0;253}254 255static void pop_frame(struct del_stack *s)256{257 struct frame *f = s->spine + s->top--;258 259 dm_tm_dec(s->tm, dm_block_location(f->b));260 dm_tm_unlock(s->tm, f->b);261}262 263static void unlock_all_frames(struct del_stack *s)264{265 struct frame *f;266 267 while (unprocessed_frames(s)) {268 f = s->spine + s->top--;269 dm_tm_unlock(s->tm, f->b);270 }271}272 273int dm_btree_del(struct dm_btree_info *info, dm_block_t root)274{275 int r;276 struct del_stack *s;277 278 /*279 * dm_btree_del() is called via an ioctl, as such should be280 * considered an FS op. We can't recurse back into the FS, so we281 * allocate GFP_NOFS.282 */283 s = kmalloc(sizeof(*s), GFP_NOFS);284 if (!s)285 return -ENOMEM;286 s->info = info;287 s->tm = info->tm;288 s->top = -1;289 290 r = push_frame(s, root, 0);291 if (r)292 goto out;293 294 while (unprocessed_frames(s)) {295 uint32_t flags;296 struct frame *f;297 dm_block_t b;298 299 r = top_frame(s, &f);300 if (r)301 goto out;302 303 if (f->current_child >= f->nr_children) {304 pop_frame(s);305 continue;306 }307 308 flags = le32_to_cpu(f->n->header.flags);309 if (flags & INTERNAL_NODE) {310 b = value64(f->n, f->current_child);311 f->current_child++;312 r = push_frame(s, b, f->level);313 if (r)314 goto out;315 316 } else if (is_internal_level(info, f)) {317 b = value64(f->n, f->current_child);318 f->current_child++;319 r = push_frame(s, b, f->level + 1);320 if (r)321 goto out;322 323 } else {324 if (info->value_type.dec)325 info->value_type.dec(info->value_type.context,326 value_ptr(f->n, 0), f->nr_children);327 pop_frame(s);328 }329 }330out:331 if (r) {332 /* cleanup all frames of del_stack */333 unlock_all_frames(s);334 }335 kfree(s);336 337 return r;338}339EXPORT_SYMBOL_GPL(dm_btree_del);340 341/*----------------------------------------------------------------*/342 343static int btree_lookup_raw(struct ro_spine *s, dm_block_t block, uint64_t key,344 int (*search_fn)(struct btree_node *, uint64_t),345 uint64_t *result_key, void *v, size_t value_size)346{347 int i, r;348 uint32_t flags, nr_entries;349 350 do {351 r = ro_step(s, block);352 if (r < 0)353 return r;354 355 i = search_fn(ro_node(s), key);356 357 flags = le32_to_cpu(ro_node(s)->header.flags);358 nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries);359 if (i < 0 || i >= nr_entries)360 return -ENODATA;361 362 if (flags & INTERNAL_NODE)363 block = value64(ro_node(s), i);364 365 } while (!(flags & LEAF_NODE));366 367 *result_key = le64_to_cpu(ro_node(s)->keys[i]);368 if (v)369 memcpy(v, value_ptr(ro_node(s), i), value_size);370 371 return 0;372}373 374int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root,375 uint64_t *keys, void *value_le)376{377 unsigned int level, last_level = info->levels - 1;378 int r = -ENODATA;379 uint64_t rkey;380 __le64 internal_value_le;381 struct ro_spine spine;382 383 init_ro_spine(&spine, info);384 for (level = 0; level < info->levels; level++) {385 size_t size;386 void *value_p;387 388 if (level == last_level) {389 value_p = value_le;390 size = info->value_type.size;391 392 } else {393 value_p = &internal_value_le;394 size = sizeof(uint64_t);395 }396 397 r = btree_lookup_raw(&spine, root, keys[level],398 lower_bound, &rkey,399 value_p, size);400 401 if (!r) {402 if (rkey != keys[level]) {403 exit_ro_spine(&spine);404 return -ENODATA;405 }406 } else {407 exit_ro_spine(&spine);408 return r;409 }410 411 root = le64_to_cpu(internal_value_le);412 }413 exit_ro_spine(&spine);414 415 return r;416}417EXPORT_SYMBOL_GPL(dm_btree_lookup);418 419static int dm_btree_lookup_next_single(struct dm_btree_info *info, dm_block_t root,420 uint64_t key, uint64_t *rkey, void *value_le)421{422 int r, i;423 uint32_t flags, nr_entries;424 struct dm_block *node;425 struct btree_node *n;426 427 r = bn_read_lock(info, root, &node);428 if (r)429 return r;430 431 n = dm_block_data(node);432 flags = le32_to_cpu(n->header.flags);433 nr_entries = le32_to_cpu(n->header.nr_entries);434 435 if (flags & INTERNAL_NODE) {436 i = lower_bound(n, key);437 if (i < 0) {438 /*439 * avoid early -ENODATA return when all entries are440 * higher than the search @key.441 */442 i = 0;443 }444 if (i >= nr_entries) {445 r = -ENODATA;446 goto out;447 }448 449 r = dm_btree_lookup_next_single(info, value64(n, i), key, rkey, value_le);450 if (r == -ENODATA && i < (nr_entries - 1)) {451 i++;452 r = dm_btree_lookup_next_single(info, value64(n, i), key, rkey, value_le);453 }454 455 } else {456 i = upper_bound(n, key);457 if (i < 0 || i >= nr_entries) {458 r = -ENODATA;459 goto out;460 }461 462 *rkey = le64_to_cpu(n->keys[i]);463 memcpy(value_le, value_ptr(n, i), info->value_type.size);464 }465out:466 dm_tm_unlock(info->tm, node);467 return r;468}469 470int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root,471 uint64_t *keys, uint64_t *rkey, void *value_le)472{473 unsigned int level;474 int r = -ENODATA;475 __le64 internal_value_le;476 struct ro_spine spine;477 478 init_ro_spine(&spine, info);479 for (level = 0; level < info->levels - 1u; level++) {480 r = btree_lookup_raw(&spine, root, keys[level],481 lower_bound, rkey,482 &internal_value_le, sizeof(uint64_t));483 if (r)484 goto out;485 486 if (*rkey != keys[level]) {487 r = -ENODATA;488 goto out;489 }490 491 root = le64_to_cpu(internal_value_le);492 }493 494 r = dm_btree_lookup_next_single(info, root, keys[level], rkey, value_le);495out:496 exit_ro_spine(&spine);497 return r;498}499EXPORT_SYMBOL_GPL(dm_btree_lookup_next);500 501/*----------------------------------------------------------------*/502 503/*504 * Copies entries from one region of a btree node to another. The regions505 * must not overlap.506 */507static void copy_entries(struct btree_node *dest, unsigned int dest_offset,508 struct btree_node *src, unsigned int src_offset,509 unsigned int count)510{511 size_t value_size = le32_to_cpu(dest->header.value_size);512 513 memcpy(dest->keys + dest_offset, src->keys + src_offset, count * sizeof(uint64_t));514 memcpy(value_ptr(dest, dest_offset), value_ptr(src, src_offset), count * value_size);515}516 517/*518 * Moves entries from one region fo a btree node to another. The regions519 * may overlap.520 */521static void move_entries(struct btree_node *dest, unsigned int dest_offset,522 struct btree_node *src, unsigned int src_offset,523 unsigned int count)524{525 size_t value_size = le32_to_cpu(dest->header.value_size);526 527 memmove(dest->keys + dest_offset, src->keys + src_offset, count * sizeof(uint64_t));528 memmove(value_ptr(dest, dest_offset), value_ptr(src, src_offset), count * value_size);529}530 531/*532 * Erases the first 'count' entries of a btree node, shifting following533 * entries down into their place.534 */535static void shift_down(struct btree_node *n, unsigned int count)536{537 move_entries(n, 0, n, count, le32_to_cpu(n->header.nr_entries) - count);538}539 540/*541 * Moves entries in a btree node up 'count' places, making space for542 * new entries at the start of the node.543 */544static void shift_up(struct btree_node *n, unsigned int count)545{546 move_entries(n, count, n, 0, le32_to_cpu(n->header.nr_entries));547}548 549/*550 * Redistributes entries between two btree nodes to make them551 * have similar numbers of entries.552 */553static void redistribute2(struct btree_node *left, struct btree_node *right)554{555 unsigned int nr_left = le32_to_cpu(left->header.nr_entries);556 unsigned int nr_right = le32_to_cpu(right->header.nr_entries);557 unsigned int total = nr_left + nr_right;558 unsigned int target_left = total / 2;559 unsigned int target_right = total - target_left;560 561 if (nr_left < target_left) {562 unsigned int delta = target_left - nr_left;563 564 copy_entries(left, nr_left, right, 0, delta);565 shift_down(right, delta);566 } else if (nr_left > target_left) {567 unsigned int delta = nr_left - target_left;568 569 if (nr_right)570 shift_up(right, delta);571 copy_entries(right, 0, left, target_left, delta);572 }573 574 left->header.nr_entries = cpu_to_le32(target_left);575 right->header.nr_entries = cpu_to_le32(target_right);576}577 578/*579 * Redistribute entries between three nodes. Assumes the central580 * node is empty.581 */582static void redistribute3(struct btree_node *left, struct btree_node *center,583 struct btree_node *right)584{585 unsigned int nr_left = le32_to_cpu(left->header.nr_entries);586 unsigned int nr_center = le32_to_cpu(center->header.nr_entries);587 unsigned int nr_right = le32_to_cpu(right->header.nr_entries);588 unsigned int total, target_left, target_center, target_right;589 590 BUG_ON(nr_center);591 592 total = nr_left + nr_right;593 target_left = total / 3;594 target_center = (total - target_left) / 2;595 target_right = (total - target_left - target_center);596 597 if (nr_left < target_left) {598 unsigned int left_short = target_left - nr_left;599 600 copy_entries(left, nr_left, right, 0, left_short);601 copy_entries(center, 0, right, left_short, target_center);602 shift_down(right, nr_right - target_right);603 604 } else if (nr_left < (target_left + target_center)) {605 unsigned int left_to_center = nr_left - target_left;606 607 copy_entries(center, 0, left, target_left, left_to_center);608 copy_entries(center, left_to_center, right, 0, target_center - left_to_center);609 shift_down(right, nr_right - target_right);610 611 } else {612 unsigned int right_short = target_right - nr_right;613 614 shift_up(right, right_short);615 copy_entries(right, 0, left, nr_left - right_short, right_short);616 copy_entries(center, 0, left, target_left, nr_left - target_left);617 }618 619 left->header.nr_entries = cpu_to_le32(target_left);620 center->header.nr_entries = cpu_to_le32(target_center);621 right->header.nr_entries = cpu_to_le32(target_right);622}623 624/*625 * Splits a node by creating a sibling node and shifting half the nodes626 * contents across. Assumes there is a parent node, and it has room for627 * another child.628 *629 * Before:630 * +--------+631 * | Parent |632 * +--------+633 * |634 * v635 * +----------+636 * | A ++++++ |637 * +----------+638 *639 *640 * After:641 * +--------+642 * | Parent |643 * +--------+644 * | |645 * v +------+646 * +---------+ |647 * | A* +++ | v648 * +---------+ +-------+649 * | B +++ |650 * +-------+651 *652 * Where A* is a shadow of A.653 */654static int split_one_into_two(struct shadow_spine *s, unsigned int parent_index,655 struct dm_btree_value_type *vt, uint64_t key)656{657 int r;658 struct dm_block *left, *right, *parent;659 struct btree_node *ln, *rn, *pn;660 __le64 location;661 662 left = shadow_current(s);663 664 r = new_block(s->info, &right);665 if (r < 0)666 return r;667 668 ln = dm_block_data(left);669 rn = dm_block_data(right);670 671 rn->header.flags = ln->header.flags;672 rn->header.nr_entries = cpu_to_le32(0);673 rn->header.max_entries = ln->header.max_entries;674 rn->header.value_size = ln->header.value_size;675 redistribute2(ln, rn);676 677 /* patch up the parent */678 parent = shadow_parent(s);679 pn = dm_block_data(parent);680 681 location = cpu_to_le64(dm_block_location(right));682 __dm_bless_for_disk(&location);683 r = insert_at(sizeof(__le64), pn, parent_index + 1,684 le64_to_cpu(rn->keys[0]), &location);685 if (r) {686 unlock_block(s->info, right);687 return r;688 }689 690 /* patch up the spine */691 if (key < le64_to_cpu(rn->keys[0])) {692 unlock_block(s->info, right);693 s->nodes[1] = left;694 } else {695 unlock_block(s->info, left);696 s->nodes[1] = right;697 }698 699 return 0;700}701 702/*703 * We often need to modify a sibling node. This function shadows a particular704 * child of the given parent node. Making sure to update the parent to point705 * to the new shadow.706 */707static int shadow_child(struct dm_btree_info *info, struct dm_btree_value_type *vt,708 struct btree_node *parent, unsigned int index,709 struct dm_block **result)710{711 int r, inc;712 dm_block_t root;713 struct btree_node *node;714 715 root = value64(parent, index);716 717 r = dm_tm_shadow_block(info->tm, root, &btree_node_validator,718 result, &inc);719 if (r)720 return r;721 722 node = dm_block_data(*result);723 724 if (inc)725 inc_children(info->tm, node, vt);726 727 *((__le64 *) value_ptr(parent, index)) =728 cpu_to_le64(dm_block_location(*result));729 730 return 0;731}732 733/*734 * Splits two nodes into three. This is more work, but results in fuller735 * nodes, so saves metadata space.736 */737static int split_two_into_three(struct shadow_spine *s, unsigned int parent_index,738 struct dm_btree_value_type *vt, uint64_t key)739{740 int r;741 unsigned int middle_index;742 struct dm_block *left, *middle, *right, *parent;743 struct btree_node *ln, *rn, *mn, *pn;744 __le64 location;745 746 parent = shadow_parent(s);747 pn = dm_block_data(parent);748 749 if (parent_index == 0) {750 middle_index = 1;751 left = shadow_current(s);752 r = shadow_child(s->info, vt, pn, parent_index + 1, &right);753 if (r)754 return r;755 } else {756 middle_index = parent_index;757 right = shadow_current(s);758 r = shadow_child(s->info, vt, pn, parent_index - 1, &left);759 if (r)760 return r;761 }762 763 r = new_block(s->info, &middle);764 if (r < 0)765 return r;766 767 ln = dm_block_data(left);768 mn = dm_block_data(middle);769 rn = dm_block_data(right);770 771 mn->header.nr_entries = cpu_to_le32(0);772 mn->header.flags = ln->header.flags;773 mn->header.max_entries = ln->header.max_entries;774 mn->header.value_size = ln->header.value_size;775 776 redistribute3(ln, mn, rn);777 778 /* patch up the parent */779 pn->keys[middle_index] = rn->keys[0];780 location = cpu_to_le64(dm_block_location(middle));781 __dm_bless_for_disk(&location);782 r = insert_at(sizeof(__le64), pn, middle_index,783 le64_to_cpu(mn->keys[0]), &location);784 if (r) {785 if (shadow_current(s) != left)786 unlock_block(s->info, left);787 788 unlock_block(s->info, middle);789 790 if (shadow_current(s) != right)791 unlock_block(s->info, right);792 793 return r;794 }795 796 797 /* patch up the spine */798 if (key < le64_to_cpu(mn->keys[0])) {799 unlock_block(s->info, middle);800 unlock_block(s->info, right);801 s->nodes[1] = left;802 } else if (key < le64_to_cpu(rn->keys[0])) {803 unlock_block(s->info, left);804 unlock_block(s->info, right);805 s->nodes[1] = middle;806 } else {807 unlock_block(s->info, left);808 unlock_block(s->info, middle);809 s->nodes[1] = right;810 }811 812 return 0;813}814 815/*----------------------------------------------------------------*/816 817/*818 * Splits a node by creating two new children beneath the given node.819 *820 * Before:821 * +----------+822 * | A ++++++ |823 * +----------+824 *825 *826 * After:827 * +------------+828 * | A (shadow) |829 * +------------+830 * | |831 * +------+ +----+832 * | |833 * v v834 * +-------+ +-------+835 * | B +++ | | C +++ |836 * +-------+ +-------+837 */838static int btree_split_beneath(struct shadow_spine *s, uint64_t key)839{840 int r;841 size_t size;842 unsigned int nr_left, nr_right;843 struct dm_block *left, *right, *new_parent;844 struct btree_node *pn, *ln, *rn;845 __le64 val;846 847 new_parent = shadow_current(s);848 849 pn = dm_block_data(new_parent);850 size = le32_to_cpu(pn->header.flags) & INTERNAL_NODE ?851 sizeof(__le64) : s->info->value_type.size;852 853 /* create & init the left block */854 r = new_block(s->info, &left);855 if (r < 0)856 return r;857 858 ln = dm_block_data(left);859 nr_left = le32_to_cpu(pn->header.nr_entries) / 2;860 861 ln->header.flags = pn->header.flags;862 ln->header.nr_entries = cpu_to_le32(nr_left);863 ln->header.max_entries = pn->header.max_entries;864 ln->header.value_size = pn->header.value_size;865 memcpy(ln->keys, pn->keys, nr_left * sizeof(pn->keys[0]));866 memcpy(value_ptr(ln, 0), value_ptr(pn, 0), nr_left * size);867 868 /* create & init the right block */869 r = new_block(s->info, &right);870 if (r < 0) {871 unlock_block(s->info, left);872 return r;873 }874 875 rn = dm_block_data(right);876 nr_right = le32_to_cpu(pn->header.nr_entries) - nr_left;877 878 rn->header.flags = pn->header.flags;879 rn->header.nr_entries = cpu_to_le32(nr_right);880 rn->header.max_entries = pn->header.max_entries;881 rn->header.value_size = pn->header.value_size;882 memcpy(rn->keys, pn->keys + nr_left, nr_right * sizeof(pn->keys[0]));883 memcpy(value_ptr(rn, 0), value_ptr(pn, nr_left),884 nr_right * size);885 886 /* new_parent should just point to l and r now */887 pn->header.flags = cpu_to_le32(INTERNAL_NODE);888 pn->header.nr_entries = cpu_to_le32(2);889 pn->header.max_entries = cpu_to_le32(890 calc_max_entries(sizeof(__le64),891 dm_bm_block_size(892 dm_tm_get_bm(s->info->tm))));893 pn->header.value_size = cpu_to_le32(sizeof(__le64));894 895 val = cpu_to_le64(dm_block_location(left));896 __dm_bless_for_disk(&val);897 pn->keys[0] = ln->keys[0];898 memcpy_disk(value_ptr(pn, 0), &val, sizeof(__le64));899 900 val = cpu_to_le64(dm_block_location(right));901 __dm_bless_for_disk(&val);902 pn->keys[1] = rn->keys[0];903 memcpy_disk(value_ptr(pn, 1), &val, sizeof(__le64));904 905 unlock_block(s->info, left);906 unlock_block(s->info, right);907 return 0;908}909 910/*----------------------------------------------------------------*/911 912/*913 * Redistributes a node's entries with its left sibling.914 */915static int rebalance_left(struct shadow_spine *s, struct dm_btree_value_type *vt,916 unsigned int parent_index, uint64_t key)917{918 int r;919 struct dm_block *sib;920 struct btree_node *left, *right, *parent = dm_block_data(shadow_parent(s));921 922 r = shadow_child(s->info, vt, parent, parent_index - 1, &sib);923 if (r)924 return r;925 926 left = dm_block_data(sib);927 right = dm_block_data(shadow_current(s));928 redistribute2(left, right);929 *key_ptr(parent, parent_index) = right->keys[0];930 931 if (key < le64_to_cpu(right->keys[0])) {932 unlock_block(s->info, s->nodes[1]);933 s->nodes[1] = sib;934 } else {935 unlock_block(s->info, sib);936 }937 938 return 0;939}940 941/*942 * Redistributes a nodes entries with its right sibling.943 */944static int rebalance_right(struct shadow_spine *s, struct dm_btree_value_type *vt,945 unsigned int parent_index, uint64_t key)946{947 int r;948 struct dm_block *sib;949 struct btree_node *left, *right, *parent = dm_block_data(shadow_parent(s));950 951 r = shadow_child(s->info, vt, parent, parent_index + 1, &sib);952 if (r)953 return r;954 955 left = dm_block_data(shadow_current(s));956 right = dm_block_data(sib);957 redistribute2(left, right);958 *key_ptr(parent, parent_index + 1) = right->keys[0];959 960 if (key < le64_to_cpu(right->keys[0])) {961 unlock_block(s->info, sib);962 } else {963 unlock_block(s->info, s->nodes[1]);964 s->nodes[1] = sib;965 }966 967 return 0;968}969 970/*971 * Returns the number of spare entries in a node.972 */973static int get_node_free_space(struct dm_btree_info *info, dm_block_t b, unsigned int *space)974{975 int r;976 unsigned int nr_entries;977 struct dm_block *block;978 struct btree_node *node;979 980 r = bn_read_lock(info, b, &block);981 if (r)982 return r;983 984 node = dm_block_data(block);985 nr_entries = le32_to_cpu(node->header.nr_entries);986 *space = le32_to_cpu(node->header.max_entries) - nr_entries;987 988 unlock_block(info, block);989 return 0;990}991 992/*993 * Make space in a node, either by moving some entries to a sibling,994 * or creating a new sibling node. SPACE_THRESHOLD defines the minimum995 * number of free entries that must be in the sibling to make the move996 * worth while. If the siblings are shared (eg, part of a snapshot),997 * then they are not touched, since this break sharing and so consume998 * more space than we save.999 */1000#define SPACE_THRESHOLD 81001static int rebalance_or_split(struct shadow_spine *s, struct dm_btree_value_type *vt,1002 unsigned int parent_index, uint64_t key)1003{1004 int r;1005 struct btree_node *parent = dm_block_data(shadow_parent(s));1006 unsigned int nr_parent = le32_to_cpu(parent->header.nr_entries);1007 unsigned int free_space;1008 int left_shared = 0, right_shared = 0;1009 1010 /* Should we move entries to the left sibling? */1011 if (parent_index > 0) {1012 dm_block_t left_b = value64(parent, parent_index - 1);1013 1014 r = dm_tm_block_is_shared(s->info->tm, left_b, &left_shared);1015 if (r)1016 return r;1017 1018 if (!left_shared) {1019 r = get_node_free_space(s->info, left_b, &free_space);1020 if (r)1021 return r;1022 1023 if (free_space >= SPACE_THRESHOLD)1024 return rebalance_left(s, vt, parent_index, key);1025 }1026 }1027 1028 /* Should we move entries to the right sibling? */1029 if (parent_index < (nr_parent - 1)) {1030 dm_block_t right_b = value64(parent, parent_index + 1);1031 1032 r = dm_tm_block_is_shared(s->info->tm, right_b, &right_shared);1033 if (r)1034 return r;1035 1036 if (!right_shared) {1037 r = get_node_free_space(s->info, right_b, &free_space);1038 if (r)1039 return r;1040 1041 if (free_space >= SPACE_THRESHOLD)1042 return rebalance_right(s, vt, parent_index, key);1043 }1044 }1045 1046 /*1047 * We need to split the node, normally we split two nodes1048 * into three. But when inserting a sequence that is either1049 * monotonically increasing or decreasing it's better to split1050 * a single node into two.1051 */1052 if (left_shared || right_shared || (nr_parent <= 2) ||1053 (parent_index == 0) || (parent_index + 1 == nr_parent)) {1054 return split_one_into_two(s, parent_index, vt, key);1055 } else {1056 return split_two_into_three(s, parent_index, vt, key);1057 }1058}1059 1060/*1061 * Does the node contain a particular key?1062 */1063static bool contains_key(struct btree_node *node, uint64_t key)1064{1065 int i = lower_bound(node, key);1066 1067 if (i >= 0 && le64_to_cpu(node->keys[i]) == key)1068 return true;1069 1070 return false;1071}1072 1073/*1074 * In general we preemptively make sure there's a free entry in every1075 * node on the spine when doing an insert. But we can avoid that with1076 * leaf nodes if we know it's an overwrite.1077 */1078static bool has_space_for_insert(struct btree_node *node, uint64_t key)1079{1080 if (node->header.nr_entries == node->header.max_entries) {1081 if (le32_to_cpu(node->header.flags) & LEAF_NODE) {1082 /* we don't need space if it's an overwrite */1083 return contains_key(node, key);1084 }1085 1086 return false;1087 }1088 1089 return true;1090}1091 1092static int btree_insert_raw(struct shadow_spine *s, dm_block_t root,1093 struct dm_btree_value_type *vt,1094 uint64_t key, unsigned int *index)1095{1096 int r, i = *index, top = 1;1097 struct btree_node *node;1098 1099 for (;;) {1100 r = shadow_step(s, root, vt);1101 if (r < 0)1102 return r;1103 1104 node = dm_block_data(shadow_current(s));1105 1106 /*1107 * We have to patch up the parent node, ugly, but I don't1108 * see a way to do this automatically as part of the spine1109 * op.1110 */1111 if (shadow_has_parent(s) && i >= 0) { /* FIXME: second clause unness. */1112 __le64 location = cpu_to_le64(dm_block_location(shadow_current(s)));1113 1114 __dm_bless_for_disk(&location);1115 memcpy_disk(value_ptr(dm_block_data(shadow_parent(s)), i),1116 &location, sizeof(__le64));1117 }1118 1119 node = dm_block_data(shadow_current(s));1120 1121 if (!has_space_for_insert(node, key)) {1122 if (top)1123 r = btree_split_beneath(s, key);1124 else1125 r = rebalance_or_split(s, vt, i, key);1126 1127 if (r < 0)1128 return r;1129 1130 /* making space can cause the current node to change */1131 node = dm_block_data(shadow_current(s));1132 }1133 1134 i = lower_bound(node, key);1135 1136 if (le32_to_cpu(node->header.flags) & LEAF_NODE)1137 break;1138 1139 if (i < 0) {1140 /* change the bounds on the lowest key */1141 node->keys[0] = cpu_to_le64(key);1142 i = 0;1143 }1144 1145 root = value64(node, i);1146 top = 0;1147 }1148 1149 if (i < 0 || le64_to_cpu(node->keys[i]) != key)1150 i++;1151 1152 *index = i;1153 return 0;1154}1155 1156static int __btree_get_overwrite_leaf(struct shadow_spine *s, dm_block_t root,1157 uint64_t key, int *index)1158{1159 int r, i = -1;1160 struct btree_node *node;1161 1162 *index = 0;1163 for (;;) {1164 r = shadow_step(s, root, &s->info->value_type);1165 if (r < 0)1166 return r;1167 1168 node = dm_block_data(shadow_current(s));1169 1170 /*1171 * We have to patch up the parent node, ugly, but I don't1172 * see a way to do this automatically as part of the spine1173 * op.1174 */1175 if (shadow_has_parent(s) && i >= 0) {1176 __le64 location = cpu_to_le64(dm_block_location(shadow_current(s)));1177 1178 __dm_bless_for_disk(&location);1179 memcpy_disk(value_ptr(dm_block_data(shadow_parent(s)), i),1180 &location, sizeof(__le64));1181 }1182 1183 node = dm_block_data(shadow_current(s));1184 i = lower_bound(node, key);1185 1186 BUG_ON(i < 0);1187 BUG_ON(i >= le32_to_cpu(node->header.nr_entries));1188 1189 if (le32_to_cpu(node->header.flags) & LEAF_NODE) {1190 if (key != le64_to_cpu(node->keys[i]))1191 return -EINVAL;1192 break;1193 }1194 1195 root = value64(node, i);1196 }1197 1198 *index = i;1199 return 0;1200}1201 1202int btree_get_overwrite_leaf(struct dm_btree_info *info, dm_block_t root,1203 uint64_t key, int *index,1204 dm_block_t *new_root, struct dm_block **leaf)1205{1206 int r;1207 struct shadow_spine spine;1208 1209 BUG_ON(info->levels > 1);1210 init_shadow_spine(&spine, info);1211 r = __btree_get_overwrite_leaf(&spine, root, key, index);1212 if (!r) {1213 *new_root = shadow_root(&spine);1214 *leaf = shadow_current(&spine);1215 1216 /*1217 * Decrement the count so exit_shadow_spine() doesn't1218 * unlock the leaf.1219 */1220 spine.count--;1221 }1222 exit_shadow_spine(&spine);1223 1224 return r;1225}1226 1227static bool need_insert(struct btree_node *node, uint64_t *keys,1228 unsigned int level, unsigned int index)1229{1230 return ((index >= le32_to_cpu(node->header.nr_entries)) ||1231 (le64_to_cpu(node->keys[index]) != keys[level]));1232}1233 1234static int insert(struct dm_btree_info *info, dm_block_t root,1235 uint64_t *keys, void *value, dm_block_t *new_root,1236 int *inserted)1237 __dm_written_to_disk(value)1238{1239 int r;1240 unsigned int level, index = -1, last_level = info->levels - 1;1241 dm_block_t block = root;1242 struct shadow_spine spine;1243 struct btree_node *n;1244 struct dm_btree_value_type le64_type;1245 1246 init_le64_type(info->tm, &le64_type);1247 init_shadow_spine(&spine, info);1248 1249 for (level = 0; level < (info->levels - 1); level++) {1250 r = btree_insert_raw(&spine, block, &le64_type, keys[level], &index);1251 if (r < 0)1252 goto bad;1253 1254 n = dm_block_data(shadow_current(&spine));1255 1256 if (need_insert(n, keys, level, index)) {1257 dm_block_t new_tree;1258 __le64 new_le;1259 1260 r = dm_btree_empty(info, &new_tree);1261 if (r < 0)1262 goto bad;1263 1264 new_le = cpu_to_le64(new_tree);1265 __dm_bless_for_disk(&new_le);1266 1267 r = insert_at(sizeof(uint64_t), n, index,1268 keys[level], &new_le);1269 if (r)1270 goto bad;1271 }1272 1273 if (level < last_level)1274 block = value64(n, index);1275 }1276 1277 r = btree_insert_raw(&spine, block, &info->value_type,1278 keys[level], &index);1279 if (r < 0)1280 goto bad;1281 1282 n = dm_block_data(shadow_current(&spine));1283 1284 if (need_insert(n, keys, level, index)) {1285 if (inserted)1286 *inserted = 1;1287 1288 r = insert_at(info->value_type.size, n, index,1289 keys[level], value);1290 if (r)1291 goto bad_unblessed;1292 } else {1293 if (inserted)1294 *inserted = 0;1295 1296 if (info->value_type.dec &&1297 (!info->value_type.equal ||1298 !info->value_type.equal(1299 info->value_type.context,1300 value_ptr(n, index),1301 value))) {1302 info->value_type.dec(info->value_type.context,1303 value_ptr(n, index), 1);1304 }1305 memcpy_disk(value_ptr(n, index),1306 value, info->value_type.size);1307 }1308 1309 *new_root = shadow_root(&spine);1310 exit_shadow_spine(&spine);1311 1312 return 0;1313 1314bad:1315 __dm_unbless_for_disk(value);1316bad_unblessed:1317 exit_shadow_spine(&spine);1318 return r;1319}1320 1321int dm_btree_insert(struct dm_btree_info *info, dm_block_t root,1322 uint64_t *keys, void *value, dm_block_t *new_root)1323 __dm_written_to_disk(value)1324{1325 return insert(info, root, keys, value, new_root, NULL);1326}1327EXPORT_SYMBOL_GPL(dm_btree_insert);1328 1329int dm_btree_insert_notify(struct dm_btree_info *info, dm_block_t root,1330 uint64_t *keys, void *value, dm_block_t *new_root,1331 int *inserted)1332 __dm_written_to_disk(value)1333{1334 return insert(info, root, keys, value, new_root, inserted);1335}1336EXPORT_SYMBOL_GPL(dm_btree_insert_notify);1337 1338/*----------------------------------------------------------------*/1339 1340static int find_key(struct ro_spine *s, dm_block_t block, bool find_highest,1341 uint64_t *result_key, dm_block_t *next_block)1342{1343 int i, r;1344 uint32_t flags;1345 1346 do {1347 r = ro_step(s, block);1348 if (r < 0)1349 return r;1350 1351 flags = le32_to_cpu(ro_node(s)->header.flags);1352 i = le32_to_cpu(ro_node(s)->header.nr_entries);1353 if (!i)1354 return -ENODATA;1355 1356 i--;1357 1358 if (find_highest)1359 *result_key = le64_to_cpu(ro_node(s)->keys[i]);1360 else1361 *result_key = le64_to_cpu(ro_node(s)->keys[0]);1362 1363 if (next_block || flags & INTERNAL_NODE) {1364 if (find_highest)1365 block = value64(ro_node(s), i);1366 else1367 block = value64(ro_node(s), 0);1368 }1369 1370 } while (flags & INTERNAL_NODE);1371 1372 if (next_block)1373 *next_block = block;1374 return 0;1375}1376 1377static int dm_btree_find_key(struct dm_btree_info *info, dm_block_t root,1378 bool find_highest, uint64_t *result_keys)1379{1380 int r = 0, count = 0, level;1381 struct ro_spine spine;1382 1383 init_ro_spine(&spine, info);1384 for (level = 0; level < info->levels; level++) {1385 r = find_key(&spine, root, find_highest, result_keys + level,1386 level == info->levels - 1 ? NULL : &root);1387 if (r == -ENODATA) {1388 r = 0;1389 break;1390 1391 } else if (r)1392 break;1393 1394 count++;1395 }1396 exit_ro_spine(&spine);1397 1398 return r ? r : count;1399}1400 1401int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,1402 uint64_t *result_keys)1403{1404 return dm_btree_find_key(info, root, true, result_keys);1405}1406EXPORT_SYMBOL_GPL(dm_btree_find_highest_key);1407 1408int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root,1409 uint64_t *result_keys)1410{1411 return dm_btree_find_key(info, root, false, result_keys);1412}1413EXPORT_SYMBOL_GPL(dm_btree_find_lowest_key);1414 1415/*----------------------------------------------------------------*/1416 1417/*1418 * FIXME: We shouldn't use a recursive algorithm when we have limited stack1419 * space. Also this only works for single level trees.1420 */1421static int walk_node(struct dm_btree_info *info, dm_block_t block,1422 int (*fn)(void *context, uint64_t *keys, void *leaf),1423 void *context)1424{1425 int r;1426 unsigned int i, nr;1427 struct dm_block *node;1428 struct btree_node *n;1429 uint64_t keys;1430 1431 r = bn_read_lock(info, block, &node);1432 if (r)1433 return r;1434 1435 n = dm_block_data(node);1436 1437 nr = le32_to_cpu(n->header.nr_entries);1438 for (i = 0; i < nr; i++) {1439 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) {1440 r = walk_node(info, value64(n, i), fn, context);1441 if (r)1442 goto out;1443 } else {1444 keys = le64_to_cpu(*key_ptr(n, i));1445 r = fn(context, &keys, value_ptr(n, i));1446 if (r)1447 goto out;1448 }1449 }1450 1451out:1452 dm_tm_unlock(info->tm, node);1453 return r;1454}1455 1456int dm_btree_walk(struct dm_btree_info *info, dm_block_t root,1457 int (*fn)(void *context, uint64_t *keys, void *leaf),1458 void *context)1459{1460 BUG_ON(info->levels > 1);1461 return walk_node(info, root, fn, context);1462}1463EXPORT_SYMBOL_GPL(dm_btree_walk);1464 1465/*----------------------------------------------------------------*/1466 1467static void prefetch_values(struct dm_btree_cursor *c)1468{1469 unsigned int i, nr;1470 __le64 value_le;1471 struct cursor_node *n = c->nodes + c->depth - 1;1472 struct btree_node *bn = dm_block_data(n->b);1473 struct dm_block_manager *bm = dm_tm_get_bm(c->info->tm);1474 1475 BUG_ON(c->info->value_type.size != sizeof(value_le));1476 1477 nr = le32_to_cpu(bn->header.nr_entries);1478 for (i = 0; i < nr; i++) {1479 memcpy(&value_le, value_ptr(bn, i), sizeof(value_le));1480 dm_bm_prefetch(bm, le64_to_cpu(value_le));1481 }1482}1483 1484static bool leaf_node(struct dm_btree_cursor *c)1485{1486 struct cursor_node *n = c->nodes + c->depth - 1;1487 struct btree_node *bn = dm_block_data(n->b);1488 1489 return le32_to_cpu(bn->header.flags) & LEAF_NODE;1490}1491 1492static int push_node(struct dm_btree_cursor *c, dm_block_t b)1493{1494 int r;1495 struct cursor_node *n = c->nodes + c->depth;1496 1497 if (c->depth >= DM_BTREE_CURSOR_MAX_DEPTH - 1) {1498 DMERR("couldn't push cursor node, stack depth too high");1499 return -EINVAL;1500 }1501 1502 r = bn_read_lock(c->info, b, &n->b);1503 if (r)1504 return r;1505 1506 n->index = 0;1507 c->depth++;1508 1509 if (c->prefetch_leaves || !leaf_node(c))1510 prefetch_values(c);1511 1512 return 0;1513}1514 1515static void pop_node(struct dm_btree_cursor *c)1516{1517 c->depth--;1518 unlock_block(c->info, c->nodes[c->depth].b);1519}1520 1521static int inc_or_backtrack(struct dm_btree_cursor *c)1522{1523 struct cursor_node *n;1524 struct btree_node *bn;1525 1526 for (;;) {1527 if (!c->depth)1528 return -ENODATA;1529 1530 n = c->nodes + c->depth - 1;1531 bn = dm_block_data(n->b);1532 1533 n->index++;1534 if (n->index < le32_to_cpu(bn->header.nr_entries))1535 break;1536 1537 pop_node(c);1538 }1539 1540 return 0;1541}1542 1543static int find_leaf(struct dm_btree_cursor *c)1544{1545 int r = 0;1546 struct cursor_node *n;1547 struct btree_node *bn;1548 __le64 value_le;1549 1550 for (;;) {1551 n = c->nodes + c->depth - 1;1552 bn = dm_block_data(n->b);1553 1554 if (le32_to_cpu(bn->header.flags) & LEAF_NODE)1555 break;1556 1557 memcpy(&value_le, value_ptr(bn, n->index), sizeof(value_le));1558 r = push_node(c, le64_to_cpu(value_le));1559 if (r) {1560 DMERR("push_node failed");1561 break;1562 }1563 }1564 1565 if (!r && (le32_to_cpu(bn->header.nr_entries) == 0))1566 return -ENODATA;1567 1568 return r;1569}1570 1571int dm_btree_cursor_begin(struct dm_btree_info *info, dm_block_t root,1572 bool prefetch_leaves, struct dm_btree_cursor *c)1573{1574 int r;1575 1576 c->info = info;1577 c->root = root;1578 c->depth = 0;1579 c->prefetch_leaves = prefetch_leaves;1580 1581 r = push_node(c, root);1582 if (r)1583 return r;1584 1585 return find_leaf(c);1586}1587EXPORT_SYMBOL_GPL(dm_btree_cursor_begin);1588 1589void dm_btree_cursor_end(struct dm_btree_cursor *c)1590{1591 while (c->depth)1592 pop_node(c);1593}1594EXPORT_SYMBOL_GPL(dm_btree_cursor_end);1595 1596int dm_btree_cursor_next(struct dm_btree_cursor *c)1597{1598 int r = inc_or_backtrack(c);1599 1600 if (!r) {1601 r = find_leaf(c);1602 if (r)1603 DMERR("find_leaf failed");1604 }1605 1606 return r;1607}1608EXPORT_SYMBOL_GPL(dm_btree_cursor_next);1609 1610int dm_btree_cursor_skip(struct dm_btree_cursor *c, uint32_t count)1611{1612 int r = 0;1613 1614 while (count-- && !r)1615 r = dm_btree_cursor_next(c);1616 1617 return r;1618}1619EXPORT_SYMBOL_GPL(dm_btree_cursor_skip);1620 1621int dm_btree_cursor_get_value(struct dm_btree_cursor *c, uint64_t *key, void *value_le)1622{1623 if (c->depth) {1624 struct cursor_node *n = c->nodes + c->depth - 1;1625 struct btree_node *bn = dm_block_data(n->b);1626 1627 if (le32_to_cpu(bn->header.flags) & INTERNAL_NODE)1628 return -EINVAL;1629 1630 *key = le64_to_cpu(*key_ptr(bn, n->index));1631 memcpy(value_le, value_ptr(bn, n->index), c->info->value_type.size);1632 return 0;1633 1634 } else1635 return -ENODATA;1636}1637EXPORT_SYMBOL_GPL(dm_btree_cursor_get_value);1638