Commit | Line | Data |
---|---|---|
b2441318 | 1 | /* SPDX-License-Identifier: GPL-2.0 */ |
cafe5635 KO |
2 | #ifndef _BCACHE_BSET_H |
3 | #define _BCACHE_BSET_H | |
4 | ||
89ebb4a2 KO |
5 | #include <linux/bcache.h> |
6 | #include <linux/kernel.h> | |
7 | #include <linux/types.h> | |
c37511b8 | 8 | |
67539e85 KO |
9 | #include "util.h" /* for time_stats */ |
10 | ||
cafe5635 KO |
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 | ||
a85e968e KO |
150 | struct btree_keys; |
151 | struct btree_iter; | |
152 | struct btree_iter_set; | |
ee811287 | 153 | struct bkey_float; |
cafe5635 | 154 | |
c37511b8 KO |
155 | #define MAX_BSETS 4U |
156 | ||
cafe5635 KO |
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 */ | |
ee811287 | 166 | unsigned size; |
cafe5635 KO |
167 | |
168 | /* function of size - precalculated for to_inorder() */ | |
ee811287 | 169 | unsigned extra; |
cafe5635 KO |
170 | |
171 | /* copy of the last key in the set */ | |
ee811287 KO |
172 | struct bkey end; |
173 | struct bkey_float *tree; | |
cafe5635 KO |
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 | */ | |
ee811287 | 183 | uint8_t *prev; |
cafe5635 KO |
184 | |
185 | /* The actual btree node, with pointers to each sorted set */ | |
ee811287 | 186 | struct bset *data; |
cafe5635 KO |
187 | }; |
188 | ||
a85e968e KO |
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 *); | |
829a60b9 KO |
193 | bool (*insert_fixup)(struct btree_keys *, struct bkey *, |
194 | struct btree_iter *, struct bkey *); | |
a85e968e KO |
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 *); | |
dc9d98d6 KO |
200 | void (*key_to_text)(char *, size_t, const struct bkey *); |
201 | void (*key_dump)(struct btree_keys *, const struct bkey *); | |
a85e968e KO |
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 | ||
ee811287 KO |
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 | ||
59158fde KO |
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 | ||
a85e968e KO |
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 *); | |
ee811287 | 287 | |
a85e968e KO |
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 *); | |
0f49cf3d | 291 | bool bch_bkey_try_merge(struct btree_keys *, struct bkey *, struct bkey *); |
a85e968e | 292 | void bch_bset_insert(struct btree_keys *, struct bkey *, struct bkey *); |
829a60b9 KO |
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 | }; | |
a85e968e | 303 | |
ee811287 KO |
304 | /* Btree key iteration */ |
305 | ||
306 | struct btree_iter { | |
307 | size_t size, used; | |
308 | #ifdef CONFIG_BCACHE_DEBUG | |
c052dd9a | 309 | struct btree_keys *b; |
ee811287 KO |
310 | #endif |
311 | struct btree_iter_set { | |
312 | struct bkey *k, *end; | |
313 | } data[MAX_BSETS]; | |
314 | }; | |
315 | ||
a85e968e | 316 | typedef bool (*ptr_filter_fn)(struct btree_keys *, const struct bkey *); |
ee811287 KO |
317 | |
318 | struct bkey *bch_btree_iter_next(struct btree_iter *); | |
319 | struct bkey *bch_btree_iter_next_filter(struct btree_iter *, | |
a85e968e | 320 | struct btree_keys *, ptr_filter_fn); |
ee811287 KO |
321 | |
322 | void bch_btree_iter_push(struct btree_iter *, struct bkey *, struct bkey *); | |
c052dd9a | 323 | struct bkey *bch_btree_iter_init(struct btree_keys *, struct btree_iter *, |
ee811287 KO |
324 | struct bkey *); |
325 | ||
c052dd9a KO |
326 | struct bkey *__bch_bset_search(struct btree_keys *, struct bset_tree *, |
327 | const struct bkey *); | |
ee811287 KO |
328 | |
329 | /* | |
330 | * Returns the first key that is strictly greater than search | |
331 | */ | |
c052dd9a KO |
332 | static inline struct bkey *bch_bset_search(struct btree_keys *b, |
333 | struct bset_tree *t, | |
ee811287 KO |
334 | const struct bkey *search) |
335 | { | |
336 | return search ? __bch_bset_search(b, t, search) : t->data->start; | |
337 | } | |
338 | ||
c052dd9a KO |
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 | ||
67539e85 KO |
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); | |
89ebb4a2 KO |
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 *, | |
67539e85 | 362 | struct bset_sort_state *); |
a85e968e | 363 | void bch_btree_sort_and_fix_extents(struct btree_keys *, struct btree_iter *, |
67539e85 | 364 | struct bset_sort_state *); |
89ebb4a2 | 365 | void bch_btree_sort_partial(struct btree_keys *, unsigned, |
67539e85 KO |
366 | struct bset_sort_state *); |
367 | ||
89ebb4a2 | 368 | static inline void bch_btree_sort(struct btree_keys *b, |
67539e85 KO |
369 | struct bset_sort_state *state) |
370 | { | |
371 | bch_btree_sort_partial(b, 0, state); | |
372 | } | |
373 | ||
f67342dd KO |
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 | ||
ee811287 KO |
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 | ||
a85e968e KO |
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 | ||
dc9d98d6 KO |
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 | ||
3bdad1e4 NS |
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) && | |
8e094808 | 457 | KEY_CSUM(l) == KEY_CSUM(r)); |
3bdad1e4 NS |
458 | } |
459 | ||
cafe5635 KO |
460 | /* Keylists */ |
461 | ||
462 | struct keylist { | |
cafe5635 | 463 | union { |
c2f95ae2 KO |
464 | struct bkey *keys; |
465 | uint64_t *keys_p; | |
466 | }; | |
467 | union { | |
468 | struct bkey *top; | |
469 | uint64_t *top_p; | |
cafe5635 KO |
470 | }; |
471 | ||
472 | /* Enough room for btree_split's keys without realloc */ | |
473 | #define KEYLIST_INLINE 16 | |
c2f95ae2 | 474 | uint64_t inline_keys[KEYLIST_INLINE]; |
cafe5635 KO |
475 | }; |
476 | ||
477 | static inline void bch_keylist_init(struct keylist *l) | |
478 | { | |
c2f95ae2 | 479 | l->top_p = l->keys_p = l->inline_keys; |
cafe5635 KO |
480 | } |
481 | ||
c13f3af9 KO |
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 | ||
cafe5635 KO |
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 | { | |
c2f95ae2 KO |
501 | return l->top == l->keys; |
502 | } | |
503 | ||
504 | static inline void bch_keylist_reset(struct keylist *l) | |
505 | { | |
506 | l->top = l->keys; | |
cafe5635 KO |
507 | } |
508 | ||
509 | static inline void bch_keylist_free(struct keylist *l) | |
510 | { | |
c2f95ae2 KO |
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); | |
cafe5635 KO |
523 | } |
524 | ||
cafe5635 | 525 | struct bkey *bch_keylist_pop(struct keylist *); |
26c949f8 | 526 | void bch_keylist_pop_front(struct keylist *); |
085d2a3d | 527 | int __bch_keylist_realloc(struct keylist *, unsigned); |
cafe5635 | 528 | |
dc9d98d6 KO |
529 | /* Debug stuff */ |
530 | ||
531 | #ifdef CONFIG_BCACHE_DEBUG | |
532 | ||
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 *); | |
537 | ||
538 | #else | |
539 | ||
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); | |
544 | ||
545 | #endif | |
546 | ||
547 | static inline bool btree_keys_expensive_checks(struct btree_keys *b) | |
548 | { | |
549 | #ifdef CONFIG_BCACHE_DEBUG | |
550 | return *b->expensive_debug_checks; | |
551 | #else | |
552 | return false; | |
553 | #endif | |
554 | } | |
555 | ||
556 | static inline int bch_count_data(struct btree_keys *b) | |
557 | { | |
558 | return btree_keys_expensive_checks(b) ? __bch_count_data(b) : -1; | |
559 | } | |
560 | ||
561 | #define bch_check_keys(b, ...) \ | |
562 | do { \ | |
563 | if (btree_keys_expensive_checks(b)) \ | |
564 | __bch_check_keys(b, __VA_ARGS__); \ | |
565 | } while (0) | |
cafe5635 | 566 | |
cafe5635 | 567 | #endif |