/* SPDX-License-Identifier: GPL-2.0 */ #ifndef _BCACHE_H #define _BCACHE_H /* * SOME HIGH LEVEL CODE DOCUMENTATION: * * Bcache mostly works with cache sets, cache devices, and backing devices. * * Support for multiple cache devices hasn't quite been finished off yet, but * it's about 95% plumbed through. A cache set and its cache devices is sort of * like a md raid array and its component devices. Most of the code doesn't care * about individual cache devices, the main abstraction is the cache set. * * Multiple cache devices is intended to give us the ability to mirror dirty * cached data and metadata, without mirroring clean cached data. * * Backing devices are different, in that they have a lifetime independent of a * cache set. When you register a newly formatted backing device it'll come up * in passthrough mode, and then you can attach and detach a backing device from * a cache set at runtime - while it's mounted and in use. Detaching implicitly * invalidates any cached data for that backing device. * * A cache set can have multiple (many) backing devices attached to it. * * There's also flash only volumes - this is the reason for the distinction * between struct cached_dev and struct bcache_device. A flash only volume * works much like a bcache device that has a backing device, except the * "cached" data is always dirty. The end result is that we get thin * provisioning with very little additional code. * * Flash only volumes work but they're not production ready because the moving * garbage collector needs more work. More on that later. * * BUCKETS/ALLOCATION: * * Bcache is primarily designed for caching, which means that in normal * operation all of our available space will be allocated. Thus, we need an * efficient way of deleting things from the cache so we can write new things to * it. * * To do this, we first divide the cache device up into buckets. A bucket is the * unit of allocation; they're typically around 1 mb - anywhere from 128k to 2M+ * works efficiently. * * Each bucket has a 16 bit priority, and an 8 bit generation associated with * it. The gens and priorities for all the buckets are stored contiguously and * packed on disk (in a linked list of buckets - aside from the superblock, all * of bcache's metadata is stored in buckets). * * The priority is used to implement an LRU. We reset a bucket's priority when * we allocate it or on cache it, and every so often we decrement the priority * of each bucket. It could be used to implement something more sophisticated, * if anyone ever gets around to it. * * The generation is used for invalidating buckets. Each pointer also has an 8 * bit generation embedded in it; for a pointer to be considered valid, its gen * must match the gen of the bucket it points into. Thus, to reuse a bucket all * we have to do is increment its gen (and write its new gen to disk; we batch * this up). * * Bcache is entirely COW - we never write twice to a bucket, even buckets that * contain metadata (including btree nodes). * * THE BTREE: * * Bcache is in large part design around the btree. * * At a high level, the btree is just an index of key -> ptr tuples. * * Keys represent extents, and thus have a size field. Keys also have a variable * number of pointers attached to them (potentially zero, which is handy for * invalidating the cache). * * The key itself is an inode:offset pair. The inode number corresponds to a * backing device or a flash only volume. The offset is the ending offset of the * extent within the inode - not the starting offset; this makes lookups * slightly more convenient. * * Pointers contain the cache device id, the offset on that device, and an 8 bit * generation number. More on the gen later. * * Index lookups are not fully abstracted - cache lookups in particular are * still somewhat mixed in with the btree code, but things are headed in that * direction. * * Updates are fairly well abstracted, though. There are two different ways of * updating the btree; insert and replace. * * BTREE_INSERT will just take a list of keys and insert them into the btree - * overwriting (possibly only partially) any extents they overlap with. This is * used to update the index after a write. * * BTREE_REPLACE is really cmpxchg(); it inserts a key into the btree iff it is * overwriting a key that matches another given key. This is used for inserting * data into the cache after a cache miss, and for background writeback, and for * the moving garbage collector. * * There is no "delete" operation; deleting things from the index is * accomplished by either by invalidating pointers (by incrementing a bucket's * gen) or by inserting a key with 0 pointers - which will overwrite anything * previously present at that location in the index. * * This means that there are always stale/invalid keys in the btree. They're * filtered out by the code that iterates through a btree node, and removed when * a btree node is rewritten. * * BTREE NODES: * * Our unit of allocation is a bucket, and we can't arbitrarily allocate and * free smaller than a bucket - so, that's how big our btree nodes are. * * (If buckets are really big we'll only use part of the bucket for a btree node * - no less than 1/4th - but a bucket still contains no more than a single * btree node. I'd actually like to change this, but for now we rely on the * bucket's gen for deleting btree nodes when we rewrite/split a node.) * * Anyways, btree nodes are big - big enough to be inefficient with a textbook * btree implementation. * * The way this is solved is that btree nodes are internally log structured; we * can append new keys to an existing btree node without rewriting it. This * means each set of keys we write is sorted, but the node is not. * * We maintain this log structure in memory - keeping 1Mb of keys sorted would * be expensive, and we have to distinguish between the keys we have written and * the keys we haven't. So to do a lookup in a btree node, we have to search * each sorted set. But we do merge written sets together lazily, so the cost of * these extra searches is quite low (normally most of the keys in a btree node * will be in one big set, and then there'll be one or two sets that are much * smaller). * * This log structure makes bcache's btree more of a hybrid between a * conventional btree and a compacting data structure, with some of the * advantages of both. * * GARBAGE COLLECTION: * * We can't just invalidate any bucket - it might contain dirty data or * metadata. If it once contained dirty data, other writes might overwrite it * later, leaving no valid pointers into that bucket in the index. * * Thus, the primary purpose of garbage collection is to find buckets to reuse. * It also counts how much valid data it each bucket currently contains, so that * allocation can reuse buckets sooner when they've been mostly overwritten. * * It also does some things that are really internal to the btree * implementation. If a btree node contains pointers that are stale by more than * some threshold, it rewrites the btree node to avoid the bucket's generation * wrapping around. It also merges adjacent btree nodes if they're empty enough. * * THE JOURNAL: * * Bcache's journal is not necessary for consistency; we always strictly * order metadata writes so that the btree and everything else is consistent on * disk in the event of an unclean shutdown, and in fact bcache had writeback * caching (with recovery from unclean shutdown) before journalling was * implemented. * * Rather, the journal is purely a performance optimization; we can't complete a * write until we've updated the index on disk, otherwise the cache would be * inconsistent in the event of an unclean shutdown. This means that without the * journal, on random write workloads we constantly have to update all the leaf * nodes in the btree, and those writes will be mostly empty (appending at most * a few keys each) - highly inefficient in terms of amount of metadata writes, * and it puts more strain on the various btree resorting/compacting code. * * The journal is just a log of keys we've inserted; on startup we just reinsert * all the keys in the open journal entries. That means that when we're updating * a node in the btree, we can wait until a 4k block of keys fills up before * writing them out. * * For simplicity, we only journal updates to leaf nodes; updates to parent * nodes are rare enough (since our leaf nodes are huge) that it wasn't worth * the complexity to deal with journalling them (in particular, journal replay) * - updates to non leaf nodes just happen synchronously (see btree_split()). */ #define pr_fmt(fmt) … #include <linux/bio.h> #include <linux/closure.h> #include <linux/kobject.h> #include <linux/list.h> #include <linux/mutex.h> #include <linux/rbtree.h> #include <linux/rwsem.h> #include <linux/refcount.h> #include <linux/types.h> #include <linux/workqueue.h> #include <linux/kthread.h> #include "bcache_ondisk.h" #include "bset.h" #include "util.h" struct bucket { … }; /* * I'd use bitfields for these, but I don't trust the compiler not to screw me * as multiple threads touch struct bucket without locking */ BITMASK(GC_MARK, struct bucket, gc_mark, 0, 2); #define GC_MARK_RECLAIMABLE … #define GC_MARK_DIRTY … #define GC_MARK_METADATA … #define GC_SECTORS_USED_SIZE … #define MAX_GC_SECTORS_USED … BITMASK(GC_SECTORS_USED, struct bucket, gc_mark, 2, GC_SECTORS_USED_SIZE); BITMASK(GC_MOVE, struct bucket, gc_mark, 15, 1); #include "journal.h" #include "stats.h" struct search; struct btree; struct keybuf; struct keybuf_key { … }; struct keybuf { … }; struct bcache_device { … }; struct io { … }; enum stop_on_failure { … }; struct cached_dev { … }; enum alloc_reserve { … }; struct cache { … }; struct gc_stat { … }; /* * Flag bits, for how the cache set is shutting down, and what phase it's at: * * CACHE_SET_UNREGISTERING means we're not just shutting down, we're detaching * all the backing devices first (their cached data gets invalidated, and they * won't automatically reattach). * * CACHE_SET_STOPPING always gets set first when we're closing down a cache set; * we'll continue to run normally for awhile with CACHE_SET_STOPPING set (i.e. * flushing dirty data). * * CACHE_SET_RUNNING means all cache devices have been registered and journal * replay is complete. * * CACHE_SET_IO_DISABLE is set when bcache is stopping the whold cache set, all * external and internal I/O should be denied when this flag is set. * */ #define CACHE_SET_UNREGISTERING … #define CACHE_SET_STOPPING … #define CACHE_SET_RUNNING … #define CACHE_SET_IO_DISABLE … struct cache_set { … }; struct bbio { … }; #define BTREE_PRIO … #define INITIAL_PRIO … #define btree_bytes(c) … #define btree_blocks(b) … #define btree_default_blocks(c) … #define bucket_bytes(ca) … #define block_bytes(ca) … static inline unsigned int meta_bucket_pages(struct cache_sb *sb) { … } static inline unsigned int meta_bucket_bytes(struct cache_sb *sb) { … } #define prios_per_bucket(ca) … #define prio_buckets(ca) … static inline size_t sector_to_bucket(struct cache_set *c, sector_t s) { … } static inline sector_t bucket_to_sector(struct cache_set *c, size_t b) { … } static inline sector_t bucket_remainder(struct cache_set *c, sector_t s) { … } static inline size_t PTR_BUCKET_NR(struct cache_set *c, const struct bkey *k, unsigned int ptr) { … } static inline struct bucket *PTR_BUCKET(struct cache_set *c, const struct bkey *k, unsigned int ptr) { … } static inline uint8_t gen_after(uint8_t a, uint8_t b) { … } static inline uint8_t ptr_stale(struct cache_set *c, const struct bkey *k, unsigned int i) { … } static inline bool ptr_available(struct cache_set *c, const struct bkey *k, unsigned int i) { … } /* Btree key macros */ /* * This is used for various on disk data structures - cache_sb, prio_set, bset, * jset: The checksum is _always_ the first 8 bytes of these structs */ #define csum_set(i) … /* Error handling macros */ #define btree_bug(b, ...) … #define cache_bug(c, ...) … #define btree_bug_on(cond, b, ...) … #define cache_bug_on(cond, c, ...) … #define cache_set_err_on(cond, c, ...) … /* Looping macros */ #define for_each_bucket(b, ca) … static inline void cached_dev_put(struct cached_dev *dc) { … } static inline bool cached_dev_get(struct cached_dev *dc) { … } /* * bucket_gc_gen() returns the difference between the bucket's current gen and * the oldest gen of any pointer into that bucket in the btree (last_gc). */ static inline uint8_t bucket_gc_gen(struct bucket *b) { … } #define BUCKET_GC_GEN_MAX … #define kobj_attribute_write(n, fn) … #define kobj_attribute_rw(n, show, store) … static inline void wake_up_allocators(struct cache_set *c) { … } static inline void closure_bio_submit(struct cache_set *c, struct bio *bio, struct closure *cl) { … } /* * Prevent the kthread exits directly, and make sure when kthread_stop() * is called to stop a kthread, it is still alive. If a kthread might be * stopped by CACHE_SET_IO_DISABLE bit set, wait_for_kthread_stop() is * necessary before the kthread returns. */ static inline void wait_for_kthread_stop(void) { … } /* Forward declarations */ void bch_count_backing_io_errors(struct cached_dev *dc, struct bio *bio); void bch_count_io_errors(struct cache *ca, blk_status_t error, int is_read, const char *m); void bch_bbio_count_io_errors(struct cache_set *c, struct bio *bio, blk_status_t error, const char *m); void bch_bbio_endio(struct cache_set *c, struct bio *bio, blk_status_t error, const char *m); void bch_bbio_free(struct bio *bio, struct cache_set *c); struct bio *bch_bbio_alloc(struct cache_set *c); void __bch_submit_bbio(struct bio *bio, struct cache_set *c); void bch_submit_bbio(struct bio *bio, struct cache_set *c, struct bkey *k, unsigned int ptr); uint8_t bch_inc_gen(struct cache *ca, struct bucket *b); void bch_rescale_priorities(struct cache_set *c, int sectors); bool bch_can_invalidate_bucket(struct cache *ca, struct bucket *b); void __bch_invalidate_one_bucket(struct cache *ca, struct bucket *b); void __bch_bucket_free(struct cache *ca, struct bucket *b); void bch_bucket_free(struct cache_set *c, struct bkey *k); long bch_bucket_alloc(struct cache *ca, unsigned int reserve, bool wait); int __bch_bucket_alloc_set(struct cache_set *c, unsigned int reserve, struct bkey *k, bool wait); int bch_bucket_alloc_set(struct cache_set *c, unsigned int reserve, struct bkey *k, bool wait); bool bch_alloc_sectors(struct cache_set *c, struct bkey *k, unsigned int sectors, unsigned int write_point, unsigned int write_prio, bool wait); bool bch_cached_dev_error(struct cached_dev *dc); __printf(2, 3) bool bch_cache_set_error(struct cache_set *c, const char *fmt, ...); int bch_prio_write(struct cache *ca, bool wait); void bch_write_bdev_super(struct cached_dev *dc, struct closure *parent); extern struct workqueue_struct *bcache_wq; extern struct workqueue_struct *bch_journal_wq; extern struct workqueue_struct *bch_flush_wq; extern struct mutex bch_register_lock; extern struct list_head bch_cache_sets; extern const struct kobj_type bch_cached_dev_ktype; extern const struct kobj_type bch_flash_dev_ktype; extern const struct kobj_type bch_cache_set_ktype; extern const struct kobj_type bch_cache_set_internal_ktype; extern const struct kobj_type bch_cache_ktype; void bch_cached_dev_release(struct kobject *kobj); void bch_flash_dev_release(struct kobject *kobj); void bch_cache_set_release(struct kobject *kobj); void bch_cache_release(struct kobject *kobj); int bch_uuid_write(struct cache_set *c); void bcache_write_super(struct cache_set *c); int bch_flash_dev_create(struct cache_set *c, uint64_t size); int bch_cached_dev_attach(struct cached_dev *dc, struct cache_set *c, uint8_t *set_uuid); void bch_cached_dev_detach(struct cached_dev *dc); int bch_cached_dev_run(struct cached_dev *dc); void bcache_device_stop(struct bcache_device *d); void bch_cache_set_unregister(struct cache_set *c); void bch_cache_set_stop(struct cache_set *c); struct cache_set *bch_cache_set_alloc(struct cache_sb *sb); void bch_btree_cache_free(struct cache_set *c); int bch_btree_cache_alloc(struct cache_set *c); void bch_moving_init_cache_set(struct cache_set *c); int bch_open_buckets_alloc(struct cache_set *c); void bch_open_buckets_free(struct cache_set *c); int bch_cache_allocator_start(struct cache *ca); void bch_debug_exit(void); void bch_debug_init(void); void bch_request_exit(void); int bch_request_init(void); void bch_btree_exit(void); int bch_btree_init(void); #endif /* _BCACHE_H */
Codebase Browser
linux