Lines Matching +full:top +full:- +full:level
7 #include "dm-btree-internal.h"
8 #include "dm-space-map.h"
9 #include "dm-transaction-manager.h"
12 #include <linux/device-mapper.h>
16 /*----------------------------------------------------------------
18 *--------------------------------------------------------------*/
33 (nr_elts - index) * elt_size); in array_insert()
38 /*----------------------------------------------------------------*/
43 int lo = -1, hi = le32_to_cpu(n->header.nr_entries); in bsearch()
45 while (hi - lo > 1) { in bsearch()
46 int mid = lo + ((hi - lo) / 2); in bsearch()
47 uint64_t mid_key = le64_to_cpu(n->keys[mid]); in bsearch()
74 uint32_t nr_entries = le32_to_cpu(n->header.nr_entries); in inc_children()
76 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) in inc_children()
79 else if (vt->inc) in inc_children()
80 vt->inc(vt->context, value_ptr(n, 0), nr_entries); in inc_children()
87 uint32_t nr_entries = le32_to_cpu(node->header.nr_entries); in insert_at()
91 index >= le32_to_cpu(node->header.max_entries)) { in insert_at()
94 return -ENOMEM; in insert_at()
99 array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le); in insert_at()
101 node->header.nr_entries = cpu_to_le32(nr_entries + 1); in insert_at()
106 /*----------------------------------------------------------------*/
117 block_size -= sizeof(struct node_header); in calc_max_entries()
136 block_size = dm_bm_block_size(dm_tm_get_bm(info->tm)); in dm_btree_empty()
137 max_entries = calc_max_entries(info->value_type.size, block_size); in dm_btree_empty()
141 n->header.flags = cpu_to_le32(LEAF_NODE); in dm_btree_empty()
142 n->header.nr_entries = cpu_to_le32(0); in dm_btree_empty()
143 n->header.max_entries = cpu_to_le32(max_entries); in dm_btree_empty()
144 n->header.value_size = cpu_to_le32(info->value_type.size); in dm_btree_empty()
153 /*----------------------------------------------------------------*/
163 unsigned level; member
171 int top; member
177 if (s->top < 0) { in top_frame()
179 return -EINVAL; in top_frame()
182 *f = s->spine + s->top; in top_frame()
189 return s->top >= 0; in unprocessed_frames()
195 struct dm_block_manager *bm = dm_tm_get_bm(s->tm); in prefetch_children()
197 for (i = 0; i < f->nr_children; i++) in prefetch_children()
198 dm_bm_prefetch(bm, value64(f->n, i)); in prefetch_children()
203 return f->level < (info->levels - 1); in is_internal_level()
206 static int push_frame(struct del_stack *s, dm_block_t b, unsigned level) in push_frame() argument
211 if (s->top >= MAX_SPINE_DEPTH - 1) { in push_frame()
213 return -ENOMEM; in push_frame()
216 r = dm_tm_ref(s->tm, b, &ref_count); in push_frame()
225 dm_tm_dec(s->tm, b); in push_frame()
229 struct frame *f = s->spine + ++s->top; in push_frame()
231 r = dm_tm_read_lock(s->tm, b, &btree_node_validator, &f->b); in push_frame()
233 s->top--; in push_frame()
237 f->n = dm_block_data(f->b); in push_frame()
238 f->level = level; in push_frame()
239 f->nr_children = le32_to_cpu(f->n->header.nr_entries); in push_frame()
240 f->current_child = 0; in push_frame()
242 flags = le32_to_cpu(f->n->header.flags); in push_frame()
243 if (flags & INTERNAL_NODE || is_internal_level(s->info, f)) in push_frame()
252 struct frame *f = s->spine + s->top--; in pop_frame()
254 dm_tm_dec(s->tm, dm_block_location(f->b)); in pop_frame()
255 dm_tm_unlock(s->tm, f->b); in pop_frame()
263 f = s->spine + s->top--; in unlock_all_frames()
264 dm_tm_unlock(s->tm, f->b); in unlock_all_frames()
280 return -ENOMEM; in dm_btree_del()
281 s->info = info; in dm_btree_del()
282 s->tm = info->tm; in dm_btree_del()
283 s->top = -1; in dm_btree_del()
298 if (f->current_child >= f->nr_children) { in dm_btree_del()
303 flags = le32_to_cpu(f->n->header.flags); in dm_btree_del()
305 b = value64(f->n, f->current_child); in dm_btree_del()
306 f->current_child++; in dm_btree_del()
307 r = push_frame(s, b, f->level); in dm_btree_del()
312 b = value64(f->n, f->current_child); in dm_btree_del()
313 f->current_child++; in dm_btree_del()
314 r = push_frame(s, b, f->level + 1); in dm_btree_del()
319 if (info->value_type.dec) in dm_btree_del()
320 info->value_type.dec(info->value_type.context, in dm_btree_del()
321 value_ptr(f->n, 0), f->nr_children); in dm_btree_del()
336 /*----------------------------------------------------------------*/
352 flags = le32_to_cpu(ro_node(s)->header.flags); in btree_lookup_raw()
353 nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries); in btree_lookup_raw()
355 return -ENODATA; in btree_lookup_raw()
362 *result_key = le64_to_cpu(ro_node(s)->keys[i]); in btree_lookup_raw()
372 unsigned level, last_level = info->levels - 1; in dm_btree_lookup() local
373 int r = -ENODATA; in dm_btree_lookup()
379 for (level = 0; level < info->levels; level++) { in dm_btree_lookup()
383 if (level == last_level) { in dm_btree_lookup()
385 size = info->value_type.size; in dm_btree_lookup()
392 r = btree_lookup_raw(&spine, root, keys[level], in dm_btree_lookup()
397 if (rkey != keys[level]) { in dm_btree_lookup()
399 return -ENODATA; in dm_btree_lookup()
427 flags = le32_to_cpu(n->header.flags); in dm_btree_lookup_next_single()
428 nr_entries = le32_to_cpu(n->header.nr_entries); in dm_btree_lookup_next_single()
434 * avoid early -ENODATA return when all entries are in dm_btree_lookup_next_single()
440 r = -ENODATA; in dm_btree_lookup_next_single()
445 if (r == -ENODATA && i < (nr_entries - 1)) { in dm_btree_lookup_next_single()
453 r = -ENODATA; in dm_btree_lookup_next_single()
457 *rkey = le64_to_cpu(n->keys[i]); in dm_btree_lookup_next_single()
458 memcpy(value_le, value_ptr(n, i), info->value_type.size); in dm_btree_lookup_next_single()
461 dm_tm_unlock(info->tm, node); in dm_btree_lookup_next_single()
468 unsigned level; in dm_btree_lookup_next() local
469 int r = -ENODATA; in dm_btree_lookup_next()
474 for (level = 0; level < info->levels - 1u; level++) { in dm_btree_lookup_next()
475 r = btree_lookup_raw(&spine, root, keys[level], in dm_btree_lookup_next()
481 if (*rkey != keys[level]) { in dm_btree_lookup_next()
482 r = -ENODATA; in dm_btree_lookup_next()
489 r = dm_btree_lookup_next_single(info, root, keys[level], rkey, value_le); in dm_btree_lookup_next()
497 /*----------------------------------------------------------------*/
507 size_t value_size = le32_to_cpu(dest->header.value_size); in copy_entries()
508 memcpy(dest->keys + dest_offset, src->keys + src_offset, count * sizeof(uint64_t)); in copy_entries()
520 size_t value_size = le32_to_cpu(dest->header.value_size); in move_entries()
521 memmove(dest->keys + dest_offset, src->keys + src_offset, count * sizeof(uint64_t)); in move_entries()
531 move_entries(n, 0, n, count, le32_to_cpu(n->header.nr_entries) - count); in shift_down()
540 move_entries(n, count, n, 0, le32_to_cpu(n->header.nr_entries)); in shift_up()
549 unsigned nr_left = le32_to_cpu(left->header.nr_entries); in redistribute2()
550 unsigned nr_right = le32_to_cpu(right->header.nr_entries); in redistribute2()
553 unsigned target_right = total - target_left; in redistribute2()
556 unsigned delta = target_left - nr_left; in redistribute2()
560 unsigned delta = nr_left - target_left; in redistribute2()
566 left->header.nr_entries = cpu_to_le32(target_left); in redistribute2()
567 right->header.nr_entries = cpu_to_le32(target_right); in redistribute2()
577 unsigned nr_left = le32_to_cpu(left->header.nr_entries); in redistribute3()
578 unsigned nr_center = le32_to_cpu(center->header.nr_entries); in redistribute3()
579 unsigned nr_right = le32_to_cpu(right->header.nr_entries); in redistribute3()
586 target_center = (total - target_left) / 2; in redistribute3()
587 target_right = (total - target_left - target_center); in redistribute3()
590 unsigned left_short = target_left - nr_left; in redistribute3()
593 shift_down(right, nr_right - target_right); in redistribute3()
596 unsigned left_to_center = nr_left - target_left; in redistribute3()
598 copy_entries(center, left_to_center, right, 0, target_center - left_to_center); in redistribute3()
599 shift_down(right, nr_right - target_right); in redistribute3()
602 unsigned right_short = target_right - nr_right; in redistribute3()
604 copy_entries(right, 0, left, nr_left - right_short, right_short); in redistribute3()
605 copy_entries(center, 0, left, target_left, nr_left - target_left); in redistribute3()
608 left->header.nr_entries = cpu_to_le32(target_left); in redistribute3()
609 center->header.nr_entries = cpu_to_le32(target_center); in redistribute3()
610 right->header.nr_entries = cpu_to_le32(target_right); in redistribute3()
619 * +--------+
621 * +--------+
624 * +----------+
626 * +----------+
630 * +--------+
632 * +--------+
634 * v +------+
635 * +---------+ |
637 * +---------+ +-------+
639 * +-------+
653 r = new_block(s->info, &right); in split_one_into_two()
660 rn->header.flags = ln->header.flags; in split_one_into_two()
661 rn->header.nr_entries = cpu_to_le32(0); in split_one_into_two()
662 rn->header.max_entries = ln->header.max_entries; in split_one_into_two()
663 rn->header.value_size = ln->header.value_size; in split_one_into_two()
673 le64_to_cpu(rn->keys[0]), &location); in split_one_into_two()
675 unlock_block(s->info, right); in split_one_into_two()
680 if (key < le64_to_cpu(rn->keys[0])) { in split_one_into_two()
681 unlock_block(s->info, right); in split_one_into_two()
682 s->nodes[1] = left; in split_one_into_two()
684 unlock_block(s->info, left); in split_one_into_two()
685 s->nodes[1] = right; in split_one_into_two()
706 r = dm_tm_shadow_block(info->tm, root, &btree_node_validator, in shadow_child()
714 inc_children(info->tm, node, vt); in shadow_child()
741 r = shadow_child(s->info, vt, pn, parent_index + 1, &right); in split_two_into_three()
747 r = shadow_child(s->info, vt, pn, parent_index - 1, &left); in split_two_into_three()
752 r = new_block(s->info, &middle); in split_two_into_three()
760 mn->header.nr_entries = cpu_to_le32(0); in split_two_into_three()
761 mn->header.flags = ln->header.flags; in split_two_into_three()
762 mn->header.max_entries = ln->header.max_entries; in split_two_into_three()
763 mn->header.value_size = ln->header.value_size; in split_two_into_three()
768 pn->keys[middle_index] = rn->keys[0]; in split_two_into_three()
772 le64_to_cpu(mn->keys[0]), &location); in split_two_into_three()
775 unlock_block(s->info, left); in split_two_into_three()
777 unlock_block(s->info, middle); in split_two_into_three()
780 unlock_block(s->info, right); in split_two_into_three()
787 if (key < le64_to_cpu(mn->keys[0])) { in split_two_into_three()
788 unlock_block(s->info, middle); in split_two_into_three()
789 unlock_block(s->info, right); in split_two_into_three()
790 s->nodes[1] = left; in split_two_into_three()
791 } else if (key < le64_to_cpu(rn->keys[0])) { in split_two_into_three()
792 unlock_block(s->info, left); in split_two_into_three()
793 unlock_block(s->info, right); in split_two_into_three()
794 s->nodes[1] = middle; in split_two_into_three()
796 unlock_block(s->info, left); in split_two_into_three()
797 unlock_block(s->info, middle); in split_two_into_three()
798 s->nodes[1] = right; in split_two_into_three()
804 /*----------------------------------------------------------------*/
810 * +----------+
812 * +----------+
816 * +------------+
818 * +------------+
820 * +------+ +----+
823 * +-------+ +-------+
825 * +-------+ +-------+
839 size = le32_to_cpu(pn->header.flags) & INTERNAL_NODE ? in btree_split_beneath()
840 sizeof(__le64) : s->info->value_type.size; in btree_split_beneath()
843 r = new_block(s->info, &left); in btree_split_beneath()
848 nr_left = le32_to_cpu(pn->header.nr_entries) / 2; in btree_split_beneath()
850 ln->header.flags = pn->header.flags; in btree_split_beneath()
851 ln->header.nr_entries = cpu_to_le32(nr_left); in btree_split_beneath()
852 ln->header.max_entries = pn->header.max_entries; in btree_split_beneath()
853 ln->header.value_size = pn->header.value_size; in btree_split_beneath()
854 memcpy(ln->keys, pn->keys, nr_left * sizeof(pn->keys[0])); in btree_split_beneath()
858 r = new_block(s->info, &right); in btree_split_beneath()
860 unlock_block(s->info, left); in btree_split_beneath()
865 nr_right = le32_to_cpu(pn->header.nr_entries) - nr_left; in btree_split_beneath()
867 rn->header.flags = pn->header.flags; in btree_split_beneath()
868 rn->header.nr_entries = cpu_to_le32(nr_right); in btree_split_beneath()
869 rn->header.max_entries = pn->header.max_entries; in btree_split_beneath()
870 rn->header.value_size = pn->header.value_size; in btree_split_beneath()
871 memcpy(rn->keys, pn->keys + nr_left, nr_right * sizeof(pn->keys[0])); in btree_split_beneath()
876 pn->header.flags = cpu_to_le32(INTERNAL_NODE); in btree_split_beneath()
877 pn->header.nr_entries = cpu_to_le32(2); in btree_split_beneath()
878 pn->header.max_entries = cpu_to_le32( in btree_split_beneath()
881 dm_tm_get_bm(s->info->tm)))); in btree_split_beneath()
882 pn->header.value_size = cpu_to_le32(sizeof(__le64)); in btree_split_beneath()
886 pn->keys[0] = ln->keys[0]; in btree_split_beneath()
891 pn->keys[1] = rn->keys[0]; in btree_split_beneath()
894 unlock_block(s->info, left); in btree_split_beneath()
895 unlock_block(s->info, right); in btree_split_beneath()
899 /*----------------------------------------------------------------*/
911 r = shadow_child(s->info, vt, parent, parent_index - 1, &sib); in rebalance_left()
918 *key_ptr(parent, parent_index) = right->keys[0]; in rebalance_left()
920 if (key < le64_to_cpu(right->keys[0])) { in rebalance_left()
921 unlock_block(s->info, s->nodes[1]); in rebalance_left()
922 s->nodes[1] = sib; in rebalance_left()
924 unlock_block(s->info, sib); in rebalance_left()
940 r = shadow_child(s->info, vt, parent, parent_index + 1, &sib); in rebalance_right()
947 *key_ptr(parent, parent_index + 1) = right->keys[0]; in rebalance_right()
949 if (key < le64_to_cpu(right->keys[0])) { in rebalance_right()
950 unlock_block(s->info, sib); in rebalance_right()
952 unlock_block(s->info, s->nodes[1]); in rebalance_right()
953 s->nodes[1] = sib; in rebalance_right()
974 nr_entries = le32_to_cpu(node->header.nr_entries); in get_node_free_space()
975 *space = le32_to_cpu(node->header.max_entries) - nr_entries; in get_node_free_space()
995 unsigned nr_parent = le32_to_cpu(parent->header.nr_entries); in rebalance_or_split()
1001 dm_block_t left_b = value64(parent, parent_index - 1); in rebalance_or_split()
1002 r = dm_tm_block_is_shared(s->info->tm, left_b, &left_shared); in rebalance_or_split()
1007 r = get_node_free_space(s->info, left_b, &free_space); in rebalance_or_split()
1017 if (parent_index < (nr_parent - 1)) { in rebalance_or_split()
1019 r = dm_tm_block_is_shared(s->info->tm, right_b, &right_shared); in rebalance_or_split()
1024 r = get_node_free_space(s->info, right_b, &free_space); in rebalance_or_split()
1054 if (i >= 0 && le64_to_cpu(node->keys[i]) == key) in contains_key()
1067 if (node->header.nr_entries == node->header.max_entries) { in has_space_for_insert()
1068 if (le32_to_cpu(node->header.flags) & LEAF_NODE) { in has_space_for_insert()
1083 int r, i = *index, top = 1; in btree_insert_raw() local
1109 if (top) in btree_insert_raw()
1123 if (le32_to_cpu(node->header.flags) & LEAF_NODE) in btree_insert_raw()
1128 node->keys[0] = cpu_to_le64(key); in btree_insert_raw()
1133 top = 0; in btree_insert_raw()
1136 if (i < 0 || le64_to_cpu(node->keys[i]) != key) in btree_insert_raw()
1146 int r, i = -1; in __btree_get_overwrite_leaf()
1151 r = shadow_step(s, root, &s->info->value_type); in __btree_get_overwrite_leaf()
1174 BUG_ON(i >= le32_to_cpu(node->header.nr_entries)); in __btree_get_overwrite_leaf()
1176 if (le32_to_cpu(node->header.flags) & LEAF_NODE) { in __btree_get_overwrite_leaf()
1177 if (key != le64_to_cpu(node->keys[i])) in __btree_get_overwrite_leaf()
1178 return -EINVAL; in __btree_get_overwrite_leaf()
1196 BUG_ON(info->levels > 1); in btree_get_overwrite_leaf()
1207 spine.count--; in btree_get_overwrite_leaf()
1215 unsigned level, unsigned index) in need_insert() argument
1217 return ((index >= le32_to_cpu(node->header.nr_entries)) || in need_insert()
1218 (le64_to_cpu(node->keys[index]) != keys[level])); in need_insert()
1227 unsigned level, index = -1, last_level = info->levels - 1; in insert() local
1233 init_le64_type(info->tm, &le64_type); in insert()
1236 for (level = 0; level < (info->levels - 1); level++) { in insert()
1237 r = btree_insert_raw(&spine, block, &le64_type, keys[level], &index); in insert()
1243 if (need_insert(n, keys, level, index)) { in insert()
1255 keys[level], &new_le); in insert()
1260 if (level < last_level) in insert()
1264 r = btree_insert_raw(&spine, block, &info->value_type, in insert()
1265 keys[level], &index); in insert()
1271 if (need_insert(n, keys, level, index)) { in insert()
1275 r = insert_at(info->value_type.size, n, index, in insert()
1276 keys[level], value); in insert()
1283 if (info->value_type.dec && in insert()
1284 (!info->value_type.equal || in insert()
1285 !info->value_type.equal( in insert()
1286 info->value_type.context, in insert()
1289 info->value_type.dec(info->value_type.context, in insert()
1293 value, info->value_type.size); in insert()
1325 /*----------------------------------------------------------------*/
1338 flags = le32_to_cpu(ro_node(s)->header.flags); in find_key()
1339 i = le32_to_cpu(ro_node(s)->header.nr_entries); in find_key()
1341 return -ENODATA; in find_key()
1343 i--; in find_key()
1346 *result_key = le64_to_cpu(ro_node(s)->keys[i]); in find_key()
1348 *result_key = le64_to_cpu(ro_node(s)->keys[0]); in find_key()
1367 int r = 0, count = 0, level; in dm_btree_find_key() local
1371 for (level = 0; level < info->levels; level++) { in dm_btree_find_key()
1372 r = find_key(&spine, root, find_highest, result_keys + level, in dm_btree_find_key()
1373 level == info->levels - 1 ? NULL : &root); in dm_btree_find_key()
1374 if (r == -ENODATA) { in dm_btree_find_key()
1402 /*----------------------------------------------------------------*/
1406 * space. Also this only works for single level trees.
1424 nr = le32_to_cpu(n->header.nr_entries); in walk_node()
1426 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) { in walk_node()
1439 dm_tm_unlock(info->tm, node); in walk_node()
1447 BUG_ON(info->levels > 1); in dm_btree_walk()
1452 /*----------------------------------------------------------------*/
1458 struct cursor_node *n = c->nodes + c->depth - 1; in prefetch_values()
1459 struct btree_node *bn = dm_block_data(n->b); in prefetch_values()
1460 struct dm_block_manager *bm = dm_tm_get_bm(c->info->tm); in prefetch_values()
1462 BUG_ON(c->info->value_type.size != sizeof(value_le)); in prefetch_values()
1464 nr = le32_to_cpu(bn->header.nr_entries); in prefetch_values()
1473 struct cursor_node *n = c->nodes + c->depth - 1; in leaf_node()
1474 struct btree_node *bn = dm_block_data(n->b); in leaf_node()
1476 return le32_to_cpu(bn->header.flags) & LEAF_NODE; in leaf_node()
1482 struct cursor_node *n = c->nodes + c->depth; in push_node()
1484 if (c->depth >= DM_BTREE_CURSOR_MAX_DEPTH - 1) { in push_node()
1486 return -EINVAL; in push_node()
1489 r = bn_read_lock(c->info, b, &n->b); in push_node()
1493 n->index = 0; in push_node()
1494 c->depth++; in push_node()
1496 if (c->prefetch_leaves || !leaf_node(c)) in push_node()
1504 c->depth--; in pop_node()
1505 unlock_block(c->info, c->nodes[c->depth].b); in pop_node()
1514 if (!c->depth) in inc_or_backtrack()
1515 return -ENODATA; in inc_or_backtrack()
1517 n = c->nodes + c->depth - 1; in inc_or_backtrack()
1518 bn = dm_block_data(n->b); in inc_or_backtrack()
1520 n->index++; in inc_or_backtrack()
1521 if (n->index < le32_to_cpu(bn->header.nr_entries)) in inc_or_backtrack()
1538 n = c->nodes + c->depth - 1; in find_leaf()
1539 bn = dm_block_data(n->b); in find_leaf()
1541 if (le32_to_cpu(bn->header.flags) & LEAF_NODE) in find_leaf()
1544 memcpy(&value_le, value_ptr(bn, n->index), sizeof(value_le)); in find_leaf()
1552 if (!r && (le32_to_cpu(bn->header.nr_entries) == 0)) in find_leaf()
1553 return -ENODATA; in find_leaf()
1563 c->info = info; in dm_btree_cursor_begin()
1564 c->root = root; in dm_btree_cursor_begin()
1565 c->depth = 0; in dm_btree_cursor_begin()
1566 c->prefetch_leaves = prefetch_leaves; in dm_btree_cursor_begin()
1578 while (c->depth) in dm_btree_cursor_end()
1600 while (count-- && !r) in dm_btree_cursor_skip()
1609 if (c->depth) { in dm_btree_cursor_get_value()
1610 struct cursor_node *n = c->nodes + c->depth - 1; in dm_btree_cursor_get_value()
1611 struct btree_node *bn = dm_block_data(n->b); in dm_btree_cursor_get_value()
1613 if (le32_to_cpu(bn->header.flags) & INTERNAL_NODE) in dm_btree_cursor_get_value()
1614 return -EINVAL; in dm_btree_cursor_get_value()
1616 *key = le64_to_cpu(*key_ptr(bn, n->index)); in dm_btree_cursor_get_value()
1617 memcpy(value_le, value_ptr(bn, n->index), c->info->value_type.size); in dm_btree_cursor_get_value()
1621 return -ENODATA; in dm_btree_cursor_get_value()