1 /* SPDX-License-Identifier: GPL-2.0 */
25  * that it also filters out keys of size 0 - these are keys that have been
27  * them on disk, just unnecessary work - so we filter them out when resorting
31  * collection needs to find them to ensure bucket gens don't wrap around -
35  * front or the back of a bkey - this is mainly used for fixing overlapping
45  * 4 in memory - we lazily resort as needed.
53  * Most of the code in bcache doesn't care about an individual bset - it needs
57  * in a btree node in sorted order, starting from either keys after a specific
62  * Since keys are variable length, we can't use a binary search on a bset - we
77  * into, we construct a binary search tree in an array - traversing a binary
78  * search tree in an array gives excellent locality of reference and is very
80  * (and their grandchildren, and great grandchildren...) - this means
83  * It's quite useful performance wise to keep these nodes small - not just
98  * The key is 84 bits (KEY_DEV + key->key, the offset on the device). To
101  * we're looking for lie within some range - bounded by our previous
110  * to partition the key range we're currently checking.  Consider key n - the
115  * Note that this could be bit 0 - we might sometimes need all 80 bits to do the
123  * happen a bit less than 1% of the time), we win - even on failures, that key
140  * simpler lookup table - it's just a flat array, so index i in the lookup table
144  * These are much easier to keep up to date when we insert a key - we do it
168 	/* function of size - precalculated for to_inorder() */
176 	 * The nodes in the bset tree point to specific keys - this
225 	 * Sets of sorted keys - the real btree node - plus a binary search tree
227 	 * set[0] is special; set[0]->tree, set[0]->prev and set[0]->data point
229 	 * set[0]->data points to the entire btree node as it exists on disk.
236 	return b->set + b->nsets;  in bset_tree_last()
241 	return t <= b->set + b->nsets - b->last_set_unwritten;  in bset_written()
246 	return !b->last_set_unwritten || k < b->set[b->nsets].data->start;  in bkey_written()
252 	return ((size_t) i) - ((size_t) b->set->data);  in bset_byte_offset()
262 #define set_bytes(i)		__set_bytes(i, i->keys)
267 	__set_blocks(i, (i)->keys, block_bytes)
273 	BUG_ON((PAGE_SIZE << b->page_order) <  in bch_btree_keys_u64s_remaining()
274 	       (bset_byte_offset(b, t->data) + set_bytes(t->data)));  in bch_btree_keys_u64s_remaining()
276 	if (!b->last_set_unwritten)  in bch_btree_keys_u64s_remaining()
279 	return ((PAGE_SIZE << b->page_order) -  in bch_btree_keys_u64s_remaining()
280 		(bset_byte_offset(b, t->data) + set_bytes(t->data))) /  in bch_btree_keys_u64s_remaining()
287 	struct bset *i = bset_tree_last(b)->data;  in bset_next_set()
350 	return search ? __bch_bset_search(b, t, search) : t->data->start;  in bch_bset_search()
400 #define bset_bkey_last(i)	bkey_idx((struct bkey *) (i)->d, \
401 					 (unsigned int)(i)->keys)
405 	return bkey_idx(i->start, idx);  in bset_bkey_idx()
417 		? (int64_t) KEY_INODE(l) - (int64_t) KEY_INODE(r)  in bkey_cmp()
418 		: (int64_t) KEY_OFFSET(l) - (int64_t) KEY_OFFSET(r);  in bkey_cmp()
444  * and it points to an on-stack variable, so the memory release is handled
451 		if (!(*preceding_key_p)->low)  in preceding_key()
452 			(*preceding_key_p)->high--;  in preceding_key()
453 		(*preceding_key_p)->low--;  in preceding_key()
461 	return b->ops->key_invalid(b, k);  in bch_ptr_invalid()
466 	return b->ops->key_bad(b, k);  in bch_ptr_bad()
472 	return b->ops->key_to_text(buf, size, k);  in bch_bkey_to_text()
502 	l->top_p = l->keys_p = l->inline_keys;  in bch_keylist_init()
507 	l->keys = k;  in bch_keylist_init_single()
508 	l->top = bkey_next(k);  in bch_keylist_init_single()
513 	l->top = bkey_next(l->top);  in bch_keylist_push()
518 	bkey_copy(l->top, k);  in bch_keylist_add()
524 	return l->top == l->keys;  in bch_keylist_empty()
529 	l->top = l->keys;  in bch_keylist_reset()
534 	if (l->keys_p != l->inline_keys)  in bch_keylist_free()
535 		kfree(l->keys_p);  in bch_keylist_free()
540 	return l->top_p - l->keys_p;  in bch_keylist_nkeys()
565 static inline int __bch_count_data(struct btree_keys *b) { return -1; }  in __bch_count_data()
576 	return *b->expensive_debug_checks;  in btree_keys_expensive_checks()
584 	return btree_keys_expensive_checks(b) ? __bch_count_data(b) : -1;  in bch_count_data()