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" 2665d45231SKent Overstreet #include "extents.h" 27cafe5635SKent Overstreet 28cafe5635SKent Overstreet #include <linux/slab.h> 29cafe5635SKent Overstreet #include <linux/bitops.h> 30cafe5635SKent Overstreet #include <linux/hash.h> 3172a44517SKent Overstreet #include <linux/kthread.h> 32cd953ed0SGeert Uytterhoeven #include <linux/prefetch.h> 33cafe5635SKent Overstreet #include <linux/random.h> 34cafe5635SKent Overstreet #include <linux/rcupdate.h> 35e6017571SIngo Molnar #include <linux/sched/clock.h> 36b2d09103SIngo Molnar #include <linux/rculist.h> 37b2d09103SIngo Molnar 38cafe5635SKent Overstreet #include <trace/events/bcache.h> 39cafe5635SKent Overstreet 40cafe5635SKent Overstreet /* 41cafe5635SKent Overstreet * Todo: 42cafe5635SKent Overstreet * register_bcache: Return errors out to userspace correctly 43cafe5635SKent Overstreet * 44cafe5635SKent Overstreet * Writeback: don't undirty key until after a cache flush 45cafe5635SKent Overstreet * 46cafe5635SKent Overstreet * Create an iterator for key pointers 47cafe5635SKent Overstreet * 48cafe5635SKent Overstreet * On btree write error, mark bucket such that it won't be freed from the cache 49cafe5635SKent Overstreet * 50cafe5635SKent Overstreet * Journalling: 51cafe5635SKent Overstreet * Check for bad keys in replay 52cafe5635SKent Overstreet * Propagate barriers 53cafe5635SKent Overstreet * Refcount journal entries in journal_replay 54cafe5635SKent Overstreet * 55cafe5635SKent Overstreet * Garbage collection: 56cafe5635SKent Overstreet * Finish incremental gc 57cafe5635SKent Overstreet * Gc should free old UUIDs, data for invalid UUIDs 58cafe5635SKent Overstreet * 59cafe5635SKent Overstreet * Provide a way to list backing device UUIDs we have data cached for, and 60cafe5635SKent Overstreet * probably how long it's been since we've seen them, and a way to invalidate 61cafe5635SKent Overstreet * dirty data for devices that will never be attached again 62cafe5635SKent Overstreet * 63cafe5635SKent Overstreet * Keep 1 min/5 min/15 min statistics of how busy a block device has been, so 64cafe5635SKent Overstreet * that based on that and how much dirty data we have we can keep writeback 65cafe5635SKent Overstreet * from being starved 66cafe5635SKent Overstreet * 67cafe5635SKent Overstreet * Add a tracepoint or somesuch to watch for writeback starvation 68cafe5635SKent Overstreet * 69cafe5635SKent Overstreet * When btree depth > 1 and splitting an interior node, we have to make sure 70cafe5635SKent Overstreet * alloc_bucket() cannot fail. This should be true but is not completely 71cafe5635SKent Overstreet * obvious. 72cafe5635SKent Overstreet * 73cafe5635SKent Overstreet * Plugging? 74cafe5635SKent Overstreet * 75cafe5635SKent Overstreet * If data write is less than hard sector size of ssd, round up offset in open 76cafe5635SKent Overstreet * bucket to the next whole sector 77cafe5635SKent Overstreet * 78cafe5635SKent Overstreet * Superblock needs to be fleshed out for multiple cache devices 79cafe5635SKent Overstreet * 80cafe5635SKent Overstreet * Add a sysfs tunable for the number of writeback IOs in flight 81cafe5635SKent Overstreet * 82cafe5635SKent Overstreet * Add a sysfs tunable for the number of open data buckets 83cafe5635SKent Overstreet * 84cafe5635SKent Overstreet * IO tracking: Can we track when one process is doing io on behalf of another? 85cafe5635SKent Overstreet * IO tracking: Don't use just an average, weigh more recent stuff higher 86cafe5635SKent Overstreet * 87cafe5635SKent Overstreet * Test module load/unload 88cafe5635SKent Overstreet */ 89cafe5635SKent Overstreet 90cafe5635SKent Overstreet #define MAX_NEED_GC 64 91cafe5635SKent Overstreet #define MAX_SAVE_PRIO 72 92cafe5635SKent Overstreet 93cafe5635SKent Overstreet #define PTR_DIRTY_BIT (((uint64_t) 1 << 36)) 94cafe5635SKent Overstreet 95cafe5635SKent Overstreet #define PTR_HASH(c, k) \ 96cafe5635SKent Overstreet (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0)) 97cafe5635SKent Overstreet 98df8e8970SKent Overstreet #define insert_lock(s, b) ((b)->level <= (s)->lock) 99df8e8970SKent Overstreet 100df8e8970SKent Overstreet /* 101df8e8970SKent Overstreet * These macros are for recursing down the btree - they handle the details of 102df8e8970SKent Overstreet * locking and looking up nodes in the cache for you. They're best treated as 103df8e8970SKent Overstreet * mere syntax when reading code that uses them. 104df8e8970SKent Overstreet * 105df8e8970SKent Overstreet * op->lock determines whether we take a read or a write lock at a given depth. 106df8e8970SKent Overstreet * If you've got a read lock and find that you need a write lock (i.e. you're 107df8e8970SKent Overstreet * going to have to split), set op->lock and return -EINTR; btree_root() will 108df8e8970SKent Overstreet * call you again and you'll have the correct lock. 109df8e8970SKent Overstreet */ 110df8e8970SKent Overstreet 111df8e8970SKent Overstreet /** 112df8e8970SKent Overstreet * btree - recurse down the btree on a specified key 113df8e8970SKent Overstreet * @fn: function to call, which will be passed the child node 114df8e8970SKent Overstreet * @key: key to recurse on 115df8e8970SKent Overstreet * @b: parent btree node 116df8e8970SKent Overstreet * @op: pointer to struct btree_op 117df8e8970SKent Overstreet */ 118df8e8970SKent Overstreet #define btree(fn, key, b, op, ...) \ 119df8e8970SKent Overstreet ({ \ 120df8e8970SKent Overstreet int _r, l = (b)->level - 1; \ 121df8e8970SKent Overstreet bool _w = l <= (op)->lock; \ 1222452cc89SSlava Pestov struct btree *_child = bch_btree_node_get((b)->c, op, key, l, \ 1232452cc89SSlava Pestov _w, b); \ 124df8e8970SKent Overstreet if (!IS_ERR(_child)) { \ 125df8e8970SKent Overstreet _r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__); \ 126df8e8970SKent Overstreet rw_unlock(_w, _child); \ 127df8e8970SKent Overstreet } else \ 128df8e8970SKent Overstreet _r = PTR_ERR(_child); \ 129df8e8970SKent Overstreet _r; \ 130df8e8970SKent Overstreet }) 131df8e8970SKent Overstreet 132df8e8970SKent Overstreet /** 133df8e8970SKent Overstreet * btree_root - call a function on the root of the btree 134df8e8970SKent Overstreet * @fn: function to call, which will be passed the child node 135df8e8970SKent Overstreet * @c: cache set 136df8e8970SKent Overstreet * @op: pointer to struct btree_op 137df8e8970SKent Overstreet */ 138df8e8970SKent Overstreet #define btree_root(fn, c, op, ...) \ 139df8e8970SKent Overstreet ({ \ 140df8e8970SKent Overstreet int _r = -EINTR; \ 141df8e8970SKent Overstreet do { \ 142df8e8970SKent Overstreet struct btree *_b = (c)->root; \ 143df8e8970SKent Overstreet bool _w = insert_lock(op, _b); \ 144df8e8970SKent Overstreet rw_lock(_w, _b, _b->level); \ 145df8e8970SKent Overstreet if (_b == (c)->root && \ 146df8e8970SKent Overstreet _w == insert_lock(op, _b)) { \ 147df8e8970SKent Overstreet _r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__); \ 148df8e8970SKent Overstreet } \ 149df8e8970SKent Overstreet rw_unlock(_w, _b); \ 1500a63b66dSKent Overstreet bch_cannibalize_unlock(c); \ 15178365411SKent Overstreet if (_r == -EINTR) \ 15278365411SKent Overstreet schedule(); \ 153df8e8970SKent Overstreet } while (_r == -EINTR); \ 154df8e8970SKent Overstreet \ 1550a63b66dSKent Overstreet finish_wait(&(c)->btree_cache_wait, &(op)->wait); \ 156df8e8970SKent Overstreet _r; \ 157df8e8970SKent Overstreet }) 158df8e8970SKent Overstreet 159a85e968eSKent Overstreet static inline struct bset *write_block(struct btree *b) 160a85e968eSKent Overstreet { 161a85e968eSKent Overstreet return ((void *) btree_bset_first(b)) + b->written * block_bytes(b->c); 162a85e968eSKent Overstreet } 163a85e968eSKent Overstreet 1642a285686SKent Overstreet static void bch_btree_init_next(struct btree *b) 1652a285686SKent Overstreet { 1662a285686SKent Overstreet /* If not a leaf node, always sort */ 1672a285686SKent Overstreet if (b->level && b->keys.nsets) 1682a285686SKent Overstreet bch_btree_sort(&b->keys, &b->c->sort); 1692a285686SKent Overstreet else 1702a285686SKent Overstreet bch_btree_sort_lazy(&b->keys, &b->c->sort); 1712a285686SKent Overstreet 1722a285686SKent Overstreet if (b->written < btree_blocks(b)) 1732a285686SKent Overstreet bch_bset_init_next(&b->keys, write_block(b), 1742a285686SKent Overstreet bset_magic(&b->c->sb)); 1752a285686SKent Overstreet 1762a285686SKent Overstreet } 1772a285686SKent Overstreet 178cafe5635SKent Overstreet /* Btree key manipulation */ 179cafe5635SKent Overstreet 1803a3b6a4eSKent Overstreet void bkey_put(struct cache_set *c, struct bkey *k) 181e7c590ebSKent Overstreet { 182e7c590ebSKent Overstreet unsigned i; 183e7c590ebSKent Overstreet 184e7c590ebSKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 185e7c590ebSKent Overstreet if (ptr_available(c, k, i)) 186e7c590ebSKent Overstreet atomic_dec_bug(&PTR_BUCKET(c, k, i)->pin); 187e7c590ebSKent Overstreet } 188e7c590ebSKent Overstreet 189cafe5635SKent Overstreet /* Btree IO */ 190cafe5635SKent Overstreet 191cafe5635SKent Overstreet static uint64_t btree_csum_set(struct btree *b, struct bset *i) 192cafe5635SKent Overstreet { 193cafe5635SKent Overstreet uint64_t crc = b->key.ptr[0]; 194fafff81cSKent Overstreet void *data = (void *) i + 8, *end = bset_bkey_last(i); 195cafe5635SKent Overstreet 196169ef1cfSKent Overstreet crc = bch_crc64_update(crc, data, end - data); 197c19ed23aSKent Overstreet return crc ^ 0xffffffffffffffffULL; 198cafe5635SKent Overstreet } 199cafe5635SKent Overstreet 20078b77bf8SKent Overstreet void bch_btree_node_read_done(struct btree *b) 201cafe5635SKent Overstreet { 202cafe5635SKent Overstreet const char *err = "bad btree header"; 203ee811287SKent Overstreet struct bset *i = btree_bset_first(b); 20457943511SKent Overstreet struct btree_iter *iter; 205cafe5635SKent Overstreet 206bcf090e0SKent Overstreet iter = mempool_alloc(b->c->fill_iter, GFP_NOIO); 20757943511SKent Overstreet iter->size = b->c->sb.bucket_size / b->c->sb.block_size; 208cafe5635SKent Overstreet iter->used = 0; 209cafe5635SKent Overstreet 210280481d0SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 211c052dd9aSKent Overstreet iter->b = &b->keys; 212280481d0SKent Overstreet #endif 213280481d0SKent Overstreet 21457943511SKent Overstreet if (!i->seq) 215cafe5635SKent Overstreet goto err; 216cafe5635SKent Overstreet 217cafe5635SKent Overstreet for (; 218a85e968eSKent Overstreet b->written < btree_blocks(b) && i->seq == b->keys.set[0].data->seq; 219cafe5635SKent Overstreet i = write_block(b)) { 220cafe5635SKent Overstreet err = "unsupported bset version"; 221cafe5635SKent Overstreet if (i->version > BCACHE_BSET_VERSION) 222cafe5635SKent Overstreet goto err; 223cafe5635SKent Overstreet 224cafe5635SKent Overstreet err = "bad btree header"; 225ee811287SKent Overstreet if (b->written + set_blocks(i, block_bytes(b->c)) > 226ee811287SKent Overstreet btree_blocks(b)) 227cafe5635SKent Overstreet goto err; 228cafe5635SKent Overstreet 229cafe5635SKent Overstreet err = "bad magic"; 23081ab4190SKent Overstreet if (i->magic != bset_magic(&b->c->sb)) 231cafe5635SKent Overstreet goto err; 232cafe5635SKent Overstreet 233cafe5635SKent Overstreet err = "bad checksum"; 234cafe5635SKent Overstreet switch (i->version) { 235cafe5635SKent Overstreet case 0: 236cafe5635SKent Overstreet if (i->csum != csum_set(i)) 237cafe5635SKent Overstreet goto err; 238cafe5635SKent Overstreet break; 239cafe5635SKent Overstreet case BCACHE_BSET_VERSION: 240cafe5635SKent Overstreet if (i->csum != btree_csum_set(b, i)) 241cafe5635SKent Overstreet goto err; 242cafe5635SKent Overstreet break; 243cafe5635SKent Overstreet } 244cafe5635SKent Overstreet 245cafe5635SKent Overstreet err = "empty set"; 246a85e968eSKent Overstreet if (i != b->keys.set[0].data && !i->keys) 247cafe5635SKent Overstreet goto err; 248cafe5635SKent Overstreet 249fafff81cSKent Overstreet bch_btree_iter_push(iter, i->start, bset_bkey_last(i)); 250cafe5635SKent Overstreet 251ee811287SKent Overstreet b->written += set_blocks(i, block_bytes(b->c)); 252cafe5635SKent Overstreet } 253cafe5635SKent Overstreet 254cafe5635SKent Overstreet err = "corrupted btree"; 255cafe5635SKent Overstreet for (i = write_block(b); 256a85e968eSKent Overstreet bset_sector_offset(&b->keys, i) < KEY_SIZE(&b->key); 257cafe5635SKent Overstreet i = ((void *) i) + block_bytes(b->c)) 258a85e968eSKent Overstreet if (i->seq == b->keys.set[0].data->seq) 259cafe5635SKent Overstreet goto err; 260cafe5635SKent Overstreet 261a85e968eSKent Overstreet bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort); 262cafe5635SKent Overstreet 263a85e968eSKent Overstreet i = b->keys.set[0].data; 264cafe5635SKent Overstreet err = "short btree key"; 265a85e968eSKent Overstreet if (b->keys.set[0].size && 266a85e968eSKent Overstreet bkey_cmp(&b->key, &b->keys.set[0].end) < 0) 267cafe5635SKent Overstreet goto err; 268cafe5635SKent Overstreet 269cafe5635SKent Overstreet if (b->written < btree_blocks(b)) 270a85e968eSKent Overstreet bch_bset_init_next(&b->keys, write_block(b), 271a85e968eSKent Overstreet bset_magic(&b->c->sb)); 272cafe5635SKent Overstreet out: 27357943511SKent Overstreet mempool_free(iter, b->c->fill_iter); 27457943511SKent Overstreet return; 275cafe5635SKent Overstreet err: 276cafe5635SKent Overstreet set_btree_node_io_error(b); 27788b9f8c4SKent Overstreet bch_cache_set_error(b->c, "%s at bucket %zu, block %u, %u keys", 278cafe5635SKent Overstreet err, PTR_BUCKET_NR(b->c, &b->key, 0), 27988b9f8c4SKent Overstreet bset_block_offset(b, i), i->keys); 280cafe5635SKent Overstreet goto out; 281cafe5635SKent Overstreet } 282cafe5635SKent Overstreet 2834246a0b6SChristoph Hellwig static void btree_node_read_endio(struct bio *bio) 284cafe5635SKent Overstreet { 28557943511SKent Overstreet struct closure *cl = bio->bi_private; 28657943511SKent Overstreet closure_put(cl); 28757943511SKent Overstreet } 288cafe5635SKent Overstreet 28978b77bf8SKent Overstreet static void bch_btree_node_read(struct btree *b) 29057943511SKent Overstreet { 29157943511SKent Overstreet uint64_t start_time = local_clock(); 29257943511SKent Overstreet struct closure cl; 29357943511SKent Overstreet struct bio *bio; 294cafe5635SKent Overstreet 295c37511b8SKent Overstreet trace_bcache_btree_read(b); 296c37511b8SKent Overstreet 29757943511SKent Overstreet closure_init_stack(&cl); 298cafe5635SKent Overstreet 29957943511SKent Overstreet bio = bch_bbio_alloc(b->c); 3004f024f37SKent Overstreet bio->bi_iter.bi_size = KEY_SIZE(&b->key) << 9; 30157943511SKent Overstreet bio->bi_end_io = btree_node_read_endio; 30257943511SKent Overstreet bio->bi_private = &cl; 30370fd7614SChristoph Hellwig bio->bi_opf = REQ_OP_READ | REQ_META; 30457943511SKent Overstreet 305a85e968eSKent Overstreet bch_bio_map(bio, b->keys.set[0].data); 30657943511SKent Overstreet 30757943511SKent Overstreet bch_submit_bbio(bio, b->c, &b->key, 0); 30857943511SKent Overstreet closure_sync(&cl); 30957943511SKent Overstreet 310*4e4cbee9SChristoph Hellwig if (bio->bi_status) 31157943511SKent Overstreet set_btree_node_io_error(b); 31257943511SKent Overstreet 31357943511SKent Overstreet bch_bbio_free(bio, b->c); 31457943511SKent Overstreet 31557943511SKent Overstreet if (btree_node_io_error(b)) 31657943511SKent Overstreet goto err; 31757943511SKent Overstreet 31857943511SKent Overstreet bch_btree_node_read_done(b); 31957943511SKent Overstreet bch_time_stats_update(&b->c->btree_read_time, start_time); 32057943511SKent Overstreet 32157943511SKent Overstreet return; 32257943511SKent Overstreet err: 32361cbd250SGeert Uytterhoeven bch_cache_set_error(b->c, "io error reading bucket %zu", 32457943511SKent Overstreet PTR_BUCKET_NR(b->c, &b->key, 0)); 325cafe5635SKent Overstreet } 326cafe5635SKent Overstreet 327cafe5635SKent Overstreet static void btree_complete_write(struct btree *b, struct btree_write *w) 328cafe5635SKent Overstreet { 329cafe5635SKent Overstreet if (w->prio_blocked && 330cafe5635SKent Overstreet !atomic_sub_return(w->prio_blocked, &b->c->prio_blocked)) 331119ba0f8SKent Overstreet wake_up_allocators(b->c); 332cafe5635SKent Overstreet 333cafe5635SKent Overstreet if (w->journal) { 334cafe5635SKent Overstreet atomic_dec_bug(w->journal); 335cafe5635SKent Overstreet __closure_wake_up(&b->c->journal.wait); 336cafe5635SKent Overstreet } 337cafe5635SKent Overstreet 338cafe5635SKent Overstreet w->prio_blocked = 0; 339cafe5635SKent Overstreet w->journal = NULL; 340cafe5635SKent Overstreet } 341cafe5635SKent Overstreet 342cb7a583eSKent Overstreet static void btree_node_write_unlock(struct closure *cl) 343cb7a583eSKent Overstreet { 344cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 345cb7a583eSKent Overstreet 346cb7a583eSKent Overstreet up(&b->io_mutex); 347cb7a583eSKent Overstreet } 348cb7a583eSKent Overstreet 34957943511SKent Overstreet static void __btree_node_write_done(struct closure *cl) 350cafe5635SKent Overstreet { 351cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 352cafe5635SKent Overstreet struct btree_write *w = btree_prev_write(b); 353cafe5635SKent Overstreet 354cafe5635SKent Overstreet bch_bbio_free(b->bio, b->c); 355cafe5635SKent Overstreet b->bio = NULL; 356cafe5635SKent Overstreet btree_complete_write(b, w); 357cafe5635SKent Overstreet 358cafe5635SKent Overstreet if (btree_node_dirty(b)) 35956b30770SKent Overstreet schedule_delayed_work(&b->work, 30 * HZ); 360cafe5635SKent Overstreet 361cb7a583eSKent Overstreet closure_return_with_destructor(cl, btree_node_write_unlock); 362cafe5635SKent Overstreet } 363cafe5635SKent Overstreet 36457943511SKent Overstreet static void btree_node_write_done(struct closure *cl) 365cafe5635SKent Overstreet { 366cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 367cafe5635SKent Overstreet 368491221f8SGuoqing Jiang bio_free_pages(b->bio); 36957943511SKent Overstreet __btree_node_write_done(cl); 370cafe5635SKent Overstreet } 371cafe5635SKent Overstreet 3724246a0b6SChristoph Hellwig static void btree_node_write_endio(struct bio *bio) 37357943511SKent Overstreet { 37457943511SKent Overstreet struct closure *cl = bio->bi_private; 375cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 37657943511SKent Overstreet 377*4e4cbee9SChristoph Hellwig if (bio->bi_status) 37857943511SKent Overstreet set_btree_node_io_error(b); 37957943511SKent Overstreet 380*4e4cbee9SChristoph Hellwig bch_bbio_count_io_errors(b->c, bio, bio->bi_status, "writing btree"); 38157943511SKent Overstreet closure_put(cl); 38257943511SKent Overstreet } 38357943511SKent Overstreet 38457943511SKent Overstreet static void do_btree_node_write(struct btree *b) 385cafe5635SKent Overstreet { 386cb7a583eSKent Overstreet struct closure *cl = &b->io; 387ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 388cafe5635SKent Overstreet BKEY_PADDED(key) k; 389cafe5635SKent Overstreet 390cafe5635SKent Overstreet i->version = BCACHE_BSET_VERSION; 391cafe5635SKent Overstreet i->csum = btree_csum_set(b, i); 392cafe5635SKent Overstreet 39357943511SKent Overstreet BUG_ON(b->bio); 39457943511SKent Overstreet b->bio = bch_bbio_alloc(b->c); 39557943511SKent Overstreet 39657943511SKent Overstreet b->bio->bi_end_io = btree_node_write_endio; 397faadf0c9SKent Overstreet b->bio->bi_private = cl; 398ee811287SKent Overstreet b->bio->bi_iter.bi_size = roundup(set_bytes(i), block_bytes(b->c)); 39970fd7614SChristoph Hellwig b->bio->bi_opf = REQ_OP_WRITE | REQ_META | REQ_FUA; 400169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 401cafe5635SKent Overstreet 402e49c7c37SKent Overstreet /* 403e49c7c37SKent Overstreet * If we're appending to a leaf node, we don't technically need FUA - 404e49c7c37SKent Overstreet * this write just needs to be persisted before the next journal write, 405e49c7c37SKent Overstreet * which will be marked FLUSH|FUA. 406e49c7c37SKent Overstreet * 407e49c7c37SKent Overstreet * Similarly if we're writing a new btree root - the pointer is going to 408e49c7c37SKent Overstreet * be in the next journal entry. 409e49c7c37SKent Overstreet * 410e49c7c37SKent Overstreet * But if we're writing a new btree node (that isn't a root) or 411e49c7c37SKent Overstreet * appending to a non leaf btree node, we need either FUA or a flush 412e49c7c37SKent Overstreet * when we write the parent with the new pointer. FUA is cheaper than a 413e49c7c37SKent Overstreet * flush, and writes appending to leaf nodes aren't blocking anything so 414e49c7c37SKent Overstreet * just make all btree node writes FUA to keep things sane. 415e49c7c37SKent Overstreet */ 416e49c7c37SKent Overstreet 417cafe5635SKent Overstreet bkey_copy(&k.key, &b->key); 418ee811287SKent Overstreet SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) + 419a85e968eSKent Overstreet bset_sector_offset(&b->keys, i)); 420cafe5635SKent Overstreet 421501d52a9SKent Overstreet if (!bio_alloc_pages(b->bio, __GFP_NOWARN|GFP_NOWAIT)) { 422cafe5635SKent Overstreet int j; 423cafe5635SKent Overstreet struct bio_vec *bv; 424cafe5635SKent Overstreet void *base = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1)); 425cafe5635SKent Overstreet 4267988613bSKent Overstreet bio_for_each_segment_all(bv, b->bio, j) 427cafe5635SKent Overstreet memcpy(page_address(bv->bv_page), 428cafe5635SKent Overstreet base + j * PAGE_SIZE, PAGE_SIZE); 429cafe5635SKent Overstreet 430cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 431cafe5635SKent Overstreet 43257943511SKent Overstreet continue_at(cl, btree_node_write_done, NULL); 433cafe5635SKent Overstreet } else { 434cafe5635SKent Overstreet b->bio->bi_vcnt = 0; 435169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 436cafe5635SKent Overstreet 437cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 438cafe5635SKent Overstreet 439cafe5635SKent Overstreet closure_sync(cl); 440cb7a583eSKent Overstreet continue_at_nobarrier(cl, __btree_node_write_done, NULL); 441cafe5635SKent Overstreet } 442cafe5635SKent Overstreet } 443cafe5635SKent Overstreet 4442a285686SKent Overstreet void __bch_btree_node_write(struct btree *b, struct closure *parent) 445cafe5635SKent Overstreet { 446ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 447cafe5635SKent Overstreet 4482a285686SKent Overstreet lockdep_assert_held(&b->write_lock); 4492a285686SKent Overstreet 450c37511b8SKent Overstreet trace_bcache_btree_write(b); 451c37511b8SKent Overstreet 452cafe5635SKent Overstreet BUG_ON(current->bio_list); 45357943511SKent Overstreet BUG_ON(b->written >= btree_blocks(b)); 45457943511SKent Overstreet BUG_ON(b->written && !i->keys); 455ee811287SKent Overstreet BUG_ON(btree_bset_first(b)->seq != i->seq); 456dc9d98d6SKent Overstreet bch_check_keys(&b->keys, "writing"); 457cafe5635SKent Overstreet 458cafe5635SKent Overstreet cancel_delayed_work(&b->work); 459cafe5635SKent Overstreet 46057943511SKent Overstreet /* If caller isn't waiting for write, parent refcount is cache set */ 461cb7a583eSKent Overstreet down(&b->io_mutex); 462cb7a583eSKent Overstreet closure_init(&b->io, parent ?: &b->c->cl); 46357943511SKent Overstreet 464cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 465cafe5635SKent Overstreet change_bit(BTREE_NODE_write_idx, &b->flags); 466cafe5635SKent Overstreet 46757943511SKent Overstreet do_btree_node_write(b); 468cafe5635SKent Overstreet 469ee811287SKent Overstreet atomic_long_add(set_blocks(i, block_bytes(b->c)) * b->c->sb.block_size, 470cafe5635SKent Overstreet &PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written); 471cafe5635SKent Overstreet 472a85e968eSKent Overstreet b->written += set_blocks(i, block_bytes(b->c)); 4732a285686SKent Overstreet } 474a85e968eSKent Overstreet 4752a285686SKent Overstreet void bch_btree_node_write(struct btree *b, struct closure *parent) 4762a285686SKent Overstreet { 4772a285686SKent Overstreet unsigned nsets = b->keys.nsets; 4782a285686SKent Overstreet 4792a285686SKent Overstreet lockdep_assert_held(&b->lock); 4802a285686SKent Overstreet 4812a285686SKent Overstreet __bch_btree_node_write(b, parent); 482cafe5635SKent Overstreet 48378b77bf8SKent Overstreet /* 48478b77bf8SKent Overstreet * do verify if there was more than one set initially (i.e. we did a 48578b77bf8SKent Overstreet * sort) and we sorted down to a single set: 48678b77bf8SKent Overstreet */ 4872a285686SKent Overstreet if (nsets && !b->keys.nsets) 48878b77bf8SKent Overstreet bch_btree_verify(b); 48978b77bf8SKent Overstreet 4902a285686SKent Overstreet bch_btree_init_next(b); 491cafe5635SKent Overstreet } 492cafe5635SKent Overstreet 493f269af5aSKent Overstreet static void bch_btree_node_write_sync(struct btree *b) 494f269af5aSKent Overstreet { 495f269af5aSKent Overstreet struct closure cl; 496f269af5aSKent Overstreet 497f269af5aSKent Overstreet closure_init_stack(&cl); 4982a285686SKent Overstreet 4992a285686SKent Overstreet mutex_lock(&b->write_lock); 500f269af5aSKent Overstreet bch_btree_node_write(b, &cl); 5012a285686SKent Overstreet mutex_unlock(&b->write_lock); 5022a285686SKent Overstreet 503f269af5aSKent Overstreet closure_sync(&cl); 504f269af5aSKent Overstreet } 505f269af5aSKent Overstreet 50657943511SKent Overstreet static void btree_node_write_work(struct work_struct *w) 507cafe5635SKent Overstreet { 508cafe5635SKent Overstreet struct btree *b = container_of(to_delayed_work(w), struct btree, work); 509cafe5635SKent Overstreet 5102a285686SKent Overstreet mutex_lock(&b->write_lock); 511cafe5635SKent Overstreet if (btree_node_dirty(b)) 5122a285686SKent Overstreet __bch_btree_node_write(b, NULL); 5132a285686SKent Overstreet mutex_unlock(&b->write_lock); 514cafe5635SKent Overstreet } 515cafe5635SKent Overstreet 516c18536a7SKent Overstreet static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref) 517cafe5635SKent Overstreet { 518ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 519cafe5635SKent Overstreet struct btree_write *w = btree_current_write(b); 520cafe5635SKent Overstreet 5212a285686SKent Overstreet lockdep_assert_held(&b->write_lock); 5222a285686SKent Overstreet 52357943511SKent Overstreet BUG_ON(!b->written); 52457943511SKent Overstreet BUG_ON(!i->keys); 525cafe5635SKent Overstreet 52657943511SKent Overstreet if (!btree_node_dirty(b)) 52756b30770SKent Overstreet schedule_delayed_work(&b->work, 30 * HZ); 52857943511SKent Overstreet 529cafe5635SKent Overstreet set_btree_node_dirty(b); 530cafe5635SKent Overstreet 531c18536a7SKent Overstreet if (journal_ref) { 532cafe5635SKent Overstreet if (w->journal && 533c18536a7SKent Overstreet journal_pin_cmp(b->c, w->journal, journal_ref)) { 534cafe5635SKent Overstreet atomic_dec_bug(w->journal); 535cafe5635SKent Overstreet w->journal = NULL; 536cafe5635SKent Overstreet } 537cafe5635SKent Overstreet 538cafe5635SKent Overstreet if (!w->journal) { 539c18536a7SKent Overstreet w->journal = journal_ref; 540cafe5635SKent Overstreet atomic_inc(w->journal); 541cafe5635SKent Overstreet } 542cafe5635SKent Overstreet } 543cafe5635SKent Overstreet 544cafe5635SKent Overstreet /* Force write if set is too big */ 54557943511SKent Overstreet if (set_bytes(i) > PAGE_SIZE - 48 && 54657943511SKent Overstreet !current->bio_list) 54757943511SKent Overstreet bch_btree_node_write(b, NULL); 548cafe5635SKent Overstreet } 549cafe5635SKent Overstreet 550cafe5635SKent Overstreet /* 551cafe5635SKent Overstreet * Btree in memory cache - allocation/freeing 552cafe5635SKent Overstreet * mca -> memory cache 553cafe5635SKent Overstreet */ 554cafe5635SKent Overstreet 555cafe5635SKent Overstreet #define mca_reserve(c) (((c->root && c->root->level) \ 556cafe5635SKent Overstreet ? c->root->level : 1) * 8 + 16) 557cafe5635SKent Overstreet #define mca_can_free(c) \ 5580a63b66dSKent Overstreet max_t(int, 0, c->btree_cache_used - mca_reserve(c)) 559cafe5635SKent Overstreet 560cafe5635SKent Overstreet static void mca_data_free(struct btree *b) 561cafe5635SKent Overstreet { 562cb7a583eSKent Overstreet BUG_ON(b->io_mutex.count != 1); 563cafe5635SKent Overstreet 564a85e968eSKent Overstreet bch_btree_keys_free(&b->keys); 565cafe5635SKent Overstreet 5660a63b66dSKent Overstreet b->c->btree_cache_used--; 567ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 568cafe5635SKent Overstreet } 569cafe5635SKent Overstreet 570cafe5635SKent Overstreet static void mca_bucket_free(struct btree *b) 571cafe5635SKent Overstreet { 572cafe5635SKent Overstreet BUG_ON(btree_node_dirty(b)); 573cafe5635SKent Overstreet 574cafe5635SKent Overstreet b->key.ptr[0] = 0; 575cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 576cafe5635SKent Overstreet list_move(&b->list, &b->c->btree_cache_freeable); 577cafe5635SKent Overstreet } 578cafe5635SKent Overstreet 579cafe5635SKent Overstreet static unsigned btree_order(struct bkey *k) 580cafe5635SKent Overstreet { 581cafe5635SKent Overstreet return ilog2(KEY_SIZE(k) / PAGE_SECTORS ?: 1); 582cafe5635SKent Overstreet } 583cafe5635SKent Overstreet 584cafe5635SKent Overstreet static void mca_data_alloc(struct btree *b, struct bkey *k, gfp_t gfp) 585cafe5635SKent Overstreet { 586a85e968eSKent Overstreet if (!bch_btree_keys_alloc(&b->keys, 587ee811287SKent Overstreet max_t(unsigned, 588cafe5635SKent Overstreet ilog2(b->c->btree_pages), 589ee811287SKent Overstreet btree_order(k)), 590ee811287SKent Overstreet gfp)) { 5910a63b66dSKent Overstreet b->c->btree_cache_used++; 592ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache); 593ee811287SKent Overstreet } else { 594ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 595ee811287SKent Overstreet } 596cafe5635SKent Overstreet } 597cafe5635SKent Overstreet 598cafe5635SKent Overstreet static struct btree *mca_bucket_alloc(struct cache_set *c, 599cafe5635SKent Overstreet struct bkey *k, gfp_t gfp) 600cafe5635SKent Overstreet { 601cafe5635SKent Overstreet struct btree *b = kzalloc(sizeof(struct btree), gfp); 602cafe5635SKent Overstreet if (!b) 603cafe5635SKent Overstreet return NULL; 604cafe5635SKent Overstreet 605cafe5635SKent Overstreet init_rwsem(&b->lock); 606cafe5635SKent Overstreet lockdep_set_novalidate_class(&b->lock); 6072a285686SKent Overstreet mutex_init(&b->write_lock); 6082a285686SKent Overstreet lockdep_set_novalidate_class(&b->write_lock); 609cafe5635SKent Overstreet INIT_LIST_HEAD(&b->list); 61057943511SKent Overstreet INIT_DELAYED_WORK(&b->work, btree_node_write_work); 611cafe5635SKent Overstreet b->c = c; 612cb7a583eSKent Overstreet sema_init(&b->io_mutex, 1); 613cafe5635SKent Overstreet 614cafe5635SKent Overstreet mca_data_alloc(b, k, gfp); 615cafe5635SKent Overstreet return b; 616cafe5635SKent Overstreet } 617cafe5635SKent Overstreet 618e8e1d468SKent Overstreet static int mca_reap(struct btree *b, unsigned min_order, bool flush) 619cafe5635SKent Overstreet { 620e8e1d468SKent Overstreet struct closure cl; 621e8e1d468SKent Overstreet 622e8e1d468SKent Overstreet closure_init_stack(&cl); 623cafe5635SKent Overstreet lockdep_assert_held(&b->c->bucket_lock); 624cafe5635SKent Overstreet 625cafe5635SKent Overstreet if (!down_write_trylock(&b->lock)) 626cafe5635SKent Overstreet return -ENOMEM; 627cafe5635SKent Overstreet 628a85e968eSKent Overstreet BUG_ON(btree_node_dirty(b) && !b->keys.set[0].data); 629e8e1d468SKent Overstreet 630a85e968eSKent Overstreet if (b->keys.page_order < min_order) 631cb7a583eSKent Overstreet goto out_unlock; 632cb7a583eSKent Overstreet 633cb7a583eSKent Overstreet if (!flush) { 634cb7a583eSKent Overstreet if (btree_node_dirty(b)) 635cb7a583eSKent Overstreet goto out_unlock; 636cb7a583eSKent Overstreet 637cb7a583eSKent Overstreet if (down_trylock(&b->io_mutex)) 638cb7a583eSKent Overstreet goto out_unlock; 639cb7a583eSKent Overstreet up(&b->io_mutex); 640cafe5635SKent Overstreet } 641cafe5635SKent Overstreet 6422a285686SKent Overstreet mutex_lock(&b->write_lock); 643f269af5aSKent Overstreet if (btree_node_dirty(b)) 6442a285686SKent Overstreet __bch_btree_node_write(b, &cl); 6452a285686SKent Overstreet mutex_unlock(&b->write_lock); 6462a285686SKent Overstreet 6472a285686SKent Overstreet closure_sync(&cl); 648cafe5635SKent Overstreet 649e8e1d468SKent Overstreet /* wait for any in flight btree write */ 650cb7a583eSKent Overstreet down(&b->io_mutex); 651cb7a583eSKent Overstreet up(&b->io_mutex); 652e8e1d468SKent Overstreet 653cafe5635SKent Overstreet return 0; 654cb7a583eSKent Overstreet out_unlock: 655cb7a583eSKent Overstreet rw_unlock(true, b); 656cb7a583eSKent Overstreet return -ENOMEM; 657cafe5635SKent Overstreet } 658cafe5635SKent Overstreet 6597dc19d5aSDave Chinner static unsigned long bch_mca_scan(struct shrinker *shrink, 6607dc19d5aSDave Chinner struct shrink_control *sc) 661cafe5635SKent Overstreet { 662cafe5635SKent Overstreet struct cache_set *c = container_of(shrink, struct cache_set, shrink); 663cafe5635SKent Overstreet struct btree *b, *t; 664cafe5635SKent Overstreet unsigned long i, nr = sc->nr_to_scan; 6657dc19d5aSDave Chinner unsigned long freed = 0; 666cafe5635SKent Overstreet 667cafe5635SKent Overstreet if (c->shrinker_disabled) 6687dc19d5aSDave Chinner return SHRINK_STOP; 669cafe5635SKent Overstreet 6700a63b66dSKent Overstreet if (c->btree_cache_alloc_lock) 6717dc19d5aSDave Chinner return SHRINK_STOP; 672cafe5635SKent Overstreet 673cafe5635SKent Overstreet /* Return -1 if we can't do anything right now */ 674a698e08cSKent Overstreet if (sc->gfp_mask & __GFP_IO) 675cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 676cafe5635SKent Overstreet else if (!mutex_trylock(&c->bucket_lock)) 677cafe5635SKent Overstreet return -1; 678cafe5635SKent Overstreet 67936c9ea98SKent Overstreet /* 68036c9ea98SKent Overstreet * It's _really_ critical that we don't free too many btree nodes - we 68136c9ea98SKent Overstreet * have to always leave ourselves a reserve. The reserve is how we 68236c9ea98SKent Overstreet * guarantee that allocating memory for a new btree node can always 68336c9ea98SKent Overstreet * succeed, so that inserting keys into the btree can always succeed and 68436c9ea98SKent Overstreet * IO can always make forward progress: 68536c9ea98SKent Overstreet */ 686cafe5635SKent Overstreet nr /= c->btree_pages; 687cafe5635SKent Overstreet nr = min_t(unsigned long, nr, mca_can_free(c)); 688cafe5635SKent Overstreet 689cafe5635SKent Overstreet i = 0; 690cafe5635SKent Overstreet list_for_each_entry_safe(b, t, &c->btree_cache_freeable, list) { 6917dc19d5aSDave Chinner if (freed >= nr) 692cafe5635SKent Overstreet break; 693cafe5635SKent Overstreet 694cafe5635SKent Overstreet if (++i > 3 && 695e8e1d468SKent Overstreet !mca_reap(b, 0, false)) { 696cafe5635SKent Overstreet mca_data_free(b); 697cafe5635SKent Overstreet rw_unlock(true, b); 6987dc19d5aSDave Chinner freed++; 699cafe5635SKent Overstreet } 700cafe5635SKent Overstreet } 701cafe5635SKent Overstreet 7020a63b66dSKent Overstreet for (i = 0; (nr--) && i < c->btree_cache_used; i++) { 703cafe5635SKent Overstreet if (list_empty(&c->btree_cache)) 704cafe5635SKent Overstreet goto out; 705cafe5635SKent Overstreet 706cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 707cafe5635SKent Overstreet list_rotate_left(&c->btree_cache); 708cafe5635SKent Overstreet 709cafe5635SKent Overstreet if (!b->accessed && 710e8e1d468SKent Overstreet !mca_reap(b, 0, false)) { 711cafe5635SKent Overstreet mca_bucket_free(b); 712cafe5635SKent Overstreet mca_data_free(b); 713cafe5635SKent Overstreet rw_unlock(true, b); 7147dc19d5aSDave Chinner freed++; 715cafe5635SKent Overstreet } else 716cafe5635SKent Overstreet b->accessed = 0; 717cafe5635SKent Overstreet } 718cafe5635SKent Overstreet out: 719cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 7207dc19d5aSDave Chinner return freed; 7217dc19d5aSDave Chinner } 7227dc19d5aSDave Chinner 7237dc19d5aSDave Chinner static unsigned long bch_mca_count(struct shrinker *shrink, 7247dc19d5aSDave Chinner struct shrink_control *sc) 7257dc19d5aSDave Chinner { 7267dc19d5aSDave Chinner struct cache_set *c = container_of(shrink, struct cache_set, shrink); 7277dc19d5aSDave Chinner 7287dc19d5aSDave Chinner if (c->shrinker_disabled) 7297dc19d5aSDave Chinner return 0; 7307dc19d5aSDave Chinner 7310a63b66dSKent Overstreet if (c->btree_cache_alloc_lock) 7327dc19d5aSDave Chinner return 0; 7337dc19d5aSDave Chinner 7347dc19d5aSDave Chinner return mca_can_free(c) * c->btree_pages; 735cafe5635SKent Overstreet } 736cafe5635SKent Overstreet 737cafe5635SKent Overstreet void bch_btree_cache_free(struct cache_set *c) 738cafe5635SKent Overstreet { 739cafe5635SKent Overstreet struct btree *b; 740cafe5635SKent Overstreet struct closure cl; 741cafe5635SKent Overstreet closure_init_stack(&cl); 742cafe5635SKent Overstreet 743cafe5635SKent Overstreet if (c->shrink.list.next) 744cafe5635SKent Overstreet unregister_shrinker(&c->shrink); 745cafe5635SKent Overstreet 746cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 747cafe5635SKent Overstreet 748cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 749cafe5635SKent Overstreet if (c->verify_data) 750cafe5635SKent Overstreet list_move(&c->verify_data->list, &c->btree_cache); 75178b77bf8SKent Overstreet 75278b77bf8SKent Overstreet free_pages((unsigned long) c->verify_ondisk, ilog2(bucket_pages(c))); 753cafe5635SKent Overstreet #endif 754cafe5635SKent Overstreet 755cafe5635SKent Overstreet list_splice(&c->btree_cache_freeable, 756cafe5635SKent Overstreet &c->btree_cache); 757cafe5635SKent Overstreet 758cafe5635SKent Overstreet while (!list_empty(&c->btree_cache)) { 759cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 760cafe5635SKent Overstreet 761cafe5635SKent Overstreet if (btree_node_dirty(b)) 762cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 763cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 764cafe5635SKent Overstreet 765cafe5635SKent Overstreet mca_data_free(b); 766cafe5635SKent Overstreet } 767cafe5635SKent Overstreet 768cafe5635SKent Overstreet while (!list_empty(&c->btree_cache_freed)) { 769cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache_freed, 770cafe5635SKent Overstreet struct btree, list); 771cafe5635SKent Overstreet list_del(&b->list); 772cafe5635SKent Overstreet cancel_delayed_work_sync(&b->work); 773cafe5635SKent Overstreet kfree(b); 774cafe5635SKent Overstreet } 775cafe5635SKent Overstreet 776cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 777cafe5635SKent Overstreet } 778cafe5635SKent Overstreet 779cafe5635SKent Overstreet int bch_btree_cache_alloc(struct cache_set *c) 780cafe5635SKent Overstreet { 781cafe5635SKent Overstreet unsigned i; 782cafe5635SKent Overstreet 783cafe5635SKent Overstreet for (i = 0; i < mca_reserve(c); i++) 78472a44517SKent Overstreet if (!mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL)) 78572a44517SKent Overstreet return -ENOMEM; 786cafe5635SKent Overstreet 787cafe5635SKent Overstreet list_splice_init(&c->btree_cache, 788cafe5635SKent Overstreet &c->btree_cache_freeable); 789cafe5635SKent Overstreet 790cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 791cafe5635SKent Overstreet mutex_init(&c->verify_lock); 792cafe5635SKent Overstreet 79378b77bf8SKent Overstreet c->verify_ondisk = (void *) 79478b77bf8SKent Overstreet __get_free_pages(GFP_KERNEL, ilog2(bucket_pages(c))); 79578b77bf8SKent Overstreet 796cafe5635SKent Overstreet c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL); 797cafe5635SKent Overstreet 798cafe5635SKent Overstreet if (c->verify_data && 799a85e968eSKent Overstreet c->verify_data->keys.set->data) 800cafe5635SKent Overstreet list_del_init(&c->verify_data->list); 801cafe5635SKent Overstreet else 802cafe5635SKent Overstreet c->verify_data = NULL; 803cafe5635SKent Overstreet #endif 804cafe5635SKent Overstreet 8057dc19d5aSDave Chinner c->shrink.count_objects = bch_mca_count; 8067dc19d5aSDave Chinner c->shrink.scan_objects = bch_mca_scan; 807cafe5635SKent Overstreet c->shrink.seeks = 4; 808cafe5635SKent Overstreet c->shrink.batch = c->btree_pages * 2; 809cafe5635SKent Overstreet register_shrinker(&c->shrink); 810cafe5635SKent Overstreet 811cafe5635SKent Overstreet return 0; 812cafe5635SKent Overstreet } 813cafe5635SKent Overstreet 814cafe5635SKent Overstreet /* Btree in memory cache - hash table */ 815cafe5635SKent Overstreet 816cafe5635SKent Overstreet static struct hlist_head *mca_hash(struct cache_set *c, struct bkey *k) 817cafe5635SKent Overstreet { 818cafe5635SKent Overstreet return &c->bucket_hash[hash_32(PTR_HASH(c, k), BUCKET_HASH_BITS)]; 819cafe5635SKent Overstreet } 820cafe5635SKent Overstreet 821cafe5635SKent Overstreet static struct btree *mca_find(struct cache_set *c, struct bkey *k) 822cafe5635SKent Overstreet { 823cafe5635SKent Overstreet struct btree *b; 824cafe5635SKent Overstreet 825cafe5635SKent Overstreet rcu_read_lock(); 826cafe5635SKent Overstreet hlist_for_each_entry_rcu(b, mca_hash(c, k), hash) 827cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) == PTR_HASH(c, k)) 828cafe5635SKent Overstreet goto out; 829cafe5635SKent Overstreet b = NULL; 830cafe5635SKent Overstreet out: 831cafe5635SKent Overstreet rcu_read_unlock(); 832cafe5635SKent Overstreet return b; 833cafe5635SKent Overstreet } 834cafe5635SKent Overstreet 8350a63b66dSKent Overstreet static int mca_cannibalize_lock(struct cache_set *c, struct btree_op *op) 8360a63b66dSKent Overstreet { 8370a63b66dSKent Overstreet struct task_struct *old; 8380a63b66dSKent Overstreet 8390a63b66dSKent Overstreet old = cmpxchg(&c->btree_cache_alloc_lock, NULL, current); 8400a63b66dSKent Overstreet if (old && old != current) { 8410a63b66dSKent Overstreet if (op) 8420a63b66dSKent Overstreet prepare_to_wait(&c->btree_cache_wait, &op->wait, 8430a63b66dSKent Overstreet TASK_UNINTERRUPTIBLE); 8440a63b66dSKent Overstreet return -EINTR; 8450a63b66dSKent Overstreet } 8460a63b66dSKent Overstreet 8470a63b66dSKent Overstreet return 0; 8480a63b66dSKent Overstreet } 8490a63b66dSKent Overstreet 8500a63b66dSKent Overstreet static struct btree *mca_cannibalize(struct cache_set *c, struct btree_op *op, 8510a63b66dSKent Overstreet struct bkey *k) 852cafe5635SKent Overstreet { 853e8e1d468SKent Overstreet struct btree *b; 854cafe5635SKent Overstreet 855c37511b8SKent Overstreet trace_bcache_btree_cache_cannibalize(c); 856c37511b8SKent Overstreet 8570a63b66dSKent Overstreet if (mca_cannibalize_lock(c, op)) 8580a63b66dSKent Overstreet return ERR_PTR(-EINTR); 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 8680a63b66dSKent Overstreet WARN(1, "btree cache cannibalize failed\n"); 869e8e1d468SKent Overstreet return ERR_PTR(-ENOMEM); 870cafe5635SKent Overstreet } 871cafe5635SKent Overstreet 872cafe5635SKent Overstreet /* 873cafe5635SKent Overstreet * We can only have one thread cannibalizing other cached btree nodes at a time, 874cafe5635SKent Overstreet * or we'll deadlock. We use an open coded mutex to ensure that, which a 875cafe5635SKent Overstreet * cannibalize_bucket() will take. This means every time we unlock the root of 876cafe5635SKent Overstreet * the btree, we need to release this lock if we have it held. 877cafe5635SKent Overstreet */ 878df8e8970SKent Overstreet static void bch_cannibalize_unlock(struct cache_set *c) 879cafe5635SKent Overstreet { 8800a63b66dSKent Overstreet if (c->btree_cache_alloc_lock == current) { 8810a63b66dSKent Overstreet c->btree_cache_alloc_lock = NULL; 8820a63b66dSKent Overstreet wake_up(&c->btree_cache_wait); 883cafe5635SKent Overstreet } 884cafe5635SKent Overstreet } 885cafe5635SKent Overstreet 8860a63b66dSKent Overstreet static struct btree *mca_alloc(struct cache_set *c, struct btree_op *op, 8870a63b66dSKent Overstreet struct bkey *k, int level) 888cafe5635SKent Overstreet { 889cafe5635SKent Overstreet struct btree *b; 890cafe5635SKent Overstreet 891e8e1d468SKent Overstreet BUG_ON(current->bio_list); 892e8e1d468SKent Overstreet 893cafe5635SKent Overstreet lockdep_assert_held(&c->bucket_lock); 894cafe5635SKent Overstreet 895cafe5635SKent Overstreet if (mca_find(c, k)) 896cafe5635SKent Overstreet return NULL; 897cafe5635SKent Overstreet 898cafe5635SKent Overstreet /* btree_free() doesn't free memory; it sticks the node on the end of 899cafe5635SKent Overstreet * the list. Check if there's any freed nodes there: 900cafe5635SKent Overstreet */ 901cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freeable, list) 902e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), false)) 903cafe5635SKent Overstreet goto out; 904cafe5635SKent Overstreet 905cafe5635SKent Overstreet /* We never free struct btree itself, just the memory that holds the on 906cafe5635SKent Overstreet * disk node. Check the freed list before allocating a new one: 907cafe5635SKent Overstreet */ 908cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freed, list) 909e8e1d468SKent Overstreet if (!mca_reap(b, 0, false)) { 910cafe5635SKent Overstreet mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO); 911a85e968eSKent Overstreet if (!b->keys.set[0].data) 912cafe5635SKent Overstreet goto err; 913cafe5635SKent Overstreet else 914cafe5635SKent Overstreet goto out; 915cafe5635SKent Overstreet } 916cafe5635SKent Overstreet 917cafe5635SKent Overstreet b = mca_bucket_alloc(c, k, __GFP_NOWARN|GFP_NOIO); 918cafe5635SKent Overstreet if (!b) 919cafe5635SKent Overstreet goto err; 920cafe5635SKent Overstreet 921cafe5635SKent Overstreet BUG_ON(!down_write_trylock(&b->lock)); 922a85e968eSKent Overstreet if (!b->keys.set->data) 923cafe5635SKent Overstreet goto err; 924cafe5635SKent Overstreet out: 925cb7a583eSKent Overstreet BUG_ON(b->io_mutex.count != 1); 926cafe5635SKent Overstreet 927cafe5635SKent Overstreet bkey_copy(&b->key, k); 928cafe5635SKent Overstreet list_move(&b->list, &c->btree_cache); 929cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 930cafe5635SKent Overstreet hlist_add_head_rcu(&b->hash, mca_hash(c, k)); 931cafe5635SKent Overstreet 932cafe5635SKent Overstreet lock_set_subclass(&b->lock.dep_map, level + 1, _THIS_IP_); 933d6fd3b11SKent Overstreet b->parent = (void *) ~0UL; 934a85e968eSKent Overstreet b->flags = 0; 935a85e968eSKent Overstreet b->written = 0; 936a85e968eSKent Overstreet b->level = level; 937cafe5635SKent Overstreet 93865d45231SKent Overstreet if (!b->level) 939a85e968eSKent Overstreet bch_btree_keys_init(&b->keys, &bch_extent_keys_ops, 940a85e968eSKent Overstreet &b->c->expensive_debug_checks); 94165d45231SKent Overstreet else 942a85e968eSKent Overstreet bch_btree_keys_init(&b->keys, &bch_btree_keys_ops, 943a85e968eSKent Overstreet &b->c->expensive_debug_checks); 944cafe5635SKent Overstreet 945cafe5635SKent Overstreet return b; 946cafe5635SKent Overstreet err: 947cafe5635SKent Overstreet if (b) 948cafe5635SKent Overstreet rw_unlock(true, b); 949cafe5635SKent Overstreet 9500a63b66dSKent Overstreet b = mca_cannibalize(c, op, k); 951cafe5635SKent Overstreet if (!IS_ERR(b)) 952cafe5635SKent Overstreet goto out; 953cafe5635SKent Overstreet 954cafe5635SKent Overstreet return b; 955cafe5635SKent Overstreet } 956cafe5635SKent Overstreet 957cafe5635SKent Overstreet /** 958cafe5635SKent Overstreet * bch_btree_node_get - find a btree node in the cache and lock it, reading it 959cafe5635SKent Overstreet * in from disk if necessary. 960cafe5635SKent Overstreet * 961b54d6934SKent Overstreet * If IO is necessary and running under generic_make_request, returns -EAGAIN. 962cafe5635SKent Overstreet * 963cafe5635SKent Overstreet * The btree node will have either a read or a write lock held, depending on 964cafe5635SKent Overstreet * level and op->lock. 965cafe5635SKent Overstreet */ 9660a63b66dSKent Overstreet struct btree *bch_btree_node_get(struct cache_set *c, struct btree_op *op, 9672452cc89SSlava Pestov struct bkey *k, int level, bool write, 9682452cc89SSlava Pestov struct btree *parent) 969cafe5635SKent Overstreet { 970cafe5635SKent Overstreet int i = 0; 971cafe5635SKent Overstreet struct btree *b; 972cafe5635SKent Overstreet 973cafe5635SKent Overstreet BUG_ON(level < 0); 974cafe5635SKent Overstreet retry: 975cafe5635SKent Overstreet b = mca_find(c, k); 976cafe5635SKent Overstreet 977cafe5635SKent Overstreet if (!b) { 97857943511SKent Overstreet if (current->bio_list) 97957943511SKent Overstreet return ERR_PTR(-EAGAIN); 98057943511SKent Overstreet 981cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 9820a63b66dSKent Overstreet b = mca_alloc(c, op, k, level); 983cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 984cafe5635SKent Overstreet 985cafe5635SKent Overstreet if (!b) 986cafe5635SKent Overstreet goto retry; 987cafe5635SKent Overstreet if (IS_ERR(b)) 988cafe5635SKent Overstreet return b; 989cafe5635SKent Overstreet 99057943511SKent Overstreet bch_btree_node_read(b); 991cafe5635SKent Overstreet 992cafe5635SKent Overstreet if (!write) 993cafe5635SKent Overstreet downgrade_write(&b->lock); 994cafe5635SKent Overstreet } else { 995cafe5635SKent Overstreet rw_lock(write, b, level); 996cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) != PTR_HASH(c, k)) { 997cafe5635SKent Overstreet rw_unlock(write, b); 998cafe5635SKent Overstreet goto retry; 999cafe5635SKent Overstreet } 1000cafe5635SKent Overstreet BUG_ON(b->level != level); 1001cafe5635SKent Overstreet } 1002cafe5635SKent Overstreet 10032452cc89SSlava Pestov b->parent = parent; 1004cafe5635SKent Overstreet b->accessed = 1; 1005cafe5635SKent Overstreet 1006a85e968eSKent Overstreet for (; i <= b->keys.nsets && b->keys.set[i].size; i++) { 1007a85e968eSKent Overstreet prefetch(b->keys.set[i].tree); 1008a85e968eSKent Overstreet prefetch(b->keys.set[i].data); 1009cafe5635SKent Overstreet } 1010cafe5635SKent Overstreet 1011a85e968eSKent Overstreet for (; i <= b->keys.nsets; i++) 1012a85e968eSKent Overstreet prefetch(b->keys.set[i].data); 1013cafe5635SKent Overstreet 101457943511SKent Overstreet if (btree_node_io_error(b)) { 1015cafe5635SKent Overstreet rw_unlock(write, b); 101657943511SKent Overstreet return ERR_PTR(-EIO); 101757943511SKent Overstreet } 101857943511SKent Overstreet 1019cafe5635SKent Overstreet BUG_ON(!b->written); 1020cafe5635SKent Overstreet 1021cafe5635SKent Overstreet return b; 1022cafe5635SKent Overstreet } 1023cafe5635SKent Overstreet 10242452cc89SSlava Pestov static void btree_node_prefetch(struct btree *parent, struct bkey *k) 1025cafe5635SKent Overstreet { 1026cafe5635SKent Overstreet struct btree *b; 1027cafe5635SKent Overstreet 10282452cc89SSlava Pestov mutex_lock(&parent->c->bucket_lock); 10292452cc89SSlava Pestov b = mca_alloc(parent->c, NULL, k, parent->level - 1); 10302452cc89SSlava Pestov mutex_unlock(&parent->c->bucket_lock); 1031cafe5635SKent Overstreet 1032cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(b)) { 10332452cc89SSlava Pestov b->parent = parent; 103457943511SKent Overstreet bch_btree_node_read(b); 1035cafe5635SKent Overstreet rw_unlock(true, b); 1036cafe5635SKent Overstreet } 1037cafe5635SKent Overstreet } 1038cafe5635SKent Overstreet 1039cafe5635SKent Overstreet /* Btree alloc */ 1040cafe5635SKent Overstreet 1041e8e1d468SKent Overstreet static void btree_node_free(struct btree *b) 1042cafe5635SKent Overstreet { 1043c37511b8SKent Overstreet trace_bcache_btree_node_free(b); 1044c37511b8SKent Overstreet 1045cafe5635SKent Overstreet BUG_ON(b == b->c->root); 1046cafe5635SKent Overstreet 10472a285686SKent Overstreet mutex_lock(&b->write_lock); 10482a285686SKent Overstreet 1049cafe5635SKent Overstreet if (btree_node_dirty(b)) 1050cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 1051cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 1052cafe5635SKent Overstreet 10532a285686SKent Overstreet mutex_unlock(&b->write_lock); 10542a285686SKent Overstreet 1055cafe5635SKent Overstreet cancel_delayed_work(&b->work); 1056cafe5635SKent Overstreet 1057cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 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 1063c5aa4a31SSlava Pestov struct btree *__bch_btree_node_alloc(struct cache_set *c, struct btree_op *op, 10642452cc89SSlava Pestov int level, bool wait, 10652452cc89SSlava Pestov struct btree *parent) 1066cafe5635SKent Overstreet { 1067cafe5635SKent Overstreet BKEY_PADDED(key) k; 1068cafe5635SKent Overstreet struct btree *b = ERR_PTR(-EAGAIN); 1069cafe5635SKent Overstreet 1070cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1071cafe5635SKent Overstreet retry: 1072c5aa4a31SSlava Pestov if (__bch_bucket_alloc_set(c, RESERVE_BTREE, &k.key, 1, wait)) 1073cafe5635SKent Overstreet goto err; 1074cafe5635SKent Overstreet 10753a3b6a4eSKent Overstreet bkey_put(c, &k.key); 1076cafe5635SKent Overstreet SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS); 1077cafe5635SKent Overstreet 10780a63b66dSKent Overstreet b = mca_alloc(c, op, &k.key, level); 1079cafe5635SKent Overstreet if (IS_ERR(b)) 1080cafe5635SKent Overstreet goto err_free; 1081cafe5635SKent Overstreet 1082cafe5635SKent Overstreet if (!b) { 1083b1a67b0fSKent Overstreet cache_bug(c, 1084b1a67b0fSKent Overstreet "Tried to allocate bucket that was in btree cache"); 1085cafe5635SKent Overstreet goto retry; 1086cafe5635SKent Overstreet } 1087cafe5635SKent Overstreet 1088cafe5635SKent Overstreet b->accessed = 1; 10892452cc89SSlava Pestov b->parent = parent; 1090a85e968eSKent Overstreet bch_bset_init_next(&b->keys, b->keys.set->data, bset_magic(&b->c->sb)); 1091cafe5635SKent Overstreet 1092cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1093c37511b8SKent Overstreet 1094c37511b8SKent Overstreet trace_bcache_btree_node_alloc(b); 1095cafe5635SKent Overstreet return b; 1096cafe5635SKent Overstreet err_free: 1097cafe5635SKent Overstreet bch_bucket_free(c, &k.key); 1098cafe5635SKent Overstreet err: 1099cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1100c37511b8SKent Overstreet 1101913dc33fSSlava Pestov trace_bcache_btree_node_alloc_fail(c); 1102cafe5635SKent Overstreet return b; 1103cafe5635SKent Overstreet } 1104cafe5635SKent Overstreet 1105c5aa4a31SSlava Pestov static struct btree *bch_btree_node_alloc(struct cache_set *c, 11062452cc89SSlava Pestov struct btree_op *op, int level, 11072452cc89SSlava Pestov struct btree *parent) 1108c5aa4a31SSlava Pestov { 11092452cc89SSlava Pestov return __bch_btree_node_alloc(c, op, level, op != NULL, parent); 1110c5aa4a31SSlava Pestov } 1111c5aa4a31SSlava Pestov 11120a63b66dSKent Overstreet static struct btree *btree_node_alloc_replacement(struct btree *b, 11130a63b66dSKent Overstreet struct btree_op *op) 1114cafe5635SKent Overstreet { 11152452cc89SSlava Pestov struct btree *n = bch_btree_node_alloc(b->c, op, b->level, b->parent); 111667539e85SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 11172a285686SKent Overstreet mutex_lock(&n->write_lock); 111889ebb4a2SKent Overstreet bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort); 111967539e85SKent Overstreet bkey_copy_key(&n->key, &b->key); 11202a285686SKent Overstreet mutex_unlock(&n->write_lock); 112167539e85SKent Overstreet } 1122cafe5635SKent Overstreet 1123cafe5635SKent Overstreet return n; 1124cafe5635SKent Overstreet } 1125cafe5635SKent Overstreet 11268835c123SKent Overstreet static void make_btree_freeing_key(struct btree *b, struct bkey *k) 11278835c123SKent Overstreet { 11288835c123SKent Overstreet unsigned i; 11298835c123SKent Overstreet 113005335cffSKent Overstreet mutex_lock(&b->c->bucket_lock); 113105335cffSKent Overstreet 113205335cffSKent Overstreet atomic_inc(&b->c->prio_blocked); 113305335cffSKent Overstreet 11348835c123SKent Overstreet bkey_copy(k, &b->key); 11358835c123SKent Overstreet bkey_copy_key(k, &ZERO_KEY); 11368835c123SKent Overstreet 113705335cffSKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 113805335cffSKent Overstreet SET_PTR_GEN(k, i, 113905335cffSKent Overstreet bch_inc_gen(PTR_CACHE(b->c, &b->key, i), 114005335cffSKent Overstreet PTR_BUCKET(b->c, &b->key, i))); 11418835c123SKent Overstreet 114205335cffSKent Overstreet mutex_unlock(&b->c->bucket_lock); 11438835c123SKent Overstreet } 11448835c123SKent Overstreet 114578365411SKent Overstreet static int btree_check_reserve(struct btree *b, struct btree_op *op) 114678365411SKent Overstreet { 114778365411SKent Overstreet struct cache_set *c = b->c; 114878365411SKent Overstreet struct cache *ca; 11490a63b66dSKent Overstreet unsigned i, reserve = (c->root->level - b->level) * 2 + 1; 115078365411SKent Overstreet 115178365411SKent Overstreet mutex_lock(&c->bucket_lock); 115278365411SKent Overstreet 115378365411SKent Overstreet for_each_cache(ca, c, i) 115478365411SKent Overstreet if (fifo_used(&ca->free[RESERVE_BTREE]) < reserve) { 115578365411SKent Overstreet if (op) 11560a63b66dSKent Overstreet prepare_to_wait(&c->btree_cache_wait, &op->wait, 115778365411SKent Overstreet TASK_UNINTERRUPTIBLE); 11580a63b66dSKent Overstreet mutex_unlock(&c->bucket_lock); 11590a63b66dSKent Overstreet return -EINTR; 116078365411SKent Overstreet } 116178365411SKent Overstreet 116278365411SKent Overstreet mutex_unlock(&c->bucket_lock); 11630a63b66dSKent Overstreet 11640a63b66dSKent Overstreet return mca_cannibalize_lock(b->c, op); 116578365411SKent Overstreet } 116678365411SKent Overstreet 1167cafe5635SKent Overstreet /* Garbage collection */ 1168cafe5635SKent Overstreet 1169487dded8SKent Overstreet static uint8_t __bch_btree_mark_key(struct cache_set *c, int level, 1170487dded8SKent Overstreet struct bkey *k) 1171cafe5635SKent Overstreet { 1172cafe5635SKent Overstreet uint8_t stale = 0; 1173cafe5635SKent Overstreet unsigned i; 1174cafe5635SKent Overstreet struct bucket *g; 1175cafe5635SKent Overstreet 1176cafe5635SKent Overstreet /* 1177cafe5635SKent Overstreet * ptr_invalid() can't return true for the keys that mark btree nodes as 1178cafe5635SKent Overstreet * freed, but since ptr_bad() returns true we'll never actually use them 1179cafe5635SKent Overstreet * for anything and thus we don't want mark their pointers here 1180cafe5635SKent Overstreet */ 1181cafe5635SKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1182cafe5635SKent Overstreet return stale; 1183cafe5635SKent Overstreet 1184cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) { 1185cafe5635SKent Overstreet if (!ptr_available(c, k, i)) 1186cafe5635SKent Overstreet continue; 1187cafe5635SKent Overstreet 1188cafe5635SKent Overstreet g = PTR_BUCKET(c, k, i); 1189cafe5635SKent Overstreet 11903a2fd9d5SKent Overstreet if (gen_after(g->last_gc, PTR_GEN(k, i))) 11913a2fd9d5SKent Overstreet g->last_gc = PTR_GEN(k, i); 1192cafe5635SKent Overstreet 1193cafe5635SKent Overstreet if (ptr_stale(c, k, i)) { 1194cafe5635SKent Overstreet stale = max(stale, ptr_stale(c, k, i)); 1195cafe5635SKent Overstreet continue; 1196cafe5635SKent Overstreet } 1197cafe5635SKent Overstreet 1198cafe5635SKent Overstreet cache_bug_on(GC_MARK(g) && 1199cafe5635SKent Overstreet (GC_MARK(g) == GC_MARK_METADATA) != (level != 0), 1200cafe5635SKent Overstreet c, "inconsistent ptrs: mark = %llu, level = %i", 1201cafe5635SKent Overstreet GC_MARK(g), level); 1202cafe5635SKent Overstreet 1203cafe5635SKent Overstreet if (level) 1204cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_METADATA); 1205cafe5635SKent Overstreet else if (KEY_DIRTY(k)) 1206cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_DIRTY); 12074fe6a816SKent Overstreet else if (!GC_MARK(g)) 12084fe6a816SKent Overstreet SET_GC_MARK(g, GC_MARK_RECLAIMABLE); 1209cafe5635SKent Overstreet 1210cafe5635SKent Overstreet /* guard against overflow */ 1211cafe5635SKent Overstreet SET_GC_SECTORS_USED(g, min_t(unsigned, 1212cafe5635SKent Overstreet GC_SECTORS_USED(g) + KEY_SIZE(k), 121394717447SDarrick J. Wong MAX_GC_SECTORS_USED)); 1214cafe5635SKent Overstreet 1215cafe5635SKent Overstreet BUG_ON(!GC_SECTORS_USED(g)); 1216cafe5635SKent Overstreet } 1217cafe5635SKent Overstreet 1218cafe5635SKent Overstreet return stale; 1219cafe5635SKent Overstreet } 1220cafe5635SKent Overstreet 1221cafe5635SKent Overstreet #define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k) 1222cafe5635SKent Overstreet 1223487dded8SKent Overstreet void bch_initial_mark_key(struct cache_set *c, int level, struct bkey *k) 1224487dded8SKent Overstreet { 1225487dded8SKent Overstreet unsigned i; 1226487dded8SKent Overstreet 1227487dded8SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 1228487dded8SKent Overstreet if (ptr_available(c, k, i) && 1229487dded8SKent Overstreet !ptr_stale(c, k, i)) { 1230487dded8SKent Overstreet struct bucket *b = PTR_BUCKET(c, k, i); 1231487dded8SKent Overstreet 1232487dded8SKent Overstreet b->gen = PTR_GEN(k, i); 1233487dded8SKent Overstreet 1234487dded8SKent Overstreet if (level && bkey_cmp(k, &ZERO_KEY)) 1235487dded8SKent Overstreet b->prio = BTREE_PRIO; 1236487dded8SKent Overstreet else if (!level && b->prio == BTREE_PRIO) 1237487dded8SKent Overstreet b->prio = INITIAL_PRIO; 1238487dded8SKent Overstreet } 1239487dded8SKent Overstreet 1240487dded8SKent Overstreet __bch_btree_mark_key(c, level, k); 1241487dded8SKent Overstreet } 1242487dded8SKent Overstreet 1243a1f0358bSKent Overstreet static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc) 1244cafe5635SKent Overstreet { 1245cafe5635SKent Overstreet uint8_t stale = 0; 1246a1f0358bSKent Overstreet unsigned keys = 0, good_keys = 0; 1247cafe5635SKent Overstreet struct bkey *k; 1248cafe5635SKent Overstreet struct btree_iter iter; 1249cafe5635SKent Overstreet struct bset_tree *t; 1250cafe5635SKent Overstreet 1251cafe5635SKent Overstreet gc->nodes++; 1252cafe5635SKent Overstreet 1253c052dd9aSKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) { 1254cafe5635SKent Overstreet stale = max(stale, btree_mark_key(b, k)); 1255a1f0358bSKent Overstreet keys++; 1256cafe5635SKent Overstreet 1257a85e968eSKent Overstreet if (bch_ptr_bad(&b->keys, k)) 1258cafe5635SKent Overstreet continue; 1259cafe5635SKent Overstreet 1260cafe5635SKent Overstreet gc->key_bytes += bkey_u64s(k); 1261cafe5635SKent Overstreet gc->nkeys++; 1262a1f0358bSKent Overstreet good_keys++; 1263cafe5635SKent Overstreet 1264cafe5635SKent Overstreet gc->data += KEY_SIZE(k); 1265cafe5635SKent Overstreet } 1266cafe5635SKent Overstreet 1267a85e968eSKent Overstreet for (t = b->keys.set; t <= &b->keys.set[b->keys.nsets]; t++) 1268cafe5635SKent Overstreet btree_bug_on(t->size && 1269a85e968eSKent Overstreet bset_written(&b->keys, t) && 1270cafe5635SKent Overstreet bkey_cmp(&b->key, &t->end) < 0, 1271cafe5635SKent Overstreet b, "found short btree key in gc"); 1272cafe5635SKent Overstreet 1273a1f0358bSKent Overstreet if (b->c->gc_always_rewrite) 1274a1f0358bSKent Overstreet return true; 1275a1f0358bSKent Overstreet 1276a1f0358bSKent Overstreet if (stale > 10) 1277a1f0358bSKent Overstreet return true; 1278a1f0358bSKent Overstreet 1279a1f0358bSKent Overstreet if ((keys - good_keys) * 2 > keys) 1280a1f0358bSKent Overstreet return true; 1281a1f0358bSKent Overstreet 1282a1f0358bSKent Overstreet return false; 1283cafe5635SKent Overstreet } 1284cafe5635SKent Overstreet 1285a1f0358bSKent Overstreet #define GC_MERGE_NODES 4U 1286cafe5635SKent Overstreet 1287cafe5635SKent Overstreet struct gc_merge_info { 1288cafe5635SKent Overstreet struct btree *b; 1289cafe5635SKent Overstreet unsigned keys; 1290cafe5635SKent Overstreet }; 1291cafe5635SKent Overstreet 1292a1f0358bSKent Overstreet static int bch_btree_insert_node(struct btree *, struct btree_op *, 1293a1f0358bSKent Overstreet struct keylist *, atomic_t *, struct bkey *); 1294a1f0358bSKent Overstreet 1295a1f0358bSKent Overstreet static int btree_gc_coalesce(struct btree *b, struct btree_op *op, 12960a63b66dSKent Overstreet struct gc_stat *gc, struct gc_merge_info *r) 1297cafe5635SKent Overstreet { 1298a1f0358bSKent Overstreet unsigned i, nodes = 0, keys = 0, blocks; 1299a1f0358bSKent Overstreet struct btree *new_nodes[GC_MERGE_NODES]; 13000a63b66dSKent Overstreet struct keylist keylist; 1301b54d6934SKent Overstreet struct closure cl; 1302a1f0358bSKent Overstreet struct bkey *k; 1303b54d6934SKent Overstreet 13040a63b66dSKent Overstreet bch_keylist_init(&keylist); 13050a63b66dSKent Overstreet 13060a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 13070a63b66dSKent Overstreet return 0; 13080a63b66dSKent Overstreet 1309a1f0358bSKent Overstreet memset(new_nodes, 0, sizeof(new_nodes)); 1310b54d6934SKent Overstreet closure_init_stack(&cl); 1311cafe5635SKent Overstreet 1312a1f0358bSKent Overstreet while (nodes < GC_MERGE_NODES && !IS_ERR_OR_NULL(r[nodes].b)) 1313cafe5635SKent Overstreet keys += r[nodes++].keys; 1314cafe5635SKent Overstreet 1315cafe5635SKent Overstreet blocks = btree_default_blocks(b->c) * 2 / 3; 1316cafe5635SKent Overstreet 1317cafe5635SKent Overstreet if (nodes < 2 || 1318a85e968eSKent Overstreet __set_blocks(b->keys.set[0].data, keys, 1319ee811287SKent Overstreet block_bytes(b->c)) > blocks * (nodes - 1)) 1320a1f0358bSKent Overstreet return 0; 1321cafe5635SKent Overstreet 1322a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 13230a63b66dSKent Overstreet new_nodes[i] = btree_node_alloc_replacement(r[i].b, NULL); 1324a1f0358bSKent Overstreet if (IS_ERR_OR_NULL(new_nodes[i])) 1325a1f0358bSKent Overstreet goto out_nocoalesce; 1326cafe5635SKent Overstreet } 1327cafe5635SKent Overstreet 13280a63b66dSKent Overstreet /* 13290a63b66dSKent Overstreet * We have to check the reserve here, after we've allocated our new 13300a63b66dSKent Overstreet * nodes, to make sure the insert below will succeed - we also check 13310a63b66dSKent Overstreet * before as an optimization to potentially avoid a bunch of expensive 13320a63b66dSKent Overstreet * allocs/sorts 13330a63b66dSKent Overstreet */ 13340a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 13350a63b66dSKent Overstreet goto out_nocoalesce; 13360a63b66dSKent Overstreet 13372a285686SKent Overstreet for (i = 0; i < nodes; i++) 13382a285686SKent Overstreet mutex_lock(&new_nodes[i]->write_lock); 13392a285686SKent Overstreet 1340cafe5635SKent Overstreet for (i = nodes - 1; i > 0; --i) { 1341ee811287SKent Overstreet struct bset *n1 = btree_bset_first(new_nodes[i]); 1342ee811287SKent Overstreet struct bset *n2 = btree_bset_first(new_nodes[i - 1]); 1343cafe5635SKent Overstreet struct bkey *k, *last = NULL; 1344cafe5635SKent Overstreet 1345cafe5635SKent Overstreet keys = 0; 1346cafe5635SKent Overstreet 1347a1f0358bSKent Overstreet if (i > 1) { 1348cafe5635SKent Overstreet for (k = n2->start; 1349fafff81cSKent Overstreet k < bset_bkey_last(n2); 1350cafe5635SKent Overstreet k = bkey_next(k)) { 1351cafe5635SKent Overstreet if (__set_blocks(n1, n1->keys + keys + 1352ee811287SKent Overstreet bkey_u64s(k), 1353ee811287SKent Overstreet block_bytes(b->c)) > blocks) 1354cafe5635SKent Overstreet break; 1355cafe5635SKent Overstreet 1356cafe5635SKent Overstreet last = k; 1357cafe5635SKent Overstreet keys += bkey_u64s(k); 1358cafe5635SKent Overstreet } 1359a1f0358bSKent Overstreet } else { 1360a1f0358bSKent Overstreet /* 1361a1f0358bSKent Overstreet * Last node we're not getting rid of - we're getting 1362a1f0358bSKent Overstreet * rid of the node at r[0]. Have to try and fit all of 1363a1f0358bSKent Overstreet * the remaining keys into this node; we can't ensure 1364a1f0358bSKent Overstreet * they will always fit due to rounding and variable 1365a1f0358bSKent Overstreet * length keys (shouldn't be possible in practice, 1366a1f0358bSKent Overstreet * though) 1367a1f0358bSKent Overstreet */ 1368a1f0358bSKent Overstreet if (__set_blocks(n1, n1->keys + n2->keys, 1369ee811287SKent Overstreet block_bytes(b->c)) > 1370ee811287SKent Overstreet btree_blocks(new_nodes[i])) 1371a1f0358bSKent Overstreet goto out_nocoalesce; 1372a1f0358bSKent Overstreet 1373a1f0358bSKent Overstreet keys = n2->keys; 1374a1f0358bSKent Overstreet /* Take the key of the node we're getting rid of */ 1375a1f0358bSKent Overstreet last = &r->b->key; 1376a1f0358bSKent Overstreet } 1377cafe5635SKent Overstreet 1378ee811287SKent Overstreet BUG_ON(__set_blocks(n1, n1->keys + keys, block_bytes(b->c)) > 1379ee811287SKent Overstreet btree_blocks(new_nodes[i])); 1380cafe5635SKent Overstreet 1381a1f0358bSKent Overstreet if (last) 1382a1f0358bSKent Overstreet bkey_copy_key(&new_nodes[i]->key, last); 1383cafe5635SKent Overstreet 1384fafff81cSKent Overstreet memcpy(bset_bkey_last(n1), 1385cafe5635SKent Overstreet n2->start, 1386fafff81cSKent Overstreet (void *) bset_bkey_idx(n2, keys) - (void *) n2->start); 1387cafe5635SKent Overstreet 1388cafe5635SKent Overstreet n1->keys += keys; 1389a1f0358bSKent Overstreet r[i].keys = n1->keys; 1390cafe5635SKent Overstreet 1391cafe5635SKent Overstreet memmove(n2->start, 1392fafff81cSKent Overstreet bset_bkey_idx(n2, keys), 1393fafff81cSKent Overstreet (void *) bset_bkey_last(n2) - 1394fafff81cSKent Overstreet (void *) bset_bkey_idx(n2, keys)); 1395cafe5635SKent Overstreet 1396cafe5635SKent Overstreet n2->keys -= keys; 1397cafe5635SKent Overstreet 13980a63b66dSKent Overstreet if (__bch_keylist_realloc(&keylist, 1399085d2a3dSKent Overstreet bkey_u64s(&new_nodes[i]->key))) 1400a1f0358bSKent Overstreet goto out_nocoalesce; 1401a1f0358bSKent Overstreet 1402a1f0358bSKent Overstreet bch_btree_node_write(new_nodes[i], &cl); 14030a63b66dSKent Overstreet bch_keylist_add(&keylist, &new_nodes[i]->key); 1404cafe5635SKent Overstreet } 1405cafe5635SKent Overstreet 14062a285686SKent Overstreet for (i = 0; i < nodes; i++) 14072a285686SKent Overstreet mutex_unlock(&new_nodes[i]->write_lock); 14082a285686SKent Overstreet 140905335cffSKent Overstreet closure_sync(&cl); 141005335cffSKent Overstreet 141105335cffSKent Overstreet /* We emptied out this node */ 141205335cffSKent Overstreet BUG_ON(btree_bset_first(new_nodes[0])->keys); 141305335cffSKent Overstreet btree_node_free(new_nodes[0]); 141405335cffSKent Overstreet rw_unlock(true, new_nodes[0]); 1415400ffaa2SSlava Pestov new_nodes[0] = NULL; 141605335cffSKent Overstreet 1417a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 14180a63b66dSKent Overstreet if (__bch_keylist_realloc(&keylist, bkey_u64s(&r[i].b->key))) 1419a1f0358bSKent Overstreet goto out_nocoalesce; 1420a1f0358bSKent Overstreet 14210a63b66dSKent Overstreet make_btree_freeing_key(r[i].b, keylist.top); 14220a63b66dSKent Overstreet bch_keylist_push(&keylist); 1423a1f0358bSKent Overstreet } 1424a1f0358bSKent Overstreet 14250a63b66dSKent Overstreet bch_btree_insert_node(b, op, &keylist, NULL, NULL); 14260a63b66dSKent Overstreet BUG_ON(!bch_keylist_empty(&keylist)); 1427a1f0358bSKent Overstreet 1428a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 1429a1f0358bSKent Overstreet btree_node_free(r[i].b); 1430a1f0358bSKent Overstreet rw_unlock(true, r[i].b); 1431a1f0358bSKent Overstreet 1432a1f0358bSKent Overstreet r[i].b = new_nodes[i]; 1433a1f0358bSKent Overstreet } 1434a1f0358bSKent Overstreet 1435a1f0358bSKent Overstreet memmove(r, r + 1, sizeof(r[0]) * (nodes - 1)); 1436a1f0358bSKent Overstreet r[nodes - 1].b = ERR_PTR(-EINTR); 1437cafe5635SKent Overstreet 1438c37511b8SKent Overstreet trace_bcache_btree_gc_coalesce(nodes); 1439cafe5635SKent Overstreet gc->nodes--; 1440cafe5635SKent Overstreet 14410a63b66dSKent Overstreet bch_keylist_free(&keylist); 14420a63b66dSKent Overstreet 1443a1f0358bSKent Overstreet /* Invalidated our iterator */ 1444a1f0358bSKent Overstreet return -EINTR; 1445a1f0358bSKent Overstreet 1446a1f0358bSKent Overstreet out_nocoalesce: 1447a1f0358bSKent Overstreet closure_sync(&cl); 14480a63b66dSKent Overstreet bch_keylist_free(&keylist); 1449a1f0358bSKent Overstreet 14500a63b66dSKent Overstreet while ((k = bch_keylist_pop(&keylist))) 1451a1f0358bSKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1452a1f0358bSKent Overstreet atomic_dec(&b->c->prio_blocked); 1453a1f0358bSKent Overstreet 1454a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) 1455a1f0358bSKent Overstreet if (!IS_ERR_OR_NULL(new_nodes[i])) { 1456a1f0358bSKent Overstreet btree_node_free(new_nodes[i]); 1457a1f0358bSKent Overstreet rw_unlock(true, new_nodes[i]); 1458a1f0358bSKent Overstreet } 1459a1f0358bSKent Overstreet return 0; 1460a1f0358bSKent Overstreet } 1461a1f0358bSKent Overstreet 14620a63b66dSKent Overstreet static int btree_gc_rewrite_node(struct btree *b, struct btree_op *op, 14630a63b66dSKent Overstreet struct btree *replace) 14640a63b66dSKent Overstreet { 14650a63b66dSKent Overstreet struct keylist keys; 14660a63b66dSKent Overstreet struct btree *n; 14670a63b66dSKent Overstreet 14680a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 14690a63b66dSKent Overstreet return 0; 14700a63b66dSKent Overstreet 14710a63b66dSKent Overstreet n = btree_node_alloc_replacement(replace, NULL); 14720a63b66dSKent Overstreet 14730a63b66dSKent Overstreet /* recheck reserve after allocating replacement node */ 14740a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) { 14750a63b66dSKent Overstreet btree_node_free(n); 14760a63b66dSKent Overstreet rw_unlock(true, n); 14770a63b66dSKent Overstreet return 0; 14780a63b66dSKent Overstreet } 14790a63b66dSKent Overstreet 14800a63b66dSKent Overstreet bch_btree_node_write_sync(n); 14810a63b66dSKent Overstreet 14820a63b66dSKent Overstreet bch_keylist_init(&keys); 14830a63b66dSKent Overstreet bch_keylist_add(&keys, &n->key); 14840a63b66dSKent Overstreet 14850a63b66dSKent Overstreet make_btree_freeing_key(replace, keys.top); 14860a63b66dSKent Overstreet bch_keylist_push(&keys); 14870a63b66dSKent Overstreet 14880a63b66dSKent Overstreet bch_btree_insert_node(b, op, &keys, NULL, NULL); 14890a63b66dSKent Overstreet BUG_ON(!bch_keylist_empty(&keys)); 14900a63b66dSKent Overstreet 14910a63b66dSKent Overstreet btree_node_free(replace); 14920a63b66dSKent Overstreet rw_unlock(true, n); 14930a63b66dSKent Overstreet 14940a63b66dSKent Overstreet /* Invalidated our iterator */ 14950a63b66dSKent Overstreet return -EINTR; 14960a63b66dSKent Overstreet } 14970a63b66dSKent Overstreet 1498a1f0358bSKent Overstreet static unsigned btree_gc_count_keys(struct btree *b) 1499a1f0358bSKent Overstreet { 1500a1f0358bSKent Overstreet struct bkey *k; 1501a1f0358bSKent Overstreet struct btree_iter iter; 1502a1f0358bSKent Overstreet unsigned ret = 0; 1503a1f0358bSKent Overstreet 1504c052dd9aSKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad) 1505a1f0358bSKent Overstreet ret += bkey_u64s(k); 1506a1f0358bSKent Overstreet 1507a1f0358bSKent Overstreet return ret; 1508cafe5635SKent Overstreet } 1509cafe5635SKent Overstreet 1510cafe5635SKent Overstreet static int btree_gc_recurse(struct btree *b, struct btree_op *op, 1511cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1512cafe5635SKent Overstreet { 1513a1f0358bSKent Overstreet int ret = 0; 1514a1f0358bSKent Overstreet bool should_rewrite; 1515a1f0358bSKent Overstreet struct bkey *k; 1516a1f0358bSKent Overstreet struct btree_iter iter; 1517cafe5635SKent Overstreet struct gc_merge_info r[GC_MERGE_NODES]; 15182a285686SKent Overstreet struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1; 1519cafe5635SKent Overstreet 1520c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done); 1521cafe5635SKent Overstreet 15222a285686SKent Overstreet for (i = r; i < r + ARRAY_SIZE(r); i++) 15232a285686SKent Overstreet i->b = ERR_PTR(-EINTR); 1524cafe5635SKent Overstreet 1525a1f0358bSKent Overstreet while (1) { 1526a85e968eSKent Overstreet k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad); 1527a1f0358bSKent Overstreet if (k) { 15280a63b66dSKent Overstreet r->b = bch_btree_node_get(b->c, op, k, b->level - 1, 15292452cc89SSlava Pestov true, b); 1530cafe5635SKent Overstreet if (IS_ERR(r->b)) { 1531cafe5635SKent Overstreet ret = PTR_ERR(r->b); 1532cafe5635SKent Overstreet break; 1533cafe5635SKent Overstreet } 1534cafe5635SKent Overstreet 1535a1f0358bSKent Overstreet r->keys = btree_gc_count_keys(r->b); 1536cafe5635SKent Overstreet 15370a63b66dSKent Overstreet ret = btree_gc_coalesce(b, op, gc, r); 1538a1f0358bSKent Overstreet if (ret) 1539cafe5635SKent Overstreet break; 1540cafe5635SKent Overstreet } 1541cafe5635SKent Overstreet 1542a1f0358bSKent Overstreet if (!last->b) 1543a1f0358bSKent Overstreet break; 1544cafe5635SKent Overstreet 1545a1f0358bSKent Overstreet if (!IS_ERR(last->b)) { 1546a1f0358bSKent Overstreet should_rewrite = btree_gc_mark_node(last->b, gc); 15470a63b66dSKent Overstreet if (should_rewrite) { 15480a63b66dSKent Overstreet ret = btree_gc_rewrite_node(b, op, last->b); 15490a63b66dSKent Overstreet if (ret) 1550a1f0358bSKent Overstreet break; 1551a1f0358bSKent Overstreet } 1552a1f0358bSKent Overstreet 1553a1f0358bSKent Overstreet if (last->b->level) { 1554a1f0358bSKent Overstreet ret = btree_gc_recurse(last->b, op, writes, gc); 1555a1f0358bSKent Overstreet if (ret) 1556a1f0358bSKent Overstreet break; 1557a1f0358bSKent Overstreet } 1558a1f0358bSKent Overstreet 1559a1f0358bSKent Overstreet bkey_copy_key(&b->c->gc_done, &last->b->key); 1560a1f0358bSKent Overstreet 1561a1f0358bSKent Overstreet /* 1562a1f0358bSKent Overstreet * Must flush leaf nodes before gc ends, since replace 1563a1f0358bSKent Overstreet * operations aren't journalled 1564cafe5635SKent Overstreet */ 15652a285686SKent Overstreet mutex_lock(&last->b->write_lock); 1566a1f0358bSKent Overstreet if (btree_node_dirty(last->b)) 1567a1f0358bSKent Overstreet bch_btree_node_write(last->b, writes); 15682a285686SKent Overstreet mutex_unlock(&last->b->write_lock); 1569a1f0358bSKent Overstreet rw_unlock(true, last->b); 1570a1f0358bSKent Overstreet } 1571a1f0358bSKent Overstreet 1572a1f0358bSKent Overstreet memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1)); 1573a1f0358bSKent Overstreet r->b = NULL; 1574a1f0358bSKent Overstreet 1575cafe5635SKent Overstreet if (need_resched()) { 1576cafe5635SKent Overstreet ret = -EAGAIN; 1577cafe5635SKent Overstreet break; 1578cafe5635SKent Overstreet } 1579cafe5635SKent Overstreet } 1580cafe5635SKent Overstreet 15812a285686SKent Overstreet for (i = r; i < r + ARRAY_SIZE(r); i++) 15822a285686SKent Overstreet if (!IS_ERR_OR_NULL(i->b)) { 15832a285686SKent Overstreet mutex_lock(&i->b->write_lock); 15842a285686SKent Overstreet if (btree_node_dirty(i->b)) 15852a285686SKent Overstreet bch_btree_node_write(i->b, writes); 15862a285686SKent Overstreet mutex_unlock(&i->b->write_lock); 15872a285686SKent Overstreet rw_unlock(true, i->b); 1588a1f0358bSKent Overstreet } 1589cafe5635SKent Overstreet 1590cafe5635SKent Overstreet return ret; 1591cafe5635SKent Overstreet } 1592cafe5635SKent Overstreet 1593cafe5635SKent Overstreet static int bch_btree_gc_root(struct btree *b, struct btree_op *op, 1594cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1595cafe5635SKent Overstreet { 1596cafe5635SKent Overstreet struct btree *n = NULL; 1597a1f0358bSKent Overstreet int ret = 0; 1598a1f0358bSKent Overstreet bool should_rewrite; 1599cafe5635SKent Overstreet 1600a1f0358bSKent Overstreet should_rewrite = btree_gc_mark_node(b, gc); 1601a1f0358bSKent Overstreet if (should_rewrite) { 16020a63b66dSKent Overstreet n = btree_node_alloc_replacement(b, NULL); 1603cafe5635SKent Overstreet 1604cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 1605a1f0358bSKent Overstreet bch_btree_node_write_sync(n); 16062a285686SKent Overstreet 1607a1f0358bSKent Overstreet bch_btree_set_root(n); 1608a1f0358bSKent Overstreet btree_node_free(b); 1609a1f0358bSKent Overstreet rw_unlock(true, n); 1610a1f0358bSKent Overstreet 1611a1f0358bSKent Overstreet return -EINTR; 1612cafe5635SKent Overstreet } 1613a1f0358bSKent Overstreet } 1614a1f0358bSKent Overstreet 1615487dded8SKent Overstreet __bch_btree_mark_key(b->c, b->level + 1, &b->key); 1616487dded8SKent Overstreet 1617a1f0358bSKent Overstreet if (b->level) { 1618a1f0358bSKent Overstreet ret = btree_gc_recurse(b, op, writes, gc); 1619a1f0358bSKent Overstreet if (ret) 1620a1f0358bSKent Overstreet return ret; 1621a1f0358bSKent Overstreet } 1622a1f0358bSKent Overstreet 1623a1f0358bSKent Overstreet bkey_copy_key(&b->c->gc_done, &b->key); 1624cafe5635SKent Overstreet 1625cafe5635SKent Overstreet return ret; 1626cafe5635SKent Overstreet } 1627cafe5635SKent Overstreet 1628cafe5635SKent Overstreet static void btree_gc_start(struct cache_set *c) 1629cafe5635SKent Overstreet { 1630cafe5635SKent Overstreet struct cache *ca; 1631cafe5635SKent Overstreet struct bucket *b; 1632cafe5635SKent Overstreet unsigned i; 1633cafe5635SKent Overstreet 1634cafe5635SKent Overstreet if (!c->gc_mark_valid) 1635cafe5635SKent Overstreet return; 1636cafe5635SKent Overstreet 1637cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1638cafe5635SKent Overstreet 1639cafe5635SKent Overstreet c->gc_mark_valid = 0; 1640cafe5635SKent Overstreet c->gc_done = ZERO_KEY; 1641cafe5635SKent Overstreet 1642cafe5635SKent Overstreet for_each_cache(ca, c, i) 1643cafe5635SKent Overstreet for_each_bucket(b, ca) { 16443a2fd9d5SKent Overstreet b->last_gc = b->gen; 164529ebf465SKent Overstreet if (!atomic_read(&b->pin)) { 16464fe6a816SKent Overstreet SET_GC_MARK(b, 0); 164729ebf465SKent Overstreet SET_GC_SECTORS_USED(b, 0); 164829ebf465SKent Overstreet } 1649cafe5635SKent Overstreet } 1650cafe5635SKent Overstreet 1651cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1652cafe5635SKent Overstreet } 1653cafe5635SKent Overstreet 16542531d9eeSKent Overstreet static size_t bch_btree_gc_finish(struct cache_set *c) 1655cafe5635SKent Overstreet { 1656cafe5635SKent Overstreet size_t available = 0; 1657cafe5635SKent Overstreet struct bucket *b; 1658cafe5635SKent Overstreet struct cache *ca; 1659cafe5635SKent Overstreet unsigned i; 1660cafe5635SKent Overstreet 1661cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1662cafe5635SKent Overstreet 1663cafe5635SKent Overstreet set_gc_sectors(c); 1664cafe5635SKent Overstreet c->gc_mark_valid = 1; 1665cafe5635SKent Overstreet c->need_gc = 0; 1666cafe5635SKent Overstreet 1667cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&c->uuid_bucket); i++) 1668cafe5635SKent Overstreet SET_GC_MARK(PTR_BUCKET(c, &c->uuid_bucket, i), 1669cafe5635SKent Overstreet GC_MARK_METADATA); 1670cafe5635SKent Overstreet 1671bf0a628aSNicholas Swenson /* don't reclaim buckets to which writeback keys point */ 1672bf0a628aSNicholas Swenson rcu_read_lock(); 1673bf0a628aSNicholas Swenson for (i = 0; i < c->nr_uuids; i++) { 1674bf0a628aSNicholas Swenson struct bcache_device *d = c->devices[i]; 1675bf0a628aSNicholas Swenson struct cached_dev *dc; 1676bf0a628aSNicholas Swenson struct keybuf_key *w, *n; 1677bf0a628aSNicholas Swenson unsigned j; 1678bf0a628aSNicholas Swenson 1679bf0a628aSNicholas Swenson if (!d || UUID_FLASH_ONLY(&c->uuids[i])) 1680bf0a628aSNicholas Swenson continue; 1681bf0a628aSNicholas Swenson dc = container_of(d, struct cached_dev, disk); 1682bf0a628aSNicholas Swenson 1683bf0a628aSNicholas Swenson spin_lock(&dc->writeback_keys.lock); 1684bf0a628aSNicholas Swenson rbtree_postorder_for_each_entry_safe(w, n, 1685bf0a628aSNicholas Swenson &dc->writeback_keys.keys, node) 1686bf0a628aSNicholas Swenson for (j = 0; j < KEY_PTRS(&w->key); j++) 1687bf0a628aSNicholas Swenson SET_GC_MARK(PTR_BUCKET(c, &w->key, j), 1688bf0a628aSNicholas Swenson GC_MARK_DIRTY); 1689bf0a628aSNicholas Swenson spin_unlock(&dc->writeback_keys.lock); 1690bf0a628aSNicholas Swenson } 1691bf0a628aSNicholas Swenson rcu_read_unlock(); 1692bf0a628aSNicholas Swenson 1693cafe5635SKent Overstreet for_each_cache(ca, c, i) { 1694cafe5635SKent Overstreet uint64_t *i; 1695cafe5635SKent Overstreet 1696cafe5635SKent Overstreet ca->invalidate_needs_gc = 0; 1697cafe5635SKent Overstreet 1698cafe5635SKent Overstreet for (i = ca->sb.d; i < ca->sb.d + ca->sb.keys; i++) 1699cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1700cafe5635SKent Overstreet 1701cafe5635SKent Overstreet for (i = ca->prio_buckets; 1702cafe5635SKent Overstreet i < ca->prio_buckets + prio_buckets(ca) * 2; i++) 1703cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1704cafe5635SKent Overstreet 1705cafe5635SKent Overstreet for_each_bucket(b, ca) { 1706cafe5635SKent Overstreet c->need_gc = max(c->need_gc, bucket_gc_gen(b)); 1707cafe5635SKent Overstreet 17084fe6a816SKent Overstreet if (atomic_read(&b->pin)) 17094fe6a816SKent Overstreet continue; 17104fe6a816SKent Overstreet 17114fe6a816SKent Overstreet BUG_ON(!GC_MARK(b) && GC_SECTORS_USED(b)); 17124fe6a816SKent Overstreet 17134fe6a816SKent Overstreet if (!GC_MARK(b) || GC_MARK(b) == GC_MARK_RECLAIMABLE) 1714cafe5635SKent Overstreet available++; 1715cafe5635SKent Overstreet } 1716cafe5635SKent Overstreet } 1717cafe5635SKent Overstreet 1718cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1719cafe5635SKent Overstreet return available; 1720cafe5635SKent Overstreet } 1721cafe5635SKent Overstreet 172272a44517SKent Overstreet static void bch_btree_gc(struct cache_set *c) 1723cafe5635SKent Overstreet { 1724cafe5635SKent Overstreet int ret; 1725cafe5635SKent Overstreet unsigned long available; 1726cafe5635SKent Overstreet struct gc_stat stats; 1727cafe5635SKent Overstreet struct closure writes; 1728cafe5635SKent Overstreet struct btree_op op; 1729cafe5635SKent Overstreet uint64_t start_time = local_clock(); 173057943511SKent Overstreet 1731c37511b8SKent Overstreet trace_bcache_gc_start(c); 1732cafe5635SKent Overstreet 1733cafe5635SKent Overstreet memset(&stats, 0, sizeof(struct gc_stat)); 1734cafe5635SKent Overstreet closure_init_stack(&writes); 1735b54d6934SKent Overstreet bch_btree_op_init(&op, SHRT_MAX); 1736cafe5635SKent Overstreet 1737cafe5635SKent Overstreet btree_gc_start(c); 1738cafe5635SKent Overstreet 1739a1f0358bSKent Overstreet do { 1740cafe5635SKent Overstreet ret = btree_root(gc_root, c, &op, &writes, &stats); 1741cafe5635SKent Overstreet closure_sync(&writes); 1742c5f1e5adSKent Overstreet cond_resched(); 1743cafe5635SKent Overstreet 1744a1f0358bSKent Overstreet if (ret && ret != -EAGAIN) 1745cafe5635SKent Overstreet pr_warn("gc failed!"); 1746a1f0358bSKent Overstreet } while (ret); 1747cafe5635SKent Overstreet 1748cafe5635SKent Overstreet available = bch_btree_gc_finish(c); 174957943511SKent Overstreet wake_up_allocators(c); 175057943511SKent Overstreet 1751169ef1cfSKent Overstreet bch_time_stats_update(&c->btree_gc_time, start_time); 1752cafe5635SKent Overstreet 1753cafe5635SKent Overstreet stats.key_bytes *= sizeof(uint64_t); 1754cafe5635SKent Overstreet stats.data <<= 9; 1755cafe5635SKent Overstreet stats.in_use = (c->nbuckets - available) * 100 / c->nbuckets; 1756cafe5635SKent Overstreet memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat)); 1757cafe5635SKent Overstreet 1758c37511b8SKent Overstreet trace_bcache_gc_end(c); 1759cafe5635SKent Overstreet 176072a44517SKent Overstreet bch_moving_gc(c); 1761cafe5635SKent Overstreet } 1762cafe5635SKent Overstreet 1763be628be0SKent Overstreet static bool gc_should_run(struct cache_set *c) 1764cafe5635SKent Overstreet { 1765a1f0358bSKent Overstreet struct cache *ca; 1766a1f0358bSKent Overstreet unsigned i; 176772a44517SKent Overstreet 1768be628be0SKent Overstreet for_each_cache(ca, c, i) 1769be628be0SKent Overstreet if (ca->invalidate_needs_gc) 1770be628be0SKent Overstreet return true; 177172a44517SKent Overstreet 1772be628be0SKent Overstreet if (atomic_read(&c->sectors_to_gc) < 0) 1773be628be0SKent Overstreet return true; 1774be628be0SKent Overstreet 1775be628be0SKent Overstreet return false; 1776be628be0SKent Overstreet } 1777be628be0SKent Overstreet 1778be628be0SKent Overstreet static int bch_gc_thread(void *arg) 1779be628be0SKent Overstreet { 1780be628be0SKent Overstreet struct cache_set *c = arg; 1781be628be0SKent Overstreet 1782be628be0SKent Overstreet while (1) { 1783be628be0SKent Overstreet wait_event_interruptible(c->gc_wait, 1784be628be0SKent Overstreet kthread_should_stop() || gc_should_run(c)); 1785be628be0SKent Overstreet 178672a44517SKent Overstreet if (kthread_should_stop()) 178772a44517SKent Overstreet break; 178872a44517SKent Overstreet 1789be628be0SKent Overstreet set_gc_sectors(c); 1790be628be0SKent Overstreet bch_btree_gc(c); 179172a44517SKent Overstreet } 179272a44517SKent Overstreet 179372a44517SKent Overstreet return 0; 179472a44517SKent Overstreet } 179572a44517SKent Overstreet 179672a44517SKent Overstreet int bch_gc_thread_start(struct cache_set *c) 179772a44517SKent Overstreet { 1798be628be0SKent Overstreet c->gc_thread = kthread_run(bch_gc_thread, c, "bcache_gc"); 179972a44517SKent Overstreet if (IS_ERR(c->gc_thread)) 180072a44517SKent Overstreet return PTR_ERR(c->gc_thread); 180172a44517SKent Overstreet 180272a44517SKent Overstreet return 0; 1803cafe5635SKent Overstreet } 1804cafe5635SKent Overstreet 1805cafe5635SKent Overstreet /* Initial partial gc */ 1806cafe5635SKent Overstreet 1807487dded8SKent Overstreet static int bch_btree_check_recurse(struct btree *b, struct btree_op *op) 1808cafe5635SKent Overstreet { 180950310164SKent Overstreet int ret = 0; 181050310164SKent Overstreet struct bkey *k, *p = NULL; 1811cafe5635SKent Overstreet struct btree_iter iter; 1812cafe5635SKent Overstreet 1813487dded8SKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) 1814487dded8SKent Overstreet bch_initial_mark_key(b->c, b->level, k); 1815cafe5635SKent Overstreet 1816487dded8SKent Overstreet bch_initial_mark_key(b->c, b->level + 1, &b->key); 1817cafe5635SKent Overstreet 1818cafe5635SKent Overstreet if (b->level) { 1819c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, NULL); 1820cafe5635SKent Overstreet 182150310164SKent Overstreet do { 1822a85e968eSKent Overstreet k = bch_btree_iter_next_filter(&iter, &b->keys, 1823a85e968eSKent Overstreet bch_ptr_bad); 182450310164SKent Overstreet if (k) 18252452cc89SSlava Pestov btree_node_prefetch(b, k); 182650310164SKent Overstreet 1827cafe5635SKent Overstreet if (p) 1828487dded8SKent Overstreet ret = btree(check_recurse, p, b, op); 1829cafe5635SKent Overstreet 183050310164SKent Overstreet p = k; 183150310164SKent Overstreet } while (p && !ret); 1832cafe5635SKent Overstreet } 1833cafe5635SKent Overstreet 1834487dded8SKent Overstreet return ret; 1835cafe5635SKent Overstreet } 1836cafe5635SKent Overstreet 1837c18536a7SKent Overstreet int bch_btree_check(struct cache_set *c) 1838cafe5635SKent Overstreet { 1839c18536a7SKent Overstreet struct btree_op op; 1840cafe5635SKent Overstreet 1841b54d6934SKent Overstreet bch_btree_op_init(&op, SHRT_MAX); 1842cafe5635SKent Overstreet 1843487dded8SKent Overstreet return btree_root(check_recurse, c, &op); 1844cafe5635SKent Overstreet } 1845cafe5635SKent Overstreet 18462531d9eeSKent Overstreet void bch_initial_gc_finish(struct cache_set *c) 18472531d9eeSKent Overstreet { 18482531d9eeSKent Overstreet struct cache *ca; 18492531d9eeSKent Overstreet struct bucket *b; 18502531d9eeSKent Overstreet unsigned i; 18512531d9eeSKent Overstreet 18522531d9eeSKent Overstreet bch_btree_gc_finish(c); 18532531d9eeSKent Overstreet 18542531d9eeSKent Overstreet mutex_lock(&c->bucket_lock); 18552531d9eeSKent Overstreet 18562531d9eeSKent Overstreet /* 18572531d9eeSKent Overstreet * We need to put some unused buckets directly on the prio freelist in 18582531d9eeSKent Overstreet * order to get the allocator thread started - it needs freed buckets in 18592531d9eeSKent Overstreet * order to rewrite the prios and gens, and it needs to rewrite prios 18602531d9eeSKent Overstreet * and gens in order to free buckets. 18612531d9eeSKent Overstreet * 18622531d9eeSKent Overstreet * This is only safe for buckets that have no live data in them, which 18632531d9eeSKent Overstreet * there should always be some of. 18642531d9eeSKent Overstreet */ 18652531d9eeSKent Overstreet for_each_cache(ca, c, i) { 18662531d9eeSKent Overstreet for_each_bucket(b, ca) { 18672531d9eeSKent Overstreet if (fifo_full(&ca->free[RESERVE_PRIO])) 18682531d9eeSKent Overstreet break; 18692531d9eeSKent Overstreet 18702531d9eeSKent Overstreet if (bch_can_invalidate_bucket(ca, b) && 18712531d9eeSKent Overstreet !GC_MARK(b)) { 18722531d9eeSKent Overstreet __bch_invalidate_one_bucket(ca, b); 18732531d9eeSKent Overstreet fifo_push(&ca->free[RESERVE_PRIO], 18742531d9eeSKent Overstreet b - ca->buckets); 18752531d9eeSKent Overstreet } 18762531d9eeSKent Overstreet } 18772531d9eeSKent Overstreet } 18782531d9eeSKent Overstreet 18792531d9eeSKent Overstreet mutex_unlock(&c->bucket_lock); 18802531d9eeSKent Overstreet } 18812531d9eeSKent Overstreet 1882cafe5635SKent Overstreet /* Btree insertion */ 1883cafe5635SKent Overstreet 1884829a60b9SKent Overstreet static bool btree_insert_key(struct btree *b, struct bkey *k, 18851b207d80SKent Overstreet struct bkey *replace_key) 1886cafe5635SKent Overstreet { 1887829a60b9SKent Overstreet unsigned status; 1888cafe5635SKent Overstreet 1889cafe5635SKent Overstreet BUG_ON(bkey_cmp(k, &b->key) > 0); 1890cafe5635SKent Overstreet 1891829a60b9SKent Overstreet status = bch_btree_insert_key(&b->keys, k, replace_key); 1892829a60b9SKent Overstreet if (status != BTREE_INSERT_STATUS_NO_INSERT) { 1893dc9d98d6SKent Overstreet bch_check_keys(&b->keys, "%u for %s", status, 18941b207d80SKent Overstreet replace_key ? "replace" : "insert"); 1895cafe5635SKent Overstreet 1896829a60b9SKent Overstreet trace_bcache_btree_insert_key(b, k, replace_key != NULL, 1897829a60b9SKent Overstreet status); 1898cafe5635SKent Overstreet return true; 1899829a60b9SKent Overstreet } else 1900829a60b9SKent Overstreet return false; 1901cafe5635SKent Overstreet } 1902cafe5635SKent Overstreet 190359158fdeSKent Overstreet static size_t insert_u64s_remaining(struct btree *b) 190459158fdeSKent Overstreet { 19053572324aSKent Overstreet long ret = bch_btree_keys_u64s_remaining(&b->keys); 190659158fdeSKent Overstreet 190759158fdeSKent Overstreet /* 190859158fdeSKent Overstreet * Might land in the middle of an existing extent and have to split it 190959158fdeSKent Overstreet */ 191059158fdeSKent Overstreet if (b->keys.ops->is_extents) 191159158fdeSKent Overstreet ret -= KEY_MAX_U64S; 191259158fdeSKent Overstreet 191359158fdeSKent Overstreet return max(ret, 0L); 191459158fdeSKent Overstreet } 191559158fdeSKent Overstreet 191626c949f8SKent Overstreet static bool bch_btree_insert_keys(struct btree *b, struct btree_op *op, 19171b207d80SKent Overstreet struct keylist *insert_keys, 19181b207d80SKent Overstreet struct bkey *replace_key) 1919cafe5635SKent Overstreet { 1920cafe5635SKent Overstreet bool ret = false; 1921dc9d98d6SKent Overstreet int oldsize = bch_count_data(&b->keys); 1922cafe5635SKent Overstreet 192326c949f8SKent Overstreet while (!bch_keylist_empty(insert_keys)) { 1924c2f95ae2SKent Overstreet struct bkey *k = insert_keys->keys; 192526c949f8SKent Overstreet 192659158fdeSKent Overstreet if (bkey_u64s(k) > insert_u64s_remaining(b)) 1927403b6cdeSKent Overstreet break; 1928403b6cdeSKent Overstreet 1929403b6cdeSKent Overstreet if (bkey_cmp(k, &b->key) <= 0) { 19303a3b6a4eSKent Overstreet if (!b->level) 19313a3b6a4eSKent Overstreet bkey_put(b->c, k); 193226c949f8SKent Overstreet 1933829a60b9SKent Overstreet ret |= btree_insert_key(b, k, replace_key); 193426c949f8SKent Overstreet bch_keylist_pop_front(insert_keys); 193526c949f8SKent Overstreet } else if (bkey_cmp(&START_KEY(k), &b->key) < 0) { 193626c949f8SKent Overstreet BKEY_PADDED(key) temp; 1937c2f95ae2SKent Overstreet bkey_copy(&temp.key, insert_keys->keys); 193826c949f8SKent Overstreet 193926c949f8SKent Overstreet bch_cut_back(&b->key, &temp.key); 1940c2f95ae2SKent Overstreet bch_cut_front(&b->key, insert_keys->keys); 194126c949f8SKent Overstreet 1942829a60b9SKent Overstreet ret |= btree_insert_key(b, &temp.key, replace_key); 194326c949f8SKent Overstreet break; 194426c949f8SKent Overstreet } else { 194526c949f8SKent Overstreet break; 194626c949f8SKent Overstreet } 1947cafe5635SKent Overstreet } 1948cafe5635SKent Overstreet 1949829a60b9SKent Overstreet if (!ret) 1950829a60b9SKent Overstreet op->insert_collision = true; 1951829a60b9SKent Overstreet 1952403b6cdeSKent Overstreet BUG_ON(!bch_keylist_empty(insert_keys) && b->level); 1953403b6cdeSKent Overstreet 1954dc9d98d6SKent Overstreet BUG_ON(bch_count_data(&b->keys) < oldsize); 1955cafe5635SKent Overstreet return ret; 1956cafe5635SKent Overstreet } 1957cafe5635SKent Overstreet 195826c949f8SKent Overstreet static int btree_split(struct btree *b, struct btree_op *op, 195926c949f8SKent Overstreet struct keylist *insert_keys, 19601b207d80SKent Overstreet struct bkey *replace_key) 1961cafe5635SKent Overstreet { 1962d6fd3b11SKent Overstreet bool split; 1963cafe5635SKent Overstreet struct btree *n1, *n2 = NULL, *n3 = NULL; 1964cafe5635SKent Overstreet uint64_t start_time = local_clock(); 1965b54d6934SKent Overstreet struct closure cl; 196617e21a9fSKent Overstreet struct keylist parent_keys; 1967b54d6934SKent Overstreet 1968b54d6934SKent Overstreet closure_init_stack(&cl); 196917e21a9fSKent Overstreet bch_keylist_init(&parent_keys); 1970cafe5635SKent Overstreet 19710a63b66dSKent Overstreet if (btree_check_reserve(b, op)) { 19720a63b66dSKent Overstreet if (!b->level) 197378365411SKent Overstreet return -EINTR; 19740a63b66dSKent Overstreet else 19750a63b66dSKent Overstreet WARN(1, "insufficient reserve for split\n"); 19760a63b66dSKent Overstreet } 197778365411SKent Overstreet 19780a63b66dSKent Overstreet n1 = btree_node_alloc_replacement(b, op); 1979cafe5635SKent Overstreet if (IS_ERR(n1)) 1980cafe5635SKent Overstreet goto err; 1981cafe5635SKent Overstreet 1982ee811287SKent Overstreet split = set_blocks(btree_bset_first(n1), 1983ee811287SKent Overstreet block_bytes(n1->c)) > (btree_blocks(b) * 4) / 5; 1984cafe5635SKent Overstreet 1985cafe5635SKent Overstreet if (split) { 1986cafe5635SKent Overstreet unsigned keys = 0; 1987cafe5635SKent Overstreet 1988ee811287SKent Overstreet trace_bcache_btree_node_split(b, btree_bset_first(n1)->keys); 1989c37511b8SKent Overstreet 19902452cc89SSlava Pestov n2 = bch_btree_node_alloc(b->c, op, b->level, b->parent); 1991cafe5635SKent Overstreet if (IS_ERR(n2)) 1992cafe5635SKent Overstreet goto err_free1; 1993cafe5635SKent Overstreet 1994d6fd3b11SKent Overstreet if (!b->parent) { 19952452cc89SSlava Pestov n3 = bch_btree_node_alloc(b->c, op, b->level + 1, NULL); 1996cafe5635SKent Overstreet if (IS_ERR(n3)) 1997cafe5635SKent Overstreet goto err_free2; 1998cafe5635SKent Overstreet } 1999cafe5635SKent Overstreet 20002a285686SKent Overstreet mutex_lock(&n1->write_lock); 20012a285686SKent Overstreet mutex_lock(&n2->write_lock); 20022a285686SKent Overstreet 20031b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 2004cafe5635SKent Overstreet 2005d6fd3b11SKent Overstreet /* 2006d6fd3b11SKent Overstreet * Has to be a linear search because we don't have an auxiliary 2007cafe5635SKent Overstreet * search tree yet 2008cafe5635SKent Overstreet */ 2009cafe5635SKent Overstreet 2010ee811287SKent Overstreet while (keys < (btree_bset_first(n1)->keys * 3) / 5) 2011ee811287SKent Overstreet keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), 2012fafff81cSKent Overstreet keys)); 2013cafe5635SKent Overstreet 2014fafff81cSKent Overstreet bkey_copy_key(&n1->key, 2015ee811287SKent Overstreet bset_bkey_idx(btree_bset_first(n1), keys)); 2016ee811287SKent Overstreet keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), keys)); 2017cafe5635SKent Overstreet 2018ee811287SKent Overstreet btree_bset_first(n2)->keys = btree_bset_first(n1)->keys - keys; 2019ee811287SKent Overstreet btree_bset_first(n1)->keys = keys; 2020cafe5635SKent Overstreet 2021ee811287SKent Overstreet memcpy(btree_bset_first(n2)->start, 2022ee811287SKent Overstreet bset_bkey_last(btree_bset_first(n1)), 2023ee811287SKent Overstreet btree_bset_first(n2)->keys * sizeof(uint64_t)); 2024cafe5635SKent Overstreet 2025cafe5635SKent Overstreet bkey_copy_key(&n2->key, &b->key); 2026cafe5635SKent Overstreet 202717e21a9fSKent Overstreet bch_keylist_add(&parent_keys, &n2->key); 2028b54d6934SKent Overstreet bch_btree_node_write(n2, &cl); 20292a285686SKent Overstreet mutex_unlock(&n2->write_lock); 2030cafe5635SKent Overstreet rw_unlock(true, n2); 2031c37511b8SKent Overstreet } else { 2032ee811287SKent Overstreet trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys); 2033c37511b8SKent Overstreet 20342a285686SKent Overstreet mutex_lock(&n1->write_lock); 20351b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 2036c37511b8SKent Overstreet } 2037cafe5635SKent Overstreet 203817e21a9fSKent Overstreet bch_keylist_add(&parent_keys, &n1->key); 2039b54d6934SKent Overstreet bch_btree_node_write(n1, &cl); 20402a285686SKent Overstreet mutex_unlock(&n1->write_lock); 2041cafe5635SKent Overstreet 2042cafe5635SKent Overstreet if (n3) { 2043d6fd3b11SKent Overstreet /* Depth increases, make a new root */ 20442a285686SKent Overstreet mutex_lock(&n3->write_lock); 2045cafe5635SKent Overstreet bkey_copy_key(&n3->key, &MAX_KEY); 204617e21a9fSKent Overstreet bch_btree_insert_keys(n3, op, &parent_keys, NULL); 2047b54d6934SKent Overstreet bch_btree_node_write(n3, &cl); 20482a285686SKent Overstreet mutex_unlock(&n3->write_lock); 2049cafe5635SKent Overstreet 2050b54d6934SKent Overstreet closure_sync(&cl); 2051cafe5635SKent Overstreet bch_btree_set_root(n3); 2052cafe5635SKent Overstreet rw_unlock(true, n3); 2053d6fd3b11SKent Overstreet } else if (!b->parent) { 2054d6fd3b11SKent Overstreet /* Root filled up but didn't need to be split */ 2055b54d6934SKent Overstreet closure_sync(&cl); 2056cafe5635SKent Overstreet bch_btree_set_root(n1); 2057cafe5635SKent Overstreet } else { 205817e21a9fSKent Overstreet /* Split a non root node */ 2059b54d6934SKent Overstreet closure_sync(&cl); 206017e21a9fSKent Overstreet make_btree_freeing_key(b, parent_keys.top); 206117e21a9fSKent Overstreet bch_keylist_push(&parent_keys); 206217e21a9fSKent Overstreet 206317e21a9fSKent Overstreet bch_btree_insert_node(b->parent, op, &parent_keys, NULL, NULL); 206417e21a9fSKent Overstreet BUG_ON(!bch_keylist_empty(&parent_keys)); 2065cafe5635SKent Overstreet } 2066cafe5635SKent Overstreet 206705335cffSKent Overstreet btree_node_free(b); 2068cafe5635SKent Overstreet rw_unlock(true, n1); 2069cafe5635SKent Overstreet 2070169ef1cfSKent Overstreet bch_time_stats_update(&b->c->btree_split_time, start_time); 2071cafe5635SKent Overstreet 2072cafe5635SKent Overstreet return 0; 2073cafe5635SKent Overstreet err_free2: 20745f5837d2SKent Overstreet bkey_put(b->c, &n2->key); 2075e8e1d468SKent Overstreet btree_node_free(n2); 2076cafe5635SKent Overstreet rw_unlock(true, n2); 2077cafe5635SKent Overstreet err_free1: 20785f5837d2SKent Overstreet bkey_put(b->c, &n1->key); 2079e8e1d468SKent Overstreet btree_node_free(n1); 2080cafe5635SKent Overstreet rw_unlock(true, n1); 2081cafe5635SKent Overstreet err: 20820a63b66dSKent Overstreet WARN(1, "bcache: btree split failed (level %u)", b->level); 20835f5837d2SKent Overstreet 2084cafe5635SKent Overstreet if (n3 == ERR_PTR(-EAGAIN) || 2085cafe5635SKent Overstreet n2 == ERR_PTR(-EAGAIN) || 2086cafe5635SKent Overstreet n1 == ERR_PTR(-EAGAIN)) 2087cafe5635SKent Overstreet return -EAGAIN; 2088cafe5635SKent Overstreet 2089cafe5635SKent Overstreet return -ENOMEM; 2090cafe5635SKent Overstreet } 2091cafe5635SKent Overstreet 209226c949f8SKent Overstreet static int bch_btree_insert_node(struct btree *b, struct btree_op *op, 2093c18536a7SKent Overstreet struct keylist *insert_keys, 20941b207d80SKent Overstreet atomic_t *journal_ref, 20951b207d80SKent Overstreet struct bkey *replace_key) 209626c949f8SKent Overstreet { 20972a285686SKent Overstreet struct closure cl; 20982a285686SKent Overstreet 20991b207d80SKent Overstreet BUG_ON(b->level && replace_key); 21001b207d80SKent Overstreet 21012a285686SKent Overstreet closure_init_stack(&cl); 21022a285686SKent Overstreet 21032a285686SKent Overstreet mutex_lock(&b->write_lock); 21042a285686SKent Overstreet 21052a285686SKent Overstreet if (write_block(b) != btree_bset_last(b) && 21062a285686SKent Overstreet b->keys.last_set_unwritten) 21072a285686SKent Overstreet bch_btree_init_next(b); /* just wrote a set */ 21082a285686SKent Overstreet 210959158fdeSKent Overstreet if (bch_keylist_nkeys(insert_keys) > insert_u64s_remaining(b)) { 21102a285686SKent Overstreet mutex_unlock(&b->write_lock); 21112a285686SKent Overstreet goto split; 21122a285686SKent Overstreet } 21132a285686SKent Overstreet 21142a285686SKent Overstreet BUG_ON(write_block(b) != btree_bset_last(b)); 21152a285686SKent Overstreet 21162a285686SKent Overstreet if (bch_btree_insert_keys(b, op, insert_keys, replace_key)) { 21172a285686SKent Overstreet if (!b->level) 21182a285686SKent Overstreet bch_btree_leaf_dirty(b, journal_ref); 21192a285686SKent Overstreet else 21202a285686SKent Overstreet bch_btree_node_write(b, &cl); 21212a285686SKent Overstreet } 21222a285686SKent Overstreet 21232a285686SKent Overstreet mutex_unlock(&b->write_lock); 21242a285686SKent Overstreet 21252a285686SKent Overstreet /* wait for btree node write if necessary, after unlock */ 21262a285686SKent Overstreet closure_sync(&cl); 21272a285686SKent Overstreet 21282a285686SKent Overstreet return 0; 21292a285686SKent Overstreet split: 213026c949f8SKent Overstreet if (current->bio_list) { 213126c949f8SKent Overstreet op->lock = b->c->root->level + 1; 213217e21a9fSKent Overstreet return -EAGAIN; 213326c949f8SKent Overstreet } else if (op->lock <= b->c->root->level) { 213426c949f8SKent Overstreet op->lock = b->c->root->level + 1; 213517e21a9fSKent Overstreet return -EINTR; 213626c949f8SKent Overstreet } else { 213717e21a9fSKent Overstreet /* Invalidated all iterators */ 21383b3e9e50SKent Overstreet int ret = btree_split(b, op, insert_keys, replace_key); 21393b3e9e50SKent Overstreet 21402a285686SKent Overstreet if (bch_keylist_empty(insert_keys)) 214117e21a9fSKent Overstreet return 0; 21422a285686SKent Overstreet else if (!ret) 21432a285686SKent Overstreet return -EINTR; 21442a285686SKent Overstreet return ret; 214517e21a9fSKent Overstreet } 214626c949f8SKent Overstreet } 214726c949f8SKent Overstreet 2148e7c590ebSKent Overstreet int bch_btree_insert_check_key(struct btree *b, struct btree_op *op, 2149e7c590ebSKent Overstreet struct bkey *check_key) 2150e7c590ebSKent Overstreet { 2151e7c590ebSKent Overstreet int ret = -EINTR; 2152e7c590ebSKent Overstreet uint64_t btree_ptr = b->key.ptr[0]; 2153e7c590ebSKent Overstreet unsigned long seq = b->seq; 2154e7c590ebSKent Overstreet struct keylist insert; 2155e7c590ebSKent Overstreet bool upgrade = op->lock == -1; 2156e7c590ebSKent Overstreet 2157e7c590ebSKent Overstreet bch_keylist_init(&insert); 2158e7c590ebSKent Overstreet 2159e7c590ebSKent Overstreet if (upgrade) { 2160e7c590ebSKent Overstreet rw_unlock(false, b); 2161e7c590ebSKent Overstreet rw_lock(true, b, b->level); 2162e7c590ebSKent Overstreet 2163e7c590ebSKent Overstreet if (b->key.ptr[0] != btree_ptr || 21642ef9ccbfSZheng Liu b->seq != seq + 1) { 21652ef9ccbfSZheng Liu op->lock = b->level; 2166e7c590ebSKent Overstreet goto out; 2167e7c590ebSKent Overstreet } 21682ef9ccbfSZheng Liu } 2169e7c590ebSKent Overstreet 2170e7c590ebSKent Overstreet SET_KEY_PTRS(check_key, 1); 2171e7c590ebSKent Overstreet get_random_bytes(&check_key->ptr[0], sizeof(uint64_t)); 2172e7c590ebSKent Overstreet 2173e7c590ebSKent Overstreet SET_PTR_DEV(check_key, 0, PTR_CHECK_DEV); 2174e7c590ebSKent Overstreet 2175e7c590ebSKent Overstreet bch_keylist_add(&insert, check_key); 2176e7c590ebSKent Overstreet 21771b207d80SKent Overstreet ret = bch_btree_insert_node(b, op, &insert, NULL, NULL); 2178e7c590ebSKent Overstreet 2179e7c590ebSKent Overstreet BUG_ON(!ret && !bch_keylist_empty(&insert)); 2180e7c590ebSKent Overstreet out: 2181e7c590ebSKent Overstreet if (upgrade) 2182e7c590ebSKent Overstreet downgrade_write(&b->lock); 2183e7c590ebSKent Overstreet return ret; 2184e7c590ebSKent Overstreet } 2185e7c590ebSKent Overstreet 2186cc7b8819SKent Overstreet struct btree_insert_op { 2187cc7b8819SKent Overstreet struct btree_op op; 2188cc7b8819SKent Overstreet struct keylist *keys; 2189cc7b8819SKent Overstreet atomic_t *journal_ref; 2190cc7b8819SKent Overstreet struct bkey *replace_key; 2191cc7b8819SKent Overstreet }; 2192cc7b8819SKent Overstreet 219308239ca2SWei Yongjun static int btree_insert_fn(struct btree_op *b_op, struct btree *b) 2194cafe5635SKent Overstreet { 2195cc7b8819SKent Overstreet struct btree_insert_op *op = container_of(b_op, 2196cc7b8819SKent Overstreet struct btree_insert_op, op); 2197403b6cdeSKent Overstreet 2198cc7b8819SKent Overstreet int ret = bch_btree_insert_node(b, &op->op, op->keys, 2199cc7b8819SKent Overstreet op->journal_ref, op->replace_key); 2200cc7b8819SKent Overstreet if (ret && !bch_keylist_empty(op->keys)) 2201cc7b8819SKent Overstreet return ret; 2202cc7b8819SKent Overstreet else 2203cc7b8819SKent Overstreet return MAP_DONE; 2204cafe5635SKent Overstreet } 2205cafe5635SKent Overstreet 2206cc7b8819SKent Overstreet int bch_btree_insert(struct cache_set *c, struct keylist *keys, 2207cc7b8819SKent Overstreet atomic_t *journal_ref, struct bkey *replace_key) 2208cafe5635SKent Overstreet { 2209cc7b8819SKent Overstreet struct btree_insert_op op; 2210cafe5635SKent Overstreet int ret = 0; 2211cafe5635SKent Overstreet 2212cc7b8819SKent Overstreet BUG_ON(current->bio_list); 22134f3d4014SKent Overstreet BUG_ON(bch_keylist_empty(keys)); 2214cafe5635SKent Overstreet 2215cc7b8819SKent Overstreet bch_btree_op_init(&op.op, 0); 2216cc7b8819SKent Overstreet op.keys = keys; 2217cc7b8819SKent Overstreet op.journal_ref = journal_ref; 2218cc7b8819SKent Overstreet op.replace_key = replace_key; 2219cafe5635SKent Overstreet 2220cc7b8819SKent Overstreet while (!ret && !bch_keylist_empty(keys)) { 2221cc7b8819SKent Overstreet op.op.lock = 0; 2222cc7b8819SKent Overstreet ret = bch_btree_map_leaf_nodes(&op.op, c, 2223cc7b8819SKent Overstreet &START_KEY(keys->keys), 2224cc7b8819SKent Overstreet btree_insert_fn); 2225cc7b8819SKent Overstreet } 2226cc7b8819SKent Overstreet 2227cc7b8819SKent Overstreet if (ret) { 2228cafe5635SKent Overstreet struct bkey *k; 2229cafe5635SKent Overstreet 22301b207d80SKent Overstreet pr_err("error %i", ret); 2231cafe5635SKent Overstreet 22324f3d4014SKent Overstreet while ((k = bch_keylist_pop(keys))) 22333a3b6a4eSKent Overstreet bkey_put(c, k); 2234cc7b8819SKent Overstreet } else if (op.op.insert_collision) 2235cc7b8819SKent Overstreet ret = -ESRCH; 22366054c6d4SKent Overstreet 2237cafe5635SKent Overstreet return ret; 2238cafe5635SKent Overstreet } 2239cafe5635SKent Overstreet 2240cafe5635SKent Overstreet void bch_btree_set_root(struct btree *b) 2241cafe5635SKent Overstreet { 2242cafe5635SKent Overstreet unsigned i; 2243e49c7c37SKent Overstreet struct closure cl; 2244e49c7c37SKent Overstreet 2245e49c7c37SKent Overstreet closure_init_stack(&cl); 2246cafe5635SKent Overstreet 2247c37511b8SKent Overstreet trace_bcache_btree_set_root(b); 2248c37511b8SKent Overstreet 2249cafe5635SKent Overstreet BUG_ON(!b->written); 2250cafe5635SKent Overstreet 2251cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) 2252cafe5635SKent Overstreet BUG_ON(PTR_BUCKET(b->c, &b->key, i)->prio != BTREE_PRIO); 2253cafe5635SKent Overstreet 2254cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 2255cafe5635SKent Overstreet list_del_init(&b->list); 2256cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 2257cafe5635SKent Overstreet 2258cafe5635SKent Overstreet b->c->root = b; 2259cafe5635SKent Overstreet 2260e49c7c37SKent Overstreet bch_journal_meta(b->c, &cl); 2261e49c7c37SKent Overstreet closure_sync(&cl); 2262cafe5635SKent Overstreet } 2263cafe5635SKent Overstreet 226448dad8baSKent Overstreet /* Map across nodes or keys */ 226548dad8baSKent Overstreet 226648dad8baSKent Overstreet static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op, 226748dad8baSKent Overstreet struct bkey *from, 226848dad8baSKent Overstreet btree_map_nodes_fn *fn, int flags) 226948dad8baSKent Overstreet { 227048dad8baSKent Overstreet int ret = MAP_CONTINUE; 227148dad8baSKent Overstreet 227248dad8baSKent Overstreet if (b->level) { 227348dad8baSKent Overstreet struct bkey *k; 227448dad8baSKent Overstreet struct btree_iter iter; 227548dad8baSKent Overstreet 2276c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, from); 227748dad8baSKent Overstreet 2278a85e968eSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, &b->keys, 227948dad8baSKent Overstreet bch_ptr_bad))) { 228048dad8baSKent Overstreet ret = btree(map_nodes_recurse, k, b, 228148dad8baSKent Overstreet op, from, fn, flags); 228248dad8baSKent Overstreet from = NULL; 228348dad8baSKent Overstreet 228448dad8baSKent Overstreet if (ret != MAP_CONTINUE) 228548dad8baSKent Overstreet return ret; 228648dad8baSKent Overstreet } 228748dad8baSKent Overstreet } 228848dad8baSKent Overstreet 228948dad8baSKent Overstreet if (!b->level || flags == MAP_ALL_NODES) 229048dad8baSKent Overstreet ret = fn(op, b); 229148dad8baSKent Overstreet 229248dad8baSKent Overstreet return ret; 229348dad8baSKent Overstreet } 229448dad8baSKent Overstreet 229548dad8baSKent Overstreet int __bch_btree_map_nodes(struct btree_op *op, struct cache_set *c, 229648dad8baSKent Overstreet struct bkey *from, btree_map_nodes_fn *fn, int flags) 229748dad8baSKent Overstreet { 2298b54d6934SKent Overstreet return btree_root(map_nodes_recurse, c, op, from, fn, flags); 229948dad8baSKent Overstreet } 230048dad8baSKent Overstreet 230148dad8baSKent Overstreet static int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op, 230248dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, 230348dad8baSKent Overstreet int flags) 230448dad8baSKent Overstreet { 230548dad8baSKent Overstreet int ret = MAP_CONTINUE; 230648dad8baSKent Overstreet struct bkey *k; 230748dad8baSKent Overstreet struct btree_iter iter; 230848dad8baSKent Overstreet 2309c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, from); 231048dad8baSKent Overstreet 2311a85e968eSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) { 231248dad8baSKent Overstreet ret = !b->level 231348dad8baSKent Overstreet ? fn(op, b, k) 231448dad8baSKent Overstreet : btree(map_keys_recurse, k, b, op, from, fn, flags); 231548dad8baSKent Overstreet from = NULL; 231648dad8baSKent Overstreet 231748dad8baSKent Overstreet if (ret != MAP_CONTINUE) 231848dad8baSKent Overstreet return ret; 231948dad8baSKent Overstreet } 232048dad8baSKent Overstreet 232148dad8baSKent Overstreet if (!b->level && (flags & MAP_END_KEY)) 232248dad8baSKent Overstreet ret = fn(op, b, &KEY(KEY_INODE(&b->key), 232348dad8baSKent Overstreet KEY_OFFSET(&b->key), 0)); 232448dad8baSKent Overstreet 232548dad8baSKent Overstreet return ret; 232648dad8baSKent Overstreet } 232748dad8baSKent Overstreet 232848dad8baSKent Overstreet int bch_btree_map_keys(struct btree_op *op, struct cache_set *c, 232948dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, int flags) 233048dad8baSKent Overstreet { 2331b54d6934SKent Overstreet return btree_root(map_keys_recurse, c, op, from, fn, flags); 233248dad8baSKent Overstreet } 233348dad8baSKent Overstreet 2334cafe5635SKent Overstreet /* Keybuf code */ 2335cafe5635SKent Overstreet 2336cafe5635SKent Overstreet static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r) 2337cafe5635SKent Overstreet { 2338cafe5635SKent Overstreet /* Overlapping keys compare equal */ 2339cafe5635SKent Overstreet if (bkey_cmp(&l->key, &START_KEY(&r->key)) <= 0) 2340cafe5635SKent Overstreet return -1; 2341cafe5635SKent Overstreet if (bkey_cmp(&START_KEY(&l->key), &r->key) >= 0) 2342cafe5635SKent Overstreet return 1; 2343cafe5635SKent Overstreet return 0; 2344cafe5635SKent Overstreet } 2345cafe5635SKent Overstreet 2346cafe5635SKent Overstreet static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l, 2347cafe5635SKent Overstreet struct keybuf_key *r) 2348cafe5635SKent Overstreet { 2349cafe5635SKent Overstreet return clamp_t(int64_t, bkey_cmp(&l->key, &r->key), -1, 1); 2350cafe5635SKent Overstreet } 2351cafe5635SKent Overstreet 235248dad8baSKent Overstreet struct refill { 235348dad8baSKent Overstreet struct btree_op op; 235448a915a8SKent Overstreet unsigned nr_found; 235548dad8baSKent Overstreet struct keybuf *buf; 235648dad8baSKent Overstreet struct bkey *end; 235748dad8baSKent Overstreet keybuf_pred_fn *pred; 235848dad8baSKent Overstreet }; 235948dad8baSKent Overstreet 236048dad8baSKent Overstreet static int refill_keybuf_fn(struct btree_op *op, struct btree *b, 236148dad8baSKent Overstreet struct bkey *k) 2362cafe5635SKent Overstreet { 236348dad8baSKent Overstreet struct refill *refill = container_of(op, struct refill, op); 236448dad8baSKent Overstreet struct keybuf *buf = refill->buf; 236548dad8baSKent Overstreet int ret = MAP_CONTINUE; 2366cafe5635SKent Overstreet 236748dad8baSKent Overstreet if (bkey_cmp(k, refill->end) >= 0) { 236848dad8baSKent Overstreet ret = MAP_DONE; 236948dad8baSKent Overstreet goto out; 2370cafe5635SKent Overstreet } 2371cafe5635SKent Overstreet 237248dad8baSKent Overstreet if (!KEY_SIZE(k)) /* end key */ 237348dad8baSKent Overstreet goto out; 2374cafe5635SKent Overstreet 237548dad8baSKent Overstreet if (refill->pred(buf, k)) { 2376cafe5635SKent Overstreet struct keybuf_key *w; 2377cafe5635SKent Overstreet 2378cafe5635SKent Overstreet spin_lock(&buf->lock); 2379cafe5635SKent Overstreet 2380cafe5635SKent Overstreet w = array_alloc(&buf->freelist); 238148dad8baSKent Overstreet if (!w) { 238248dad8baSKent Overstreet spin_unlock(&buf->lock); 238348dad8baSKent Overstreet return MAP_DONE; 238448dad8baSKent Overstreet } 2385cafe5635SKent Overstreet 2386cafe5635SKent Overstreet w->private = NULL; 2387cafe5635SKent Overstreet bkey_copy(&w->key, k); 2388cafe5635SKent Overstreet 2389cafe5635SKent Overstreet if (RB_INSERT(&buf->keys, w, node, keybuf_cmp)) 2390cafe5635SKent Overstreet array_free(&buf->freelist, w); 239148a915a8SKent Overstreet else 239248a915a8SKent Overstreet refill->nr_found++; 2393cafe5635SKent Overstreet 239448dad8baSKent Overstreet if (array_freelist_empty(&buf->freelist)) 239548dad8baSKent Overstreet ret = MAP_DONE; 239648dad8baSKent Overstreet 2397cafe5635SKent Overstreet spin_unlock(&buf->lock); 2398cafe5635SKent Overstreet } 239948dad8baSKent Overstreet out: 240048dad8baSKent Overstreet buf->last_scanned = *k; 240148dad8baSKent Overstreet return ret; 2402cafe5635SKent Overstreet } 2403cafe5635SKent Overstreet 2404cafe5635SKent Overstreet void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf, 240572c27061SKent Overstreet struct bkey *end, keybuf_pred_fn *pred) 2406cafe5635SKent Overstreet { 2407cafe5635SKent Overstreet struct bkey start = buf->last_scanned; 240848dad8baSKent Overstreet struct refill refill; 2409cafe5635SKent Overstreet 2410cafe5635SKent Overstreet cond_resched(); 2411cafe5635SKent Overstreet 2412b54d6934SKent Overstreet bch_btree_op_init(&refill.op, -1); 241348a915a8SKent Overstreet refill.nr_found = 0; 241448dad8baSKent Overstreet refill.buf = buf; 241548dad8baSKent Overstreet refill.end = end; 241648dad8baSKent Overstreet refill.pred = pred; 241748dad8baSKent Overstreet 241848dad8baSKent Overstreet bch_btree_map_keys(&refill.op, c, &buf->last_scanned, 241948dad8baSKent Overstreet refill_keybuf_fn, MAP_END_KEY); 2420cafe5635SKent Overstreet 242148a915a8SKent Overstreet trace_bcache_keyscan(refill.nr_found, 2422cafe5635SKent Overstreet KEY_INODE(&start), KEY_OFFSET(&start), 242348a915a8SKent Overstreet KEY_INODE(&buf->last_scanned), 242448a915a8SKent Overstreet KEY_OFFSET(&buf->last_scanned)); 2425cafe5635SKent Overstreet 2426cafe5635SKent Overstreet spin_lock(&buf->lock); 2427cafe5635SKent Overstreet 2428cafe5635SKent Overstreet if (!RB_EMPTY_ROOT(&buf->keys)) { 2429cafe5635SKent Overstreet struct keybuf_key *w; 2430cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2431cafe5635SKent Overstreet buf->start = START_KEY(&w->key); 2432cafe5635SKent Overstreet 2433cafe5635SKent Overstreet w = RB_LAST(&buf->keys, struct keybuf_key, node); 2434cafe5635SKent Overstreet buf->end = w->key; 2435cafe5635SKent Overstreet } else { 2436cafe5635SKent Overstreet buf->start = MAX_KEY; 2437cafe5635SKent Overstreet buf->end = MAX_KEY; 2438cafe5635SKent Overstreet } 2439cafe5635SKent Overstreet 2440cafe5635SKent Overstreet spin_unlock(&buf->lock); 2441cafe5635SKent Overstreet } 2442cafe5635SKent Overstreet 2443cafe5635SKent Overstreet static void __bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2444cafe5635SKent Overstreet { 2445cafe5635SKent Overstreet rb_erase(&w->node, &buf->keys); 2446cafe5635SKent Overstreet array_free(&buf->freelist, w); 2447cafe5635SKent Overstreet } 2448cafe5635SKent Overstreet 2449cafe5635SKent Overstreet void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2450cafe5635SKent Overstreet { 2451cafe5635SKent Overstreet spin_lock(&buf->lock); 2452cafe5635SKent Overstreet __bch_keybuf_del(buf, w); 2453cafe5635SKent Overstreet spin_unlock(&buf->lock); 2454cafe5635SKent Overstreet } 2455cafe5635SKent Overstreet 2456cafe5635SKent Overstreet bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start, 2457cafe5635SKent Overstreet struct bkey *end) 2458cafe5635SKent Overstreet { 2459cafe5635SKent Overstreet bool ret = false; 2460cafe5635SKent Overstreet struct keybuf_key *p, *w, s; 2461cafe5635SKent Overstreet s.key = *start; 2462cafe5635SKent Overstreet 2463cafe5635SKent Overstreet if (bkey_cmp(end, &buf->start) <= 0 || 2464cafe5635SKent Overstreet bkey_cmp(start, &buf->end) >= 0) 2465cafe5635SKent Overstreet return false; 2466cafe5635SKent Overstreet 2467cafe5635SKent Overstreet spin_lock(&buf->lock); 2468cafe5635SKent Overstreet w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp); 2469cafe5635SKent Overstreet 2470cafe5635SKent Overstreet while (w && bkey_cmp(&START_KEY(&w->key), end) < 0) { 2471cafe5635SKent Overstreet p = w; 2472cafe5635SKent Overstreet w = RB_NEXT(w, node); 2473cafe5635SKent Overstreet 2474cafe5635SKent Overstreet if (p->private) 2475cafe5635SKent Overstreet ret = true; 2476cafe5635SKent Overstreet else 2477cafe5635SKent Overstreet __bch_keybuf_del(buf, p); 2478cafe5635SKent Overstreet } 2479cafe5635SKent Overstreet 2480cafe5635SKent Overstreet spin_unlock(&buf->lock); 2481cafe5635SKent Overstreet return ret; 2482cafe5635SKent Overstreet } 2483cafe5635SKent Overstreet 2484cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next(struct keybuf *buf) 2485cafe5635SKent Overstreet { 2486cafe5635SKent Overstreet struct keybuf_key *w; 2487cafe5635SKent Overstreet spin_lock(&buf->lock); 2488cafe5635SKent Overstreet 2489cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2490cafe5635SKent Overstreet 2491cafe5635SKent Overstreet while (w && w->private) 2492cafe5635SKent Overstreet w = RB_NEXT(w, node); 2493cafe5635SKent Overstreet 2494cafe5635SKent Overstreet if (w) 2495cafe5635SKent Overstreet w->private = ERR_PTR(-EINTR); 2496cafe5635SKent Overstreet 2497cafe5635SKent Overstreet spin_unlock(&buf->lock); 2498cafe5635SKent Overstreet return w; 2499cafe5635SKent Overstreet } 2500cafe5635SKent Overstreet 2501cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c, 2502cafe5635SKent Overstreet struct keybuf *buf, 250372c27061SKent Overstreet struct bkey *end, 250472c27061SKent Overstreet keybuf_pred_fn *pred) 2505cafe5635SKent Overstreet { 2506cafe5635SKent Overstreet struct keybuf_key *ret; 2507cafe5635SKent Overstreet 2508cafe5635SKent Overstreet while (1) { 2509cafe5635SKent Overstreet ret = bch_keybuf_next(buf); 2510cafe5635SKent Overstreet if (ret) 2511cafe5635SKent Overstreet break; 2512cafe5635SKent Overstreet 2513cafe5635SKent Overstreet if (bkey_cmp(&buf->last_scanned, end) >= 0) { 2514cafe5635SKent Overstreet pr_debug("scan finished"); 2515cafe5635SKent Overstreet break; 2516cafe5635SKent Overstreet } 2517cafe5635SKent Overstreet 251872c27061SKent Overstreet bch_refill_keybuf(c, buf, end, pred); 2519cafe5635SKent Overstreet } 2520cafe5635SKent Overstreet 2521cafe5635SKent Overstreet return ret; 2522cafe5635SKent Overstreet } 2523cafe5635SKent Overstreet 252472c27061SKent Overstreet void bch_keybuf_init(struct keybuf *buf) 2525cafe5635SKent Overstreet { 2526cafe5635SKent Overstreet buf->last_scanned = MAX_KEY; 2527cafe5635SKent Overstreet buf->keys = RB_ROOT; 2528cafe5635SKent Overstreet 2529cafe5635SKent Overstreet spin_lock_init(&buf->lock); 2530cafe5635SKent Overstreet array_allocator_init(&buf->freelist); 2531cafe5635SKent Overstreet } 2532