xref: /linux/drivers/md/bcache/bset.h (revision fa84cf094ef9667e2b91c104b0a788fd1896f482)
1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef _BCACHE_BSET_H
3 #define _BCACHE_BSET_H
4 
5 #include <linux/bcache.h>
6 #include <linux/kernel.h>
7 #include <linux/types.h>
8 
9 #include "util.h" /* for time_stats */
10 
11 /*
12  * BKEYS:
13  *
14  * A bkey contains a key, a size field, a variable number of pointers, and some
15  * ancillary flag bits.
16  *
17  * We use two different functions for validating bkeys, bch_ptr_invalid and
18  * bch_ptr_bad().
19  *
20  * bch_ptr_invalid() primarily filters out keys and pointers that would be
21  * invalid due to some sort of bug, whereas bch_ptr_bad() filters out keys and
22  * pointer that occur in normal practice but don't point to real data.
23  *
24  * The one exception to the rule that ptr_invalid() filters out invalid keys is
25  * that it also filters out keys of size 0 - these are keys that have been
26  * completely overwritten. It'd be safe to delete these in memory while leaving
27  * them on disk, just unnecessary work - so we filter them out when resorting
28  * instead.
29  *
30  * We can't filter out stale keys when we're resorting, because garbage
31  * collection needs to find them to ensure bucket gens don't wrap around -
32  * unless we're rewriting the btree node those stale keys still exist on disk.
33  *
34  * We also implement functions here for removing some number of sectors from the
35  * front or the back of a bkey - this is mainly used for fixing overlapping
36  * extents, by removing the overlapping sectors from the older key.
37  *
38  * BSETS:
39  *
40  * A bset is an array of bkeys laid out contiguously in memory in sorted order,
41  * along with a header. A btree node is made up of a number of these, written at
42  * different times.
43  *
44  * There could be many of them on disk, but we never allow there to be more than
45  * 4 in memory - we lazily resort as needed.
46  *
47  * We implement code here for creating and maintaining auxiliary search trees
48  * (described below) for searching an individial bset, and on top of that we
49  * implement a btree iterator.
50  *
51  * BTREE ITERATOR:
52  *
53  * Most of the code in bcache doesn't care about an individual bset - it needs
54  * to search entire btree nodes and iterate over them in sorted order.
55  *
56  * The btree iterator code serves both functions; it iterates through the keys
57  * in a btree node in sorted order, starting from either keys after a specific
58  * point (if you pass it a search key) or the start of the btree node.
59  *
60  * AUXILIARY SEARCH TREES:
61  *
62  * Since keys are variable length, we can't use a binary search on a bset - we
63  * wouldn't be able to find the start of the next key. But binary searches are
64  * slow anyways, due to terrible cache behaviour; bcache originally used binary
65  * searches and that code topped out at under 50k lookups/second.
66  *
67  * So we need to construct some sort of lookup table. Since we only insert keys
68  * into the last (unwritten) set, most of the keys within a given btree node are
69  * usually in sets that are mostly constant. We use two different types of
70  * lookup tables to take advantage of this.
71  *
72  * Both lookup tables share in common that they don't index every key in the
73  * set; they index one key every BSET_CACHELINE bytes, and then a linear search
74  * is used for the rest.
75  *
76  * For sets that have been written to disk and are no longer being inserted
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
79  * fast, since both children of any node are adjacent to each other in memory
80  * (and their grandchildren, and great grandchildren...) - this means
81  * prefetching can be used to great effect.
82  *
83  * It's quite useful performance wise to keep these nodes small - not just
84  * because they're more likely to be in L2, but also because we can prefetch
85  * more nodes on a single cacheline and thus prefetch more iterations in advance
86  * when traversing this tree.
87  *
88  * Nodes in the auxiliary search tree must contain both a key to compare against
89  * (we don't want to fetch the key from the set, that would defeat the purpose),
90  * and a pointer to the key. We use a few tricks to compress both of these.
91  *
92  * To compress the pointer, we take advantage of the fact that one node in the
93  * search tree corresponds to precisely BSET_CACHELINE bytes in the set. We have
94  * a function (to_inorder()) that takes the index of a node in a binary tree and
95  * returns what its index would be in an inorder traversal, so we only have to
96  * store the low bits of the offset.
97  *
98  * The key is 84 bits (KEY_DEV + key->key, the offset on the device). To
99  * compress that,  we take advantage of the fact that when we're traversing the
100  * search tree at every iteration we know that both our search key and the key
101  * we're looking for lie within some range - bounded by our previous
102  * comparisons. (We special case the start of a search so that this is true even
103  * at the root of the tree).
104  *
105  * So we know the key we're looking for is between a and b, and a and b don't
106  * differ higher than bit 50, we don't need to check anything higher than bit
107  * 50.
108  *
109  * We don't usually need the rest of the bits, either; we only need enough bits
110  * to partition the key range we're currently checking.  Consider key n - the
111  * key our auxiliary search tree node corresponds to, and key p, the key
112  * immediately preceding n.  The lowest bit we need to store in the auxiliary
113  * search tree is the highest bit that differs between n and p.
114  *
115  * Note that this could be bit 0 - we might sometimes need all 80 bits to do the
116  * comparison. But we'd really like our nodes in the auxiliary search tree to be
117  * of fixed size.
118  *
119  * The solution is to make them fixed size, and when we're constructing a node
120  * check if p and n differed in the bits we needed them to. If they don't we
121  * flag that node, and when doing lookups we fallback to comparing against the
122  * real key. As long as this doesn't happen to often (and it seems to reliably
123  * happen a bit less than 1% of the time), we win - even on failures, that key
124  * is then more likely to be in cache than if we were doing binary searches all
125  * the way, since we're touching so much less memory.
126  *
127  * The keys in the auxiliary search tree are stored in (software) floating
128  * point, with an exponent and a mantissa. The exponent needs to be big enough
129  * to address all the bits in the original key, but the number of bits in the
130  * mantissa is somewhat arbitrary; more bits just gets us fewer failures.
131  *
132  * We need 7 bits for the exponent and 3 bits for the key's offset (since keys
133  * are 8 byte aligned); using 22 bits for the mantissa means a node is 4 bytes.
134  * We need one node per 128 bytes in the btree node, which means the auxiliary
135  * search trees take up 3% as much memory as the btree itself.
136  *
137  * Constructing these auxiliary search trees is moderately expensive, and we
138  * don't want to be constantly rebuilding the search tree for the last set
139  * whenever we insert another key into it. For the unwritten set, we use a much
140  * simpler lookup table - it's just a flat array, so index i in the lookup table
141  * corresponds to the i range of BSET_CACHELINE bytes in the set. Indexing
142  * within each byte range works the same as with the auxiliary search trees.
143  *
144  * These are much easier to keep up to date when we insert a key - we do it
145  * somewhat lazily; when we shift a key up we usually just increment the pointer
146  * to it, only when it would overflow do we go to the trouble of finding the
147  * first key in that range of bytes again.
148  */
149 
150 struct btree_keys;
151 struct btree_iter;
152 struct btree_iter_set;
153 struct bkey_float;
154 
155 #define MAX_BSETS		4U
156 
157 struct bset_tree {
158 	/*
159 	 * We construct a binary tree in an array as if the array
160 	 * started at 1, so that things line up on the same cachelines
161 	 * better: see comments in bset.c at cacheline_to_bkey() for
162 	 * details
163 	 */
164 
165 	/* size of the binary tree and prev array */
166 	unsigned		size;
167 
168 	/* function of size - precalculated for to_inorder() */
169 	unsigned		extra;
170 
171 	/* copy of the last key in the set */
172 	struct bkey		end;
173 	struct bkey_float	*tree;
174 
175 	/*
176 	 * The nodes in the bset tree point to specific keys - this
177 	 * array holds the sizes of the previous key.
178 	 *
179 	 * Conceptually it's a member of struct bkey_float, but we want
180 	 * to keep bkey_float to 4 bytes and prev isn't used in the fast
181 	 * path.
182 	 */
183 	uint8_t			*prev;
184 
185 	/* The actual btree node, with pointers to each sorted set */
186 	struct bset		*data;
187 };
188 
189 struct btree_keys_ops {
190 	bool		(*sort_cmp)(struct btree_iter_set,
191 				    struct btree_iter_set);
192 	struct bkey	*(*sort_fixup)(struct btree_iter *, struct bkey *);
193 	bool		(*insert_fixup)(struct btree_keys *, struct bkey *,
194 					struct btree_iter *, struct bkey *);
195 	bool		(*key_invalid)(struct btree_keys *,
196 				       const struct bkey *);
197 	bool		(*key_bad)(struct btree_keys *, const struct bkey *);
198 	bool		(*key_merge)(struct btree_keys *,
199 				     struct bkey *, struct bkey *);
200 	void		(*key_to_text)(char *, size_t, const struct bkey *);
201 	void		(*key_dump)(struct btree_keys *, const struct bkey *);
202 
203 	/*
204 	 * Only used for deciding whether to use START_KEY(k) or just the key
205 	 * itself in a couple places
206 	 */
207 	bool		is_extents;
208 };
209 
210 struct btree_keys {
211 	const struct btree_keys_ops	*ops;
212 	uint8_t			page_order;
213 	uint8_t			nsets;
214 	unsigned		last_set_unwritten:1;
215 	bool			*expensive_debug_checks;
216 
217 	/*
218 	 * Sets of sorted keys - the real btree node - plus a binary search tree
219 	 *
220 	 * set[0] is special; set[0]->tree, set[0]->prev and set[0]->data point
221 	 * to the memory we have allocated for this btree node. Additionally,
222 	 * set[0]->data points to the entire btree node as it exists on disk.
223 	 */
224 	struct bset_tree	set[MAX_BSETS];
225 };
226 
227 static inline struct bset_tree *bset_tree_last(struct btree_keys *b)
228 {
229 	return b->set + b->nsets;
230 }
231 
232 static inline bool bset_written(struct btree_keys *b, struct bset_tree *t)
233 {
234 	return t <= b->set + b->nsets - b->last_set_unwritten;
235 }
236 
237 static inline bool bkey_written(struct btree_keys *b, struct bkey *k)
238 {
239 	return !b->last_set_unwritten || k < b->set[b->nsets].data->start;
240 }
241 
242 static inline unsigned bset_byte_offset(struct btree_keys *b, struct bset *i)
243 {
244 	return ((size_t) i) - ((size_t) b->set->data);
245 }
246 
247 static inline unsigned bset_sector_offset(struct btree_keys *b, struct bset *i)
248 {
249 	return bset_byte_offset(b, i) >> 9;
250 }
251 
252 #define __set_bytes(i, k)	(sizeof(*(i)) + (k) * sizeof(uint64_t))
253 #define set_bytes(i)		__set_bytes(i, i->keys)
254 
255 #define __set_blocks(i, k, block_bytes)				\
256 	DIV_ROUND_UP(__set_bytes(i, k), block_bytes)
257 #define set_blocks(i, block_bytes)				\
258 	__set_blocks(i, (i)->keys, block_bytes)
259 
260 static inline size_t bch_btree_keys_u64s_remaining(struct btree_keys *b)
261 {
262 	struct bset_tree *t = bset_tree_last(b);
263 
264 	BUG_ON((PAGE_SIZE << b->page_order) <
265 	       (bset_byte_offset(b, t->data) + set_bytes(t->data)));
266 
267 	if (!b->last_set_unwritten)
268 		return 0;
269 
270 	return ((PAGE_SIZE << b->page_order) -
271 		(bset_byte_offset(b, t->data) + set_bytes(t->data))) /
272 		sizeof(u64);
273 }
274 
275 static inline struct bset *bset_next_set(struct btree_keys *b,
276 					 unsigned block_bytes)
277 {
278 	struct bset *i = bset_tree_last(b)->data;
279 
280 	return ((void *) i) + roundup(set_bytes(i), block_bytes);
281 }
282 
283 void bch_btree_keys_free(struct btree_keys *);
284 int bch_btree_keys_alloc(struct btree_keys *, unsigned, gfp_t);
285 void bch_btree_keys_init(struct btree_keys *, const struct btree_keys_ops *,
286 			 bool *);
287 
288 void bch_bset_init_next(struct btree_keys *, struct bset *, uint64_t);
289 void bch_bset_build_written_tree(struct btree_keys *);
290 void bch_bset_fix_invalidated_key(struct btree_keys *, struct bkey *);
291 bool bch_bkey_try_merge(struct btree_keys *, struct bkey *, struct bkey *);
292 void bch_bset_insert(struct btree_keys *, struct bkey *, struct bkey *);
293 unsigned bch_btree_insert_key(struct btree_keys *, struct bkey *,
294 			      struct bkey *);
295 
296 enum {
297 	BTREE_INSERT_STATUS_NO_INSERT = 0,
298 	BTREE_INSERT_STATUS_INSERT,
299 	BTREE_INSERT_STATUS_BACK_MERGE,
300 	BTREE_INSERT_STATUS_OVERWROTE,
301 	BTREE_INSERT_STATUS_FRONT_MERGE,
302 };
303 
304 /* Btree key iteration */
305 
306 struct btree_iter {
307 	size_t size, used;
308 #ifdef CONFIG_BCACHE_DEBUG
309 	struct btree_keys *b;
310 #endif
311 	struct btree_iter_set {
312 		struct bkey *k, *end;
313 	} data[MAX_BSETS];
314 };
315 
316 typedef bool (*ptr_filter_fn)(struct btree_keys *, const struct bkey *);
317 
318 struct bkey *bch_btree_iter_next(struct btree_iter *);
319 struct bkey *bch_btree_iter_next_filter(struct btree_iter *,
320 					struct btree_keys *, ptr_filter_fn);
321 
322 void bch_btree_iter_push(struct btree_iter *, struct bkey *, struct bkey *);
323 struct bkey *bch_btree_iter_init(struct btree_keys *, struct btree_iter *,
324 				 struct bkey *);
325 
326 struct bkey *__bch_bset_search(struct btree_keys *, struct bset_tree *,
327 			       const struct bkey *);
328 
329 /*
330  * Returns the first key that is strictly greater than search
331  */
332 static inline struct bkey *bch_bset_search(struct btree_keys *b,
333 					   struct bset_tree *t,
334 					   const struct bkey *search)
335 {
336 	return search ? __bch_bset_search(b, t, search) : t->data->start;
337 }
338 
339 #define for_each_key_filter(b, k, iter, filter)				\
340 	for (bch_btree_iter_init((b), (iter), NULL);			\
341 	     ((k) = bch_btree_iter_next_filter((iter), (b), filter));)
342 
343 #define for_each_key(b, k, iter)					\
344 	for (bch_btree_iter_init((b), (iter), NULL);			\
345 	     ((k) = bch_btree_iter_next(iter));)
346 
347 /* Sorting */
348 
349 struct bset_sort_state {
350 	mempool_t		pool;
351 
352 	unsigned		page_order;
353 	unsigned		crit_factor;
354 
355 	struct time_stats	time;
356 };
357 
358 void bch_bset_sort_state_free(struct bset_sort_state *);
359 int bch_bset_sort_state_init(struct bset_sort_state *, unsigned);
360 void bch_btree_sort_lazy(struct btree_keys *, struct bset_sort_state *);
361 void bch_btree_sort_into(struct btree_keys *, struct btree_keys *,
362 			 struct bset_sort_state *);
363 void bch_btree_sort_and_fix_extents(struct btree_keys *, struct btree_iter *,
364 				    struct bset_sort_state *);
365 void bch_btree_sort_partial(struct btree_keys *, unsigned,
366 			    struct bset_sort_state *);
367 
368 static inline void bch_btree_sort(struct btree_keys *b,
369 				  struct bset_sort_state *state)
370 {
371 	bch_btree_sort_partial(b, 0, state);
372 }
373 
374 struct bset_stats {
375 	size_t sets_written, sets_unwritten;
376 	size_t bytes_written, bytes_unwritten;
377 	size_t floats, failed;
378 };
379 
380 void bch_btree_keys_stats(struct btree_keys *, struct bset_stats *);
381 
382 /* Bkey utility code */
383 
384 #define bset_bkey_last(i)	bkey_idx((struct bkey *) (i)->d, (i)->keys)
385 
386 static inline struct bkey *bset_bkey_idx(struct bset *i, unsigned idx)
387 {
388 	return bkey_idx(i->start, idx);
389 }
390 
391 static inline void bkey_init(struct bkey *k)
392 {
393 	*k = ZERO_KEY;
394 }
395 
396 static __always_inline int64_t bkey_cmp(const struct bkey *l,
397 					const struct bkey *r)
398 {
399 	return unlikely(KEY_INODE(l) != KEY_INODE(r))
400 		? (int64_t) KEY_INODE(l) - (int64_t) KEY_INODE(r)
401 		: (int64_t) KEY_OFFSET(l) - (int64_t) KEY_OFFSET(r);
402 }
403 
404 void bch_bkey_copy_single_ptr(struct bkey *, const struct bkey *,
405 			      unsigned);
406 bool __bch_cut_front(const struct bkey *, struct bkey *);
407 bool __bch_cut_back(const struct bkey *, struct bkey *);
408 
409 static inline bool bch_cut_front(const struct bkey *where, struct bkey *k)
410 {
411 	BUG_ON(bkey_cmp(where, k) > 0);
412 	return __bch_cut_front(where, k);
413 }
414 
415 static inline bool bch_cut_back(const struct bkey *where, struct bkey *k)
416 {
417 	BUG_ON(bkey_cmp(where, &START_KEY(k)) < 0);
418 	return __bch_cut_back(where, k);
419 }
420 
421 #define PRECEDING_KEY(_k)					\
422 ({								\
423 	struct bkey *_ret = NULL;				\
424 								\
425 	if (KEY_INODE(_k) || KEY_OFFSET(_k)) {			\
426 		_ret = &KEY(KEY_INODE(_k), KEY_OFFSET(_k), 0);	\
427 								\
428 		if (!_ret->low)					\
429 			_ret->high--;				\
430 		_ret->low--;					\
431 	}							\
432 								\
433 	_ret;							\
434 })
435 
436 static inline bool bch_ptr_invalid(struct btree_keys *b, const struct bkey *k)
437 {
438 	return b->ops->key_invalid(b, k);
439 }
440 
441 static inline bool bch_ptr_bad(struct btree_keys *b, const struct bkey *k)
442 {
443 	return b->ops->key_bad(b, k);
444 }
445 
446 static inline void bch_bkey_to_text(struct btree_keys *b, char *buf,
447 				    size_t size, const struct bkey *k)
448 {
449 	return b->ops->key_to_text(buf, size, k);
450 }
451 
452 static inline bool bch_bkey_equal_header(const struct bkey *l,
453 					 const struct bkey *r)
454 {
455 	return (KEY_DIRTY(l) == KEY_DIRTY(r) &&
456 		KEY_PTRS(l) == KEY_PTRS(r) &&
457 		KEY_CSUM(l) == KEY_CSUM(r));
458 }
459 
460 /* Keylists */
461 
462 struct keylist {
463 	union {
464 		struct bkey		*keys;
465 		uint64_t		*keys_p;
466 	};
467 	union {
468 		struct bkey		*top;
469 		uint64_t		*top_p;
470 	};
471 
472 	/* Enough room for btree_split's keys without realloc */
473 #define KEYLIST_INLINE		16
474 	uint64_t		inline_keys[KEYLIST_INLINE];
475 };
476 
477 static inline void bch_keylist_init(struct keylist *l)
478 {
479 	l->top_p = l->keys_p = l->inline_keys;
480 }
481 
482 static inline void bch_keylist_init_single(struct keylist *l, struct bkey *k)
483 {
484 	l->keys = k;
485 	l->top = bkey_next(k);
486 }
487 
488 static inline void bch_keylist_push(struct keylist *l)
489 {
490 	l->top = bkey_next(l->top);
491 }
492 
493 static inline void bch_keylist_add(struct keylist *l, struct bkey *k)
494 {
495 	bkey_copy(l->top, k);
496 	bch_keylist_push(l);
497 }
498 
499 static inline bool bch_keylist_empty(struct keylist *l)
500 {
501 	return l->top == l->keys;
502 }
503 
504 static inline void bch_keylist_reset(struct keylist *l)
505 {
506 	l->top = l->keys;
507 }
508 
509 static inline void bch_keylist_free(struct keylist *l)
510 {
511 	if (l->keys_p != l->inline_keys)
512 		kfree(l->keys_p);
513 }
514 
515 static inline size_t bch_keylist_nkeys(struct keylist *l)
516 {
517 	return l->top_p - l->keys_p;
518 }
519 
520 static inline size_t bch_keylist_bytes(struct keylist *l)
521 {
522 	return bch_keylist_nkeys(l) * sizeof(uint64_t);
523 }
524 
525 struct bkey *bch_keylist_pop(struct keylist *);
526 void bch_keylist_pop_front(struct keylist *);
527 int __bch_keylist_realloc(struct keylist *, unsigned);
528 
529 /* Debug stuff */
530 
531 #ifdef CONFIG_BCACHE_DEBUG
532 
533 int __bch_count_data(struct btree_keys *);
534 void __printf(2, 3) __bch_check_keys(struct btree_keys *, const char *, ...);
535 void bch_dump_bset(struct btree_keys *, struct bset *, unsigned);
536 void bch_dump_bucket(struct btree_keys *);
537 
538 #else
539 
540 static inline int __bch_count_data(struct btree_keys *b) { return -1; }
541 static inline void __printf(2, 3)
542 	__bch_check_keys(struct btree_keys *b, const char *fmt, ...) {}
543 static inline void bch_dump_bucket(struct btree_keys *b) {}
544 void bch_dump_bset(struct btree_keys *, struct bset *, unsigned);
545 
546 #endif
547 
548 static inline bool btree_keys_expensive_checks(struct btree_keys *b)
549 {
550 #ifdef CONFIG_BCACHE_DEBUG
551 	return *b->expensive_debug_checks;
552 #else
553 	return false;
554 #endif
555 }
556 
557 static inline int bch_count_data(struct btree_keys *b)
558 {
559 	return btree_keys_expensive_checks(b) ? __bch_count_data(b) : -1;
560 }
561 
562 #define bch_check_keys(b, ...)						\
563 do {									\
564 	if (btree_keys_expensive_checks(b))				\
565 		__bch_check_keys(b, __VA_ARGS__);			\
566 } while (0)
567 
568 #endif
569