292 	struct bset_tree *t = b->set;  in bch_btree_keys_free()  local
295 		kfree(t->prev);  in bch_btree_keys_free()
297 		free_pages((unsigned long) t->prev,  in bch_btree_keys_free()
301 		kfree(t->tree);  in bch_btree_keys_free()
303 		free_pages((unsigned long) t->tree,  in bch_btree_keys_free()
306 	free_pages((unsigned long) t->data, b->page_order);  in bch_btree_keys_free()
308 	t->prev = NULL;  in bch_btree_keys_free()
309 	t->tree = NULL;  in bch_btree_keys_free()
310 	t->data = NULL;  in bch_btree_keys_free()
318 	struct bset_tree *t = b->set;  in bch_btree_keys_alloc()  local
320 	BUG_ON(t->data);  in bch_btree_keys_alloc()
324 	t->data = (void *) __get_free_pages(gfp, b->page_order);  in bch_btree_keys_alloc()
325 	if (!t->data)  in bch_btree_keys_alloc()
328 	t->tree = bset_tree_bytes(b) < PAGE_SIZE  in bch_btree_keys_alloc()
331 	if (!t->tree)  in bch_btree_keys_alloc()
334 	t->prev = bset_prev_bytes(b) < PAGE_SIZE  in bch_btree_keys_alloc()
337 	if (!t->prev)  in bch_btree_keys_alloc()
438 static unsigned int to_inorder(unsigned int j, struct bset_tree *t)  in to_inorder()  argument
440 	return __to_inorder(j, t->size, t->extra);  in to_inorder()
464 static unsigned int inorder_to_tree(unsigned int j, struct bset_tree *t)  in inorder_to_tree()  argument
466 	return __inorder_to_tree(j, t->size, t->extra);  in inorder_to_tree()
526 static struct bkey *cacheline_to_bkey(struct bset_tree *t,  in cacheline_to_bkey()  argument
530 	return ((void *) t->data) + cacheline * BSET_CACHELINE + offset * 8;  in cacheline_to_bkey()
533 static unsigned int bkey_to_cacheline(struct bset_tree *t, struct bkey *k)  in bkey_to_cacheline()  argument
535 	return ((void *) k - (void *) t->data) / BSET_CACHELINE;  in bkey_to_cacheline()
538 static unsigned int bkey_to_cacheline_offset(struct bset_tree *t,  in bkey_to_cacheline_offset()  argument
542 	return (u64 *) k - (u64 *) cacheline_to_bkey(t, cacheline, 0);  in bkey_to_cacheline_offset()
545 static struct bkey *tree_to_bkey(struct bset_tree *t, unsigned int j)  in tree_to_bkey()  argument
547 	return cacheline_to_bkey(t, to_inorder(j, t), t->tree[j].m);  in tree_to_bkey()
550 static struct bkey *tree_to_prev_bkey(struct bset_tree *t, unsigned int j)  in tree_to_prev_bkey()  argument
552 	return (void *) (((uint64_t *) tree_to_bkey(t, j)) - t->prev[j]);  in tree_to_prev_bkey()
559 static struct bkey *table_to_bkey(struct bset_tree *t, unsigned int cacheline)  in table_to_bkey()  argument
561 	return cacheline_to_bkey(t, cacheline, t->prev[cacheline]);  in table_to_bkey()
593 static void make_bfloat(struct bset_tree *t, unsigned int j)  in make_bfloat()  argument
595 	struct bkey_float *f = &t->tree[j];  in make_bfloat()
596 	struct bkey *m = tree_to_bkey(t, j);  in make_bfloat()
597 	struct bkey *p = tree_to_prev_bkey(t, j);  in make_bfloat()
600 		? t->data->start  in make_bfloat()
601 		: tree_to_prev_bkey(t, j >> ffs(j));  in make_bfloat()
604 		? bset_bkey_idx(t->data, t->data->keys - bkey_u64s(&t->end))  in make_bfloat()
605 		: tree_to_bkey(t, j >> (ffz(j) + 1));  in make_bfloat()
638 static void bset_alloc_tree(struct btree_keys *b, struct bset_tree *t)  in bset_alloc_tree()  argument
640 	if (t != b->set) {  in bset_alloc_tree()
641 		unsigned int j = roundup(t[-1].size,  in bset_alloc_tree()
644 		t->tree = t[-1].tree + j;  in bset_alloc_tree()
645 		t->prev = t[-1].prev + j;  in bset_alloc_tree()
648 	while (t < b->set + MAX_BSETS)  in bset_alloc_tree()
649 		t++->size = 0;  in bset_alloc_tree()
654 	struct bset_tree *t = bset_tree_last(b);  in bch_bset_build_unwritten_tree()  local
659 	bset_alloc_tree(b, t);  in bch_bset_build_unwritten_tree()
661 	if (t->tree != b->set->tree + btree_keys_cachelines(b)) {  in bch_bset_build_unwritten_tree()
662 		t->prev[0] = bkey_to_cacheline_offset(t, 0, t->data->start);  in bch_bset_build_unwritten_tree()
663 		t->size = 1;  in bch_bset_build_unwritten_tree()
694 	struct bset_tree *t = bset_tree_last(b);  in bch_bset_build_written_tree()  local
695 	struct bkey *prev = NULL, *k = t->data->start;  in bch_bset_build_written_tree()
700 	bset_alloc_tree(b, t);  in bch_bset_build_written_tree()
702 	t->size = min_t(unsigned int,  in bch_bset_build_written_tree()
703 			bkey_to_cacheline(t, bset_bkey_last(t->data)),  in bch_bset_build_written_tree()
704 			b->set->tree + btree_keys_cachelines(b) - t->tree);  in bch_bset_build_written_tree()
706 	if (t->size < 2) {  in bch_bset_build_written_tree()
707 		t->size = 0;  in bch_bset_build_written_tree()
711 	t->extra = (t->size - rounddown_pow_of_two(t->size - 1)) << 1;  in bch_bset_build_written_tree()
714 	for (j = inorder_next(0, t->size);  in bch_bset_build_written_tree()
716 	     j = inorder_next(j, t->size)) {  in bch_bset_build_written_tree()
717 		while (bkey_to_cacheline(t, k) < cacheline)  in bch_bset_build_written_tree()
720 		t->prev[j] = bkey_u64s(prev);  in bch_bset_build_written_tree()
721 		t->tree[j].m = bkey_to_cacheline_offset(t, cacheline++, k);  in bch_bset_build_written_tree()
724 	while (bkey_next(k) != bset_bkey_last(t->data))  in bch_bset_build_written_tree()
727 	t->end = *k;  in bch_bset_build_written_tree()
730 	for (j = inorder_next(0, t->size);  in bch_bset_build_written_tree()
732 	     j = inorder_next(j, t->size))  in bch_bset_build_written_tree()
733 		make_bfloat(t, j);  in bch_bset_build_written_tree()
741 	struct bset_tree *t;  in bch_bset_fix_invalidated_key()  local
744 	for (t = b->set; t <= bset_tree_last(b); t++)  in bch_bset_fix_invalidated_key()
745 		if (k < bset_bkey_last(t->data))  in bch_bset_fix_invalidated_key()
750 	if (!t->size || !bset_written(b, t))  in bch_bset_fix_invalidated_key()
753 	inorder = bkey_to_cacheline(t, k);  in bch_bset_fix_invalidated_key()
755 	if (k == t->data->start)  in bch_bset_fix_invalidated_key()
758 	if (bkey_next(k) == bset_bkey_last(t->data)) {  in bch_bset_fix_invalidated_key()
759 		t->end = *k;  in bch_bset_fix_invalidated_key()
763 	j = inorder_to_tree(inorder, t);  in bch_bset_fix_invalidated_key()
766 	    j < t->size &&  in bch_bset_fix_invalidated_key()
767 	    k == tree_to_bkey(t, j))  in bch_bset_fix_invalidated_key()
769 			make_bfloat(t, j);  in bch_bset_fix_invalidated_key()
771 		} while (j < t->size);  in bch_bset_fix_invalidated_key()
773 	j = inorder_to_tree(inorder + 1, t);  in bch_bset_fix_invalidated_key()
776 	    j < t->size &&  in bch_bset_fix_invalidated_key()
777 	    k == tree_to_prev_bkey(t, j))  in bch_bset_fix_invalidated_key()
779 			make_bfloat(t, j);  in bch_bset_fix_invalidated_key()
781 		} while (j < t->size);  in bch_bset_fix_invalidated_key()
786 				      struct bset_tree *t,  in bch_bset_fix_lookup_table()  argument
790 	unsigned int j = bkey_to_cacheline(t, k);  in bch_bset_fix_lookup_table()
793 	if (!t->size)  in bch_bset_fix_lookup_table()
801 	while (j < t->size &&  in bch_bset_fix_lookup_table()
802 	       table_to_bkey(t, j) <= k)  in bch_bset_fix_lookup_table()
809 	for (; j < t->size; j++) {  in bch_bset_fix_lookup_table()
810 		t->prev[j] += shift;  in bch_bset_fix_lookup_table()
812 		if (t->prev[j] > 7) {  in bch_bset_fix_lookup_table()
813 			k = table_to_bkey(t, j - 1);  in bch_bset_fix_lookup_table()
815 			while (k < cacheline_to_bkey(t, j, 0))  in bch_bset_fix_lookup_table()
818 			t->prev[j] = bkey_to_cacheline_offset(t, j, k);  in bch_bset_fix_lookup_table()
822 	if (t->size == b->set->tree + btree_keys_cachelines(b) - t->tree)  in bch_bset_fix_lookup_table()
827 	for (k = table_to_bkey(t, t->size - 1);  in bch_bset_fix_lookup_table()
828 	     k != bset_bkey_last(t->data);  in bch_bset_fix_lookup_table()
830 		if (t->size == bkey_to_cacheline(t, k)) {  in bch_bset_fix_lookup_table()
831 			t->prev[t->size] =  in bch_bset_fix_lookup_table()
832 				bkey_to_cacheline_offset(t, t->size, k);  in bch_bset_fix_lookup_table()
833 			t->size++;  in bch_bset_fix_lookup_table()
863 	struct bset_tree *t = bset_tree_last(b);  in bch_bset_insert()  local
866 	BUG_ON(bset_byte_offset(b, t->data) +  in bch_bset_insert()
867 	       __set_bytes(t->data, t->data->keys + bkey_u64s(insert)) >  in bch_bset_insert()
872 		(void *) bset_bkey_last(t->data) - (void *) where);  in bch_bset_insert()
874 	t->data->keys += bkey_u64s(insert);  in bch_bset_insert()
876 	bch_bset_fix_lookup_table(b, t, where);  in bch_bset_insert()
942 static struct bset_search_iter bset_search_write_set(struct bset_tree *t,  in bset_search_write_set()  argument
945 	unsigned int li = 0, ri = t->size;  in bset_search_write_set()
950 		if (bkey_cmp(table_to_bkey(t, m), search) > 0)  in bset_search_write_set()
957 		table_to_bkey(t, li),  in bset_search_write_set()
958 		ri < t->size ? table_to_bkey(t, ri) : bset_bkey_last(t->data)  in bset_search_write_set()
962 static struct bset_search_iter bset_search_tree(struct bset_tree *t,  in bset_search_tree()  argument
972 		if (p < t->size)  in bset_search_tree()
973 			prefetch(&t->tree[p]);  in bset_search_tree()
976 		f = &t->tree[j];  in bset_search_tree()
984 			if (bkey_cmp(tree_to_bkey(t, j), search) > 0)  in bset_search_tree()
989 	} while (n < t->size);  in bset_search_tree()
991 	inorder = to_inorder(j, t);  in bset_search_tree()
998 		l = cacheline_to_bkey(t, inorder, f->m);  in bset_search_tree()
1000 		if (++inorder != t->size) {  in bset_search_tree()
1001 			f = &t->tree[inorder_next(j, t->size)];  in bset_search_tree()
1002 			r = cacheline_to_bkey(t, inorder, f->m);  in bset_search_tree()
1004 			r = bset_bkey_last(t->data);  in bset_search_tree()
1006 		r = cacheline_to_bkey(t, inorder, f->m);  in bset_search_tree()
1009 			f = &t->tree[inorder_prev(j, t->size)];  in bset_search_tree()
1010 			l = cacheline_to_bkey(t, inorder, f->m);  in bset_search_tree()
1012 			l = t->data->start;  in bset_search_tree()
1018 struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t,  in __bch_bset_search()  argument
1038 	if (unlikely(!t->size)) {  in __bch_bset_search()
1039 		i.l = t->data->start;  in __bch_bset_search()
1040 		i.r = bset_bkey_last(t->data);  in __bch_bset_search()
1041 	} else if (bset_written(b, t)) {  in __bch_bset_search()
1049 		if (unlikely(bkey_cmp(search, &t->end) >= 0))  in __bch_bset_search()
1050 			return bset_bkey_last(t->data);  in __bch_bset_search()
1052 		if (unlikely(bkey_cmp(search, t->data->start) < 0))  in __bch_bset_search()
1053 			return t->data->start;  in __bch_bset_search()
1055 		i = bset_search_tree(t, search);  in __bch_bset_search()
1058 		       t->size < bkey_to_cacheline(t, bset_bkey_last(t->data)));  in __bch_bset_search()
1060 		i = bset_search_write_set(t, search);  in __bch_bset_search()
1064 		BUG_ON(bset_written(b, t) &&  in __bch_bset_search()
1065 		       i.l != t->data->start &&  in __bch_bset_search()
1066 		       bkey_cmp(tree_to_prev_bkey(t,  in __bch_bset_search()
1067 			  inorder_to_tree(bkey_to_cacheline(t, i.l), t)),  in __bch_bset_search()
1070 		BUG_ON(i.r != bset_bkey_last(t->data) &&  in __bch_bset_search()
1376 		struct bset_tree *t = &b->set[i];  in bch_btree_keys_stats()  local
1377 		size_t bytes = t->data->keys * sizeof(uint64_t);  in bch_btree_keys_stats()
1380 		if (bset_written(b, t)) {  in bch_btree_keys_stats()
1384 			stats->floats += t->size - 1;  in bch_btree_keys_stats()
1386 			for (j = 1; j < t->size; j++)  in bch_btree_keys_stats()
1387 				if (t->tree[j].exponent == 127)  in bch_btree_keys_stats()