1 /* SPDX-License-Identifier: GPL-2.0 */
5 #include <linux/bcache.h>
6 #include <linux/kernel.h>
7 #include <linux/types.h>
9 #include "util.h" /* for time_stats */
14 * A bkey contains a key, a size field, a variable number of pointers, and some
15 * ancillary flag bits.
17 * We use two different functions for validating bkeys, bch_ptr_invalid and
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.
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
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.
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.
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
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.
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.
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.
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.
60 * AUXILIARY SEARCH TREES:
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.
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.
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.
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.
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.
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.
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.
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).
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
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.
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
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.
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.
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.
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.
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.
152 struct btree_iter_set
;
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
165 /* size of the binary tree and prev array */
168 /* function of size - precalculated for to_inorder() */
171 /* copy of the last key in the set */
173 struct bkey_float
*tree
;
176 * The nodes in the bset tree point to specific keys - this
177 * array holds the sizes of the previous key.
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
185 /* The actual btree node, with pointers to each sorted set */
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
*);
204 * Only used for deciding whether to use START_KEY(k) or just the key
205 * itself in a couple places
211 const struct btree_keys_ops
*ops
;
214 unsigned last_set_unwritten
:1;
215 bool *expensive_debug_checks
;
218 * Sets of sorted keys - the real btree node - plus a binary search tree
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.
224 struct bset_tree set
[MAX_BSETS
];
227 static inline struct bset_tree
*bset_tree_last(struct btree_keys
*b
)
229 return b
->set
+ b
->nsets
;
232 static inline bool bset_written(struct btree_keys
*b
, struct bset_tree
*t
)
234 return t
<= b
->set
+ b
->nsets
- b
->last_set_unwritten
;
237 static inline bool bkey_written(struct btree_keys
*b
, struct bkey
*k
)
239 return !b
->last_set_unwritten
|| k
< b
->set
[b
->nsets
].data
->start
;
242 static inline unsigned bset_byte_offset(struct btree_keys
*b
, struct bset
*i
)
244 return ((size_t) i
) - ((size_t) b
->set
->data
);
247 static inline unsigned bset_sector_offset(struct btree_keys
*b
, struct bset
*i
)
249 return bset_byte_offset(b
, i
) >> 9;
252 #define __set_bytes(i, k) (sizeof(*(i)) + (k) * sizeof(uint64_t))
253 #define set_bytes(i) __set_bytes(i, i->keys)
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)
260 static inline size_t bch_btree_keys_u64s_remaining(struct btree_keys
*b
)
262 struct bset_tree
*t
= bset_tree_last(b
);
264 BUG_ON((PAGE_SIZE
<< b
->page_order
) <
265 (bset_byte_offset(b
, t
->data
) + set_bytes(t
->data
)));
267 if (!b
->last_set_unwritten
)
270 return ((PAGE_SIZE
<< b
->page_order
) -
271 (bset_byte_offset(b
, t
->data
) + set_bytes(t
->data
))) /
275 static inline struct bset
*bset_next_set(struct btree_keys
*b
,
276 unsigned block_bytes
)
278 struct bset
*i
= bset_tree_last(b
)->data
;
280 return ((void *) i
) + roundup(set_bytes(i
), block_bytes
);
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
*,
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
*,
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
,
304 /* Btree key iteration */
308 #ifdef CONFIG_BCACHE_DEBUG
309 struct btree_keys
*b
;
311 struct btree_iter_set
{
312 struct bkey
*k
, *end
;
316 typedef bool (*ptr_filter_fn
)(struct btree_keys
*, const struct bkey
*);
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
);
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
*,
326 struct bkey
*__bch_bset_search(struct btree_keys
*, struct bset_tree
*,
327 const struct bkey
*);
330 * Returns the first key that is strictly greater than search
332 static inline struct bkey
*bch_bset_search(struct btree_keys
*b
,
334 const struct bkey
*search
)
336 return search
? __bch_bset_search(b
, t
, search
) : t
->data
->start
;
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));)
343 #define for_each_key(b, k, iter) \
344 for (bch_btree_iter_init((b), (iter), NULL); \
345 ((k) = bch_btree_iter_next(iter));)
349 struct bset_sort_state
{
353 unsigned crit_factor
;
355 struct time_stats time
;
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
*);
368 static inline void bch_btree_sort(struct btree_keys
*b
,
369 struct bset_sort_state
*state
)
371 bch_btree_sort_partial(b
, 0, state
);
375 size_t sets_written
, sets_unwritten
;
376 size_t bytes_written
, bytes_unwritten
;
377 size_t floats
, failed
;
380 void bch_btree_keys_stats(struct btree_keys
*, struct bset_stats
*);
382 /* Bkey utility code */
384 #define bset_bkey_last(i) bkey_idx((struct bkey *) (i)->d, (i)->keys)
386 static inline struct bkey
*bset_bkey_idx(struct bset
*i
, unsigned idx
)
388 return bkey_idx(i
->start
, idx
);
391 static inline void bkey_init(struct bkey
*k
)
396 static __always_inline
int64_t bkey_cmp(const struct bkey
*l
,
397 const struct bkey
*r
)
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
);
404 void bch_bkey_copy_single_ptr(struct bkey
*, const struct bkey
*,
406 bool __bch_cut_front(const struct bkey
*, struct bkey
*);
407 bool __bch_cut_back(const struct bkey
*, struct bkey
*);
409 static inline bool bch_cut_front(const struct bkey
*where
, struct bkey
*k
)
411 BUG_ON(bkey_cmp(where
, k
) > 0);
412 return __bch_cut_front(where
, k
);
415 static inline bool bch_cut_back(const struct bkey
*where
, struct bkey
*k
)
417 BUG_ON(bkey_cmp(where
, &START_KEY(k
)) < 0);
418 return __bch_cut_back(where
, k
);
421 #define PRECEDING_KEY(_k) \
423 struct bkey *_ret = NULL; \
425 if (KEY_INODE(_k) || KEY_OFFSET(_k)) { \
426 _ret = &KEY(KEY_INODE(_k), KEY_OFFSET(_k), 0); \
436 static inline bool bch_ptr_invalid(struct btree_keys
*b
, const struct bkey
*k
)
438 return b
->ops
->key_invalid(b
, k
);
441 static inline bool bch_ptr_bad(struct btree_keys
*b
, const struct bkey
*k
)
443 return b
->ops
->key_bad(b
, k
);
446 static inline void bch_bkey_to_text(struct btree_keys
*b
, char *buf
,
447 size_t size
, const struct bkey
*k
)
449 return b
->ops
->key_to_text(buf
, size
, k
);
452 static inline bool bch_bkey_equal_header(const struct bkey
*l
,
453 const struct bkey
*r
)
455 return (KEY_DIRTY(l
) == KEY_DIRTY(r
) &&
456 KEY_PTRS(l
) == KEY_PTRS(r
) &&
457 KEY_CSUM(l
) == KEY_CSUM(r
));
472 /* Enough room for btree_split's keys without realloc */
473 #define KEYLIST_INLINE 16
474 uint64_t inline_keys
[KEYLIST_INLINE
];
477 static inline void bch_keylist_init(struct keylist
*l
)
479 l
->top_p
= l
->keys_p
= l
->inline_keys
;
482 static inline void bch_keylist_init_single(struct keylist
*l
, struct bkey
*k
)
485 l
->top
= bkey_next(k
);
488 static inline void bch_keylist_push(struct keylist
*l
)
490 l
->top
= bkey_next(l
->top
);
493 static inline void bch_keylist_add(struct keylist
*l
, struct bkey
*k
)
495 bkey_copy(l
->top
, k
);
499 static inline bool bch_keylist_empty(struct keylist
*l
)
501 return l
->top
== l
->keys
;
504 static inline void bch_keylist_reset(struct keylist
*l
)
509 static inline void bch_keylist_free(struct keylist
*l
)
511 if (l
->keys_p
!= l
->inline_keys
)
515 static inline size_t bch_keylist_nkeys(struct keylist
*l
)
517 return l
->top_p
- l
->keys_p
;
520 static inline size_t bch_keylist_bytes(struct keylist
*l
)
522 return bch_keylist_nkeys(l
) * sizeof(uint64_t);
525 struct bkey
*bch_keylist_pop(struct keylist
*);
526 void bch_keylist_pop_front(struct keylist
*);
527 int __bch_keylist_realloc(struct keylist
*, unsigned);
531 #ifdef CONFIG_BCACHE_DEBUG
533 int __bch_count_data(struct btree_keys
*);
534 void __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
*);
540 static inline int __bch_count_data(struct btree_keys
*b
) { return -1; }
541 static inline void __bch_check_keys(struct btree_keys
*b
, const char *fmt
, ...) {}
542 static inline void bch_dump_bucket(struct btree_keys
*b
) {}
543 void bch_dump_bset(struct btree_keys
*, struct bset
*, unsigned);
547 static inline bool btree_keys_expensive_checks(struct btree_keys
*b
)
549 #ifdef CONFIG_BCACHE_DEBUG
550 return *b
->expensive_debug_checks
;
556 static inline int bch_count_data(struct btree_keys
*b
)
558 return btree_keys_expensive_checks(b
) ? __bch_count_data(b
) : -1;
561 #define bch_check_keys(b, ...) \
563 if (btree_keys_expensive_checks(b)) \
564 __bch_check_keys(b, __VA_ARGS__); \