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()
72 		  struct dm_btree_value_type *vt)  in inc_children()  argument
75 	uint32_t nr_entries = le32_to_cpu(n->header.nr_entries);  in inc_children()
77 	if (le32_to_cpu(n->header.flags) & INTERNAL_NODE)  in inc_children()
80 	else if (vt->inc)  in inc_children()
82 			vt->inc(vt->context, value_ptr(n, i));  in inc_children()
89 	uint32_t nr_entries = le32_to_cpu(node->header.nr_entries);  in insert_at()
93 	    index >= 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 /*----------------------------------------------------------------*/
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()
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()
324 				for (i = 0; i < f->nr_children; i++)  in dm_btree_del()
325 					info->value_type.dec(info->value_type.context,  in dm_btree_del()
326 							     value_ptr(f->n, i));  in dm_btree_del()
342 /*----------------------------------------------------------------*/
358 		flags = le32_to_cpu(ro_node(s)->header.flags);  in btree_lookup_raw()
359 		nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries);  in btree_lookup_raw()
361 			return -ENODATA;  in btree_lookup_raw()
368 	*result_key = le64_to_cpu(ro_node(s)->keys[i]);  in btree_lookup_raw()
378 	unsigned level, last_level = info->levels - 1;  in dm_btree_lookup()
379 	int r = -ENODATA;  in dm_btree_lookup()
385 	for (level = 0; level < info->levels; level++) {  in dm_btree_lookup()
391 			size = info->value_type.size;  in dm_btree_lookup()
405 				return -ENODATA;  in dm_btree_lookup()
433 	flags = le32_to_cpu(n->header.flags);  in dm_btree_lookup_next_single()
434 	nr_entries = le32_to_cpu(n->header.nr_entries);  in dm_btree_lookup_next_single()
440 			 * avoid early -ENODATA return when all entries are  in dm_btree_lookup_next_single()
446 			r = -ENODATA;  in dm_btree_lookup_next_single()
451 		if (r == -ENODATA && i < (nr_entries - 1)) {  in dm_btree_lookup_next_single()
459 			r = -ENODATA;  in dm_btree_lookup_next_single()
463 		*rkey = le64_to_cpu(n->keys[i]);  in dm_btree_lookup_next_single()
464 		memcpy(value_le, value_ptr(n, i), info->value_type.size);  in dm_btree_lookup_next_single()
467 	dm_tm_unlock(info->tm, node);  in dm_btree_lookup_next_single()
475 	int r = -ENODATA;  in dm_btree_lookup_next()
480 	for (level = 0; level < info->levels - 1u; level++) {  in dm_btree_lookup_next()
488 			r = -ENODATA;  in dm_btree_lookup_next()
509  *	  +--------+
511  *	  +--------+
514  *	+----------+
516  *	+----------+
520  *		+--------+
522  *		+--------+
524  *		  v	+------+
525  *	    +---------+	       |
527  *	    +---------+	  +-------+
529  *			  +-------+
545 	r = new_block(s->info, &right);  in btree_split_sibling()
552 	nr_left = le32_to_cpu(ln->header.nr_entries) / 2;  in btree_split_sibling()
553 	nr_right = le32_to_cpu(ln->header.nr_entries) - nr_left;  in btree_split_sibling()
555 	ln->header.nr_entries = cpu_to_le32(nr_left);  in btree_split_sibling()
557 	rn->header.flags = ln->header.flags;  in btree_split_sibling()
558 	rn->header.nr_entries = cpu_to_le32(nr_right);  in btree_split_sibling()
559 	rn->header.max_entries = ln->header.max_entries;  in btree_split_sibling()
560 	rn->header.value_size = ln->header.value_size;  in btree_split_sibling()
561 	memcpy(rn->keys, ln->keys + nr_left, nr_right * sizeof(rn->keys[0]));  in btree_split_sibling()
563 	size = le32_to_cpu(ln->header.flags) & INTERNAL_NODE ?  in btree_split_sibling()
564 		sizeof(uint64_t) : s->info->value_type.size;  in btree_split_sibling()
583 		      le64_to_cpu(rn->keys[0]), &location);  in btree_split_sibling()
585 		unlock_block(s->info, right);  in btree_split_sibling()
589 	if (key < le64_to_cpu(rn->keys[0])) {  in btree_split_sibling()
590 		unlock_block(s->info, right);  in btree_split_sibling()
591 		s->nodes[1] = left;  in btree_split_sibling()
593 		unlock_block(s->info, left);  in btree_split_sibling()
594 		s->nodes[1] = right;  in btree_split_sibling()
604  *	  +----------+
606  *	  +----------+
610  *	+------------+
612  *	+------------+
614  *   +------+	+----+
617  * +-------+	 +-------+
619  * +-------+	 +-------+
633 	size = le32_to_cpu(pn->header.flags) & INTERNAL_NODE ?  in btree_split_beneath()
634 		sizeof(__le64) : s->info->value_type.size;  in btree_split_beneath()
637 	r = new_block(s->info, &left);  in btree_split_beneath()
642 	nr_left = le32_to_cpu(pn->header.nr_entries) / 2;  in btree_split_beneath()
644 	ln->header.flags = pn->header.flags;  in btree_split_beneath()
645 	ln->header.nr_entries = cpu_to_le32(nr_left);  in btree_split_beneath()
646 	ln->header.max_entries = pn->header.max_entries;  in btree_split_beneath()
647 	ln->header.value_size = pn->header.value_size;  in btree_split_beneath()
648 	memcpy(ln->keys, pn->keys, nr_left * sizeof(pn->keys[0]));  in btree_split_beneath()
652 	r = new_block(s->info, &right);  in btree_split_beneath()
654 		unlock_block(s->info, left);  in btree_split_beneath()
659 	nr_right = le32_to_cpu(pn->header.nr_entries) - nr_left;  in btree_split_beneath()
661 	rn->header.flags = pn->header.flags;  in btree_split_beneath()
662 	rn->header.nr_entries = cpu_to_le32(nr_right);  in btree_split_beneath()
663 	rn->header.max_entries = pn->header.max_entries;  in btree_split_beneath()
664 	rn->header.value_size = pn->header.value_size;  in btree_split_beneath()
665 	memcpy(rn->keys, pn->keys + nr_left, nr_right * sizeof(pn->keys[0]));  in btree_split_beneath()
670 	pn->header.flags = cpu_to_le32(INTERNAL_NODE);  in btree_split_beneath()
671 	pn->header.nr_entries = cpu_to_le32(2);  in btree_split_beneath()
672 	pn->header.max_entries = cpu_to_le32(  in btree_split_beneath()
675 					 dm_tm_get_bm(s->info->tm))));  in btree_split_beneath()
676 	pn->header.value_size = cpu_to_le32(sizeof(__le64));  in btree_split_beneath()
680 	pn->keys[0] = ln->keys[0];  in btree_split_beneath()
685 	pn->keys[1] = rn->keys[0];  in btree_split_beneath()
688 	unlock_block(s->info, left);  in btree_split_beneath()
689 	unlock_block(s->info, right);  in btree_split_beneath()
694 			    struct dm_btree_value_type *vt,  in btree_insert_raw()  argument
701 		r = shadow_step(s, root, vt);  in btree_insert_raw()
722 		if (node->header.nr_entries == node->header.max_entries) {  in btree_insert_raw()
736 		if (le32_to_cpu(node->header.flags) & LEAF_NODE)  in btree_insert_raw()
741 			node->keys[0] = cpu_to_le64(key);  in btree_insert_raw()
749 	if (i < 0 || le64_to_cpu(node->keys[i]) != key)  in btree_insert_raw()
759         return ((index >= le32_to_cpu(node->header.nr_entries)) ||  in need_insert()
760 		(le64_to_cpu(node->keys[index]) != keys[level]));  in need_insert()
769 	unsigned level, index = -1, last_level = info->levels - 1;  in insert()
775 	init_le64_type(info->tm, &le64_type);  in insert()
778 	for (level = 0; level < (info->levels - 1); level++) {  in insert()
806 	r = btree_insert_raw(&spine, block, &info->value_type,  in insert()
817 		r = insert_at(info->value_type.size, n, index,  in insert()
825 		if (info->value_type.dec &&  in insert()
826 		    (!info->value_type.equal ||  in insert()
827 		     !info->value_type.equal(  in insert()
828 			     info->value_type.context,  in insert()
831 			info->value_type.dec(info->value_type.context,  in insert()
835 			    value, info->value_type.size);  in insert()
867 /*----------------------------------------------------------------*/
880 		flags = le32_to_cpu(ro_node(s)->header.flags);  in find_key()
881 		i = le32_to_cpu(ro_node(s)->header.nr_entries);  in find_key()
883 			return -ENODATA;  in find_key()
885 			i--;  in find_key()
888 			*result_key = le64_to_cpu(ro_node(s)->keys[i]);  in find_key()
890 			*result_key = le64_to_cpu(ro_node(s)->keys[0]);  in find_key()
913 	for (level = 0; level < info->levels; level++) {  in dm_btree_find_key()
915 			     level == info->levels - 1 ? NULL : &root);  in dm_btree_find_key()
916 		if (r == -ENODATA) {  in dm_btree_find_key()
944 /*----------------------------------------------------------------*/
966 	nr = le32_to_cpu(n->header.nr_entries);  in walk_node()
968 		if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) {  in walk_node()
981 	dm_tm_unlock(info->tm, node);  in walk_node()
989 	BUG_ON(info->levels > 1);  in dm_btree_walk()
994 /*----------------------------------------------------------------*/
1000 	struct cursor_node *n = c->nodes + c->depth - 1;  in prefetch_values()
1001 	struct btree_node *bn = dm_block_data(n->b);  in prefetch_values()
1002 	struct dm_block_manager *bm = dm_tm_get_bm(c->info->tm);  in prefetch_values()
1004 	BUG_ON(c->info->value_type.size != sizeof(value_le));  in prefetch_values()
1006 	nr = le32_to_cpu(bn->header.nr_entries);  in prefetch_values()
1015 	struct cursor_node *n = c->nodes + c->depth - 1;  in leaf_node()
1016 	struct btree_node *bn = dm_block_data(n->b);  in leaf_node()
1018 	return le32_to_cpu(bn->header.flags) & LEAF_NODE;  in leaf_node()
1024 	struct cursor_node *n = c->nodes + c->depth;  in push_node()
1026 	if (c->depth >= DM_BTREE_CURSOR_MAX_DEPTH - 1) {  in push_node()
1027 		DMERR("couldn't push cursor node, stack depth too high");  in push_node()
1028 		return -EINVAL;  in push_node()
1031 	r = bn_read_lock(c->info, b, &n->b);  in push_node()
1035 	n->index = 0;  in push_node()
1036 	c->depth++;  in push_node()
1038 	if (c->prefetch_leaves || !leaf_node(c))  in push_node()
1046 	c->depth--;  in pop_node()
1047 	unlock_block(c->info, c->nodes[c->depth].b);  in pop_node()
1056 		if (!c->depth)  in inc_or_backtrack()
1057 			return -ENODATA;  in inc_or_backtrack()
1059 		n = c->nodes + c->depth - 1;  in inc_or_backtrack()
1060 		bn = dm_block_data(n->b);  in inc_or_backtrack()
1062 		n->index++;  in inc_or_backtrack()
1063 		if (n->index < le32_to_cpu(bn->header.nr_entries))  in inc_or_backtrack()
1080 		n = c->nodes + c->depth - 1;  in find_leaf()
1081 		bn = dm_block_data(n->b);  in find_leaf()
1083 		if (le32_to_cpu(bn->header.flags) & LEAF_NODE)  in find_leaf()
1086 		memcpy(&value_le, value_ptr(bn, n->index), sizeof(value_le));  in find_leaf()
1094 	if (!r && (le32_to_cpu(bn->header.nr_entries) == 0))  in find_leaf()
1095 		return -ENODATA;  in find_leaf()
1105 	c->info = info;  in dm_btree_cursor_begin()
1106 	c->root = root;  in dm_btree_cursor_begin()
1107 	c->depth = 0;  in dm_btree_cursor_begin()
1108 	c->prefetch_leaves = prefetch_leaves;  in dm_btree_cursor_begin()
1120 	while (c->depth)  in dm_btree_cursor_end()
1142 	while (count-- && !r)  in dm_btree_cursor_skip()
1151 	if (c->depth) {  in dm_btree_cursor_get_value()
1152 		struct cursor_node *n = c->nodes + c->depth - 1;  in dm_btree_cursor_get_value()
1153 		struct btree_node *bn = dm_block_data(n->b);  in dm_btree_cursor_get_value()
1155 		if (le32_to_cpu(bn->header.flags) & INTERNAL_NODE)  in dm_btree_cursor_get_value()
1156 			return -EINVAL;  in dm_btree_cursor_get_value()
1158 		*key = le64_to_cpu(*key_ptr(bn, n->index));  in dm_btree_cursor_get_value()
1159 		memcpy(value_le, value_ptr(bn, n->index), c->info->value_type.size);  in dm_btree_cursor_get_value()
1163 		return -ENODATA;  in dm_btree_cursor_get_value()