1 #ifndef _BCACHE_H 2 #define _BCACHE_H 3 4 /* 5 * SOME HIGH LEVEL CODE DOCUMENTATION: 6 * 7 * Bcache mostly works with cache sets, cache devices, and backing devices. 8 * 9 * Support for multiple cache devices hasn't quite been finished off yet, but 10 * it's about 95% plumbed through. A cache set and its cache devices is sort of 11 * like a md raid array and its component devices. Most of the code doesn't care 12 * about individual cache devices, the main abstraction is the cache set. 13 * 14 * Multiple cache devices is intended to give us the ability to mirror dirty 15 * cached data and metadata, without mirroring clean cached data. 16 * 17 * Backing devices are different, in that they have a lifetime independent of a 18 * cache set. When you register a newly formatted backing device it'll come up 19 * in passthrough mode, and then you can attach and detach a backing device from 20 * a cache set at runtime - while it's mounted and in use. Detaching implicitly 21 * invalidates any cached data for that backing device. 22 * 23 * A cache set can have multiple (many) backing devices attached to it. 24 * 25 * There's also flash only volumes - this is the reason for the distinction 26 * between struct cached_dev and struct bcache_device. A flash only volume 27 * works much like a bcache device that has a backing device, except the 28 * "cached" data is always dirty. The end result is that we get thin 29 * provisioning with very little additional code. 30 * 31 * Flash only volumes work but they're not production ready because the moving 32 * garbage collector needs more work. More on that later. 33 * 34 * BUCKETS/ALLOCATION: 35 * 36 * Bcache is primarily designed for caching, which means that in normal 37 * operation all of our available space will be allocated. Thus, we need an 38 * efficient way of deleting things from the cache so we can write new things to 39 * it. 40 * 41 * To do this, we first divide the cache device up into buckets. A bucket is the 42 * unit of allocation; they're typically around 1 mb - anywhere from 128k to 2M+ 43 * works efficiently. 44 * 45 * Each bucket has a 16 bit priority, and an 8 bit generation associated with 46 * it. The gens and priorities for all the buckets are stored contiguously and 47 * packed on disk (in a linked list of buckets - aside from the superblock, all 48 * of bcache's metadata is stored in buckets). 49 * 50 * The priority is used to implement an LRU. We reset a bucket's priority when 51 * we allocate it or on cache it, and every so often we decrement the priority 52 * of each bucket. It could be used to implement something more sophisticated, 53 * if anyone ever gets around to it. 54 * 55 * The generation is used for invalidating buckets. Each pointer also has an 8 56 * bit generation embedded in it; for a pointer to be considered valid, its gen 57 * must match the gen of the bucket it points into. Thus, to reuse a bucket all 58 * we have to do is increment its gen (and write its new gen to disk; we batch 59 * this up). 60 * 61 * Bcache is entirely COW - we never write twice to a bucket, even buckets that 62 * contain metadata (including btree nodes). 63 * 64 * THE BTREE: 65 * 66 * Bcache is in large part design around the btree. 67 * 68 * At a high level, the btree is just an index of key -> ptr tuples. 69 * 70 * Keys represent extents, and thus have a size field. Keys also have a variable 71 * number of pointers attached to them (potentially zero, which is handy for 72 * invalidating the cache). 73 * 74 * The key itself is an inode:offset pair. The inode number corresponds to a 75 * backing device or a flash only volume. The offset is the ending offset of the 76 * extent within the inode - not the starting offset; this makes lookups 77 * slightly more convenient. 78 * 79 * Pointers contain the cache device id, the offset on that device, and an 8 bit 80 * generation number. More on the gen later. 81 * 82 * Index lookups are not fully abstracted - cache lookups in particular are 83 * still somewhat mixed in with the btree code, but things are headed in that 84 * direction. 85 * 86 * Updates are fairly well abstracted, though. There are two different ways of 87 * updating the btree; insert and replace. 88 * 89 * BTREE_INSERT will just take a list of keys and insert them into the btree - 90 * overwriting (possibly only partially) any extents they overlap with. This is 91 * used to update the index after a write. 92 * 93 * BTREE_REPLACE is really cmpxchg(); it inserts a key into the btree iff it is 94 * overwriting a key that matches another given key. This is used for inserting 95 * data into the cache after a cache miss, and for background writeback, and for 96 * the moving garbage collector. 97 * 98 * There is no "delete" operation; deleting things from the index is 99 * accomplished by either by invalidating pointers (by incrementing a bucket's 100 * gen) or by inserting a key with 0 pointers - which will overwrite anything 101 * previously present at that location in the index. 102 * 103 * This means that there are always stale/invalid keys in the btree. They're 104 * filtered out by the code that iterates through a btree node, and removed when 105 * a btree node is rewritten. 106 * 107 * BTREE NODES: 108 * 109 * Our unit of allocation is a bucket, and we we can't arbitrarily allocate and 110 * free smaller than a bucket - so, that's how big our btree nodes are. 111 * 112 * (If buckets are really big we'll only use part of the bucket for a btree node 113 * - no less than 1/4th - but a bucket still contains no more than a single 114 * btree node. I'd actually like to change this, but for now we rely on the 115 * bucket's gen for deleting btree nodes when we rewrite/split a node.) 116 * 117 * Anyways, btree nodes are big - big enough to be inefficient with a textbook 118 * btree implementation. 119 * 120 * The way this is solved is that btree nodes are internally log structured; we 121 * can append new keys to an existing btree node without rewriting it. This 122 * means each set of keys we write is sorted, but the node is not. 123 * 124 * We maintain this log structure in memory - keeping 1Mb of keys sorted would 125 * be expensive, and we have to distinguish between the keys we have written and 126 * the keys we haven't. So to do a lookup in a btree node, we have to search 127 * each sorted set. But we do merge written sets together lazily, so the cost of 128 * these extra searches is quite low (normally most of the keys in a btree node 129 * will be in one big set, and then there'll be one or two sets that are much 130 * smaller). 131 * 132 * This log structure makes bcache's btree more of a hybrid between a 133 * conventional btree and a compacting data structure, with some of the 134 * advantages of both. 135 * 136 * GARBAGE COLLECTION: 137 * 138 * We can't just invalidate any bucket - it might contain dirty data or 139 * metadata. If it once contained dirty data, other writes might overwrite it 140 * later, leaving no valid pointers into that bucket in the index. 141 * 142 * Thus, the primary purpose of garbage collection is to find buckets to reuse. 143 * It also counts how much valid data it each bucket currently contains, so that 144 * allocation can reuse buckets sooner when they've been mostly overwritten. 145 * 146 * It also does some things that are really internal to the btree 147 * implementation. If a btree node contains pointers that are stale by more than 148 * some threshold, it rewrites the btree node to avoid the bucket's generation 149 * wrapping around. It also merges adjacent btree nodes if they're empty enough. 150 * 151 * THE JOURNAL: 152 * 153 * Bcache's journal is not necessary for consistency; we always strictly 154 * order metadata writes so that the btree and everything else is consistent on 155 * disk in the event of an unclean shutdown, and in fact bcache had writeback 156 * caching (with recovery from unclean shutdown) before journalling was 157 * implemented. 158 * 159 * Rather, the journal is purely a performance optimization; we can't complete a 160 * write until we've updated the index on disk, otherwise the cache would be 161 * inconsistent in the event of an unclean shutdown. This means that without the 162 * journal, on random write workloads we constantly have to update all the leaf 163 * nodes in the btree, and those writes will be mostly empty (appending at most 164 * a few keys each) - highly inefficient in terms of amount of metadata writes, 165 * and it puts more strain on the various btree resorting/compacting code. 166 * 167 * The journal is just a log of keys we've inserted; on startup we just reinsert 168 * all the keys in the open journal entries. That means that when we're updating 169 * a node in the btree, we can wait until a 4k block of keys fills up before 170 * writing them out. 171 * 172 * For simplicity, we only journal updates to leaf nodes; updates to parent 173 * nodes are rare enough (since our leaf nodes are huge) that it wasn't worth 174 * the complexity to deal with journalling them (in particular, journal replay) 175 * - updates to non leaf nodes just happen synchronously (see btree_split()). 176 */ 177 178 #define pr_fmt(fmt) "bcache: %s() " fmt "\n", __func__ 179 180 #include <linux/bio.h> 181 #include <linux/blktrace_api.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/types.h> 188 #include <linux/workqueue.h> 189 190 #include "util.h" 191 #include "closure.h" 192 193 struct bucket { 194 atomic_t pin; 195 uint16_t prio; 196 uint8_t gen; 197 uint8_t disk_gen; 198 uint8_t last_gc; /* Most out of date gen in the btree */ 199 uint8_t gc_gen; 200 uint16_t gc_mark; 201 }; 202 203 /* 204 * I'd use bitfields for these, but I don't trust the compiler not to screw me 205 * as multiple threads touch struct bucket without locking 206 */ 207 208 BITMASK(GC_MARK, struct bucket, gc_mark, 0, 2); 209 #define GC_MARK_RECLAIMABLE 0 210 #define GC_MARK_DIRTY 1 211 #define GC_MARK_METADATA 2 212 BITMASK(GC_SECTORS_USED, struct bucket, gc_mark, 2, 14); 213 214 struct bkey { 215 uint64_t high; 216 uint64_t low; 217 uint64_t ptr[]; 218 }; 219 220 /* Enough for a key with 6 pointers */ 221 #define BKEY_PAD 8 222 223 #define BKEY_PADDED(key) \ 224 union { struct bkey key; uint64_t key ## _pad[BKEY_PAD]; } 225 226 /* Version 1: Backing device 227 * Version 2: Seed pointer into btree node checksum 228 * Version 3: New UUID format 229 */ 230 #define BCACHE_SB_VERSION 3 231 232 #define SB_SECTOR 8 233 #define SB_SIZE 4096 234 #define SB_LABEL_SIZE 32 235 #define SB_JOURNAL_BUCKETS 256U 236 /* SB_JOURNAL_BUCKETS must be divisible by BITS_PER_LONG */ 237 #define MAX_CACHES_PER_SET 8 238 239 #define BDEV_DATA_START 16 /* sectors */ 240 241 struct cache_sb { 242 uint64_t csum; 243 uint64_t offset; /* sector where this sb was written */ 244 uint64_t version; 245 #define CACHE_BACKING_DEV 1 246 247 uint8_t magic[16]; 248 249 uint8_t uuid[16]; 250 union { 251 uint8_t set_uuid[16]; 252 uint64_t set_magic; 253 }; 254 uint8_t label[SB_LABEL_SIZE]; 255 256 uint64_t flags; 257 uint64_t seq; 258 uint64_t pad[8]; 259 260 uint64_t nbuckets; /* device size */ 261 uint16_t block_size; /* sectors */ 262 uint16_t bucket_size; /* sectors */ 263 264 uint16_t nr_in_set; 265 uint16_t nr_this_dev; 266 267 uint32_t last_mount; /* time_t */ 268 269 uint16_t first_bucket; 270 union { 271 uint16_t njournal_buckets; 272 uint16_t keys; 273 }; 274 uint64_t d[SB_JOURNAL_BUCKETS]; /* journal buckets */ 275 }; 276 277 BITMASK(CACHE_SYNC, struct cache_sb, flags, 0, 1); 278 BITMASK(CACHE_DISCARD, struct cache_sb, flags, 1, 1); 279 BITMASK(CACHE_REPLACEMENT, struct cache_sb, flags, 2, 3); 280 #define CACHE_REPLACEMENT_LRU 0U 281 #define CACHE_REPLACEMENT_FIFO 1U 282 #define CACHE_REPLACEMENT_RANDOM 2U 283 284 BITMASK(BDEV_CACHE_MODE, struct cache_sb, flags, 0, 4); 285 #define CACHE_MODE_WRITETHROUGH 0U 286 #define CACHE_MODE_WRITEBACK 1U 287 #define CACHE_MODE_WRITEAROUND 2U 288 #define CACHE_MODE_NONE 3U 289 BITMASK(BDEV_STATE, struct cache_sb, flags, 61, 2); 290 #define BDEV_STATE_NONE 0U 291 #define BDEV_STATE_CLEAN 1U 292 #define BDEV_STATE_DIRTY 2U 293 #define BDEV_STATE_STALE 3U 294 295 /* Version 1: Seed pointer into btree node checksum 296 */ 297 #define BCACHE_BSET_VERSION 1 298 299 /* 300 * This is the on disk format for btree nodes - a btree node on disk is a list 301 * of these; within each set the keys are sorted 302 */ 303 struct bset { 304 uint64_t csum; 305 uint64_t magic; 306 uint64_t seq; 307 uint32_t version; 308 uint32_t keys; 309 310 union { 311 struct bkey start[0]; 312 uint64_t d[0]; 313 }; 314 }; 315 316 /* 317 * On disk format for priorities and gens - see super.c near prio_write() for 318 * more. 319 */ 320 struct prio_set { 321 uint64_t csum; 322 uint64_t magic; 323 uint64_t seq; 324 uint32_t version; 325 uint32_t pad; 326 327 uint64_t next_bucket; 328 329 struct bucket_disk { 330 uint16_t prio; 331 uint8_t gen; 332 } __attribute((packed)) data[]; 333 }; 334 335 struct uuid_entry { 336 union { 337 struct { 338 uint8_t uuid[16]; 339 uint8_t label[32]; 340 uint32_t first_reg; 341 uint32_t last_reg; 342 uint32_t invalidated; 343 344 uint32_t flags; 345 /* Size of flash only volumes */ 346 uint64_t sectors; 347 }; 348 349 uint8_t pad[128]; 350 }; 351 }; 352 353 BITMASK(UUID_FLASH_ONLY, struct uuid_entry, flags, 0, 1); 354 355 #include "journal.h" 356 #include "stats.h" 357 struct search; 358 struct btree; 359 struct keybuf; 360 361 struct keybuf_key { 362 struct rb_node node; 363 BKEY_PADDED(key); 364 void *private; 365 }; 366 367 typedef bool (keybuf_pred_fn)(struct keybuf *, struct bkey *); 368 369 struct keybuf { 370 keybuf_pred_fn *key_predicate; 371 372 struct bkey last_scanned; 373 spinlock_t lock; 374 375 /* 376 * Beginning and end of range in rb tree - so that we can skip taking 377 * lock and checking the rb tree when we need to check for overlapping 378 * keys. 379 */ 380 struct bkey start; 381 struct bkey end; 382 383 struct rb_root keys; 384 385 #define KEYBUF_NR 100 386 DECLARE_ARRAY_ALLOCATOR(struct keybuf_key, freelist, KEYBUF_NR); 387 }; 388 389 struct bio_split_pool { 390 struct bio_set *bio_split; 391 mempool_t *bio_split_hook; 392 }; 393 394 struct bio_split_hook { 395 struct closure cl; 396 struct bio_split_pool *p; 397 struct bio *bio; 398 bio_end_io_t *bi_end_io; 399 void *bi_private; 400 }; 401 402 struct bcache_device { 403 struct closure cl; 404 405 struct kobject kobj; 406 407 struct cache_set *c; 408 unsigned id; 409 #define BCACHEDEVNAME_SIZE 12 410 char name[BCACHEDEVNAME_SIZE]; 411 412 struct gendisk *disk; 413 414 /* If nonzero, we're closing */ 415 atomic_t closing; 416 417 /* If nonzero, we're detaching/unregistering from cache set */ 418 atomic_t detaching; 419 420 atomic_long_t sectors_dirty; 421 unsigned long sectors_dirty_gc; 422 unsigned long sectors_dirty_last; 423 long sectors_dirty_derivative; 424 425 mempool_t *unaligned_bvec; 426 struct bio_set *bio_split; 427 428 unsigned data_csum:1; 429 430 int (*cache_miss)(struct btree *, struct search *, 431 struct bio *, unsigned); 432 int (*ioctl) (struct bcache_device *, fmode_t, unsigned, unsigned long); 433 434 struct bio_split_pool bio_split_hook; 435 }; 436 437 struct io { 438 /* Used to track sequential IO so it can be skipped */ 439 struct hlist_node hash; 440 struct list_head lru; 441 442 unsigned long jiffies; 443 unsigned sequential; 444 sector_t last; 445 }; 446 447 struct cached_dev { 448 struct list_head list; 449 struct bcache_device disk; 450 struct block_device *bdev; 451 452 struct cache_sb sb; 453 struct bio sb_bio; 454 struct bio_vec sb_bv[1]; 455 struct closure_with_waitlist sb_write; 456 457 /* Refcount on the cache set. Always nonzero when we're caching. */ 458 atomic_t count; 459 struct work_struct detach; 460 461 /* 462 * Device might not be running if it's dirty and the cache set hasn't 463 * showed up yet. 464 */ 465 atomic_t running; 466 467 /* 468 * Writes take a shared lock from start to finish; scanning for dirty 469 * data to refill the rb tree requires an exclusive lock. 470 */ 471 struct rw_semaphore writeback_lock; 472 473 /* 474 * Nonzero, and writeback has a refcount (d->count), iff there is dirty 475 * data in the cache. Protected by writeback_lock; must have an 476 * shared lock to set and exclusive lock to clear. 477 */ 478 atomic_t has_dirty; 479 480 struct ratelimit writeback_rate; 481 struct delayed_work writeback_rate_update; 482 483 /* 484 * Internal to the writeback code, so read_dirty() can keep track of 485 * where it's at. 486 */ 487 sector_t last_read; 488 489 /* Number of writeback bios in flight */ 490 atomic_t in_flight; 491 struct closure_with_timer writeback; 492 struct closure_waitlist writeback_wait; 493 494 struct keybuf writeback_keys; 495 496 /* For tracking sequential IO */ 497 #define RECENT_IO_BITS 7 498 #define RECENT_IO (1 << RECENT_IO_BITS) 499 struct io io[RECENT_IO]; 500 struct hlist_head io_hash[RECENT_IO + 1]; 501 struct list_head io_lru; 502 spinlock_t io_lock; 503 504 struct cache_accounting accounting; 505 506 /* The rest of this all shows up in sysfs */ 507 unsigned sequential_cutoff; 508 unsigned readahead; 509 510 unsigned sequential_merge:1; 511 unsigned verify:1; 512 513 unsigned writeback_metadata:1; 514 unsigned writeback_running:1; 515 unsigned char writeback_percent; 516 unsigned writeback_delay; 517 518 int writeback_rate_change; 519 int64_t writeback_rate_derivative; 520 uint64_t writeback_rate_target; 521 522 unsigned writeback_rate_update_seconds; 523 unsigned writeback_rate_d_term; 524 unsigned writeback_rate_p_term_inverse; 525 unsigned writeback_rate_d_smooth; 526 }; 527 528 enum alloc_watermarks { 529 WATERMARK_PRIO, 530 WATERMARK_METADATA, 531 WATERMARK_MOVINGGC, 532 WATERMARK_NONE, 533 WATERMARK_MAX 534 }; 535 536 struct cache { 537 struct cache_set *set; 538 struct cache_sb sb; 539 struct bio sb_bio; 540 struct bio_vec sb_bv[1]; 541 542 struct kobject kobj; 543 struct block_device *bdev; 544 545 unsigned watermark[WATERMARK_MAX]; 546 547 struct closure alloc; 548 struct workqueue_struct *alloc_workqueue; 549 550 struct closure prio; 551 struct prio_set *disk_buckets; 552 553 /* 554 * When allocating new buckets, prio_write() gets first dibs - since we 555 * may not be allocate at all without writing priorities and gens. 556 * prio_buckets[] contains the last buckets we wrote priorities to (so 557 * gc can mark them as metadata), prio_next[] contains the buckets 558 * allocated for the next prio write. 559 */ 560 uint64_t *prio_buckets; 561 uint64_t *prio_last_buckets; 562 563 /* 564 * free: Buckets that are ready to be used 565 * 566 * free_inc: Incoming buckets - these are buckets that currently have 567 * cached data in them, and we can't reuse them until after we write 568 * their new gen to disk. After prio_write() finishes writing the new 569 * gens/prios, they'll be moved to the free list (and possibly discarded 570 * in the process) 571 * 572 * unused: GC found nothing pointing into these buckets (possibly 573 * because all the data they contained was overwritten), so we only 574 * need to discard them before they can be moved to the free list. 575 */ 576 DECLARE_FIFO(long, free); 577 DECLARE_FIFO(long, free_inc); 578 DECLARE_FIFO(long, unused); 579 580 size_t fifo_last_bucket; 581 582 /* Allocation stuff: */ 583 struct bucket *buckets; 584 585 DECLARE_HEAP(struct bucket *, heap); 586 587 /* 588 * max(gen - disk_gen) for all buckets. When it gets too big we have to 589 * call prio_write() to keep gens from wrapping. 590 */ 591 uint8_t need_save_prio; 592 unsigned gc_move_threshold; 593 594 /* 595 * If nonzero, we know we aren't going to find any buckets to invalidate 596 * until a gc finishes - otherwise we could pointlessly burn a ton of 597 * cpu 598 */ 599 unsigned invalidate_needs_gc:1; 600 601 bool discard; /* Get rid of? */ 602 603 /* 604 * We preallocate structs for issuing discards to buckets, and keep them 605 * on this list when they're not in use; do_discard() issues discards 606 * whenever there's work to do and is called by free_some_buckets() and 607 * when a discard finishes. 608 */ 609 atomic_t discards_in_flight; 610 struct list_head discards; 611 612 struct journal_device journal; 613 614 /* The rest of this all shows up in sysfs */ 615 #define IO_ERROR_SHIFT 20 616 atomic_t io_errors; 617 atomic_t io_count; 618 619 atomic_long_t meta_sectors_written; 620 atomic_long_t btree_sectors_written; 621 atomic_long_t sectors_written; 622 623 struct bio_split_pool bio_split_hook; 624 }; 625 626 struct gc_stat { 627 size_t nodes; 628 size_t key_bytes; 629 630 size_t nkeys; 631 uint64_t data; /* sectors */ 632 uint64_t dirty; /* sectors */ 633 unsigned in_use; /* percent */ 634 }; 635 636 /* 637 * Flag bits, for how the cache set is shutting down, and what phase it's at: 638 * 639 * CACHE_SET_UNREGISTERING means we're not just shutting down, we're detaching 640 * all the backing devices first (their cached data gets invalidated, and they 641 * won't automatically reattach). 642 * 643 * CACHE_SET_STOPPING always gets set first when we're closing down a cache set; 644 * we'll continue to run normally for awhile with CACHE_SET_STOPPING set (i.e. 645 * flushing dirty data). 646 * 647 * CACHE_SET_STOPPING_2 gets set at the last phase, when it's time to shut down the 648 * allocation thread. 649 */ 650 #define CACHE_SET_UNREGISTERING 0 651 #define CACHE_SET_STOPPING 1 652 #define CACHE_SET_STOPPING_2 2 653 654 struct cache_set { 655 struct closure cl; 656 657 struct list_head list; 658 struct kobject kobj; 659 struct kobject internal; 660 struct dentry *debug; 661 struct cache_accounting accounting; 662 663 unsigned long flags; 664 665 struct cache_sb sb; 666 667 struct cache *cache[MAX_CACHES_PER_SET]; 668 struct cache *cache_by_alloc[MAX_CACHES_PER_SET]; 669 int caches_loaded; 670 671 struct bcache_device **devices; 672 struct list_head cached_devs; 673 uint64_t cached_dev_sectors; 674 struct closure caching; 675 676 struct closure_with_waitlist sb_write; 677 678 mempool_t *search; 679 mempool_t *bio_meta; 680 struct bio_set *bio_split; 681 682 /* For the btree cache */ 683 struct shrinker shrink; 684 685 /* For the allocator itself */ 686 wait_queue_head_t alloc_wait; 687 688 /* For the btree cache and anything allocation related */ 689 struct mutex bucket_lock; 690 691 /* log2(bucket_size), in sectors */ 692 unsigned short bucket_bits; 693 694 /* log2(block_size), in sectors */ 695 unsigned short block_bits; 696 697 /* 698 * Default number of pages for a new btree node - may be less than a 699 * full bucket 700 */ 701 unsigned btree_pages; 702 703 /* 704 * Lists of struct btrees; lru is the list for structs that have memory 705 * allocated for actual btree node, freed is for structs that do not. 706 * 707 * We never free a struct btree, except on shutdown - we just put it on 708 * the btree_cache_freed list and reuse it later. This simplifies the 709 * code, and it doesn't cost us much memory as the memory usage is 710 * dominated by buffers that hold the actual btree node data and those 711 * can be freed - and the number of struct btrees allocated is 712 * effectively bounded. 713 * 714 * btree_cache_freeable effectively is a small cache - we use it because 715 * high order page allocations can be rather expensive, and it's quite 716 * common to delete and allocate btree nodes in quick succession. It 717 * should never grow past ~2-3 nodes in practice. 718 */ 719 struct list_head btree_cache; 720 struct list_head btree_cache_freeable; 721 struct list_head btree_cache_freed; 722 723 /* Number of elements in btree_cache + btree_cache_freeable lists */ 724 unsigned bucket_cache_used; 725 726 /* 727 * If we need to allocate memory for a new btree node and that 728 * allocation fails, we can cannibalize another node in the btree cache 729 * to satisfy the allocation. However, only one thread can be doing this 730 * at a time, for obvious reasons - try_harder and try_wait are 731 * basically a lock for this that we can wait on asynchronously. The 732 * btree_root() macro releases the lock when it returns. 733 */ 734 struct closure *try_harder; 735 struct closure_waitlist try_wait; 736 uint64_t try_harder_start; 737 738 /* 739 * When we free a btree node, we increment the gen of the bucket the 740 * node is in - but we can't rewrite the prios and gens until we 741 * finished whatever it is we were doing, otherwise after a crash the 742 * btree node would be freed but for say a split, we might not have the 743 * pointers to the new nodes inserted into the btree yet. 744 * 745 * This is a refcount that blocks prio_write() until the new keys are 746 * written. 747 */ 748 atomic_t prio_blocked; 749 struct closure_waitlist bucket_wait; 750 751 /* 752 * For any bio we don't skip we subtract the number of sectors from 753 * rescale; when it hits 0 we rescale all the bucket priorities. 754 */ 755 atomic_t rescale; 756 /* 757 * When we invalidate buckets, we use both the priority and the amount 758 * of good data to determine which buckets to reuse first - to weight 759 * those together consistently we keep track of the smallest nonzero 760 * priority of any bucket. 761 */ 762 uint16_t min_prio; 763 764 /* 765 * max(gen - gc_gen) for all buckets. When it gets too big we have to gc 766 * to keep gens from wrapping around. 767 */ 768 uint8_t need_gc; 769 struct gc_stat gc_stats; 770 size_t nbuckets; 771 772 struct closure_with_waitlist gc; 773 /* Where in the btree gc currently is */ 774 struct bkey gc_done; 775 776 /* 777 * The allocation code needs gc_mark in struct bucket to be correct, but 778 * it's not while a gc is in progress. Protected by bucket_lock. 779 */ 780 int gc_mark_valid; 781 782 /* Counts how many sectors bio_insert has added to the cache */ 783 atomic_t sectors_to_gc; 784 785 struct closure moving_gc; 786 struct closure_waitlist moving_gc_wait; 787 struct keybuf moving_gc_keys; 788 /* Number of moving GC bios in flight */ 789 atomic_t in_flight; 790 791 struct btree *root; 792 793 #ifdef CONFIG_BCACHE_DEBUG 794 struct btree *verify_data; 795 struct mutex verify_lock; 796 #endif 797 798 unsigned nr_uuids; 799 struct uuid_entry *uuids; 800 BKEY_PADDED(uuid_bucket); 801 struct closure_with_waitlist uuid_write; 802 803 /* 804 * A btree node on disk could have too many bsets for an iterator to fit 805 * on the stack - this is a single element mempool for btree_read_work() 806 */ 807 struct mutex fill_lock; 808 struct btree_iter *fill_iter; 809 810 /* 811 * btree_sort() is a merge sort and requires temporary space - single 812 * element mempool 813 */ 814 struct mutex sort_lock; 815 struct bset *sort; 816 817 /* List of buckets we're currently writing data to */ 818 struct list_head data_buckets; 819 spinlock_t data_bucket_lock; 820 821 struct journal journal; 822 823 #define CONGESTED_MAX 1024 824 unsigned congested_last_us; 825 atomic_t congested; 826 827 /* The rest of this all shows up in sysfs */ 828 unsigned congested_read_threshold_us; 829 unsigned congested_write_threshold_us; 830 831 spinlock_t sort_time_lock; 832 struct time_stats sort_time; 833 struct time_stats btree_gc_time; 834 struct time_stats btree_split_time; 835 spinlock_t btree_read_time_lock; 836 struct time_stats btree_read_time; 837 struct time_stats try_harder_time; 838 839 atomic_long_t cache_read_races; 840 atomic_long_t writeback_keys_done; 841 atomic_long_t writeback_keys_failed; 842 unsigned error_limit; 843 unsigned error_decay; 844 unsigned short journal_delay_ms; 845 unsigned verify:1; 846 unsigned key_merging_disabled:1; 847 unsigned gc_always_rewrite:1; 848 unsigned shrinker_disabled:1; 849 unsigned copy_gc_enabled:1; 850 851 #define BUCKET_HASH_BITS 12 852 struct hlist_head bucket_hash[1 << BUCKET_HASH_BITS]; 853 }; 854 855 static inline bool key_merging_disabled(struct cache_set *c) 856 { 857 #ifdef CONFIG_BCACHE_DEBUG 858 return c->key_merging_disabled; 859 #else 860 return 0; 861 #endif 862 } 863 864 struct bbio { 865 unsigned submit_time_us; 866 union { 867 struct bkey key; 868 uint64_t _pad[3]; 869 /* 870 * We only need pad = 3 here because we only ever carry around a 871 * single pointer - i.e. the pointer we're doing io to/from. 872 */ 873 }; 874 struct bio bio; 875 }; 876 877 static inline unsigned local_clock_us(void) 878 { 879 return local_clock() >> 10; 880 } 881 882 #define MAX_BSETS 4U 883 884 #define BTREE_PRIO USHRT_MAX 885 #define INITIAL_PRIO 32768 886 887 #define btree_bytes(c) ((c)->btree_pages * PAGE_SIZE) 888 #define btree_blocks(b) \ 889 ((unsigned) (KEY_SIZE(&b->key) >> (b)->c->block_bits)) 890 891 #define btree_default_blocks(c) \ 892 ((unsigned) ((PAGE_SECTORS * (c)->btree_pages) >> (c)->block_bits)) 893 894 #define bucket_pages(c) ((c)->sb.bucket_size / PAGE_SECTORS) 895 #define bucket_bytes(c) ((c)->sb.bucket_size << 9) 896 #define block_bytes(c) ((c)->sb.block_size << 9) 897 898 #define __set_bytes(i, k) (sizeof(*(i)) + (k) * sizeof(uint64_t)) 899 #define set_bytes(i) __set_bytes(i, i->keys) 900 901 #define __set_blocks(i, k, c) DIV_ROUND_UP(__set_bytes(i, k), block_bytes(c)) 902 #define set_blocks(i, c) __set_blocks(i, (i)->keys, c) 903 904 #define node(i, j) ((struct bkey *) ((i)->d + (j))) 905 #define end(i) node(i, (i)->keys) 906 907 #define index(i, b) \ 908 ((size_t) (((void *) i - (void *) (b)->sets[0].data) / \ 909 block_bytes(b->c))) 910 911 #define btree_data_space(b) (PAGE_SIZE << (b)->page_order) 912 913 #define prios_per_bucket(c) \ 914 ((bucket_bytes(c) - sizeof(struct prio_set)) / \ 915 sizeof(struct bucket_disk)) 916 #define prio_buckets(c) \ 917 DIV_ROUND_UP((size_t) (c)->sb.nbuckets, prios_per_bucket(c)) 918 919 #define JSET_MAGIC 0x245235c1a3625032ULL 920 #define PSET_MAGIC 0x6750e15f87337f91ULL 921 #define BSET_MAGIC 0x90135c78b99e07f5ULL 922 923 #define jset_magic(c) ((c)->sb.set_magic ^ JSET_MAGIC) 924 #define pset_magic(c) ((c)->sb.set_magic ^ PSET_MAGIC) 925 #define bset_magic(c) ((c)->sb.set_magic ^ BSET_MAGIC) 926 927 /* Bkey fields: all units are in sectors */ 928 929 #define KEY_FIELD(name, field, offset, size) \ 930 BITMASK(name, struct bkey, field, offset, size) 931 932 #define PTR_FIELD(name, offset, size) \ 933 static inline uint64_t name(const struct bkey *k, unsigned i) \ 934 { return (k->ptr[i] >> offset) & ~(((uint64_t) ~0) << size); } \ 935 \ 936 static inline void SET_##name(struct bkey *k, unsigned i, uint64_t v)\ 937 { \ 938 k->ptr[i] &= ~(~((uint64_t) ~0 << size) << offset); \ 939 k->ptr[i] |= v << offset; \ 940 } 941 942 KEY_FIELD(KEY_PTRS, high, 60, 3) 943 KEY_FIELD(HEADER_SIZE, high, 58, 2) 944 KEY_FIELD(KEY_CSUM, high, 56, 2) 945 KEY_FIELD(KEY_PINNED, high, 55, 1) 946 KEY_FIELD(KEY_DIRTY, high, 36, 1) 947 948 KEY_FIELD(KEY_SIZE, high, 20, 16) 949 KEY_FIELD(KEY_INODE, high, 0, 20) 950 951 /* Next time I change the on disk format, KEY_OFFSET() won't be 64 bits */ 952 953 static inline uint64_t KEY_OFFSET(const struct bkey *k) 954 { 955 return k->low; 956 } 957 958 static inline void SET_KEY_OFFSET(struct bkey *k, uint64_t v) 959 { 960 k->low = v; 961 } 962 963 PTR_FIELD(PTR_DEV, 51, 12) 964 PTR_FIELD(PTR_OFFSET, 8, 43) 965 PTR_FIELD(PTR_GEN, 0, 8) 966 967 #define PTR_CHECK_DEV ((1 << 12) - 1) 968 969 #define PTR(gen, offset, dev) \ 970 ((((uint64_t) dev) << 51) | ((uint64_t) offset) << 8 | gen) 971 972 static inline size_t sector_to_bucket(struct cache_set *c, sector_t s) 973 { 974 return s >> c->bucket_bits; 975 } 976 977 static inline sector_t bucket_to_sector(struct cache_set *c, size_t b) 978 { 979 return ((sector_t) b) << c->bucket_bits; 980 } 981 982 static inline sector_t bucket_remainder(struct cache_set *c, sector_t s) 983 { 984 return s & (c->sb.bucket_size - 1); 985 } 986 987 static inline struct cache *PTR_CACHE(struct cache_set *c, 988 const struct bkey *k, 989 unsigned ptr) 990 { 991 return c->cache[PTR_DEV(k, ptr)]; 992 } 993 994 static inline size_t PTR_BUCKET_NR(struct cache_set *c, 995 const struct bkey *k, 996 unsigned ptr) 997 { 998 return sector_to_bucket(c, PTR_OFFSET(k, ptr)); 999 } 1000 1001 static inline struct bucket *PTR_BUCKET(struct cache_set *c, 1002 const struct bkey *k, 1003 unsigned ptr) 1004 { 1005 return PTR_CACHE(c, k, ptr)->buckets + PTR_BUCKET_NR(c, k, ptr); 1006 } 1007 1008 /* Btree key macros */ 1009 1010 /* 1011 * The high bit being set is a relic from when we used it to do binary 1012 * searches - it told you where a key started. It's not used anymore, 1013 * and can probably be safely dropped. 1014 */ 1015 #define KEY(dev, sector, len) (struct bkey) \ 1016 { \ 1017 .high = (1ULL << 63) | ((uint64_t) (len) << 20) | (dev), \ 1018 .low = (sector) \ 1019 } 1020 1021 static inline void bkey_init(struct bkey *k) 1022 { 1023 *k = KEY(0, 0, 0); 1024 } 1025 1026 #define KEY_START(k) (KEY_OFFSET(k) - KEY_SIZE(k)) 1027 #define START_KEY(k) KEY(KEY_INODE(k), KEY_START(k), 0) 1028 #define MAX_KEY KEY(~(~0 << 20), ((uint64_t) ~0) >> 1, 0) 1029 #define ZERO_KEY KEY(0, 0, 0) 1030 1031 /* 1032 * This is used for various on disk data structures - cache_sb, prio_set, bset, 1033 * jset: The checksum is _always_ the first 8 bytes of these structs 1034 */ 1035 #define csum_set(i) \ 1036 crc64(((void *) (i)) + sizeof(uint64_t), \ 1037 ((void *) end(i)) - (((void *) (i)) + sizeof(uint64_t))) 1038 1039 /* Error handling macros */ 1040 1041 #define btree_bug(b, ...) \ 1042 do { \ 1043 if (bch_cache_set_error((b)->c, __VA_ARGS__)) \ 1044 dump_stack(); \ 1045 } while (0) 1046 1047 #define cache_bug(c, ...) \ 1048 do { \ 1049 if (bch_cache_set_error(c, __VA_ARGS__)) \ 1050 dump_stack(); \ 1051 } while (0) 1052 1053 #define btree_bug_on(cond, b, ...) \ 1054 do { \ 1055 if (cond) \ 1056 btree_bug(b, __VA_ARGS__); \ 1057 } while (0) 1058 1059 #define cache_bug_on(cond, c, ...) \ 1060 do { \ 1061 if (cond) \ 1062 cache_bug(c, __VA_ARGS__); \ 1063 } while (0) 1064 1065 #define cache_set_err_on(cond, c, ...) \ 1066 do { \ 1067 if (cond) \ 1068 bch_cache_set_error(c, __VA_ARGS__); \ 1069 } while (0) 1070 1071 /* Looping macros */ 1072 1073 #define for_each_cache(ca, cs, iter) \ 1074 for (iter = 0; ca = cs->cache[iter], iter < (cs)->sb.nr_in_set; iter++) 1075 1076 #define for_each_bucket(b, ca) \ 1077 for (b = (ca)->buckets + (ca)->sb.first_bucket; \ 1078 b < (ca)->buckets + (ca)->sb.nbuckets; b++) 1079 1080 static inline void __bkey_put(struct cache_set *c, struct bkey *k) 1081 { 1082 unsigned i; 1083 1084 for (i = 0; i < KEY_PTRS(k); i++) 1085 atomic_dec_bug(&PTR_BUCKET(c, k, i)->pin); 1086 } 1087 1088 /* Blktrace macros */ 1089 1090 #define blktrace_msg(c, fmt, ...) \ 1091 do { \ 1092 struct request_queue *q = bdev_get_queue(c->bdev); \ 1093 if (q) \ 1094 blk_add_trace_msg(q, fmt, ##__VA_ARGS__); \ 1095 } while (0) 1096 1097 #define blktrace_msg_all(s, fmt, ...) \ 1098 do { \ 1099 struct cache *_c; \ 1100 unsigned i; \ 1101 for_each_cache(_c, (s), i) \ 1102 blktrace_msg(_c, fmt, ##__VA_ARGS__); \ 1103 } while (0) 1104 1105 static inline void cached_dev_put(struct cached_dev *dc) 1106 { 1107 if (atomic_dec_and_test(&dc->count)) 1108 schedule_work(&dc->detach); 1109 } 1110 1111 static inline bool cached_dev_get(struct cached_dev *dc) 1112 { 1113 if (!atomic_inc_not_zero(&dc->count)) 1114 return false; 1115 1116 /* Paired with the mb in cached_dev_attach */ 1117 smp_mb__after_atomic_inc(); 1118 return true; 1119 } 1120 1121 /* 1122 * bucket_gc_gen() returns the difference between the bucket's current gen and 1123 * the oldest gen of any pointer into that bucket in the btree (last_gc). 1124 * 1125 * bucket_disk_gen() returns the difference between the current gen and the gen 1126 * on disk; they're both used to make sure gens don't wrap around. 1127 */ 1128 1129 static inline uint8_t bucket_gc_gen(struct bucket *b) 1130 { 1131 return b->gen - b->last_gc; 1132 } 1133 1134 static inline uint8_t bucket_disk_gen(struct bucket *b) 1135 { 1136 return b->gen - b->disk_gen; 1137 } 1138 1139 #define BUCKET_GC_GEN_MAX 96U 1140 #define BUCKET_DISK_GEN_MAX 64U 1141 1142 #define kobj_attribute_write(n, fn) \ 1143 static struct kobj_attribute ksysfs_##n = __ATTR(n, S_IWUSR, NULL, fn) 1144 1145 #define kobj_attribute_rw(n, show, store) \ 1146 static struct kobj_attribute ksysfs_##n = \ 1147 __ATTR(n, S_IWUSR|S_IRUSR, show, store) 1148 1149 /* Forward declarations */ 1150 1151 void bch_writeback_queue(struct cached_dev *); 1152 void bch_writeback_add(struct cached_dev *, unsigned); 1153 1154 void bch_count_io_errors(struct cache *, int, const char *); 1155 void bch_bbio_count_io_errors(struct cache_set *, struct bio *, 1156 int, const char *); 1157 void bch_bbio_endio(struct cache_set *, struct bio *, int, const char *); 1158 void bch_bbio_free(struct bio *, struct cache_set *); 1159 struct bio *bch_bbio_alloc(struct cache_set *); 1160 1161 struct bio *bch_bio_split(struct bio *, int, gfp_t, struct bio_set *); 1162 void bch_generic_make_request(struct bio *, struct bio_split_pool *); 1163 void __bch_submit_bbio(struct bio *, struct cache_set *); 1164 void bch_submit_bbio(struct bio *, struct cache_set *, struct bkey *, unsigned); 1165 1166 uint8_t bch_inc_gen(struct cache *, struct bucket *); 1167 void bch_rescale_priorities(struct cache_set *, int); 1168 bool bch_bucket_add_unused(struct cache *, struct bucket *); 1169 void bch_allocator_thread(struct closure *); 1170 1171 long bch_bucket_alloc(struct cache *, unsigned, struct closure *); 1172 void bch_bucket_free(struct cache_set *, struct bkey *); 1173 1174 int __bch_bucket_alloc_set(struct cache_set *, unsigned, 1175 struct bkey *, int, struct closure *); 1176 int bch_bucket_alloc_set(struct cache_set *, unsigned, 1177 struct bkey *, int, struct closure *); 1178 1179 __printf(2, 3) 1180 bool bch_cache_set_error(struct cache_set *, const char *, ...); 1181 1182 void bch_prio_write(struct cache *); 1183 void bch_write_bdev_super(struct cached_dev *, struct closure *); 1184 1185 extern struct workqueue_struct *bcache_wq, *bch_gc_wq; 1186 extern const char * const bch_cache_modes[]; 1187 extern struct mutex bch_register_lock; 1188 extern struct list_head bch_cache_sets; 1189 1190 extern struct kobj_type bch_cached_dev_ktype; 1191 extern struct kobj_type bch_flash_dev_ktype; 1192 extern struct kobj_type bch_cache_set_ktype; 1193 extern struct kobj_type bch_cache_set_internal_ktype; 1194 extern struct kobj_type bch_cache_ktype; 1195 1196 void bch_cached_dev_release(struct kobject *); 1197 void bch_flash_dev_release(struct kobject *); 1198 void bch_cache_set_release(struct kobject *); 1199 void bch_cache_release(struct kobject *); 1200 1201 int bch_uuid_write(struct cache_set *); 1202 void bcache_write_super(struct cache_set *); 1203 1204 int bch_flash_dev_create(struct cache_set *c, uint64_t size); 1205 1206 int bch_cached_dev_attach(struct cached_dev *, struct cache_set *); 1207 void bch_cached_dev_detach(struct cached_dev *); 1208 void bch_cached_dev_run(struct cached_dev *); 1209 void bcache_device_stop(struct bcache_device *); 1210 1211 void bch_cache_set_unregister(struct cache_set *); 1212 void bch_cache_set_stop(struct cache_set *); 1213 1214 struct cache_set *bch_cache_set_alloc(struct cache_sb *); 1215 void bch_btree_cache_free(struct cache_set *); 1216 int bch_btree_cache_alloc(struct cache_set *); 1217 void bch_writeback_init_cached_dev(struct cached_dev *); 1218 void bch_moving_init_cache_set(struct cache_set *); 1219 1220 void bch_cache_allocator_exit(struct cache *ca); 1221 int bch_cache_allocator_init(struct cache *ca); 1222 1223 void bch_debug_exit(void); 1224 int bch_debug_init(struct kobject *); 1225 void bch_writeback_exit(void); 1226 int bch_writeback_init(void); 1227 void bch_request_exit(void); 1228 int bch_request_init(void); 1229 void bch_btree_exit(void); 1230 int bch_btree_init(void); 1231 1232 #endif /* _BCACHE_H */ 1233