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