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/kobject.h>
183 #include <linux/list.h>
184 #include <linux/mutex.h>
185 #include <linux/rbtree.h>
186 #include <linux/rwsem.h>
187 #include <linux/refcount.h>
188 #include <linux/types.h>
189 #include <linux/workqueue.h>
190 #include <linux/kthread.h>
191 
192 #include "bcache_ondisk.h"
193 #include "bset.h"
194 #include "util.h"
195 #include "closure.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 #define BCH_MIN_STRIPE_SZ		((4 << 20) >> SECTOR_SHIFT)
269 	unsigned int		stripe_size;
270 	atomic_t		*stripe_sectors_dirty;
271 	unsigned long		*full_dirty_stripes;
272 
273 	struct bio_set		bio_split;
274 
275 	unsigned int		data_csum:1;
276 
277 	int (*cache_miss)(struct btree *b, struct search *s,
278 			  struct bio *bio, unsigned int sectors);
279 	int (*ioctl)(struct bcache_device *d, blk_mode_t mode,
280 		     unsigned int cmd, unsigned long arg);
281 };
282 
283 struct io {
284 	/* Used to track sequential IO so it can be skipped */
285 	struct hlist_node	hash;
286 	struct list_head	lru;
287 
288 	unsigned long		jiffies;
289 	unsigned int		sequential;
290 	sector_t		last;
291 };
292 
293 enum stop_on_failure {
294 	BCH_CACHED_DEV_STOP_AUTO = 0,
295 	BCH_CACHED_DEV_STOP_ALWAYS,
296 	BCH_CACHED_DEV_STOP_MODE_MAX,
297 };
298 
299 struct cached_dev {
300 	struct list_head	list;
301 	struct bcache_device	disk;
302 	struct block_device	*bdev;
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 
426 	struct task_struct	*alloc_thread;
427 
428 	struct closure		prio;
429 	struct prio_set		*disk_buckets;
430 
431 	/*
432 	 * When allocating new buckets, prio_write() gets first dibs - since we
433 	 * may not be allocate at all without writing priorities and gens.
434 	 * prio_last_buckets[] contains the last buckets we wrote priorities to
435 	 * (so gc can mark them as metadata), prio_buckets[] contains the
436 	 * buckets allocated for the next prio write.
437 	 */
438 	uint64_t		*prio_buckets;
439 	uint64_t		*prio_last_buckets;
440 
441 	/*
442 	 * free: Buckets that are ready to be used
443 	 *
444 	 * free_inc: Incoming buckets - these are buckets that currently have
445 	 * cached data in them, and we can't reuse them until after we write
446 	 * their new gen to disk. After prio_write() finishes writing the new
447 	 * gens/prios, they'll be moved to the free list (and possibly discarded
448 	 * in the process)
449 	 */
450 	DECLARE_FIFO(long, free)[RESERVE_NR];
451 	DECLARE_FIFO(long, free_inc);
452 
453 	size_t			fifo_last_bucket;
454 
455 	/* Allocation stuff: */
456 	struct bucket		*buckets;
457 
458 	DECLARE_HEAP(struct bucket *, heap);
459 
460 	/*
461 	 * If nonzero, we know we aren't going to find any buckets to invalidate
462 	 * until a gc finishes - otherwise we could pointlessly burn a ton of
463 	 * cpu
464 	 */
465 	unsigned int		invalidate_needs_gc;
466 
467 	bool			discard; /* Get rid of? */
468 
469 	struct journal_device	journal;
470 
471 	/* The rest of this all shows up in sysfs */
472 #define IO_ERROR_SHIFT		20
473 	atomic_t		io_errors;
474 	atomic_t		io_count;
475 
476 	atomic_long_t		meta_sectors_written;
477 	atomic_long_t		btree_sectors_written;
478 	atomic_long_t		sectors_written;
479 };
480 
481 struct gc_stat {
482 	size_t			nodes;
483 	size_t			nodes_pre;
484 	size_t			key_bytes;
485 
486 	size_t			nkeys;
487 	uint64_t		data;	/* sectors */
488 	unsigned int		in_use; /* percent */
489 };
490 
491 /*
492  * Flag bits, for how the cache set is shutting down, and what phase it's at:
493  *
494  * CACHE_SET_UNREGISTERING means we're not just shutting down, we're detaching
495  * all the backing devices first (their cached data gets invalidated, and they
496  * won't automatically reattach).
497  *
498  * CACHE_SET_STOPPING always gets set first when we're closing down a cache set;
499  * we'll continue to run normally for awhile with CACHE_SET_STOPPING set (i.e.
500  * flushing dirty data).
501  *
502  * CACHE_SET_RUNNING means all cache devices have been registered and journal
503  * replay is complete.
504  *
505  * CACHE_SET_IO_DISABLE is set when bcache is stopping the whold cache set, all
506  * external and internal I/O should be denied when this flag is set.
507  *
508  */
509 #define CACHE_SET_UNREGISTERING		0
510 #define	CACHE_SET_STOPPING		1
511 #define	CACHE_SET_RUNNING		2
512 #define CACHE_SET_IO_DISABLE		3
513 
514 struct cache_set {
515 	struct closure		cl;
516 
517 	struct list_head	list;
518 	struct kobject		kobj;
519 	struct kobject		internal;
520 	struct dentry		*debug;
521 	struct cache_accounting accounting;
522 
523 	unsigned long		flags;
524 	atomic_t		idle_counter;
525 	atomic_t		at_max_writeback_rate;
526 
527 	struct cache		*cache;
528 
529 	struct bcache_device	**devices;
530 	unsigned int		devices_max_used;
531 	atomic_t		attached_dev_nr;
532 	struct list_head	cached_devs;
533 	uint64_t		cached_dev_sectors;
534 	atomic_long_t		flash_dev_dirty_sectors;
535 	struct closure		caching;
536 
537 	struct closure		sb_write;
538 	struct semaphore	sb_write_mutex;
539 
540 	mempool_t		search;
541 	mempool_t		bio_meta;
542 	struct bio_set		bio_split;
543 
544 	/* For the btree cache */
545 	struct shrinker		shrink;
546 
547 	/* For the btree cache and anything allocation related */
548 	struct mutex		bucket_lock;
549 
550 	/* log2(bucket_size), in sectors */
551 	unsigned short		bucket_bits;
552 
553 	/* log2(block_size), in sectors */
554 	unsigned short		block_bits;
555 
556 	/*
557 	 * Default number of pages for a new btree node - may be less than a
558 	 * full bucket
559 	 */
560 	unsigned int		btree_pages;
561 
562 	/*
563 	 * Lists of struct btrees; lru is the list for structs that have memory
564 	 * allocated for actual btree node, freed is for structs that do not.
565 	 *
566 	 * We never free a struct btree, except on shutdown - we just put it on
567 	 * the btree_cache_freed list and reuse it later. This simplifies the
568 	 * code, and it doesn't cost us much memory as the memory usage is
569 	 * dominated by buffers that hold the actual btree node data and those
570 	 * can be freed - and the number of struct btrees allocated is
571 	 * effectively bounded.
572 	 *
573 	 * btree_cache_freeable effectively is a small cache - we use it because
574 	 * high order page allocations can be rather expensive, and it's quite
575 	 * common to delete and allocate btree nodes in quick succession. It
576 	 * should never grow past ~2-3 nodes in practice.
577 	 */
578 	struct list_head	btree_cache;
579 	struct list_head	btree_cache_freeable;
580 	struct list_head	btree_cache_freed;
581 
582 	/* Number of elements in btree_cache + btree_cache_freeable lists */
583 	unsigned int		btree_cache_used;
584 
585 	/*
586 	 * If we need to allocate memory for a new btree node and that
587 	 * allocation fails, we can cannibalize another node in the btree cache
588 	 * to satisfy the allocation - lock to guarantee only one thread does
589 	 * this at a time:
590 	 */
591 	wait_queue_head_t	btree_cache_wait;
592 	struct task_struct	*btree_cache_alloc_lock;
593 	spinlock_t		btree_cannibalize_lock;
594 
595 	/*
596 	 * When we free a btree node, we increment the gen of the bucket the
597 	 * node is in - but we can't rewrite the prios and gens until we
598 	 * finished whatever it is we were doing, otherwise after a crash the
599 	 * btree node would be freed but for say a split, we might not have the
600 	 * pointers to the new nodes inserted into the btree yet.
601 	 *
602 	 * This is a refcount that blocks prio_write() until the new keys are
603 	 * written.
604 	 */
605 	atomic_t		prio_blocked;
606 	wait_queue_head_t	bucket_wait;
607 
608 	/*
609 	 * For any bio we don't skip we subtract the number of sectors from
610 	 * rescale; when it hits 0 we rescale all the bucket priorities.
611 	 */
612 	atomic_t		rescale;
613 	/*
614 	 * used for GC, identify if any front side I/Os is inflight
615 	 */
616 	atomic_t		search_inflight;
617 	/*
618 	 * When we invalidate buckets, we use both the priority and the amount
619 	 * of good data to determine which buckets to reuse first - to weight
620 	 * those together consistently we keep track of the smallest nonzero
621 	 * priority of any bucket.
622 	 */
623 	uint16_t		min_prio;
624 
625 	/*
626 	 * max(gen - last_gc) for all buckets. When it gets too big we have to
627 	 * gc to keep gens from wrapping around.
628 	 */
629 	uint8_t			need_gc;
630 	struct gc_stat		gc_stats;
631 	size_t			nbuckets;
632 	size_t			avail_nbuckets;
633 
634 	struct task_struct	*gc_thread;
635 	/* Where in the btree gc currently is */
636 	struct bkey		gc_done;
637 
638 	/*
639 	 * For automatical garbage collection after writeback completed, this
640 	 * varialbe is used as bit fields,
641 	 * - 0000 0001b (BCH_ENABLE_AUTO_GC): enable gc after writeback
642 	 * - 0000 0010b (BCH_DO_AUTO_GC):     do gc after writeback
643 	 * This is an optimization for following write request after writeback
644 	 * finished, but read hit rate dropped due to clean data on cache is
645 	 * discarded. Unless user explicitly sets it via sysfs, it won't be
646 	 * enabled.
647 	 */
648 #define BCH_ENABLE_AUTO_GC	1
649 #define BCH_DO_AUTO_GC		2
650 	uint8_t			gc_after_writeback;
651 
652 	/*
653 	 * The allocation code needs gc_mark in struct bucket to be correct, but
654 	 * it's not while a gc is in progress. Protected by bucket_lock.
655 	 */
656 	int			gc_mark_valid;
657 
658 	/* Counts how many sectors bio_insert has added to the cache */
659 	atomic_t		sectors_to_gc;
660 	wait_queue_head_t	gc_wait;
661 
662 	struct keybuf		moving_gc_keys;
663 	/* Number of moving GC bios in flight */
664 	struct semaphore	moving_in_flight;
665 
666 	struct workqueue_struct	*moving_gc_wq;
667 
668 	struct btree		*root;
669 
670 #ifdef CONFIG_BCACHE_DEBUG
671 	struct btree		*verify_data;
672 	struct bset		*verify_ondisk;
673 	struct mutex		verify_lock;
674 #endif
675 
676 	uint8_t			set_uuid[16];
677 	unsigned int		nr_uuids;
678 	struct uuid_entry	*uuids;
679 	BKEY_PADDED(uuid_bucket);
680 	struct closure		uuid_write;
681 	struct semaphore	uuid_write_mutex;
682 
683 	/*
684 	 * A btree node on disk could have too many bsets for an iterator to fit
685 	 * on the stack - have to dynamically allocate them.
686 	 * bch_cache_set_alloc() will make sure the pool can allocate iterators
687 	 * equipped with enough room that can host
688 	 *     (sb.bucket_size / sb.block_size)
689 	 * btree_iter_sets, which is more than static MAX_BSETS.
690 	 */
691 	mempool_t		fill_iter;
692 
693 	struct bset_sort_state	sort;
694 
695 	/* List of buckets we're currently writing data to */
696 	struct list_head	data_buckets;
697 	spinlock_t		data_bucket_lock;
698 
699 	struct journal		journal;
700 
701 #define CONGESTED_MAX		1024
702 	unsigned int		congested_last_us;
703 	atomic_t		congested;
704 
705 	/* The rest of this all shows up in sysfs */
706 	unsigned int		congested_read_threshold_us;
707 	unsigned int		congested_write_threshold_us;
708 
709 	struct time_stats	btree_gc_time;
710 	struct time_stats	btree_split_time;
711 	struct time_stats	btree_read_time;
712 
713 	atomic_long_t		cache_read_races;
714 	atomic_long_t		writeback_keys_done;
715 	atomic_long_t		writeback_keys_failed;
716 
717 	atomic_long_t		reclaim;
718 	atomic_long_t		reclaimed_journal_buckets;
719 	atomic_long_t		flush_write;
720 
721 	enum			{
722 		ON_ERROR_UNREGISTER,
723 		ON_ERROR_PANIC,
724 	}			on_error;
725 #define DEFAULT_IO_ERROR_LIMIT 8
726 	unsigned int		error_limit;
727 	unsigned int		error_decay;
728 
729 	unsigned short		journal_delay_ms;
730 	bool			expensive_debug_checks;
731 	unsigned int		verify:1;
732 	unsigned int		key_merging_disabled:1;
733 	unsigned int		gc_always_rewrite:1;
734 	unsigned int		shrinker_disabled:1;
735 	unsigned int		copy_gc_enabled:1;
736 	unsigned int		idle_max_writeback_rate_enabled:1;
737 
738 #define BUCKET_HASH_BITS	12
739 	struct hlist_head	bucket_hash[1 << BUCKET_HASH_BITS];
740 };
741 
742 struct bbio {
743 	unsigned int		submit_time_us;
744 	union {
745 		struct bkey	key;
746 		uint64_t	_pad[3];
747 		/*
748 		 * We only need pad = 3 here because we only ever carry around a
749 		 * single pointer - i.e. the pointer we're doing io to/from.
750 		 */
751 	};
752 	struct bio		bio;
753 };
754 
755 #define BTREE_PRIO		USHRT_MAX
756 #define INITIAL_PRIO		32768U
757 
758 #define btree_bytes(c)		((c)->btree_pages * PAGE_SIZE)
759 #define btree_blocks(b)							\
760 	((unsigned int) (KEY_SIZE(&b->key) >> (b)->c->block_bits))
761 
762 #define btree_default_blocks(c)						\
763 	((unsigned int) ((PAGE_SECTORS * (c)->btree_pages) >> (c)->block_bits))
764 
765 #define bucket_bytes(ca)	((ca)->sb.bucket_size << 9)
766 #define block_bytes(ca)		((ca)->sb.block_size << 9)
767 
meta_bucket_pages(struct cache_sb * sb)768 static inline unsigned int meta_bucket_pages(struct cache_sb *sb)
769 {
770 	unsigned int n, max_pages;
771 
772 	max_pages = min_t(unsigned int,
773 			  __rounddown_pow_of_two(USHRT_MAX) / PAGE_SECTORS,
774 			  MAX_ORDER_NR_PAGES);
775 
776 	n = sb->bucket_size / PAGE_SECTORS;
777 	if (n > max_pages)
778 		n = max_pages;
779 
780 	return n;
781 }
782 
meta_bucket_bytes(struct cache_sb * sb)783 static inline unsigned int meta_bucket_bytes(struct cache_sb *sb)
784 {
785 	return meta_bucket_pages(sb) << PAGE_SHIFT;
786 }
787 
788 #define prios_per_bucket(ca)						\
789 	((meta_bucket_bytes(&(ca)->sb) - sizeof(struct prio_set)) /	\
790 	 sizeof(struct bucket_disk))
791 
792 #define prio_buckets(ca)						\
793 	DIV_ROUND_UP((size_t) (ca)->sb.nbuckets, prios_per_bucket(ca))
794 
sector_to_bucket(struct cache_set * c,sector_t s)795 static inline size_t sector_to_bucket(struct cache_set *c, sector_t s)
796 {
797 	return s >> c->bucket_bits;
798 }
799 
bucket_to_sector(struct cache_set * c,size_t b)800 static inline sector_t bucket_to_sector(struct cache_set *c, size_t b)
801 {
802 	return ((sector_t) b) << c->bucket_bits;
803 }
804 
bucket_remainder(struct cache_set * c,sector_t s)805 static inline sector_t bucket_remainder(struct cache_set *c, sector_t s)
806 {
807 	return s & (c->cache->sb.bucket_size - 1);
808 }
809 
PTR_BUCKET_NR(struct cache_set * c,const struct bkey * k,unsigned int ptr)810 static inline size_t PTR_BUCKET_NR(struct cache_set *c,
811 				   const struct bkey *k,
812 				   unsigned int ptr)
813 {
814 	return sector_to_bucket(c, PTR_OFFSET(k, ptr));
815 }
816 
PTR_BUCKET(struct cache_set * c,const struct bkey * k,unsigned int ptr)817 static inline struct bucket *PTR_BUCKET(struct cache_set *c,
818 					const struct bkey *k,
819 					unsigned int ptr)
820 {
821 	return c->cache->buckets + PTR_BUCKET_NR(c, k, ptr);
822 }
823 
gen_after(uint8_t a,uint8_t b)824 static inline uint8_t gen_after(uint8_t a, uint8_t b)
825 {
826 	uint8_t r = a - b;
827 
828 	return r > 128U ? 0 : r;
829 }
830 
ptr_stale(struct cache_set * c,const struct bkey * k,unsigned int i)831 static inline uint8_t ptr_stale(struct cache_set *c, const struct bkey *k,
832 				unsigned int i)
833 {
834 	return gen_after(PTR_BUCKET(c, k, i)->gen, PTR_GEN(k, i));
835 }
836 
ptr_available(struct cache_set * c,const struct bkey * k,unsigned int i)837 static inline bool ptr_available(struct cache_set *c, const struct bkey *k,
838 				 unsigned int i)
839 {
840 	return (PTR_DEV(k, i) < MAX_CACHES_PER_SET) && c->cache;
841 }
842 
843 /* Btree key macros */
844 
845 /*
846  * This is used for various on disk data structures - cache_sb, prio_set, bset,
847  * jset: The checksum is _always_ the first 8 bytes of these structs
848  */
849 #define csum_set(i)							\
850 	bch_crc64(((void *) (i)) + sizeof(uint64_t),			\
851 		  ((void *) bset_bkey_last(i)) -			\
852 		  (((void *) (i)) + sizeof(uint64_t)))
853 
854 /* Error handling macros */
855 
856 #define btree_bug(b, ...)						\
857 do {									\
858 	if (bch_cache_set_error((b)->c, __VA_ARGS__))			\
859 		dump_stack();						\
860 } while (0)
861 
862 #define cache_bug(c, ...)						\
863 do {									\
864 	if (bch_cache_set_error(c, __VA_ARGS__))			\
865 		dump_stack();						\
866 } while (0)
867 
868 #define btree_bug_on(cond, b, ...)					\
869 do {									\
870 	if (cond)							\
871 		btree_bug(b, __VA_ARGS__);				\
872 } while (0)
873 
874 #define cache_bug_on(cond, c, ...)					\
875 do {									\
876 	if (cond)							\
877 		cache_bug(c, __VA_ARGS__);				\
878 } while (0)
879 
880 #define cache_set_err_on(cond, c, ...)					\
881 do {									\
882 	if (cond)							\
883 		bch_cache_set_error(c, __VA_ARGS__);			\
884 } while (0)
885 
886 /* Looping macros */
887 
888 #define for_each_bucket(b, ca)						\
889 	for (b = (ca)->buckets + (ca)->sb.first_bucket;			\
890 	     b < (ca)->buckets + (ca)->sb.nbuckets; b++)
891 
cached_dev_put(struct cached_dev * dc)892 static inline void cached_dev_put(struct cached_dev *dc)
893 {
894 	if (refcount_dec_and_test(&dc->count))
895 		schedule_work(&dc->detach);
896 }
897 
cached_dev_get(struct cached_dev * dc)898 static inline bool cached_dev_get(struct cached_dev *dc)
899 {
900 	if (!refcount_inc_not_zero(&dc->count))
901 		return false;
902 
903 	/* Paired with the mb in cached_dev_attach */
904 	smp_mb__after_atomic();
905 	return true;
906 }
907 
908 /*
909  * bucket_gc_gen() returns the difference between the bucket's current gen and
910  * the oldest gen of any pointer into that bucket in the btree (last_gc).
911  */
912 
bucket_gc_gen(struct bucket * b)913 static inline uint8_t bucket_gc_gen(struct bucket *b)
914 {
915 	return b->gen - b->last_gc;
916 }
917 
918 #define BUCKET_GC_GEN_MAX	96U
919 
920 #define kobj_attribute_write(n, fn)					\
921 	static struct kobj_attribute ksysfs_##n = __ATTR(n, 0200, NULL, fn)
922 
923 #define kobj_attribute_rw(n, show, store)				\
924 	static struct kobj_attribute ksysfs_##n =			\
925 		__ATTR(n, 0600, show, store)
926 
wake_up_allocators(struct cache_set * c)927 static inline void wake_up_allocators(struct cache_set *c)
928 {
929 	struct cache *ca = c->cache;
930 
931 	wake_up_process(ca->alloc_thread);
932 }
933 
closure_bio_submit(struct cache_set * c,struct bio * bio,struct closure * cl)934 static inline void closure_bio_submit(struct cache_set *c,
935 				      struct bio *bio,
936 				      struct closure *cl)
937 {
938 	closure_get(cl);
939 	if (unlikely(test_bit(CACHE_SET_IO_DISABLE, &c->flags))) {
940 		bio->bi_status = BLK_STS_IOERR;
941 		bio_endio(bio);
942 		return;
943 	}
944 	submit_bio_noacct(bio);
945 }
946 
947 /*
948  * Prevent the kthread exits directly, and make sure when kthread_stop()
949  * is called to stop a kthread, it is still alive. If a kthread might be
950  * stopped by CACHE_SET_IO_DISABLE bit set, wait_for_kthread_stop() is
951  * necessary before the kthread returns.
952  */
wait_for_kthread_stop(void)953 static inline void wait_for_kthread_stop(void)
954 {
955 	while (!kthread_should_stop()) {
956 		set_current_state(TASK_INTERRUPTIBLE);
957 		schedule();
958 	}
959 }
960 
961 /* Forward declarations */
962 
963 void bch_count_backing_io_errors(struct cached_dev *dc, struct bio *bio);
964 void bch_count_io_errors(struct cache *ca, blk_status_t error,
965 			 int is_read, const char *m);
966 void bch_bbio_count_io_errors(struct cache_set *c, struct bio *bio,
967 			      blk_status_t error, const char *m);
968 void bch_bbio_endio(struct cache_set *c, struct bio *bio,
969 		    blk_status_t error, const char *m);
970 void bch_bbio_free(struct bio *bio, struct cache_set *c);
971 struct bio *bch_bbio_alloc(struct cache_set *c);
972 
973 void __bch_submit_bbio(struct bio *bio, struct cache_set *c);
974 void bch_submit_bbio(struct bio *bio, struct cache_set *c,
975 		     struct bkey *k, unsigned int ptr);
976 
977 uint8_t bch_inc_gen(struct cache *ca, struct bucket *b);
978 void bch_rescale_priorities(struct cache_set *c, int sectors);
979 
980 bool bch_can_invalidate_bucket(struct cache *ca, struct bucket *b);
981 void __bch_invalidate_one_bucket(struct cache *ca, struct bucket *b);
982 
983 void __bch_bucket_free(struct cache *ca, struct bucket *b);
984 void bch_bucket_free(struct cache_set *c, struct bkey *k);
985 
986 long bch_bucket_alloc(struct cache *ca, unsigned int reserve, bool wait);
987 int __bch_bucket_alloc_set(struct cache_set *c, unsigned int reserve,
988 			   struct bkey *k, bool wait);
989 int bch_bucket_alloc_set(struct cache_set *c, unsigned int reserve,
990 			 struct bkey *k, bool wait);
991 bool bch_alloc_sectors(struct cache_set *c, struct bkey *k,
992 		       unsigned int sectors, unsigned int write_point,
993 		       unsigned int write_prio, bool wait);
994 bool bch_cached_dev_error(struct cached_dev *dc);
995 
996 __printf(2, 3)
997 bool bch_cache_set_error(struct cache_set *c, const char *fmt, ...);
998 
999 int bch_prio_write(struct cache *ca, bool wait);
1000 void bch_write_bdev_super(struct cached_dev *dc, struct closure *parent);
1001 
1002 extern struct workqueue_struct *bcache_wq;
1003 extern struct workqueue_struct *bch_journal_wq;
1004 extern struct workqueue_struct *bch_flush_wq;
1005 extern struct mutex bch_register_lock;
1006 extern struct list_head bch_cache_sets;
1007 
1008 extern const struct kobj_type bch_cached_dev_ktype;
1009 extern const struct kobj_type bch_flash_dev_ktype;
1010 extern const struct kobj_type bch_cache_set_ktype;
1011 extern const struct kobj_type bch_cache_set_internal_ktype;
1012 extern const struct kobj_type bch_cache_ktype;
1013 
1014 void bch_cached_dev_release(struct kobject *kobj);
1015 void bch_flash_dev_release(struct kobject *kobj);
1016 void bch_cache_set_release(struct kobject *kobj);
1017 void bch_cache_release(struct kobject *kobj);
1018 
1019 int bch_uuid_write(struct cache_set *c);
1020 void bcache_write_super(struct cache_set *c);
1021 
1022 int bch_flash_dev_create(struct cache_set *c, uint64_t size);
1023 
1024 int bch_cached_dev_attach(struct cached_dev *dc, struct cache_set *c,
1025 			  uint8_t *set_uuid);
1026 void bch_cached_dev_detach(struct cached_dev *dc);
1027 int bch_cached_dev_run(struct cached_dev *dc);
1028 void bcache_device_stop(struct bcache_device *d);
1029 
1030 void bch_cache_set_unregister(struct cache_set *c);
1031 void bch_cache_set_stop(struct cache_set *c);
1032 
1033 struct cache_set *bch_cache_set_alloc(struct cache_sb *sb);
1034 void bch_btree_cache_free(struct cache_set *c);
1035 int bch_btree_cache_alloc(struct cache_set *c);
1036 void bch_moving_init_cache_set(struct cache_set *c);
1037 int bch_open_buckets_alloc(struct cache_set *c);
1038 void bch_open_buckets_free(struct cache_set *c);
1039 
1040 int bch_cache_allocator_start(struct cache *ca);
1041 
1042 void bch_debug_exit(void);
1043 void bch_debug_init(void);
1044 void bch_request_exit(void);
1045 int bch_request_init(void);
1046 void bch_btree_exit(void);
1047 int bch_btree_init(void);
1048 
1049 #endif /* _BCACHE_H */
1050