170 static int top_frame(struct del_stack *s, struct frame **f)  in top_frame()  argument
172 	if (s->top < 0) {  in top_frame()
177 	*f = s->spine + s->top;  in top_frame()
182 static int unprocessed_frames(struct del_stack *s)  in unprocessed_frames()  argument
184 	return s->top >= 0;  in unprocessed_frames()
187 static void prefetch_children(struct del_stack *s, struct frame *f)  in prefetch_children()  argument
190 	struct dm_block_manager *bm = dm_tm_get_bm(s->tm);  in prefetch_children()
201 static int push_frame(struct del_stack *s, dm_block_t b, unsigned level)  in push_frame()  argument
206 	if (s->top >= MAX_SPINE_DEPTH - 1) {  in push_frame()
211 	r = dm_tm_ref(s->tm, b, &ref_count);  in push_frame()
220 		dm_tm_dec(s->tm, b);  in push_frame()
224 		struct frame *f = s->spine + ++s->top;  in push_frame()
226 		r = dm_tm_read_lock(s->tm, b, &btree_node_validator, &f->b);  in push_frame()
228 			s->top--;  in push_frame()
238 		if (flags & INTERNAL_NODE || is_internal_level(s->info, f))  in push_frame()
239 			prefetch_children(s, f);  in push_frame()
245 static void pop_frame(struct del_stack *s)  in pop_frame()  argument
247 	struct frame *f = s->spine + s->top--;  in pop_frame()
249 	dm_tm_dec(s->tm, dm_block_location(f->b));  in pop_frame()
250 	dm_tm_unlock(s->tm, f->b);  in pop_frame()
256 	struct del_stack *s;  in dm_btree_del()  local
258 	s = kmalloc(sizeof(*s), GFP_NOIO);  in dm_btree_del()
259 	if (!s)  in dm_btree_del()
261 	s->info = info;  in dm_btree_del()
262 	s->tm = info->tm;  in dm_btree_del()
263 	s->top = -1;  in dm_btree_del()
265 	r = push_frame(s, root, 0);  in dm_btree_del()
269 	while (unprocessed_frames(s)) {  in dm_btree_del()
274 		r = top_frame(s, &f);  in dm_btree_del()
279 			pop_frame(s);  in dm_btree_del()
287 			r = push_frame(s, b, f->level);  in dm_btree_del()
294 			r = push_frame(s, b, f->level + 1);  in dm_btree_del()
306 			pop_frame(s);  in dm_btree_del()
311 	kfree(s);  in dm_btree_del()
318 static int btree_lookup_raw(struct ro_spine *s, dm_block_t block, uint64_t key,  in btree_lookup_raw()  argument
326 		r = ro_step(s, block);  in btree_lookup_raw()
330 		i = search_fn(ro_node(s), key);  in btree_lookup_raw()
332 		flags = le32_to_cpu(ro_node(s)->header.flags);  in btree_lookup_raw()
333 		nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries);  in btree_lookup_raw()
338 			block = value64(ro_node(s), i);  in btree_lookup_raw()
342 	*result_key = le64_to_cpu(ro_node(s)->keys[i]);  in btree_lookup_raw()
343 	memcpy(v, value_ptr(ro_node(s), i), value_size);  in btree_lookup_raw()
423 static int btree_split_sibling(struct shadow_spine *s, dm_block_t root,  in btree_split_sibling()  argument
433 	left = shadow_current(s);  in btree_split_sibling()
435 	r = new_block(s->info, &right);  in btree_split_sibling()
454 		sizeof(uint64_t) : s->info->value_type.size;  in btree_split_sibling()
461 	parent = shadow_parent(s);  in btree_split_sibling()
478 		unlock_block(s->info, right);  in btree_split_sibling()
479 		s->nodes[1] = left;  in btree_split_sibling()
481 		unlock_block(s->info, left);  in btree_split_sibling()
482 		s->nodes[1] = right;  in btree_split_sibling()
509 static int btree_split_beneath(struct shadow_spine *s, uint64_t key)  in btree_split_beneath()  argument
518 	new_parent = shadow_current(s);  in btree_split_beneath()
520 	r = new_block(s->info, &left);  in btree_split_beneath()
524 	r = new_block(s->info, &right);  in btree_split_beneath()
526 		unlock_block(s->info, left);  in btree_split_beneath()
551 		sizeof(__le64) : s->info->value_type.size;  in btree_split_beneath()
562 					 dm_tm_get_bm(s->info->tm))));  in btree_split_beneath()
579 	if (s->nodes[0] != new_parent) {  in btree_split_beneath()
580 		unlock_block(s->info, s->nodes[0]);  in btree_split_beneath()
581 		s->nodes[0] = new_parent;  in btree_split_beneath()
584 		unlock_block(s->info, right);  in btree_split_beneath()
585 		s->nodes[1] = left;  in btree_split_beneath()
587 		unlock_block(s->info, left);  in btree_split_beneath()
588 		s->nodes[1] = right;  in btree_split_beneath()
590 	s->count = 2;  in btree_split_beneath()
595 static int btree_insert_raw(struct shadow_spine *s, dm_block_t root,  in btree_insert_raw()  argument
603 		r = shadow_step(s, root, vt);  in btree_insert_raw()
607 		node = dm_block_data(shadow_current(s));  in btree_insert_raw()
614 		if (shadow_has_parent(s) && i >= 0) { /* FIXME: second clause unness. */  in btree_insert_raw()
615 			__le64 location = cpu_to_le64(dm_block_location(shadow_current(s)));  in btree_insert_raw()
618 			memcpy_disk(value_ptr(dm_block_data(shadow_parent(s)), i),  in btree_insert_raw()
622 		node = dm_block_data(shadow_current(s));  in btree_insert_raw()
626 				r = btree_split_beneath(s, key);  in btree_insert_raw()
628 				r = btree_split_sibling(s, root, i, key);  in btree_insert_raw()
634 		node = dm_block_data(shadow_current(s));  in btree_insert_raw()
768 static int find_key(struct ro_spine *s, dm_block_t block, bool find_highest,  in find_key()  argument
775 		r = ro_step(s, block);  in find_key()
779 		flags = le32_to_cpu(ro_node(s)->header.flags);  in find_key()
780 		i = le32_to_cpu(ro_node(s)->header.nr_entries);  in find_key()
787 			*result_key = le64_to_cpu(ro_node(s)->keys[i]);  in find_key()
789 			*result_key = le64_to_cpu(ro_node(s)->keys[0]);  in find_key()
792 			block = value64(ro_node(s), i);  in find_key()