xref: /linux/drivers/md/persistent-data/dm-btree-remove.c (revision 624d146d97c5fbe7200ef4b2dd5350ecf57d6b79)
1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * Copyright (C) 2011 Red Hat, Inc.
4  *
5  * This file is released under the GPL.
6  */
7 
8 #include "dm-btree.h"
9 #include "dm-btree-internal.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  * Removing an entry from a btree
19  * ==============================
20  *
21  * A very important constraint for our btree is that no node, except the
22  * root, may have fewer than a certain number of entries.
23  * (MIN_ENTRIES <= nr_entries <= MAX_ENTRIES).
24  *
25  * Ensuring this is complicated by the way we want to only ever hold the
26  * locks on 2 nodes concurrently, and only change nodes in a top to bottom
27  * fashion.
28  *
29  * Each node may have a left or right sibling.  When decending the spine,
30  * if a node contains only MIN_ENTRIES then we try and increase this to at
31  * least MIN_ENTRIES + 1.  We do this in the following ways:
32  *
33  * [A] No siblings => this can only happen if the node is the root, in which
34  *     case we copy the children contents over the root.
35  *
36  * [B] No left sibling
37  *     ==> rebalance(node, right sibling)
38  *
39  * [C] No right sibling
40  *     ==> rebalance(left sibling, node)
41  *
42  * [D] Both siblings, total_entries(left, node, right) <= DEL_THRESHOLD
43  *     ==> delete node adding it's contents to left and right
44  *
45  * [E] Both siblings, total_entries(left, node, right) > DEL_THRESHOLD
46  *     ==> rebalance(left, node, right)
47  *
48  * After these operations it's possible that the our original node no
49  * longer contains the desired sub tree.  For this reason this rebalancing
50  * is performed on the children of the current node.  This also avoids
51  * having a special case for the root.
52  *
53  * Once this rebalancing has occurred we can then step into the child node
54  * for internal nodes.  Or delete the entry for leaf nodes.
55  */
56 
57 /*
58  * Some little utilities for moving node data around.
59  */
60 static void node_shift(struct btree_node *n, int shift)
61 {
62 	uint32_t nr_entries = le32_to_cpu(n->header.nr_entries);
63 	uint32_t value_size = le32_to_cpu(n->header.value_size);
64 
65 	if (shift < 0) {
66 		shift = -shift;
67 		BUG_ON(shift > nr_entries);
68 		BUG_ON((void *) key_ptr(n, shift) >= value_ptr(n, shift));
69 		memmove(key_ptr(n, 0),
70 			key_ptr(n, shift),
71 			(nr_entries - shift) * sizeof(__le64));
72 		memmove(value_ptr(n, 0),
73 			value_ptr(n, shift),
74 			(nr_entries - shift) * value_size);
75 	} else {
76 		BUG_ON(nr_entries + shift > le32_to_cpu(n->header.max_entries));
77 		memmove(key_ptr(n, shift),
78 			key_ptr(n, 0),
79 			nr_entries * sizeof(__le64));
80 		memmove(value_ptr(n, shift),
81 			value_ptr(n, 0),
82 			nr_entries * value_size);
83 	}
84 }
85 
86 static int node_copy(struct btree_node *left, struct btree_node *right, int shift)
87 {
88 	uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
89 	uint32_t value_size = le32_to_cpu(left->header.value_size);
90 
91 	if (value_size != le32_to_cpu(right->header.value_size)) {
92 		DMERR("mismatched value size");
93 		return -EILSEQ;
94 	}
95 
96 	if (shift < 0) {
97 		shift = -shift;
98 
99 		if (nr_left + shift > le32_to_cpu(left->header.max_entries)) {
100 			DMERR("bad shift");
101 			return -EINVAL;
102 		}
103 
104 		memcpy(key_ptr(left, nr_left),
105 		       key_ptr(right, 0),
106 		       shift * sizeof(__le64));
107 		memcpy(value_ptr(left, nr_left),
108 		       value_ptr(right, 0),
109 		       shift * value_size);
110 	} else {
111 		if (shift > le32_to_cpu(right->header.max_entries)) {
112 			DMERR("bad shift");
113 			return -EINVAL;
114 		}
115 
116 		memcpy(key_ptr(right, 0),
117 		       key_ptr(left, nr_left - shift),
118 		       shift * sizeof(__le64));
119 		memcpy(value_ptr(right, 0),
120 		       value_ptr(left, nr_left - shift),
121 		       shift * value_size);
122 	}
123 	return 0;
124 }
125 
126 /*
127  * Delete a specific entry from a leaf node.
128  */
129 static void delete_at(struct btree_node *n, unsigned int index)
130 {
131 	unsigned int nr_entries = le32_to_cpu(n->header.nr_entries);
132 	unsigned int nr_to_copy = nr_entries - (index + 1);
133 	uint32_t value_size = le32_to_cpu(n->header.value_size);
134 
135 	BUG_ON(index >= nr_entries);
136 
137 	if (nr_to_copy) {
138 		memmove(key_ptr(n, index),
139 			key_ptr(n, index + 1),
140 			nr_to_copy * sizeof(__le64));
141 
142 		memmove(value_ptr(n, index),
143 			value_ptr(n, index + 1),
144 			nr_to_copy * value_size);
145 	}
146 
147 	n->header.nr_entries = cpu_to_le32(nr_entries - 1);
148 }
149 
150 static unsigned int merge_threshold(struct btree_node *n)
151 {
152 	return le32_to_cpu(n->header.max_entries) / 3;
153 }
154 
155 struct child {
156 	unsigned int index;
157 	struct dm_block *block;
158 	struct btree_node *n;
159 };
160 
161 static int init_child(struct dm_btree_info *info, struct dm_btree_value_type *vt,
162 		      struct btree_node *parent,
163 		      unsigned int index, struct child *result)
164 {
165 	int r, inc;
166 	dm_block_t root;
167 
168 	result->index = index;
169 	root = value64(parent, index);
170 
171 	r = dm_tm_shadow_block(info->tm, root, &btree_node_validator,
172 			       &result->block, &inc);
173 	if (r)
174 		return r;
175 
176 	result->n = dm_block_data(result->block);
177 
178 	if (inc)
179 		inc_children(info->tm, result->n, vt);
180 
181 	*((__le64 *) value_ptr(parent, index)) =
182 		cpu_to_le64(dm_block_location(result->block));
183 
184 	return 0;
185 }
186 
187 static void exit_child(struct dm_btree_info *info, struct child *c)
188 {
189 	dm_tm_unlock(info->tm, c->block);
190 }
191 
192 static int shift(struct btree_node *left, struct btree_node *right, int count)
193 {
194 	int r;
195 	uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
196 	uint32_t nr_right = le32_to_cpu(right->header.nr_entries);
197 	uint32_t max_entries = le32_to_cpu(left->header.max_entries);
198 	uint32_t r_max_entries = le32_to_cpu(right->header.max_entries);
199 
200 	if (max_entries != r_max_entries) {
201 		DMERR("node max_entries mismatch");
202 		return -EILSEQ;
203 	}
204 
205 	if (nr_left - count > max_entries) {
206 		DMERR("node shift out of bounds");
207 		return -EINVAL;
208 	}
209 
210 	if (nr_right + count > max_entries) {
211 		DMERR("node shift out of bounds");
212 		return -EINVAL;
213 	}
214 
215 	if (!count)
216 		return 0;
217 
218 	if (count > 0) {
219 		node_shift(right, count);
220 		r = node_copy(left, right, count);
221 		if (r)
222 			return r;
223 	} else {
224 		r = node_copy(left, right, count);
225 		if (r)
226 			return r;
227 		node_shift(right, count);
228 	}
229 
230 	left->header.nr_entries = cpu_to_le32(nr_left - count);
231 	right->header.nr_entries = cpu_to_le32(nr_right + count);
232 
233 	return 0;
234 }
235 
236 static int __rebalance2(struct dm_btree_info *info, struct btree_node *parent,
237 			struct child *l, struct child *r)
238 {
239 	int ret;
240 	struct btree_node *left = l->n;
241 	struct btree_node *right = r->n;
242 	uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
243 	uint32_t nr_right = le32_to_cpu(right->header.nr_entries);
244 	/*
245 	 * Ensure the number of entries in each child will be greater
246 	 * than or equal to (max_entries / 3 + 1), so no matter which
247 	 * child is used for removal, the number will still be not
248 	 * less than (max_entries / 3).
249 	 */
250 	unsigned int threshold = 2 * (merge_threshold(left) + 1);
251 
252 	if (nr_left + nr_right < threshold) {
253 		/*
254 		 * Merge
255 		 */
256 		ret = node_copy(left, right, -nr_right);
257 		if (unlikely(ret))
258 			return ret;
259 		left->header.nr_entries = cpu_to_le32(nr_left + nr_right);
260 		delete_at(parent, r->index);
261 
262 		/*
263 		 * We need to decrement the right block, but not it's
264 		 * children, since they're still referenced by left.
265 		 */
266 		dm_tm_dec(info->tm, dm_block_location(r->block));
267 	} else {
268 		/*
269 		 * Rebalance.
270 		 */
271 		unsigned int target_left = (nr_left + nr_right) / 2;
272 
273 		ret = shift(left, right, nr_left - target_left);
274 		if (ret)
275 			return ret;
276 		*key_ptr(parent, r->index) = right->keys[0];
277 	}
278 	return 0;
279 }
280 
281 static int rebalance2(struct shadow_spine *s, struct dm_btree_info *info,
282 		      struct dm_btree_value_type *vt, unsigned int left_index)
283 {
284 	int r;
285 	struct btree_node *parent;
286 	struct child left, right;
287 
288 	parent = dm_block_data(shadow_current(s));
289 
290 	r = init_child(info, vt, parent, left_index, &left);
291 	if (r)
292 		return r;
293 
294 	r = init_child(info, vt, parent, left_index + 1, &right);
295 	if (r) {
296 		exit_child(info, &left);
297 		return r;
298 	}
299 
300 	r = __rebalance2(info, parent, &left, &right);
301 
302 	exit_child(info, &left);
303 	exit_child(info, &right);
304 
305 	return r;
306 }
307 
308 /*
309  * We dump as many entries from center as possible into left, then the rest
310  * in right, then rebalance2.  This wastes some cpu, but I want something
311  * simple atm.
312  */
313 static int delete_center_node(struct dm_btree_info *info, struct btree_node *parent,
314 			      struct child *l, struct child *c, struct child *r,
315 			      struct btree_node *left, struct btree_node *center, struct btree_node *right,
316 			      uint32_t nr_left, uint32_t nr_center, uint32_t nr_right)
317 {
318 	uint32_t max_entries = le32_to_cpu(left->header.max_entries);
319 	unsigned int shift = min(max_entries - nr_left, nr_center);
320 	int ret;
321 
322 	if (nr_left + shift > max_entries) {
323 		DMERR("node shift out of bounds");
324 		return -EINVAL;
325 	}
326 
327 	ret = node_copy(left, center, -shift);
328 	if (unlikely(ret))
329 		return ret;
330 	left->header.nr_entries = cpu_to_le32(nr_left + shift);
331 
332 	if (shift != nr_center) {
333 		shift = nr_center - shift;
334 
335 		if ((nr_right + shift) > max_entries) {
336 			DMERR("node shift out of bounds");
337 			return -EINVAL;
338 		}
339 
340 		node_shift(right, shift);
341 		ret = node_copy(center, right, shift);
342 		if (unlikely(ret))
343 			return ret;
344 		right->header.nr_entries = cpu_to_le32(nr_right + shift);
345 	}
346 	*key_ptr(parent, r->index) = right->keys[0];
347 
348 	delete_at(parent, c->index);
349 	r->index--;
350 
351 	dm_tm_dec(info->tm, dm_block_location(c->block));
352 	return __rebalance2(info, parent, l, r);
353 }
354 
355 /*
356  * Redistributes entries among 3 sibling nodes.
357  */
358 static int redistribute3(struct dm_btree_info *info, struct btree_node *parent,
359 			 struct child *l, struct child *c, struct child *r,
360 			 struct btree_node *left, struct btree_node *center, struct btree_node *right,
361 			 uint32_t nr_left, uint32_t nr_center, uint32_t nr_right)
362 {
363 	int s, ret;
364 	uint32_t max_entries = le32_to_cpu(left->header.max_entries);
365 	unsigned int total = nr_left + nr_center + nr_right;
366 	unsigned int target_right = total / 3;
367 	unsigned int remainder = (target_right * 3) != total;
368 	unsigned int target_left = target_right + remainder;
369 
370 	BUG_ON(target_left > max_entries);
371 	BUG_ON(target_right > max_entries);
372 
373 	if (nr_left < nr_right) {
374 		s = nr_left - target_left;
375 
376 		if (s < 0 && nr_center < -s) {
377 			/* not enough in central node */
378 			ret = shift(left, center, -nr_center);
379 			if (ret)
380 				return ret;
381 
382 			s += nr_center;
383 			ret = shift(left, right, s);
384 			if (ret)
385 				return ret;
386 
387 			nr_right += s;
388 		} else {
389 			ret = shift(left, center, s);
390 			if (ret)
391 				return ret;
392 		}
393 
394 		ret = shift(center, right, target_right - nr_right);
395 		if (ret)
396 			return ret;
397 	} else {
398 		s = target_right - nr_right;
399 		if (s > 0 && nr_center < s) {
400 			/* not enough in central node */
401 			ret = shift(center, right, nr_center);
402 			if (ret)
403 				return ret;
404 			s -= nr_center;
405 			ret = shift(left, right, s);
406 			if (ret)
407 				return ret;
408 			nr_left -= s;
409 		} else {
410 			ret = shift(center, right, s);
411 			if (ret)
412 				return ret;
413 		}
414 
415 		ret = shift(left, center, nr_left - target_left);
416 		if (ret)
417 			return ret;
418 	}
419 
420 	*key_ptr(parent, c->index) = center->keys[0];
421 	*key_ptr(parent, r->index) = right->keys[0];
422 	return 0;
423 }
424 
425 static int __rebalance3(struct dm_btree_info *info, struct btree_node *parent,
426 			struct child *l, struct child *c, struct child *r)
427 {
428 	struct btree_node *left = l->n;
429 	struct btree_node *center = c->n;
430 	struct btree_node *right = r->n;
431 
432 	uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
433 	uint32_t nr_center = le32_to_cpu(center->header.nr_entries);
434 	uint32_t nr_right = le32_to_cpu(right->header.nr_entries);
435 
436 	unsigned int threshold = merge_threshold(left) * 4 + 1;
437 
438 	if ((left->header.max_entries != center->header.max_entries) ||
439 	    (center->header.max_entries != right->header.max_entries)) {
440 		DMERR("bad btree metadata, max_entries differ");
441 		return -EILSEQ;
442 	}
443 
444 	if ((nr_left + nr_center + nr_right) < threshold) {
445 		return delete_center_node(info, parent, l, c, r, left, center, right,
446 					  nr_left, nr_center, nr_right);
447 	}
448 
449 	return redistribute3(info, parent, l, c, r, left, center, right,
450 			     nr_left, nr_center, nr_right);
451 }
452 
453 static int rebalance3(struct shadow_spine *s, struct dm_btree_info *info,
454 		      struct dm_btree_value_type *vt, unsigned int left_index)
455 {
456 	int r;
457 	struct btree_node *parent = dm_block_data(shadow_current(s));
458 	struct child left, center, right;
459 
460 	/*
461 	 * FIXME: fill out an array?
462 	 */
463 	r = init_child(info, vt, parent, left_index, &left);
464 	if (r)
465 		return r;
466 
467 	r = init_child(info, vt, parent, left_index + 1, &center);
468 	if (r) {
469 		exit_child(info, &left);
470 		return r;
471 	}
472 
473 	r = init_child(info, vt, parent, left_index + 2, &right);
474 	if (r) {
475 		exit_child(info, &left);
476 		exit_child(info, &center);
477 		return r;
478 	}
479 
480 	r = __rebalance3(info, parent, &left, &center, &right);
481 
482 	exit_child(info, &left);
483 	exit_child(info, &center);
484 	exit_child(info, &right);
485 
486 	return r;
487 }
488 
489 static int rebalance_children(struct shadow_spine *s,
490 			      struct dm_btree_info *info,
491 			      struct dm_btree_value_type *vt, uint64_t key)
492 {
493 	int i, r, has_left_sibling, has_right_sibling;
494 	struct btree_node *n;
495 
496 	n = dm_block_data(shadow_current(s));
497 
498 	if (le32_to_cpu(n->header.nr_entries) == 1) {
499 		struct dm_block *child;
500 		int is_shared;
501 		dm_block_t b = value64(n, 0);
502 
503 		r = dm_tm_block_is_shared(info->tm, b, &is_shared);
504 		if (r)
505 			return r;
506 
507 		r = dm_tm_read_lock(info->tm, b, &btree_node_validator, &child);
508 		if (r)
509 			return r;
510 
511 		if (is_shared)
512 			inc_children(info->tm, dm_block_data(child), vt);
513 
514 		memcpy(n, dm_block_data(child),
515 		       dm_bm_block_size(dm_tm_get_bm(info->tm)));
516 
517 		dm_tm_dec(info->tm, dm_block_location(child));
518 		dm_tm_unlock(info->tm, child);
519 		return 0;
520 	}
521 
522 	i = lower_bound(n, key);
523 	if (i < 0)
524 		return -ENODATA;
525 
526 	has_left_sibling = i > 0;
527 	has_right_sibling = i < (le32_to_cpu(n->header.nr_entries) - 1);
528 
529 	if (!has_left_sibling)
530 		r = rebalance2(s, info, vt, i);
531 
532 	else if (!has_right_sibling)
533 		r = rebalance2(s, info, vt, i - 1);
534 
535 	else
536 		r = rebalance3(s, info, vt, i - 1);
537 
538 	return r;
539 }
540 
541 static int do_leaf(struct btree_node *n, uint64_t key, unsigned int *index)
542 {
543 	int i = lower_bound(n, key);
544 
545 	if ((i < 0) ||
546 	    (i >= le32_to_cpu(n->header.nr_entries)) ||
547 	    (le64_to_cpu(n->keys[i]) != key))
548 		return -ENODATA;
549 
550 	*index = i;
551 
552 	return 0;
553 }
554 
555 /*
556  * Prepares for removal from one level of the hierarchy.  The caller must
557  * call delete_at() to remove the entry at index.
558  */
559 static int remove_raw(struct shadow_spine *s, struct dm_btree_info *info,
560 		      struct dm_btree_value_type *vt, dm_block_t root,
561 		      uint64_t key, unsigned int *index)
562 {
563 	int i = *index, r;
564 	struct btree_node *n;
565 
566 	for (;;) {
567 		r = shadow_step(s, root, vt);
568 		if (r < 0)
569 			break;
570 
571 		/*
572 		 * We have to patch up the parent node, ugly, but I don't
573 		 * see a way to do this automatically as part of the spine
574 		 * op.
575 		 */
576 		if (shadow_has_parent(s)) {
577 			__le64 location = cpu_to_le64(dm_block_location(shadow_current(s)));
578 
579 			memcpy(value_ptr(dm_block_data(shadow_parent(s)), i),
580 			       &location, sizeof(__le64));
581 		}
582 
583 		n = dm_block_data(shadow_current(s));
584 
585 		if (le32_to_cpu(n->header.flags) & LEAF_NODE)
586 			return do_leaf(n, key, index);
587 
588 		r = rebalance_children(s, info, vt, key);
589 		if (r)
590 			break;
591 
592 		n = dm_block_data(shadow_current(s));
593 		if (le32_to_cpu(n->header.flags) & LEAF_NODE)
594 			return do_leaf(n, key, index);
595 
596 		i = lower_bound(n, key);
597 
598 		/*
599 		 * We know the key is present, or else
600 		 * rebalance_children would have returned
601 		 * -ENODATA
602 		 */
603 		root = value64(n, i);
604 	}
605 
606 	return r;
607 }
608 
609 int dm_btree_remove(struct dm_btree_info *info, dm_block_t root,
610 		    uint64_t *keys, dm_block_t *new_root)
611 {
612 	unsigned int level, last_level = info->levels - 1;
613 	int index = 0, r = 0;
614 	struct shadow_spine spine;
615 	struct btree_node *n;
616 	struct dm_btree_value_type le64_vt;
617 
618 	init_le64_type(info->tm, &le64_vt);
619 	init_shadow_spine(&spine, info);
620 	for (level = 0; level < info->levels; level++) {
621 		r = remove_raw(&spine, info,
622 			       (level == last_level ?
623 				&info->value_type : &le64_vt),
624 			       root, keys[level], (unsigned int *)&index);
625 		if (r < 0)
626 			break;
627 
628 		n = dm_block_data(shadow_current(&spine));
629 		if (level != last_level) {
630 			root = value64(n, index);
631 			continue;
632 		}
633 
634 		BUG_ON(index < 0 || index >= le32_to_cpu(n->header.nr_entries));
635 
636 		if (info->value_type.dec)
637 			info->value_type.dec(info->value_type.context,
638 					     value_ptr(n, index), 1);
639 
640 		delete_at(n, index);
641 	}
642 
643 	if (!r)
644 		*new_root = shadow_root(&spine);
645 	exit_shadow_spine(&spine);
646 
647 	return r;
648 }
649 EXPORT_SYMBOL_GPL(dm_btree_remove);
650 
651 /*----------------------------------------------------------------*/
652 
653 static int remove_nearest(struct shadow_spine *s, struct dm_btree_info *info,
654 			  struct dm_btree_value_type *vt, dm_block_t root,
655 			  uint64_t key, int *index)
656 {
657 	int i = *index, r;
658 	struct btree_node *n;
659 
660 	for (;;) {
661 		r = shadow_step(s, root, vt);
662 		if (r < 0)
663 			break;
664 
665 		/*
666 		 * We have to patch up the parent node, ugly, but I don't
667 		 * see a way to do this automatically as part of the spine
668 		 * op.
669 		 */
670 		if (shadow_has_parent(s)) {
671 			__le64 location = cpu_to_le64(dm_block_location(shadow_current(s)));
672 
673 			memcpy(value_ptr(dm_block_data(shadow_parent(s)), i),
674 			       &location, sizeof(__le64));
675 		}
676 
677 		n = dm_block_data(shadow_current(s));
678 
679 		if (le32_to_cpu(n->header.flags) & LEAF_NODE) {
680 			*index = lower_bound(n, key);
681 			return 0;
682 		}
683 
684 		r = rebalance_children(s, info, vt, key);
685 		if (r)
686 			break;
687 
688 		n = dm_block_data(shadow_current(s));
689 		if (le32_to_cpu(n->header.flags) & LEAF_NODE) {
690 			*index = lower_bound(n, key);
691 			return 0;
692 		}
693 
694 		i = lower_bound(n, key);
695 
696 		/*
697 		 * We know the key is present, or else
698 		 * rebalance_children would have returned
699 		 * -ENODATA
700 		 */
701 		root = value64(n, i);
702 	}
703 
704 	return r;
705 }
706 
707 static int remove_one(struct dm_btree_info *info, dm_block_t root,
708 		      uint64_t *keys, uint64_t end_key,
709 		      dm_block_t *new_root, unsigned int *nr_removed)
710 {
711 	unsigned int level, last_level = info->levels - 1;
712 	int index = 0, r = 0;
713 	struct shadow_spine spine;
714 	struct btree_node *n;
715 	struct dm_btree_value_type le64_vt;
716 	uint64_t k;
717 
718 	init_le64_type(info->tm, &le64_vt);
719 	init_shadow_spine(&spine, info);
720 	for (level = 0; level < last_level; level++) {
721 		r = remove_raw(&spine, info, &le64_vt,
722 			       root, keys[level], (unsigned int *) &index);
723 		if (r < 0)
724 			goto out;
725 
726 		n = dm_block_data(shadow_current(&spine));
727 		root = value64(n, index);
728 	}
729 
730 	r = remove_nearest(&spine, info, &info->value_type,
731 			   root, keys[last_level], &index);
732 	if (r < 0)
733 		goto out;
734 
735 	n = dm_block_data(shadow_current(&spine));
736 
737 	if (index < 0)
738 		index = 0;
739 
740 	if (index >= le32_to_cpu(n->header.nr_entries)) {
741 		r = -ENODATA;
742 		goto out;
743 	}
744 
745 	k = le64_to_cpu(n->keys[index]);
746 	if (k >= keys[last_level] && k < end_key) {
747 		if (info->value_type.dec)
748 			info->value_type.dec(info->value_type.context,
749 					     value_ptr(n, index), 1);
750 
751 		delete_at(n, index);
752 		keys[last_level] = k + 1ull;
753 
754 	} else
755 		r = -ENODATA;
756 
757 out:
758 	*new_root = shadow_root(&spine);
759 	exit_shadow_spine(&spine);
760 
761 	return r;
762 }
763 
764 int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root,
765 			   uint64_t *first_key, uint64_t end_key,
766 			   dm_block_t *new_root, unsigned int *nr_removed)
767 {
768 	int r;
769 
770 	*nr_removed = 0;
771 	do {
772 		r = remove_one(info, root, first_key, end_key, &root, nr_removed);
773 		if (!r)
774 			(*nr_removed)++;
775 	} while (!r);
776 
777 	*new_root = root;
778 	return r == -ENODATA ? 0 : r;
779 }
780 EXPORT_SYMBOL_GPL(dm_btree_remove_leaves);
781