Lines Matching +full:left +full:- +full:shift
1 // SPDX-License-Identifier: GPL-2.0-only
8 #include "dm-btree.h"
9 #include "dm-btree-internal.h"
10 #include "dm-transaction-manager.h"
13 #include <linux/device-mapper.h>
29 * Each node may have a left or right sibling. When decending the spine,
36 * [B] No left sibling
40 * ==> rebalance(left sibling, node)
42 * [D] Both siblings, total_entries(left, node, right) <= DEL_THRESHOLD
43 * ==> delete node adding it's contents to left and right
45 * [E] Both siblings, total_entries(left, node, right) > DEL_THRESHOLD
46 * ==> rebalance(left, node, right)
60 static void node_shift(struct btree_node *n, int shift) in node_shift() argument
62 uint32_t nr_entries = le32_to_cpu(n->header.nr_entries); in node_shift()
63 uint32_t value_size = le32_to_cpu(n->header.value_size); in node_shift()
65 if (shift < 0) { in node_shift()
66 shift = -shift; in node_shift()
67 BUG_ON(shift > nr_entries); in node_shift()
68 BUG_ON((void *) key_ptr(n, shift) >= value_ptr(n, shift)); in node_shift()
70 key_ptr(n, shift), in node_shift()
71 (nr_entries - shift) * sizeof(__le64)); in node_shift()
73 value_ptr(n, shift), in node_shift()
74 (nr_entries - shift) * value_size); in node_shift()
76 BUG_ON(nr_entries + shift > le32_to_cpu(n->header.max_entries)); in node_shift()
77 memmove(key_ptr(n, shift), in node_shift()
80 memmove(value_ptr(n, shift), in node_shift()
86 static int node_copy(struct btree_node *left, struct btree_node *right, int shift) in node_copy() argument
88 uint32_t nr_left = le32_to_cpu(left->header.nr_entries); in node_copy()
89 uint32_t value_size = le32_to_cpu(left->header.value_size); in node_copy()
91 if (value_size != le32_to_cpu(right->header.value_size)) { in node_copy()
93 return -EILSEQ; in node_copy()
96 if (shift < 0) { in node_copy()
97 shift = -shift; in node_copy()
99 if (nr_left + shift > le32_to_cpu(left->header.max_entries)) { in node_copy()
100 DMERR("bad shift"); in node_copy()
101 return -EINVAL; in node_copy()
104 memcpy(key_ptr(left, nr_left), in node_copy()
106 shift * sizeof(__le64)); in node_copy()
107 memcpy(value_ptr(left, nr_left), in node_copy()
109 shift * value_size); in node_copy()
111 if (shift > le32_to_cpu(right->header.max_entries)) { in node_copy()
112 DMERR("bad shift"); in node_copy()
113 return -EINVAL; in node_copy()
117 key_ptr(left, nr_left - shift), in node_copy()
118 shift * sizeof(__le64)); in node_copy()
120 value_ptr(left, nr_left - shift), in node_copy()
121 shift * value_size); in node_copy()
131 unsigned int nr_entries = le32_to_cpu(n->header.nr_entries); in delete_at()
132 unsigned int nr_to_copy = nr_entries - (index + 1); in delete_at()
133 uint32_t value_size = le32_to_cpu(n->header.value_size); in delete_at()
147 n->header.nr_entries = cpu_to_le32(nr_entries - 1); in delete_at()
152 return le32_to_cpu(n->header.max_entries) / 3; in merge_threshold()
168 result->index = index; in init_child()
171 r = dm_tm_shadow_block(info->tm, root, &btree_node_validator, in init_child()
172 &result->block, &inc); in init_child()
176 result->n = dm_block_data(result->block); in init_child()
179 inc_children(info->tm, result->n, vt); in init_child()
182 cpu_to_le64(dm_block_location(result->block)); in init_child()
189 dm_tm_unlock(info->tm, c->block); in exit_child()
192 static int shift(struct btree_node *left, struct btree_node *right, int count) in shift() argument
195 uint32_t nr_left = le32_to_cpu(left->header.nr_entries); in shift()
196 uint32_t nr_right = le32_to_cpu(right->header.nr_entries); in shift()
197 uint32_t max_entries = le32_to_cpu(left->header.max_entries); in shift()
198 uint32_t r_max_entries = le32_to_cpu(right->header.max_entries); in shift()
202 return -EILSEQ; in shift()
205 if (nr_left - count > max_entries) { in shift()
206 DMERR("node shift out of bounds"); in shift()
207 return -EINVAL; in shift()
211 DMERR("node shift out of bounds"); in shift()
212 return -EINVAL; in shift()
220 r = node_copy(left, right, count); in shift()
224 r = node_copy(left, right, count); in shift()
230 left->header.nr_entries = cpu_to_le32(nr_left - count); in shift()
231 right->header.nr_entries = cpu_to_le32(nr_right + count); in shift()
240 struct btree_node *left = l->n; in __rebalance2() local
241 struct btree_node *right = r->n; in __rebalance2()
242 uint32_t nr_left = le32_to_cpu(left->header.nr_entries); in __rebalance2()
243 uint32_t nr_right = le32_to_cpu(right->header.nr_entries); in __rebalance2()
250 unsigned int threshold = 2 * (merge_threshold(left) + 1); in __rebalance2()
256 node_copy(left, right, -nr_right); in __rebalance2()
257 left->header.nr_entries = cpu_to_le32(nr_left + nr_right); in __rebalance2()
258 delete_at(parent, r->index); in __rebalance2()
262 * children, since they're still referenced by left. in __rebalance2()
264 dm_tm_dec(info->tm, dm_block_location(r->block)); in __rebalance2()
271 ret = shift(left, right, nr_left - target_left); in __rebalance2()
274 *key_ptr(parent, r->index) = right->keys[0]; in __rebalance2()
284 struct child left, right; in rebalance2() local
288 r = init_child(info, vt, parent, left_index, &left); in rebalance2()
294 exit_child(info, &left); in rebalance2()
298 r = __rebalance2(info, parent, &left, &right); in rebalance2()
300 exit_child(info, &left); in rebalance2()
307 * We dump as many entries from center as possible into left, then the rest
313 struct btree_node *left, struct btree_node *center, struct btree_node *right, in delete_center_node() argument
316 uint32_t max_entries = le32_to_cpu(left->header.max_entries); in delete_center_node()
317 unsigned int shift = min(max_entries - nr_left, nr_center); in delete_center_node() local
319 if (nr_left + shift > max_entries) { in delete_center_node()
320 DMERR("node shift out of bounds"); in delete_center_node()
321 return -EINVAL; in delete_center_node()
324 node_copy(left, center, -shift); in delete_center_node()
325 left->header.nr_entries = cpu_to_le32(nr_left + shift); in delete_center_node()
327 if (shift != nr_center) { in delete_center_node()
328 shift = nr_center - shift; in delete_center_node()
330 if ((nr_right + shift) > max_entries) { in delete_center_node()
331 DMERR("node shift out of bounds"); in delete_center_node()
332 return -EINVAL; in delete_center_node()
335 node_shift(right, shift); in delete_center_node()
336 node_copy(center, right, shift); in delete_center_node()
337 right->header.nr_entries = cpu_to_le32(nr_right + shift); in delete_center_node()
339 *key_ptr(parent, r->index) = right->keys[0]; in delete_center_node()
341 delete_at(parent, c->index); in delete_center_node()
342 r->index--; in delete_center_node()
344 dm_tm_dec(info->tm, dm_block_location(c->block)); in delete_center_node()
353 struct btree_node *left, struct btree_node *center, struct btree_node *right, in redistribute3() argument
357 uint32_t max_entries = le32_to_cpu(left->header.max_entries); in redistribute3()
367 s = nr_left - target_left; in redistribute3()
369 if (s < 0 && nr_center < -s) { in redistribute3()
371 ret = shift(left, center, -nr_center); in redistribute3()
376 ret = shift(left, right, s); in redistribute3()
382 ret = shift(left, center, s); in redistribute3()
387 ret = shift(center, right, target_right - nr_right); in redistribute3()
391 s = target_right - nr_right; in redistribute3()
394 ret = shift(center, right, nr_center); in redistribute3()
397 s -= nr_center; in redistribute3()
398 ret = shift(left, right, s); in redistribute3()
401 nr_left -= s; in redistribute3()
403 ret = shift(center, right, s); in redistribute3()
408 ret = shift(left, center, nr_left - target_left); in redistribute3()
413 *key_ptr(parent, c->index) = center->keys[0]; in redistribute3()
414 *key_ptr(parent, r->index) = right->keys[0]; in redistribute3()
421 struct btree_node *left = l->n; in __rebalance3() local
422 struct btree_node *center = c->n; in __rebalance3()
423 struct btree_node *right = r->n; in __rebalance3()
425 uint32_t nr_left = le32_to_cpu(left->header.nr_entries); in __rebalance3()
426 uint32_t nr_center = le32_to_cpu(center->header.nr_entries); in __rebalance3()
427 uint32_t nr_right = le32_to_cpu(right->header.nr_entries); in __rebalance3()
429 unsigned int threshold = merge_threshold(left) * 4 + 1; in __rebalance3()
431 if ((left->header.max_entries != center->header.max_entries) || in __rebalance3()
432 (center->header.max_entries != right->header.max_entries)) { in __rebalance3()
434 return -EILSEQ; in __rebalance3()
438 return delete_center_node(info, parent, l, c, r, left, center, right, in __rebalance3()
442 return redistribute3(info, parent, l, c, r, left, center, right, in __rebalance3()
451 struct child left, center, right; in rebalance3() local
456 r = init_child(info, vt, parent, left_index, &left); in rebalance3()
462 exit_child(info, &left); in rebalance3()
468 exit_child(info, &left); in rebalance3()
473 r = __rebalance3(info, parent, &left, ¢er, &right); in rebalance3()
475 exit_child(info, &left); in rebalance3()
491 if (le32_to_cpu(n->header.nr_entries) == 1) { in rebalance_children()
495 r = dm_tm_read_lock(info->tm, b, &btree_node_validator, &child); in rebalance_children()
500 dm_bm_block_size(dm_tm_get_bm(info->tm))); in rebalance_children()
502 dm_tm_dec(info->tm, dm_block_location(child)); in rebalance_children()
503 dm_tm_unlock(info->tm, child); in rebalance_children()
509 return -ENODATA; in rebalance_children()
512 has_right_sibling = i < (le32_to_cpu(n->header.nr_entries) - 1); in rebalance_children()
518 r = rebalance2(s, info, vt, i - 1); in rebalance_children()
521 r = rebalance3(s, info, vt, i - 1); in rebalance_children()
531 (i >= le32_to_cpu(n->header.nr_entries)) || in do_leaf()
532 (le64_to_cpu(n->keys[i]) != key)) in do_leaf()
533 return -ENODATA; in do_leaf()
570 if (le32_to_cpu(n->header.flags) & LEAF_NODE) in remove_raw()
578 if (le32_to_cpu(n->header.flags) & LEAF_NODE) in remove_raw()
586 * -ENODATA in remove_raw()
597 unsigned int level, last_level = info->levels - 1; in dm_btree_remove()
603 init_le64_type(info->tm, &le64_vt); in dm_btree_remove()
605 for (level = 0; level < info->levels; level++) { in dm_btree_remove()
608 &info->value_type : &le64_vt), in dm_btree_remove()
619 BUG_ON(index < 0 || index >= le32_to_cpu(n->header.nr_entries)); in dm_btree_remove()
621 if (info->value_type.dec) in dm_btree_remove()
622 info->value_type.dec(info->value_type.context, in dm_btree_remove()
636 /*----------------------------------------------------------------*/
664 if (le32_to_cpu(n->header.flags) & LEAF_NODE) { in remove_nearest()
674 if (le32_to_cpu(n->header.flags) & LEAF_NODE) { in remove_nearest()
684 * -ENODATA in remove_nearest()
696 unsigned int level, last_level = info->levels - 1; in remove_one()
703 init_le64_type(info->tm, &le64_vt); in remove_one()
715 r = remove_nearest(&spine, info, &info->value_type, in remove_one()
725 if (index >= le32_to_cpu(n->header.nr_entries)) { in remove_one()
726 r = -ENODATA; in remove_one()
730 k = le64_to_cpu(n->keys[index]); in remove_one()
732 if (info->value_type.dec) in remove_one()
733 info->value_type.dec(info->value_type.context, in remove_one()
740 r = -ENODATA; in remove_one()
763 return r == -ENODATA ? 0 : r; in dm_btree_remove_leaves()