1cafe5635SKent Overstreet /* 2cafe5635SKent Overstreet * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com> 3cafe5635SKent Overstreet * 4cafe5635SKent Overstreet * Uses a block device as cache for other block devices; optimized for SSDs. 5cafe5635SKent Overstreet * All allocation is done in buckets, which should match the erase block size 6cafe5635SKent Overstreet * of the device. 7cafe5635SKent Overstreet * 8cafe5635SKent Overstreet * Buckets containing cached data are kept on a heap sorted by priority; 9cafe5635SKent Overstreet * bucket priority is increased on cache hit, and periodically all the buckets 10cafe5635SKent Overstreet * on the heap have their priority scaled down. This currently is just used as 11cafe5635SKent Overstreet * an LRU but in the future should allow for more intelligent heuristics. 12cafe5635SKent Overstreet * 13cafe5635SKent Overstreet * Buckets have an 8 bit counter; freeing is accomplished by incrementing the 14cafe5635SKent Overstreet * counter. Garbage collection is used to remove stale pointers. 15cafe5635SKent Overstreet * 16cafe5635SKent Overstreet * Indexing is done via a btree; nodes are not necessarily fully sorted, rather 17cafe5635SKent Overstreet * as keys are inserted we only sort the pages that have not yet been written. 18cafe5635SKent Overstreet * When garbage collection is run, we resort the entire node. 19cafe5635SKent Overstreet * 20cafe5635SKent Overstreet * All configuration is done via sysfs; see Documentation/bcache.txt. 21cafe5635SKent Overstreet */ 22cafe5635SKent Overstreet 23cafe5635SKent Overstreet #include "bcache.h" 24cafe5635SKent Overstreet #include "btree.h" 25cafe5635SKent Overstreet #include "debug.h" 26*65d45231SKent Overstreet #include "extents.h" 27279afbadSKent Overstreet #include "writeback.h" 28cafe5635SKent Overstreet 29cafe5635SKent Overstreet #include <linux/slab.h> 30cafe5635SKent Overstreet #include <linux/bitops.h> 3172a44517SKent Overstreet #include <linux/freezer.h> 32cafe5635SKent Overstreet #include <linux/hash.h> 3372a44517SKent Overstreet #include <linux/kthread.h> 34cd953ed0SGeert Uytterhoeven #include <linux/prefetch.h> 35cafe5635SKent Overstreet #include <linux/random.h> 36cafe5635SKent Overstreet #include <linux/rcupdate.h> 37cafe5635SKent Overstreet #include <trace/events/bcache.h> 38cafe5635SKent Overstreet 39cafe5635SKent Overstreet /* 40cafe5635SKent Overstreet * Todo: 41cafe5635SKent Overstreet * register_bcache: Return errors out to userspace correctly 42cafe5635SKent Overstreet * 43cafe5635SKent Overstreet * Writeback: don't undirty key until after a cache flush 44cafe5635SKent Overstreet * 45cafe5635SKent Overstreet * Create an iterator for key pointers 46cafe5635SKent Overstreet * 47cafe5635SKent Overstreet * On btree write error, mark bucket such that it won't be freed from the cache 48cafe5635SKent Overstreet * 49cafe5635SKent Overstreet * Journalling: 50cafe5635SKent Overstreet * Check for bad keys in replay 51cafe5635SKent Overstreet * Propagate barriers 52cafe5635SKent Overstreet * Refcount journal entries in journal_replay 53cafe5635SKent Overstreet * 54cafe5635SKent Overstreet * Garbage collection: 55cafe5635SKent Overstreet * Finish incremental gc 56cafe5635SKent Overstreet * Gc should free old UUIDs, data for invalid UUIDs 57cafe5635SKent Overstreet * 58cafe5635SKent Overstreet * Provide a way to list backing device UUIDs we have data cached for, and 59cafe5635SKent Overstreet * probably how long it's been since we've seen them, and a way to invalidate 60cafe5635SKent Overstreet * dirty data for devices that will never be attached again 61cafe5635SKent Overstreet * 62cafe5635SKent Overstreet * Keep 1 min/5 min/15 min statistics of how busy a block device has been, so 63cafe5635SKent Overstreet * that based on that and how much dirty data we have we can keep writeback 64cafe5635SKent Overstreet * from being starved 65cafe5635SKent Overstreet * 66cafe5635SKent Overstreet * Add a tracepoint or somesuch to watch for writeback starvation 67cafe5635SKent Overstreet * 68cafe5635SKent Overstreet * When btree depth > 1 and splitting an interior node, we have to make sure 69cafe5635SKent Overstreet * alloc_bucket() cannot fail. This should be true but is not completely 70cafe5635SKent Overstreet * obvious. 71cafe5635SKent Overstreet * 72cafe5635SKent Overstreet * Make sure all allocations get charged to the root cgroup 73cafe5635SKent Overstreet * 74cafe5635SKent Overstreet * Plugging? 75cafe5635SKent Overstreet * 76cafe5635SKent Overstreet * If data write is less than hard sector size of ssd, round up offset in open 77cafe5635SKent Overstreet * bucket to the next whole sector 78cafe5635SKent Overstreet * 79cafe5635SKent Overstreet * Also lookup by cgroup in get_open_bucket() 80cafe5635SKent Overstreet * 81cafe5635SKent Overstreet * Superblock needs to be fleshed out for multiple cache devices 82cafe5635SKent Overstreet * 83cafe5635SKent Overstreet * Add a sysfs tunable for the number of writeback IOs in flight 84cafe5635SKent Overstreet * 85cafe5635SKent Overstreet * Add a sysfs tunable for the number of open data buckets 86cafe5635SKent Overstreet * 87cafe5635SKent Overstreet * IO tracking: Can we track when one process is doing io on behalf of another? 88cafe5635SKent Overstreet * IO tracking: Don't use just an average, weigh more recent stuff higher 89cafe5635SKent Overstreet * 90cafe5635SKent Overstreet * Test module load/unload 91cafe5635SKent Overstreet */ 92cafe5635SKent Overstreet 93df8e8970SKent Overstreet enum { 94df8e8970SKent Overstreet BTREE_INSERT_STATUS_INSERT, 95df8e8970SKent Overstreet BTREE_INSERT_STATUS_BACK_MERGE, 96df8e8970SKent Overstreet BTREE_INSERT_STATUS_OVERWROTE, 97df8e8970SKent Overstreet BTREE_INSERT_STATUS_FRONT_MERGE, 98df8e8970SKent Overstreet }; 99df8e8970SKent Overstreet 100cafe5635SKent Overstreet #define MAX_NEED_GC 64 101cafe5635SKent Overstreet #define MAX_SAVE_PRIO 72 102cafe5635SKent Overstreet 103cafe5635SKent Overstreet #define PTR_DIRTY_BIT (((uint64_t) 1 << 36)) 104cafe5635SKent Overstreet 105cafe5635SKent Overstreet #define PTR_HASH(c, k) \ 106cafe5635SKent Overstreet (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0)) 107cafe5635SKent Overstreet 108cafe5635SKent Overstreet static struct workqueue_struct *btree_io_wq; 109cafe5635SKent Overstreet 110df8e8970SKent Overstreet static inline bool should_split(struct btree *b) 111df8e8970SKent Overstreet { 112df8e8970SKent Overstreet struct bset *i = write_block(b); 113df8e8970SKent Overstreet return b->written >= btree_blocks(b) || 114ee811287SKent Overstreet (b->written + __set_blocks(i, i->keys + 15, block_bytes(b->c)) 115df8e8970SKent Overstreet > btree_blocks(b)); 116df8e8970SKent Overstreet } 117df8e8970SKent Overstreet 118df8e8970SKent Overstreet #define insert_lock(s, b) ((b)->level <= (s)->lock) 119df8e8970SKent Overstreet 120df8e8970SKent Overstreet /* 121df8e8970SKent Overstreet * These macros are for recursing down the btree - they handle the details of 122df8e8970SKent Overstreet * locking and looking up nodes in the cache for you. They're best treated as 123df8e8970SKent Overstreet * mere syntax when reading code that uses them. 124df8e8970SKent Overstreet * 125df8e8970SKent Overstreet * op->lock determines whether we take a read or a write lock at a given depth. 126df8e8970SKent Overstreet * If you've got a read lock and find that you need a write lock (i.e. you're 127df8e8970SKent Overstreet * going to have to split), set op->lock and return -EINTR; btree_root() will 128df8e8970SKent Overstreet * call you again and you'll have the correct lock. 129df8e8970SKent Overstreet */ 130df8e8970SKent Overstreet 131df8e8970SKent Overstreet /** 132df8e8970SKent Overstreet * btree - recurse down the btree on a specified key 133df8e8970SKent Overstreet * @fn: function to call, which will be passed the child node 134df8e8970SKent Overstreet * @key: key to recurse on 135df8e8970SKent Overstreet * @b: parent btree node 136df8e8970SKent Overstreet * @op: pointer to struct btree_op 137df8e8970SKent Overstreet */ 138df8e8970SKent Overstreet #define btree(fn, key, b, op, ...) \ 139df8e8970SKent Overstreet ({ \ 140df8e8970SKent Overstreet int _r, l = (b)->level - 1; \ 141df8e8970SKent Overstreet bool _w = l <= (op)->lock; \ 142df8e8970SKent Overstreet struct btree *_child = bch_btree_node_get((b)->c, key, l, _w); \ 143df8e8970SKent Overstreet if (!IS_ERR(_child)) { \ 144df8e8970SKent Overstreet _child->parent = (b); \ 145df8e8970SKent Overstreet _r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__); \ 146df8e8970SKent Overstreet rw_unlock(_w, _child); \ 147df8e8970SKent Overstreet } else \ 148df8e8970SKent Overstreet _r = PTR_ERR(_child); \ 149df8e8970SKent Overstreet _r; \ 150df8e8970SKent Overstreet }) 151df8e8970SKent Overstreet 152df8e8970SKent Overstreet /** 153df8e8970SKent Overstreet * btree_root - call a function on the root of the btree 154df8e8970SKent Overstreet * @fn: function to call, which will be passed the child node 155df8e8970SKent Overstreet * @c: cache set 156df8e8970SKent Overstreet * @op: pointer to struct btree_op 157df8e8970SKent Overstreet */ 158df8e8970SKent Overstreet #define btree_root(fn, c, op, ...) \ 159df8e8970SKent Overstreet ({ \ 160df8e8970SKent Overstreet int _r = -EINTR; \ 161df8e8970SKent Overstreet do { \ 162df8e8970SKent Overstreet struct btree *_b = (c)->root; \ 163df8e8970SKent Overstreet bool _w = insert_lock(op, _b); \ 164df8e8970SKent Overstreet rw_lock(_w, _b, _b->level); \ 165df8e8970SKent Overstreet if (_b == (c)->root && \ 166df8e8970SKent Overstreet _w == insert_lock(op, _b)) { \ 167df8e8970SKent Overstreet _b->parent = NULL; \ 168df8e8970SKent Overstreet _r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__); \ 169df8e8970SKent Overstreet } \ 170df8e8970SKent Overstreet rw_unlock(_w, _b); \ 17178365411SKent Overstreet if (_r == -EINTR) \ 17278365411SKent Overstreet schedule(); \ 173df8e8970SKent Overstreet bch_cannibalize_unlock(c); \ 174df8e8970SKent Overstreet if (_r == -ENOSPC) { \ 175df8e8970SKent Overstreet wait_event((c)->try_wait, \ 176df8e8970SKent Overstreet !(c)->try_harder); \ 177df8e8970SKent Overstreet _r = -EINTR; \ 178df8e8970SKent Overstreet } \ 179df8e8970SKent Overstreet } while (_r == -EINTR); \ 180df8e8970SKent Overstreet \ 18178365411SKent Overstreet finish_wait(&(c)->bucket_wait, &(op)->wait); \ 182df8e8970SKent Overstreet _r; \ 183df8e8970SKent Overstreet }) 184df8e8970SKent Overstreet 185cafe5635SKent Overstreet /* Btree key manipulation */ 186cafe5635SKent Overstreet 1873a3b6a4eSKent Overstreet void bkey_put(struct cache_set *c, struct bkey *k) 188e7c590ebSKent Overstreet { 189e7c590ebSKent Overstreet unsigned i; 190e7c590ebSKent Overstreet 191e7c590ebSKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 192e7c590ebSKent Overstreet if (ptr_available(c, k, i)) 193e7c590ebSKent Overstreet atomic_dec_bug(&PTR_BUCKET(c, k, i)->pin); 194e7c590ebSKent Overstreet } 195e7c590ebSKent Overstreet 196cafe5635SKent Overstreet /* Btree IO */ 197cafe5635SKent Overstreet 198cafe5635SKent Overstreet static uint64_t btree_csum_set(struct btree *b, struct bset *i) 199cafe5635SKent Overstreet { 200cafe5635SKent Overstreet uint64_t crc = b->key.ptr[0]; 201fafff81cSKent Overstreet void *data = (void *) i + 8, *end = bset_bkey_last(i); 202cafe5635SKent Overstreet 203169ef1cfSKent Overstreet crc = bch_crc64_update(crc, data, end - data); 204c19ed23aSKent Overstreet return crc ^ 0xffffffffffffffffULL; 205cafe5635SKent Overstreet } 206cafe5635SKent Overstreet 20778b77bf8SKent Overstreet void bch_btree_node_read_done(struct btree *b) 208cafe5635SKent Overstreet { 209cafe5635SKent Overstreet const char *err = "bad btree header"; 210ee811287SKent Overstreet struct bset *i = btree_bset_first(b); 21157943511SKent Overstreet struct btree_iter *iter; 212cafe5635SKent Overstreet 21357943511SKent Overstreet iter = mempool_alloc(b->c->fill_iter, GFP_NOWAIT); 21457943511SKent Overstreet iter->size = b->c->sb.bucket_size / b->c->sb.block_size; 215cafe5635SKent Overstreet iter->used = 0; 216cafe5635SKent Overstreet 217280481d0SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 218280481d0SKent Overstreet iter->b = b; 219280481d0SKent Overstreet #endif 220280481d0SKent Overstreet 22157943511SKent Overstreet if (!i->seq) 222cafe5635SKent Overstreet goto err; 223cafe5635SKent Overstreet 224cafe5635SKent Overstreet for (; 225cafe5635SKent Overstreet b->written < btree_blocks(b) && i->seq == b->sets[0].data->seq; 226cafe5635SKent Overstreet i = write_block(b)) { 227cafe5635SKent Overstreet err = "unsupported bset version"; 228cafe5635SKent Overstreet if (i->version > BCACHE_BSET_VERSION) 229cafe5635SKent Overstreet goto err; 230cafe5635SKent Overstreet 231cafe5635SKent Overstreet err = "bad btree header"; 232ee811287SKent Overstreet if (b->written + set_blocks(i, block_bytes(b->c)) > 233ee811287SKent Overstreet btree_blocks(b)) 234cafe5635SKent Overstreet goto err; 235cafe5635SKent Overstreet 236cafe5635SKent Overstreet err = "bad magic"; 23781ab4190SKent Overstreet if (i->magic != bset_magic(&b->c->sb)) 238cafe5635SKent Overstreet goto err; 239cafe5635SKent Overstreet 240cafe5635SKent Overstreet err = "bad checksum"; 241cafe5635SKent Overstreet switch (i->version) { 242cafe5635SKent Overstreet case 0: 243cafe5635SKent Overstreet if (i->csum != csum_set(i)) 244cafe5635SKent Overstreet goto err; 245cafe5635SKent Overstreet break; 246cafe5635SKent Overstreet case BCACHE_BSET_VERSION: 247cafe5635SKent Overstreet if (i->csum != btree_csum_set(b, i)) 248cafe5635SKent Overstreet goto err; 249cafe5635SKent Overstreet break; 250cafe5635SKent Overstreet } 251cafe5635SKent Overstreet 252cafe5635SKent Overstreet err = "empty set"; 253cafe5635SKent Overstreet if (i != b->sets[0].data && !i->keys) 254cafe5635SKent Overstreet goto err; 255cafe5635SKent Overstreet 256fafff81cSKent Overstreet bch_btree_iter_push(iter, i->start, bset_bkey_last(i)); 257cafe5635SKent Overstreet 258ee811287SKent Overstreet b->written += set_blocks(i, block_bytes(b->c)); 259cafe5635SKent Overstreet } 260cafe5635SKent Overstreet 261cafe5635SKent Overstreet err = "corrupted btree"; 262cafe5635SKent Overstreet for (i = write_block(b); 26388b9f8c4SKent Overstreet bset_sector_offset(b, i) < KEY_SIZE(&b->key); 264cafe5635SKent Overstreet i = ((void *) i) + block_bytes(b->c)) 265cafe5635SKent Overstreet if (i->seq == b->sets[0].data->seq) 266cafe5635SKent Overstreet goto err; 267cafe5635SKent Overstreet 26867539e85SKent Overstreet bch_btree_sort_and_fix_extents(b, iter, &b->c->sort); 269cafe5635SKent Overstreet 270cafe5635SKent Overstreet i = b->sets[0].data; 271cafe5635SKent Overstreet err = "short btree key"; 272cafe5635SKent Overstreet if (b->sets[0].size && 273cafe5635SKent Overstreet bkey_cmp(&b->key, &b->sets[0].end) < 0) 274cafe5635SKent Overstreet goto err; 275cafe5635SKent Overstreet 276cafe5635SKent Overstreet if (b->written < btree_blocks(b)) 277ee811287SKent Overstreet bch_bset_init_next(b, write_block(b), bset_magic(&b->c->sb)); 278cafe5635SKent Overstreet out: 27957943511SKent Overstreet mempool_free(iter, b->c->fill_iter); 28057943511SKent Overstreet return; 281cafe5635SKent Overstreet err: 282cafe5635SKent Overstreet set_btree_node_io_error(b); 28388b9f8c4SKent Overstreet bch_cache_set_error(b->c, "%s at bucket %zu, block %u, %u keys", 284cafe5635SKent Overstreet err, PTR_BUCKET_NR(b->c, &b->key, 0), 28588b9f8c4SKent Overstreet bset_block_offset(b, i), i->keys); 286cafe5635SKent Overstreet goto out; 287cafe5635SKent Overstreet } 288cafe5635SKent Overstreet 28957943511SKent Overstreet static void btree_node_read_endio(struct bio *bio, int error) 290cafe5635SKent Overstreet { 29157943511SKent Overstreet struct closure *cl = bio->bi_private; 29257943511SKent Overstreet closure_put(cl); 29357943511SKent Overstreet } 294cafe5635SKent Overstreet 29578b77bf8SKent Overstreet static void bch_btree_node_read(struct btree *b) 29657943511SKent Overstreet { 29757943511SKent Overstreet uint64_t start_time = local_clock(); 29857943511SKent Overstreet struct closure cl; 29957943511SKent Overstreet struct bio *bio; 300cafe5635SKent Overstreet 301c37511b8SKent Overstreet trace_bcache_btree_read(b); 302c37511b8SKent Overstreet 30357943511SKent Overstreet closure_init_stack(&cl); 304cafe5635SKent Overstreet 30557943511SKent Overstreet bio = bch_bbio_alloc(b->c); 30657943511SKent Overstreet bio->bi_rw = REQ_META|READ_SYNC; 3074f024f37SKent Overstreet bio->bi_iter.bi_size = KEY_SIZE(&b->key) << 9; 30857943511SKent Overstreet bio->bi_end_io = btree_node_read_endio; 30957943511SKent Overstreet bio->bi_private = &cl; 31057943511SKent Overstreet 31157943511SKent Overstreet bch_bio_map(bio, b->sets[0].data); 31257943511SKent Overstreet 31357943511SKent Overstreet bch_submit_bbio(bio, b->c, &b->key, 0); 31457943511SKent Overstreet closure_sync(&cl); 31557943511SKent Overstreet 31657943511SKent Overstreet if (!test_bit(BIO_UPTODATE, &bio->bi_flags)) 31757943511SKent Overstreet set_btree_node_io_error(b); 31857943511SKent Overstreet 31957943511SKent Overstreet bch_bbio_free(bio, b->c); 32057943511SKent Overstreet 32157943511SKent Overstreet if (btree_node_io_error(b)) 32257943511SKent Overstreet goto err; 32357943511SKent Overstreet 32457943511SKent Overstreet bch_btree_node_read_done(b); 32557943511SKent Overstreet bch_time_stats_update(&b->c->btree_read_time, start_time); 32657943511SKent Overstreet 32757943511SKent Overstreet return; 32857943511SKent Overstreet err: 32961cbd250SGeert Uytterhoeven bch_cache_set_error(b->c, "io error reading bucket %zu", 33057943511SKent Overstreet PTR_BUCKET_NR(b->c, &b->key, 0)); 331cafe5635SKent Overstreet } 332cafe5635SKent Overstreet 333cafe5635SKent Overstreet static void btree_complete_write(struct btree *b, struct btree_write *w) 334cafe5635SKent Overstreet { 335cafe5635SKent Overstreet if (w->prio_blocked && 336cafe5635SKent Overstreet !atomic_sub_return(w->prio_blocked, &b->c->prio_blocked)) 337119ba0f8SKent Overstreet wake_up_allocators(b->c); 338cafe5635SKent Overstreet 339cafe5635SKent Overstreet if (w->journal) { 340cafe5635SKent Overstreet atomic_dec_bug(w->journal); 341cafe5635SKent Overstreet __closure_wake_up(&b->c->journal.wait); 342cafe5635SKent Overstreet } 343cafe5635SKent Overstreet 344cafe5635SKent Overstreet w->prio_blocked = 0; 345cafe5635SKent Overstreet w->journal = NULL; 346cafe5635SKent Overstreet } 347cafe5635SKent Overstreet 348cb7a583eSKent Overstreet static void btree_node_write_unlock(struct closure *cl) 349cb7a583eSKent Overstreet { 350cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 351cb7a583eSKent Overstreet 352cb7a583eSKent Overstreet up(&b->io_mutex); 353cb7a583eSKent Overstreet } 354cb7a583eSKent Overstreet 35557943511SKent Overstreet static void __btree_node_write_done(struct closure *cl) 356cafe5635SKent Overstreet { 357cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 358cafe5635SKent Overstreet struct btree_write *w = btree_prev_write(b); 359cafe5635SKent Overstreet 360cafe5635SKent Overstreet bch_bbio_free(b->bio, b->c); 361cafe5635SKent Overstreet b->bio = NULL; 362cafe5635SKent Overstreet btree_complete_write(b, w); 363cafe5635SKent Overstreet 364cafe5635SKent Overstreet if (btree_node_dirty(b)) 365cafe5635SKent Overstreet queue_delayed_work(btree_io_wq, &b->work, 366cafe5635SKent Overstreet msecs_to_jiffies(30000)); 367cafe5635SKent Overstreet 368cb7a583eSKent Overstreet closure_return_with_destructor(cl, btree_node_write_unlock); 369cafe5635SKent Overstreet } 370cafe5635SKent Overstreet 37157943511SKent Overstreet static void btree_node_write_done(struct closure *cl) 372cafe5635SKent Overstreet { 373cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 374cafe5635SKent Overstreet struct bio_vec *bv; 375cafe5635SKent Overstreet int n; 376cafe5635SKent Overstreet 3777988613bSKent Overstreet bio_for_each_segment_all(bv, b->bio, n) 378cafe5635SKent Overstreet __free_page(bv->bv_page); 379cafe5635SKent Overstreet 38057943511SKent Overstreet __btree_node_write_done(cl); 381cafe5635SKent Overstreet } 382cafe5635SKent Overstreet 38357943511SKent Overstreet static void btree_node_write_endio(struct bio *bio, int error) 38457943511SKent Overstreet { 38557943511SKent Overstreet struct closure *cl = bio->bi_private; 386cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 38757943511SKent Overstreet 38857943511SKent Overstreet if (error) 38957943511SKent Overstreet set_btree_node_io_error(b); 39057943511SKent Overstreet 39157943511SKent Overstreet bch_bbio_count_io_errors(b->c, bio, error, "writing btree"); 39257943511SKent Overstreet closure_put(cl); 39357943511SKent Overstreet } 39457943511SKent Overstreet 39557943511SKent Overstreet static void do_btree_node_write(struct btree *b) 396cafe5635SKent Overstreet { 397cb7a583eSKent Overstreet struct closure *cl = &b->io; 398ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 399cafe5635SKent Overstreet BKEY_PADDED(key) k; 400cafe5635SKent Overstreet 401cafe5635SKent Overstreet i->version = BCACHE_BSET_VERSION; 402cafe5635SKent Overstreet i->csum = btree_csum_set(b, i); 403cafe5635SKent Overstreet 40457943511SKent Overstreet BUG_ON(b->bio); 40557943511SKent Overstreet b->bio = bch_bbio_alloc(b->c); 40657943511SKent Overstreet 40757943511SKent Overstreet b->bio->bi_end_io = btree_node_write_endio; 408faadf0c9SKent Overstreet b->bio->bi_private = cl; 409e49c7c37SKent Overstreet b->bio->bi_rw = REQ_META|WRITE_SYNC|REQ_FUA; 410ee811287SKent Overstreet b->bio->bi_iter.bi_size = roundup(set_bytes(i), block_bytes(b->c)); 411169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 412cafe5635SKent Overstreet 413e49c7c37SKent Overstreet /* 414e49c7c37SKent Overstreet * If we're appending to a leaf node, we don't technically need FUA - 415e49c7c37SKent Overstreet * this write just needs to be persisted before the next journal write, 416e49c7c37SKent Overstreet * which will be marked FLUSH|FUA. 417e49c7c37SKent Overstreet * 418e49c7c37SKent Overstreet * Similarly if we're writing a new btree root - the pointer is going to 419e49c7c37SKent Overstreet * be in the next journal entry. 420e49c7c37SKent Overstreet * 421e49c7c37SKent Overstreet * But if we're writing a new btree node (that isn't a root) or 422e49c7c37SKent Overstreet * appending to a non leaf btree node, we need either FUA or a flush 423e49c7c37SKent Overstreet * when we write the parent with the new pointer. FUA is cheaper than a 424e49c7c37SKent Overstreet * flush, and writes appending to leaf nodes aren't blocking anything so 425e49c7c37SKent Overstreet * just make all btree node writes FUA to keep things sane. 426e49c7c37SKent Overstreet */ 427e49c7c37SKent Overstreet 428cafe5635SKent Overstreet bkey_copy(&k.key, &b->key); 429ee811287SKent Overstreet SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) + 430ee811287SKent Overstreet bset_sector_offset(b, i)); 431cafe5635SKent Overstreet 4328e51e414SKent Overstreet if (!bio_alloc_pages(b->bio, GFP_NOIO)) { 433cafe5635SKent Overstreet int j; 434cafe5635SKent Overstreet struct bio_vec *bv; 435cafe5635SKent Overstreet void *base = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1)); 436cafe5635SKent Overstreet 4377988613bSKent Overstreet bio_for_each_segment_all(bv, b->bio, j) 438cafe5635SKent Overstreet memcpy(page_address(bv->bv_page), 439cafe5635SKent Overstreet base + j * PAGE_SIZE, PAGE_SIZE); 440cafe5635SKent Overstreet 441cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 442cafe5635SKent Overstreet 44357943511SKent Overstreet continue_at(cl, btree_node_write_done, NULL); 444cafe5635SKent Overstreet } else { 445cafe5635SKent Overstreet b->bio->bi_vcnt = 0; 446169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 447cafe5635SKent Overstreet 448cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 449cafe5635SKent Overstreet 450cafe5635SKent Overstreet closure_sync(cl); 451cb7a583eSKent Overstreet continue_at_nobarrier(cl, __btree_node_write_done, NULL); 452cafe5635SKent Overstreet } 453cafe5635SKent Overstreet } 454cafe5635SKent Overstreet 45557943511SKent Overstreet void bch_btree_node_write(struct btree *b, struct closure *parent) 456cafe5635SKent Overstreet { 457ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 458cafe5635SKent Overstreet 459c37511b8SKent Overstreet trace_bcache_btree_write(b); 460c37511b8SKent Overstreet 461cafe5635SKent Overstreet BUG_ON(current->bio_list); 46257943511SKent Overstreet BUG_ON(b->written >= btree_blocks(b)); 46357943511SKent Overstreet BUG_ON(b->written && !i->keys); 464ee811287SKent Overstreet BUG_ON(btree_bset_first(b)->seq != i->seq); 465280481d0SKent Overstreet bch_check_keys(b, "writing"); 466cafe5635SKent Overstreet 467cafe5635SKent Overstreet cancel_delayed_work(&b->work); 468cafe5635SKent Overstreet 46957943511SKent Overstreet /* If caller isn't waiting for write, parent refcount is cache set */ 470cb7a583eSKent Overstreet down(&b->io_mutex); 471cb7a583eSKent Overstreet closure_init(&b->io, parent ?: &b->c->cl); 47257943511SKent Overstreet 473cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 474cafe5635SKent Overstreet change_bit(BTREE_NODE_write_idx, &b->flags); 475cafe5635SKent Overstreet 47657943511SKent Overstreet do_btree_node_write(b); 477cafe5635SKent Overstreet 478ee811287SKent Overstreet b->written += set_blocks(i, block_bytes(b->c)); 479ee811287SKent Overstreet atomic_long_add(set_blocks(i, block_bytes(b->c)) * b->c->sb.block_size, 480cafe5635SKent Overstreet &PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written); 481cafe5635SKent Overstreet 48267539e85SKent Overstreet /* If not a leaf node, always sort */ 48367539e85SKent Overstreet if (b->level && b->nsets) 48467539e85SKent Overstreet bch_btree_sort(b, &b->c->sort); 48567539e85SKent Overstreet else 48667539e85SKent Overstreet bch_btree_sort_lazy(b, &b->c->sort); 487cafe5635SKent Overstreet 48878b77bf8SKent Overstreet /* 48978b77bf8SKent Overstreet * do verify if there was more than one set initially (i.e. we did a 49078b77bf8SKent Overstreet * sort) and we sorted down to a single set: 49178b77bf8SKent Overstreet */ 49278b77bf8SKent Overstreet if (i != b->sets->data && !b->nsets) 49378b77bf8SKent Overstreet bch_btree_verify(b); 49478b77bf8SKent Overstreet 495cafe5635SKent Overstreet if (b->written < btree_blocks(b)) 496ee811287SKent Overstreet bch_bset_init_next(b, write_block(b), bset_magic(&b->c->sb)); 497cafe5635SKent Overstreet } 498cafe5635SKent Overstreet 499f269af5aSKent Overstreet static void bch_btree_node_write_sync(struct btree *b) 500f269af5aSKent Overstreet { 501f269af5aSKent Overstreet struct closure cl; 502f269af5aSKent Overstreet 503f269af5aSKent Overstreet closure_init_stack(&cl); 504f269af5aSKent Overstreet bch_btree_node_write(b, &cl); 505f269af5aSKent Overstreet closure_sync(&cl); 506f269af5aSKent Overstreet } 507f269af5aSKent Overstreet 50857943511SKent Overstreet static void btree_node_write_work(struct work_struct *w) 509cafe5635SKent Overstreet { 510cafe5635SKent Overstreet struct btree *b = container_of(to_delayed_work(w), struct btree, work); 511cafe5635SKent Overstreet 51257943511SKent Overstreet rw_lock(true, b, b->level); 513cafe5635SKent Overstreet 514cafe5635SKent Overstreet if (btree_node_dirty(b)) 51557943511SKent Overstreet bch_btree_node_write(b, NULL); 51657943511SKent Overstreet rw_unlock(true, b); 517cafe5635SKent Overstreet } 518cafe5635SKent Overstreet 519c18536a7SKent Overstreet static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref) 520cafe5635SKent Overstreet { 521ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 522cafe5635SKent Overstreet struct btree_write *w = btree_current_write(b); 523cafe5635SKent Overstreet 52457943511SKent Overstreet BUG_ON(!b->written); 52557943511SKent Overstreet BUG_ON(!i->keys); 526cafe5635SKent Overstreet 52757943511SKent Overstreet if (!btree_node_dirty(b)) 52857943511SKent Overstreet queue_delayed_work(btree_io_wq, &b->work, 30 * HZ); 52957943511SKent Overstreet 530cafe5635SKent Overstreet set_btree_node_dirty(b); 531cafe5635SKent Overstreet 532c18536a7SKent Overstreet if (journal_ref) { 533cafe5635SKent Overstreet if (w->journal && 534c18536a7SKent Overstreet journal_pin_cmp(b->c, w->journal, journal_ref)) { 535cafe5635SKent Overstreet atomic_dec_bug(w->journal); 536cafe5635SKent Overstreet w->journal = NULL; 537cafe5635SKent Overstreet } 538cafe5635SKent Overstreet 539cafe5635SKent Overstreet if (!w->journal) { 540c18536a7SKent Overstreet w->journal = journal_ref; 541cafe5635SKent Overstreet atomic_inc(w->journal); 542cafe5635SKent Overstreet } 543cafe5635SKent Overstreet } 544cafe5635SKent Overstreet 545cafe5635SKent Overstreet /* Force write if set is too big */ 54657943511SKent Overstreet if (set_bytes(i) > PAGE_SIZE - 48 && 54757943511SKent Overstreet !current->bio_list) 54857943511SKent Overstreet bch_btree_node_write(b, NULL); 549cafe5635SKent Overstreet } 550cafe5635SKent Overstreet 551cafe5635SKent Overstreet /* 552cafe5635SKent Overstreet * Btree in memory cache - allocation/freeing 553cafe5635SKent Overstreet * mca -> memory cache 554cafe5635SKent Overstreet */ 555cafe5635SKent Overstreet 556cafe5635SKent Overstreet static void mca_reinit(struct btree *b) 557cafe5635SKent Overstreet { 558cafe5635SKent Overstreet unsigned i; 559cafe5635SKent Overstreet 560cafe5635SKent Overstreet b->flags = 0; 561cafe5635SKent Overstreet b->written = 0; 562cafe5635SKent Overstreet b->nsets = 0; 563cafe5635SKent Overstreet 564cafe5635SKent Overstreet for (i = 0; i < MAX_BSETS; i++) 565cafe5635SKent Overstreet b->sets[i].size = 0; 566cafe5635SKent Overstreet /* 567cafe5635SKent Overstreet * Second loop starts at 1 because b->sets[0]->data is the memory we 568cafe5635SKent Overstreet * allocated 569cafe5635SKent Overstreet */ 570cafe5635SKent Overstreet for (i = 1; i < MAX_BSETS; i++) 571cafe5635SKent Overstreet b->sets[i].data = NULL; 572cafe5635SKent Overstreet } 573cafe5635SKent Overstreet 574cafe5635SKent Overstreet #define mca_reserve(c) (((c->root && c->root->level) \ 575cafe5635SKent Overstreet ? c->root->level : 1) * 8 + 16) 576cafe5635SKent Overstreet #define mca_can_free(c) \ 577cafe5635SKent Overstreet max_t(int, 0, c->bucket_cache_used - mca_reserve(c)) 578cafe5635SKent Overstreet 579cafe5635SKent Overstreet static void mca_data_free(struct btree *b) 580cafe5635SKent Overstreet { 581cb7a583eSKent Overstreet BUG_ON(b->io_mutex.count != 1); 582cafe5635SKent Overstreet 583ee811287SKent Overstreet bch_btree_keys_free(b); 584cafe5635SKent Overstreet 585cafe5635SKent Overstreet b->c->bucket_cache_used--; 586ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 587cafe5635SKent Overstreet } 588cafe5635SKent Overstreet 589cafe5635SKent Overstreet static void mca_bucket_free(struct btree *b) 590cafe5635SKent Overstreet { 591cafe5635SKent Overstreet BUG_ON(btree_node_dirty(b)); 592cafe5635SKent Overstreet 593cafe5635SKent Overstreet b->key.ptr[0] = 0; 594cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 595cafe5635SKent Overstreet list_move(&b->list, &b->c->btree_cache_freeable); 596cafe5635SKent Overstreet } 597cafe5635SKent Overstreet 598cafe5635SKent Overstreet static unsigned btree_order(struct bkey *k) 599cafe5635SKent Overstreet { 600cafe5635SKent Overstreet return ilog2(KEY_SIZE(k) / PAGE_SECTORS ?: 1); 601cafe5635SKent Overstreet } 602cafe5635SKent Overstreet 603cafe5635SKent Overstreet static void mca_data_alloc(struct btree *b, struct bkey *k, gfp_t gfp) 604cafe5635SKent Overstreet { 605ee811287SKent Overstreet if (!bch_btree_keys_alloc(b, 606ee811287SKent Overstreet max_t(unsigned, 607cafe5635SKent Overstreet ilog2(b->c->btree_pages), 608ee811287SKent Overstreet btree_order(k)), 609ee811287SKent Overstreet gfp)) { 610cafe5635SKent Overstreet b->c->bucket_cache_used++; 611ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache); 612ee811287SKent Overstreet } else { 613ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 614ee811287SKent Overstreet } 615cafe5635SKent Overstreet } 616cafe5635SKent Overstreet 617cafe5635SKent Overstreet static struct btree *mca_bucket_alloc(struct cache_set *c, 618cafe5635SKent Overstreet struct bkey *k, gfp_t gfp) 619cafe5635SKent Overstreet { 620cafe5635SKent Overstreet struct btree *b = kzalloc(sizeof(struct btree), gfp); 621cafe5635SKent Overstreet if (!b) 622cafe5635SKent Overstreet return NULL; 623cafe5635SKent Overstreet 624cafe5635SKent Overstreet init_rwsem(&b->lock); 625cafe5635SKent Overstreet lockdep_set_novalidate_class(&b->lock); 626cafe5635SKent Overstreet INIT_LIST_HEAD(&b->list); 62757943511SKent Overstreet INIT_DELAYED_WORK(&b->work, btree_node_write_work); 628cafe5635SKent Overstreet b->c = c; 629cb7a583eSKent Overstreet sema_init(&b->io_mutex, 1); 630cafe5635SKent Overstreet 631cafe5635SKent Overstreet mca_data_alloc(b, k, gfp); 632cafe5635SKent Overstreet return b; 633cafe5635SKent Overstreet } 634cafe5635SKent Overstreet 635e8e1d468SKent Overstreet static int mca_reap(struct btree *b, unsigned min_order, bool flush) 636cafe5635SKent Overstreet { 637e8e1d468SKent Overstreet struct closure cl; 638e8e1d468SKent Overstreet 639e8e1d468SKent Overstreet closure_init_stack(&cl); 640cafe5635SKent Overstreet lockdep_assert_held(&b->c->bucket_lock); 641cafe5635SKent Overstreet 642cafe5635SKent Overstreet if (!down_write_trylock(&b->lock)) 643cafe5635SKent Overstreet return -ENOMEM; 644cafe5635SKent Overstreet 645e8e1d468SKent Overstreet BUG_ON(btree_node_dirty(b) && !b->sets[0].data); 646e8e1d468SKent Overstreet 647cb7a583eSKent Overstreet if (b->page_order < min_order) 648cb7a583eSKent Overstreet goto out_unlock; 649cb7a583eSKent Overstreet 650cb7a583eSKent Overstreet if (!flush) { 651cb7a583eSKent Overstreet if (btree_node_dirty(b)) 652cb7a583eSKent Overstreet goto out_unlock; 653cb7a583eSKent Overstreet 654cb7a583eSKent Overstreet if (down_trylock(&b->io_mutex)) 655cb7a583eSKent Overstreet goto out_unlock; 656cb7a583eSKent Overstreet up(&b->io_mutex); 657cafe5635SKent Overstreet } 658cafe5635SKent Overstreet 659f269af5aSKent Overstreet if (btree_node_dirty(b)) 660f269af5aSKent Overstreet bch_btree_node_write_sync(b); 661cafe5635SKent Overstreet 662e8e1d468SKent Overstreet /* wait for any in flight btree write */ 663cb7a583eSKent Overstreet down(&b->io_mutex); 664cb7a583eSKent Overstreet up(&b->io_mutex); 665e8e1d468SKent Overstreet 666cafe5635SKent Overstreet return 0; 667cb7a583eSKent Overstreet out_unlock: 668cb7a583eSKent Overstreet rw_unlock(true, b); 669cb7a583eSKent Overstreet return -ENOMEM; 670cafe5635SKent Overstreet } 671cafe5635SKent Overstreet 6727dc19d5aSDave Chinner static unsigned long bch_mca_scan(struct shrinker *shrink, 6737dc19d5aSDave Chinner struct shrink_control *sc) 674cafe5635SKent Overstreet { 675cafe5635SKent Overstreet struct cache_set *c = container_of(shrink, struct cache_set, shrink); 676cafe5635SKent Overstreet struct btree *b, *t; 677cafe5635SKent Overstreet unsigned long i, nr = sc->nr_to_scan; 6787dc19d5aSDave Chinner unsigned long freed = 0; 679cafe5635SKent Overstreet 680cafe5635SKent Overstreet if (c->shrinker_disabled) 6817dc19d5aSDave Chinner return SHRINK_STOP; 682cafe5635SKent Overstreet 683cafe5635SKent Overstreet if (c->try_harder) 6847dc19d5aSDave Chinner return SHRINK_STOP; 685cafe5635SKent Overstreet 686cafe5635SKent Overstreet /* Return -1 if we can't do anything right now */ 687a698e08cSKent Overstreet if (sc->gfp_mask & __GFP_IO) 688cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 689cafe5635SKent Overstreet else if (!mutex_trylock(&c->bucket_lock)) 690cafe5635SKent Overstreet return -1; 691cafe5635SKent Overstreet 69236c9ea98SKent Overstreet /* 69336c9ea98SKent Overstreet * It's _really_ critical that we don't free too many btree nodes - we 69436c9ea98SKent Overstreet * have to always leave ourselves a reserve. The reserve is how we 69536c9ea98SKent Overstreet * guarantee that allocating memory for a new btree node can always 69636c9ea98SKent Overstreet * succeed, so that inserting keys into the btree can always succeed and 69736c9ea98SKent Overstreet * IO can always make forward progress: 69836c9ea98SKent Overstreet */ 699cafe5635SKent Overstreet nr /= c->btree_pages; 700cafe5635SKent Overstreet nr = min_t(unsigned long, nr, mca_can_free(c)); 701cafe5635SKent Overstreet 702cafe5635SKent Overstreet i = 0; 703cafe5635SKent Overstreet list_for_each_entry_safe(b, t, &c->btree_cache_freeable, list) { 7047dc19d5aSDave Chinner if (freed >= nr) 705cafe5635SKent Overstreet break; 706cafe5635SKent Overstreet 707cafe5635SKent Overstreet if (++i > 3 && 708e8e1d468SKent Overstreet !mca_reap(b, 0, false)) { 709cafe5635SKent Overstreet mca_data_free(b); 710cafe5635SKent Overstreet rw_unlock(true, b); 7117dc19d5aSDave Chinner freed++; 712cafe5635SKent Overstreet } 713cafe5635SKent Overstreet } 714cafe5635SKent Overstreet 715b0f32a56SKent Overstreet for (i = 0; (nr--) && i < c->bucket_cache_used; i++) { 716cafe5635SKent Overstreet if (list_empty(&c->btree_cache)) 717cafe5635SKent Overstreet goto out; 718cafe5635SKent Overstreet 719cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 720cafe5635SKent Overstreet list_rotate_left(&c->btree_cache); 721cafe5635SKent Overstreet 722cafe5635SKent Overstreet if (!b->accessed && 723e8e1d468SKent Overstreet !mca_reap(b, 0, false)) { 724cafe5635SKent Overstreet mca_bucket_free(b); 725cafe5635SKent Overstreet mca_data_free(b); 726cafe5635SKent Overstreet rw_unlock(true, b); 7277dc19d5aSDave Chinner freed++; 728cafe5635SKent Overstreet } else 729cafe5635SKent Overstreet b->accessed = 0; 730cafe5635SKent Overstreet } 731cafe5635SKent Overstreet out: 732cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 7337dc19d5aSDave Chinner return freed; 7347dc19d5aSDave Chinner } 7357dc19d5aSDave Chinner 7367dc19d5aSDave Chinner static unsigned long bch_mca_count(struct shrinker *shrink, 7377dc19d5aSDave Chinner struct shrink_control *sc) 7387dc19d5aSDave Chinner { 7397dc19d5aSDave Chinner struct cache_set *c = container_of(shrink, struct cache_set, shrink); 7407dc19d5aSDave Chinner 7417dc19d5aSDave Chinner if (c->shrinker_disabled) 7427dc19d5aSDave Chinner return 0; 7437dc19d5aSDave Chinner 7447dc19d5aSDave Chinner if (c->try_harder) 7457dc19d5aSDave Chinner return 0; 7467dc19d5aSDave Chinner 7477dc19d5aSDave Chinner return mca_can_free(c) * c->btree_pages; 748cafe5635SKent Overstreet } 749cafe5635SKent Overstreet 750cafe5635SKent Overstreet void bch_btree_cache_free(struct cache_set *c) 751cafe5635SKent Overstreet { 752cafe5635SKent Overstreet struct btree *b; 753cafe5635SKent Overstreet struct closure cl; 754cafe5635SKent Overstreet closure_init_stack(&cl); 755cafe5635SKent Overstreet 756cafe5635SKent Overstreet if (c->shrink.list.next) 757cafe5635SKent Overstreet unregister_shrinker(&c->shrink); 758cafe5635SKent Overstreet 759cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 760cafe5635SKent Overstreet 761cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 762cafe5635SKent Overstreet if (c->verify_data) 763cafe5635SKent Overstreet list_move(&c->verify_data->list, &c->btree_cache); 76478b77bf8SKent Overstreet 76578b77bf8SKent Overstreet free_pages((unsigned long) c->verify_ondisk, ilog2(bucket_pages(c))); 766cafe5635SKent Overstreet #endif 767cafe5635SKent Overstreet 768cafe5635SKent Overstreet list_splice(&c->btree_cache_freeable, 769cafe5635SKent Overstreet &c->btree_cache); 770cafe5635SKent Overstreet 771cafe5635SKent Overstreet while (!list_empty(&c->btree_cache)) { 772cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 773cafe5635SKent Overstreet 774cafe5635SKent Overstreet if (btree_node_dirty(b)) 775cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 776cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 777cafe5635SKent Overstreet 778cafe5635SKent Overstreet mca_data_free(b); 779cafe5635SKent Overstreet } 780cafe5635SKent Overstreet 781cafe5635SKent Overstreet while (!list_empty(&c->btree_cache_freed)) { 782cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache_freed, 783cafe5635SKent Overstreet struct btree, list); 784cafe5635SKent Overstreet list_del(&b->list); 785cafe5635SKent Overstreet cancel_delayed_work_sync(&b->work); 786cafe5635SKent Overstreet kfree(b); 787cafe5635SKent Overstreet } 788cafe5635SKent Overstreet 789cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 790cafe5635SKent Overstreet } 791cafe5635SKent Overstreet 792cafe5635SKent Overstreet int bch_btree_cache_alloc(struct cache_set *c) 793cafe5635SKent Overstreet { 794cafe5635SKent Overstreet unsigned i; 795cafe5635SKent Overstreet 796cafe5635SKent Overstreet for (i = 0; i < mca_reserve(c); i++) 79772a44517SKent Overstreet if (!mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL)) 79872a44517SKent Overstreet return -ENOMEM; 799cafe5635SKent Overstreet 800cafe5635SKent Overstreet list_splice_init(&c->btree_cache, 801cafe5635SKent Overstreet &c->btree_cache_freeable); 802cafe5635SKent Overstreet 803cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 804cafe5635SKent Overstreet mutex_init(&c->verify_lock); 805cafe5635SKent Overstreet 80678b77bf8SKent Overstreet c->verify_ondisk = (void *) 80778b77bf8SKent Overstreet __get_free_pages(GFP_KERNEL, ilog2(bucket_pages(c))); 80878b77bf8SKent Overstreet 809cafe5635SKent Overstreet c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL); 810cafe5635SKent Overstreet 811cafe5635SKent Overstreet if (c->verify_data && 812cafe5635SKent Overstreet c->verify_data->sets[0].data) 813cafe5635SKent Overstreet list_del_init(&c->verify_data->list); 814cafe5635SKent Overstreet else 815cafe5635SKent Overstreet c->verify_data = NULL; 816cafe5635SKent Overstreet #endif 817cafe5635SKent Overstreet 8187dc19d5aSDave Chinner c->shrink.count_objects = bch_mca_count; 8197dc19d5aSDave Chinner c->shrink.scan_objects = bch_mca_scan; 820cafe5635SKent Overstreet c->shrink.seeks = 4; 821cafe5635SKent Overstreet c->shrink.batch = c->btree_pages * 2; 822cafe5635SKent Overstreet register_shrinker(&c->shrink); 823cafe5635SKent Overstreet 824cafe5635SKent Overstreet return 0; 825cafe5635SKent Overstreet } 826cafe5635SKent Overstreet 827cafe5635SKent Overstreet /* Btree in memory cache - hash table */ 828cafe5635SKent Overstreet 829cafe5635SKent Overstreet static struct hlist_head *mca_hash(struct cache_set *c, struct bkey *k) 830cafe5635SKent Overstreet { 831cafe5635SKent Overstreet return &c->bucket_hash[hash_32(PTR_HASH(c, k), BUCKET_HASH_BITS)]; 832cafe5635SKent Overstreet } 833cafe5635SKent Overstreet 834cafe5635SKent Overstreet static struct btree *mca_find(struct cache_set *c, struct bkey *k) 835cafe5635SKent Overstreet { 836cafe5635SKent Overstreet struct btree *b; 837cafe5635SKent Overstreet 838cafe5635SKent Overstreet rcu_read_lock(); 839cafe5635SKent Overstreet hlist_for_each_entry_rcu(b, mca_hash(c, k), hash) 840cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) == PTR_HASH(c, k)) 841cafe5635SKent Overstreet goto out; 842cafe5635SKent Overstreet b = NULL; 843cafe5635SKent Overstreet out: 844cafe5635SKent Overstreet rcu_read_unlock(); 845cafe5635SKent Overstreet return b; 846cafe5635SKent Overstreet } 847cafe5635SKent Overstreet 848e8e1d468SKent Overstreet static struct btree *mca_cannibalize(struct cache_set *c, struct bkey *k) 849cafe5635SKent Overstreet { 850e8e1d468SKent Overstreet struct btree *b; 851cafe5635SKent Overstreet 852c37511b8SKent Overstreet trace_bcache_btree_cache_cannibalize(c); 853c37511b8SKent Overstreet 854e8e1d468SKent Overstreet if (!c->try_harder) { 855e8e1d468SKent Overstreet c->try_harder = current; 856cafe5635SKent Overstreet c->try_harder_start = local_clock(); 857e8e1d468SKent Overstreet } else if (c->try_harder != current) 858e8e1d468SKent Overstreet return ERR_PTR(-ENOSPC); 859cafe5635SKent Overstreet 860e8e1d468SKent Overstreet list_for_each_entry_reverse(b, &c->btree_cache, list) 861e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), false)) 862e8e1d468SKent Overstreet return b; 863cafe5635SKent Overstreet 864e8e1d468SKent Overstreet list_for_each_entry_reverse(b, &c->btree_cache, list) 865e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), true)) 866e8e1d468SKent Overstreet return b; 867e8e1d468SKent Overstreet 868e8e1d468SKent Overstreet return ERR_PTR(-ENOMEM); 869cafe5635SKent Overstreet } 870cafe5635SKent Overstreet 871cafe5635SKent Overstreet /* 872cafe5635SKent Overstreet * We can only have one thread cannibalizing other cached btree nodes at a time, 873cafe5635SKent Overstreet * or we'll deadlock. We use an open coded mutex to ensure that, which a 874cafe5635SKent Overstreet * cannibalize_bucket() will take. This means every time we unlock the root of 875cafe5635SKent Overstreet * the btree, we need to release this lock if we have it held. 876cafe5635SKent Overstreet */ 877df8e8970SKent Overstreet static void bch_cannibalize_unlock(struct cache_set *c) 878cafe5635SKent Overstreet { 879e8e1d468SKent Overstreet if (c->try_harder == current) { 880169ef1cfSKent Overstreet bch_time_stats_update(&c->try_harder_time, c->try_harder_start); 881cafe5635SKent Overstreet c->try_harder = NULL; 882e8e1d468SKent Overstreet wake_up(&c->try_wait); 883cafe5635SKent Overstreet } 884cafe5635SKent Overstreet } 885cafe5635SKent Overstreet 886e8e1d468SKent Overstreet static struct btree *mca_alloc(struct cache_set *c, struct bkey *k, int level) 887cafe5635SKent Overstreet { 888cafe5635SKent Overstreet struct btree *b; 889cafe5635SKent Overstreet 890e8e1d468SKent Overstreet BUG_ON(current->bio_list); 891e8e1d468SKent Overstreet 892cafe5635SKent Overstreet lockdep_assert_held(&c->bucket_lock); 893cafe5635SKent Overstreet 894cafe5635SKent Overstreet if (mca_find(c, k)) 895cafe5635SKent Overstreet return NULL; 896cafe5635SKent Overstreet 897cafe5635SKent Overstreet /* btree_free() doesn't free memory; it sticks the node on the end of 898cafe5635SKent Overstreet * the list. Check if there's any freed nodes there: 899cafe5635SKent Overstreet */ 900cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freeable, list) 901e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), false)) 902cafe5635SKent Overstreet goto out; 903cafe5635SKent Overstreet 904cafe5635SKent Overstreet /* We never free struct btree itself, just the memory that holds the on 905cafe5635SKent Overstreet * disk node. Check the freed list before allocating a new one: 906cafe5635SKent Overstreet */ 907cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freed, list) 908e8e1d468SKent Overstreet if (!mca_reap(b, 0, false)) { 909cafe5635SKent Overstreet mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO); 910cafe5635SKent Overstreet if (!b->sets[0].data) 911cafe5635SKent Overstreet goto err; 912cafe5635SKent Overstreet else 913cafe5635SKent Overstreet goto out; 914cafe5635SKent Overstreet } 915cafe5635SKent Overstreet 916cafe5635SKent Overstreet b = mca_bucket_alloc(c, k, __GFP_NOWARN|GFP_NOIO); 917cafe5635SKent Overstreet if (!b) 918cafe5635SKent Overstreet goto err; 919cafe5635SKent Overstreet 920cafe5635SKent Overstreet BUG_ON(!down_write_trylock(&b->lock)); 921cafe5635SKent Overstreet if (!b->sets->data) 922cafe5635SKent Overstreet goto err; 923cafe5635SKent Overstreet out: 924cb7a583eSKent Overstreet BUG_ON(b->io_mutex.count != 1); 925cafe5635SKent Overstreet 926cafe5635SKent Overstreet bkey_copy(&b->key, k); 927cafe5635SKent Overstreet list_move(&b->list, &c->btree_cache); 928cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 929cafe5635SKent Overstreet hlist_add_head_rcu(&b->hash, mca_hash(c, k)); 930cafe5635SKent Overstreet 931cafe5635SKent Overstreet lock_set_subclass(&b->lock.dep_map, level + 1, _THIS_IP_); 932cafe5635SKent Overstreet b->level = level; 933d6fd3b11SKent Overstreet b->parent = (void *) ~0UL; 934cafe5635SKent Overstreet 935*65d45231SKent Overstreet if (!b->level) 936*65d45231SKent Overstreet b->ops = &bch_extent_keys_ops; 937*65d45231SKent Overstreet else 938*65d45231SKent Overstreet b->ops = &bch_btree_keys_ops; 939*65d45231SKent Overstreet 940cafe5635SKent Overstreet mca_reinit(b); 941cafe5635SKent Overstreet 942cafe5635SKent Overstreet return b; 943cafe5635SKent Overstreet err: 944cafe5635SKent Overstreet if (b) 945cafe5635SKent Overstreet rw_unlock(true, b); 946cafe5635SKent Overstreet 947e8e1d468SKent Overstreet b = mca_cannibalize(c, k); 948cafe5635SKent Overstreet if (!IS_ERR(b)) 949cafe5635SKent Overstreet goto out; 950cafe5635SKent Overstreet 951cafe5635SKent Overstreet return b; 952cafe5635SKent Overstreet } 953cafe5635SKent Overstreet 954cafe5635SKent Overstreet /** 955cafe5635SKent Overstreet * bch_btree_node_get - find a btree node in the cache and lock it, reading it 956cafe5635SKent Overstreet * in from disk if necessary. 957cafe5635SKent Overstreet * 958b54d6934SKent Overstreet * If IO is necessary and running under generic_make_request, returns -EAGAIN. 959cafe5635SKent Overstreet * 960cafe5635SKent Overstreet * The btree node will have either a read or a write lock held, depending on 961cafe5635SKent Overstreet * level and op->lock. 962cafe5635SKent Overstreet */ 963cafe5635SKent Overstreet struct btree *bch_btree_node_get(struct cache_set *c, struct bkey *k, 964e8e1d468SKent Overstreet int level, bool write) 965cafe5635SKent Overstreet { 966cafe5635SKent Overstreet int i = 0; 967cafe5635SKent Overstreet struct btree *b; 968cafe5635SKent Overstreet 969cafe5635SKent Overstreet BUG_ON(level < 0); 970cafe5635SKent Overstreet retry: 971cafe5635SKent Overstreet b = mca_find(c, k); 972cafe5635SKent Overstreet 973cafe5635SKent Overstreet if (!b) { 97457943511SKent Overstreet if (current->bio_list) 97557943511SKent Overstreet return ERR_PTR(-EAGAIN); 97657943511SKent Overstreet 977cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 978e8e1d468SKent Overstreet b = mca_alloc(c, k, level); 979cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 980cafe5635SKent Overstreet 981cafe5635SKent Overstreet if (!b) 982cafe5635SKent Overstreet goto retry; 983cafe5635SKent Overstreet if (IS_ERR(b)) 984cafe5635SKent Overstreet return b; 985cafe5635SKent Overstreet 98657943511SKent Overstreet bch_btree_node_read(b); 987cafe5635SKent Overstreet 988cafe5635SKent Overstreet if (!write) 989cafe5635SKent Overstreet downgrade_write(&b->lock); 990cafe5635SKent Overstreet } else { 991cafe5635SKent Overstreet rw_lock(write, b, level); 992cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) != PTR_HASH(c, k)) { 993cafe5635SKent Overstreet rw_unlock(write, b); 994cafe5635SKent Overstreet goto retry; 995cafe5635SKent Overstreet } 996cafe5635SKent Overstreet BUG_ON(b->level != level); 997cafe5635SKent Overstreet } 998cafe5635SKent Overstreet 999cafe5635SKent Overstreet b->accessed = 1; 1000cafe5635SKent Overstreet 1001cafe5635SKent Overstreet for (; i <= b->nsets && b->sets[i].size; i++) { 1002cafe5635SKent Overstreet prefetch(b->sets[i].tree); 1003cafe5635SKent Overstreet prefetch(b->sets[i].data); 1004cafe5635SKent Overstreet } 1005cafe5635SKent Overstreet 1006cafe5635SKent Overstreet for (; i <= b->nsets; i++) 1007cafe5635SKent Overstreet prefetch(b->sets[i].data); 1008cafe5635SKent Overstreet 100957943511SKent Overstreet if (btree_node_io_error(b)) { 1010cafe5635SKent Overstreet rw_unlock(write, b); 101157943511SKent Overstreet return ERR_PTR(-EIO); 101257943511SKent Overstreet } 101357943511SKent Overstreet 1014cafe5635SKent Overstreet BUG_ON(!b->written); 1015cafe5635SKent Overstreet 1016cafe5635SKent Overstreet return b; 1017cafe5635SKent Overstreet } 1018cafe5635SKent Overstreet 1019cafe5635SKent Overstreet static void btree_node_prefetch(struct cache_set *c, struct bkey *k, int level) 1020cafe5635SKent Overstreet { 1021cafe5635SKent Overstreet struct btree *b; 1022cafe5635SKent Overstreet 1023cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1024e8e1d468SKent Overstreet b = mca_alloc(c, k, level); 1025cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1026cafe5635SKent Overstreet 1027cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(b)) { 102857943511SKent Overstreet bch_btree_node_read(b); 1029cafe5635SKent Overstreet rw_unlock(true, b); 1030cafe5635SKent Overstreet } 1031cafe5635SKent Overstreet } 1032cafe5635SKent Overstreet 1033cafe5635SKent Overstreet /* Btree alloc */ 1034cafe5635SKent Overstreet 1035e8e1d468SKent Overstreet static void btree_node_free(struct btree *b) 1036cafe5635SKent Overstreet { 1037cafe5635SKent Overstreet unsigned i; 1038cafe5635SKent Overstreet 1039c37511b8SKent Overstreet trace_bcache_btree_node_free(b); 1040c37511b8SKent Overstreet 1041cafe5635SKent Overstreet BUG_ON(b == b->c->root); 1042cafe5635SKent Overstreet 1043cafe5635SKent Overstreet if (btree_node_dirty(b)) 1044cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 1045cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 1046cafe5635SKent Overstreet 1047cafe5635SKent Overstreet cancel_delayed_work(&b->work); 1048cafe5635SKent Overstreet 1049cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 1050cafe5635SKent Overstreet 1051cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) { 1052cafe5635SKent Overstreet BUG_ON(atomic_read(&PTR_BUCKET(b->c, &b->key, i)->pin)); 1053cafe5635SKent Overstreet 1054cafe5635SKent Overstreet bch_inc_gen(PTR_CACHE(b->c, &b->key, i), 1055cafe5635SKent Overstreet PTR_BUCKET(b->c, &b->key, i)); 1056cafe5635SKent Overstreet } 1057cafe5635SKent Overstreet 1058cafe5635SKent Overstreet bch_bucket_free(b->c, &b->key); 1059cafe5635SKent Overstreet mca_bucket_free(b); 1060cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 1061cafe5635SKent Overstreet } 1062cafe5635SKent Overstreet 1063bc9389eeSKent Overstreet struct btree *bch_btree_node_alloc(struct cache_set *c, int level, bool wait) 1064cafe5635SKent Overstreet { 1065cafe5635SKent Overstreet BKEY_PADDED(key) k; 1066cafe5635SKent Overstreet struct btree *b = ERR_PTR(-EAGAIN); 1067cafe5635SKent Overstreet 1068cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1069cafe5635SKent Overstreet retry: 107078365411SKent Overstreet if (__bch_bucket_alloc_set(c, RESERVE_BTREE, &k.key, 1, wait)) 1071cafe5635SKent Overstreet goto err; 1072cafe5635SKent Overstreet 10733a3b6a4eSKent Overstreet bkey_put(c, &k.key); 1074cafe5635SKent Overstreet SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS); 1075cafe5635SKent Overstreet 1076e8e1d468SKent Overstreet b = mca_alloc(c, &k.key, level); 1077cafe5635SKent Overstreet if (IS_ERR(b)) 1078cafe5635SKent Overstreet goto err_free; 1079cafe5635SKent Overstreet 1080cafe5635SKent Overstreet if (!b) { 1081b1a67b0fSKent Overstreet cache_bug(c, 1082b1a67b0fSKent Overstreet "Tried to allocate bucket that was in btree cache"); 1083cafe5635SKent Overstreet goto retry; 1084cafe5635SKent Overstreet } 1085cafe5635SKent Overstreet 1086cafe5635SKent Overstreet b->accessed = 1; 1087ee811287SKent Overstreet bch_bset_init_next(b, b->sets->data, bset_magic(&b->c->sb)); 1088cafe5635SKent Overstreet 1089cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1090c37511b8SKent Overstreet 1091c37511b8SKent Overstreet trace_bcache_btree_node_alloc(b); 1092cafe5635SKent Overstreet return b; 1093cafe5635SKent Overstreet err_free: 1094cafe5635SKent Overstreet bch_bucket_free(c, &k.key); 1095cafe5635SKent Overstreet err: 1096cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1097c37511b8SKent Overstreet 1098c37511b8SKent Overstreet trace_bcache_btree_node_alloc_fail(b); 1099cafe5635SKent Overstreet return b; 1100cafe5635SKent Overstreet } 1101cafe5635SKent Overstreet 1102bc9389eeSKent Overstreet static struct btree *btree_node_alloc_replacement(struct btree *b, bool wait) 1103cafe5635SKent Overstreet { 1104bc9389eeSKent Overstreet struct btree *n = bch_btree_node_alloc(b->c, b->level, wait); 110567539e85SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 110667539e85SKent Overstreet bch_btree_sort_into(b, n, &b->c->sort); 110767539e85SKent Overstreet bkey_copy_key(&n->key, &b->key); 110867539e85SKent Overstreet } 1109cafe5635SKent Overstreet 1110cafe5635SKent Overstreet return n; 1111cafe5635SKent Overstreet } 1112cafe5635SKent Overstreet 11138835c123SKent Overstreet static void make_btree_freeing_key(struct btree *b, struct bkey *k) 11148835c123SKent Overstreet { 11158835c123SKent Overstreet unsigned i; 11168835c123SKent Overstreet 11178835c123SKent Overstreet bkey_copy(k, &b->key); 11188835c123SKent Overstreet bkey_copy_key(k, &ZERO_KEY); 11198835c123SKent Overstreet 11208835c123SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) { 11218835c123SKent Overstreet uint8_t g = PTR_BUCKET(b->c, k, i)->gen + 1; 11228835c123SKent Overstreet 11238835c123SKent Overstreet SET_PTR_GEN(k, i, g); 11248835c123SKent Overstreet } 11258835c123SKent Overstreet 11268835c123SKent Overstreet atomic_inc(&b->c->prio_blocked); 11278835c123SKent Overstreet } 11288835c123SKent Overstreet 112978365411SKent Overstreet static int btree_check_reserve(struct btree *b, struct btree_op *op) 113078365411SKent Overstreet { 113178365411SKent Overstreet struct cache_set *c = b->c; 113278365411SKent Overstreet struct cache *ca; 113378365411SKent Overstreet unsigned i, reserve = c->root->level * 2 + 1; 113478365411SKent Overstreet int ret = 0; 113578365411SKent Overstreet 113678365411SKent Overstreet mutex_lock(&c->bucket_lock); 113778365411SKent Overstreet 113878365411SKent Overstreet for_each_cache(ca, c, i) 113978365411SKent Overstreet if (fifo_used(&ca->free[RESERVE_BTREE]) < reserve) { 114078365411SKent Overstreet if (op) 114178365411SKent Overstreet prepare_to_wait(&c->bucket_wait, &op->wait, 114278365411SKent Overstreet TASK_UNINTERRUPTIBLE); 114378365411SKent Overstreet ret = -EINTR; 114478365411SKent Overstreet break; 114578365411SKent Overstreet } 114678365411SKent Overstreet 114778365411SKent Overstreet mutex_unlock(&c->bucket_lock); 114878365411SKent Overstreet return ret; 114978365411SKent Overstreet } 115078365411SKent Overstreet 1151cafe5635SKent Overstreet /* Garbage collection */ 1152cafe5635SKent Overstreet 1153cafe5635SKent Overstreet uint8_t __bch_btree_mark_key(struct cache_set *c, int level, struct bkey *k) 1154cafe5635SKent Overstreet { 1155cafe5635SKent Overstreet uint8_t stale = 0; 1156cafe5635SKent Overstreet unsigned i; 1157cafe5635SKent Overstreet struct bucket *g; 1158cafe5635SKent Overstreet 1159cafe5635SKent Overstreet /* 1160cafe5635SKent Overstreet * ptr_invalid() can't return true for the keys that mark btree nodes as 1161cafe5635SKent Overstreet * freed, but since ptr_bad() returns true we'll never actually use them 1162cafe5635SKent Overstreet * for anything and thus we don't want mark their pointers here 1163cafe5635SKent Overstreet */ 1164cafe5635SKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1165cafe5635SKent Overstreet return stale; 1166cafe5635SKent Overstreet 1167cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) { 1168cafe5635SKent Overstreet if (!ptr_available(c, k, i)) 1169cafe5635SKent Overstreet continue; 1170cafe5635SKent Overstreet 1171cafe5635SKent Overstreet g = PTR_BUCKET(c, k, i); 1172cafe5635SKent Overstreet 1173cafe5635SKent Overstreet if (gen_after(g->gc_gen, PTR_GEN(k, i))) 1174cafe5635SKent Overstreet g->gc_gen = PTR_GEN(k, i); 1175cafe5635SKent Overstreet 1176cafe5635SKent Overstreet if (ptr_stale(c, k, i)) { 1177cafe5635SKent Overstreet stale = max(stale, ptr_stale(c, k, i)); 1178cafe5635SKent Overstreet continue; 1179cafe5635SKent Overstreet } 1180cafe5635SKent Overstreet 1181cafe5635SKent Overstreet cache_bug_on(GC_MARK(g) && 1182cafe5635SKent Overstreet (GC_MARK(g) == GC_MARK_METADATA) != (level != 0), 1183cafe5635SKent Overstreet c, "inconsistent ptrs: mark = %llu, level = %i", 1184cafe5635SKent Overstreet GC_MARK(g), level); 1185cafe5635SKent Overstreet 1186cafe5635SKent Overstreet if (level) 1187cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_METADATA); 1188cafe5635SKent Overstreet else if (KEY_DIRTY(k)) 1189cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_DIRTY); 1190cafe5635SKent Overstreet 1191cafe5635SKent Overstreet /* guard against overflow */ 1192cafe5635SKent Overstreet SET_GC_SECTORS_USED(g, min_t(unsigned, 1193cafe5635SKent Overstreet GC_SECTORS_USED(g) + KEY_SIZE(k), 1194cafe5635SKent Overstreet (1 << 14) - 1)); 1195cafe5635SKent Overstreet 1196cafe5635SKent Overstreet BUG_ON(!GC_SECTORS_USED(g)); 1197cafe5635SKent Overstreet } 1198cafe5635SKent Overstreet 1199cafe5635SKent Overstreet return stale; 1200cafe5635SKent Overstreet } 1201cafe5635SKent Overstreet 1202cafe5635SKent Overstreet #define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k) 1203cafe5635SKent Overstreet 1204a1f0358bSKent Overstreet static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc) 1205cafe5635SKent Overstreet { 1206cafe5635SKent Overstreet uint8_t stale = 0; 1207a1f0358bSKent Overstreet unsigned keys = 0, good_keys = 0; 1208cafe5635SKent Overstreet struct bkey *k; 1209cafe5635SKent Overstreet struct btree_iter iter; 1210cafe5635SKent Overstreet struct bset_tree *t; 1211cafe5635SKent Overstreet 1212cafe5635SKent Overstreet gc->nodes++; 1213cafe5635SKent Overstreet 1214cafe5635SKent Overstreet for_each_key_filter(b, k, &iter, bch_ptr_invalid) { 1215cafe5635SKent Overstreet stale = max(stale, btree_mark_key(b, k)); 1216a1f0358bSKent Overstreet keys++; 1217cafe5635SKent Overstreet 1218cafe5635SKent Overstreet if (bch_ptr_bad(b, k)) 1219cafe5635SKent Overstreet continue; 1220cafe5635SKent Overstreet 1221cafe5635SKent Overstreet gc->key_bytes += bkey_u64s(k); 1222cafe5635SKent Overstreet gc->nkeys++; 1223a1f0358bSKent Overstreet good_keys++; 1224cafe5635SKent Overstreet 1225cafe5635SKent Overstreet gc->data += KEY_SIZE(k); 1226cafe5635SKent Overstreet } 1227cafe5635SKent Overstreet 1228cafe5635SKent Overstreet for (t = b->sets; t <= &b->sets[b->nsets]; t++) 1229cafe5635SKent Overstreet btree_bug_on(t->size && 1230cafe5635SKent Overstreet bset_written(b, t) && 1231cafe5635SKent Overstreet bkey_cmp(&b->key, &t->end) < 0, 1232cafe5635SKent Overstreet b, "found short btree key in gc"); 1233cafe5635SKent Overstreet 1234a1f0358bSKent Overstreet if (b->c->gc_always_rewrite) 1235a1f0358bSKent Overstreet return true; 1236a1f0358bSKent Overstreet 1237a1f0358bSKent Overstreet if (stale > 10) 1238a1f0358bSKent Overstreet return true; 1239a1f0358bSKent Overstreet 1240a1f0358bSKent Overstreet if ((keys - good_keys) * 2 > keys) 1241a1f0358bSKent Overstreet return true; 1242a1f0358bSKent Overstreet 1243a1f0358bSKent Overstreet return false; 1244cafe5635SKent Overstreet } 1245cafe5635SKent Overstreet 1246a1f0358bSKent Overstreet #define GC_MERGE_NODES 4U 1247cafe5635SKent Overstreet 1248cafe5635SKent Overstreet struct gc_merge_info { 1249cafe5635SKent Overstreet struct btree *b; 1250cafe5635SKent Overstreet unsigned keys; 1251cafe5635SKent Overstreet }; 1252cafe5635SKent Overstreet 1253a1f0358bSKent Overstreet static int bch_btree_insert_node(struct btree *, struct btree_op *, 1254a1f0358bSKent Overstreet struct keylist *, atomic_t *, struct bkey *); 1255a1f0358bSKent Overstreet 1256a1f0358bSKent Overstreet static int btree_gc_coalesce(struct btree *b, struct btree_op *op, 1257a1f0358bSKent Overstreet struct keylist *keylist, struct gc_stat *gc, 1258e8e1d468SKent Overstreet struct gc_merge_info *r) 1259cafe5635SKent Overstreet { 1260a1f0358bSKent Overstreet unsigned i, nodes = 0, keys = 0, blocks; 1261a1f0358bSKent Overstreet struct btree *new_nodes[GC_MERGE_NODES]; 1262b54d6934SKent Overstreet struct closure cl; 1263a1f0358bSKent Overstreet struct bkey *k; 1264b54d6934SKent Overstreet 1265a1f0358bSKent Overstreet memset(new_nodes, 0, sizeof(new_nodes)); 1266b54d6934SKent Overstreet closure_init_stack(&cl); 1267cafe5635SKent Overstreet 1268a1f0358bSKent Overstreet while (nodes < GC_MERGE_NODES && !IS_ERR_OR_NULL(r[nodes].b)) 1269cafe5635SKent Overstreet keys += r[nodes++].keys; 1270cafe5635SKent Overstreet 1271cafe5635SKent Overstreet blocks = btree_default_blocks(b->c) * 2 / 3; 1272cafe5635SKent Overstreet 1273cafe5635SKent Overstreet if (nodes < 2 || 1274ee811287SKent Overstreet __set_blocks(b->sets[0].data, keys, 1275ee811287SKent Overstreet block_bytes(b->c)) > blocks * (nodes - 1)) 1276a1f0358bSKent Overstreet return 0; 1277cafe5635SKent Overstreet 1278a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 1279bc9389eeSKent Overstreet new_nodes[i] = btree_node_alloc_replacement(r[i].b, false); 1280a1f0358bSKent Overstreet if (IS_ERR_OR_NULL(new_nodes[i])) 1281a1f0358bSKent Overstreet goto out_nocoalesce; 1282cafe5635SKent Overstreet } 1283cafe5635SKent Overstreet 1284cafe5635SKent Overstreet for (i = nodes - 1; i > 0; --i) { 1285ee811287SKent Overstreet struct bset *n1 = btree_bset_first(new_nodes[i]); 1286ee811287SKent Overstreet struct bset *n2 = btree_bset_first(new_nodes[i - 1]); 1287cafe5635SKent Overstreet struct bkey *k, *last = NULL; 1288cafe5635SKent Overstreet 1289cafe5635SKent Overstreet keys = 0; 1290cafe5635SKent Overstreet 1291a1f0358bSKent Overstreet if (i > 1) { 1292cafe5635SKent Overstreet for (k = n2->start; 1293fafff81cSKent Overstreet k < bset_bkey_last(n2); 1294cafe5635SKent Overstreet k = bkey_next(k)) { 1295cafe5635SKent Overstreet if (__set_blocks(n1, n1->keys + keys + 1296ee811287SKent Overstreet bkey_u64s(k), 1297ee811287SKent Overstreet block_bytes(b->c)) > blocks) 1298cafe5635SKent Overstreet break; 1299cafe5635SKent Overstreet 1300cafe5635SKent Overstreet last = k; 1301cafe5635SKent Overstreet keys += bkey_u64s(k); 1302cafe5635SKent Overstreet } 1303a1f0358bSKent Overstreet } else { 1304a1f0358bSKent Overstreet /* 1305a1f0358bSKent Overstreet * Last node we're not getting rid of - we're getting 1306a1f0358bSKent Overstreet * rid of the node at r[0]. Have to try and fit all of 1307a1f0358bSKent Overstreet * the remaining keys into this node; we can't ensure 1308a1f0358bSKent Overstreet * they will always fit due to rounding and variable 1309a1f0358bSKent Overstreet * length keys (shouldn't be possible in practice, 1310a1f0358bSKent Overstreet * though) 1311a1f0358bSKent Overstreet */ 1312a1f0358bSKent Overstreet if (__set_blocks(n1, n1->keys + n2->keys, 1313ee811287SKent Overstreet block_bytes(b->c)) > 1314ee811287SKent Overstreet btree_blocks(new_nodes[i])) 1315a1f0358bSKent Overstreet goto out_nocoalesce; 1316a1f0358bSKent Overstreet 1317a1f0358bSKent Overstreet keys = n2->keys; 1318a1f0358bSKent Overstreet /* Take the key of the node we're getting rid of */ 1319a1f0358bSKent Overstreet last = &r->b->key; 1320a1f0358bSKent Overstreet } 1321cafe5635SKent Overstreet 1322ee811287SKent Overstreet BUG_ON(__set_blocks(n1, n1->keys + keys, block_bytes(b->c)) > 1323ee811287SKent Overstreet btree_blocks(new_nodes[i])); 1324cafe5635SKent Overstreet 1325a1f0358bSKent Overstreet if (last) 1326a1f0358bSKent Overstreet bkey_copy_key(&new_nodes[i]->key, last); 1327cafe5635SKent Overstreet 1328fafff81cSKent Overstreet memcpy(bset_bkey_last(n1), 1329cafe5635SKent Overstreet n2->start, 1330fafff81cSKent Overstreet (void *) bset_bkey_idx(n2, keys) - (void *) n2->start); 1331cafe5635SKent Overstreet 1332cafe5635SKent Overstreet n1->keys += keys; 1333a1f0358bSKent Overstreet r[i].keys = n1->keys; 1334cafe5635SKent Overstreet 1335cafe5635SKent Overstreet memmove(n2->start, 1336fafff81cSKent Overstreet bset_bkey_idx(n2, keys), 1337fafff81cSKent Overstreet (void *) bset_bkey_last(n2) - 1338fafff81cSKent Overstreet (void *) bset_bkey_idx(n2, keys)); 1339cafe5635SKent Overstreet 1340cafe5635SKent Overstreet n2->keys -= keys; 1341cafe5635SKent Overstreet 1342085d2a3dSKent Overstreet if (__bch_keylist_realloc(keylist, 1343085d2a3dSKent Overstreet bkey_u64s(&new_nodes[i]->key))) 1344a1f0358bSKent Overstreet goto out_nocoalesce; 1345a1f0358bSKent Overstreet 1346a1f0358bSKent Overstreet bch_btree_node_write(new_nodes[i], &cl); 1347a1f0358bSKent Overstreet bch_keylist_add(keylist, &new_nodes[i]->key); 1348cafe5635SKent Overstreet } 1349cafe5635SKent Overstreet 1350a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 1351085d2a3dSKent Overstreet if (__bch_keylist_realloc(keylist, bkey_u64s(&r[i].b->key))) 1352a1f0358bSKent Overstreet goto out_nocoalesce; 1353a1f0358bSKent Overstreet 1354a1f0358bSKent Overstreet make_btree_freeing_key(r[i].b, keylist->top); 1355a1f0358bSKent Overstreet bch_keylist_push(keylist); 1356a1f0358bSKent Overstreet } 1357a1f0358bSKent Overstreet 1358a1f0358bSKent Overstreet /* We emptied out this node */ 1359ee811287SKent Overstreet BUG_ON(btree_bset_first(new_nodes[0])->keys); 1360a1f0358bSKent Overstreet btree_node_free(new_nodes[0]); 1361a1f0358bSKent Overstreet rw_unlock(true, new_nodes[0]); 1362a1f0358bSKent Overstreet 1363a1f0358bSKent Overstreet closure_sync(&cl); 1364a1f0358bSKent Overstreet 1365a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 1366a1f0358bSKent Overstreet btree_node_free(r[i].b); 1367a1f0358bSKent Overstreet rw_unlock(true, r[i].b); 1368a1f0358bSKent Overstreet 1369a1f0358bSKent Overstreet r[i].b = new_nodes[i]; 1370a1f0358bSKent Overstreet } 1371a1f0358bSKent Overstreet 1372a1f0358bSKent Overstreet bch_btree_insert_node(b, op, keylist, NULL, NULL); 1373a1f0358bSKent Overstreet BUG_ON(!bch_keylist_empty(keylist)); 1374a1f0358bSKent Overstreet 1375a1f0358bSKent Overstreet memmove(r, r + 1, sizeof(r[0]) * (nodes - 1)); 1376a1f0358bSKent Overstreet r[nodes - 1].b = ERR_PTR(-EINTR); 1377cafe5635SKent Overstreet 1378c37511b8SKent Overstreet trace_bcache_btree_gc_coalesce(nodes); 1379cafe5635SKent Overstreet gc->nodes--; 1380cafe5635SKent Overstreet 1381a1f0358bSKent Overstreet /* Invalidated our iterator */ 1382a1f0358bSKent Overstreet return -EINTR; 1383a1f0358bSKent Overstreet 1384a1f0358bSKent Overstreet out_nocoalesce: 1385a1f0358bSKent Overstreet closure_sync(&cl); 1386a1f0358bSKent Overstreet 1387a1f0358bSKent Overstreet while ((k = bch_keylist_pop(keylist))) 1388a1f0358bSKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1389a1f0358bSKent Overstreet atomic_dec(&b->c->prio_blocked); 1390a1f0358bSKent Overstreet 1391a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) 1392a1f0358bSKent Overstreet if (!IS_ERR_OR_NULL(new_nodes[i])) { 1393a1f0358bSKent Overstreet btree_node_free(new_nodes[i]); 1394a1f0358bSKent Overstreet rw_unlock(true, new_nodes[i]); 1395a1f0358bSKent Overstreet } 1396a1f0358bSKent Overstreet return 0; 1397a1f0358bSKent Overstreet } 1398a1f0358bSKent Overstreet 1399a1f0358bSKent Overstreet static unsigned btree_gc_count_keys(struct btree *b) 1400a1f0358bSKent Overstreet { 1401a1f0358bSKent Overstreet struct bkey *k; 1402a1f0358bSKent Overstreet struct btree_iter iter; 1403a1f0358bSKent Overstreet unsigned ret = 0; 1404a1f0358bSKent Overstreet 1405a1f0358bSKent Overstreet for_each_key_filter(b, k, &iter, bch_ptr_bad) 1406a1f0358bSKent Overstreet ret += bkey_u64s(k); 1407a1f0358bSKent Overstreet 1408a1f0358bSKent Overstreet return ret; 1409cafe5635SKent Overstreet } 1410cafe5635SKent Overstreet 1411cafe5635SKent Overstreet static int btree_gc_recurse(struct btree *b, struct btree_op *op, 1412cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1413cafe5635SKent Overstreet { 1414cafe5635SKent Overstreet unsigned i; 1415a1f0358bSKent Overstreet int ret = 0; 1416a1f0358bSKent Overstreet bool should_rewrite; 1417a1f0358bSKent Overstreet struct btree *n; 1418a1f0358bSKent Overstreet struct bkey *k; 1419a1f0358bSKent Overstreet struct keylist keys; 1420a1f0358bSKent Overstreet struct btree_iter iter; 1421cafe5635SKent Overstreet struct gc_merge_info r[GC_MERGE_NODES]; 1422a1f0358bSKent Overstreet struct gc_merge_info *last = r + GC_MERGE_NODES - 1; 1423cafe5635SKent Overstreet 1424a1f0358bSKent Overstreet bch_keylist_init(&keys); 1425a1f0358bSKent Overstreet bch_btree_iter_init(b, &iter, &b->c->gc_done); 1426cafe5635SKent Overstreet 1427a1f0358bSKent Overstreet for (i = 0; i < GC_MERGE_NODES; i++) 1428a1f0358bSKent Overstreet r[i].b = ERR_PTR(-EINTR); 1429cafe5635SKent Overstreet 1430a1f0358bSKent Overstreet while (1) { 1431a1f0358bSKent Overstreet k = bch_btree_iter_next_filter(&iter, b, bch_ptr_bad); 1432a1f0358bSKent Overstreet if (k) { 1433a1f0358bSKent Overstreet r->b = bch_btree_node_get(b->c, k, b->level - 1, true); 1434cafe5635SKent Overstreet if (IS_ERR(r->b)) { 1435cafe5635SKent Overstreet ret = PTR_ERR(r->b); 1436cafe5635SKent Overstreet break; 1437cafe5635SKent Overstreet } 1438cafe5635SKent Overstreet 1439a1f0358bSKent Overstreet r->keys = btree_gc_count_keys(r->b); 1440cafe5635SKent Overstreet 1441a1f0358bSKent Overstreet ret = btree_gc_coalesce(b, op, &keys, gc, r); 1442a1f0358bSKent Overstreet if (ret) 1443cafe5635SKent Overstreet break; 1444cafe5635SKent Overstreet } 1445cafe5635SKent Overstreet 1446a1f0358bSKent Overstreet if (!last->b) 1447a1f0358bSKent Overstreet break; 1448cafe5635SKent Overstreet 1449a1f0358bSKent Overstreet if (!IS_ERR(last->b)) { 1450a1f0358bSKent Overstreet should_rewrite = btree_gc_mark_node(last->b, gc); 145178365411SKent Overstreet if (should_rewrite && 145278365411SKent Overstreet !btree_check_reserve(b, NULL)) { 1453bc9389eeSKent Overstreet n = btree_node_alloc_replacement(last->b, 1454bc9389eeSKent Overstreet false); 1455cafe5635SKent Overstreet 1456a1f0358bSKent Overstreet if (!IS_ERR_OR_NULL(n)) { 1457a1f0358bSKent Overstreet bch_btree_node_write_sync(n); 1458a1f0358bSKent Overstreet bch_keylist_add(&keys, &n->key); 1459cafe5635SKent Overstreet 1460a1f0358bSKent Overstreet make_btree_freeing_key(last->b, 1461a1f0358bSKent Overstreet keys.top); 1462a1f0358bSKent Overstreet bch_keylist_push(&keys); 1463cafe5635SKent Overstreet 1464a1f0358bSKent Overstreet btree_node_free(last->b); 1465a1f0358bSKent Overstreet 1466a1f0358bSKent Overstreet bch_btree_insert_node(b, op, &keys, 1467a1f0358bSKent Overstreet NULL, NULL); 1468a1f0358bSKent Overstreet BUG_ON(!bch_keylist_empty(&keys)); 1469a1f0358bSKent Overstreet 1470a1f0358bSKent Overstreet rw_unlock(true, last->b); 1471a1f0358bSKent Overstreet last->b = n; 1472a1f0358bSKent Overstreet 1473a1f0358bSKent Overstreet /* Invalidated our iterator */ 1474a1f0358bSKent Overstreet ret = -EINTR; 1475a1f0358bSKent Overstreet break; 1476a1f0358bSKent Overstreet } 1477a1f0358bSKent Overstreet } 1478a1f0358bSKent Overstreet 1479a1f0358bSKent Overstreet if (last->b->level) { 1480a1f0358bSKent Overstreet ret = btree_gc_recurse(last->b, op, writes, gc); 1481a1f0358bSKent Overstreet if (ret) 1482a1f0358bSKent Overstreet break; 1483a1f0358bSKent Overstreet } 1484a1f0358bSKent Overstreet 1485a1f0358bSKent Overstreet bkey_copy_key(&b->c->gc_done, &last->b->key); 1486a1f0358bSKent Overstreet 1487a1f0358bSKent Overstreet /* 1488a1f0358bSKent Overstreet * Must flush leaf nodes before gc ends, since replace 1489a1f0358bSKent Overstreet * operations aren't journalled 1490cafe5635SKent Overstreet */ 1491a1f0358bSKent Overstreet if (btree_node_dirty(last->b)) 1492a1f0358bSKent Overstreet bch_btree_node_write(last->b, writes); 1493a1f0358bSKent Overstreet rw_unlock(true, last->b); 1494a1f0358bSKent Overstreet } 1495a1f0358bSKent Overstreet 1496a1f0358bSKent Overstreet memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1)); 1497a1f0358bSKent Overstreet r->b = NULL; 1498a1f0358bSKent Overstreet 1499cafe5635SKent Overstreet if (need_resched()) { 1500cafe5635SKent Overstreet ret = -EAGAIN; 1501cafe5635SKent Overstreet break; 1502cafe5635SKent Overstreet } 1503cafe5635SKent Overstreet } 1504cafe5635SKent Overstreet 1505a1f0358bSKent Overstreet for (i = 0; i < GC_MERGE_NODES; i++) 1506a1f0358bSKent Overstreet if (!IS_ERR_OR_NULL(r[i].b)) { 1507a1f0358bSKent Overstreet if (btree_node_dirty(r[i].b)) 1508a1f0358bSKent Overstreet bch_btree_node_write(r[i].b, writes); 1509a1f0358bSKent Overstreet rw_unlock(true, r[i].b); 1510a1f0358bSKent Overstreet } 1511cafe5635SKent Overstreet 1512a1f0358bSKent Overstreet bch_keylist_free(&keys); 1513cafe5635SKent Overstreet 1514cafe5635SKent Overstreet return ret; 1515cafe5635SKent Overstreet } 1516cafe5635SKent Overstreet 1517cafe5635SKent Overstreet static int bch_btree_gc_root(struct btree *b, struct btree_op *op, 1518cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1519cafe5635SKent Overstreet { 1520cafe5635SKent Overstreet struct btree *n = NULL; 1521a1f0358bSKent Overstreet int ret = 0; 1522a1f0358bSKent Overstreet bool should_rewrite; 1523cafe5635SKent Overstreet 1524a1f0358bSKent Overstreet should_rewrite = btree_gc_mark_node(b, gc); 1525a1f0358bSKent Overstreet if (should_rewrite) { 1526bc9389eeSKent Overstreet n = btree_node_alloc_replacement(b, false); 1527cafe5635SKent Overstreet 1528cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 1529a1f0358bSKent Overstreet bch_btree_node_write_sync(n); 1530a1f0358bSKent Overstreet bch_btree_set_root(n); 1531a1f0358bSKent Overstreet btree_node_free(b); 1532a1f0358bSKent Overstreet rw_unlock(true, n); 1533a1f0358bSKent Overstreet 1534a1f0358bSKent Overstreet return -EINTR; 1535cafe5635SKent Overstreet } 1536a1f0358bSKent Overstreet } 1537a1f0358bSKent Overstreet 1538a1f0358bSKent Overstreet if (b->level) { 1539a1f0358bSKent Overstreet ret = btree_gc_recurse(b, op, writes, gc); 1540a1f0358bSKent Overstreet if (ret) 1541a1f0358bSKent Overstreet return ret; 1542a1f0358bSKent Overstreet } 1543a1f0358bSKent Overstreet 1544a1f0358bSKent Overstreet bkey_copy_key(&b->c->gc_done, &b->key); 1545cafe5635SKent Overstreet 1546cafe5635SKent Overstreet return ret; 1547cafe5635SKent Overstreet } 1548cafe5635SKent Overstreet 1549cafe5635SKent Overstreet static void btree_gc_start(struct cache_set *c) 1550cafe5635SKent Overstreet { 1551cafe5635SKent Overstreet struct cache *ca; 1552cafe5635SKent Overstreet struct bucket *b; 1553cafe5635SKent Overstreet unsigned i; 1554cafe5635SKent Overstreet 1555cafe5635SKent Overstreet if (!c->gc_mark_valid) 1556cafe5635SKent Overstreet return; 1557cafe5635SKent Overstreet 1558cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1559cafe5635SKent Overstreet 1560cafe5635SKent Overstreet c->gc_mark_valid = 0; 1561cafe5635SKent Overstreet c->gc_done = ZERO_KEY; 1562cafe5635SKent Overstreet 1563cafe5635SKent Overstreet for_each_cache(ca, c, i) 1564cafe5635SKent Overstreet for_each_bucket(b, ca) { 1565cafe5635SKent Overstreet b->gc_gen = b->gen; 156629ebf465SKent Overstreet if (!atomic_read(&b->pin)) { 1567cafe5635SKent Overstreet SET_GC_MARK(b, GC_MARK_RECLAIMABLE); 156829ebf465SKent Overstreet SET_GC_SECTORS_USED(b, 0); 156929ebf465SKent Overstreet } 1570cafe5635SKent Overstreet } 1571cafe5635SKent Overstreet 1572cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1573cafe5635SKent Overstreet } 1574cafe5635SKent Overstreet 1575cafe5635SKent Overstreet size_t bch_btree_gc_finish(struct cache_set *c) 1576cafe5635SKent Overstreet { 1577cafe5635SKent Overstreet size_t available = 0; 1578cafe5635SKent Overstreet struct bucket *b; 1579cafe5635SKent Overstreet struct cache *ca; 1580cafe5635SKent Overstreet unsigned i; 1581cafe5635SKent Overstreet 1582cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1583cafe5635SKent Overstreet 1584cafe5635SKent Overstreet set_gc_sectors(c); 1585cafe5635SKent Overstreet c->gc_mark_valid = 1; 1586cafe5635SKent Overstreet c->need_gc = 0; 1587cafe5635SKent Overstreet 1588cafe5635SKent Overstreet if (c->root) 1589cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&c->root->key); i++) 1590cafe5635SKent Overstreet SET_GC_MARK(PTR_BUCKET(c, &c->root->key, i), 1591cafe5635SKent Overstreet GC_MARK_METADATA); 1592cafe5635SKent Overstreet 1593cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&c->uuid_bucket); i++) 1594cafe5635SKent Overstreet SET_GC_MARK(PTR_BUCKET(c, &c->uuid_bucket, i), 1595cafe5635SKent Overstreet GC_MARK_METADATA); 1596cafe5635SKent Overstreet 1597bf0a628aSNicholas Swenson /* don't reclaim buckets to which writeback keys point */ 1598bf0a628aSNicholas Swenson rcu_read_lock(); 1599bf0a628aSNicholas Swenson for (i = 0; i < c->nr_uuids; i++) { 1600bf0a628aSNicholas Swenson struct bcache_device *d = c->devices[i]; 1601bf0a628aSNicholas Swenson struct cached_dev *dc; 1602bf0a628aSNicholas Swenson struct keybuf_key *w, *n; 1603bf0a628aSNicholas Swenson unsigned j; 1604bf0a628aSNicholas Swenson 1605bf0a628aSNicholas Swenson if (!d || UUID_FLASH_ONLY(&c->uuids[i])) 1606bf0a628aSNicholas Swenson continue; 1607bf0a628aSNicholas Swenson dc = container_of(d, struct cached_dev, disk); 1608bf0a628aSNicholas Swenson 1609bf0a628aSNicholas Swenson spin_lock(&dc->writeback_keys.lock); 1610bf0a628aSNicholas Swenson rbtree_postorder_for_each_entry_safe(w, n, 1611bf0a628aSNicholas Swenson &dc->writeback_keys.keys, node) 1612bf0a628aSNicholas Swenson for (j = 0; j < KEY_PTRS(&w->key); j++) 1613bf0a628aSNicholas Swenson SET_GC_MARK(PTR_BUCKET(c, &w->key, j), 1614bf0a628aSNicholas Swenson GC_MARK_DIRTY); 1615bf0a628aSNicholas Swenson spin_unlock(&dc->writeback_keys.lock); 1616bf0a628aSNicholas Swenson } 1617bf0a628aSNicholas Swenson rcu_read_unlock(); 1618bf0a628aSNicholas Swenson 1619cafe5635SKent Overstreet for_each_cache(ca, c, i) { 1620cafe5635SKent Overstreet uint64_t *i; 1621cafe5635SKent Overstreet 1622cafe5635SKent Overstreet ca->invalidate_needs_gc = 0; 1623cafe5635SKent Overstreet 1624cafe5635SKent Overstreet for (i = ca->sb.d; i < ca->sb.d + ca->sb.keys; i++) 1625cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1626cafe5635SKent Overstreet 1627cafe5635SKent Overstreet for (i = ca->prio_buckets; 1628cafe5635SKent Overstreet i < ca->prio_buckets + prio_buckets(ca) * 2; i++) 1629cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1630cafe5635SKent Overstreet 1631cafe5635SKent Overstreet for_each_bucket(b, ca) { 1632cafe5635SKent Overstreet b->last_gc = b->gc_gen; 1633cafe5635SKent Overstreet c->need_gc = max(c->need_gc, bucket_gc_gen(b)); 1634cafe5635SKent Overstreet 1635cafe5635SKent Overstreet if (!atomic_read(&b->pin) && 1636cafe5635SKent Overstreet GC_MARK(b) == GC_MARK_RECLAIMABLE) { 1637cafe5635SKent Overstreet available++; 1638cafe5635SKent Overstreet if (!GC_SECTORS_USED(b)) 1639cafe5635SKent Overstreet bch_bucket_add_unused(ca, b); 1640cafe5635SKent Overstreet } 1641cafe5635SKent Overstreet } 1642cafe5635SKent Overstreet } 1643cafe5635SKent Overstreet 1644cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1645cafe5635SKent Overstreet return available; 1646cafe5635SKent Overstreet } 1647cafe5635SKent Overstreet 164872a44517SKent Overstreet static void bch_btree_gc(struct cache_set *c) 1649cafe5635SKent Overstreet { 1650cafe5635SKent Overstreet int ret; 1651cafe5635SKent Overstreet unsigned long available; 1652cafe5635SKent Overstreet struct gc_stat stats; 1653cafe5635SKent Overstreet struct closure writes; 1654cafe5635SKent Overstreet struct btree_op op; 1655cafe5635SKent Overstreet uint64_t start_time = local_clock(); 165657943511SKent Overstreet 1657c37511b8SKent Overstreet trace_bcache_gc_start(c); 1658cafe5635SKent Overstreet 1659cafe5635SKent Overstreet memset(&stats, 0, sizeof(struct gc_stat)); 1660cafe5635SKent Overstreet closure_init_stack(&writes); 1661b54d6934SKent Overstreet bch_btree_op_init(&op, SHRT_MAX); 1662cafe5635SKent Overstreet 1663cafe5635SKent Overstreet btree_gc_start(c); 1664cafe5635SKent Overstreet 1665a1f0358bSKent Overstreet do { 1666cafe5635SKent Overstreet ret = btree_root(gc_root, c, &op, &writes, &stats); 1667cafe5635SKent Overstreet closure_sync(&writes); 1668cafe5635SKent Overstreet 1669a1f0358bSKent Overstreet if (ret && ret != -EAGAIN) 1670cafe5635SKent Overstreet pr_warn("gc failed!"); 1671a1f0358bSKent Overstreet } while (ret); 1672cafe5635SKent Overstreet 1673cafe5635SKent Overstreet available = bch_btree_gc_finish(c); 167457943511SKent Overstreet wake_up_allocators(c); 167557943511SKent Overstreet 1676169ef1cfSKent Overstreet bch_time_stats_update(&c->btree_gc_time, start_time); 1677cafe5635SKent Overstreet 1678cafe5635SKent Overstreet stats.key_bytes *= sizeof(uint64_t); 1679cafe5635SKent Overstreet stats.data <<= 9; 1680cafe5635SKent Overstreet stats.in_use = (c->nbuckets - available) * 100 / c->nbuckets; 1681cafe5635SKent Overstreet memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat)); 1682cafe5635SKent Overstreet 1683c37511b8SKent Overstreet trace_bcache_gc_end(c); 1684cafe5635SKent Overstreet 168572a44517SKent Overstreet bch_moving_gc(c); 1686cafe5635SKent Overstreet } 1687cafe5635SKent Overstreet 168872a44517SKent Overstreet static int bch_gc_thread(void *arg) 1689cafe5635SKent Overstreet { 169072a44517SKent Overstreet struct cache_set *c = arg; 1691a1f0358bSKent Overstreet struct cache *ca; 1692a1f0358bSKent Overstreet unsigned i; 169372a44517SKent Overstreet 169472a44517SKent Overstreet while (1) { 1695a1f0358bSKent Overstreet again: 169672a44517SKent Overstreet bch_btree_gc(c); 169772a44517SKent Overstreet 169872a44517SKent Overstreet set_current_state(TASK_INTERRUPTIBLE); 169972a44517SKent Overstreet if (kthread_should_stop()) 170072a44517SKent Overstreet break; 170172a44517SKent Overstreet 1702a1f0358bSKent Overstreet mutex_lock(&c->bucket_lock); 1703a1f0358bSKent Overstreet 1704a1f0358bSKent Overstreet for_each_cache(ca, c, i) 1705a1f0358bSKent Overstreet if (ca->invalidate_needs_gc) { 1706a1f0358bSKent Overstreet mutex_unlock(&c->bucket_lock); 1707a1f0358bSKent Overstreet set_current_state(TASK_RUNNING); 1708a1f0358bSKent Overstreet goto again; 1709a1f0358bSKent Overstreet } 1710a1f0358bSKent Overstreet 1711a1f0358bSKent Overstreet mutex_unlock(&c->bucket_lock); 1712a1f0358bSKent Overstreet 171372a44517SKent Overstreet try_to_freeze(); 171472a44517SKent Overstreet schedule(); 171572a44517SKent Overstreet } 171672a44517SKent Overstreet 171772a44517SKent Overstreet return 0; 171872a44517SKent Overstreet } 171972a44517SKent Overstreet 172072a44517SKent Overstreet int bch_gc_thread_start(struct cache_set *c) 172172a44517SKent Overstreet { 172272a44517SKent Overstreet c->gc_thread = kthread_create(bch_gc_thread, c, "bcache_gc"); 172372a44517SKent Overstreet if (IS_ERR(c->gc_thread)) 172472a44517SKent Overstreet return PTR_ERR(c->gc_thread); 172572a44517SKent Overstreet 172672a44517SKent Overstreet set_task_state(c->gc_thread, TASK_INTERRUPTIBLE); 172772a44517SKent Overstreet return 0; 1728cafe5635SKent Overstreet } 1729cafe5635SKent Overstreet 1730cafe5635SKent Overstreet /* Initial partial gc */ 1731cafe5635SKent Overstreet 1732cafe5635SKent Overstreet static int bch_btree_check_recurse(struct btree *b, struct btree_op *op, 1733cafe5635SKent Overstreet unsigned long **seen) 1734cafe5635SKent Overstreet { 173550310164SKent Overstreet int ret = 0; 1736cafe5635SKent Overstreet unsigned i; 173750310164SKent Overstreet struct bkey *k, *p = NULL; 1738cafe5635SKent Overstreet struct bucket *g; 1739cafe5635SKent Overstreet struct btree_iter iter; 1740cafe5635SKent Overstreet 1741cafe5635SKent Overstreet for_each_key_filter(b, k, &iter, bch_ptr_invalid) { 1742cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) { 1743cafe5635SKent Overstreet if (!ptr_available(b->c, k, i)) 1744cafe5635SKent Overstreet continue; 1745cafe5635SKent Overstreet 1746cafe5635SKent Overstreet g = PTR_BUCKET(b->c, k, i); 1747cafe5635SKent Overstreet 1748cafe5635SKent Overstreet if (!__test_and_set_bit(PTR_BUCKET_NR(b->c, k, i), 1749cafe5635SKent Overstreet seen[PTR_DEV(k, i)]) || 1750cafe5635SKent Overstreet !ptr_stale(b->c, k, i)) { 1751cafe5635SKent Overstreet g->gen = PTR_GEN(k, i); 1752cafe5635SKent Overstreet 1753cafe5635SKent Overstreet if (b->level) 1754cafe5635SKent Overstreet g->prio = BTREE_PRIO; 1755cafe5635SKent Overstreet else if (g->prio == BTREE_PRIO) 1756cafe5635SKent Overstreet g->prio = INITIAL_PRIO; 1757cafe5635SKent Overstreet } 1758cafe5635SKent Overstreet } 1759cafe5635SKent Overstreet 1760cafe5635SKent Overstreet btree_mark_key(b, k); 1761cafe5635SKent Overstreet } 1762cafe5635SKent Overstreet 1763cafe5635SKent Overstreet if (b->level) { 176450310164SKent Overstreet bch_btree_iter_init(b, &iter, NULL); 1765cafe5635SKent Overstreet 176650310164SKent Overstreet do { 176750310164SKent Overstreet k = bch_btree_iter_next_filter(&iter, b, bch_ptr_bad); 176850310164SKent Overstreet if (k) 176950310164SKent Overstreet btree_node_prefetch(b->c, k, b->level - 1); 177050310164SKent Overstreet 1771cafe5635SKent Overstreet if (p) 177250310164SKent Overstreet ret = btree(check_recurse, p, b, op, seen); 1773cafe5635SKent Overstreet 177450310164SKent Overstreet p = k; 177550310164SKent Overstreet } while (p && !ret); 1776cafe5635SKent Overstreet } 1777cafe5635SKent Overstreet 1778cafe5635SKent Overstreet return 0; 1779cafe5635SKent Overstreet } 1780cafe5635SKent Overstreet 1781c18536a7SKent Overstreet int bch_btree_check(struct cache_set *c) 1782cafe5635SKent Overstreet { 1783cafe5635SKent Overstreet int ret = -ENOMEM; 1784cafe5635SKent Overstreet unsigned i; 1785cafe5635SKent Overstreet unsigned long *seen[MAX_CACHES_PER_SET]; 1786c18536a7SKent Overstreet struct btree_op op; 1787cafe5635SKent Overstreet 1788cafe5635SKent Overstreet memset(seen, 0, sizeof(seen)); 1789b54d6934SKent Overstreet bch_btree_op_init(&op, SHRT_MAX); 1790cafe5635SKent Overstreet 1791cafe5635SKent Overstreet for (i = 0; c->cache[i]; i++) { 1792cafe5635SKent Overstreet size_t n = DIV_ROUND_UP(c->cache[i]->sb.nbuckets, 8); 1793cafe5635SKent Overstreet seen[i] = kmalloc(n, GFP_KERNEL); 1794cafe5635SKent Overstreet if (!seen[i]) 1795cafe5635SKent Overstreet goto err; 1796cafe5635SKent Overstreet 1797cafe5635SKent Overstreet /* Disables the seen array until prio_read() uses it too */ 1798cafe5635SKent Overstreet memset(seen[i], 0xFF, n); 1799cafe5635SKent Overstreet } 1800cafe5635SKent Overstreet 1801c18536a7SKent Overstreet ret = btree_root(check_recurse, c, &op, seen); 1802cafe5635SKent Overstreet err: 1803cafe5635SKent Overstreet for (i = 0; i < MAX_CACHES_PER_SET; i++) 1804cafe5635SKent Overstreet kfree(seen[i]); 1805cafe5635SKent Overstreet return ret; 1806cafe5635SKent Overstreet } 1807cafe5635SKent Overstreet 1808cafe5635SKent Overstreet /* Btree insertion */ 1809cafe5635SKent Overstreet 18101b207d80SKent Overstreet static bool fix_overlapping_extents(struct btree *b, struct bkey *insert, 1811cafe5635SKent Overstreet struct btree_iter *iter, 18121b207d80SKent Overstreet struct bkey *replace_key) 1813cafe5635SKent Overstreet { 1814279afbadSKent Overstreet void subtract_dirty(struct bkey *k, uint64_t offset, int sectors) 1815cafe5635SKent Overstreet { 1816279afbadSKent Overstreet if (KEY_DIRTY(k)) 1817279afbadSKent Overstreet bcache_dev_sectors_dirty_add(b->c, KEY_INODE(k), 1818279afbadSKent Overstreet offset, -sectors); 1819cafe5635SKent Overstreet } 1820cafe5635SKent Overstreet 1821279afbadSKent Overstreet uint64_t old_offset; 1822cafe5635SKent Overstreet unsigned old_size, sectors_found = 0; 1823cafe5635SKent Overstreet 1824cafe5635SKent Overstreet while (1) { 1825cafe5635SKent Overstreet struct bkey *k = bch_btree_iter_next(iter); 1826911c9610SKent Overstreet if (!k) 1827cafe5635SKent Overstreet break; 1828cafe5635SKent Overstreet 1829911c9610SKent Overstreet if (bkey_cmp(&START_KEY(k), insert) >= 0) { 1830911c9610SKent Overstreet if (KEY_SIZE(k)) 1831911c9610SKent Overstreet break; 1832911c9610SKent Overstreet else 1833911c9610SKent Overstreet continue; 1834911c9610SKent Overstreet } 1835911c9610SKent Overstreet 1836cafe5635SKent Overstreet if (bkey_cmp(k, &START_KEY(insert)) <= 0) 1837cafe5635SKent Overstreet continue; 1838cafe5635SKent Overstreet 1839279afbadSKent Overstreet old_offset = KEY_START(k); 1840cafe5635SKent Overstreet old_size = KEY_SIZE(k); 1841cafe5635SKent Overstreet 1842cafe5635SKent Overstreet /* 1843cafe5635SKent Overstreet * We might overlap with 0 size extents; we can't skip these 1844cafe5635SKent Overstreet * because if they're in the set we're inserting to we have to 1845cafe5635SKent Overstreet * adjust them so they don't overlap with the key we're 18461b207d80SKent Overstreet * inserting. But we don't want to check them for replace 1847cafe5635SKent Overstreet * operations. 1848cafe5635SKent Overstreet */ 1849cafe5635SKent Overstreet 18501b207d80SKent Overstreet if (replace_key && KEY_SIZE(k)) { 1851cafe5635SKent Overstreet /* 1852cafe5635SKent Overstreet * k might have been split since we inserted/found the 1853cafe5635SKent Overstreet * key we're replacing 1854cafe5635SKent Overstreet */ 1855cafe5635SKent Overstreet unsigned i; 1856cafe5635SKent Overstreet uint64_t offset = KEY_START(k) - 18571b207d80SKent Overstreet KEY_START(replace_key); 1858cafe5635SKent Overstreet 1859cafe5635SKent Overstreet /* But it must be a subset of the replace key */ 18601b207d80SKent Overstreet if (KEY_START(k) < KEY_START(replace_key) || 18611b207d80SKent Overstreet KEY_OFFSET(k) > KEY_OFFSET(replace_key)) 1862cafe5635SKent Overstreet goto check_failed; 1863cafe5635SKent Overstreet 1864cafe5635SKent Overstreet /* We didn't find a key that we were supposed to */ 1865cafe5635SKent Overstreet if (KEY_START(k) > KEY_START(insert) + sectors_found) 1866cafe5635SKent Overstreet goto check_failed; 1867cafe5635SKent Overstreet 1868d24a6e10SKent Overstreet if (KEY_PTRS(k) != KEY_PTRS(replace_key) || 1869d24a6e10SKent Overstreet KEY_DIRTY(k) != KEY_DIRTY(replace_key)) 1870cafe5635SKent Overstreet goto check_failed; 1871cafe5635SKent Overstreet 1872cafe5635SKent Overstreet /* skip past gen */ 1873cafe5635SKent Overstreet offset <<= 8; 1874cafe5635SKent Overstreet 18751b207d80SKent Overstreet BUG_ON(!KEY_PTRS(replace_key)); 1876cafe5635SKent Overstreet 18771b207d80SKent Overstreet for (i = 0; i < KEY_PTRS(replace_key); i++) 18781b207d80SKent Overstreet if (k->ptr[i] != replace_key->ptr[i] + offset) 1879cafe5635SKent Overstreet goto check_failed; 1880cafe5635SKent Overstreet 1881cafe5635SKent Overstreet sectors_found = KEY_OFFSET(k) - KEY_START(insert); 1882cafe5635SKent Overstreet } 1883cafe5635SKent Overstreet 1884cafe5635SKent Overstreet if (bkey_cmp(insert, k) < 0 && 1885cafe5635SKent Overstreet bkey_cmp(&START_KEY(insert), &START_KEY(k)) > 0) { 1886cafe5635SKent Overstreet /* 1887cafe5635SKent Overstreet * We overlapped in the middle of an existing key: that 1888cafe5635SKent Overstreet * means we have to split the old key. But we have to do 1889cafe5635SKent Overstreet * slightly different things depending on whether the 1890cafe5635SKent Overstreet * old key has been written out yet. 1891cafe5635SKent Overstreet */ 1892cafe5635SKent Overstreet 1893cafe5635SKent Overstreet struct bkey *top; 1894cafe5635SKent Overstreet 1895279afbadSKent Overstreet subtract_dirty(k, KEY_START(insert), KEY_SIZE(insert)); 1896cafe5635SKent Overstreet 1897cafe5635SKent Overstreet if (bkey_written(b, k)) { 1898cafe5635SKent Overstreet /* 1899cafe5635SKent Overstreet * We insert a new key to cover the top of the 1900cafe5635SKent Overstreet * old key, and the old key is modified in place 1901cafe5635SKent Overstreet * to represent the bottom split. 1902cafe5635SKent Overstreet * 1903cafe5635SKent Overstreet * It's completely arbitrary whether the new key 1904cafe5635SKent Overstreet * is the top or the bottom, but it has to match 1905cafe5635SKent Overstreet * up with what btree_sort_fixup() does - it 1906cafe5635SKent Overstreet * doesn't check for this kind of overlap, it 1907cafe5635SKent Overstreet * depends on us inserting a new key for the top 1908cafe5635SKent Overstreet * here. 1909cafe5635SKent Overstreet */ 1910ee811287SKent Overstreet top = bch_bset_search(b, bset_tree_last(b), 1911cafe5635SKent Overstreet insert); 1912ee811287SKent Overstreet bch_bset_insert(b, top, k); 1913cafe5635SKent Overstreet } else { 1914cafe5635SKent Overstreet BKEY_PADDED(key) temp; 1915cafe5635SKent Overstreet bkey_copy(&temp.key, k); 1916ee811287SKent Overstreet bch_bset_insert(b, k, &temp.key); 1917cafe5635SKent Overstreet top = bkey_next(k); 1918cafe5635SKent Overstreet } 1919cafe5635SKent Overstreet 1920cafe5635SKent Overstreet bch_cut_front(insert, top); 1921cafe5635SKent Overstreet bch_cut_back(&START_KEY(insert), k); 1922cafe5635SKent Overstreet bch_bset_fix_invalidated_key(b, k); 1923cafe5635SKent Overstreet return false; 1924cafe5635SKent Overstreet } 1925cafe5635SKent Overstreet 1926cafe5635SKent Overstreet if (bkey_cmp(insert, k) < 0) { 1927cafe5635SKent Overstreet bch_cut_front(insert, k); 1928cafe5635SKent Overstreet } else { 19291fa8455dSKent Overstreet if (bkey_cmp(&START_KEY(insert), &START_KEY(k)) > 0) 19301fa8455dSKent Overstreet old_offset = KEY_START(insert); 19311fa8455dSKent Overstreet 1932cafe5635SKent Overstreet if (bkey_written(b, k) && 1933cafe5635SKent Overstreet bkey_cmp(&START_KEY(insert), &START_KEY(k)) <= 0) { 1934cafe5635SKent Overstreet /* 1935cafe5635SKent Overstreet * Completely overwrote, so we don't have to 1936cafe5635SKent Overstreet * invalidate the binary search tree 1937cafe5635SKent Overstreet */ 1938cafe5635SKent Overstreet bch_cut_front(k, k); 1939cafe5635SKent Overstreet } else { 1940cafe5635SKent Overstreet __bch_cut_back(&START_KEY(insert), k); 1941cafe5635SKent Overstreet bch_bset_fix_invalidated_key(b, k); 1942cafe5635SKent Overstreet } 1943cafe5635SKent Overstreet } 1944cafe5635SKent Overstreet 1945279afbadSKent Overstreet subtract_dirty(k, old_offset, old_size - KEY_SIZE(k)); 1946cafe5635SKent Overstreet } 1947cafe5635SKent Overstreet 1948cafe5635SKent Overstreet check_failed: 19491b207d80SKent Overstreet if (replace_key) { 1950cafe5635SKent Overstreet if (!sectors_found) { 1951cafe5635SKent Overstreet return true; 1952cafe5635SKent Overstreet } else if (sectors_found < KEY_SIZE(insert)) { 1953cafe5635SKent Overstreet SET_KEY_OFFSET(insert, KEY_OFFSET(insert) - 1954cafe5635SKent Overstreet (KEY_SIZE(insert) - sectors_found)); 1955cafe5635SKent Overstreet SET_KEY_SIZE(insert, sectors_found); 1956cafe5635SKent Overstreet } 1957cafe5635SKent Overstreet } 1958cafe5635SKent Overstreet 1959cafe5635SKent Overstreet return false; 1960cafe5635SKent Overstreet } 1961cafe5635SKent Overstreet 1962cafe5635SKent Overstreet static bool btree_insert_key(struct btree *b, struct btree_op *op, 19631b207d80SKent Overstreet struct bkey *k, struct bkey *replace_key) 1964cafe5635SKent Overstreet { 1965ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 1966cafe5635SKent Overstreet struct bkey *m, *prev; 196785b1492eSKent Overstreet unsigned status = BTREE_INSERT_STATUS_INSERT; 1968cafe5635SKent Overstreet 1969cafe5635SKent Overstreet BUG_ON(bkey_cmp(k, &b->key) > 0); 1970cafe5635SKent Overstreet BUG_ON(b->level && !KEY_PTRS(k)); 1971cafe5635SKent Overstreet BUG_ON(!b->level && !KEY_OFFSET(k)); 1972cafe5635SKent Overstreet 1973cafe5635SKent Overstreet if (!b->level) { 1974cafe5635SKent Overstreet struct btree_iter iter; 1975cafe5635SKent Overstreet 1976cafe5635SKent Overstreet /* 1977cafe5635SKent Overstreet * bset_search() returns the first key that is strictly greater 1978cafe5635SKent Overstreet * than the search key - but for back merging, we want to find 19790eacac22SKent Overstreet * the previous key. 1980cafe5635SKent Overstreet */ 1981cafe5635SKent Overstreet prev = NULL; 19820eacac22SKent Overstreet m = bch_btree_iter_init(b, &iter, PRECEDING_KEY(&START_KEY(k))); 1983cafe5635SKent Overstreet 19841b207d80SKent Overstreet if (fix_overlapping_extents(b, k, &iter, replace_key)) { 19851b207d80SKent Overstreet op->insert_collision = true; 1986cafe5635SKent Overstreet return false; 19871b207d80SKent Overstreet } 1988cafe5635SKent Overstreet 19891fa8455dSKent Overstreet if (KEY_DIRTY(k)) 19901fa8455dSKent Overstreet bcache_dev_sectors_dirty_add(b->c, KEY_INODE(k), 19911fa8455dSKent Overstreet KEY_START(k), KEY_SIZE(k)); 19921fa8455dSKent Overstreet 1993fafff81cSKent Overstreet while (m != bset_bkey_last(i) && 1994cafe5635SKent Overstreet bkey_cmp(k, &START_KEY(m)) > 0) 1995cafe5635SKent Overstreet prev = m, m = bkey_next(m); 1996cafe5635SKent Overstreet 1997cafe5635SKent Overstreet if (key_merging_disabled(b->c)) 1998cafe5635SKent Overstreet goto insert; 1999cafe5635SKent Overstreet 2000cafe5635SKent Overstreet /* prev is in the tree, if we merge we're done */ 200185b1492eSKent Overstreet status = BTREE_INSERT_STATUS_BACK_MERGE; 2002cafe5635SKent Overstreet if (prev && 2003cafe5635SKent Overstreet bch_bkey_try_merge(b, prev, k)) 2004cafe5635SKent Overstreet goto merged; 2005cafe5635SKent Overstreet 200685b1492eSKent Overstreet status = BTREE_INSERT_STATUS_OVERWROTE; 2007fafff81cSKent Overstreet if (m != bset_bkey_last(i) && 2008cafe5635SKent Overstreet KEY_PTRS(m) == KEY_PTRS(k) && !KEY_SIZE(m)) 2009cafe5635SKent Overstreet goto copy; 2010cafe5635SKent Overstreet 201185b1492eSKent Overstreet status = BTREE_INSERT_STATUS_FRONT_MERGE; 2012fafff81cSKent Overstreet if (m != bset_bkey_last(i) && 2013cafe5635SKent Overstreet bch_bkey_try_merge(b, k, m)) 2014cafe5635SKent Overstreet goto copy; 20151b207d80SKent Overstreet } else { 20161b207d80SKent Overstreet BUG_ON(replace_key); 2017ee811287SKent Overstreet m = bch_bset_search(b, bset_tree_last(b), k); 20181b207d80SKent Overstreet } 2019cafe5635SKent Overstreet 2020ee811287SKent Overstreet insert: bch_bset_insert(b, m, k); 2021cafe5635SKent Overstreet copy: bkey_copy(m, k); 2022cafe5635SKent Overstreet merged: 20231b207d80SKent Overstreet bch_check_keys(b, "%u for %s", status, 20241b207d80SKent Overstreet replace_key ? "replace" : "insert"); 2025cafe5635SKent Overstreet 2026cafe5635SKent Overstreet if (b->level && !KEY_OFFSET(k)) 202757943511SKent Overstreet btree_current_write(b)->prio_blocked++; 2028cafe5635SKent Overstreet 20291b207d80SKent Overstreet trace_bcache_btree_insert_key(b, k, replace_key != NULL, status); 2030cafe5635SKent Overstreet 2031cafe5635SKent Overstreet return true; 2032cafe5635SKent Overstreet } 2033cafe5635SKent Overstreet 203426c949f8SKent Overstreet static bool bch_btree_insert_keys(struct btree *b, struct btree_op *op, 20351b207d80SKent Overstreet struct keylist *insert_keys, 20361b207d80SKent Overstreet struct bkey *replace_key) 2037cafe5635SKent Overstreet { 2038cafe5635SKent Overstreet bool ret = false; 2039280481d0SKent Overstreet int oldsize = bch_count_data(b); 2040cafe5635SKent Overstreet 204126c949f8SKent Overstreet while (!bch_keylist_empty(insert_keys)) { 2042403b6cdeSKent Overstreet struct bset *i = write_block(b); 2043c2f95ae2SKent Overstreet struct bkey *k = insert_keys->keys; 204426c949f8SKent Overstreet 2045ee811287SKent Overstreet if (b->written + 2046ee811287SKent Overstreet __set_blocks(i, i->keys + bkey_u64s(k), 2047ee811287SKent Overstreet block_bytes(b->c)) > btree_blocks(b)) 2048403b6cdeSKent Overstreet break; 2049403b6cdeSKent Overstreet 2050403b6cdeSKent Overstreet if (bkey_cmp(k, &b->key) <= 0) { 20513a3b6a4eSKent Overstreet if (!b->level) 20523a3b6a4eSKent Overstreet bkey_put(b->c, k); 205326c949f8SKent Overstreet 20541b207d80SKent Overstreet ret |= btree_insert_key(b, op, k, replace_key); 205526c949f8SKent Overstreet bch_keylist_pop_front(insert_keys); 205626c949f8SKent Overstreet } else if (bkey_cmp(&START_KEY(k), &b->key) < 0) { 205726c949f8SKent Overstreet BKEY_PADDED(key) temp; 2058c2f95ae2SKent Overstreet bkey_copy(&temp.key, insert_keys->keys); 205926c949f8SKent Overstreet 206026c949f8SKent Overstreet bch_cut_back(&b->key, &temp.key); 2061c2f95ae2SKent Overstreet bch_cut_front(&b->key, insert_keys->keys); 206226c949f8SKent Overstreet 20631b207d80SKent Overstreet ret |= btree_insert_key(b, op, &temp.key, replace_key); 206426c949f8SKent Overstreet break; 206526c949f8SKent Overstreet } else { 206626c949f8SKent Overstreet break; 206726c949f8SKent Overstreet } 2068cafe5635SKent Overstreet } 2069cafe5635SKent Overstreet 2070403b6cdeSKent Overstreet BUG_ON(!bch_keylist_empty(insert_keys) && b->level); 2071403b6cdeSKent Overstreet 2072cafe5635SKent Overstreet BUG_ON(bch_count_data(b) < oldsize); 2073cafe5635SKent Overstreet return ret; 2074cafe5635SKent Overstreet } 2075cafe5635SKent Overstreet 207626c949f8SKent Overstreet static int btree_split(struct btree *b, struct btree_op *op, 207726c949f8SKent Overstreet struct keylist *insert_keys, 20781b207d80SKent Overstreet struct bkey *replace_key) 2079cafe5635SKent Overstreet { 2080d6fd3b11SKent Overstreet bool split; 2081cafe5635SKent Overstreet struct btree *n1, *n2 = NULL, *n3 = NULL; 2082cafe5635SKent Overstreet uint64_t start_time = local_clock(); 2083b54d6934SKent Overstreet struct closure cl; 208417e21a9fSKent Overstreet struct keylist parent_keys; 2085b54d6934SKent Overstreet 2086b54d6934SKent Overstreet closure_init_stack(&cl); 208717e21a9fSKent Overstreet bch_keylist_init(&parent_keys); 2088cafe5635SKent Overstreet 208978365411SKent Overstreet if (!b->level && 209078365411SKent Overstreet btree_check_reserve(b, op)) 209178365411SKent Overstreet return -EINTR; 209278365411SKent Overstreet 2093bc9389eeSKent Overstreet n1 = btree_node_alloc_replacement(b, true); 2094cafe5635SKent Overstreet if (IS_ERR(n1)) 2095cafe5635SKent Overstreet goto err; 2096cafe5635SKent Overstreet 2097ee811287SKent Overstreet split = set_blocks(btree_bset_first(n1), 2098ee811287SKent Overstreet block_bytes(n1->c)) > (btree_blocks(b) * 4) / 5; 2099cafe5635SKent Overstreet 2100cafe5635SKent Overstreet if (split) { 2101cafe5635SKent Overstreet unsigned keys = 0; 2102cafe5635SKent Overstreet 2103ee811287SKent Overstreet trace_bcache_btree_node_split(b, btree_bset_first(n1)->keys); 2104c37511b8SKent Overstreet 2105bc9389eeSKent Overstreet n2 = bch_btree_node_alloc(b->c, b->level, true); 2106cafe5635SKent Overstreet if (IS_ERR(n2)) 2107cafe5635SKent Overstreet goto err_free1; 2108cafe5635SKent Overstreet 2109d6fd3b11SKent Overstreet if (!b->parent) { 2110bc9389eeSKent Overstreet n3 = bch_btree_node_alloc(b->c, b->level + 1, true); 2111cafe5635SKent Overstreet if (IS_ERR(n3)) 2112cafe5635SKent Overstreet goto err_free2; 2113cafe5635SKent Overstreet } 2114cafe5635SKent Overstreet 21151b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 2116cafe5635SKent Overstreet 2117d6fd3b11SKent Overstreet /* 2118d6fd3b11SKent Overstreet * Has to be a linear search because we don't have an auxiliary 2119cafe5635SKent Overstreet * search tree yet 2120cafe5635SKent Overstreet */ 2121cafe5635SKent Overstreet 2122ee811287SKent Overstreet while (keys < (btree_bset_first(n1)->keys * 3) / 5) 2123ee811287SKent Overstreet keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), 2124fafff81cSKent Overstreet keys)); 2125cafe5635SKent Overstreet 2126fafff81cSKent Overstreet bkey_copy_key(&n1->key, 2127ee811287SKent Overstreet bset_bkey_idx(btree_bset_first(n1), keys)); 2128ee811287SKent Overstreet keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), keys)); 2129cafe5635SKent Overstreet 2130ee811287SKent Overstreet btree_bset_first(n2)->keys = btree_bset_first(n1)->keys - keys; 2131ee811287SKent Overstreet btree_bset_first(n1)->keys = keys; 2132cafe5635SKent Overstreet 2133ee811287SKent Overstreet memcpy(btree_bset_first(n2)->start, 2134ee811287SKent Overstreet bset_bkey_last(btree_bset_first(n1)), 2135ee811287SKent Overstreet btree_bset_first(n2)->keys * sizeof(uint64_t)); 2136cafe5635SKent Overstreet 2137cafe5635SKent Overstreet bkey_copy_key(&n2->key, &b->key); 2138cafe5635SKent Overstreet 213917e21a9fSKent Overstreet bch_keylist_add(&parent_keys, &n2->key); 2140b54d6934SKent Overstreet bch_btree_node_write(n2, &cl); 2141cafe5635SKent Overstreet rw_unlock(true, n2); 2142c37511b8SKent Overstreet } else { 2143ee811287SKent Overstreet trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys); 2144c37511b8SKent Overstreet 21451b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 2146c37511b8SKent Overstreet } 2147cafe5635SKent Overstreet 214817e21a9fSKent Overstreet bch_keylist_add(&parent_keys, &n1->key); 2149b54d6934SKent Overstreet bch_btree_node_write(n1, &cl); 2150cafe5635SKent Overstreet 2151cafe5635SKent Overstreet if (n3) { 2152d6fd3b11SKent Overstreet /* Depth increases, make a new root */ 2153cafe5635SKent Overstreet bkey_copy_key(&n3->key, &MAX_KEY); 215417e21a9fSKent Overstreet bch_btree_insert_keys(n3, op, &parent_keys, NULL); 2155b54d6934SKent Overstreet bch_btree_node_write(n3, &cl); 2156cafe5635SKent Overstreet 2157b54d6934SKent Overstreet closure_sync(&cl); 2158cafe5635SKent Overstreet bch_btree_set_root(n3); 2159cafe5635SKent Overstreet rw_unlock(true, n3); 216017e21a9fSKent Overstreet 216117e21a9fSKent Overstreet btree_node_free(b); 2162d6fd3b11SKent Overstreet } else if (!b->parent) { 2163d6fd3b11SKent Overstreet /* Root filled up but didn't need to be split */ 2164b54d6934SKent Overstreet closure_sync(&cl); 2165cafe5635SKent Overstreet bch_btree_set_root(n1); 216617e21a9fSKent Overstreet 216717e21a9fSKent Overstreet btree_node_free(b); 2168cafe5635SKent Overstreet } else { 216917e21a9fSKent Overstreet /* Split a non root node */ 2170b54d6934SKent Overstreet closure_sync(&cl); 217117e21a9fSKent Overstreet make_btree_freeing_key(b, parent_keys.top); 217217e21a9fSKent Overstreet bch_keylist_push(&parent_keys); 217317e21a9fSKent Overstreet 217417e21a9fSKent Overstreet btree_node_free(b); 217517e21a9fSKent Overstreet 217617e21a9fSKent Overstreet bch_btree_insert_node(b->parent, op, &parent_keys, NULL, NULL); 217717e21a9fSKent Overstreet BUG_ON(!bch_keylist_empty(&parent_keys)); 2178cafe5635SKent Overstreet } 2179cafe5635SKent Overstreet 2180cafe5635SKent Overstreet rw_unlock(true, n1); 2181cafe5635SKent Overstreet 2182169ef1cfSKent Overstreet bch_time_stats_update(&b->c->btree_split_time, start_time); 2183cafe5635SKent Overstreet 2184cafe5635SKent Overstreet return 0; 2185cafe5635SKent Overstreet err_free2: 21865f5837d2SKent Overstreet bkey_put(b->c, &n2->key); 2187e8e1d468SKent Overstreet btree_node_free(n2); 2188cafe5635SKent Overstreet rw_unlock(true, n2); 2189cafe5635SKent Overstreet err_free1: 21905f5837d2SKent Overstreet bkey_put(b->c, &n1->key); 2191e8e1d468SKent Overstreet btree_node_free(n1); 2192cafe5635SKent Overstreet rw_unlock(true, n1); 2193cafe5635SKent Overstreet err: 21945f5837d2SKent Overstreet WARN(1, "bcache: btree split failed"); 21955f5837d2SKent Overstreet 2196cafe5635SKent Overstreet if (n3 == ERR_PTR(-EAGAIN) || 2197cafe5635SKent Overstreet n2 == ERR_PTR(-EAGAIN) || 2198cafe5635SKent Overstreet n1 == ERR_PTR(-EAGAIN)) 2199cafe5635SKent Overstreet return -EAGAIN; 2200cafe5635SKent Overstreet 2201cafe5635SKent Overstreet return -ENOMEM; 2202cafe5635SKent Overstreet } 2203cafe5635SKent Overstreet 220426c949f8SKent Overstreet static int bch_btree_insert_node(struct btree *b, struct btree_op *op, 2205c18536a7SKent Overstreet struct keylist *insert_keys, 22061b207d80SKent Overstreet atomic_t *journal_ref, 22071b207d80SKent Overstreet struct bkey *replace_key) 220826c949f8SKent Overstreet { 22091b207d80SKent Overstreet BUG_ON(b->level && replace_key); 22101b207d80SKent Overstreet 221126c949f8SKent Overstreet if (should_split(b)) { 221226c949f8SKent Overstreet if (current->bio_list) { 221326c949f8SKent Overstreet op->lock = b->c->root->level + 1; 221417e21a9fSKent Overstreet return -EAGAIN; 221526c949f8SKent Overstreet } else if (op->lock <= b->c->root->level) { 221626c949f8SKent Overstreet op->lock = b->c->root->level + 1; 221717e21a9fSKent Overstreet return -EINTR; 221826c949f8SKent Overstreet } else { 221917e21a9fSKent Overstreet /* Invalidated all iterators */ 222017e21a9fSKent Overstreet return btree_split(b, op, insert_keys, replace_key) ?: 222117e21a9fSKent Overstreet -EINTR; 222226c949f8SKent Overstreet } 222326c949f8SKent Overstreet } else { 2224ee811287SKent Overstreet BUG_ON(write_block(b) != btree_bset_last(b)); 222526c949f8SKent Overstreet 222617e21a9fSKent Overstreet if (bch_btree_insert_keys(b, op, insert_keys, replace_key)) { 2227f269af5aSKent Overstreet if (!b->level) 2228c18536a7SKent Overstreet bch_btree_leaf_dirty(b, journal_ref); 2229f269af5aSKent Overstreet else 2230f269af5aSKent Overstreet bch_btree_node_write_sync(b); 223126c949f8SKent Overstreet } 223226c949f8SKent Overstreet 223317e21a9fSKent Overstreet return 0; 223417e21a9fSKent Overstreet } 223526c949f8SKent Overstreet } 223626c949f8SKent Overstreet 2237e7c590ebSKent Overstreet int bch_btree_insert_check_key(struct btree *b, struct btree_op *op, 2238e7c590ebSKent Overstreet struct bkey *check_key) 2239e7c590ebSKent Overstreet { 2240e7c590ebSKent Overstreet int ret = -EINTR; 2241e7c590ebSKent Overstreet uint64_t btree_ptr = b->key.ptr[0]; 2242e7c590ebSKent Overstreet unsigned long seq = b->seq; 2243e7c590ebSKent Overstreet struct keylist insert; 2244e7c590ebSKent Overstreet bool upgrade = op->lock == -1; 2245e7c590ebSKent Overstreet 2246e7c590ebSKent Overstreet bch_keylist_init(&insert); 2247e7c590ebSKent Overstreet 2248e7c590ebSKent Overstreet if (upgrade) { 2249e7c590ebSKent Overstreet rw_unlock(false, b); 2250e7c590ebSKent Overstreet rw_lock(true, b, b->level); 2251e7c590ebSKent Overstreet 2252e7c590ebSKent Overstreet if (b->key.ptr[0] != btree_ptr || 2253e7c590ebSKent Overstreet b->seq != seq + 1) 2254e7c590ebSKent Overstreet goto out; 2255e7c590ebSKent Overstreet } 2256e7c590ebSKent Overstreet 2257e7c590ebSKent Overstreet SET_KEY_PTRS(check_key, 1); 2258e7c590ebSKent Overstreet get_random_bytes(&check_key->ptr[0], sizeof(uint64_t)); 2259e7c590ebSKent Overstreet 2260e7c590ebSKent Overstreet SET_PTR_DEV(check_key, 0, PTR_CHECK_DEV); 2261e7c590ebSKent Overstreet 2262e7c590ebSKent Overstreet bch_keylist_add(&insert, check_key); 2263e7c590ebSKent Overstreet 22641b207d80SKent Overstreet ret = bch_btree_insert_node(b, op, &insert, NULL, NULL); 2265e7c590ebSKent Overstreet 2266e7c590ebSKent Overstreet BUG_ON(!ret && !bch_keylist_empty(&insert)); 2267e7c590ebSKent Overstreet out: 2268e7c590ebSKent Overstreet if (upgrade) 2269e7c590ebSKent Overstreet downgrade_write(&b->lock); 2270e7c590ebSKent Overstreet return ret; 2271e7c590ebSKent Overstreet } 2272e7c590ebSKent Overstreet 2273cc7b8819SKent Overstreet struct btree_insert_op { 2274cc7b8819SKent Overstreet struct btree_op op; 2275cc7b8819SKent Overstreet struct keylist *keys; 2276cc7b8819SKent Overstreet atomic_t *journal_ref; 2277cc7b8819SKent Overstreet struct bkey *replace_key; 2278cc7b8819SKent Overstreet }; 2279cc7b8819SKent Overstreet 228008239ca2SWei Yongjun static int btree_insert_fn(struct btree_op *b_op, struct btree *b) 2281cafe5635SKent Overstreet { 2282cc7b8819SKent Overstreet struct btree_insert_op *op = container_of(b_op, 2283cc7b8819SKent Overstreet struct btree_insert_op, op); 2284403b6cdeSKent Overstreet 2285cc7b8819SKent Overstreet int ret = bch_btree_insert_node(b, &op->op, op->keys, 2286cc7b8819SKent Overstreet op->journal_ref, op->replace_key); 2287cc7b8819SKent Overstreet if (ret && !bch_keylist_empty(op->keys)) 2288cc7b8819SKent Overstreet return ret; 2289cc7b8819SKent Overstreet else 2290cc7b8819SKent Overstreet return MAP_DONE; 2291cafe5635SKent Overstreet } 2292cafe5635SKent Overstreet 2293cc7b8819SKent Overstreet int bch_btree_insert(struct cache_set *c, struct keylist *keys, 2294cc7b8819SKent Overstreet atomic_t *journal_ref, struct bkey *replace_key) 2295cafe5635SKent Overstreet { 2296cc7b8819SKent Overstreet struct btree_insert_op op; 2297cafe5635SKent Overstreet int ret = 0; 2298cafe5635SKent Overstreet 2299cc7b8819SKent Overstreet BUG_ON(current->bio_list); 23004f3d4014SKent Overstreet BUG_ON(bch_keylist_empty(keys)); 2301cafe5635SKent Overstreet 2302cc7b8819SKent Overstreet bch_btree_op_init(&op.op, 0); 2303cc7b8819SKent Overstreet op.keys = keys; 2304cc7b8819SKent Overstreet op.journal_ref = journal_ref; 2305cc7b8819SKent Overstreet op.replace_key = replace_key; 2306cafe5635SKent Overstreet 2307cc7b8819SKent Overstreet while (!ret && !bch_keylist_empty(keys)) { 2308cc7b8819SKent Overstreet op.op.lock = 0; 2309cc7b8819SKent Overstreet ret = bch_btree_map_leaf_nodes(&op.op, c, 2310cc7b8819SKent Overstreet &START_KEY(keys->keys), 2311cc7b8819SKent Overstreet btree_insert_fn); 2312cc7b8819SKent Overstreet } 2313cc7b8819SKent Overstreet 2314cc7b8819SKent Overstreet if (ret) { 2315cafe5635SKent Overstreet struct bkey *k; 2316cafe5635SKent Overstreet 23171b207d80SKent Overstreet pr_err("error %i", ret); 2318cafe5635SKent Overstreet 23194f3d4014SKent Overstreet while ((k = bch_keylist_pop(keys))) 23203a3b6a4eSKent Overstreet bkey_put(c, k); 2321cc7b8819SKent Overstreet } else if (op.op.insert_collision) 2322cc7b8819SKent Overstreet ret = -ESRCH; 23236054c6d4SKent Overstreet 2324cafe5635SKent Overstreet return ret; 2325cafe5635SKent Overstreet } 2326cafe5635SKent Overstreet 2327cafe5635SKent Overstreet void bch_btree_set_root(struct btree *b) 2328cafe5635SKent Overstreet { 2329cafe5635SKent Overstreet unsigned i; 2330e49c7c37SKent Overstreet struct closure cl; 2331e49c7c37SKent Overstreet 2332e49c7c37SKent Overstreet closure_init_stack(&cl); 2333cafe5635SKent Overstreet 2334c37511b8SKent Overstreet trace_bcache_btree_set_root(b); 2335c37511b8SKent Overstreet 2336cafe5635SKent Overstreet BUG_ON(!b->written); 2337cafe5635SKent Overstreet 2338cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) 2339cafe5635SKent Overstreet BUG_ON(PTR_BUCKET(b->c, &b->key, i)->prio != BTREE_PRIO); 2340cafe5635SKent Overstreet 2341cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 2342cafe5635SKent Overstreet list_del_init(&b->list); 2343cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 2344cafe5635SKent Overstreet 2345cafe5635SKent Overstreet b->c->root = b; 2346cafe5635SKent Overstreet 2347e49c7c37SKent Overstreet bch_journal_meta(b->c, &cl); 2348e49c7c37SKent Overstreet closure_sync(&cl); 2349cafe5635SKent Overstreet } 2350cafe5635SKent Overstreet 235148dad8baSKent Overstreet /* Map across nodes or keys */ 235248dad8baSKent Overstreet 235348dad8baSKent Overstreet static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op, 235448dad8baSKent Overstreet struct bkey *from, 235548dad8baSKent Overstreet btree_map_nodes_fn *fn, int flags) 235648dad8baSKent Overstreet { 235748dad8baSKent Overstreet int ret = MAP_CONTINUE; 235848dad8baSKent Overstreet 235948dad8baSKent Overstreet if (b->level) { 236048dad8baSKent Overstreet struct bkey *k; 236148dad8baSKent Overstreet struct btree_iter iter; 236248dad8baSKent Overstreet 236348dad8baSKent Overstreet bch_btree_iter_init(b, &iter, from); 236448dad8baSKent Overstreet 236548dad8baSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, b, 236648dad8baSKent Overstreet bch_ptr_bad))) { 236748dad8baSKent Overstreet ret = btree(map_nodes_recurse, k, b, 236848dad8baSKent Overstreet op, from, fn, flags); 236948dad8baSKent Overstreet from = NULL; 237048dad8baSKent Overstreet 237148dad8baSKent Overstreet if (ret != MAP_CONTINUE) 237248dad8baSKent Overstreet return ret; 237348dad8baSKent Overstreet } 237448dad8baSKent Overstreet } 237548dad8baSKent Overstreet 237648dad8baSKent Overstreet if (!b->level || flags == MAP_ALL_NODES) 237748dad8baSKent Overstreet ret = fn(op, b); 237848dad8baSKent Overstreet 237948dad8baSKent Overstreet return ret; 238048dad8baSKent Overstreet } 238148dad8baSKent Overstreet 238248dad8baSKent Overstreet int __bch_btree_map_nodes(struct btree_op *op, struct cache_set *c, 238348dad8baSKent Overstreet struct bkey *from, btree_map_nodes_fn *fn, int flags) 238448dad8baSKent Overstreet { 2385b54d6934SKent Overstreet return btree_root(map_nodes_recurse, c, op, from, fn, flags); 238648dad8baSKent Overstreet } 238748dad8baSKent Overstreet 238848dad8baSKent Overstreet static int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op, 238948dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, 239048dad8baSKent Overstreet int flags) 239148dad8baSKent Overstreet { 239248dad8baSKent Overstreet int ret = MAP_CONTINUE; 239348dad8baSKent Overstreet struct bkey *k; 239448dad8baSKent Overstreet struct btree_iter iter; 239548dad8baSKent Overstreet 239648dad8baSKent Overstreet bch_btree_iter_init(b, &iter, from); 239748dad8baSKent Overstreet 239848dad8baSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, b, bch_ptr_bad))) { 239948dad8baSKent Overstreet ret = !b->level 240048dad8baSKent Overstreet ? fn(op, b, k) 240148dad8baSKent Overstreet : btree(map_keys_recurse, k, b, op, from, fn, flags); 240248dad8baSKent Overstreet from = NULL; 240348dad8baSKent Overstreet 240448dad8baSKent Overstreet if (ret != MAP_CONTINUE) 240548dad8baSKent Overstreet return ret; 240648dad8baSKent Overstreet } 240748dad8baSKent Overstreet 240848dad8baSKent Overstreet if (!b->level && (flags & MAP_END_KEY)) 240948dad8baSKent Overstreet ret = fn(op, b, &KEY(KEY_INODE(&b->key), 241048dad8baSKent Overstreet KEY_OFFSET(&b->key), 0)); 241148dad8baSKent Overstreet 241248dad8baSKent Overstreet return ret; 241348dad8baSKent Overstreet } 241448dad8baSKent Overstreet 241548dad8baSKent Overstreet int bch_btree_map_keys(struct btree_op *op, struct cache_set *c, 241648dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, int flags) 241748dad8baSKent Overstreet { 2418b54d6934SKent Overstreet return btree_root(map_keys_recurse, c, op, from, fn, flags); 241948dad8baSKent Overstreet } 242048dad8baSKent Overstreet 2421cafe5635SKent Overstreet /* Keybuf code */ 2422cafe5635SKent Overstreet 2423cafe5635SKent Overstreet static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r) 2424cafe5635SKent Overstreet { 2425cafe5635SKent Overstreet /* Overlapping keys compare equal */ 2426cafe5635SKent Overstreet if (bkey_cmp(&l->key, &START_KEY(&r->key)) <= 0) 2427cafe5635SKent Overstreet return -1; 2428cafe5635SKent Overstreet if (bkey_cmp(&START_KEY(&l->key), &r->key) >= 0) 2429cafe5635SKent Overstreet return 1; 2430cafe5635SKent Overstreet return 0; 2431cafe5635SKent Overstreet } 2432cafe5635SKent Overstreet 2433cafe5635SKent Overstreet static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l, 2434cafe5635SKent Overstreet struct keybuf_key *r) 2435cafe5635SKent Overstreet { 2436cafe5635SKent Overstreet return clamp_t(int64_t, bkey_cmp(&l->key, &r->key), -1, 1); 2437cafe5635SKent Overstreet } 2438cafe5635SKent Overstreet 243948dad8baSKent Overstreet struct refill { 244048dad8baSKent Overstreet struct btree_op op; 244148a915a8SKent Overstreet unsigned nr_found; 244248dad8baSKent Overstreet struct keybuf *buf; 244348dad8baSKent Overstreet struct bkey *end; 244448dad8baSKent Overstreet keybuf_pred_fn *pred; 244548dad8baSKent Overstreet }; 244648dad8baSKent Overstreet 244748dad8baSKent Overstreet static int refill_keybuf_fn(struct btree_op *op, struct btree *b, 244848dad8baSKent Overstreet struct bkey *k) 2449cafe5635SKent Overstreet { 245048dad8baSKent Overstreet struct refill *refill = container_of(op, struct refill, op); 245148dad8baSKent Overstreet struct keybuf *buf = refill->buf; 245248dad8baSKent Overstreet int ret = MAP_CONTINUE; 2453cafe5635SKent Overstreet 245448dad8baSKent Overstreet if (bkey_cmp(k, refill->end) >= 0) { 245548dad8baSKent Overstreet ret = MAP_DONE; 245648dad8baSKent Overstreet goto out; 2457cafe5635SKent Overstreet } 2458cafe5635SKent Overstreet 245948dad8baSKent Overstreet if (!KEY_SIZE(k)) /* end key */ 246048dad8baSKent Overstreet goto out; 2461cafe5635SKent Overstreet 246248dad8baSKent Overstreet if (refill->pred(buf, k)) { 2463cafe5635SKent Overstreet struct keybuf_key *w; 2464cafe5635SKent Overstreet 2465cafe5635SKent Overstreet spin_lock(&buf->lock); 2466cafe5635SKent Overstreet 2467cafe5635SKent Overstreet w = array_alloc(&buf->freelist); 246848dad8baSKent Overstreet if (!w) { 246948dad8baSKent Overstreet spin_unlock(&buf->lock); 247048dad8baSKent Overstreet return MAP_DONE; 247148dad8baSKent Overstreet } 2472cafe5635SKent Overstreet 2473cafe5635SKent Overstreet w->private = NULL; 2474cafe5635SKent Overstreet bkey_copy(&w->key, k); 2475cafe5635SKent Overstreet 2476cafe5635SKent Overstreet if (RB_INSERT(&buf->keys, w, node, keybuf_cmp)) 2477cafe5635SKent Overstreet array_free(&buf->freelist, w); 247848a915a8SKent Overstreet else 247948a915a8SKent Overstreet refill->nr_found++; 2480cafe5635SKent Overstreet 248148dad8baSKent Overstreet if (array_freelist_empty(&buf->freelist)) 248248dad8baSKent Overstreet ret = MAP_DONE; 248348dad8baSKent Overstreet 2484cafe5635SKent Overstreet spin_unlock(&buf->lock); 2485cafe5635SKent Overstreet } 248648dad8baSKent Overstreet out: 248748dad8baSKent Overstreet buf->last_scanned = *k; 248848dad8baSKent Overstreet return ret; 2489cafe5635SKent Overstreet } 2490cafe5635SKent Overstreet 2491cafe5635SKent Overstreet void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf, 249272c27061SKent Overstreet struct bkey *end, keybuf_pred_fn *pred) 2493cafe5635SKent Overstreet { 2494cafe5635SKent Overstreet struct bkey start = buf->last_scanned; 249548dad8baSKent Overstreet struct refill refill; 2496cafe5635SKent Overstreet 2497cafe5635SKent Overstreet cond_resched(); 2498cafe5635SKent Overstreet 2499b54d6934SKent Overstreet bch_btree_op_init(&refill.op, -1); 250048a915a8SKent Overstreet refill.nr_found = 0; 250148dad8baSKent Overstreet refill.buf = buf; 250248dad8baSKent Overstreet refill.end = end; 250348dad8baSKent Overstreet refill.pred = pred; 250448dad8baSKent Overstreet 250548dad8baSKent Overstreet bch_btree_map_keys(&refill.op, c, &buf->last_scanned, 250648dad8baSKent Overstreet refill_keybuf_fn, MAP_END_KEY); 2507cafe5635SKent Overstreet 250848a915a8SKent Overstreet trace_bcache_keyscan(refill.nr_found, 2509cafe5635SKent Overstreet KEY_INODE(&start), KEY_OFFSET(&start), 251048a915a8SKent Overstreet KEY_INODE(&buf->last_scanned), 251148a915a8SKent Overstreet KEY_OFFSET(&buf->last_scanned)); 2512cafe5635SKent Overstreet 2513cafe5635SKent Overstreet spin_lock(&buf->lock); 2514cafe5635SKent Overstreet 2515cafe5635SKent Overstreet if (!RB_EMPTY_ROOT(&buf->keys)) { 2516cafe5635SKent Overstreet struct keybuf_key *w; 2517cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2518cafe5635SKent Overstreet buf->start = START_KEY(&w->key); 2519cafe5635SKent Overstreet 2520cafe5635SKent Overstreet w = RB_LAST(&buf->keys, struct keybuf_key, node); 2521cafe5635SKent Overstreet buf->end = w->key; 2522cafe5635SKent Overstreet } else { 2523cafe5635SKent Overstreet buf->start = MAX_KEY; 2524cafe5635SKent Overstreet buf->end = MAX_KEY; 2525cafe5635SKent Overstreet } 2526cafe5635SKent Overstreet 2527cafe5635SKent Overstreet spin_unlock(&buf->lock); 2528cafe5635SKent Overstreet } 2529cafe5635SKent Overstreet 2530cafe5635SKent Overstreet static void __bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2531cafe5635SKent Overstreet { 2532cafe5635SKent Overstreet rb_erase(&w->node, &buf->keys); 2533cafe5635SKent Overstreet array_free(&buf->freelist, w); 2534cafe5635SKent Overstreet } 2535cafe5635SKent Overstreet 2536cafe5635SKent Overstreet void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2537cafe5635SKent Overstreet { 2538cafe5635SKent Overstreet spin_lock(&buf->lock); 2539cafe5635SKent Overstreet __bch_keybuf_del(buf, w); 2540cafe5635SKent Overstreet spin_unlock(&buf->lock); 2541cafe5635SKent Overstreet } 2542cafe5635SKent Overstreet 2543cafe5635SKent Overstreet bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start, 2544cafe5635SKent Overstreet struct bkey *end) 2545cafe5635SKent Overstreet { 2546cafe5635SKent Overstreet bool ret = false; 2547cafe5635SKent Overstreet struct keybuf_key *p, *w, s; 2548cafe5635SKent Overstreet s.key = *start; 2549cafe5635SKent Overstreet 2550cafe5635SKent Overstreet if (bkey_cmp(end, &buf->start) <= 0 || 2551cafe5635SKent Overstreet bkey_cmp(start, &buf->end) >= 0) 2552cafe5635SKent Overstreet return false; 2553cafe5635SKent Overstreet 2554cafe5635SKent Overstreet spin_lock(&buf->lock); 2555cafe5635SKent Overstreet w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp); 2556cafe5635SKent Overstreet 2557cafe5635SKent Overstreet while (w && bkey_cmp(&START_KEY(&w->key), end) < 0) { 2558cafe5635SKent Overstreet p = w; 2559cafe5635SKent Overstreet w = RB_NEXT(w, node); 2560cafe5635SKent Overstreet 2561cafe5635SKent Overstreet if (p->private) 2562cafe5635SKent Overstreet ret = true; 2563cafe5635SKent Overstreet else 2564cafe5635SKent Overstreet __bch_keybuf_del(buf, p); 2565cafe5635SKent Overstreet } 2566cafe5635SKent Overstreet 2567cafe5635SKent Overstreet spin_unlock(&buf->lock); 2568cafe5635SKent Overstreet return ret; 2569cafe5635SKent Overstreet } 2570cafe5635SKent Overstreet 2571cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next(struct keybuf *buf) 2572cafe5635SKent Overstreet { 2573cafe5635SKent Overstreet struct keybuf_key *w; 2574cafe5635SKent Overstreet spin_lock(&buf->lock); 2575cafe5635SKent Overstreet 2576cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2577cafe5635SKent Overstreet 2578cafe5635SKent Overstreet while (w && w->private) 2579cafe5635SKent Overstreet w = RB_NEXT(w, node); 2580cafe5635SKent Overstreet 2581cafe5635SKent Overstreet if (w) 2582cafe5635SKent Overstreet w->private = ERR_PTR(-EINTR); 2583cafe5635SKent Overstreet 2584cafe5635SKent Overstreet spin_unlock(&buf->lock); 2585cafe5635SKent Overstreet return w; 2586cafe5635SKent Overstreet } 2587cafe5635SKent Overstreet 2588cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c, 2589cafe5635SKent Overstreet struct keybuf *buf, 259072c27061SKent Overstreet struct bkey *end, 259172c27061SKent Overstreet keybuf_pred_fn *pred) 2592cafe5635SKent Overstreet { 2593cafe5635SKent Overstreet struct keybuf_key *ret; 2594cafe5635SKent Overstreet 2595cafe5635SKent Overstreet while (1) { 2596cafe5635SKent Overstreet ret = bch_keybuf_next(buf); 2597cafe5635SKent Overstreet if (ret) 2598cafe5635SKent Overstreet break; 2599cafe5635SKent Overstreet 2600cafe5635SKent Overstreet if (bkey_cmp(&buf->last_scanned, end) >= 0) { 2601cafe5635SKent Overstreet pr_debug("scan finished"); 2602cafe5635SKent Overstreet break; 2603cafe5635SKent Overstreet } 2604cafe5635SKent Overstreet 260572c27061SKent Overstreet bch_refill_keybuf(c, buf, end, pred); 2606cafe5635SKent Overstreet } 2607cafe5635SKent Overstreet 2608cafe5635SKent Overstreet return ret; 2609cafe5635SKent Overstreet } 2610cafe5635SKent Overstreet 261172c27061SKent Overstreet void bch_keybuf_init(struct keybuf *buf) 2612cafe5635SKent Overstreet { 2613cafe5635SKent Overstreet buf->last_scanned = MAX_KEY; 2614cafe5635SKent Overstreet buf->keys = RB_ROOT; 2615cafe5635SKent Overstreet 2616cafe5635SKent Overstreet spin_lock_init(&buf->lock); 2617cafe5635SKent Overstreet array_allocator_init(&buf->freelist); 2618cafe5635SKent Overstreet } 2619cafe5635SKent Overstreet 2620cafe5635SKent Overstreet void bch_btree_exit(void) 2621cafe5635SKent Overstreet { 2622cafe5635SKent Overstreet if (btree_io_wq) 2623cafe5635SKent Overstreet destroy_workqueue(btree_io_wq); 2624cafe5635SKent Overstreet } 2625cafe5635SKent Overstreet 2626cafe5635SKent Overstreet int __init bch_btree_init(void) 2627cafe5635SKent Overstreet { 262872a44517SKent Overstreet btree_io_wq = create_singlethread_workqueue("bch_btree_io"); 262972a44517SKent Overstreet if (!btree_io_wq) 2630cafe5635SKent Overstreet return -ENOMEM; 2631cafe5635SKent Overstreet 2632cafe5635SKent Overstreet return 0; 2633cafe5635SKent Overstreet } 2634