Lines Matching +full:high +full:- +full:vt
1 // SPDX-License-Identifier: GPL-2.0-only
8 #include "dm-btree-internal.h"
9 #include "dm-space-map.h"
10 #include "dm-transaction-manager.h"
13 #include <linux/device-mapper.h>
18 *--------------------------------------------------------------
20 *--------------------------------------------------------------
36 (nr_elts - index) * elt_size); in array_insert()
41 /*----------------------------------------------------------------*/
46 int lo = -1, hi = le32_to_cpu(n->header.nr_entries); in bsearch()
48 while (hi - lo > 1) { in bsearch()
49 int mid = lo + ((hi - lo) / 2); in bsearch()
50 uint64_t mid_key = le64_to_cpu(n->keys[mid]); in bsearch()
75 struct dm_btree_value_type *vt) in inc_children() argument
77 uint32_t nr_entries = le32_to_cpu(n->header.nr_entries); in inc_children()
79 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) in inc_children()
82 else if (vt->inc) in inc_children()
83 vt->inc(vt->context, value_ptr(n, 0), nr_entries); in inc_children()
90 uint32_t nr_entries = le32_to_cpu(node->header.nr_entries); in insert_at()
91 uint32_t max_entries = le32_to_cpu(node->header.max_entries); in insert_at()
99 return -ENOMEM; in insert_at()
104 array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le); in insert_at()
106 node->header.nr_entries = cpu_to_le32(nr_entries + 1); in insert_at()
111 /*----------------------------------------------------------------*/
122 block_size -= sizeof(struct node_header); in calc_max_entries()
141 block_size = dm_bm_block_size(dm_tm_get_bm(info->tm)); in dm_btree_empty()
142 max_entries = calc_max_entries(info->value_type.size, block_size); in dm_btree_empty()
146 n->header.flags = cpu_to_le32(LEAF_NODE); in dm_btree_empty()
147 n->header.nr_entries = cpu_to_le32(0); in dm_btree_empty()
148 n->header.max_entries = cpu_to_le32(max_entries); in dm_btree_empty()
149 n->header.value_size = cpu_to_le32(info->value_type.size); in dm_btree_empty()
158 /*----------------------------------------------------------------*/
182 if (s->top < 0) { in top_frame()
184 return -EINVAL; in top_frame()
187 *f = s->spine + s->top; in top_frame()
194 return s->top >= 0; in unprocessed_frames()
200 struct dm_block_manager *bm = dm_tm_get_bm(s->tm); in prefetch_children()
202 for (i = 0; i < f->nr_children; i++) in prefetch_children()
203 dm_bm_prefetch(bm, value64(f->n, i)); in prefetch_children()
208 return f->level < (info->levels - 1); in is_internal_level()
216 if (s->top >= MAX_SPINE_DEPTH - 1) { in push_frame()
218 return -ENOMEM; in push_frame()
221 r = dm_tm_ref(s->tm, b, &ref_count); in push_frame()
230 dm_tm_dec(s->tm, b); in push_frame()
234 struct frame *f = s->spine + ++s->top; in push_frame()
236 r = dm_tm_read_lock(s->tm, b, &btree_node_validator, &f->b); in push_frame()
238 s->top--; in push_frame()
242 f->n = dm_block_data(f->b); in push_frame()
243 f->level = level; in push_frame()
244 f->nr_children = le32_to_cpu(f->n->header.nr_entries); in push_frame()
245 f->current_child = 0; in push_frame()
247 flags = le32_to_cpu(f->n->header.flags); in push_frame()
248 if (flags & INTERNAL_NODE || is_internal_level(s->info, f)) in push_frame()
257 struct frame *f = s->spine + s->top--; in pop_frame()
259 dm_tm_dec(s->tm, dm_block_location(f->b)); in pop_frame()
260 dm_tm_unlock(s->tm, f->b); in pop_frame()
268 f = s->spine + s->top--; in unlock_all_frames()
269 dm_tm_unlock(s->tm, f->b); in unlock_all_frames()
285 return -ENOMEM; in dm_btree_del()
286 s->info = info; in dm_btree_del()
287 s->tm = info->tm; in dm_btree_del()
288 s->top = -1; in dm_btree_del()
303 if (f->current_child >= f->nr_children) { in dm_btree_del()
308 flags = le32_to_cpu(f->n->header.flags); in dm_btree_del()
310 b = value64(f->n, f->current_child); in dm_btree_del()
311 f->current_child++; in dm_btree_del()
312 r = push_frame(s, b, f->level); in dm_btree_del()
317 b = value64(f->n, f->current_child); in dm_btree_del()
318 f->current_child++; in dm_btree_del()
319 r = push_frame(s, b, f->level + 1); in dm_btree_del()
324 if (info->value_type.dec) in dm_btree_del()
325 info->value_type.dec(info->value_type.context, in dm_btree_del()
326 value_ptr(f->n, 0), f->nr_children); in dm_btree_del()
341 /*----------------------------------------------------------------*/
357 flags = le32_to_cpu(ro_node(s)->header.flags); in btree_lookup_raw()
358 nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries); in btree_lookup_raw()
360 return -ENODATA; in btree_lookup_raw()
367 *result_key = le64_to_cpu(ro_node(s)->keys[i]); in btree_lookup_raw()
377 unsigned int level, last_level = info->levels - 1; in dm_btree_lookup()
378 int r = -ENODATA; in dm_btree_lookup()
384 for (level = 0; level < info->levels; level++) { in dm_btree_lookup()
390 size = info->value_type.size; in dm_btree_lookup()
404 return -ENODATA; in dm_btree_lookup()
432 flags = le32_to_cpu(n->header.flags); in dm_btree_lookup_next_single()
433 nr_entries = le32_to_cpu(n->header.nr_entries); in dm_btree_lookup_next_single()
439 * avoid early -ENODATA return when all entries are in dm_btree_lookup_next_single()
445 r = -ENODATA; in dm_btree_lookup_next_single()
450 if (r == -ENODATA && i < (nr_entries - 1)) { in dm_btree_lookup_next_single()
458 r = -ENODATA; in dm_btree_lookup_next_single()
462 *rkey = le64_to_cpu(n->keys[i]); in dm_btree_lookup_next_single()
463 memcpy(value_le, value_ptr(n, i), info->value_type.size); in dm_btree_lookup_next_single()
466 dm_tm_unlock(info->tm, node); in dm_btree_lookup_next_single()
474 int r = -ENODATA; in dm_btree_lookup_next()
479 for (level = 0; level < info->levels - 1u; level++) { in dm_btree_lookup_next()
487 r = -ENODATA; in dm_btree_lookup_next()
501 /*----------------------------------------------------------------*/
511 size_t value_size = le32_to_cpu(dest->header.value_size); in copy_entries()
513 memcpy(dest->keys + dest_offset, src->keys + src_offset, count * sizeof(uint64_t)); in copy_entries()
525 size_t value_size = le32_to_cpu(dest->header.value_size); in move_entries()
527 memmove(dest->keys + dest_offset, src->keys + src_offset, count * sizeof(uint64_t)); in move_entries()
537 move_entries(n, 0, n, count, le32_to_cpu(n->header.nr_entries) - count); in shift_down()
546 move_entries(n, count, n, 0, le32_to_cpu(n->header.nr_entries)); in shift_up()
555 unsigned int nr_left = le32_to_cpu(left->header.nr_entries); in redistribute2()
556 unsigned int nr_right = le32_to_cpu(right->header.nr_entries); in redistribute2()
559 unsigned int target_right = total - target_left; in redistribute2()
562 unsigned int delta = target_left - nr_left; in redistribute2()
567 unsigned int delta = nr_left - target_left; in redistribute2()
574 left->header.nr_entries = cpu_to_le32(target_left); in redistribute2()
575 right->header.nr_entries = cpu_to_le32(target_right); in redistribute2()
585 unsigned int nr_left = le32_to_cpu(left->header.nr_entries); in redistribute3()
586 unsigned int nr_center = le32_to_cpu(center->header.nr_entries); in redistribute3()
587 unsigned int nr_right = le32_to_cpu(right->header.nr_entries); in redistribute3()
594 target_center = (total - target_left) / 2; in redistribute3()
595 target_right = (total - target_left - target_center); in redistribute3()
598 unsigned int left_short = target_left - nr_left; in redistribute3()
602 shift_down(right, nr_right - target_right); in redistribute3()
605 unsigned int left_to_center = nr_left - target_left; in redistribute3()
608 copy_entries(center, left_to_center, right, 0, target_center - left_to_center); in redistribute3()
609 shift_down(right, nr_right - target_right); in redistribute3()
612 unsigned int right_short = target_right - nr_right; in redistribute3()
615 copy_entries(right, 0, left, nr_left - right_short, right_short); in redistribute3()
616 copy_entries(center, 0, left, target_left, nr_left - target_left); in redistribute3()
619 left->header.nr_entries = cpu_to_le32(target_left); in redistribute3()
620 center->header.nr_entries = cpu_to_le32(target_center); in redistribute3()
621 right->header.nr_entries = cpu_to_le32(target_right); in redistribute3()
630 * +--------+
632 * +--------+
635 * +----------+
637 * +----------+
641 * +--------+
643 * +--------+
645 * v +------+
646 * +---------+ |
648 * +---------+ +-------+
650 * +-------+
655 struct dm_btree_value_type *vt, uint64_t key) in split_one_into_two() argument
664 r = new_block(s->info, &right); in split_one_into_two()
671 rn->header.flags = ln->header.flags; in split_one_into_two()
672 rn->header.nr_entries = cpu_to_le32(0); in split_one_into_two()
673 rn->header.max_entries = ln->header.max_entries; in split_one_into_two()
674 rn->header.value_size = ln->header.value_size; in split_one_into_two()
684 le64_to_cpu(rn->keys[0]), &location); in split_one_into_two()
686 unlock_block(s->info, right); in split_one_into_two()
691 if (key < le64_to_cpu(rn->keys[0])) { in split_one_into_two()
692 unlock_block(s->info, right); in split_one_into_two()
693 s->nodes[1] = left; in split_one_into_two()
695 unlock_block(s->info, left); in split_one_into_two()
696 s->nodes[1] = right; in split_one_into_two()
707 static int shadow_child(struct dm_btree_info *info, struct dm_btree_value_type *vt, in shadow_child() argument
717 r = dm_tm_shadow_block(info->tm, root, &btree_node_validator, in shadow_child()
725 inc_children(info->tm, node, vt); in shadow_child()
738 struct dm_btree_value_type *vt, uint64_t key) in split_two_into_three() argument
752 r = shadow_child(s->info, vt, pn, parent_index + 1, &right); in split_two_into_three()
758 r = shadow_child(s->info, vt, pn, parent_index - 1, &left); in split_two_into_three()
763 r = new_block(s->info, &middle); in split_two_into_three()
771 mn->header.nr_entries = cpu_to_le32(0); in split_two_into_three()
772 mn->header.flags = ln->header.flags; in split_two_into_three()
773 mn->header.max_entries = ln->header.max_entries; in split_two_into_three()
774 mn->header.value_size = ln->header.value_size; in split_two_into_three()
779 pn->keys[middle_index] = rn->keys[0]; in split_two_into_three()
783 le64_to_cpu(mn->keys[0]), &location); in split_two_into_three()
786 unlock_block(s->info, left); in split_two_into_three()
788 unlock_block(s->info, middle); in split_two_into_three()
791 unlock_block(s->info, right); in split_two_into_three()
798 if (key < le64_to_cpu(mn->keys[0])) { in split_two_into_three()
799 unlock_block(s->info, middle); in split_two_into_three()
800 unlock_block(s->info, right); in split_two_into_three()
801 s->nodes[1] = left; in split_two_into_three()
802 } else if (key < le64_to_cpu(rn->keys[0])) { in split_two_into_three()
803 unlock_block(s->info, left); in split_two_into_three()
804 unlock_block(s->info, right); in split_two_into_three()
805 s->nodes[1] = middle; in split_two_into_three()
807 unlock_block(s->info, left); in split_two_into_three()
808 unlock_block(s->info, middle); in split_two_into_three()
809 s->nodes[1] = right; in split_two_into_three()
815 /*----------------------------------------------------------------*/
821 * +----------+
823 * +----------+
827 * +------------+
829 * +------------+
831 * +------+ +----+
834 * +-------+ +-------+
836 * +-------+ +-------+
850 size = le32_to_cpu(pn->header.flags) & INTERNAL_NODE ? in btree_split_beneath()
851 sizeof(__le64) : s->info->value_type.size; in btree_split_beneath()
854 r = new_block(s->info, &left); in btree_split_beneath()
859 nr_left = le32_to_cpu(pn->header.nr_entries) / 2; in btree_split_beneath()
861 ln->header.flags = pn->header.flags; in btree_split_beneath()
862 ln->header.nr_entries = cpu_to_le32(nr_left); in btree_split_beneath()
863 ln->header.max_entries = pn->header.max_entries; in btree_split_beneath()
864 ln->header.value_size = pn->header.value_size; in btree_split_beneath()
865 memcpy(ln->keys, pn->keys, nr_left * sizeof(pn->keys[0])); in btree_split_beneath()
869 r = new_block(s->info, &right); in btree_split_beneath()
871 unlock_block(s->info, left); in btree_split_beneath()
876 nr_right = le32_to_cpu(pn->header.nr_entries) - nr_left; in btree_split_beneath()
878 rn->header.flags = pn->header.flags; in btree_split_beneath()
879 rn->header.nr_entries = cpu_to_le32(nr_right); in btree_split_beneath()
880 rn->header.max_entries = pn->header.max_entries; in btree_split_beneath()
881 rn->header.value_size = pn->header.value_size; in btree_split_beneath()
882 memcpy(rn->keys, pn->keys + nr_left, nr_right * sizeof(pn->keys[0])); in btree_split_beneath()
887 pn->header.flags = cpu_to_le32(INTERNAL_NODE); in btree_split_beneath()
888 pn->header.nr_entries = cpu_to_le32(2); in btree_split_beneath()
889 pn->header.max_entries = cpu_to_le32( in btree_split_beneath()
892 dm_tm_get_bm(s->info->tm)))); in btree_split_beneath()
893 pn->header.value_size = cpu_to_le32(sizeof(__le64)); in btree_split_beneath()
897 pn->keys[0] = ln->keys[0]; in btree_split_beneath()
902 pn->keys[1] = rn->keys[0]; in btree_split_beneath()
905 unlock_block(s->info, left); in btree_split_beneath()
906 unlock_block(s->info, right); in btree_split_beneath()
910 /*----------------------------------------------------------------*/
915 static int rebalance_left(struct shadow_spine *s, struct dm_btree_value_type *vt, in rebalance_left() argument
922 r = shadow_child(s->info, vt, parent, parent_index - 1, &sib); in rebalance_left()
929 *key_ptr(parent, parent_index) = right->keys[0]; in rebalance_left()
931 if (key < le64_to_cpu(right->keys[0])) { in rebalance_left()
932 unlock_block(s->info, s->nodes[1]); in rebalance_left()
933 s->nodes[1] = sib; in rebalance_left()
935 unlock_block(s->info, sib); in rebalance_left()
944 static int rebalance_right(struct shadow_spine *s, struct dm_btree_value_type *vt, in rebalance_right() argument
951 r = shadow_child(s->info, vt, parent, parent_index + 1, &sib); in rebalance_right()
958 *key_ptr(parent, parent_index + 1) = right->keys[0]; in rebalance_right()
960 if (key < le64_to_cpu(right->keys[0])) { in rebalance_right()
961 unlock_block(s->info, sib); in rebalance_right()
963 unlock_block(s->info, s->nodes[1]); in rebalance_right()
964 s->nodes[1] = sib; in rebalance_right()
985 nr_entries = le32_to_cpu(node->header.nr_entries); in get_node_free_space()
986 *space = le32_to_cpu(node->header.max_entries) - nr_entries; in get_node_free_space()
1001 static int rebalance_or_split(struct shadow_spine *s, struct dm_btree_value_type *vt, in rebalance_or_split() argument
1006 unsigned int nr_parent = le32_to_cpu(parent->header.nr_entries); in rebalance_or_split()
1012 dm_block_t left_b = value64(parent, parent_index - 1); in rebalance_or_split()
1014 r = dm_tm_block_is_shared(s->info->tm, left_b, &left_shared); in rebalance_or_split()
1019 r = get_node_free_space(s->info, left_b, &free_space); in rebalance_or_split()
1024 return rebalance_left(s, vt, parent_index, key); in rebalance_or_split()
1029 if (parent_index < (nr_parent - 1)) { in rebalance_or_split()
1032 r = dm_tm_block_is_shared(s->info->tm, right_b, &right_shared); in rebalance_or_split()
1037 r = get_node_free_space(s->info, right_b, &free_space); in rebalance_or_split()
1042 return rebalance_right(s, vt, parent_index, key); in rebalance_or_split()
1054 return split_one_into_two(s, parent_index, vt, key); in rebalance_or_split()
1056 return split_two_into_three(s, parent_index, vt, key); in rebalance_or_split()
1067 if (i >= 0 && le64_to_cpu(node->keys[i]) == key) in contains_key()
1080 if (node->header.nr_entries == node->header.max_entries) { in has_space_for_insert()
1081 if (le32_to_cpu(node->header.flags) & LEAF_NODE) { in has_space_for_insert()
1093 struct dm_btree_value_type *vt, in btree_insert_raw() argument
1100 r = shadow_step(s, root, vt); in btree_insert_raw()
1125 r = rebalance_or_split(s, vt, i, key); in btree_insert_raw()
1136 if (le32_to_cpu(node->header.flags) & LEAF_NODE) in btree_insert_raw()
1141 node->keys[0] = cpu_to_le64(key); in btree_insert_raw()
1149 if (i < 0 || le64_to_cpu(node->keys[i]) != key) in btree_insert_raw()
1159 int r, i = -1; in __btree_get_overwrite_leaf()
1164 r = shadow_step(s, root, &s->info->value_type); in __btree_get_overwrite_leaf()
1187 BUG_ON(i >= le32_to_cpu(node->header.nr_entries)); in __btree_get_overwrite_leaf()
1189 if (le32_to_cpu(node->header.flags) & LEAF_NODE) { in __btree_get_overwrite_leaf()
1190 if (key != le64_to_cpu(node->keys[i])) in __btree_get_overwrite_leaf()
1191 return -EINVAL; in __btree_get_overwrite_leaf()
1209 BUG_ON(info->levels > 1); in btree_get_overwrite_leaf()
1220 spine.count--; in btree_get_overwrite_leaf()
1230 return ((index >= le32_to_cpu(node->header.nr_entries)) || in need_insert()
1231 (le64_to_cpu(node->keys[index]) != keys[level])); in need_insert()
1240 unsigned int level, index = -1, last_level = info->levels - 1; in insert()
1246 init_le64_type(info->tm, &le64_type); in insert()
1249 for (level = 0; level < (info->levels - 1); level++) { in insert()
1277 r = btree_insert_raw(&spine, block, &info->value_type, in insert()
1288 r = insert_at(info->value_type.size, n, index, in insert()
1296 if (info->value_type.dec && in insert()
1297 (!info->value_type.equal || in insert()
1298 !info->value_type.equal( in insert()
1299 info->value_type.context, in insert()
1302 info->value_type.dec(info->value_type.context, in insert()
1306 value, info->value_type.size); in insert()
1338 /*----------------------------------------------------------------*/
1351 flags = le32_to_cpu(ro_node(s)->header.flags); in find_key()
1352 i = le32_to_cpu(ro_node(s)->header.nr_entries); in find_key()
1354 return -ENODATA; in find_key()
1356 i--; in find_key()
1359 *result_key = le64_to_cpu(ro_node(s)->keys[i]); in find_key()
1361 *result_key = le64_to_cpu(ro_node(s)->keys[0]); in find_key()
1384 for (level = 0; level < info->levels; level++) { in dm_btree_find_key()
1386 level == info->levels - 1 ? NULL : &root); in dm_btree_find_key()
1387 if (r == -ENODATA) { in dm_btree_find_key()
1415 /*----------------------------------------------------------------*/
1437 nr = le32_to_cpu(n->header.nr_entries); in walk_node()
1439 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) { in walk_node()
1452 dm_tm_unlock(info->tm, node); in walk_node()
1460 BUG_ON(info->levels > 1); in dm_btree_walk()
1465 /*----------------------------------------------------------------*/
1471 struct cursor_node *n = c->nodes + c->depth - 1; in prefetch_values()
1472 struct btree_node *bn = dm_block_data(n->b); in prefetch_values()
1473 struct dm_block_manager *bm = dm_tm_get_bm(c->info->tm); in prefetch_values()
1475 BUG_ON(c->info->value_type.size != sizeof(value_le)); in prefetch_values()
1477 nr = le32_to_cpu(bn->header.nr_entries); in prefetch_values()
1486 struct cursor_node *n = c->nodes + c->depth - 1; in leaf_node()
1487 struct btree_node *bn = dm_block_data(n->b); in leaf_node()
1489 return le32_to_cpu(bn->header.flags) & LEAF_NODE; in leaf_node()
1495 struct cursor_node *n = c->nodes + c->depth; in push_node()
1497 if (c->depth >= DM_BTREE_CURSOR_MAX_DEPTH - 1) { in push_node()
1498 DMERR("couldn't push cursor node, stack depth too high"); in push_node()
1499 return -EINVAL; in push_node()
1502 r = bn_read_lock(c->info, b, &n->b); in push_node()
1506 n->index = 0; in push_node()
1507 c->depth++; in push_node()
1509 if (c->prefetch_leaves || !leaf_node(c)) in push_node()
1517 c->depth--; in pop_node()
1518 unlock_block(c->info, c->nodes[c->depth].b); in pop_node()
1527 if (!c->depth) in inc_or_backtrack()
1528 return -ENODATA; in inc_or_backtrack()
1530 n = c->nodes + c->depth - 1; in inc_or_backtrack()
1531 bn = dm_block_data(n->b); in inc_or_backtrack()
1533 n->index++; in inc_or_backtrack()
1534 if (n->index < le32_to_cpu(bn->header.nr_entries)) in inc_or_backtrack()
1551 n = c->nodes + c->depth - 1; in find_leaf()
1552 bn = dm_block_data(n->b); in find_leaf()
1554 if (le32_to_cpu(bn->header.flags) & LEAF_NODE) in find_leaf()
1557 memcpy(&value_le, value_ptr(bn, n->index), sizeof(value_le)); in find_leaf()
1565 if (!r && (le32_to_cpu(bn->header.nr_entries) == 0)) in find_leaf()
1566 return -ENODATA; in find_leaf()
1576 c->info = info; in dm_btree_cursor_begin()
1577 c->root = root; in dm_btree_cursor_begin()
1578 c->depth = 0; in dm_btree_cursor_begin()
1579 c->prefetch_leaves = prefetch_leaves; in dm_btree_cursor_begin()
1591 while (c->depth) in dm_btree_cursor_end()
1614 while (count-- && !r) in dm_btree_cursor_skip()
1623 if (c->depth) { in dm_btree_cursor_get_value()
1624 struct cursor_node *n = c->nodes + c->depth - 1; in dm_btree_cursor_get_value()
1625 struct btree_node *bn = dm_block_data(n->b); in dm_btree_cursor_get_value()
1627 if (le32_to_cpu(bn->header.flags) & INTERNAL_NODE) in dm_btree_cursor_get_value()
1628 return -EINVAL; in dm_btree_cursor_get_value()
1630 *key = le64_to_cpu(*key_ptr(bn, n->index)); in dm_btree_cursor_get_value()
1631 memcpy(value_le, value_ptr(bn, n->index), c->info->value_type.size); in dm_btree_cursor_get_value()
1635 return -ENODATA; in dm_btree_cursor_get_value()