19 void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned set)  in bch_dump_bset()  argument
29 		if (b->ops->key_dump)  in bch_dump_bset()
30 			b->ops->key_dump(b, k);  in bch_dump_bset()
35 		    bkey_cmp(k, b->ops->is_extents ?  in bch_dump_bset()
41 void bch_dump_bucket(struct btree_keys *b)  in bch_dump_bucket()  argument
46 	for (i = 0; i <= b->nsets; i++)  in bch_dump_bucket()
47 		bch_dump_bset(b, b->set[i].data,  in bch_dump_bucket()
48 			      bset_sector_offset(b, b->set[i].data));  in bch_dump_bucket()
52 int __bch_count_data(struct btree_keys *b)  in __bch_count_data()  argument
58 	if (b->ops->is_extents)  in __bch_count_data()
59 		for_each_key(b, k, &iter)  in __bch_count_data()
64 void __bch_check_keys(struct btree_keys *b, const char *fmt, ...)  in __bch_check_keys()  argument
71 	for_each_key(b, k, &iter) {  in __bch_check_keys()
72 		if (b->ops->is_extents) {  in __bch_check_keys()
77 			if (bch_ptr_invalid(b, k))  in __bch_check_keys()
84 			if (bch_ptr_bad(b, k))  in __bch_check_keys()
95 	if (p && bkey_cmp(p, &b->key) > 0)  in __bch_check_keys()
100 	bch_dump_bucket(b);  in __bch_check_keys()
114 	    bkey_cmp(k, iter->b->ops->is_extents ?  in bch_btree_iter_next_check()
116 		bch_dump_bucket(iter->b);  in bch_btree_iter_next_check()
264 static inline size_t btree_keys_bytes(struct btree_keys *b)  in btree_keys_bytes()  argument
266 	return PAGE_SIZE << b->page_order;  in btree_keys_bytes()
269 static inline size_t btree_keys_cachelines(struct btree_keys *b)  in btree_keys_cachelines()  argument
271 	return btree_keys_bytes(b) / BSET_CACHELINE;  in btree_keys_cachelines()
275 static inline size_t bset_tree_bytes(struct btree_keys *b)  in bset_tree_bytes()  argument
277 	return btree_keys_cachelines(b) * sizeof(struct bkey_float);  in bset_tree_bytes()
281 static inline size_t bset_prev_bytes(struct btree_keys *b)  in bset_prev_bytes()  argument
283 	return btree_keys_cachelines(b) * sizeof(uint8_t);  in bset_prev_bytes()
288 void bch_btree_keys_free(struct btree_keys *b)  in bch_btree_keys_free()  argument
290 	struct bset_tree *t = b->set;  in bch_btree_keys_free()
292 	if (bset_prev_bytes(b) < PAGE_SIZE)  in bch_btree_keys_free()
296 			   get_order(bset_prev_bytes(b)));  in bch_btree_keys_free()
298 	if (bset_tree_bytes(b) < PAGE_SIZE)  in bch_btree_keys_free()
302 			   get_order(bset_tree_bytes(b)));  in bch_btree_keys_free()
304 	free_pages((unsigned long) t->data, b->page_order);  in bch_btree_keys_free()
312 int bch_btree_keys_alloc(struct btree_keys *b, unsigned page_order, gfp_t gfp)  in bch_btree_keys_alloc()  argument
314 	struct bset_tree *t = b->set;  in bch_btree_keys_alloc()
318 	b->page_order = page_order;  in bch_btree_keys_alloc()
320 	t->data = (void *) __get_free_pages(gfp, b->page_order);  in bch_btree_keys_alloc()
324 	t->tree = bset_tree_bytes(b) < PAGE_SIZE  in bch_btree_keys_alloc()
325 		? kmalloc(bset_tree_bytes(b), gfp)  in bch_btree_keys_alloc()
326 		: (void *) __get_free_pages(gfp, get_order(bset_tree_bytes(b)));  in bch_btree_keys_alloc()
330 	t->prev = bset_prev_bytes(b) < PAGE_SIZE  in bch_btree_keys_alloc()
331 		? kmalloc(bset_prev_bytes(b), gfp)  in bch_btree_keys_alloc()
332 		: (void *) __get_free_pages(gfp, get_order(bset_prev_bytes(b)));  in bch_btree_keys_alloc()
338 	bch_btree_keys_free(b);  in bch_btree_keys_alloc()
343 void bch_btree_keys_init(struct btree_keys *b, const struct btree_keys_ops *ops,  in bch_btree_keys_init()  argument
348 	b->ops = ops;  in bch_btree_keys_init()
349 	b->expensive_debug_checks = expensive_debug_checks;  in bch_btree_keys_init()
350 	b->nsets = 0;  in bch_btree_keys_init()
351 	b->last_set_unwritten = 0;  in bch_btree_keys_init()
355 		b->set[i].size = 0;  in bch_btree_keys_init()
361 		b->set[i].data = NULL;  in bch_btree_keys_init()
408 	unsigned b = fls(j);  in __to_inorder()  local
409 	unsigned shift = fls(size - 1) - b;  in __to_inorder()
411 	j  ^= 1U << (b - 1);  in __to_inorder()
589 static void bset_alloc_tree(struct btree_keys *b, struct bset_tree *t)  in bset_alloc_tree()  argument
591 	if (t != b->set) {  in bset_alloc_tree()
599 	while (t < b->set + MAX_BSETS)  in bset_alloc_tree()
603 static void bch_bset_build_unwritten_tree(struct btree_keys *b)  in bch_bset_build_unwritten_tree()  argument
605 	struct bset_tree *t = bset_tree_last(b);  in bch_bset_build_unwritten_tree()
607 	BUG_ON(b->last_set_unwritten);  in bch_bset_build_unwritten_tree()
608 	b->last_set_unwritten = 1;  in bch_bset_build_unwritten_tree()
610 	bset_alloc_tree(b, t);  in bch_bset_build_unwritten_tree()
612 	if (t->tree != b->set->tree + btree_keys_cachelines(b)) {  in bch_bset_build_unwritten_tree()
618 void bch_bset_init_next(struct btree_keys *b, struct bset *i, uint64_t magic)  in bch_bset_init_next()  argument
620 	if (i != b->set->data) {  in bch_bset_init_next()
621 		b->set[++b->nsets].data = i;  in bch_bset_init_next()
622 		i->seq = b->set->data->seq;  in bch_bset_init_next()
630 	bch_bset_build_unwritten_tree(b);  in bch_bset_init_next()
634 void bch_bset_build_written_tree(struct btree_keys *b)  in bch_bset_build_written_tree()  argument
636 	struct bset_tree *t = bset_tree_last(b);  in bch_bset_build_written_tree()
640 	b->last_set_unwritten = 0;  in bch_bset_build_written_tree()
642 	bset_alloc_tree(b, t);  in bch_bset_build_written_tree()
646 			b->set->tree + btree_keys_cachelines(b) - t->tree);  in bch_bset_build_written_tree()
681 void bch_bset_fix_invalidated_key(struct btree_keys *b, struct bkey *k)  in bch_bset_fix_invalidated_key()  argument
686 	for (t = b->set; t <= bset_tree_last(b); t++)  in bch_bset_fix_invalidated_key()
692 	if (!t->size || !bset_written(b, t))  in bch_bset_fix_invalidated_key()
727 static void bch_bset_fix_lookup_table(struct btree_keys *b,  in bch_bset_fix_lookup_table()  argument
762 	if (t->size == b->set->tree + btree_keys_cachelines(b) - t->tree)  in bch_bset_fix_lookup_table()
781 bool bch_bkey_try_merge(struct btree_keys *b, struct bkey *l, struct bkey *r)  in bch_bkey_try_merge()  argument
783 	if (!b->ops->key_merge)  in bch_bkey_try_merge()
795 	return b->ops->key_merge(b, l, r);  in bch_bkey_try_merge()
799 void bch_bset_insert(struct btree_keys *b, struct bkey *where,  in bch_bset_insert()  argument
802 	struct bset_tree *t = bset_tree_last(b);  in bch_bset_insert()
804 	BUG_ON(!b->last_set_unwritten);  in bch_bset_insert()
805 	BUG_ON(bset_byte_offset(b, t->data) +  in bch_bset_insert()
807 	       PAGE_SIZE << b->page_order);  in bch_bset_insert()
815 	bch_bset_fix_lookup_table(b, t, where);  in bch_bset_insert()
819 unsigned bch_btree_insert_key(struct btree_keys *b, struct bkey *k,  in bch_btree_insert_key()  argument
823 	struct bset *i = bset_tree_last(b)->data;  in bch_btree_insert_key()
827 	BUG_ON(b->ops->is_extents && !KEY_SIZE(k));  in bch_btree_insert_key()
829 	m = bch_btree_iter_init(b, &iter, b->ops->is_extents  in bch_btree_insert_key()
833 	if (b->ops->insert_fixup(b, k, &iter, replace_key))  in bch_btree_insert_key()
839 	       bkey_cmp(k, b->ops->is_extents ? &START_KEY(m) : m) > 0)  in bch_btree_insert_key()
845 	    bch_bkey_try_merge(b, prev, k))  in bch_btree_insert_key()
855 	    bch_bkey_try_merge(b, k, m))  in bch_btree_insert_key()
858 	bch_bset_insert(b, m, k);  in bch_btree_insert_key()
952 struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t,  in __bch_bset_search()  argument
975 	} else if (bset_written(b, t)) {  in __bch_bset_search()
991 		BUG_ON(!b->nsets &&  in __bch_bset_search()
997 	if (btree_keys_expensive_checks(b)) {  in __bch_bset_search()
998 		BUG_ON(bset_written(b, t) &&  in __bch_bset_search()
1041 static struct bkey *__bch_btree_iter_init(struct btree_keys *b,  in __bch_btree_iter_init()  argument
1051 	iter->b = b;  in __bch_btree_iter_init()
1054 	for (; start <= bset_tree_last(b); start++) {  in __bch_btree_iter_init()
1055 		ret = bch_bset_search(b, start, search);  in __bch_btree_iter_init()
1062 struct bkey *bch_btree_iter_init(struct btree_keys *b,  in bch_btree_iter_init()  argument
1066 	return __bch_btree_iter_init(b, iter, search, b->set);  in bch_btree_iter_init()
1104 					struct btree_keys *b, ptr_filter_fn fn)  in bch_btree_iter_next_filter()  argument
1110 	} while (ret && fn(b, ret));  in bch_btree_iter_next_filter()
1138 static void btree_mergesort(struct btree_keys *b, struct bset *out,  in btree_mergesort()  argument
1151 		heap_sift(iter, i, b->ops->sort_cmp);  in btree_mergesort()
1154 		if (b->ops->sort_fixup && fixup)  in btree_mergesort()
1155 			k = b->ops->sort_fixup(iter, &tmp.k);  in btree_mergesort()
1160 			k = __bch_btree_iter_next(iter, b->ops->sort_cmp);  in btree_mergesort()
1162 		if (bad(b, k))  in btree_mergesort()
1168 		} else if (!bch_bkey_try_merge(b, last, k)) {  in btree_mergesort()
1179 static void __btree_sort(struct btree_keys *b, struct btree_iter *iter,  in __btree_sort()  argument
1200 	btree_mergesort(b, out, iter, fixup, false);  in __btree_sort()
1201 	b->nsets = start;  in __btree_sort()
1203 	if (!start && order == b->page_order) {  in __btree_sort()
1210 		out->magic	= b->set->data->magic;  in __btree_sort()
1211 		out->seq	= b->set->data->seq;  in __btree_sort()
1212 		out->version	= b->set->data->version;  in __btree_sort()
1213 		swap(out, b->set->data);  in __btree_sort()
1215 		b->set[start].data->keys = out->keys;  in __btree_sort()
1216 		memcpy(b->set[start].data->start, out->start,  in __btree_sort()
1225 	bch_bset_build_written_tree(b);  in __btree_sort()
1231 void bch_btree_sort_partial(struct btree_keys *b, unsigned start,  in bch_btree_sort_partial()  argument
1234 	size_t order = b->page_order, keys = 0;  in bch_btree_sort_partial()
1236 	int oldsize = bch_count_data(b);  in bch_btree_sort_partial()
1238 	__bch_btree_iter_init(b, &iter, NULL, &b->set[start]);  in bch_btree_sort_partial()
1243 		for (i = start; i <= b->nsets; i++)  in bch_btree_sort_partial()
1244 			keys += b->set[i].data->keys;  in bch_btree_sort_partial()
1246 		order = get_order(__set_bytes(b->set->data, keys));  in bch_btree_sort_partial()
1249 	__btree_sort(b, &iter, start, order, false, state);  in bch_btree_sort_partial()
1251 	EBUG_ON(oldsize >= 0 && bch_count_data(b) != oldsize);  in bch_btree_sort_partial()
1255 void bch_btree_sort_and_fix_extents(struct btree_keys *b,  in bch_btree_sort_and_fix_extents()  argument
1259 	__btree_sort(b, iter, 0, b->page_order, true, state);  in bch_btree_sort_and_fix_extents()
1262 void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new,  in bch_btree_sort_into()  argument
1268 	bch_btree_iter_init(b, &iter, NULL);  in bch_btree_sort_into()
1270 	btree_mergesort(b, new->set->data, &iter, false, true);  in bch_btree_sort_into()
1279 void bch_btree_sort_lazy(struct btree_keys *b, struct bset_sort_state *state)  in bch_btree_sort_lazy()  argument
1285 	if (!b->nsets)  in bch_btree_sort_lazy()
1288 	for (i = b->nsets - 1; i >= 0; --i) {  in bch_btree_sort_lazy()
1291 		if (b->set[i].data->keys < crit) {  in bch_btree_sort_lazy()
1292 			bch_btree_sort_partial(b, i, state);  in bch_btree_sort_lazy()
1298 	if (b->nsets + 1 == MAX_BSETS) {  in bch_btree_sort_lazy()
1299 		bch_btree_sort(b, state);  in bch_btree_sort_lazy()
1304 	bch_bset_build_written_tree(b);  in bch_btree_sort_lazy()
1308 void bch_btree_keys_stats(struct btree_keys *b, struct bset_stats *stats)  in bch_btree_keys_stats()  argument
1312 	for (i = 0; i <= b->nsets; i++) {  in bch_btree_keys_stats()
1313 		struct bset_tree *t = &b->set[i];  in bch_btree_keys_stats()
1317 		if (bset_written(b, t)) {  in bch_btree_keys_stats()