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()
88 uint32_t max_entries = le32_to_cpu(node->header.max_entries); in insert_at()
96 return -ENOMEM; in insert_at()
101 array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le); in insert_at()
103 node->header.nr_entries = cpu_to_le32(nr_entries + 1); in insert_at()
108 /*----------------------------------------------------------------*/
119 block_size -= sizeof(struct node_header); in calc_max_entries()
138 block_size = dm_bm_block_size(dm_tm_get_bm(info->tm)); in dm_btree_empty()
139 max_entries = calc_max_entries(info->value_type.size, block_size); in dm_btree_empty()
143 n->header.flags = cpu_to_le32(LEAF_NODE); in dm_btree_empty()
144 n->header.nr_entries = cpu_to_le32(0); in dm_btree_empty()
145 n->header.max_entries = cpu_to_le32(max_entries); in dm_btree_empty()
146 n->header.value_size = cpu_to_le32(info->value_type.size); in dm_btree_empty()
155 /*----------------------------------------------------------------*/
165 unsigned level; member
173 int top; member
179 if (s->top < 0) { in top_frame()
181 return -EINVAL; in top_frame()
184 *f = s->spine + s->top; in top_frame()
191 return s->top >= 0; in unprocessed_frames()
197 struct dm_block_manager *bm = dm_tm_get_bm(s->tm); in prefetch_children()
199 for (i = 0; i < f->nr_children; i++) in prefetch_children()
200 dm_bm_prefetch(bm, value64(f->n, i)); in prefetch_children()
205 return f->level < (info->levels - 1); in is_internal_level()
208 static int push_frame(struct del_stack *s, dm_block_t b, unsigned level) in push_frame() argument
213 if (s->top >= MAX_SPINE_DEPTH - 1) { in push_frame()
215 return -ENOMEM; in push_frame()
218 r = dm_tm_ref(s->tm, b, &ref_count); in push_frame()
227 dm_tm_dec(s->tm, b); in push_frame()
231 struct frame *f = s->spine + ++s->top; in push_frame()
233 r = dm_tm_read_lock(s->tm, b, &btree_node_validator, &f->b); in push_frame()
235 s->top--; in push_frame()
239 f->n = dm_block_data(f->b); in push_frame()
240 f->level = level; in push_frame()
241 f->nr_children = le32_to_cpu(f->n->header.nr_entries); in push_frame()
242 f->current_child = 0; in push_frame()
244 flags = le32_to_cpu(f->n->header.flags); in push_frame()
245 if (flags & INTERNAL_NODE || is_internal_level(s->info, f)) in push_frame()
254 struct frame *f = s->spine + s->top--; in pop_frame()
256 dm_tm_dec(s->tm, dm_block_location(f->b)); in pop_frame()
257 dm_tm_unlock(s->tm, f->b); in pop_frame()
265 f = s->spine + s->top--; in unlock_all_frames()
266 dm_tm_unlock(s->tm, f->b); in unlock_all_frames()
282 return -ENOMEM; in dm_btree_del()
283 s->info = info; in dm_btree_del()
284 s->tm = info->tm; in dm_btree_del()
285 s->top = -1; in dm_btree_del()
300 if (f->current_child >= f->nr_children) { in dm_btree_del()
305 flags = le32_to_cpu(f->n->header.flags); in dm_btree_del()
307 b = value64(f->n, f->current_child); in dm_btree_del()
308 f->current_child++; in dm_btree_del()
309 r = push_frame(s, b, f->level); in dm_btree_del()
314 b = value64(f->n, f->current_child); in dm_btree_del()
315 f->current_child++; in dm_btree_del()
316 r = push_frame(s, b, f->level + 1); in dm_btree_del()
321 if (info->value_type.dec) in dm_btree_del()
322 info->value_type.dec(info->value_type.context, in dm_btree_del()
323 value_ptr(f->n, 0), f->nr_children); in dm_btree_del()
338 /*----------------------------------------------------------------*/
354 flags = le32_to_cpu(ro_node(s)->header.flags); in btree_lookup_raw()
355 nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries); in btree_lookup_raw()
357 return -ENODATA; in btree_lookup_raw()
364 *result_key = le64_to_cpu(ro_node(s)->keys[i]); in btree_lookup_raw()
374 unsigned level, last_level = info->levels - 1; in dm_btree_lookup() local
375 int r = -ENODATA; in dm_btree_lookup()
381 for (level = 0; level < info->levels; level++) { in dm_btree_lookup()
385 if (level == last_level) { in dm_btree_lookup()
387 size = info->value_type.size; in dm_btree_lookup()
394 r = btree_lookup_raw(&spine, root, keys[level], in dm_btree_lookup()
399 if (rkey != keys[level]) { in dm_btree_lookup()
401 return -ENODATA; in dm_btree_lookup()
429 flags = le32_to_cpu(n->header.flags); in dm_btree_lookup_next_single()
430 nr_entries = le32_to_cpu(n->header.nr_entries); in dm_btree_lookup_next_single()
436 * avoid early -ENODATA return when all entries are in dm_btree_lookup_next_single()
442 r = -ENODATA; in dm_btree_lookup_next_single()
447 if (r == -ENODATA && i < (nr_entries - 1)) { in dm_btree_lookup_next_single()
455 r = -ENODATA; in dm_btree_lookup_next_single()
459 *rkey = le64_to_cpu(n->keys[i]); in dm_btree_lookup_next_single()
460 memcpy(value_le, value_ptr(n, i), info->value_type.size); in dm_btree_lookup_next_single()
463 dm_tm_unlock(info->tm, node); in dm_btree_lookup_next_single()
470 unsigned level; in dm_btree_lookup_next() local
471 int r = -ENODATA; in dm_btree_lookup_next()
476 for (level = 0; level < info->levels - 1u; level++) { in dm_btree_lookup_next()
477 r = btree_lookup_raw(&spine, root, keys[level], in dm_btree_lookup_next()
483 if (*rkey != keys[level]) { in dm_btree_lookup_next()
484 r = -ENODATA; in dm_btree_lookup_next()
491 r = dm_btree_lookup_next_single(info, root, keys[level], rkey, value_le); in dm_btree_lookup_next()
499 /*----------------------------------------------------------------*/
509 size_t value_size = le32_to_cpu(dest->header.value_size); in copy_entries()
510 memcpy(dest->keys + dest_offset, src->keys + src_offset, count * sizeof(uint64_t)); in copy_entries()
522 size_t value_size = le32_to_cpu(dest->header.value_size); in move_entries()
523 memmove(dest->keys + dest_offset, src->keys + src_offset, count * sizeof(uint64_t)); in move_entries()
533 move_entries(n, 0, n, count, le32_to_cpu(n->header.nr_entries) - count); in shift_down()
542 move_entries(n, count, n, 0, le32_to_cpu(n->header.nr_entries)); in shift_up()
551 unsigned nr_left = le32_to_cpu(left->header.nr_entries); in redistribute2()
552 unsigned nr_right = le32_to_cpu(right->header.nr_entries); in redistribute2()
555 unsigned target_right = total - target_left; in redistribute2()
558 unsigned delta = target_left - nr_left; in redistribute2()
562 unsigned delta = nr_left - target_left; in redistribute2()
568 left->header.nr_entries = cpu_to_le32(target_left); in redistribute2()
569 right->header.nr_entries = cpu_to_le32(target_right); in redistribute2()
579 unsigned nr_left = le32_to_cpu(left->header.nr_entries); in redistribute3()
580 unsigned nr_center = le32_to_cpu(center->header.nr_entries); in redistribute3()
581 unsigned nr_right = le32_to_cpu(right->header.nr_entries); in redistribute3()
588 target_center = (total - target_left) / 2; in redistribute3()
589 target_right = (total - target_left - target_center); in redistribute3()
592 unsigned left_short = target_left - nr_left; in redistribute3()
595 shift_down(right, nr_right - target_right); in redistribute3()
598 unsigned left_to_center = nr_left - target_left; in redistribute3()
600 copy_entries(center, left_to_center, right, 0, target_center - left_to_center); in redistribute3()
601 shift_down(right, nr_right - target_right); in redistribute3()
604 unsigned right_short = target_right - nr_right; in redistribute3()
606 copy_entries(right, 0, left, nr_left - right_short, right_short); in redistribute3()
607 copy_entries(center, 0, left, target_left, nr_left - target_left); in redistribute3()
610 left->header.nr_entries = cpu_to_le32(target_left); in redistribute3()
611 center->header.nr_entries = cpu_to_le32(target_center); in redistribute3()
612 right->header.nr_entries = cpu_to_le32(target_right); in redistribute3()
621 * +--------+
623 * +--------+
626 * +----------+
628 * +----------+
632 * +--------+
634 * +--------+
636 * v +------+
637 * +---------+ |
639 * +---------+ +-------+
641 * +-------+
655 r = new_block(s->info, &right); in split_one_into_two()
662 rn->header.flags = ln->header.flags; in split_one_into_two()
663 rn->header.nr_entries = cpu_to_le32(0); in split_one_into_two()
664 rn->header.max_entries = ln->header.max_entries; in split_one_into_two()
665 rn->header.value_size = ln->header.value_size; in split_one_into_two()
675 le64_to_cpu(rn->keys[0]), &location); in split_one_into_two()
677 unlock_block(s->info, right); in split_one_into_two()
682 if (key < le64_to_cpu(rn->keys[0])) { in split_one_into_two()
683 unlock_block(s->info, right); in split_one_into_two()
684 s->nodes[1] = left; in split_one_into_two()
686 unlock_block(s->info, left); in split_one_into_two()
687 s->nodes[1] = right; in split_one_into_two()
708 r = dm_tm_shadow_block(info->tm, root, &btree_node_validator, in shadow_child()
716 inc_children(info->tm, node, vt); in shadow_child()
743 r = shadow_child(s->info, vt, pn, parent_index + 1, &right); in split_two_into_three()
749 r = shadow_child(s->info, vt, pn, parent_index - 1, &left); in split_two_into_three()
754 r = new_block(s->info, &middle); in split_two_into_three()
762 mn->header.nr_entries = cpu_to_le32(0); in split_two_into_three()
763 mn->header.flags = ln->header.flags; in split_two_into_three()
764 mn->header.max_entries = ln->header.max_entries; in split_two_into_three()
765 mn->header.value_size = ln->header.value_size; in split_two_into_three()
770 pn->keys[middle_index] = rn->keys[0]; in split_two_into_three()
774 le64_to_cpu(mn->keys[0]), &location); in split_two_into_three()
777 unlock_block(s->info, left); in split_two_into_three()
779 unlock_block(s->info, middle); in split_two_into_three()
782 unlock_block(s->info, right); in split_two_into_three()
789 if (key < le64_to_cpu(mn->keys[0])) { in split_two_into_three()
790 unlock_block(s->info, middle); in split_two_into_three()
791 unlock_block(s->info, right); in split_two_into_three()
792 s->nodes[1] = left; in split_two_into_three()
793 } else if (key < le64_to_cpu(rn->keys[0])) { in split_two_into_three()
794 unlock_block(s->info, left); in split_two_into_three()
795 unlock_block(s->info, right); in split_two_into_three()
796 s->nodes[1] = middle; in split_two_into_three()
798 unlock_block(s->info, left); in split_two_into_three()
799 unlock_block(s->info, middle); in split_two_into_three()
800 s->nodes[1] = right; in split_two_into_three()
806 /*----------------------------------------------------------------*/
812 * +----------+
814 * +----------+
818 * +------------+
820 * +------------+
822 * +------+ +----+
825 * +-------+ +-------+
827 * +-------+ +-------+
841 size = le32_to_cpu(pn->header.flags) & INTERNAL_NODE ? in btree_split_beneath()
842 sizeof(__le64) : s->info->value_type.size; in btree_split_beneath()
845 r = new_block(s->info, &left); in btree_split_beneath()
850 nr_left = le32_to_cpu(pn->header.nr_entries) / 2; in btree_split_beneath()
852 ln->header.flags = pn->header.flags; in btree_split_beneath()
853 ln->header.nr_entries = cpu_to_le32(nr_left); in btree_split_beneath()
854 ln->header.max_entries = pn->header.max_entries; in btree_split_beneath()
855 ln->header.value_size = pn->header.value_size; in btree_split_beneath()
856 memcpy(ln->keys, pn->keys, nr_left * sizeof(pn->keys[0])); in btree_split_beneath()
860 r = new_block(s->info, &right); in btree_split_beneath()
862 unlock_block(s->info, left); in btree_split_beneath()
867 nr_right = le32_to_cpu(pn->header.nr_entries) - nr_left; in btree_split_beneath()
869 rn->header.flags = pn->header.flags; in btree_split_beneath()
870 rn->header.nr_entries = cpu_to_le32(nr_right); in btree_split_beneath()
871 rn->header.max_entries = pn->header.max_entries; in btree_split_beneath()
872 rn->header.value_size = pn->header.value_size; in btree_split_beneath()
873 memcpy(rn->keys, pn->keys + nr_left, nr_right * sizeof(pn->keys[0])); in btree_split_beneath()
878 pn->header.flags = cpu_to_le32(INTERNAL_NODE); in btree_split_beneath()
879 pn->header.nr_entries = cpu_to_le32(2); in btree_split_beneath()
880 pn->header.max_entries = cpu_to_le32( in btree_split_beneath()
883 dm_tm_get_bm(s->info->tm)))); in btree_split_beneath()
884 pn->header.value_size = cpu_to_le32(sizeof(__le64)); in btree_split_beneath()
888 pn->keys[0] = ln->keys[0]; in btree_split_beneath()
893 pn->keys[1] = rn->keys[0]; in btree_split_beneath()
896 unlock_block(s->info, left); in btree_split_beneath()
897 unlock_block(s->info, right); in btree_split_beneath()
901 /*----------------------------------------------------------------*/
913 r = shadow_child(s->info, vt, parent, parent_index - 1, &sib); in rebalance_left()
920 *key_ptr(parent, parent_index) = right->keys[0]; in rebalance_left()
922 if (key < le64_to_cpu(right->keys[0])) { in rebalance_left()
923 unlock_block(s->info, s->nodes[1]); in rebalance_left()
924 s->nodes[1] = sib; in rebalance_left()
926 unlock_block(s->info, sib); in rebalance_left()
942 r = shadow_child(s->info, vt, parent, parent_index + 1, &sib); in rebalance_right()
949 *key_ptr(parent, parent_index + 1) = right->keys[0]; in rebalance_right()
951 if (key < le64_to_cpu(right->keys[0])) { in rebalance_right()
952 unlock_block(s->info, sib); in rebalance_right()
954 unlock_block(s->info, s->nodes[1]); in rebalance_right()
955 s->nodes[1] = sib; in rebalance_right()
976 nr_entries = le32_to_cpu(node->header.nr_entries); in get_node_free_space()
977 *space = le32_to_cpu(node->header.max_entries) - nr_entries; in get_node_free_space()
997 unsigned nr_parent = le32_to_cpu(parent->header.nr_entries); in rebalance_or_split()
1003 dm_block_t left_b = value64(parent, parent_index - 1); in rebalance_or_split()
1004 r = dm_tm_block_is_shared(s->info->tm, left_b, &left_shared); in rebalance_or_split()
1009 r = get_node_free_space(s->info, left_b, &free_space); in rebalance_or_split()
1019 if (parent_index < (nr_parent - 1)) { in rebalance_or_split()
1021 r = dm_tm_block_is_shared(s->info->tm, right_b, &right_shared); in rebalance_or_split()
1026 r = get_node_free_space(s->info, right_b, &free_space); in rebalance_or_split()
1056 if (i >= 0 && le64_to_cpu(node->keys[i]) == key) in contains_key()
1069 if (node->header.nr_entries == node->header.max_entries) { in has_space_for_insert()
1070 if (le32_to_cpu(node->header.flags) & LEAF_NODE) { in has_space_for_insert()
1085 int r, i = *index, top = 1; in btree_insert_raw() local
1111 if (top) in btree_insert_raw()
1125 if (le32_to_cpu(node->header.flags) & LEAF_NODE) in btree_insert_raw()
1130 node->keys[0] = cpu_to_le64(key); in btree_insert_raw()
1135 top = 0; in btree_insert_raw()
1138 if (i < 0 || le64_to_cpu(node->keys[i]) != key) in btree_insert_raw()
1148 int r, i = -1; in __btree_get_overwrite_leaf()
1153 r = shadow_step(s, root, &s->info->value_type); in __btree_get_overwrite_leaf()
1176 BUG_ON(i >= le32_to_cpu(node->header.nr_entries)); in __btree_get_overwrite_leaf()
1178 if (le32_to_cpu(node->header.flags) & LEAF_NODE) { in __btree_get_overwrite_leaf()
1179 if (key != le64_to_cpu(node->keys[i])) in __btree_get_overwrite_leaf()
1180 return -EINVAL; in __btree_get_overwrite_leaf()
1198 BUG_ON(info->levels > 1); in btree_get_overwrite_leaf()
1209 spine.count--; in btree_get_overwrite_leaf()
1217 unsigned level, unsigned index) in need_insert() argument
1219 return ((index >= le32_to_cpu(node->header.nr_entries)) || in need_insert()
1220 (le64_to_cpu(node->keys[index]) != keys[level])); in need_insert()
1229 unsigned level, index = -1, last_level = info->levels - 1; in insert() local
1235 init_le64_type(info->tm, &le64_type); in insert()
1238 for (level = 0; level < (info->levels - 1); level++) { in insert()
1239 r = btree_insert_raw(&spine, block, &le64_type, keys[level], &index); in insert()
1245 if (need_insert(n, keys, level, index)) { in insert()
1257 keys[level], &new_le); in insert()
1262 if (level < last_level) in insert()
1266 r = btree_insert_raw(&spine, block, &info->value_type, in insert()
1267 keys[level], &index); in insert()
1273 if (need_insert(n, keys, level, index)) { in insert()
1277 r = insert_at(info->value_type.size, n, index, in insert()
1278 keys[level], value); in insert()
1285 if (info->value_type.dec && in insert()
1286 (!info->value_type.equal || in insert()
1287 !info->value_type.equal( in insert()
1288 info->value_type.context, in insert()
1291 info->value_type.dec(info->value_type.context, in insert()
1295 value, info->value_type.size); in insert()
1327 /*----------------------------------------------------------------*/
1340 flags = le32_to_cpu(ro_node(s)->header.flags); in find_key()
1341 i = le32_to_cpu(ro_node(s)->header.nr_entries); in find_key()
1343 return -ENODATA; in find_key()
1345 i--; in find_key()
1348 *result_key = le64_to_cpu(ro_node(s)->keys[i]); in find_key()
1350 *result_key = le64_to_cpu(ro_node(s)->keys[0]); in find_key()
1369 int r = 0, count = 0, level; in dm_btree_find_key() local
1373 for (level = 0; level < info->levels; level++) { in dm_btree_find_key()
1374 r = find_key(&spine, root, find_highest, result_keys + level, in dm_btree_find_key()
1375 level == info->levels - 1 ? NULL : &root); in dm_btree_find_key()
1376 if (r == -ENODATA) { in dm_btree_find_key()
1404 /*----------------------------------------------------------------*/
1408 * space. Also this only works for single level trees.
1426 nr = le32_to_cpu(n->header.nr_entries); in walk_node()
1428 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) { in walk_node()
1441 dm_tm_unlock(info->tm, node); in walk_node()
1449 BUG_ON(info->levels > 1); in dm_btree_walk()
1454 /*----------------------------------------------------------------*/
1460 struct cursor_node *n = c->nodes + c->depth - 1; in prefetch_values()
1461 struct btree_node *bn = dm_block_data(n->b); in prefetch_values()
1462 struct dm_block_manager *bm = dm_tm_get_bm(c->info->tm); in prefetch_values()
1464 BUG_ON(c->info->value_type.size != sizeof(value_le)); in prefetch_values()
1466 nr = le32_to_cpu(bn->header.nr_entries); in prefetch_values()
1475 struct cursor_node *n = c->nodes + c->depth - 1; in leaf_node()
1476 struct btree_node *bn = dm_block_data(n->b); in leaf_node()
1478 return le32_to_cpu(bn->header.flags) & LEAF_NODE; in leaf_node()
1484 struct cursor_node *n = c->nodes + c->depth; in push_node()
1486 if (c->depth >= DM_BTREE_CURSOR_MAX_DEPTH - 1) { in push_node()
1488 return -EINVAL; in push_node()
1491 r = bn_read_lock(c->info, b, &n->b); in push_node()
1495 n->index = 0; in push_node()
1496 c->depth++; in push_node()
1498 if (c->prefetch_leaves || !leaf_node(c)) in push_node()
1506 c->depth--; in pop_node()
1507 unlock_block(c->info, c->nodes[c->depth].b); in pop_node()
1516 if (!c->depth) in inc_or_backtrack()
1517 return -ENODATA; in inc_or_backtrack()
1519 n = c->nodes + c->depth - 1; in inc_or_backtrack()
1520 bn = dm_block_data(n->b); in inc_or_backtrack()
1522 n->index++; in inc_or_backtrack()
1523 if (n->index < le32_to_cpu(bn->header.nr_entries)) in inc_or_backtrack()
1540 n = c->nodes + c->depth - 1; in find_leaf()
1541 bn = dm_block_data(n->b); in find_leaf()
1543 if (le32_to_cpu(bn->header.flags) & LEAF_NODE) in find_leaf()
1546 memcpy(&value_le, value_ptr(bn, n->index), sizeof(value_le)); in find_leaf()
1554 if (!r && (le32_to_cpu(bn->header.nr_entries) == 0)) in find_leaf()
1555 return -ENODATA; in find_leaf()
1565 c->info = info; in dm_btree_cursor_begin()
1566 c->root = root; in dm_btree_cursor_begin()
1567 c->depth = 0; in dm_btree_cursor_begin()
1568 c->prefetch_leaves = prefetch_leaves; in dm_btree_cursor_begin()
1580 while (c->depth) in dm_btree_cursor_end()
1602 while (count-- && !r) in dm_btree_cursor_skip()
1611 if (c->depth) { in dm_btree_cursor_get_value()
1612 struct cursor_node *n = c->nodes + c->depth - 1; in dm_btree_cursor_get_value()
1613 struct btree_node *bn = dm_block_data(n->b); in dm_btree_cursor_get_value()
1615 if (le32_to_cpu(bn->header.flags) & INTERNAL_NODE) in dm_btree_cursor_get_value()
1616 return -EINVAL; in dm_btree_cursor_get_value()
1618 *key = le64_to_cpu(*key_ptr(bn, n->index)); in dm_btree_cursor_get_value()
1619 memcpy(value_le, value_ptr(bn, n->index), c->info->value_type.size); in dm_btree_cursor_get_value()
1623 return -ENODATA; in dm_btree_cursor_get_value()