1 | /* SPDX-License-Identifier: GPL-2.0 */ |
2 | #ifndef _BCACHE_H |
3 | #define _BCACHE_H |
4 | |
5 | /* |
6 | * SOME HIGH LEVEL CODE DOCUMENTATION: |
7 | * |
8 | * Bcache mostly works with cache sets, cache devices, and backing devices. |
9 | * |
10 | * Support for multiple cache devices hasn't quite been finished off yet, but |
11 | * it's about 95% plumbed through. A cache set and its cache devices is sort of |
12 | * like a md raid array and its component devices. Most of the code doesn't care |
13 | * about individual cache devices, the main abstraction is the cache set. |
14 | * |
15 | * Multiple cache devices is intended to give us the ability to mirror dirty |
16 | * cached data and metadata, without mirroring clean cached data. |
17 | * |
18 | * Backing devices are different, in that they have a lifetime independent of a |
19 | * cache set. When you register a newly formatted backing device it'll come up |
20 | * in passthrough mode, and then you can attach and detach a backing device from |
21 | * a cache set at runtime - while it's mounted and in use. Detaching implicitly |
22 | * invalidates any cached data for that backing device. |
23 | * |
24 | * A cache set can have multiple (many) backing devices attached to it. |
25 | * |
26 | * There's also flash only volumes - this is the reason for the distinction |
27 | * between struct cached_dev and struct bcache_device. A flash only volume |
28 | * works much like a bcache device that has a backing device, except the |
29 | * "cached" data is always dirty. The end result is that we get thin |
30 | * provisioning with very little additional code. |
31 | * |
32 | * Flash only volumes work but they're not production ready because the moving |
33 | * garbage collector needs more work. More on that later. |
34 | * |
35 | * BUCKETS/ALLOCATION: |
36 | * |
37 | * Bcache is primarily designed for caching, which means that in normal |
38 | * operation all of our available space will be allocated. Thus, we need an |
39 | * efficient way of deleting things from the cache so we can write new things to |
40 | * it. |
41 | * |
42 | * To do this, we first divide the cache device up into buckets. A bucket is the |
43 | * unit of allocation; they're typically around 1 mb - anywhere from 128k to 2M+ |
44 | * works efficiently. |
45 | * |
46 | * Each bucket has a 16 bit priority, and an 8 bit generation associated with |
47 | * it. The gens and priorities for all the buckets are stored contiguously and |
48 | * packed on disk (in a linked list of buckets - aside from the superblock, all |
49 | * of bcache's metadata is stored in buckets). |
50 | * |
51 | * The priority is used to implement an LRU. We reset a bucket's priority when |
52 | * we allocate it or on cache it, and every so often we decrement the priority |
53 | * of each bucket. It could be used to implement something more sophisticated, |
54 | * if anyone ever gets around to it. |
55 | * |
56 | * The generation is used for invalidating buckets. Each pointer also has an 8 |
57 | * bit generation embedded in it; for a pointer to be considered valid, its gen |
58 | * must match the gen of the bucket it points into. Thus, to reuse a bucket all |
59 | * we have to do is increment its gen (and write its new gen to disk; we batch |
60 | * this up). |
61 | * |
62 | * Bcache is entirely COW - we never write twice to a bucket, even buckets that |
63 | * contain metadata (including btree nodes). |
64 | * |
65 | * THE BTREE: |
66 | * |
67 | * Bcache is in large part design around the btree. |
68 | * |
69 | * At a high level, the btree is just an index of key -> ptr tuples. |
70 | * |
71 | * Keys represent extents, and thus have a size field. Keys also have a variable |
72 | * number of pointers attached to them (potentially zero, which is handy for |
73 | * invalidating the cache). |
74 | * |
75 | * The key itself is an inode:offset pair. The inode number corresponds to a |
76 | * backing device or a flash only volume. The offset is the ending offset of the |
77 | * extent within the inode - not the starting offset; this makes lookups |
78 | * slightly more convenient. |
79 | * |
80 | * Pointers contain the cache device id, the offset on that device, and an 8 bit |
81 | * generation number. More on the gen later. |
82 | * |
83 | * Index lookups are not fully abstracted - cache lookups in particular are |
84 | * still somewhat mixed in with the btree code, but things are headed in that |
85 | * direction. |
86 | * |
87 | * Updates are fairly well abstracted, though. There are two different ways of |
88 | * updating the btree; insert and replace. |
89 | * |
90 | * BTREE_INSERT will just take a list of keys and insert them into the btree - |
91 | * overwriting (possibly only partially) any extents they overlap with. This is |
92 | * used to update the index after a write. |
93 | * |
94 | * BTREE_REPLACE is really cmpxchg(); it inserts a key into the btree iff it is |
95 | * overwriting a key that matches another given key. This is used for inserting |
96 | * data into the cache after a cache miss, and for background writeback, and for |
97 | * the moving garbage collector. |
98 | * |
99 | * There is no "delete" operation; deleting things from the index is |
100 | * accomplished by either by invalidating pointers (by incrementing a bucket's |
101 | * gen) or by inserting a key with 0 pointers - which will overwrite anything |
102 | * previously present at that location in the index. |
103 | * |
104 | * This means that there are always stale/invalid keys in the btree. They're |
105 | * filtered out by the code that iterates through a btree node, and removed when |
106 | * a btree node is rewritten. |
107 | * |
108 | * BTREE NODES: |
109 | * |
110 | * Our unit of allocation is a bucket, and we can't arbitrarily allocate and |
111 | * free smaller than a bucket - so, that's how big our btree nodes are. |
112 | * |
113 | * (If buckets are really big we'll only use part of the bucket for a btree node |
114 | * - no less than 1/4th - but a bucket still contains no more than a single |
115 | * btree node. I'd actually like to change this, but for now we rely on the |
116 | * bucket's gen for deleting btree nodes when we rewrite/split a node.) |
117 | * |
118 | * Anyways, btree nodes are big - big enough to be inefficient with a textbook |
119 | * btree implementation. |
120 | * |
121 | * The way this is solved is that btree nodes are internally log structured; we |
122 | * can append new keys to an existing btree node without rewriting it. This |
123 | * means each set of keys we write is sorted, but the node is not. |
124 | * |
125 | * We maintain this log structure in memory - keeping 1Mb of keys sorted would |
126 | * be expensive, and we have to distinguish between the keys we have written and |
127 | * the keys we haven't. So to do a lookup in a btree node, we have to search |
128 | * each sorted set. But we do merge written sets together lazily, so the cost of |
129 | * these extra searches is quite low (normally most of the keys in a btree node |
130 | * will be in one big set, and then there'll be one or two sets that are much |
131 | * smaller). |
132 | * |
133 | * This log structure makes bcache's btree more of a hybrid between a |
134 | * conventional btree and a compacting data structure, with some of the |
135 | * advantages of both. |
136 | * |
137 | * GARBAGE COLLECTION: |
138 | * |
139 | * We can't just invalidate any bucket - it might contain dirty data or |
140 | * metadata. If it once contained dirty data, other writes might overwrite it |
141 | * later, leaving no valid pointers into that bucket in the index. |
142 | * |
143 | * Thus, the primary purpose of garbage collection is to find buckets to reuse. |
144 | * It also counts how much valid data it each bucket currently contains, so that |
145 | * allocation can reuse buckets sooner when they've been mostly overwritten. |
146 | * |
147 | * It also does some things that are really internal to the btree |
148 | * implementation. If a btree node contains pointers that are stale by more than |
149 | * some threshold, it rewrites the btree node to avoid the bucket's generation |
150 | * wrapping around. It also merges adjacent btree nodes if they're empty enough. |
151 | * |
152 | * THE JOURNAL: |
153 | * |
154 | * Bcache's journal is not necessary for consistency; we always strictly |
155 | * order metadata writes so that the btree and everything else is consistent on |
156 | * disk in the event of an unclean shutdown, and in fact bcache had writeback |
157 | * caching (with recovery from unclean shutdown) before journalling was |
158 | * implemented. |
159 | * |
160 | * Rather, the journal is purely a performance optimization; we can't complete a |
161 | * write until we've updated the index on disk, otherwise the cache would be |
162 | * inconsistent in the event of an unclean shutdown. This means that without the |
163 | * journal, on random write workloads we constantly have to update all the leaf |
164 | * nodes in the btree, and those writes will be mostly empty (appending at most |
165 | * a few keys each) - highly inefficient in terms of amount of metadata writes, |
166 | * and it puts more strain on the various btree resorting/compacting code. |
167 | * |
168 | * The journal is just a log of keys we've inserted; on startup we just reinsert |
169 | * all the keys in the open journal entries. That means that when we're updating |
170 | * a node in the btree, we can wait until a 4k block of keys fills up before |
171 | * writing them out. |
172 | * |
173 | * For simplicity, we only journal updates to leaf nodes; updates to parent |
174 | * nodes are rare enough (since our leaf nodes are huge) that it wasn't worth |
175 | * the complexity to deal with journalling them (in particular, journal replay) |
176 | * - updates to non leaf nodes just happen synchronously (see btree_split()). |
177 | */ |
178 | |
179 | #define pr_fmt(fmt) "bcache: %s() " fmt, __func__ |
180 | |
181 | #include <linux/bio.h> |
182 | #include <linux/closure.h> |
183 | #include <linux/kobject.h> |
184 | #include <linux/list.h> |
185 | #include <linux/mutex.h> |
186 | #include <linux/rbtree.h> |
187 | #include <linux/rwsem.h> |
188 | #include <linux/refcount.h> |
189 | #include <linux/types.h> |
190 | #include <linux/workqueue.h> |
191 | #include <linux/kthread.h> |
192 | |
193 | #include "bcache_ondisk.h" |
194 | #include "bset.h" |
195 | #include "util.h" |
196 | |
197 | struct bucket { |
198 | atomic_t pin; |
199 | uint16_t prio; |
200 | uint8_t gen; |
201 | uint8_t last_gc; /* Most out of date gen in the btree */ |
202 | uint16_t gc_mark; /* Bitfield used by GC. See below for field */ |
203 | }; |
204 | |
205 | /* |
206 | * I'd use bitfields for these, but I don't trust the compiler not to screw me |
207 | * as multiple threads touch struct bucket without locking |
208 | */ |
209 | |
210 | BITMASK(GC_MARK, struct bucket, gc_mark, 0, 2); |
211 | #define GC_MARK_RECLAIMABLE 1 |
212 | #define GC_MARK_DIRTY 2 |
213 | #define GC_MARK_METADATA 3 |
214 | #define GC_SECTORS_USED_SIZE 13 |
215 | #define MAX_GC_SECTORS_USED (~(~0ULL << GC_SECTORS_USED_SIZE)) |
216 | BITMASK(GC_SECTORS_USED, struct bucket, gc_mark, 2, GC_SECTORS_USED_SIZE); |
217 | BITMASK(GC_MOVE, struct bucket, gc_mark, 15, 1); |
218 | |
219 | #include "journal.h" |
220 | #include "stats.h" |
221 | struct search; |
222 | struct btree; |
223 | struct keybuf; |
224 | |
225 | struct keybuf_key { |
226 | struct rb_node node; |
227 | BKEY_PADDED(key); |
228 | void *private; |
229 | }; |
230 | |
231 | struct keybuf { |
232 | struct bkey last_scanned; |
233 | spinlock_t lock; |
234 | |
235 | /* |
236 | * Beginning and end of range in rb tree - so that we can skip taking |
237 | * lock and checking the rb tree when we need to check for overlapping |
238 | * keys. |
239 | */ |
240 | struct bkey start; |
241 | struct bkey end; |
242 | |
243 | struct rb_root keys; |
244 | |
245 | #define KEYBUF_NR 500 |
246 | DECLARE_ARRAY_ALLOCATOR(struct keybuf_key, freelist, KEYBUF_NR); |
247 | }; |
248 | |
249 | struct bcache_device { |
250 | struct closure cl; |
251 | |
252 | struct kobject kobj; |
253 | |
254 | struct cache_set *c; |
255 | unsigned int id; |
256 | #define BCACHEDEVNAME_SIZE 12 |
257 | char name[BCACHEDEVNAME_SIZE]; |
258 | |
259 | struct gendisk *disk; |
260 | |
261 | unsigned long flags; |
262 | #define BCACHE_DEV_CLOSING 0 |
263 | #define BCACHE_DEV_DETACHING 1 |
264 | #define BCACHE_DEV_UNLINK_DONE 2 |
265 | #define BCACHE_DEV_WB_RUNNING 3 |
266 | #define BCACHE_DEV_RATE_DW_RUNNING 4 |
267 | int nr_stripes; |
268 | unsigned int stripe_size; |
269 | atomic_t *stripe_sectors_dirty; |
270 | unsigned long *full_dirty_stripes; |
271 | |
272 | struct bio_set bio_split; |
273 | |
274 | unsigned int data_csum:1; |
275 | |
276 | int (*cache_miss)(struct btree *b, struct search *s, |
277 | struct bio *bio, unsigned int sectors); |
278 | int (*ioctl)(struct bcache_device *d, blk_mode_t mode, |
279 | unsigned int cmd, unsigned long arg); |
280 | }; |
281 | |
282 | struct io { |
283 | /* Used to track sequential IO so it can be skipped */ |
284 | struct hlist_node hash; |
285 | struct list_head lru; |
286 | |
287 | unsigned long jiffies; |
288 | unsigned int sequential; |
289 | sector_t last; |
290 | }; |
291 | |
292 | enum stop_on_failure { |
293 | BCH_CACHED_DEV_STOP_AUTO = 0, |
294 | BCH_CACHED_DEV_STOP_ALWAYS, |
295 | BCH_CACHED_DEV_STOP_MODE_MAX, |
296 | }; |
297 | |
298 | struct cached_dev { |
299 | struct list_head list; |
300 | struct bcache_device disk; |
301 | struct block_device *bdev; |
302 | struct bdev_handle *bdev_handle; |
303 | |
304 | struct cache_sb sb; |
305 | struct cache_sb_disk *sb_disk; |
306 | struct bio sb_bio; |
307 | struct bio_vec sb_bv[1]; |
308 | struct closure sb_write; |
309 | struct semaphore sb_write_mutex; |
310 | |
311 | /* Refcount on the cache set. Always nonzero when we're caching. */ |
312 | refcount_t count; |
313 | struct work_struct detach; |
314 | |
315 | /* |
316 | * Device might not be running if it's dirty and the cache set hasn't |
317 | * showed up yet. |
318 | */ |
319 | atomic_t running; |
320 | |
321 | /* |
322 | * Writes take a shared lock from start to finish; scanning for dirty |
323 | * data to refill the rb tree requires an exclusive lock. |
324 | */ |
325 | struct rw_semaphore writeback_lock; |
326 | |
327 | /* |
328 | * Nonzero, and writeback has a refcount (d->count), iff there is dirty |
329 | * data in the cache. Protected by writeback_lock; must have an |
330 | * shared lock to set and exclusive lock to clear. |
331 | */ |
332 | atomic_t has_dirty; |
333 | |
334 | #define BCH_CACHE_READA_ALL 0 |
335 | #define BCH_CACHE_READA_META_ONLY 1 |
336 | unsigned int cache_readahead_policy; |
337 | struct bch_ratelimit writeback_rate; |
338 | struct delayed_work writeback_rate_update; |
339 | |
340 | /* Limit number of writeback bios in flight */ |
341 | struct semaphore in_flight; |
342 | struct task_struct *writeback_thread; |
343 | struct workqueue_struct *writeback_write_wq; |
344 | |
345 | struct keybuf writeback_keys; |
346 | |
347 | struct task_struct *status_update_thread; |
348 | /* |
349 | * Order the write-half of writeback operations strongly in dispatch |
350 | * order. (Maintain LBA order; don't allow reads completing out of |
351 | * order to re-order the writes...) |
352 | */ |
353 | struct closure_waitlist writeback_ordering_wait; |
354 | atomic_t writeback_sequence_next; |
355 | |
356 | /* For tracking sequential IO */ |
357 | #define RECENT_IO_BITS 7 |
358 | #define RECENT_IO (1 << RECENT_IO_BITS) |
359 | struct io io[RECENT_IO]; |
360 | struct hlist_head io_hash[RECENT_IO + 1]; |
361 | struct list_head io_lru; |
362 | spinlock_t io_lock; |
363 | |
364 | struct cache_accounting accounting; |
365 | |
366 | /* The rest of this all shows up in sysfs */ |
367 | unsigned int sequential_cutoff; |
368 | |
369 | unsigned int io_disable:1; |
370 | unsigned int verify:1; |
371 | unsigned int bypass_torture_test:1; |
372 | |
373 | unsigned int partial_stripes_expensive:1; |
374 | unsigned int writeback_metadata:1; |
375 | unsigned int writeback_running:1; |
376 | unsigned int writeback_consider_fragment:1; |
377 | unsigned char writeback_percent; |
378 | unsigned int writeback_delay; |
379 | |
380 | uint64_t writeback_rate_target; |
381 | int64_t writeback_rate_proportional; |
382 | int64_t writeback_rate_integral; |
383 | int64_t writeback_rate_integral_scaled; |
384 | int32_t writeback_rate_change; |
385 | |
386 | unsigned int writeback_rate_update_seconds; |
387 | unsigned int writeback_rate_i_term_inverse; |
388 | unsigned int writeback_rate_p_term_inverse; |
389 | unsigned int writeback_rate_fp_term_low; |
390 | unsigned int writeback_rate_fp_term_mid; |
391 | unsigned int writeback_rate_fp_term_high; |
392 | unsigned int writeback_rate_minimum; |
393 | |
394 | enum stop_on_failure stop_when_cache_set_failed; |
395 | #define DEFAULT_CACHED_DEV_ERROR_LIMIT 64 |
396 | atomic_t io_errors; |
397 | unsigned int error_limit; |
398 | unsigned int offline_seconds; |
399 | |
400 | /* |
401 | * Retry to update writeback_rate if contention happens for |
402 | * down_read(dc->writeback_lock) in update_writeback_rate() |
403 | */ |
404 | #define BCH_WBRATE_UPDATE_MAX_SKIPS 15 |
405 | unsigned int rate_update_retry; |
406 | }; |
407 | |
408 | enum alloc_reserve { |
409 | RESERVE_BTREE, |
410 | RESERVE_PRIO, |
411 | RESERVE_MOVINGGC, |
412 | RESERVE_NONE, |
413 | RESERVE_NR, |
414 | }; |
415 | |
416 | struct cache { |
417 | struct cache_set *set; |
418 | struct cache_sb sb; |
419 | struct cache_sb_disk *sb_disk; |
420 | struct bio sb_bio; |
421 | struct bio_vec sb_bv[1]; |
422 | |
423 | struct kobject kobj; |
424 | struct block_device *bdev; |
425 | struct bdev_handle *bdev_handle; |
426 | |
427 | struct task_struct *alloc_thread; |
428 | |
429 | struct closure prio; |
430 | struct prio_set *disk_buckets; |
431 | |
432 | /* |
433 | * When allocating new buckets, prio_write() gets first dibs - since we |
434 | * may not be allocate at all without writing priorities and gens. |
435 | * prio_last_buckets[] contains the last buckets we wrote priorities to |
436 | * (so gc can mark them as metadata), prio_buckets[] contains the |
437 | * buckets allocated for the next prio write. |
438 | */ |
439 | uint64_t *prio_buckets; |
440 | uint64_t *prio_last_buckets; |
441 | |
442 | /* |
443 | * free: Buckets that are ready to be used |
444 | * |
445 | * free_inc: Incoming buckets - these are buckets that currently have |
446 | * cached data in them, and we can't reuse them until after we write |
447 | * their new gen to disk. After prio_write() finishes writing the new |
448 | * gens/prios, they'll be moved to the free list (and possibly discarded |
449 | * in the process) |
450 | */ |
451 | DECLARE_FIFO(long, free)[RESERVE_NR]; |
452 | DECLARE_FIFO(long, free_inc); |
453 | |
454 | size_t fifo_last_bucket; |
455 | |
456 | /* Allocation stuff: */ |
457 | struct bucket *buckets; |
458 | |
459 | DECLARE_HEAP(struct bucket *, heap); |
460 | |
461 | /* |
462 | * If nonzero, we know we aren't going to find any buckets to invalidate |
463 | * until a gc finishes - otherwise we could pointlessly burn a ton of |
464 | * cpu |
465 | */ |
466 | unsigned int invalidate_needs_gc; |
467 | |
468 | bool discard; /* Get rid of? */ |
469 | |
470 | struct journal_device journal; |
471 | |
472 | /* The rest of this all shows up in sysfs */ |
473 | #define IO_ERROR_SHIFT 20 |
474 | atomic_t io_errors; |
475 | atomic_t io_count; |
476 | |
477 | atomic_long_t meta_sectors_written; |
478 | atomic_long_t btree_sectors_written; |
479 | atomic_long_t sectors_written; |
480 | }; |
481 | |
482 | struct gc_stat { |
483 | size_t nodes; |
484 | size_t nodes_pre; |
485 | size_t key_bytes; |
486 | |
487 | size_t nkeys; |
488 | uint64_t data; /* sectors */ |
489 | unsigned int in_use; /* percent */ |
490 | }; |
491 | |
492 | /* |
493 | * Flag bits, for how the cache set is shutting down, and what phase it's at: |
494 | * |
495 | * CACHE_SET_UNREGISTERING means we're not just shutting down, we're detaching |
496 | * all the backing devices first (their cached data gets invalidated, and they |
497 | * won't automatically reattach). |
498 | * |
499 | * CACHE_SET_STOPPING always gets set first when we're closing down a cache set; |
500 | * we'll continue to run normally for awhile with CACHE_SET_STOPPING set (i.e. |
501 | * flushing dirty data). |
502 | * |
503 | * CACHE_SET_RUNNING means all cache devices have been registered and journal |
504 | * replay is complete. |
505 | * |
506 | * CACHE_SET_IO_DISABLE is set when bcache is stopping the whold cache set, all |
507 | * external and internal I/O should be denied when this flag is set. |
508 | * |
509 | */ |
510 | #define CACHE_SET_UNREGISTERING 0 |
511 | #define CACHE_SET_STOPPING 1 |
512 | #define CACHE_SET_RUNNING 2 |
513 | #define CACHE_SET_IO_DISABLE 3 |
514 | |
515 | struct cache_set { |
516 | struct closure cl; |
517 | |
518 | struct list_head list; |
519 | struct kobject kobj; |
520 | struct kobject internal; |
521 | struct dentry *debug; |
522 | struct cache_accounting accounting; |
523 | |
524 | unsigned long flags; |
525 | atomic_t idle_counter; |
526 | atomic_t at_max_writeback_rate; |
527 | |
528 | struct cache *cache; |
529 | |
530 | struct bcache_device **devices; |
531 | unsigned int devices_max_used; |
532 | atomic_t attached_dev_nr; |
533 | struct list_head cached_devs; |
534 | uint64_t cached_dev_sectors; |
535 | atomic_long_t flash_dev_dirty_sectors; |
536 | struct closure caching; |
537 | |
538 | struct closure sb_write; |
539 | struct semaphore sb_write_mutex; |
540 | |
541 | mempool_t search; |
542 | mempool_t bio_meta; |
543 | struct bio_set bio_split; |
544 | |
545 | /* For the btree cache */ |
546 | struct shrinker *shrink; |
547 | |
548 | /* For the btree cache and anything allocation related */ |
549 | struct mutex bucket_lock; |
550 | |
551 | /* log2(bucket_size), in sectors */ |
552 | unsigned short bucket_bits; |
553 | |
554 | /* log2(block_size), in sectors */ |
555 | unsigned short block_bits; |
556 | |
557 | /* |
558 | * Default number of pages for a new btree node - may be less than a |
559 | * full bucket |
560 | */ |
561 | unsigned int btree_pages; |
562 | |
563 | /* |
564 | * Lists of struct btrees; lru is the list for structs that have memory |
565 | * allocated for actual btree node, freed is for structs that do not. |
566 | * |
567 | * We never free a struct btree, except on shutdown - we just put it on |
568 | * the btree_cache_freed list and reuse it later. This simplifies the |
569 | * code, and it doesn't cost us much memory as the memory usage is |
570 | * dominated by buffers that hold the actual btree node data and those |
571 | * can be freed - and the number of struct btrees allocated is |
572 | * effectively bounded. |
573 | * |
574 | * btree_cache_freeable effectively is a small cache - we use it because |
575 | * high order page allocations can be rather expensive, and it's quite |
576 | * common to delete and allocate btree nodes in quick succession. It |
577 | * should never grow past ~2-3 nodes in practice. |
578 | */ |
579 | struct list_head btree_cache; |
580 | struct list_head btree_cache_freeable; |
581 | struct list_head btree_cache_freed; |
582 | |
583 | /* Number of elements in btree_cache + btree_cache_freeable lists */ |
584 | unsigned int btree_cache_used; |
585 | |
586 | /* |
587 | * If we need to allocate memory for a new btree node and that |
588 | * allocation fails, we can cannibalize another node in the btree cache |
589 | * to satisfy the allocation - lock to guarantee only one thread does |
590 | * this at a time: |
591 | */ |
592 | wait_queue_head_t btree_cache_wait; |
593 | struct task_struct *btree_cache_alloc_lock; |
594 | spinlock_t btree_cannibalize_lock; |
595 | |
596 | /* |
597 | * When we free a btree node, we increment the gen of the bucket the |
598 | * node is in - but we can't rewrite the prios and gens until we |
599 | * finished whatever it is we were doing, otherwise after a crash the |
600 | * btree node would be freed but for say a split, we might not have the |
601 | * pointers to the new nodes inserted into the btree yet. |
602 | * |
603 | * This is a refcount that blocks prio_write() until the new keys are |
604 | * written. |
605 | */ |
606 | atomic_t prio_blocked; |
607 | wait_queue_head_t bucket_wait; |
608 | |
609 | /* |
610 | * For any bio we don't skip we subtract the number of sectors from |
611 | * rescale; when it hits 0 we rescale all the bucket priorities. |
612 | */ |
613 | atomic_t rescale; |
614 | /* |
615 | * used for GC, identify if any front side I/Os is inflight |
616 | */ |
617 | atomic_t search_inflight; |
618 | /* |
619 | * When we invalidate buckets, we use both the priority and the amount |
620 | * of good data to determine which buckets to reuse first - to weight |
621 | * those together consistently we keep track of the smallest nonzero |
622 | * priority of any bucket. |
623 | */ |
624 | uint16_t min_prio; |
625 | |
626 | /* |
627 | * max(gen - last_gc) for all buckets. When it gets too big we have to |
628 | * gc to keep gens from wrapping around. |
629 | */ |
630 | uint8_t need_gc; |
631 | struct gc_stat gc_stats; |
632 | size_t nbuckets; |
633 | size_t avail_nbuckets; |
634 | |
635 | struct task_struct *gc_thread; |
636 | /* Where in the btree gc currently is */ |
637 | struct bkey gc_done; |
638 | |
639 | /* |
640 | * For automatical garbage collection after writeback completed, this |
641 | * varialbe is used as bit fields, |
642 | * - 0000 0001b (BCH_ENABLE_AUTO_GC): enable gc after writeback |
643 | * - 0000 0010b (BCH_DO_AUTO_GC): do gc after writeback |
644 | * This is an optimization for following write request after writeback |
645 | * finished, but read hit rate dropped due to clean data on cache is |
646 | * discarded. Unless user explicitly sets it via sysfs, it won't be |
647 | * enabled. |
648 | */ |
649 | #define BCH_ENABLE_AUTO_GC 1 |
650 | #define BCH_DO_AUTO_GC 2 |
651 | uint8_t gc_after_writeback; |
652 | |
653 | /* |
654 | * The allocation code needs gc_mark in struct bucket to be correct, but |
655 | * it's not while a gc is in progress. Protected by bucket_lock. |
656 | */ |
657 | int gc_mark_valid; |
658 | |
659 | /* Counts how many sectors bio_insert has added to the cache */ |
660 | atomic_t sectors_to_gc; |
661 | wait_queue_head_t gc_wait; |
662 | |
663 | struct keybuf moving_gc_keys; |
664 | /* Number of moving GC bios in flight */ |
665 | struct semaphore moving_in_flight; |
666 | |
667 | struct workqueue_struct *moving_gc_wq; |
668 | |
669 | struct btree *root; |
670 | |
671 | #ifdef CONFIG_BCACHE_DEBUG |
672 | struct btree *verify_data; |
673 | struct bset *verify_ondisk; |
674 | struct mutex verify_lock; |
675 | #endif |
676 | |
677 | uint8_t set_uuid[16]; |
678 | unsigned int nr_uuids; |
679 | struct uuid_entry *uuids; |
680 | BKEY_PADDED(uuid_bucket); |
681 | struct closure uuid_write; |
682 | struct semaphore uuid_write_mutex; |
683 | |
684 | /* |
685 | * A btree node on disk could have too many bsets for an iterator to fit |
686 | * on the stack - have to dynamically allocate them. |
687 | * bch_cache_set_alloc() will make sure the pool can allocate iterators |
688 | * equipped with enough room that can host |
689 | * (sb.bucket_size / sb.block_size) |
690 | * btree_iter_sets, which is more than static MAX_BSETS. |
691 | */ |
692 | mempool_t fill_iter; |
693 | |
694 | struct bset_sort_state sort; |
695 | |
696 | /* List of buckets we're currently writing data to */ |
697 | struct list_head data_buckets; |
698 | spinlock_t data_bucket_lock; |
699 | |
700 | struct journal journal; |
701 | |
702 | #define CONGESTED_MAX 1024 |
703 | unsigned int congested_last_us; |
704 | atomic_t congested; |
705 | |
706 | /* The rest of this all shows up in sysfs */ |
707 | unsigned int congested_read_threshold_us; |
708 | unsigned int congested_write_threshold_us; |
709 | |
710 | struct time_stats btree_gc_time; |
711 | struct time_stats btree_split_time; |
712 | struct time_stats btree_read_time; |
713 | |
714 | atomic_long_t cache_read_races; |
715 | atomic_long_t writeback_keys_done; |
716 | atomic_long_t writeback_keys_failed; |
717 | |
718 | atomic_long_t reclaim; |
719 | atomic_long_t reclaimed_journal_buckets; |
720 | atomic_long_t flush_write; |
721 | |
722 | enum { |
723 | ON_ERROR_UNREGISTER, |
724 | ON_ERROR_PANIC, |
725 | } on_error; |
726 | #define DEFAULT_IO_ERROR_LIMIT 8 |
727 | unsigned int error_limit; |
728 | unsigned int error_decay; |
729 | |
730 | unsigned short journal_delay_ms; |
731 | bool expensive_debug_checks; |
732 | unsigned int verify:1; |
733 | unsigned int key_merging_disabled:1; |
734 | unsigned int gc_always_rewrite:1; |
735 | unsigned int shrinker_disabled:1; |
736 | unsigned int copy_gc_enabled:1; |
737 | unsigned int idle_max_writeback_rate_enabled:1; |
738 | |
739 | #define BUCKET_HASH_BITS 12 |
740 | struct hlist_head bucket_hash[1 << BUCKET_HASH_BITS]; |
741 | }; |
742 | |
743 | struct bbio { |
744 | unsigned int submit_time_us; |
745 | union { |
746 | struct bkey key; |
747 | uint64_t _pad[3]; |
748 | /* |
749 | * We only need pad = 3 here because we only ever carry around a |
750 | * single pointer - i.e. the pointer we're doing io to/from. |
751 | */ |
752 | }; |
753 | struct bio bio; |
754 | }; |
755 | |
756 | #define BTREE_PRIO USHRT_MAX |
757 | #define INITIAL_PRIO 32768U |
758 | |
759 | #define btree_bytes(c) ((c)->btree_pages * PAGE_SIZE) |
760 | #define btree_blocks(b) \ |
761 | ((unsigned int) (KEY_SIZE(&b->key) >> (b)->c->block_bits)) |
762 | |
763 | #define btree_default_blocks(c) \ |
764 | ((unsigned int) ((PAGE_SECTORS * (c)->btree_pages) >> (c)->block_bits)) |
765 | |
766 | #define bucket_bytes(ca) ((ca)->sb.bucket_size << 9) |
767 | #define block_bytes(ca) ((ca)->sb.block_size << 9) |
768 | |
769 | static inline unsigned int meta_bucket_pages(struct cache_sb *sb) |
770 | { |
771 | unsigned int n, max_pages; |
772 | |
773 | max_pages = min_t(unsigned int, |
774 | __rounddown_pow_of_two(USHRT_MAX) / PAGE_SECTORS, |
775 | MAX_ORDER_NR_PAGES); |
776 | |
777 | n = sb->bucket_size / PAGE_SECTORS; |
778 | if (n > max_pages) |
779 | n = max_pages; |
780 | |
781 | return n; |
782 | } |
783 | |
784 | static inline unsigned int meta_bucket_bytes(struct cache_sb *sb) |
785 | { |
786 | return meta_bucket_pages(sb) << PAGE_SHIFT; |
787 | } |
788 | |
789 | #define prios_per_bucket(ca) \ |
790 | ((meta_bucket_bytes(&(ca)->sb) - sizeof(struct prio_set)) / \ |
791 | sizeof(struct bucket_disk)) |
792 | |
793 | #define prio_buckets(ca) \ |
794 | DIV_ROUND_UP((size_t) (ca)->sb.nbuckets, prios_per_bucket(ca)) |
795 | |
796 | static inline size_t sector_to_bucket(struct cache_set *c, sector_t s) |
797 | { |
798 | return s >> c->bucket_bits; |
799 | } |
800 | |
801 | static inline sector_t bucket_to_sector(struct cache_set *c, size_t b) |
802 | { |
803 | return ((sector_t) b) << c->bucket_bits; |
804 | } |
805 | |
806 | static inline sector_t bucket_remainder(struct cache_set *c, sector_t s) |
807 | { |
808 | return s & (c->cache->sb.bucket_size - 1); |
809 | } |
810 | |
811 | static inline size_t PTR_BUCKET_NR(struct cache_set *c, |
812 | const struct bkey *k, |
813 | unsigned int ptr) |
814 | { |
815 | return sector_to_bucket(c, s: PTR_OFFSET(k, i: ptr)); |
816 | } |
817 | |
818 | static inline struct bucket *PTR_BUCKET(struct cache_set *c, |
819 | const struct bkey *k, |
820 | unsigned int ptr) |
821 | { |
822 | return c->cache->buckets + PTR_BUCKET_NR(c, k, ptr); |
823 | } |
824 | |
825 | static inline uint8_t gen_after(uint8_t a, uint8_t b) |
826 | { |
827 | uint8_t r = a - b; |
828 | |
829 | return r > 128U ? 0 : r; |
830 | } |
831 | |
832 | static inline uint8_t ptr_stale(struct cache_set *c, const struct bkey *k, |
833 | unsigned int i) |
834 | { |
835 | return gen_after(a: PTR_BUCKET(c, k, ptr: i)->gen, b: PTR_GEN(k, i)); |
836 | } |
837 | |
838 | static inline bool ptr_available(struct cache_set *c, const struct bkey *k, |
839 | unsigned int i) |
840 | { |
841 | return (PTR_DEV(k, i) < MAX_CACHES_PER_SET) && c->cache; |
842 | } |
843 | |
844 | /* Btree key macros */ |
845 | |
846 | /* |
847 | * This is used for various on disk data structures - cache_sb, prio_set, bset, |
848 | * jset: The checksum is _always_ the first 8 bytes of these structs |
849 | */ |
850 | #define csum_set(i) \ |
851 | bch_crc64(((void *) (i)) + sizeof(uint64_t), \ |
852 | ((void *) bset_bkey_last(i)) - \ |
853 | (((void *) (i)) + sizeof(uint64_t))) |
854 | |
855 | /* Error handling macros */ |
856 | |
857 | #define btree_bug(b, ...) \ |
858 | do { \ |
859 | if (bch_cache_set_error((b)->c, __VA_ARGS__)) \ |
860 | dump_stack(); \ |
861 | } while (0) |
862 | |
863 | #define cache_bug(c, ...) \ |
864 | do { \ |
865 | if (bch_cache_set_error(c, __VA_ARGS__)) \ |
866 | dump_stack(); \ |
867 | } while (0) |
868 | |
869 | #define btree_bug_on(cond, b, ...) \ |
870 | do { \ |
871 | if (cond) \ |
872 | btree_bug(b, __VA_ARGS__); \ |
873 | } while (0) |
874 | |
875 | #define cache_bug_on(cond, c, ...) \ |
876 | do { \ |
877 | if (cond) \ |
878 | cache_bug(c, __VA_ARGS__); \ |
879 | } while (0) |
880 | |
881 | #define cache_set_err_on(cond, c, ...) \ |
882 | do { \ |
883 | if (cond) \ |
884 | bch_cache_set_error(c, __VA_ARGS__); \ |
885 | } while (0) |
886 | |
887 | /* Looping macros */ |
888 | |
889 | #define for_each_bucket(b, ca) \ |
890 | for (b = (ca)->buckets + (ca)->sb.first_bucket; \ |
891 | b < (ca)->buckets + (ca)->sb.nbuckets; b++) |
892 | |
893 | static inline void cached_dev_put(struct cached_dev *dc) |
894 | { |
895 | if (refcount_dec_and_test(r: &dc->count)) |
896 | schedule_work(work: &dc->detach); |
897 | } |
898 | |
899 | static inline bool cached_dev_get(struct cached_dev *dc) |
900 | { |
901 | if (!refcount_inc_not_zero(r: &dc->count)) |
902 | return false; |
903 | |
904 | /* Paired with the mb in cached_dev_attach */ |
905 | smp_mb__after_atomic(); |
906 | return true; |
907 | } |
908 | |
909 | /* |
910 | * bucket_gc_gen() returns the difference between the bucket's current gen and |
911 | * the oldest gen of any pointer into that bucket in the btree (last_gc). |
912 | */ |
913 | |
914 | static inline uint8_t bucket_gc_gen(struct bucket *b) |
915 | { |
916 | return b->gen - b->last_gc; |
917 | } |
918 | |
919 | #define BUCKET_GC_GEN_MAX 96U |
920 | |
921 | #define kobj_attribute_write(n, fn) \ |
922 | static struct kobj_attribute ksysfs_##n = __ATTR(n, 0200, NULL, fn) |
923 | |
924 | #define kobj_attribute_rw(n, show, store) \ |
925 | static struct kobj_attribute ksysfs_##n = \ |
926 | __ATTR(n, 0600, show, store) |
927 | |
928 | static inline void wake_up_allocators(struct cache_set *c) |
929 | { |
930 | struct cache *ca = c->cache; |
931 | |
932 | wake_up_process(tsk: ca->alloc_thread); |
933 | } |
934 | |
935 | static inline void closure_bio_submit(struct cache_set *c, |
936 | struct bio *bio, |
937 | struct closure *cl) |
938 | { |
939 | closure_get(cl); |
940 | if (unlikely(test_bit(CACHE_SET_IO_DISABLE, &c->flags))) { |
941 | bio->bi_status = BLK_STS_IOERR; |
942 | bio_endio(bio); |
943 | return; |
944 | } |
945 | submit_bio_noacct(bio); |
946 | } |
947 | |
948 | /* |
949 | * Prevent the kthread exits directly, and make sure when kthread_stop() |
950 | * is called to stop a kthread, it is still alive. If a kthread might be |
951 | * stopped by CACHE_SET_IO_DISABLE bit set, wait_for_kthread_stop() is |
952 | * necessary before the kthread returns. |
953 | */ |
954 | static inline void wait_for_kthread_stop(void) |
955 | { |
956 | while (!kthread_should_stop()) { |
957 | set_current_state(TASK_INTERRUPTIBLE); |
958 | schedule(); |
959 | } |
960 | } |
961 | |
962 | /* Forward declarations */ |
963 | |
964 | void bch_count_backing_io_errors(struct cached_dev *dc, struct bio *bio); |
965 | void bch_count_io_errors(struct cache *ca, blk_status_t error, |
966 | int is_read, const char *m); |
967 | void bch_bbio_count_io_errors(struct cache_set *c, struct bio *bio, |
968 | blk_status_t error, const char *m); |
969 | void bch_bbio_endio(struct cache_set *c, struct bio *bio, |
970 | blk_status_t error, const char *m); |
971 | void bch_bbio_free(struct bio *bio, struct cache_set *c); |
972 | struct bio *bch_bbio_alloc(struct cache_set *c); |
973 | |
974 | void __bch_submit_bbio(struct bio *bio, struct cache_set *c); |
975 | void bch_submit_bbio(struct bio *bio, struct cache_set *c, |
976 | struct bkey *k, unsigned int ptr); |
977 | |
978 | uint8_t bch_inc_gen(struct cache *ca, struct bucket *b); |
979 | void bch_rescale_priorities(struct cache_set *c, int sectors); |
980 | |
981 | bool bch_can_invalidate_bucket(struct cache *ca, struct bucket *b); |
982 | void __bch_invalidate_one_bucket(struct cache *ca, struct bucket *b); |
983 | |
984 | void __bch_bucket_free(struct cache *ca, struct bucket *b); |
985 | void bch_bucket_free(struct cache_set *c, struct bkey *k); |
986 | |
987 | long bch_bucket_alloc(struct cache *ca, unsigned int reserve, bool wait); |
988 | int __bch_bucket_alloc_set(struct cache_set *c, unsigned int reserve, |
989 | struct bkey *k, bool wait); |
990 | int bch_bucket_alloc_set(struct cache_set *c, unsigned int reserve, |
991 | struct bkey *k, bool wait); |
992 | bool bch_alloc_sectors(struct cache_set *c, struct bkey *k, |
993 | unsigned int sectors, unsigned int write_point, |
994 | unsigned int write_prio, bool wait); |
995 | bool bch_cached_dev_error(struct cached_dev *dc); |
996 | |
997 | __printf(2, 3) |
998 | bool bch_cache_set_error(struct cache_set *c, const char *fmt, ...); |
999 | |
1000 | int bch_prio_write(struct cache *ca, bool wait); |
1001 | void bch_write_bdev_super(struct cached_dev *dc, struct closure *parent); |
1002 | |
1003 | extern struct workqueue_struct *bcache_wq; |
1004 | extern struct workqueue_struct *bch_journal_wq; |
1005 | extern struct workqueue_struct *bch_flush_wq; |
1006 | extern struct mutex bch_register_lock; |
1007 | extern struct list_head bch_cache_sets; |
1008 | |
1009 | extern const struct kobj_type bch_cached_dev_ktype; |
1010 | extern const struct kobj_type bch_flash_dev_ktype; |
1011 | extern const struct kobj_type bch_cache_set_ktype; |
1012 | extern const struct kobj_type bch_cache_set_internal_ktype; |
1013 | extern const struct kobj_type bch_cache_ktype; |
1014 | |
1015 | void bch_cached_dev_release(struct kobject *kobj); |
1016 | void bch_flash_dev_release(struct kobject *kobj); |
1017 | void bch_cache_set_release(struct kobject *kobj); |
1018 | void bch_cache_release(struct kobject *kobj); |
1019 | |
1020 | int bch_uuid_write(struct cache_set *c); |
1021 | void bcache_write_super(struct cache_set *c); |
1022 | |
1023 | int bch_flash_dev_create(struct cache_set *c, uint64_t size); |
1024 | |
1025 | int bch_cached_dev_attach(struct cached_dev *dc, struct cache_set *c, |
1026 | uint8_t *set_uuid); |
1027 | void bch_cached_dev_detach(struct cached_dev *dc); |
1028 | int bch_cached_dev_run(struct cached_dev *dc); |
1029 | void bcache_device_stop(struct bcache_device *d); |
1030 | |
1031 | void bch_cache_set_unregister(struct cache_set *c); |
1032 | void bch_cache_set_stop(struct cache_set *c); |
1033 | |
1034 | struct cache_set *bch_cache_set_alloc(struct cache_sb *sb); |
1035 | void bch_btree_cache_free(struct cache_set *c); |
1036 | int bch_btree_cache_alloc(struct cache_set *c); |
1037 | void bch_moving_init_cache_set(struct cache_set *c); |
1038 | int bch_open_buckets_alloc(struct cache_set *c); |
1039 | void bch_open_buckets_free(struct cache_set *c); |
1040 | |
1041 | int bch_cache_allocator_start(struct cache *ca); |
1042 | |
1043 | void bch_debug_exit(void); |
1044 | void bch_debug_init(void); |
1045 | void bch_request_exit(void); |
1046 | int bch_request_init(void); |
1047 | void bch_btree_exit(void); |
1048 | int bch_btree_init(void); |
1049 | |
1050 | #endif /* _BCACHE_H */ |
1051 | |