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