1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0 2cafe5635SKent Overstreet /* 3cafe5635SKent Overstreet * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com> 4cafe5635SKent Overstreet * 5cafe5635SKent Overstreet * Uses a block device as cache for other block devices; optimized for SSDs. 6cafe5635SKent Overstreet * All allocation is done in buckets, which should match the erase block size 7cafe5635SKent Overstreet * of the device. 8cafe5635SKent Overstreet * 9cafe5635SKent Overstreet * Buckets containing cached data are kept on a heap sorted by priority; 10cafe5635SKent Overstreet * bucket priority is increased on cache hit, and periodically all the buckets 11cafe5635SKent Overstreet * on the heap have their priority scaled down. This currently is just used as 12cafe5635SKent Overstreet * an LRU but in the future should allow for more intelligent heuristics. 13cafe5635SKent Overstreet * 14cafe5635SKent Overstreet * Buckets have an 8 bit counter; freeing is accomplished by incrementing the 15cafe5635SKent Overstreet * counter. Garbage collection is used to remove stale pointers. 16cafe5635SKent Overstreet * 17cafe5635SKent Overstreet * Indexing is done via a btree; nodes are not necessarily fully sorted, rather 18cafe5635SKent Overstreet * as keys are inserted we only sort the pages that have not yet been written. 19cafe5635SKent Overstreet * When garbage collection is run, we resort the entire node. 20cafe5635SKent Overstreet * 215fb94e9cSMauro Carvalho Chehab * All configuration is done via sysfs; see Documentation/admin-guide/bcache.rst. 22cafe5635SKent Overstreet */ 23cafe5635SKent Overstreet 24cafe5635SKent Overstreet #include "bcache.h" 25cafe5635SKent Overstreet #include "btree.h" 26cafe5635SKent Overstreet #include "debug.h" 2765d45231SKent Overstreet #include "extents.h" 28cafe5635SKent Overstreet 29cafe5635SKent Overstreet #include <linux/slab.h> 30cafe5635SKent Overstreet #include <linux/bitops.h> 31cafe5635SKent Overstreet #include <linux/hash.h> 3272a44517SKent Overstreet #include <linux/kthread.h> 33cd953ed0SGeert Uytterhoeven #include <linux/prefetch.h> 34cafe5635SKent Overstreet #include <linux/random.h> 35cafe5635SKent Overstreet #include <linux/rcupdate.h> 36e6017571SIngo Molnar #include <linux/sched/clock.h> 37b2d09103SIngo Molnar #include <linux/rculist.h> 38b2d09103SIngo Molnar 39cafe5635SKent Overstreet #include <trace/events/bcache.h> 40cafe5635SKent Overstreet 41cafe5635SKent Overstreet /* 42cafe5635SKent Overstreet * Todo: 43cafe5635SKent Overstreet * register_bcache: Return errors out to userspace correctly 44cafe5635SKent Overstreet * 45cafe5635SKent Overstreet * Writeback: don't undirty key until after a cache flush 46cafe5635SKent Overstreet * 47cafe5635SKent Overstreet * Create an iterator for key pointers 48cafe5635SKent Overstreet * 49cafe5635SKent Overstreet * On btree write error, mark bucket such that it won't be freed from the cache 50cafe5635SKent Overstreet * 51cafe5635SKent Overstreet * Journalling: 52cafe5635SKent Overstreet * Check for bad keys in replay 53cafe5635SKent Overstreet * Propagate barriers 54cafe5635SKent Overstreet * Refcount journal entries in journal_replay 55cafe5635SKent Overstreet * 56cafe5635SKent Overstreet * Garbage collection: 57cafe5635SKent Overstreet * Finish incremental gc 58cafe5635SKent Overstreet * Gc should free old UUIDs, data for invalid UUIDs 59cafe5635SKent Overstreet * 60cafe5635SKent Overstreet * Provide a way to list backing device UUIDs we have data cached for, and 61cafe5635SKent Overstreet * probably how long it's been since we've seen them, and a way to invalidate 62cafe5635SKent Overstreet * dirty data for devices that will never be attached again 63cafe5635SKent Overstreet * 64cafe5635SKent Overstreet * Keep 1 min/5 min/15 min statistics of how busy a block device has been, so 65cafe5635SKent Overstreet * that based on that and how much dirty data we have we can keep writeback 66cafe5635SKent Overstreet * from being starved 67cafe5635SKent Overstreet * 68cafe5635SKent Overstreet * Add a tracepoint or somesuch to watch for writeback starvation 69cafe5635SKent Overstreet * 70cafe5635SKent Overstreet * When btree depth > 1 and splitting an interior node, we have to make sure 71cafe5635SKent Overstreet * alloc_bucket() cannot fail. This should be true but is not completely 72cafe5635SKent Overstreet * obvious. 73cafe5635SKent Overstreet * 74cafe5635SKent Overstreet * Plugging? 75cafe5635SKent Overstreet * 76cafe5635SKent Overstreet * If data write is less than hard sector size of ssd, round up offset in open 77cafe5635SKent Overstreet * bucket to the next whole sector 78cafe5635SKent Overstreet * 79cafe5635SKent Overstreet * Superblock needs to be fleshed out for multiple cache devices 80cafe5635SKent Overstreet * 81cafe5635SKent Overstreet * Add a sysfs tunable for the number of writeback IOs in flight 82cafe5635SKent Overstreet * 83cafe5635SKent Overstreet * Add a sysfs tunable for the number of open data buckets 84cafe5635SKent Overstreet * 85cafe5635SKent Overstreet * IO tracking: Can we track when one process is doing io on behalf of another? 86cafe5635SKent Overstreet * IO tracking: Don't use just an average, weigh more recent stuff higher 87cafe5635SKent Overstreet * 88cafe5635SKent Overstreet * Test module load/unload 89cafe5635SKent Overstreet */ 90cafe5635SKent Overstreet 91cafe5635SKent Overstreet #define MAX_NEED_GC 64 92cafe5635SKent Overstreet #define MAX_SAVE_PRIO 72 93*5c25c4fcSTang Junhui #define MIN_GC_NODES 100 94*5c25c4fcSTang Junhui #define GC_SLEEP_MS 100 95cafe5635SKent Overstreet 96cafe5635SKent Overstreet #define PTR_DIRTY_BIT (((uint64_t) 1 << 36)) 97cafe5635SKent Overstreet 98cafe5635SKent Overstreet #define PTR_HASH(c, k) \ 99cafe5635SKent Overstreet (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0)) 100cafe5635SKent Overstreet 101df8e8970SKent Overstreet #define insert_lock(s, b) ((b)->level <= (s)->lock) 102df8e8970SKent Overstreet 103df8e8970SKent Overstreet /* 104df8e8970SKent Overstreet * These macros are for recursing down the btree - they handle the details of 105df8e8970SKent Overstreet * locking and looking up nodes in the cache for you. They're best treated as 106df8e8970SKent Overstreet * mere syntax when reading code that uses them. 107df8e8970SKent Overstreet * 108df8e8970SKent Overstreet * op->lock determines whether we take a read or a write lock at a given depth. 109df8e8970SKent Overstreet * If you've got a read lock and find that you need a write lock (i.e. you're 110df8e8970SKent Overstreet * going to have to split), set op->lock and return -EINTR; btree_root() will 111df8e8970SKent Overstreet * call you again and you'll have the correct lock. 112df8e8970SKent Overstreet */ 113df8e8970SKent Overstreet 114df8e8970SKent Overstreet /** 115df8e8970SKent Overstreet * btree - recurse down the btree on a specified key 116df8e8970SKent Overstreet * @fn: function to call, which will be passed the child node 117df8e8970SKent Overstreet * @key: key to recurse on 118df8e8970SKent Overstreet * @b: parent btree node 119df8e8970SKent Overstreet * @op: pointer to struct btree_op 120df8e8970SKent Overstreet */ 121df8e8970SKent Overstreet #define btree(fn, key, b, op, ...) \ 122df8e8970SKent Overstreet ({ \ 123df8e8970SKent Overstreet int _r, l = (b)->level - 1; \ 124df8e8970SKent Overstreet bool _w = l <= (op)->lock; \ 1252452cc89SSlava Pestov struct btree *_child = bch_btree_node_get((b)->c, op, key, l, \ 1262452cc89SSlava Pestov _w, b); \ 127df8e8970SKent Overstreet if (!IS_ERR(_child)) { \ 128df8e8970SKent Overstreet _r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__); \ 129df8e8970SKent Overstreet rw_unlock(_w, _child); \ 130df8e8970SKent Overstreet } else \ 131df8e8970SKent Overstreet _r = PTR_ERR(_child); \ 132df8e8970SKent Overstreet _r; \ 133df8e8970SKent Overstreet }) 134df8e8970SKent Overstreet 135df8e8970SKent Overstreet /** 136df8e8970SKent Overstreet * btree_root - call a function on the root of the btree 137df8e8970SKent Overstreet * @fn: function to call, which will be passed the child node 138df8e8970SKent Overstreet * @c: cache set 139df8e8970SKent Overstreet * @op: pointer to struct btree_op 140df8e8970SKent Overstreet */ 141df8e8970SKent Overstreet #define btree_root(fn, c, op, ...) \ 142df8e8970SKent Overstreet ({ \ 143df8e8970SKent Overstreet int _r = -EINTR; \ 144df8e8970SKent Overstreet do { \ 145df8e8970SKent Overstreet struct btree *_b = (c)->root; \ 146df8e8970SKent Overstreet bool _w = insert_lock(op, _b); \ 147df8e8970SKent Overstreet rw_lock(_w, _b, _b->level); \ 148df8e8970SKent Overstreet if (_b == (c)->root && \ 149df8e8970SKent Overstreet _w == insert_lock(op, _b)) { \ 150df8e8970SKent Overstreet _r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__); \ 151df8e8970SKent Overstreet } \ 152df8e8970SKent Overstreet rw_unlock(_w, _b); \ 1530a63b66dSKent Overstreet bch_cannibalize_unlock(c); \ 15478365411SKent Overstreet if (_r == -EINTR) \ 15578365411SKent Overstreet schedule(); \ 156df8e8970SKent Overstreet } while (_r == -EINTR); \ 157df8e8970SKent Overstreet \ 1580a63b66dSKent Overstreet finish_wait(&(c)->btree_cache_wait, &(op)->wait); \ 159df8e8970SKent Overstreet _r; \ 160df8e8970SKent Overstreet }) 161df8e8970SKent Overstreet 162a85e968eSKent Overstreet static inline struct bset *write_block(struct btree *b) 163a85e968eSKent Overstreet { 164a85e968eSKent Overstreet return ((void *) btree_bset_first(b)) + b->written * block_bytes(b->c); 165a85e968eSKent Overstreet } 166a85e968eSKent Overstreet 1672a285686SKent Overstreet static void bch_btree_init_next(struct btree *b) 1682a285686SKent Overstreet { 1692a285686SKent Overstreet /* If not a leaf node, always sort */ 1702a285686SKent Overstreet if (b->level && b->keys.nsets) 1712a285686SKent Overstreet bch_btree_sort(&b->keys, &b->c->sort); 1722a285686SKent Overstreet else 1732a285686SKent Overstreet bch_btree_sort_lazy(&b->keys, &b->c->sort); 1742a285686SKent Overstreet 1752a285686SKent Overstreet if (b->written < btree_blocks(b)) 1762a285686SKent Overstreet bch_bset_init_next(&b->keys, write_block(b), 1772a285686SKent Overstreet bset_magic(&b->c->sb)); 1782a285686SKent Overstreet 1792a285686SKent Overstreet } 1802a285686SKent Overstreet 181cafe5635SKent Overstreet /* Btree key manipulation */ 182cafe5635SKent Overstreet 1833a3b6a4eSKent Overstreet void bkey_put(struct cache_set *c, struct bkey *k) 184e7c590ebSKent Overstreet { 185e7c590ebSKent Overstreet unsigned i; 186e7c590ebSKent Overstreet 187e7c590ebSKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 188e7c590ebSKent Overstreet if (ptr_available(c, k, i)) 189e7c590ebSKent Overstreet atomic_dec_bug(&PTR_BUCKET(c, k, i)->pin); 190e7c590ebSKent Overstreet } 191e7c590ebSKent Overstreet 192cafe5635SKent Overstreet /* Btree IO */ 193cafe5635SKent Overstreet 194cafe5635SKent Overstreet static uint64_t btree_csum_set(struct btree *b, struct bset *i) 195cafe5635SKent Overstreet { 196cafe5635SKent Overstreet uint64_t crc = b->key.ptr[0]; 197fafff81cSKent Overstreet void *data = (void *) i + 8, *end = bset_bkey_last(i); 198cafe5635SKent Overstreet 199169ef1cfSKent Overstreet crc = bch_crc64_update(crc, data, end - data); 200c19ed23aSKent Overstreet return crc ^ 0xffffffffffffffffULL; 201cafe5635SKent Overstreet } 202cafe5635SKent Overstreet 20378b77bf8SKent Overstreet void bch_btree_node_read_done(struct btree *b) 204cafe5635SKent Overstreet { 205cafe5635SKent Overstreet const char *err = "bad btree header"; 206ee811287SKent Overstreet struct bset *i = btree_bset_first(b); 20757943511SKent Overstreet struct btree_iter *iter; 208cafe5635SKent Overstreet 209d19936a2SKent Overstreet iter = mempool_alloc(&b->c->fill_iter, GFP_NOIO); 21057943511SKent Overstreet iter->size = b->c->sb.bucket_size / b->c->sb.block_size; 211cafe5635SKent Overstreet iter->used = 0; 212cafe5635SKent Overstreet 213280481d0SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 214c052dd9aSKent Overstreet iter->b = &b->keys; 215280481d0SKent Overstreet #endif 216280481d0SKent Overstreet 21757943511SKent Overstreet if (!i->seq) 218cafe5635SKent Overstreet goto err; 219cafe5635SKent Overstreet 220cafe5635SKent Overstreet for (; 221a85e968eSKent Overstreet b->written < btree_blocks(b) && i->seq == b->keys.set[0].data->seq; 222cafe5635SKent Overstreet i = write_block(b)) { 223cafe5635SKent Overstreet err = "unsupported bset version"; 224cafe5635SKent Overstreet if (i->version > BCACHE_BSET_VERSION) 225cafe5635SKent Overstreet goto err; 226cafe5635SKent Overstreet 227cafe5635SKent Overstreet err = "bad btree header"; 228ee811287SKent Overstreet if (b->written + set_blocks(i, block_bytes(b->c)) > 229ee811287SKent Overstreet btree_blocks(b)) 230cafe5635SKent Overstreet goto err; 231cafe5635SKent Overstreet 232cafe5635SKent Overstreet err = "bad magic"; 23381ab4190SKent Overstreet if (i->magic != bset_magic(&b->c->sb)) 234cafe5635SKent Overstreet goto err; 235cafe5635SKent Overstreet 236cafe5635SKent Overstreet err = "bad checksum"; 237cafe5635SKent Overstreet switch (i->version) { 238cafe5635SKent Overstreet case 0: 239cafe5635SKent Overstreet if (i->csum != csum_set(i)) 240cafe5635SKent Overstreet goto err; 241cafe5635SKent Overstreet break; 242cafe5635SKent Overstreet case BCACHE_BSET_VERSION: 243cafe5635SKent Overstreet if (i->csum != btree_csum_set(b, i)) 244cafe5635SKent Overstreet goto err; 245cafe5635SKent Overstreet break; 246cafe5635SKent Overstreet } 247cafe5635SKent Overstreet 248cafe5635SKent Overstreet err = "empty set"; 249a85e968eSKent Overstreet if (i != b->keys.set[0].data && !i->keys) 250cafe5635SKent Overstreet goto err; 251cafe5635SKent Overstreet 252fafff81cSKent Overstreet bch_btree_iter_push(iter, i->start, bset_bkey_last(i)); 253cafe5635SKent Overstreet 254ee811287SKent Overstreet b->written += set_blocks(i, block_bytes(b->c)); 255cafe5635SKent Overstreet } 256cafe5635SKent Overstreet 257cafe5635SKent Overstreet err = "corrupted btree"; 258cafe5635SKent Overstreet for (i = write_block(b); 259a85e968eSKent Overstreet bset_sector_offset(&b->keys, i) < KEY_SIZE(&b->key); 260cafe5635SKent Overstreet i = ((void *) i) + block_bytes(b->c)) 261a85e968eSKent Overstreet if (i->seq == b->keys.set[0].data->seq) 262cafe5635SKent Overstreet goto err; 263cafe5635SKent Overstreet 264a85e968eSKent Overstreet bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort); 265cafe5635SKent Overstreet 266a85e968eSKent Overstreet i = b->keys.set[0].data; 267cafe5635SKent Overstreet err = "short btree key"; 268a85e968eSKent Overstreet if (b->keys.set[0].size && 269a85e968eSKent Overstreet bkey_cmp(&b->key, &b->keys.set[0].end) < 0) 270cafe5635SKent Overstreet goto err; 271cafe5635SKent Overstreet 272cafe5635SKent Overstreet if (b->written < btree_blocks(b)) 273a85e968eSKent Overstreet bch_bset_init_next(&b->keys, write_block(b), 274a85e968eSKent Overstreet bset_magic(&b->c->sb)); 275cafe5635SKent Overstreet out: 276d19936a2SKent Overstreet mempool_free(iter, &b->c->fill_iter); 27757943511SKent Overstreet return; 278cafe5635SKent Overstreet err: 279cafe5635SKent Overstreet set_btree_node_io_error(b); 28088b9f8c4SKent Overstreet bch_cache_set_error(b->c, "%s at bucket %zu, block %u, %u keys", 281cafe5635SKent Overstreet err, PTR_BUCKET_NR(b->c, &b->key, 0), 28288b9f8c4SKent Overstreet bset_block_offset(b, i), i->keys); 283cafe5635SKent Overstreet goto out; 284cafe5635SKent Overstreet } 285cafe5635SKent Overstreet 2864246a0b6SChristoph Hellwig static void btree_node_read_endio(struct bio *bio) 287cafe5635SKent Overstreet { 28857943511SKent Overstreet struct closure *cl = bio->bi_private; 28957943511SKent Overstreet closure_put(cl); 29057943511SKent Overstreet } 291cafe5635SKent Overstreet 29278b77bf8SKent Overstreet static void bch_btree_node_read(struct btree *b) 29357943511SKent Overstreet { 29457943511SKent Overstreet uint64_t start_time = local_clock(); 29557943511SKent Overstreet struct closure cl; 29657943511SKent Overstreet struct bio *bio; 297cafe5635SKent Overstreet 298c37511b8SKent Overstreet trace_bcache_btree_read(b); 299c37511b8SKent Overstreet 30057943511SKent Overstreet closure_init_stack(&cl); 301cafe5635SKent Overstreet 30257943511SKent Overstreet bio = bch_bbio_alloc(b->c); 3034f024f37SKent Overstreet bio->bi_iter.bi_size = KEY_SIZE(&b->key) << 9; 30457943511SKent Overstreet bio->bi_end_io = btree_node_read_endio; 30557943511SKent Overstreet bio->bi_private = &cl; 30670fd7614SChristoph Hellwig bio->bi_opf = REQ_OP_READ | REQ_META; 30757943511SKent Overstreet 308a85e968eSKent Overstreet bch_bio_map(bio, b->keys.set[0].data); 30957943511SKent Overstreet 31057943511SKent Overstreet bch_submit_bbio(bio, b->c, &b->key, 0); 31157943511SKent Overstreet closure_sync(&cl); 31257943511SKent Overstreet 3134e4cbee9SChristoph Hellwig if (bio->bi_status) 31457943511SKent Overstreet set_btree_node_io_error(b); 31557943511SKent Overstreet 31657943511SKent Overstreet bch_bbio_free(bio, b->c); 31757943511SKent Overstreet 31857943511SKent Overstreet if (btree_node_io_error(b)) 31957943511SKent Overstreet goto err; 32057943511SKent Overstreet 32157943511SKent Overstreet bch_btree_node_read_done(b); 32257943511SKent Overstreet bch_time_stats_update(&b->c->btree_read_time, start_time); 32357943511SKent Overstreet 32457943511SKent Overstreet return; 32557943511SKent Overstreet err: 32661cbd250SGeert Uytterhoeven bch_cache_set_error(b->c, "io error reading bucket %zu", 32757943511SKent Overstreet PTR_BUCKET_NR(b->c, &b->key, 0)); 328cafe5635SKent Overstreet } 329cafe5635SKent Overstreet 330cafe5635SKent Overstreet static void btree_complete_write(struct btree *b, struct btree_write *w) 331cafe5635SKent Overstreet { 332cafe5635SKent Overstreet if (w->prio_blocked && 333cafe5635SKent Overstreet !atomic_sub_return(w->prio_blocked, &b->c->prio_blocked)) 334119ba0f8SKent Overstreet wake_up_allocators(b->c); 335cafe5635SKent Overstreet 336cafe5635SKent Overstreet if (w->journal) { 337cafe5635SKent Overstreet atomic_dec_bug(w->journal); 338cafe5635SKent Overstreet __closure_wake_up(&b->c->journal.wait); 339cafe5635SKent Overstreet } 340cafe5635SKent Overstreet 341cafe5635SKent Overstreet w->prio_blocked = 0; 342cafe5635SKent Overstreet w->journal = NULL; 343cafe5635SKent Overstreet } 344cafe5635SKent Overstreet 345cb7a583eSKent Overstreet static void btree_node_write_unlock(struct closure *cl) 346cb7a583eSKent Overstreet { 347cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 348cb7a583eSKent Overstreet 349cb7a583eSKent Overstreet up(&b->io_mutex); 350cb7a583eSKent Overstreet } 351cb7a583eSKent Overstreet 35257943511SKent Overstreet static void __btree_node_write_done(struct closure *cl) 353cafe5635SKent Overstreet { 354cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 355cafe5635SKent Overstreet struct btree_write *w = btree_prev_write(b); 356cafe5635SKent Overstreet 357cafe5635SKent Overstreet bch_bbio_free(b->bio, b->c); 358cafe5635SKent Overstreet b->bio = NULL; 359cafe5635SKent Overstreet btree_complete_write(b, w); 360cafe5635SKent Overstreet 361cafe5635SKent Overstreet if (btree_node_dirty(b)) 36256b30770SKent Overstreet schedule_delayed_work(&b->work, 30 * HZ); 363cafe5635SKent Overstreet 364cb7a583eSKent Overstreet closure_return_with_destructor(cl, btree_node_write_unlock); 365cafe5635SKent Overstreet } 366cafe5635SKent Overstreet 36757943511SKent Overstreet static void btree_node_write_done(struct closure *cl) 368cafe5635SKent Overstreet { 369cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 370cafe5635SKent Overstreet 371491221f8SGuoqing Jiang bio_free_pages(b->bio); 37257943511SKent Overstreet __btree_node_write_done(cl); 373cafe5635SKent Overstreet } 374cafe5635SKent Overstreet 3754246a0b6SChristoph Hellwig static void btree_node_write_endio(struct bio *bio) 37657943511SKent Overstreet { 37757943511SKent Overstreet struct closure *cl = bio->bi_private; 378cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 37957943511SKent Overstreet 3804e4cbee9SChristoph Hellwig if (bio->bi_status) 38157943511SKent Overstreet set_btree_node_io_error(b); 38257943511SKent Overstreet 3834e4cbee9SChristoph Hellwig bch_bbio_count_io_errors(b->c, bio, bio->bi_status, "writing btree"); 38457943511SKent Overstreet closure_put(cl); 38557943511SKent Overstreet } 38657943511SKent Overstreet 38757943511SKent Overstreet static void do_btree_node_write(struct btree *b) 388cafe5635SKent Overstreet { 389cb7a583eSKent Overstreet struct closure *cl = &b->io; 390ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 391cafe5635SKent Overstreet BKEY_PADDED(key) k; 392cafe5635SKent Overstreet 393cafe5635SKent Overstreet i->version = BCACHE_BSET_VERSION; 394cafe5635SKent Overstreet i->csum = btree_csum_set(b, i); 395cafe5635SKent Overstreet 39657943511SKent Overstreet BUG_ON(b->bio); 39757943511SKent Overstreet b->bio = bch_bbio_alloc(b->c); 39857943511SKent Overstreet 39957943511SKent Overstreet b->bio->bi_end_io = btree_node_write_endio; 400faadf0c9SKent Overstreet b->bio->bi_private = cl; 401ee811287SKent Overstreet b->bio->bi_iter.bi_size = roundup(set_bytes(i), block_bytes(b->c)); 40270fd7614SChristoph Hellwig b->bio->bi_opf = REQ_OP_WRITE | REQ_META | REQ_FUA; 403169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 404cafe5635SKent Overstreet 405e49c7c37SKent Overstreet /* 406e49c7c37SKent Overstreet * If we're appending to a leaf node, we don't technically need FUA - 407e49c7c37SKent Overstreet * this write just needs to be persisted before the next journal write, 408e49c7c37SKent Overstreet * which will be marked FLUSH|FUA. 409e49c7c37SKent Overstreet * 410e49c7c37SKent Overstreet * Similarly if we're writing a new btree root - the pointer is going to 411e49c7c37SKent Overstreet * be in the next journal entry. 412e49c7c37SKent Overstreet * 413e49c7c37SKent Overstreet * But if we're writing a new btree node (that isn't a root) or 414e49c7c37SKent Overstreet * appending to a non leaf btree node, we need either FUA or a flush 415e49c7c37SKent Overstreet * when we write the parent with the new pointer. FUA is cheaper than a 416e49c7c37SKent Overstreet * flush, and writes appending to leaf nodes aren't blocking anything so 417e49c7c37SKent Overstreet * just make all btree node writes FUA to keep things sane. 418e49c7c37SKent Overstreet */ 419e49c7c37SKent Overstreet 420cafe5635SKent Overstreet bkey_copy(&k.key, &b->key); 421ee811287SKent Overstreet SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) + 422a85e968eSKent Overstreet bset_sector_offset(&b->keys, i)); 423cafe5635SKent Overstreet 42425d8be77SMing Lei if (!bch_bio_alloc_pages(b->bio, __GFP_NOWARN|GFP_NOWAIT)) { 425cafe5635SKent Overstreet int j; 426cafe5635SKent Overstreet struct bio_vec *bv; 427cafe5635SKent Overstreet void *base = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1)); 428cafe5635SKent Overstreet 4297988613bSKent Overstreet bio_for_each_segment_all(bv, b->bio, j) 430cafe5635SKent Overstreet memcpy(page_address(bv->bv_page), 431cafe5635SKent Overstreet base + j * PAGE_SIZE, PAGE_SIZE); 432cafe5635SKent Overstreet 433cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 434cafe5635SKent Overstreet 43557943511SKent Overstreet continue_at(cl, btree_node_write_done, NULL); 436cafe5635SKent Overstreet } else { 437c2421edfSMing Lei /* No problem for multipage bvec since the bio is just allocated */ 438cafe5635SKent Overstreet b->bio->bi_vcnt = 0; 439169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 440cafe5635SKent Overstreet 441cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 442cafe5635SKent Overstreet 443cafe5635SKent Overstreet closure_sync(cl); 444cb7a583eSKent Overstreet continue_at_nobarrier(cl, __btree_node_write_done, NULL); 445cafe5635SKent Overstreet } 446cafe5635SKent Overstreet } 447cafe5635SKent Overstreet 4482a285686SKent Overstreet void __bch_btree_node_write(struct btree *b, struct closure *parent) 449cafe5635SKent Overstreet { 450ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 451cafe5635SKent Overstreet 4522a285686SKent Overstreet lockdep_assert_held(&b->write_lock); 4532a285686SKent Overstreet 454c37511b8SKent Overstreet trace_bcache_btree_write(b); 455c37511b8SKent Overstreet 456cafe5635SKent Overstreet BUG_ON(current->bio_list); 45757943511SKent Overstreet BUG_ON(b->written >= btree_blocks(b)); 45857943511SKent Overstreet BUG_ON(b->written && !i->keys); 459ee811287SKent Overstreet BUG_ON(btree_bset_first(b)->seq != i->seq); 460dc9d98d6SKent Overstreet bch_check_keys(&b->keys, "writing"); 461cafe5635SKent Overstreet 462cafe5635SKent Overstreet cancel_delayed_work(&b->work); 463cafe5635SKent Overstreet 46457943511SKent Overstreet /* If caller isn't waiting for write, parent refcount is cache set */ 465cb7a583eSKent Overstreet down(&b->io_mutex); 466cb7a583eSKent Overstreet closure_init(&b->io, parent ?: &b->c->cl); 46757943511SKent Overstreet 468cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 469cafe5635SKent Overstreet change_bit(BTREE_NODE_write_idx, &b->flags); 470cafe5635SKent Overstreet 47157943511SKent Overstreet do_btree_node_write(b); 472cafe5635SKent Overstreet 473ee811287SKent Overstreet atomic_long_add(set_blocks(i, block_bytes(b->c)) * b->c->sb.block_size, 474cafe5635SKent Overstreet &PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written); 475cafe5635SKent Overstreet 476a85e968eSKent Overstreet b->written += set_blocks(i, block_bytes(b->c)); 4772a285686SKent Overstreet } 478a85e968eSKent Overstreet 4792a285686SKent Overstreet void bch_btree_node_write(struct btree *b, struct closure *parent) 4802a285686SKent Overstreet { 4812a285686SKent Overstreet unsigned nsets = b->keys.nsets; 4822a285686SKent Overstreet 4832a285686SKent Overstreet lockdep_assert_held(&b->lock); 4842a285686SKent Overstreet 4852a285686SKent Overstreet __bch_btree_node_write(b, parent); 486cafe5635SKent Overstreet 48778b77bf8SKent Overstreet /* 48878b77bf8SKent Overstreet * do verify if there was more than one set initially (i.e. we did a 48978b77bf8SKent Overstreet * sort) and we sorted down to a single set: 49078b77bf8SKent Overstreet */ 4912a285686SKent Overstreet if (nsets && !b->keys.nsets) 49278b77bf8SKent Overstreet bch_btree_verify(b); 49378b77bf8SKent Overstreet 4942a285686SKent Overstreet bch_btree_init_next(b); 495cafe5635SKent Overstreet } 496cafe5635SKent Overstreet 497f269af5aSKent Overstreet static void bch_btree_node_write_sync(struct btree *b) 498f269af5aSKent Overstreet { 499f269af5aSKent Overstreet struct closure cl; 500f269af5aSKent Overstreet 501f269af5aSKent Overstreet closure_init_stack(&cl); 5022a285686SKent Overstreet 5032a285686SKent Overstreet mutex_lock(&b->write_lock); 504f269af5aSKent Overstreet bch_btree_node_write(b, &cl); 5052a285686SKent Overstreet mutex_unlock(&b->write_lock); 5062a285686SKent Overstreet 507f269af5aSKent Overstreet closure_sync(&cl); 508f269af5aSKent Overstreet } 509f269af5aSKent Overstreet 51057943511SKent Overstreet static void btree_node_write_work(struct work_struct *w) 511cafe5635SKent Overstreet { 512cafe5635SKent Overstreet struct btree *b = container_of(to_delayed_work(w), struct btree, work); 513cafe5635SKent Overstreet 5142a285686SKent Overstreet mutex_lock(&b->write_lock); 515cafe5635SKent Overstreet if (btree_node_dirty(b)) 5162a285686SKent Overstreet __bch_btree_node_write(b, NULL); 5172a285686SKent Overstreet mutex_unlock(&b->write_lock); 518cafe5635SKent Overstreet } 519cafe5635SKent Overstreet 520c18536a7SKent Overstreet static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref) 521cafe5635SKent Overstreet { 522ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 523cafe5635SKent Overstreet struct btree_write *w = btree_current_write(b); 524cafe5635SKent Overstreet 5252a285686SKent Overstreet lockdep_assert_held(&b->write_lock); 5262a285686SKent Overstreet 52757943511SKent Overstreet BUG_ON(!b->written); 52857943511SKent Overstreet BUG_ON(!i->keys); 529cafe5635SKent Overstreet 53057943511SKent Overstreet if (!btree_node_dirty(b)) 53156b30770SKent Overstreet schedule_delayed_work(&b->work, 30 * HZ); 53257943511SKent Overstreet 533cafe5635SKent Overstreet set_btree_node_dirty(b); 534cafe5635SKent Overstreet 535c18536a7SKent Overstreet if (journal_ref) { 536cafe5635SKent Overstreet if (w->journal && 537c18536a7SKent Overstreet journal_pin_cmp(b->c, w->journal, journal_ref)) { 538cafe5635SKent Overstreet atomic_dec_bug(w->journal); 539cafe5635SKent Overstreet w->journal = NULL; 540cafe5635SKent Overstreet } 541cafe5635SKent Overstreet 542cafe5635SKent Overstreet if (!w->journal) { 543c18536a7SKent Overstreet w->journal = journal_ref; 544cafe5635SKent Overstreet atomic_inc(w->journal); 545cafe5635SKent Overstreet } 546cafe5635SKent Overstreet } 547cafe5635SKent Overstreet 548cafe5635SKent Overstreet /* Force write if set is too big */ 54957943511SKent Overstreet if (set_bytes(i) > PAGE_SIZE - 48 && 55057943511SKent Overstreet !current->bio_list) 55157943511SKent Overstreet bch_btree_node_write(b, NULL); 552cafe5635SKent Overstreet } 553cafe5635SKent Overstreet 554cafe5635SKent Overstreet /* 555cafe5635SKent Overstreet * Btree in memory cache - allocation/freeing 556cafe5635SKent Overstreet * mca -> memory cache 557cafe5635SKent Overstreet */ 558cafe5635SKent Overstreet 559cafe5635SKent Overstreet #define mca_reserve(c) (((c->root && c->root->level) \ 560cafe5635SKent Overstreet ? c->root->level : 1) * 8 + 16) 561cafe5635SKent Overstreet #define mca_can_free(c) \ 5620a63b66dSKent Overstreet max_t(int, 0, c->btree_cache_used - mca_reserve(c)) 563cafe5635SKent Overstreet 564cafe5635SKent Overstreet static void mca_data_free(struct btree *b) 565cafe5635SKent Overstreet { 566cb7a583eSKent Overstreet BUG_ON(b->io_mutex.count != 1); 567cafe5635SKent Overstreet 568a85e968eSKent Overstreet bch_btree_keys_free(&b->keys); 569cafe5635SKent Overstreet 5700a63b66dSKent Overstreet b->c->btree_cache_used--; 571ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 572cafe5635SKent Overstreet } 573cafe5635SKent Overstreet 574cafe5635SKent Overstreet static void mca_bucket_free(struct btree *b) 575cafe5635SKent Overstreet { 576cafe5635SKent Overstreet BUG_ON(btree_node_dirty(b)); 577cafe5635SKent Overstreet 578cafe5635SKent Overstreet b->key.ptr[0] = 0; 579cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 580cafe5635SKent Overstreet list_move(&b->list, &b->c->btree_cache_freeable); 581cafe5635SKent Overstreet } 582cafe5635SKent Overstreet 583cafe5635SKent Overstreet static unsigned btree_order(struct bkey *k) 584cafe5635SKent Overstreet { 585cafe5635SKent Overstreet return ilog2(KEY_SIZE(k) / PAGE_SECTORS ?: 1); 586cafe5635SKent Overstreet } 587cafe5635SKent Overstreet 588cafe5635SKent Overstreet static void mca_data_alloc(struct btree *b, struct bkey *k, gfp_t gfp) 589cafe5635SKent Overstreet { 590a85e968eSKent Overstreet if (!bch_btree_keys_alloc(&b->keys, 591ee811287SKent Overstreet max_t(unsigned, 592cafe5635SKent Overstreet ilog2(b->c->btree_pages), 593ee811287SKent Overstreet btree_order(k)), 594ee811287SKent Overstreet gfp)) { 5950a63b66dSKent Overstreet b->c->btree_cache_used++; 596ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache); 597ee811287SKent Overstreet } else { 598ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 599ee811287SKent Overstreet } 600cafe5635SKent Overstreet } 601cafe5635SKent Overstreet 602cafe5635SKent Overstreet static struct btree *mca_bucket_alloc(struct cache_set *c, 603cafe5635SKent Overstreet struct bkey *k, gfp_t gfp) 604cafe5635SKent Overstreet { 605cafe5635SKent Overstreet struct btree *b = kzalloc(sizeof(struct btree), gfp); 606cafe5635SKent Overstreet if (!b) 607cafe5635SKent Overstreet return NULL; 608cafe5635SKent Overstreet 609cafe5635SKent Overstreet init_rwsem(&b->lock); 610cafe5635SKent Overstreet lockdep_set_novalidate_class(&b->lock); 6112a285686SKent Overstreet mutex_init(&b->write_lock); 6122a285686SKent Overstreet lockdep_set_novalidate_class(&b->write_lock); 613cafe5635SKent Overstreet INIT_LIST_HEAD(&b->list); 61457943511SKent Overstreet INIT_DELAYED_WORK(&b->work, btree_node_write_work); 615cafe5635SKent Overstreet b->c = c; 616cb7a583eSKent Overstreet sema_init(&b->io_mutex, 1); 617cafe5635SKent Overstreet 618cafe5635SKent Overstreet mca_data_alloc(b, k, gfp); 619cafe5635SKent Overstreet return b; 620cafe5635SKent Overstreet } 621cafe5635SKent Overstreet 622e8e1d468SKent Overstreet static int mca_reap(struct btree *b, unsigned min_order, bool flush) 623cafe5635SKent Overstreet { 624e8e1d468SKent Overstreet struct closure cl; 625e8e1d468SKent Overstreet 626e8e1d468SKent Overstreet closure_init_stack(&cl); 627cafe5635SKent Overstreet lockdep_assert_held(&b->c->bucket_lock); 628cafe5635SKent Overstreet 629cafe5635SKent Overstreet if (!down_write_trylock(&b->lock)) 630cafe5635SKent Overstreet return -ENOMEM; 631cafe5635SKent Overstreet 632a85e968eSKent Overstreet BUG_ON(btree_node_dirty(b) && !b->keys.set[0].data); 633e8e1d468SKent Overstreet 634a85e968eSKent Overstreet if (b->keys.page_order < min_order) 635cb7a583eSKent Overstreet goto out_unlock; 636cb7a583eSKent Overstreet 637cb7a583eSKent Overstreet if (!flush) { 638cb7a583eSKent Overstreet if (btree_node_dirty(b)) 639cb7a583eSKent Overstreet goto out_unlock; 640cb7a583eSKent Overstreet 641cb7a583eSKent Overstreet if (down_trylock(&b->io_mutex)) 642cb7a583eSKent Overstreet goto out_unlock; 643cb7a583eSKent Overstreet up(&b->io_mutex); 644cafe5635SKent Overstreet } 645cafe5635SKent Overstreet 6462a285686SKent Overstreet mutex_lock(&b->write_lock); 647f269af5aSKent Overstreet if (btree_node_dirty(b)) 6482a285686SKent Overstreet __bch_btree_node_write(b, &cl); 6492a285686SKent Overstreet mutex_unlock(&b->write_lock); 6502a285686SKent Overstreet 6512a285686SKent Overstreet closure_sync(&cl); 652cafe5635SKent Overstreet 653e8e1d468SKent Overstreet /* wait for any in flight btree write */ 654cb7a583eSKent Overstreet down(&b->io_mutex); 655cb7a583eSKent Overstreet up(&b->io_mutex); 656e8e1d468SKent Overstreet 657cafe5635SKent Overstreet return 0; 658cb7a583eSKent Overstreet out_unlock: 659cb7a583eSKent Overstreet rw_unlock(true, b); 660cb7a583eSKent Overstreet return -ENOMEM; 661cafe5635SKent Overstreet } 662cafe5635SKent Overstreet 6637dc19d5aSDave Chinner static unsigned long bch_mca_scan(struct shrinker *shrink, 6647dc19d5aSDave Chinner struct shrink_control *sc) 665cafe5635SKent Overstreet { 666cafe5635SKent Overstreet struct cache_set *c = container_of(shrink, struct cache_set, shrink); 667cafe5635SKent Overstreet struct btree *b, *t; 668cafe5635SKent Overstreet unsigned long i, nr = sc->nr_to_scan; 6697dc19d5aSDave Chinner unsigned long freed = 0; 670ca71df31STang Junhui unsigned int btree_cache_used; 671cafe5635SKent Overstreet 672cafe5635SKent Overstreet if (c->shrinker_disabled) 6737dc19d5aSDave Chinner return SHRINK_STOP; 674cafe5635SKent Overstreet 6750a63b66dSKent Overstreet if (c->btree_cache_alloc_lock) 6767dc19d5aSDave Chinner return SHRINK_STOP; 677cafe5635SKent Overstreet 678cafe5635SKent Overstreet /* Return -1 if we can't do anything right now */ 679a698e08cSKent Overstreet if (sc->gfp_mask & __GFP_IO) 680cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 681cafe5635SKent Overstreet else if (!mutex_trylock(&c->bucket_lock)) 682cafe5635SKent Overstreet return -1; 683cafe5635SKent Overstreet 68436c9ea98SKent Overstreet /* 68536c9ea98SKent Overstreet * It's _really_ critical that we don't free too many btree nodes - we 68636c9ea98SKent Overstreet * have to always leave ourselves a reserve. The reserve is how we 68736c9ea98SKent Overstreet * guarantee that allocating memory for a new btree node can always 68836c9ea98SKent Overstreet * succeed, so that inserting keys into the btree can always succeed and 68936c9ea98SKent Overstreet * IO can always make forward progress: 69036c9ea98SKent Overstreet */ 691cafe5635SKent Overstreet nr /= c->btree_pages; 692cafe5635SKent Overstreet nr = min_t(unsigned long, nr, mca_can_free(c)); 693cafe5635SKent Overstreet 694cafe5635SKent Overstreet i = 0; 695ca71df31STang Junhui btree_cache_used = c->btree_cache_used; 696cafe5635SKent Overstreet list_for_each_entry_safe(b, t, &c->btree_cache_freeable, list) { 697ca71df31STang Junhui if (nr <= 0) 698ca71df31STang Junhui goto out; 699cafe5635SKent Overstreet 700cafe5635SKent Overstreet if (++i > 3 && 701e8e1d468SKent Overstreet !mca_reap(b, 0, false)) { 702cafe5635SKent Overstreet mca_data_free(b); 703cafe5635SKent Overstreet rw_unlock(true, b); 7047dc19d5aSDave Chinner freed++; 705cafe5635SKent Overstreet } 706ca71df31STang Junhui nr--; 707cafe5635SKent Overstreet } 708cafe5635SKent Overstreet 709ca71df31STang Junhui for (; (nr--) && i < btree_cache_used; i++) { 710cafe5635SKent Overstreet if (list_empty(&c->btree_cache)) 711cafe5635SKent Overstreet goto out; 712cafe5635SKent Overstreet 713cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 714cafe5635SKent Overstreet list_rotate_left(&c->btree_cache); 715cafe5635SKent Overstreet 716cafe5635SKent Overstreet if (!b->accessed && 717e8e1d468SKent Overstreet !mca_reap(b, 0, false)) { 718cafe5635SKent Overstreet mca_bucket_free(b); 719cafe5635SKent Overstreet mca_data_free(b); 720cafe5635SKent Overstreet rw_unlock(true, b); 7217dc19d5aSDave Chinner freed++; 722cafe5635SKent Overstreet } else 723cafe5635SKent Overstreet b->accessed = 0; 724cafe5635SKent Overstreet } 725cafe5635SKent Overstreet out: 726cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 727f3641c3aSTang Junhui return freed * c->btree_pages; 7287dc19d5aSDave Chinner } 7297dc19d5aSDave Chinner 7307dc19d5aSDave Chinner static unsigned long bch_mca_count(struct shrinker *shrink, 7317dc19d5aSDave Chinner struct shrink_control *sc) 7327dc19d5aSDave Chinner { 7337dc19d5aSDave Chinner struct cache_set *c = container_of(shrink, struct cache_set, shrink); 7347dc19d5aSDave Chinner 7357dc19d5aSDave Chinner if (c->shrinker_disabled) 7367dc19d5aSDave Chinner return 0; 7377dc19d5aSDave Chinner 7380a63b66dSKent Overstreet if (c->btree_cache_alloc_lock) 7397dc19d5aSDave Chinner return 0; 7407dc19d5aSDave Chinner 7417dc19d5aSDave Chinner return mca_can_free(c) * c->btree_pages; 742cafe5635SKent Overstreet } 743cafe5635SKent Overstreet 744cafe5635SKent Overstreet void bch_btree_cache_free(struct cache_set *c) 745cafe5635SKent Overstreet { 746cafe5635SKent Overstreet struct btree *b; 747cafe5635SKent Overstreet struct closure cl; 748cafe5635SKent Overstreet closure_init_stack(&cl); 749cafe5635SKent Overstreet 750cafe5635SKent Overstreet if (c->shrink.list.next) 751cafe5635SKent Overstreet unregister_shrinker(&c->shrink); 752cafe5635SKent Overstreet 753cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 754cafe5635SKent Overstreet 755cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 756cafe5635SKent Overstreet if (c->verify_data) 757cafe5635SKent Overstreet list_move(&c->verify_data->list, &c->btree_cache); 75878b77bf8SKent Overstreet 75978b77bf8SKent Overstreet free_pages((unsigned long) c->verify_ondisk, ilog2(bucket_pages(c))); 760cafe5635SKent Overstreet #endif 761cafe5635SKent Overstreet 762cafe5635SKent Overstreet list_splice(&c->btree_cache_freeable, 763cafe5635SKent Overstreet &c->btree_cache); 764cafe5635SKent Overstreet 765cafe5635SKent Overstreet while (!list_empty(&c->btree_cache)) { 766cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 767cafe5635SKent Overstreet 768cafe5635SKent Overstreet if (btree_node_dirty(b)) 769cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 770cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 771cafe5635SKent Overstreet 772cafe5635SKent Overstreet mca_data_free(b); 773cafe5635SKent Overstreet } 774cafe5635SKent Overstreet 775cafe5635SKent Overstreet while (!list_empty(&c->btree_cache_freed)) { 776cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache_freed, 777cafe5635SKent Overstreet struct btree, list); 778cafe5635SKent Overstreet list_del(&b->list); 779cafe5635SKent Overstreet cancel_delayed_work_sync(&b->work); 780cafe5635SKent Overstreet kfree(b); 781cafe5635SKent Overstreet } 782cafe5635SKent Overstreet 783cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 784cafe5635SKent Overstreet } 785cafe5635SKent Overstreet 786cafe5635SKent Overstreet int bch_btree_cache_alloc(struct cache_set *c) 787cafe5635SKent Overstreet { 788cafe5635SKent Overstreet unsigned i; 789cafe5635SKent Overstreet 790cafe5635SKent Overstreet for (i = 0; i < mca_reserve(c); i++) 79172a44517SKent Overstreet if (!mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL)) 79272a44517SKent Overstreet return -ENOMEM; 793cafe5635SKent Overstreet 794cafe5635SKent Overstreet list_splice_init(&c->btree_cache, 795cafe5635SKent Overstreet &c->btree_cache_freeable); 796cafe5635SKent Overstreet 797cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 798cafe5635SKent Overstreet mutex_init(&c->verify_lock); 799cafe5635SKent Overstreet 80078b77bf8SKent Overstreet c->verify_ondisk = (void *) 80178b77bf8SKent Overstreet __get_free_pages(GFP_KERNEL, ilog2(bucket_pages(c))); 80278b77bf8SKent Overstreet 803cafe5635SKent Overstreet c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL); 804cafe5635SKent Overstreet 805cafe5635SKent Overstreet if (c->verify_data && 806a85e968eSKent Overstreet c->verify_data->keys.set->data) 807cafe5635SKent Overstreet list_del_init(&c->verify_data->list); 808cafe5635SKent Overstreet else 809cafe5635SKent Overstreet c->verify_data = NULL; 810cafe5635SKent Overstreet #endif 811cafe5635SKent Overstreet 8127dc19d5aSDave Chinner c->shrink.count_objects = bch_mca_count; 8137dc19d5aSDave Chinner c->shrink.scan_objects = bch_mca_scan; 814cafe5635SKent Overstreet c->shrink.seeks = 4; 815cafe5635SKent Overstreet c->shrink.batch = c->btree_pages * 2; 8166c4ca1e3SMichael Lyle 8176c4ca1e3SMichael Lyle if (register_shrinker(&c->shrink)) 8186c4ca1e3SMichael Lyle pr_warn("bcache: %s: could not register shrinker", 8196c4ca1e3SMichael Lyle __func__); 820cafe5635SKent Overstreet 821cafe5635SKent Overstreet return 0; 822cafe5635SKent Overstreet } 823cafe5635SKent Overstreet 824cafe5635SKent Overstreet /* Btree in memory cache - hash table */ 825cafe5635SKent Overstreet 826cafe5635SKent Overstreet static struct hlist_head *mca_hash(struct cache_set *c, struct bkey *k) 827cafe5635SKent Overstreet { 828cafe5635SKent Overstreet return &c->bucket_hash[hash_32(PTR_HASH(c, k), BUCKET_HASH_BITS)]; 829cafe5635SKent Overstreet } 830cafe5635SKent Overstreet 831cafe5635SKent Overstreet static struct btree *mca_find(struct cache_set *c, struct bkey *k) 832cafe5635SKent Overstreet { 833cafe5635SKent Overstreet struct btree *b; 834cafe5635SKent Overstreet 835cafe5635SKent Overstreet rcu_read_lock(); 836cafe5635SKent Overstreet hlist_for_each_entry_rcu(b, mca_hash(c, k), hash) 837cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) == PTR_HASH(c, k)) 838cafe5635SKent Overstreet goto out; 839cafe5635SKent Overstreet b = NULL; 840cafe5635SKent Overstreet out: 841cafe5635SKent Overstreet rcu_read_unlock(); 842cafe5635SKent Overstreet return b; 843cafe5635SKent Overstreet } 844cafe5635SKent Overstreet 8450a63b66dSKent Overstreet static int mca_cannibalize_lock(struct cache_set *c, struct btree_op *op) 8460a63b66dSKent Overstreet { 8470a63b66dSKent Overstreet struct task_struct *old; 8480a63b66dSKent Overstreet 8490a63b66dSKent Overstreet old = cmpxchg(&c->btree_cache_alloc_lock, NULL, current); 8500a63b66dSKent Overstreet if (old && old != current) { 8510a63b66dSKent Overstreet if (op) 8520a63b66dSKent Overstreet prepare_to_wait(&c->btree_cache_wait, &op->wait, 8530a63b66dSKent Overstreet TASK_UNINTERRUPTIBLE); 8540a63b66dSKent Overstreet return -EINTR; 8550a63b66dSKent Overstreet } 8560a63b66dSKent Overstreet 8570a63b66dSKent Overstreet return 0; 8580a63b66dSKent Overstreet } 8590a63b66dSKent Overstreet 8600a63b66dSKent Overstreet static struct btree *mca_cannibalize(struct cache_set *c, struct btree_op *op, 8610a63b66dSKent Overstreet struct bkey *k) 862cafe5635SKent Overstreet { 863e8e1d468SKent Overstreet struct btree *b; 864cafe5635SKent Overstreet 865c37511b8SKent Overstreet trace_bcache_btree_cache_cannibalize(c); 866c37511b8SKent Overstreet 8670a63b66dSKent Overstreet if (mca_cannibalize_lock(c, op)) 8680a63b66dSKent Overstreet return ERR_PTR(-EINTR); 869cafe5635SKent Overstreet 870e8e1d468SKent Overstreet list_for_each_entry_reverse(b, &c->btree_cache, list) 871e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), false)) 872e8e1d468SKent Overstreet return b; 873cafe5635SKent Overstreet 874e8e1d468SKent Overstreet list_for_each_entry_reverse(b, &c->btree_cache, list) 875e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), true)) 876e8e1d468SKent Overstreet return b; 877e8e1d468SKent Overstreet 8780a63b66dSKent Overstreet WARN(1, "btree cache cannibalize failed\n"); 879e8e1d468SKent Overstreet return ERR_PTR(-ENOMEM); 880cafe5635SKent Overstreet } 881cafe5635SKent Overstreet 882cafe5635SKent Overstreet /* 883cafe5635SKent Overstreet * We can only have one thread cannibalizing other cached btree nodes at a time, 884cafe5635SKent Overstreet * or we'll deadlock. We use an open coded mutex to ensure that, which a 885cafe5635SKent Overstreet * cannibalize_bucket() will take. This means every time we unlock the root of 886cafe5635SKent Overstreet * the btree, we need to release this lock if we have it held. 887cafe5635SKent Overstreet */ 888df8e8970SKent Overstreet static void bch_cannibalize_unlock(struct cache_set *c) 889cafe5635SKent Overstreet { 8900a63b66dSKent Overstreet if (c->btree_cache_alloc_lock == current) { 8910a63b66dSKent Overstreet c->btree_cache_alloc_lock = NULL; 8920a63b66dSKent Overstreet wake_up(&c->btree_cache_wait); 893cafe5635SKent Overstreet } 894cafe5635SKent Overstreet } 895cafe5635SKent Overstreet 8960a63b66dSKent Overstreet static struct btree *mca_alloc(struct cache_set *c, struct btree_op *op, 8970a63b66dSKent Overstreet struct bkey *k, int level) 898cafe5635SKent Overstreet { 899cafe5635SKent Overstreet struct btree *b; 900cafe5635SKent Overstreet 901e8e1d468SKent Overstreet BUG_ON(current->bio_list); 902e8e1d468SKent Overstreet 903cafe5635SKent Overstreet lockdep_assert_held(&c->bucket_lock); 904cafe5635SKent Overstreet 905cafe5635SKent Overstreet if (mca_find(c, k)) 906cafe5635SKent Overstreet return NULL; 907cafe5635SKent Overstreet 908cafe5635SKent Overstreet /* btree_free() doesn't free memory; it sticks the node on the end of 909cafe5635SKent Overstreet * the list. Check if there's any freed nodes there: 910cafe5635SKent Overstreet */ 911cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freeable, list) 912e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), false)) 913cafe5635SKent Overstreet goto out; 914cafe5635SKent Overstreet 915cafe5635SKent Overstreet /* We never free struct btree itself, just the memory that holds the on 916cafe5635SKent Overstreet * disk node. Check the freed list before allocating a new one: 917cafe5635SKent Overstreet */ 918cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freed, list) 919e8e1d468SKent Overstreet if (!mca_reap(b, 0, false)) { 920cafe5635SKent Overstreet mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO); 921a85e968eSKent Overstreet if (!b->keys.set[0].data) 922cafe5635SKent Overstreet goto err; 923cafe5635SKent Overstreet else 924cafe5635SKent Overstreet goto out; 925cafe5635SKent Overstreet } 926cafe5635SKent Overstreet 927cafe5635SKent Overstreet b = mca_bucket_alloc(c, k, __GFP_NOWARN|GFP_NOIO); 928cafe5635SKent Overstreet if (!b) 929cafe5635SKent Overstreet goto err; 930cafe5635SKent Overstreet 931cafe5635SKent Overstreet BUG_ON(!down_write_trylock(&b->lock)); 932a85e968eSKent Overstreet if (!b->keys.set->data) 933cafe5635SKent Overstreet goto err; 934cafe5635SKent Overstreet out: 935cb7a583eSKent Overstreet BUG_ON(b->io_mutex.count != 1); 936cafe5635SKent Overstreet 937cafe5635SKent Overstreet bkey_copy(&b->key, k); 938cafe5635SKent Overstreet list_move(&b->list, &c->btree_cache); 939cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 940cafe5635SKent Overstreet hlist_add_head_rcu(&b->hash, mca_hash(c, k)); 941cafe5635SKent Overstreet 942cafe5635SKent Overstreet lock_set_subclass(&b->lock.dep_map, level + 1, _THIS_IP_); 943d6fd3b11SKent Overstreet b->parent = (void *) ~0UL; 944a85e968eSKent Overstreet b->flags = 0; 945a85e968eSKent Overstreet b->written = 0; 946a85e968eSKent Overstreet b->level = level; 947cafe5635SKent Overstreet 94865d45231SKent Overstreet if (!b->level) 949a85e968eSKent Overstreet bch_btree_keys_init(&b->keys, &bch_extent_keys_ops, 950a85e968eSKent Overstreet &b->c->expensive_debug_checks); 95165d45231SKent Overstreet else 952a85e968eSKent Overstreet bch_btree_keys_init(&b->keys, &bch_btree_keys_ops, 953a85e968eSKent Overstreet &b->c->expensive_debug_checks); 954cafe5635SKent Overstreet 955cafe5635SKent Overstreet return b; 956cafe5635SKent Overstreet err: 957cafe5635SKent Overstreet if (b) 958cafe5635SKent Overstreet rw_unlock(true, b); 959cafe5635SKent Overstreet 9600a63b66dSKent Overstreet b = mca_cannibalize(c, op, k); 961cafe5635SKent Overstreet if (!IS_ERR(b)) 962cafe5635SKent Overstreet goto out; 963cafe5635SKent Overstreet 964cafe5635SKent Overstreet return b; 965cafe5635SKent Overstreet } 966cafe5635SKent Overstreet 96747344e33SBart Van Assche /* 968cafe5635SKent Overstreet * bch_btree_node_get - find a btree node in the cache and lock it, reading it 969cafe5635SKent Overstreet * in from disk if necessary. 970cafe5635SKent Overstreet * 971b54d6934SKent Overstreet * If IO is necessary and running under generic_make_request, returns -EAGAIN. 972cafe5635SKent Overstreet * 973cafe5635SKent Overstreet * The btree node will have either a read or a write lock held, depending on 974cafe5635SKent Overstreet * level and op->lock. 975cafe5635SKent Overstreet */ 9760a63b66dSKent Overstreet struct btree *bch_btree_node_get(struct cache_set *c, struct btree_op *op, 9772452cc89SSlava Pestov struct bkey *k, int level, bool write, 9782452cc89SSlava Pestov struct btree *parent) 979cafe5635SKent Overstreet { 980cafe5635SKent Overstreet int i = 0; 981cafe5635SKent Overstreet struct btree *b; 982cafe5635SKent Overstreet 983cafe5635SKent Overstreet BUG_ON(level < 0); 984cafe5635SKent Overstreet retry: 985cafe5635SKent Overstreet b = mca_find(c, k); 986cafe5635SKent Overstreet 987cafe5635SKent Overstreet if (!b) { 98857943511SKent Overstreet if (current->bio_list) 98957943511SKent Overstreet return ERR_PTR(-EAGAIN); 99057943511SKent Overstreet 991cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 9920a63b66dSKent Overstreet b = mca_alloc(c, op, k, level); 993cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 994cafe5635SKent Overstreet 995cafe5635SKent Overstreet if (!b) 996cafe5635SKent Overstreet goto retry; 997cafe5635SKent Overstreet if (IS_ERR(b)) 998cafe5635SKent Overstreet return b; 999cafe5635SKent Overstreet 100057943511SKent Overstreet bch_btree_node_read(b); 1001cafe5635SKent Overstreet 1002cafe5635SKent Overstreet if (!write) 1003cafe5635SKent Overstreet downgrade_write(&b->lock); 1004cafe5635SKent Overstreet } else { 1005cafe5635SKent Overstreet rw_lock(write, b, level); 1006cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) != PTR_HASH(c, k)) { 1007cafe5635SKent Overstreet rw_unlock(write, b); 1008cafe5635SKent Overstreet goto retry; 1009cafe5635SKent Overstreet } 1010cafe5635SKent Overstreet BUG_ON(b->level != level); 1011cafe5635SKent Overstreet } 1012cafe5635SKent Overstreet 10132452cc89SSlava Pestov b->parent = parent; 1014cafe5635SKent Overstreet b->accessed = 1; 1015cafe5635SKent Overstreet 1016a85e968eSKent Overstreet for (; i <= b->keys.nsets && b->keys.set[i].size; i++) { 1017a85e968eSKent Overstreet prefetch(b->keys.set[i].tree); 1018a85e968eSKent Overstreet prefetch(b->keys.set[i].data); 1019cafe5635SKent Overstreet } 1020cafe5635SKent Overstreet 1021a85e968eSKent Overstreet for (; i <= b->keys.nsets; i++) 1022a85e968eSKent Overstreet prefetch(b->keys.set[i].data); 1023cafe5635SKent Overstreet 102457943511SKent Overstreet if (btree_node_io_error(b)) { 1025cafe5635SKent Overstreet rw_unlock(write, b); 102657943511SKent Overstreet return ERR_PTR(-EIO); 102757943511SKent Overstreet } 102857943511SKent Overstreet 1029cafe5635SKent Overstreet BUG_ON(!b->written); 1030cafe5635SKent Overstreet 1031cafe5635SKent Overstreet return b; 1032cafe5635SKent Overstreet } 1033cafe5635SKent Overstreet 10342452cc89SSlava Pestov static void btree_node_prefetch(struct btree *parent, struct bkey *k) 1035cafe5635SKent Overstreet { 1036cafe5635SKent Overstreet struct btree *b; 1037cafe5635SKent Overstreet 10382452cc89SSlava Pestov mutex_lock(&parent->c->bucket_lock); 10392452cc89SSlava Pestov b = mca_alloc(parent->c, NULL, k, parent->level - 1); 10402452cc89SSlava Pestov mutex_unlock(&parent->c->bucket_lock); 1041cafe5635SKent Overstreet 1042cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(b)) { 10432452cc89SSlava Pestov b->parent = parent; 104457943511SKent Overstreet bch_btree_node_read(b); 1045cafe5635SKent Overstreet rw_unlock(true, b); 1046cafe5635SKent Overstreet } 1047cafe5635SKent Overstreet } 1048cafe5635SKent Overstreet 1049cafe5635SKent Overstreet /* Btree alloc */ 1050cafe5635SKent Overstreet 1051e8e1d468SKent Overstreet static void btree_node_free(struct btree *b) 1052cafe5635SKent Overstreet { 1053c37511b8SKent Overstreet trace_bcache_btree_node_free(b); 1054c37511b8SKent Overstreet 1055cafe5635SKent Overstreet BUG_ON(b == b->c->root); 1056cafe5635SKent Overstreet 10572a285686SKent Overstreet mutex_lock(&b->write_lock); 10582a285686SKent Overstreet 1059cafe5635SKent Overstreet if (btree_node_dirty(b)) 1060cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 1061cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 1062cafe5635SKent Overstreet 10632a285686SKent Overstreet mutex_unlock(&b->write_lock); 10642a285686SKent Overstreet 1065cafe5635SKent Overstreet cancel_delayed_work(&b->work); 1066cafe5635SKent Overstreet 1067cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 1068cafe5635SKent Overstreet bch_bucket_free(b->c, &b->key); 1069cafe5635SKent Overstreet mca_bucket_free(b); 1070cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 1071cafe5635SKent Overstreet } 1072cafe5635SKent Overstreet 1073c5aa4a31SSlava Pestov struct btree *__bch_btree_node_alloc(struct cache_set *c, struct btree_op *op, 10742452cc89SSlava Pestov int level, bool wait, 10752452cc89SSlava Pestov struct btree *parent) 1076cafe5635SKent Overstreet { 1077cafe5635SKent Overstreet BKEY_PADDED(key) k; 1078cafe5635SKent Overstreet struct btree *b = ERR_PTR(-EAGAIN); 1079cafe5635SKent Overstreet 1080cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1081cafe5635SKent Overstreet retry: 1082c5aa4a31SSlava Pestov if (__bch_bucket_alloc_set(c, RESERVE_BTREE, &k.key, 1, wait)) 1083cafe5635SKent Overstreet goto err; 1084cafe5635SKent Overstreet 10853a3b6a4eSKent Overstreet bkey_put(c, &k.key); 1086cafe5635SKent Overstreet SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS); 1087cafe5635SKent Overstreet 10880a63b66dSKent Overstreet b = mca_alloc(c, op, &k.key, level); 1089cafe5635SKent Overstreet if (IS_ERR(b)) 1090cafe5635SKent Overstreet goto err_free; 1091cafe5635SKent Overstreet 1092cafe5635SKent Overstreet if (!b) { 1093b1a67b0fSKent Overstreet cache_bug(c, 1094b1a67b0fSKent Overstreet "Tried to allocate bucket that was in btree cache"); 1095cafe5635SKent Overstreet goto retry; 1096cafe5635SKent Overstreet } 1097cafe5635SKent Overstreet 1098cafe5635SKent Overstreet b->accessed = 1; 10992452cc89SSlava Pestov b->parent = parent; 1100a85e968eSKent Overstreet bch_bset_init_next(&b->keys, b->keys.set->data, bset_magic(&b->c->sb)); 1101cafe5635SKent Overstreet 1102cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1103c37511b8SKent Overstreet 1104c37511b8SKent Overstreet trace_bcache_btree_node_alloc(b); 1105cafe5635SKent Overstreet return b; 1106cafe5635SKent Overstreet err_free: 1107cafe5635SKent Overstreet bch_bucket_free(c, &k.key); 1108cafe5635SKent Overstreet err: 1109cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1110c37511b8SKent Overstreet 1111913dc33fSSlava Pestov trace_bcache_btree_node_alloc_fail(c); 1112cafe5635SKent Overstreet return b; 1113cafe5635SKent Overstreet } 1114cafe5635SKent Overstreet 1115c5aa4a31SSlava Pestov static struct btree *bch_btree_node_alloc(struct cache_set *c, 11162452cc89SSlava Pestov struct btree_op *op, int level, 11172452cc89SSlava Pestov struct btree *parent) 1118c5aa4a31SSlava Pestov { 11192452cc89SSlava Pestov return __bch_btree_node_alloc(c, op, level, op != NULL, parent); 1120c5aa4a31SSlava Pestov } 1121c5aa4a31SSlava Pestov 11220a63b66dSKent Overstreet static struct btree *btree_node_alloc_replacement(struct btree *b, 11230a63b66dSKent Overstreet struct btree_op *op) 1124cafe5635SKent Overstreet { 11252452cc89SSlava Pestov struct btree *n = bch_btree_node_alloc(b->c, op, b->level, b->parent); 112667539e85SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 11272a285686SKent Overstreet mutex_lock(&n->write_lock); 112889ebb4a2SKent Overstreet bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort); 112967539e85SKent Overstreet bkey_copy_key(&n->key, &b->key); 11302a285686SKent Overstreet mutex_unlock(&n->write_lock); 113167539e85SKent Overstreet } 1132cafe5635SKent Overstreet 1133cafe5635SKent Overstreet return n; 1134cafe5635SKent Overstreet } 1135cafe5635SKent Overstreet 11368835c123SKent Overstreet static void make_btree_freeing_key(struct btree *b, struct bkey *k) 11378835c123SKent Overstreet { 11388835c123SKent Overstreet unsigned i; 11398835c123SKent Overstreet 114005335cffSKent Overstreet mutex_lock(&b->c->bucket_lock); 114105335cffSKent Overstreet 114205335cffSKent Overstreet atomic_inc(&b->c->prio_blocked); 114305335cffSKent Overstreet 11448835c123SKent Overstreet bkey_copy(k, &b->key); 11458835c123SKent Overstreet bkey_copy_key(k, &ZERO_KEY); 11468835c123SKent Overstreet 114705335cffSKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 114805335cffSKent Overstreet SET_PTR_GEN(k, i, 114905335cffSKent Overstreet bch_inc_gen(PTR_CACHE(b->c, &b->key, i), 115005335cffSKent Overstreet PTR_BUCKET(b->c, &b->key, i))); 11518835c123SKent Overstreet 115205335cffSKent Overstreet mutex_unlock(&b->c->bucket_lock); 11538835c123SKent Overstreet } 11548835c123SKent Overstreet 115578365411SKent Overstreet static int btree_check_reserve(struct btree *b, struct btree_op *op) 115678365411SKent Overstreet { 115778365411SKent Overstreet struct cache_set *c = b->c; 115878365411SKent Overstreet struct cache *ca; 11590a63b66dSKent Overstreet unsigned i, reserve = (c->root->level - b->level) * 2 + 1; 116078365411SKent Overstreet 116178365411SKent Overstreet mutex_lock(&c->bucket_lock); 116278365411SKent Overstreet 116378365411SKent Overstreet for_each_cache(ca, c, i) 116478365411SKent Overstreet if (fifo_used(&ca->free[RESERVE_BTREE]) < reserve) { 116578365411SKent Overstreet if (op) 11660a63b66dSKent Overstreet prepare_to_wait(&c->btree_cache_wait, &op->wait, 116778365411SKent Overstreet TASK_UNINTERRUPTIBLE); 11680a63b66dSKent Overstreet mutex_unlock(&c->bucket_lock); 11690a63b66dSKent Overstreet return -EINTR; 117078365411SKent Overstreet } 117178365411SKent Overstreet 117278365411SKent Overstreet mutex_unlock(&c->bucket_lock); 11730a63b66dSKent Overstreet 11740a63b66dSKent Overstreet return mca_cannibalize_lock(b->c, op); 117578365411SKent Overstreet } 117678365411SKent Overstreet 1177cafe5635SKent Overstreet /* Garbage collection */ 1178cafe5635SKent Overstreet 1179487dded8SKent Overstreet static uint8_t __bch_btree_mark_key(struct cache_set *c, int level, 1180487dded8SKent Overstreet struct bkey *k) 1181cafe5635SKent Overstreet { 1182cafe5635SKent Overstreet uint8_t stale = 0; 1183cafe5635SKent Overstreet unsigned i; 1184cafe5635SKent Overstreet struct bucket *g; 1185cafe5635SKent Overstreet 1186cafe5635SKent Overstreet /* 1187cafe5635SKent Overstreet * ptr_invalid() can't return true for the keys that mark btree nodes as 1188cafe5635SKent Overstreet * freed, but since ptr_bad() returns true we'll never actually use them 1189cafe5635SKent Overstreet * for anything and thus we don't want mark their pointers here 1190cafe5635SKent Overstreet */ 1191cafe5635SKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1192cafe5635SKent Overstreet return stale; 1193cafe5635SKent Overstreet 1194cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) { 1195cafe5635SKent Overstreet if (!ptr_available(c, k, i)) 1196cafe5635SKent Overstreet continue; 1197cafe5635SKent Overstreet 1198cafe5635SKent Overstreet g = PTR_BUCKET(c, k, i); 1199cafe5635SKent Overstreet 12003a2fd9d5SKent Overstreet if (gen_after(g->last_gc, PTR_GEN(k, i))) 12013a2fd9d5SKent Overstreet g->last_gc = PTR_GEN(k, i); 1202cafe5635SKent Overstreet 1203cafe5635SKent Overstreet if (ptr_stale(c, k, i)) { 1204cafe5635SKent Overstreet stale = max(stale, ptr_stale(c, k, i)); 1205cafe5635SKent Overstreet continue; 1206cafe5635SKent Overstreet } 1207cafe5635SKent Overstreet 1208cafe5635SKent Overstreet cache_bug_on(GC_MARK(g) && 1209cafe5635SKent Overstreet (GC_MARK(g) == GC_MARK_METADATA) != (level != 0), 1210cafe5635SKent Overstreet c, "inconsistent ptrs: mark = %llu, level = %i", 1211cafe5635SKent Overstreet GC_MARK(g), level); 1212cafe5635SKent Overstreet 1213cafe5635SKent Overstreet if (level) 1214cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_METADATA); 1215cafe5635SKent Overstreet else if (KEY_DIRTY(k)) 1216cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_DIRTY); 12174fe6a816SKent Overstreet else if (!GC_MARK(g)) 12184fe6a816SKent Overstreet SET_GC_MARK(g, GC_MARK_RECLAIMABLE); 1219cafe5635SKent Overstreet 1220cafe5635SKent Overstreet /* guard against overflow */ 1221cafe5635SKent Overstreet SET_GC_SECTORS_USED(g, min_t(unsigned, 1222cafe5635SKent Overstreet GC_SECTORS_USED(g) + KEY_SIZE(k), 122394717447SDarrick J. Wong MAX_GC_SECTORS_USED)); 1224cafe5635SKent Overstreet 1225cafe5635SKent Overstreet BUG_ON(!GC_SECTORS_USED(g)); 1226cafe5635SKent Overstreet } 1227cafe5635SKent Overstreet 1228cafe5635SKent Overstreet return stale; 1229cafe5635SKent Overstreet } 1230cafe5635SKent Overstreet 1231cafe5635SKent Overstreet #define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k) 1232cafe5635SKent Overstreet 1233487dded8SKent Overstreet void bch_initial_mark_key(struct cache_set *c, int level, struct bkey *k) 1234487dded8SKent Overstreet { 1235487dded8SKent Overstreet unsigned i; 1236487dded8SKent Overstreet 1237487dded8SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 1238487dded8SKent Overstreet if (ptr_available(c, k, i) && 1239487dded8SKent Overstreet !ptr_stale(c, k, i)) { 1240487dded8SKent Overstreet struct bucket *b = PTR_BUCKET(c, k, i); 1241487dded8SKent Overstreet 1242487dded8SKent Overstreet b->gen = PTR_GEN(k, i); 1243487dded8SKent Overstreet 1244487dded8SKent Overstreet if (level && bkey_cmp(k, &ZERO_KEY)) 1245487dded8SKent Overstreet b->prio = BTREE_PRIO; 1246487dded8SKent Overstreet else if (!level && b->prio == BTREE_PRIO) 1247487dded8SKent Overstreet b->prio = INITIAL_PRIO; 1248487dded8SKent Overstreet } 1249487dded8SKent Overstreet 1250487dded8SKent Overstreet __bch_btree_mark_key(c, level, k); 1251487dded8SKent Overstreet } 1252487dded8SKent Overstreet 1253d44c2f9eSTang Junhui void bch_update_bucket_in_use(struct cache_set *c, struct gc_stat *stats) 1254d44c2f9eSTang Junhui { 1255d44c2f9eSTang Junhui stats->in_use = (c->nbuckets - c->avail_nbuckets) * 100 / c->nbuckets; 1256d44c2f9eSTang Junhui } 1257d44c2f9eSTang Junhui 1258a1f0358bSKent Overstreet static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc) 1259cafe5635SKent Overstreet { 1260cafe5635SKent Overstreet uint8_t stale = 0; 1261a1f0358bSKent Overstreet unsigned keys = 0, good_keys = 0; 1262cafe5635SKent Overstreet struct bkey *k; 1263cafe5635SKent Overstreet struct btree_iter iter; 1264cafe5635SKent Overstreet struct bset_tree *t; 1265cafe5635SKent Overstreet 1266cafe5635SKent Overstreet gc->nodes++; 1267cafe5635SKent Overstreet 1268c052dd9aSKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) { 1269cafe5635SKent Overstreet stale = max(stale, btree_mark_key(b, k)); 1270a1f0358bSKent Overstreet keys++; 1271cafe5635SKent Overstreet 1272a85e968eSKent Overstreet if (bch_ptr_bad(&b->keys, k)) 1273cafe5635SKent Overstreet continue; 1274cafe5635SKent Overstreet 1275cafe5635SKent Overstreet gc->key_bytes += bkey_u64s(k); 1276cafe5635SKent Overstreet gc->nkeys++; 1277a1f0358bSKent Overstreet good_keys++; 1278cafe5635SKent Overstreet 1279cafe5635SKent Overstreet gc->data += KEY_SIZE(k); 1280cafe5635SKent Overstreet } 1281cafe5635SKent Overstreet 1282a85e968eSKent Overstreet for (t = b->keys.set; t <= &b->keys.set[b->keys.nsets]; t++) 1283cafe5635SKent Overstreet btree_bug_on(t->size && 1284a85e968eSKent Overstreet bset_written(&b->keys, t) && 1285cafe5635SKent Overstreet bkey_cmp(&b->key, &t->end) < 0, 1286cafe5635SKent Overstreet b, "found short btree key in gc"); 1287cafe5635SKent Overstreet 1288a1f0358bSKent Overstreet if (b->c->gc_always_rewrite) 1289a1f0358bSKent Overstreet return true; 1290a1f0358bSKent Overstreet 1291a1f0358bSKent Overstreet if (stale > 10) 1292a1f0358bSKent Overstreet return true; 1293a1f0358bSKent Overstreet 1294a1f0358bSKent Overstreet if ((keys - good_keys) * 2 > keys) 1295a1f0358bSKent Overstreet return true; 1296a1f0358bSKent Overstreet 1297a1f0358bSKent Overstreet return false; 1298cafe5635SKent Overstreet } 1299cafe5635SKent Overstreet 1300a1f0358bSKent Overstreet #define GC_MERGE_NODES 4U 1301cafe5635SKent Overstreet 1302cafe5635SKent Overstreet struct gc_merge_info { 1303cafe5635SKent Overstreet struct btree *b; 1304cafe5635SKent Overstreet unsigned keys; 1305cafe5635SKent Overstreet }; 1306cafe5635SKent Overstreet 1307a1f0358bSKent Overstreet static int bch_btree_insert_node(struct btree *, struct btree_op *, 1308a1f0358bSKent Overstreet struct keylist *, atomic_t *, struct bkey *); 1309a1f0358bSKent Overstreet 1310a1f0358bSKent Overstreet static int btree_gc_coalesce(struct btree *b, struct btree_op *op, 13110a63b66dSKent Overstreet struct gc_stat *gc, struct gc_merge_info *r) 1312cafe5635SKent Overstreet { 1313a1f0358bSKent Overstreet unsigned i, nodes = 0, keys = 0, blocks; 1314a1f0358bSKent Overstreet struct btree *new_nodes[GC_MERGE_NODES]; 13150a63b66dSKent Overstreet struct keylist keylist; 1316b54d6934SKent Overstreet struct closure cl; 1317a1f0358bSKent Overstreet struct bkey *k; 1318b54d6934SKent Overstreet 13190a63b66dSKent Overstreet bch_keylist_init(&keylist); 13200a63b66dSKent Overstreet 13210a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 13220a63b66dSKent Overstreet return 0; 13230a63b66dSKent Overstreet 1324a1f0358bSKent Overstreet memset(new_nodes, 0, sizeof(new_nodes)); 1325b54d6934SKent Overstreet closure_init_stack(&cl); 1326cafe5635SKent Overstreet 1327a1f0358bSKent Overstreet while (nodes < GC_MERGE_NODES && !IS_ERR_OR_NULL(r[nodes].b)) 1328cafe5635SKent Overstreet keys += r[nodes++].keys; 1329cafe5635SKent Overstreet 1330cafe5635SKent Overstreet blocks = btree_default_blocks(b->c) * 2 / 3; 1331cafe5635SKent Overstreet 1332cafe5635SKent Overstreet if (nodes < 2 || 1333a85e968eSKent Overstreet __set_blocks(b->keys.set[0].data, keys, 1334ee811287SKent Overstreet block_bytes(b->c)) > blocks * (nodes - 1)) 1335a1f0358bSKent Overstreet return 0; 1336cafe5635SKent Overstreet 1337a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 13380a63b66dSKent Overstreet new_nodes[i] = btree_node_alloc_replacement(r[i].b, NULL); 1339a1f0358bSKent Overstreet if (IS_ERR_OR_NULL(new_nodes[i])) 1340a1f0358bSKent Overstreet goto out_nocoalesce; 1341cafe5635SKent Overstreet } 1342cafe5635SKent Overstreet 13430a63b66dSKent Overstreet /* 13440a63b66dSKent Overstreet * We have to check the reserve here, after we've allocated our new 13450a63b66dSKent Overstreet * nodes, to make sure the insert below will succeed - we also check 13460a63b66dSKent Overstreet * before as an optimization to potentially avoid a bunch of expensive 13470a63b66dSKent Overstreet * allocs/sorts 13480a63b66dSKent Overstreet */ 13490a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 13500a63b66dSKent Overstreet goto out_nocoalesce; 13510a63b66dSKent Overstreet 13522a285686SKent Overstreet for (i = 0; i < nodes; i++) 13532a285686SKent Overstreet mutex_lock(&new_nodes[i]->write_lock); 13542a285686SKent Overstreet 1355cafe5635SKent Overstreet for (i = nodes - 1; i > 0; --i) { 1356ee811287SKent Overstreet struct bset *n1 = btree_bset_first(new_nodes[i]); 1357ee811287SKent Overstreet struct bset *n2 = btree_bset_first(new_nodes[i - 1]); 1358cafe5635SKent Overstreet struct bkey *k, *last = NULL; 1359cafe5635SKent Overstreet 1360cafe5635SKent Overstreet keys = 0; 1361cafe5635SKent Overstreet 1362a1f0358bSKent Overstreet if (i > 1) { 1363cafe5635SKent Overstreet for (k = n2->start; 1364fafff81cSKent Overstreet k < bset_bkey_last(n2); 1365cafe5635SKent Overstreet k = bkey_next(k)) { 1366cafe5635SKent Overstreet if (__set_blocks(n1, n1->keys + keys + 1367ee811287SKent Overstreet bkey_u64s(k), 1368ee811287SKent Overstreet block_bytes(b->c)) > blocks) 1369cafe5635SKent Overstreet break; 1370cafe5635SKent Overstreet 1371cafe5635SKent Overstreet last = k; 1372cafe5635SKent Overstreet keys += bkey_u64s(k); 1373cafe5635SKent Overstreet } 1374a1f0358bSKent Overstreet } else { 1375a1f0358bSKent Overstreet /* 1376a1f0358bSKent Overstreet * Last node we're not getting rid of - we're getting 1377a1f0358bSKent Overstreet * rid of the node at r[0]. Have to try and fit all of 1378a1f0358bSKent Overstreet * the remaining keys into this node; we can't ensure 1379a1f0358bSKent Overstreet * they will always fit due to rounding and variable 1380a1f0358bSKent Overstreet * length keys (shouldn't be possible in practice, 1381a1f0358bSKent Overstreet * though) 1382a1f0358bSKent Overstreet */ 1383a1f0358bSKent Overstreet if (__set_blocks(n1, n1->keys + n2->keys, 1384ee811287SKent Overstreet block_bytes(b->c)) > 1385ee811287SKent Overstreet btree_blocks(new_nodes[i])) 1386a1f0358bSKent Overstreet goto out_nocoalesce; 1387a1f0358bSKent Overstreet 1388a1f0358bSKent Overstreet keys = n2->keys; 1389a1f0358bSKent Overstreet /* Take the key of the node we're getting rid of */ 1390a1f0358bSKent Overstreet last = &r->b->key; 1391a1f0358bSKent Overstreet } 1392cafe5635SKent Overstreet 1393ee811287SKent Overstreet BUG_ON(__set_blocks(n1, n1->keys + keys, block_bytes(b->c)) > 1394ee811287SKent Overstreet btree_blocks(new_nodes[i])); 1395cafe5635SKent Overstreet 1396a1f0358bSKent Overstreet if (last) 1397a1f0358bSKent Overstreet bkey_copy_key(&new_nodes[i]->key, last); 1398cafe5635SKent Overstreet 1399fafff81cSKent Overstreet memcpy(bset_bkey_last(n1), 1400cafe5635SKent Overstreet n2->start, 1401fafff81cSKent Overstreet (void *) bset_bkey_idx(n2, keys) - (void *) n2->start); 1402cafe5635SKent Overstreet 1403cafe5635SKent Overstreet n1->keys += keys; 1404a1f0358bSKent Overstreet r[i].keys = n1->keys; 1405cafe5635SKent Overstreet 1406cafe5635SKent Overstreet memmove(n2->start, 1407fafff81cSKent Overstreet bset_bkey_idx(n2, keys), 1408fafff81cSKent Overstreet (void *) bset_bkey_last(n2) - 1409fafff81cSKent Overstreet (void *) bset_bkey_idx(n2, keys)); 1410cafe5635SKent Overstreet 1411cafe5635SKent Overstreet n2->keys -= keys; 1412cafe5635SKent Overstreet 14130a63b66dSKent Overstreet if (__bch_keylist_realloc(&keylist, 1414085d2a3dSKent Overstreet bkey_u64s(&new_nodes[i]->key))) 1415a1f0358bSKent Overstreet goto out_nocoalesce; 1416a1f0358bSKent Overstreet 1417a1f0358bSKent Overstreet bch_btree_node_write(new_nodes[i], &cl); 14180a63b66dSKent Overstreet bch_keylist_add(&keylist, &new_nodes[i]->key); 1419cafe5635SKent Overstreet } 1420cafe5635SKent Overstreet 14212a285686SKent Overstreet for (i = 0; i < nodes; i++) 14222a285686SKent Overstreet mutex_unlock(&new_nodes[i]->write_lock); 14232a285686SKent Overstreet 142405335cffSKent Overstreet closure_sync(&cl); 142505335cffSKent Overstreet 142605335cffSKent Overstreet /* We emptied out this node */ 142705335cffSKent Overstreet BUG_ON(btree_bset_first(new_nodes[0])->keys); 142805335cffSKent Overstreet btree_node_free(new_nodes[0]); 142905335cffSKent Overstreet rw_unlock(true, new_nodes[0]); 1430400ffaa2SSlava Pestov new_nodes[0] = NULL; 143105335cffSKent Overstreet 1432a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 14330a63b66dSKent Overstreet if (__bch_keylist_realloc(&keylist, bkey_u64s(&r[i].b->key))) 1434a1f0358bSKent Overstreet goto out_nocoalesce; 1435a1f0358bSKent Overstreet 14360a63b66dSKent Overstreet make_btree_freeing_key(r[i].b, keylist.top); 14370a63b66dSKent Overstreet bch_keylist_push(&keylist); 1438a1f0358bSKent Overstreet } 1439a1f0358bSKent Overstreet 14400a63b66dSKent Overstreet bch_btree_insert_node(b, op, &keylist, NULL, NULL); 14410a63b66dSKent Overstreet BUG_ON(!bch_keylist_empty(&keylist)); 1442a1f0358bSKent Overstreet 1443a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 1444a1f0358bSKent Overstreet btree_node_free(r[i].b); 1445a1f0358bSKent Overstreet rw_unlock(true, r[i].b); 1446a1f0358bSKent Overstreet 1447a1f0358bSKent Overstreet r[i].b = new_nodes[i]; 1448a1f0358bSKent Overstreet } 1449a1f0358bSKent Overstreet 1450a1f0358bSKent Overstreet memmove(r, r + 1, sizeof(r[0]) * (nodes - 1)); 1451a1f0358bSKent Overstreet r[nodes - 1].b = ERR_PTR(-EINTR); 1452cafe5635SKent Overstreet 1453c37511b8SKent Overstreet trace_bcache_btree_gc_coalesce(nodes); 1454cafe5635SKent Overstreet gc->nodes--; 1455cafe5635SKent Overstreet 14560a63b66dSKent Overstreet bch_keylist_free(&keylist); 14570a63b66dSKent Overstreet 1458a1f0358bSKent Overstreet /* Invalidated our iterator */ 1459a1f0358bSKent Overstreet return -EINTR; 1460a1f0358bSKent Overstreet 1461a1f0358bSKent Overstreet out_nocoalesce: 1462a1f0358bSKent Overstreet closure_sync(&cl); 14630a63b66dSKent Overstreet bch_keylist_free(&keylist); 1464a1f0358bSKent Overstreet 14650a63b66dSKent Overstreet while ((k = bch_keylist_pop(&keylist))) 1466a1f0358bSKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1467a1f0358bSKent Overstreet atomic_dec(&b->c->prio_blocked); 1468a1f0358bSKent Overstreet 1469a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) 1470a1f0358bSKent Overstreet if (!IS_ERR_OR_NULL(new_nodes[i])) { 1471a1f0358bSKent Overstreet btree_node_free(new_nodes[i]); 1472a1f0358bSKent Overstreet rw_unlock(true, new_nodes[i]); 1473a1f0358bSKent Overstreet } 1474a1f0358bSKent Overstreet return 0; 1475a1f0358bSKent Overstreet } 1476a1f0358bSKent Overstreet 14770a63b66dSKent Overstreet static int btree_gc_rewrite_node(struct btree *b, struct btree_op *op, 14780a63b66dSKent Overstreet struct btree *replace) 14790a63b66dSKent Overstreet { 14800a63b66dSKent Overstreet struct keylist keys; 14810a63b66dSKent Overstreet struct btree *n; 14820a63b66dSKent Overstreet 14830a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 14840a63b66dSKent Overstreet return 0; 14850a63b66dSKent Overstreet 14860a63b66dSKent Overstreet n = btree_node_alloc_replacement(replace, NULL); 14870a63b66dSKent Overstreet 14880a63b66dSKent Overstreet /* recheck reserve after allocating replacement node */ 14890a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) { 14900a63b66dSKent Overstreet btree_node_free(n); 14910a63b66dSKent Overstreet rw_unlock(true, n); 14920a63b66dSKent Overstreet return 0; 14930a63b66dSKent Overstreet } 14940a63b66dSKent Overstreet 14950a63b66dSKent Overstreet bch_btree_node_write_sync(n); 14960a63b66dSKent Overstreet 14970a63b66dSKent Overstreet bch_keylist_init(&keys); 14980a63b66dSKent Overstreet bch_keylist_add(&keys, &n->key); 14990a63b66dSKent Overstreet 15000a63b66dSKent Overstreet make_btree_freeing_key(replace, keys.top); 15010a63b66dSKent Overstreet bch_keylist_push(&keys); 15020a63b66dSKent Overstreet 15030a63b66dSKent Overstreet bch_btree_insert_node(b, op, &keys, NULL, NULL); 15040a63b66dSKent Overstreet BUG_ON(!bch_keylist_empty(&keys)); 15050a63b66dSKent Overstreet 15060a63b66dSKent Overstreet btree_node_free(replace); 15070a63b66dSKent Overstreet rw_unlock(true, n); 15080a63b66dSKent Overstreet 15090a63b66dSKent Overstreet /* Invalidated our iterator */ 15100a63b66dSKent Overstreet return -EINTR; 15110a63b66dSKent Overstreet } 15120a63b66dSKent Overstreet 1513a1f0358bSKent Overstreet static unsigned btree_gc_count_keys(struct btree *b) 1514a1f0358bSKent Overstreet { 1515a1f0358bSKent Overstreet struct bkey *k; 1516a1f0358bSKent Overstreet struct btree_iter iter; 1517a1f0358bSKent Overstreet unsigned ret = 0; 1518a1f0358bSKent Overstreet 1519c052dd9aSKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad) 1520a1f0358bSKent Overstreet ret += bkey_u64s(k); 1521a1f0358bSKent Overstreet 1522a1f0358bSKent Overstreet return ret; 1523cafe5635SKent Overstreet } 1524cafe5635SKent Overstreet 1525cafe5635SKent Overstreet static int btree_gc_recurse(struct btree *b, struct btree_op *op, 1526cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1527cafe5635SKent Overstreet { 1528a1f0358bSKent Overstreet int ret = 0; 1529a1f0358bSKent Overstreet bool should_rewrite; 1530a1f0358bSKent Overstreet struct bkey *k; 1531a1f0358bSKent Overstreet struct btree_iter iter; 1532cafe5635SKent Overstreet struct gc_merge_info r[GC_MERGE_NODES]; 15332a285686SKent Overstreet struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1; 1534cafe5635SKent Overstreet 1535c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done); 1536cafe5635SKent Overstreet 15372a285686SKent Overstreet for (i = r; i < r + ARRAY_SIZE(r); i++) 15382a285686SKent Overstreet i->b = ERR_PTR(-EINTR); 1539cafe5635SKent Overstreet 1540a1f0358bSKent Overstreet while (1) { 1541a85e968eSKent Overstreet k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad); 1542a1f0358bSKent Overstreet if (k) { 15430a63b66dSKent Overstreet r->b = bch_btree_node_get(b->c, op, k, b->level - 1, 15442452cc89SSlava Pestov true, b); 1545cafe5635SKent Overstreet if (IS_ERR(r->b)) { 1546cafe5635SKent Overstreet ret = PTR_ERR(r->b); 1547cafe5635SKent Overstreet break; 1548cafe5635SKent Overstreet } 1549cafe5635SKent Overstreet 1550a1f0358bSKent Overstreet r->keys = btree_gc_count_keys(r->b); 1551cafe5635SKent Overstreet 15520a63b66dSKent Overstreet ret = btree_gc_coalesce(b, op, gc, r); 1553a1f0358bSKent Overstreet if (ret) 1554cafe5635SKent Overstreet break; 1555cafe5635SKent Overstreet } 1556cafe5635SKent Overstreet 1557a1f0358bSKent Overstreet if (!last->b) 1558a1f0358bSKent Overstreet break; 1559cafe5635SKent Overstreet 1560a1f0358bSKent Overstreet if (!IS_ERR(last->b)) { 1561a1f0358bSKent Overstreet should_rewrite = btree_gc_mark_node(last->b, gc); 15620a63b66dSKent Overstreet if (should_rewrite) { 15630a63b66dSKent Overstreet ret = btree_gc_rewrite_node(b, op, last->b); 15640a63b66dSKent Overstreet if (ret) 1565a1f0358bSKent Overstreet break; 1566a1f0358bSKent Overstreet } 1567a1f0358bSKent Overstreet 1568a1f0358bSKent Overstreet if (last->b->level) { 1569a1f0358bSKent Overstreet ret = btree_gc_recurse(last->b, op, writes, gc); 1570a1f0358bSKent Overstreet if (ret) 1571a1f0358bSKent Overstreet break; 1572a1f0358bSKent Overstreet } 1573a1f0358bSKent Overstreet 1574a1f0358bSKent Overstreet bkey_copy_key(&b->c->gc_done, &last->b->key); 1575a1f0358bSKent Overstreet 1576a1f0358bSKent Overstreet /* 1577a1f0358bSKent Overstreet * Must flush leaf nodes before gc ends, since replace 1578a1f0358bSKent Overstreet * operations aren't journalled 1579cafe5635SKent Overstreet */ 15802a285686SKent Overstreet mutex_lock(&last->b->write_lock); 1581a1f0358bSKent Overstreet if (btree_node_dirty(last->b)) 1582a1f0358bSKent Overstreet bch_btree_node_write(last->b, writes); 15832a285686SKent Overstreet mutex_unlock(&last->b->write_lock); 1584a1f0358bSKent Overstreet rw_unlock(true, last->b); 1585a1f0358bSKent Overstreet } 1586a1f0358bSKent Overstreet 1587a1f0358bSKent Overstreet memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1)); 1588a1f0358bSKent Overstreet r->b = NULL; 1589a1f0358bSKent Overstreet 1590*5c25c4fcSTang Junhui if (atomic_read(&b->c->search_inflight) && 1591*5c25c4fcSTang Junhui gc->nodes >= gc->nodes_pre + MIN_GC_NODES) { 1592*5c25c4fcSTang Junhui gc->nodes_pre = gc->nodes; 1593*5c25c4fcSTang Junhui ret = -EAGAIN; 1594*5c25c4fcSTang Junhui break; 1595*5c25c4fcSTang Junhui } 1596*5c25c4fcSTang Junhui 1597cafe5635SKent Overstreet if (need_resched()) { 1598cafe5635SKent Overstreet ret = -EAGAIN; 1599cafe5635SKent Overstreet break; 1600cafe5635SKent Overstreet } 1601cafe5635SKent Overstreet } 1602cafe5635SKent Overstreet 16032a285686SKent Overstreet for (i = r; i < r + ARRAY_SIZE(r); i++) 16042a285686SKent Overstreet if (!IS_ERR_OR_NULL(i->b)) { 16052a285686SKent Overstreet mutex_lock(&i->b->write_lock); 16062a285686SKent Overstreet if (btree_node_dirty(i->b)) 16072a285686SKent Overstreet bch_btree_node_write(i->b, writes); 16082a285686SKent Overstreet mutex_unlock(&i->b->write_lock); 16092a285686SKent Overstreet rw_unlock(true, i->b); 1610a1f0358bSKent Overstreet } 1611cafe5635SKent Overstreet 1612cafe5635SKent Overstreet return ret; 1613cafe5635SKent Overstreet } 1614cafe5635SKent Overstreet 1615cafe5635SKent Overstreet static int bch_btree_gc_root(struct btree *b, struct btree_op *op, 1616cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1617cafe5635SKent Overstreet { 1618cafe5635SKent Overstreet struct btree *n = NULL; 1619a1f0358bSKent Overstreet int ret = 0; 1620a1f0358bSKent Overstreet bool should_rewrite; 1621cafe5635SKent Overstreet 1622a1f0358bSKent Overstreet should_rewrite = btree_gc_mark_node(b, gc); 1623a1f0358bSKent Overstreet if (should_rewrite) { 16240a63b66dSKent Overstreet n = btree_node_alloc_replacement(b, NULL); 1625cafe5635SKent Overstreet 1626cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 1627a1f0358bSKent Overstreet bch_btree_node_write_sync(n); 16282a285686SKent Overstreet 1629a1f0358bSKent Overstreet bch_btree_set_root(n); 1630a1f0358bSKent Overstreet btree_node_free(b); 1631a1f0358bSKent Overstreet rw_unlock(true, n); 1632a1f0358bSKent Overstreet 1633a1f0358bSKent Overstreet return -EINTR; 1634cafe5635SKent Overstreet } 1635a1f0358bSKent Overstreet } 1636a1f0358bSKent Overstreet 1637487dded8SKent Overstreet __bch_btree_mark_key(b->c, b->level + 1, &b->key); 1638487dded8SKent Overstreet 1639a1f0358bSKent Overstreet if (b->level) { 1640a1f0358bSKent Overstreet ret = btree_gc_recurse(b, op, writes, gc); 1641a1f0358bSKent Overstreet if (ret) 1642a1f0358bSKent Overstreet return ret; 1643a1f0358bSKent Overstreet } 1644a1f0358bSKent Overstreet 1645a1f0358bSKent Overstreet bkey_copy_key(&b->c->gc_done, &b->key); 1646cafe5635SKent Overstreet 1647cafe5635SKent Overstreet return ret; 1648cafe5635SKent Overstreet } 1649cafe5635SKent Overstreet 1650cafe5635SKent Overstreet static void btree_gc_start(struct cache_set *c) 1651cafe5635SKent Overstreet { 1652cafe5635SKent Overstreet struct cache *ca; 1653cafe5635SKent Overstreet struct bucket *b; 1654cafe5635SKent Overstreet unsigned i; 1655cafe5635SKent Overstreet 1656cafe5635SKent Overstreet if (!c->gc_mark_valid) 1657cafe5635SKent Overstreet return; 1658cafe5635SKent Overstreet 1659cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1660cafe5635SKent Overstreet 1661cafe5635SKent Overstreet c->gc_mark_valid = 0; 1662cafe5635SKent Overstreet c->gc_done = ZERO_KEY; 1663cafe5635SKent Overstreet 1664cafe5635SKent Overstreet for_each_cache(ca, c, i) 1665cafe5635SKent Overstreet for_each_bucket(b, ca) { 16663a2fd9d5SKent Overstreet b->last_gc = b->gen; 166729ebf465SKent Overstreet if (!atomic_read(&b->pin)) { 16684fe6a816SKent Overstreet SET_GC_MARK(b, 0); 166929ebf465SKent Overstreet SET_GC_SECTORS_USED(b, 0); 167029ebf465SKent Overstreet } 1671cafe5635SKent Overstreet } 1672cafe5635SKent Overstreet 1673cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1674cafe5635SKent Overstreet } 1675cafe5635SKent Overstreet 1676d44c2f9eSTang Junhui static void bch_btree_gc_finish(struct cache_set *c) 1677cafe5635SKent Overstreet { 1678cafe5635SKent Overstreet struct bucket *b; 1679cafe5635SKent Overstreet struct cache *ca; 1680cafe5635SKent Overstreet unsigned i; 1681cafe5635SKent Overstreet 1682cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1683cafe5635SKent Overstreet 1684cafe5635SKent Overstreet set_gc_sectors(c); 1685cafe5635SKent Overstreet c->gc_mark_valid = 1; 1686cafe5635SKent Overstreet c->need_gc = 0; 1687cafe5635SKent Overstreet 1688cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&c->uuid_bucket); i++) 1689cafe5635SKent Overstreet SET_GC_MARK(PTR_BUCKET(c, &c->uuid_bucket, i), 1690cafe5635SKent Overstreet GC_MARK_METADATA); 1691cafe5635SKent Overstreet 1692bf0a628aSNicholas Swenson /* don't reclaim buckets to which writeback keys point */ 1693bf0a628aSNicholas Swenson rcu_read_lock(); 16942831231dSColy Li for (i = 0; i < c->devices_max_used; i++) { 1695bf0a628aSNicholas Swenson struct bcache_device *d = c->devices[i]; 1696bf0a628aSNicholas Swenson struct cached_dev *dc; 1697bf0a628aSNicholas Swenson struct keybuf_key *w, *n; 1698bf0a628aSNicholas Swenson unsigned j; 1699bf0a628aSNicholas Swenson 1700bf0a628aSNicholas Swenson if (!d || UUID_FLASH_ONLY(&c->uuids[i])) 1701bf0a628aSNicholas Swenson continue; 1702bf0a628aSNicholas Swenson dc = container_of(d, struct cached_dev, disk); 1703bf0a628aSNicholas Swenson 1704bf0a628aSNicholas Swenson spin_lock(&dc->writeback_keys.lock); 1705bf0a628aSNicholas Swenson rbtree_postorder_for_each_entry_safe(w, n, 1706bf0a628aSNicholas Swenson &dc->writeback_keys.keys, node) 1707bf0a628aSNicholas Swenson for (j = 0; j < KEY_PTRS(&w->key); j++) 1708bf0a628aSNicholas Swenson SET_GC_MARK(PTR_BUCKET(c, &w->key, j), 1709bf0a628aSNicholas Swenson GC_MARK_DIRTY); 1710bf0a628aSNicholas Swenson spin_unlock(&dc->writeback_keys.lock); 1711bf0a628aSNicholas Swenson } 1712bf0a628aSNicholas Swenson rcu_read_unlock(); 1713bf0a628aSNicholas Swenson 1714d44c2f9eSTang Junhui c->avail_nbuckets = 0; 1715cafe5635SKent Overstreet for_each_cache(ca, c, i) { 1716cafe5635SKent Overstreet uint64_t *i; 1717cafe5635SKent Overstreet 1718cafe5635SKent Overstreet ca->invalidate_needs_gc = 0; 1719cafe5635SKent Overstreet 1720cafe5635SKent Overstreet for (i = ca->sb.d; i < ca->sb.d + ca->sb.keys; i++) 1721cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1722cafe5635SKent Overstreet 1723cafe5635SKent Overstreet for (i = ca->prio_buckets; 1724cafe5635SKent Overstreet i < ca->prio_buckets + prio_buckets(ca) * 2; i++) 1725cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1726cafe5635SKent Overstreet 1727cafe5635SKent Overstreet for_each_bucket(b, ca) { 1728cafe5635SKent Overstreet c->need_gc = max(c->need_gc, bucket_gc_gen(b)); 1729cafe5635SKent Overstreet 17304fe6a816SKent Overstreet if (atomic_read(&b->pin)) 17314fe6a816SKent Overstreet continue; 17324fe6a816SKent Overstreet 17334fe6a816SKent Overstreet BUG_ON(!GC_MARK(b) && GC_SECTORS_USED(b)); 17344fe6a816SKent Overstreet 17354fe6a816SKent Overstreet if (!GC_MARK(b) || GC_MARK(b) == GC_MARK_RECLAIMABLE) 1736d44c2f9eSTang Junhui c->avail_nbuckets++; 1737cafe5635SKent Overstreet } 1738cafe5635SKent Overstreet } 1739cafe5635SKent Overstreet 1740cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1741cafe5635SKent Overstreet } 1742cafe5635SKent Overstreet 174372a44517SKent Overstreet static void bch_btree_gc(struct cache_set *c) 1744cafe5635SKent Overstreet { 1745cafe5635SKent Overstreet int ret; 1746cafe5635SKent Overstreet struct gc_stat stats; 1747cafe5635SKent Overstreet struct closure writes; 1748cafe5635SKent Overstreet struct btree_op op; 1749cafe5635SKent Overstreet uint64_t start_time = local_clock(); 175057943511SKent Overstreet 1751c37511b8SKent Overstreet trace_bcache_gc_start(c); 1752cafe5635SKent Overstreet 1753cafe5635SKent Overstreet memset(&stats, 0, sizeof(struct gc_stat)); 1754cafe5635SKent Overstreet closure_init_stack(&writes); 1755b54d6934SKent Overstreet bch_btree_op_init(&op, SHRT_MAX); 1756cafe5635SKent Overstreet 1757cafe5635SKent Overstreet btree_gc_start(c); 1758cafe5635SKent Overstreet 1759771f393eSColy Li /* if CACHE_SET_IO_DISABLE set, gc thread should stop too */ 1760a1f0358bSKent Overstreet do { 1761cafe5635SKent Overstreet ret = btree_root(gc_root, c, &op, &writes, &stats); 1762cafe5635SKent Overstreet closure_sync(&writes); 1763c5f1e5adSKent Overstreet cond_resched(); 1764cafe5635SKent Overstreet 1765*5c25c4fcSTang Junhui if (ret == -EAGAIN) 1766*5c25c4fcSTang Junhui schedule_timeout_interruptible(msecs_to_jiffies 1767*5c25c4fcSTang Junhui (GC_SLEEP_MS)); 1768*5c25c4fcSTang Junhui else if (ret) 1769cafe5635SKent Overstreet pr_warn("gc failed!"); 1770771f393eSColy Li } while (ret && !test_bit(CACHE_SET_IO_DISABLE, &c->flags)); 1771cafe5635SKent Overstreet 1772d44c2f9eSTang Junhui bch_btree_gc_finish(c); 177357943511SKent Overstreet wake_up_allocators(c); 177457943511SKent Overstreet 1775169ef1cfSKent Overstreet bch_time_stats_update(&c->btree_gc_time, start_time); 1776cafe5635SKent Overstreet 1777cafe5635SKent Overstreet stats.key_bytes *= sizeof(uint64_t); 1778cafe5635SKent Overstreet stats.data <<= 9; 1779d44c2f9eSTang Junhui bch_update_bucket_in_use(c, &stats); 1780cafe5635SKent Overstreet memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat)); 1781cafe5635SKent Overstreet 1782c37511b8SKent Overstreet trace_bcache_gc_end(c); 1783cafe5635SKent Overstreet 178472a44517SKent Overstreet bch_moving_gc(c); 1785cafe5635SKent Overstreet } 1786cafe5635SKent Overstreet 1787be628be0SKent Overstreet static bool gc_should_run(struct cache_set *c) 1788cafe5635SKent Overstreet { 1789a1f0358bSKent Overstreet struct cache *ca; 1790a1f0358bSKent Overstreet unsigned i; 179172a44517SKent Overstreet 1792be628be0SKent Overstreet for_each_cache(ca, c, i) 1793be628be0SKent Overstreet if (ca->invalidate_needs_gc) 1794be628be0SKent Overstreet return true; 179572a44517SKent Overstreet 1796be628be0SKent Overstreet if (atomic_read(&c->sectors_to_gc) < 0) 1797be628be0SKent Overstreet return true; 1798be628be0SKent Overstreet 1799be628be0SKent Overstreet return false; 1800be628be0SKent Overstreet } 1801be628be0SKent Overstreet 1802be628be0SKent Overstreet static int bch_gc_thread(void *arg) 1803be628be0SKent Overstreet { 1804be628be0SKent Overstreet struct cache_set *c = arg; 1805be628be0SKent Overstreet 1806be628be0SKent Overstreet while (1) { 1807be628be0SKent Overstreet wait_event_interruptible(c->gc_wait, 1808771f393eSColy Li kthread_should_stop() || 1809771f393eSColy Li test_bit(CACHE_SET_IO_DISABLE, &c->flags) || 1810771f393eSColy Li gc_should_run(c)); 1811be628be0SKent Overstreet 1812771f393eSColy Li if (kthread_should_stop() || 1813771f393eSColy Li test_bit(CACHE_SET_IO_DISABLE, &c->flags)) 181472a44517SKent Overstreet break; 181572a44517SKent Overstreet 1816be628be0SKent Overstreet set_gc_sectors(c); 1817be628be0SKent Overstreet bch_btree_gc(c); 181872a44517SKent Overstreet } 181972a44517SKent Overstreet 1820771f393eSColy Li wait_for_kthread_stop(); 182172a44517SKent Overstreet return 0; 182272a44517SKent Overstreet } 182372a44517SKent Overstreet 182472a44517SKent Overstreet int bch_gc_thread_start(struct cache_set *c) 182572a44517SKent Overstreet { 1826be628be0SKent Overstreet c->gc_thread = kthread_run(bch_gc_thread, c, "bcache_gc"); 18279d134117SVasyl Gomonovych return PTR_ERR_OR_ZERO(c->gc_thread); 1828cafe5635SKent Overstreet } 1829cafe5635SKent Overstreet 1830cafe5635SKent Overstreet /* Initial partial gc */ 1831cafe5635SKent Overstreet 1832487dded8SKent Overstreet static int bch_btree_check_recurse(struct btree *b, struct btree_op *op) 1833cafe5635SKent Overstreet { 183450310164SKent Overstreet int ret = 0; 183550310164SKent Overstreet struct bkey *k, *p = NULL; 1836cafe5635SKent Overstreet struct btree_iter iter; 1837cafe5635SKent Overstreet 1838487dded8SKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) 1839487dded8SKent Overstreet bch_initial_mark_key(b->c, b->level, k); 1840cafe5635SKent Overstreet 1841487dded8SKent Overstreet bch_initial_mark_key(b->c, b->level + 1, &b->key); 1842cafe5635SKent Overstreet 1843cafe5635SKent Overstreet if (b->level) { 1844c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, NULL); 1845cafe5635SKent Overstreet 184650310164SKent Overstreet do { 1847a85e968eSKent Overstreet k = bch_btree_iter_next_filter(&iter, &b->keys, 1848a85e968eSKent Overstreet bch_ptr_bad); 184950310164SKent Overstreet if (k) 18502452cc89SSlava Pestov btree_node_prefetch(b, k); 185150310164SKent Overstreet 1852cafe5635SKent Overstreet if (p) 1853487dded8SKent Overstreet ret = btree(check_recurse, p, b, op); 1854cafe5635SKent Overstreet 185550310164SKent Overstreet p = k; 185650310164SKent Overstreet } while (p && !ret); 1857cafe5635SKent Overstreet } 1858cafe5635SKent Overstreet 1859487dded8SKent Overstreet return ret; 1860cafe5635SKent Overstreet } 1861cafe5635SKent Overstreet 1862c18536a7SKent Overstreet int bch_btree_check(struct cache_set *c) 1863cafe5635SKent Overstreet { 1864c18536a7SKent Overstreet struct btree_op op; 1865cafe5635SKent Overstreet 1866b54d6934SKent Overstreet bch_btree_op_init(&op, SHRT_MAX); 1867cafe5635SKent Overstreet 1868487dded8SKent Overstreet return btree_root(check_recurse, c, &op); 1869cafe5635SKent Overstreet } 1870cafe5635SKent Overstreet 18712531d9eeSKent Overstreet void bch_initial_gc_finish(struct cache_set *c) 18722531d9eeSKent Overstreet { 18732531d9eeSKent Overstreet struct cache *ca; 18742531d9eeSKent Overstreet struct bucket *b; 18752531d9eeSKent Overstreet unsigned i; 18762531d9eeSKent Overstreet 18772531d9eeSKent Overstreet bch_btree_gc_finish(c); 18782531d9eeSKent Overstreet 18792531d9eeSKent Overstreet mutex_lock(&c->bucket_lock); 18802531d9eeSKent Overstreet 18812531d9eeSKent Overstreet /* 18822531d9eeSKent Overstreet * We need to put some unused buckets directly on the prio freelist in 18832531d9eeSKent Overstreet * order to get the allocator thread started - it needs freed buckets in 18842531d9eeSKent Overstreet * order to rewrite the prios and gens, and it needs to rewrite prios 18852531d9eeSKent Overstreet * and gens in order to free buckets. 18862531d9eeSKent Overstreet * 18872531d9eeSKent Overstreet * This is only safe for buckets that have no live data in them, which 18882531d9eeSKent Overstreet * there should always be some of. 18892531d9eeSKent Overstreet */ 18902531d9eeSKent Overstreet for_each_cache(ca, c, i) { 18912531d9eeSKent Overstreet for_each_bucket(b, ca) { 1892682811b3STang Junhui if (fifo_full(&ca->free[RESERVE_PRIO]) && 1893682811b3STang Junhui fifo_full(&ca->free[RESERVE_BTREE])) 18942531d9eeSKent Overstreet break; 18952531d9eeSKent Overstreet 18962531d9eeSKent Overstreet if (bch_can_invalidate_bucket(ca, b) && 18972531d9eeSKent Overstreet !GC_MARK(b)) { 18982531d9eeSKent Overstreet __bch_invalidate_one_bucket(ca, b); 1899682811b3STang Junhui if (!fifo_push(&ca->free[RESERVE_PRIO], 1900682811b3STang Junhui b - ca->buckets)) 1901682811b3STang Junhui fifo_push(&ca->free[RESERVE_BTREE], 19022531d9eeSKent Overstreet b - ca->buckets); 19032531d9eeSKent Overstreet } 19042531d9eeSKent Overstreet } 19052531d9eeSKent Overstreet } 19062531d9eeSKent Overstreet 19072531d9eeSKent Overstreet mutex_unlock(&c->bucket_lock); 19082531d9eeSKent Overstreet } 19092531d9eeSKent Overstreet 1910cafe5635SKent Overstreet /* Btree insertion */ 1911cafe5635SKent Overstreet 1912829a60b9SKent Overstreet static bool btree_insert_key(struct btree *b, struct bkey *k, 19131b207d80SKent Overstreet struct bkey *replace_key) 1914cafe5635SKent Overstreet { 1915829a60b9SKent Overstreet unsigned status; 1916cafe5635SKent Overstreet 1917cafe5635SKent Overstreet BUG_ON(bkey_cmp(k, &b->key) > 0); 1918cafe5635SKent Overstreet 1919829a60b9SKent Overstreet status = bch_btree_insert_key(&b->keys, k, replace_key); 1920829a60b9SKent Overstreet if (status != BTREE_INSERT_STATUS_NO_INSERT) { 1921dc9d98d6SKent Overstreet bch_check_keys(&b->keys, "%u for %s", status, 19221b207d80SKent Overstreet replace_key ? "replace" : "insert"); 1923cafe5635SKent Overstreet 1924829a60b9SKent Overstreet trace_bcache_btree_insert_key(b, k, replace_key != NULL, 1925829a60b9SKent Overstreet status); 1926cafe5635SKent Overstreet return true; 1927829a60b9SKent Overstreet } else 1928829a60b9SKent Overstreet return false; 1929cafe5635SKent Overstreet } 1930cafe5635SKent Overstreet 193159158fdeSKent Overstreet static size_t insert_u64s_remaining(struct btree *b) 193259158fdeSKent Overstreet { 19333572324aSKent Overstreet long ret = bch_btree_keys_u64s_remaining(&b->keys); 193459158fdeSKent Overstreet 193559158fdeSKent Overstreet /* 193659158fdeSKent Overstreet * Might land in the middle of an existing extent and have to split it 193759158fdeSKent Overstreet */ 193859158fdeSKent Overstreet if (b->keys.ops->is_extents) 193959158fdeSKent Overstreet ret -= KEY_MAX_U64S; 194059158fdeSKent Overstreet 194159158fdeSKent Overstreet return max(ret, 0L); 194259158fdeSKent Overstreet } 194359158fdeSKent Overstreet 194426c949f8SKent Overstreet static bool bch_btree_insert_keys(struct btree *b, struct btree_op *op, 19451b207d80SKent Overstreet struct keylist *insert_keys, 19461b207d80SKent Overstreet struct bkey *replace_key) 1947cafe5635SKent Overstreet { 1948cafe5635SKent Overstreet bool ret = false; 1949dc9d98d6SKent Overstreet int oldsize = bch_count_data(&b->keys); 1950cafe5635SKent Overstreet 195126c949f8SKent Overstreet while (!bch_keylist_empty(insert_keys)) { 1952c2f95ae2SKent Overstreet struct bkey *k = insert_keys->keys; 195326c949f8SKent Overstreet 195459158fdeSKent Overstreet if (bkey_u64s(k) > insert_u64s_remaining(b)) 1955403b6cdeSKent Overstreet break; 1956403b6cdeSKent Overstreet 1957403b6cdeSKent Overstreet if (bkey_cmp(k, &b->key) <= 0) { 19583a3b6a4eSKent Overstreet if (!b->level) 19593a3b6a4eSKent Overstreet bkey_put(b->c, k); 196026c949f8SKent Overstreet 1961829a60b9SKent Overstreet ret |= btree_insert_key(b, k, replace_key); 196226c949f8SKent Overstreet bch_keylist_pop_front(insert_keys); 196326c949f8SKent Overstreet } else if (bkey_cmp(&START_KEY(k), &b->key) < 0) { 196426c949f8SKent Overstreet BKEY_PADDED(key) temp; 1965c2f95ae2SKent Overstreet bkey_copy(&temp.key, insert_keys->keys); 196626c949f8SKent Overstreet 196726c949f8SKent Overstreet bch_cut_back(&b->key, &temp.key); 1968c2f95ae2SKent Overstreet bch_cut_front(&b->key, insert_keys->keys); 196926c949f8SKent Overstreet 1970829a60b9SKent Overstreet ret |= btree_insert_key(b, &temp.key, replace_key); 197126c949f8SKent Overstreet break; 197226c949f8SKent Overstreet } else { 197326c949f8SKent Overstreet break; 197426c949f8SKent Overstreet } 1975cafe5635SKent Overstreet } 1976cafe5635SKent Overstreet 1977829a60b9SKent Overstreet if (!ret) 1978829a60b9SKent Overstreet op->insert_collision = true; 1979829a60b9SKent Overstreet 1980403b6cdeSKent Overstreet BUG_ON(!bch_keylist_empty(insert_keys) && b->level); 1981403b6cdeSKent Overstreet 1982dc9d98d6SKent Overstreet BUG_ON(bch_count_data(&b->keys) < oldsize); 1983cafe5635SKent Overstreet return ret; 1984cafe5635SKent Overstreet } 1985cafe5635SKent Overstreet 198626c949f8SKent Overstreet static int btree_split(struct btree *b, struct btree_op *op, 198726c949f8SKent Overstreet struct keylist *insert_keys, 19881b207d80SKent Overstreet struct bkey *replace_key) 1989cafe5635SKent Overstreet { 1990d6fd3b11SKent Overstreet bool split; 1991cafe5635SKent Overstreet struct btree *n1, *n2 = NULL, *n3 = NULL; 1992cafe5635SKent Overstreet uint64_t start_time = local_clock(); 1993b54d6934SKent Overstreet struct closure cl; 199417e21a9fSKent Overstreet struct keylist parent_keys; 1995b54d6934SKent Overstreet 1996b54d6934SKent Overstreet closure_init_stack(&cl); 199717e21a9fSKent Overstreet bch_keylist_init(&parent_keys); 1998cafe5635SKent Overstreet 19990a63b66dSKent Overstreet if (btree_check_reserve(b, op)) { 20000a63b66dSKent Overstreet if (!b->level) 200178365411SKent Overstreet return -EINTR; 20020a63b66dSKent Overstreet else 20030a63b66dSKent Overstreet WARN(1, "insufficient reserve for split\n"); 20040a63b66dSKent Overstreet } 200578365411SKent Overstreet 20060a63b66dSKent Overstreet n1 = btree_node_alloc_replacement(b, op); 2007cafe5635SKent Overstreet if (IS_ERR(n1)) 2008cafe5635SKent Overstreet goto err; 2009cafe5635SKent Overstreet 2010ee811287SKent Overstreet split = set_blocks(btree_bset_first(n1), 2011ee811287SKent Overstreet block_bytes(n1->c)) > (btree_blocks(b) * 4) / 5; 2012cafe5635SKent Overstreet 2013cafe5635SKent Overstreet if (split) { 2014cafe5635SKent Overstreet unsigned keys = 0; 2015cafe5635SKent Overstreet 2016ee811287SKent Overstreet trace_bcache_btree_node_split(b, btree_bset_first(n1)->keys); 2017c37511b8SKent Overstreet 20182452cc89SSlava Pestov n2 = bch_btree_node_alloc(b->c, op, b->level, b->parent); 2019cafe5635SKent Overstreet if (IS_ERR(n2)) 2020cafe5635SKent Overstreet goto err_free1; 2021cafe5635SKent Overstreet 2022d6fd3b11SKent Overstreet if (!b->parent) { 20232452cc89SSlava Pestov n3 = bch_btree_node_alloc(b->c, op, b->level + 1, NULL); 2024cafe5635SKent Overstreet if (IS_ERR(n3)) 2025cafe5635SKent Overstreet goto err_free2; 2026cafe5635SKent Overstreet } 2027cafe5635SKent Overstreet 20282a285686SKent Overstreet mutex_lock(&n1->write_lock); 20292a285686SKent Overstreet mutex_lock(&n2->write_lock); 20302a285686SKent Overstreet 20311b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 2032cafe5635SKent Overstreet 2033d6fd3b11SKent Overstreet /* 2034d6fd3b11SKent Overstreet * Has to be a linear search because we don't have an auxiliary 2035cafe5635SKent Overstreet * search tree yet 2036cafe5635SKent Overstreet */ 2037cafe5635SKent Overstreet 2038ee811287SKent Overstreet while (keys < (btree_bset_first(n1)->keys * 3) / 5) 2039ee811287SKent Overstreet keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), 2040fafff81cSKent Overstreet keys)); 2041cafe5635SKent Overstreet 2042fafff81cSKent Overstreet bkey_copy_key(&n1->key, 2043ee811287SKent Overstreet bset_bkey_idx(btree_bset_first(n1), keys)); 2044ee811287SKent Overstreet keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), keys)); 2045cafe5635SKent Overstreet 2046ee811287SKent Overstreet btree_bset_first(n2)->keys = btree_bset_first(n1)->keys - keys; 2047ee811287SKent Overstreet btree_bset_first(n1)->keys = keys; 2048cafe5635SKent Overstreet 2049ee811287SKent Overstreet memcpy(btree_bset_first(n2)->start, 2050ee811287SKent Overstreet bset_bkey_last(btree_bset_first(n1)), 2051ee811287SKent Overstreet btree_bset_first(n2)->keys * sizeof(uint64_t)); 2052cafe5635SKent Overstreet 2053cafe5635SKent Overstreet bkey_copy_key(&n2->key, &b->key); 2054cafe5635SKent Overstreet 205517e21a9fSKent Overstreet bch_keylist_add(&parent_keys, &n2->key); 2056b54d6934SKent Overstreet bch_btree_node_write(n2, &cl); 20572a285686SKent Overstreet mutex_unlock(&n2->write_lock); 2058cafe5635SKent Overstreet rw_unlock(true, n2); 2059c37511b8SKent Overstreet } else { 2060ee811287SKent Overstreet trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys); 2061c37511b8SKent Overstreet 20622a285686SKent Overstreet mutex_lock(&n1->write_lock); 20631b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 2064c37511b8SKent Overstreet } 2065cafe5635SKent Overstreet 206617e21a9fSKent Overstreet bch_keylist_add(&parent_keys, &n1->key); 2067b54d6934SKent Overstreet bch_btree_node_write(n1, &cl); 20682a285686SKent Overstreet mutex_unlock(&n1->write_lock); 2069cafe5635SKent Overstreet 2070cafe5635SKent Overstreet if (n3) { 2071d6fd3b11SKent Overstreet /* Depth increases, make a new root */ 20722a285686SKent Overstreet mutex_lock(&n3->write_lock); 2073cafe5635SKent Overstreet bkey_copy_key(&n3->key, &MAX_KEY); 207417e21a9fSKent Overstreet bch_btree_insert_keys(n3, op, &parent_keys, NULL); 2075b54d6934SKent Overstreet bch_btree_node_write(n3, &cl); 20762a285686SKent Overstreet mutex_unlock(&n3->write_lock); 2077cafe5635SKent Overstreet 2078b54d6934SKent Overstreet closure_sync(&cl); 2079cafe5635SKent Overstreet bch_btree_set_root(n3); 2080cafe5635SKent Overstreet rw_unlock(true, n3); 2081d6fd3b11SKent Overstreet } else if (!b->parent) { 2082d6fd3b11SKent Overstreet /* Root filled up but didn't need to be split */ 2083b54d6934SKent Overstreet closure_sync(&cl); 2084cafe5635SKent Overstreet bch_btree_set_root(n1); 2085cafe5635SKent Overstreet } else { 208617e21a9fSKent Overstreet /* Split a non root node */ 2087b54d6934SKent Overstreet closure_sync(&cl); 208817e21a9fSKent Overstreet make_btree_freeing_key(b, parent_keys.top); 208917e21a9fSKent Overstreet bch_keylist_push(&parent_keys); 209017e21a9fSKent Overstreet 209117e21a9fSKent Overstreet bch_btree_insert_node(b->parent, op, &parent_keys, NULL, NULL); 209217e21a9fSKent Overstreet BUG_ON(!bch_keylist_empty(&parent_keys)); 2093cafe5635SKent Overstreet } 2094cafe5635SKent Overstreet 209505335cffSKent Overstreet btree_node_free(b); 2096cafe5635SKent Overstreet rw_unlock(true, n1); 2097cafe5635SKent Overstreet 2098169ef1cfSKent Overstreet bch_time_stats_update(&b->c->btree_split_time, start_time); 2099cafe5635SKent Overstreet 2100cafe5635SKent Overstreet return 0; 2101cafe5635SKent Overstreet err_free2: 21025f5837d2SKent Overstreet bkey_put(b->c, &n2->key); 2103e8e1d468SKent Overstreet btree_node_free(n2); 2104cafe5635SKent Overstreet rw_unlock(true, n2); 2105cafe5635SKent Overstreet err_free1: 21065f5837d2SKent Overstreet bkey_put(b->c, &n1->key); 2107e8e1d468SKent Overstreet btree_node_free(n1); 2108cafe5635SKent Overstreet rw_unlock(true, n1); 2109cafe5635SKent Overstreet err: 21100a63b66dSKent Overstreet WARN(1, "bcache: btree split failed (level %u)", b->level); 21115f5837d2SKent Overstreet 2112cafe5635SKent Overstreet if (n3 == ERR_PTR(-EAGAIN) || 2113cafe5635SKent Overstreet n2 == ERR_PTR(-EAGAIN) || 2114cafe5635SKent Overstreet n1 == ERR_PTR(-EAGAIN)) 2115cafe5635SKent Overstreet return -EAGAIN; 2116cafe5635SKent Overstreet 2117cafe5635SKent Overstreet return -ENOMEM; 2118cafe5635SKent Overstreet } 2119cafe5635SKent Overstreet 212026c949f8SKent Overstreet static int bch_btree_insert_node(struct btree *b, struct btree_op *op, 2121c18536a7SKent Overstreet struct keylist *insert_keys, 21221b207d80SKent Overstreet atomic_t *journal_ref, 21231b207d80SKent Overstreet struct bkey *replace_key) 212426c949f8SKent Overstreet { 21252a285686SKent Overstreet struct closure cl; 21262a285686SKent Overstreet 21271b207d80SKent Overstreet BUG_ON(b->level && replace_key); 21281b207d80SKent Overstreet 21292a285686SKent Overstreet closure_init_stack(&cl); 21302a285686SKent Overstreet 21312a285686SKent Overstreet mutex_lock(&b->write_lock); 21322a285686SKent Overstreet 21332a285686SKent Overstreet if (write_block(b) != btree_bset_last(b) && 21342a285686SKent Overstreet b->keys.last_set_unwritten) 21352a285686SKent Overstreet bch_btree_init_next(b); /* just wrote a set */ 21362a285686SKent Overstreet 213759158fdeSKent Overstreet if (bch_keylist_nkeys(insert_keys) > insert_u64s_remaining(b)) { 21382a285686SKent Overstreet mutex_unlock(&b->write_lock); 21392a285686SKent Overstreet goto split; 21402a285686SKent Overstreet } 21412a285686SKent Overstreet 21422a285686SKent Overstreet BUG_ON(write_block(b) != btree_bset_last(b)); 21432a285686SKent Overstreet 21442a285686SKent Overstreet if (bch_btree_insert_keys(b, op, insert_keys, replace_key)) { 21452a285686SKent Overstreet if (!b->level) 21462a285686SKent Overstreet bch_btree_leaf_dirty(b, journal_ref); 21472a285686SKent Overstreet else 21482a285686SKent Overstreet bch_btree_node_write(b, &cl); 21492a285686SKent Overstreet } 21502a285686SKent Overstreet 21512a285686SKent Overstreet mutex_unlock(&b->write_lock); 21522a285686SKent Overstreet 21532a285686SKent Overstreet /* wait for btree node write if necessary, after unlock */ 21542a285686SKent Overstreet closure_sync(&cl); 21552a285686SKent Overstreet 21562a285686SKent Overstreet return 0; 21572a285686SKent Overstreet split: 215826c949f8SKent Overstreet if (current->bio_list) { 215926c949f8SKent Overstreet op->lock = b->c->root->level + 1; 216017e21a9fSKent Overstreet return -EAGAIN; 216126c949f8SKent Overstreet } else if (op->lock <= b->c->root->level) { 216226c949f8SKent Overstreet op->lock = b->c->root->level + 1; 216317e21a9fSKent Overstreet return -EINTR; 216426c949f8SKent Overstreet } else { 216517e21a9fSKent Overstreet /* Invalidated all iterators */ 21663b3e9e50SKent Overstreet int ret = btree_split(b, op, insert_keys, replace_key); 21673b3e9e50SKent Overstreet 21682a285686SKent Overstreet if (bch_keylist_empty(insert_keys)) 216917e21a9fSKent Overstreet return 0; 21702a285686SKent Overstreet else if (!ret) 21712a285686SKent Overstreet return -EINTR; 21722a285686SKent Overstreet return ret; 217317e21a9fSKent Overstreet } 217426c949f8SKent Overstreet } 217526c949f8SKent Overstreet 2176e7c590ebSKent Overstreet int bch_btree_insert_check_key(struct btree *b, struct btree_op *op, 2177e7c590ebSKent Overstreet struct bkey *check_key) 2178e7c590ebSKent Overstreet { 2179e7c590ebSKent Overstreet int ret = -EINTR; 2180e7c590ebSKent Overstreet uint64_t btree_ptr = b->key.ptr[0]; 2181e7c590ebSKent Overstreet unsigned long seq = b->seq; 2182e7c590ebSKent Overstreet struct keylist insert; 2183e7c590ebSKent Overstreet bool upgrade = op->lock == -1; 2184e7c590ebSKent Overstreet 2185e7c590ebSKent Overstreet bch_keylist_init(&insert); 2186e7c590ebSKent Overstreet 2187e7c590ebSKent Overstreet if (upgrade) { 2188e7c590ebSKent Overstreet rw_unlock(false, b); 2189e7c590ebSKent Overstreet rw_lock(true, b, b->level); 2190e7c590ebSKent Overstreet 2191e7c590ebSKent Overstreet if (b->key.ptr[0] != btree_ptr || 21922ef9ccbfSZheng Liu b->seq != seq + 1) { 21932ef9ccbfSZheng Liu op->lock = b->level; 2194e7c590ebSKent Overstreet goto out; 2195e7c590ebSKent Overstreet } 21962ef9ccbfSZheng Liu } 2197e7c590ebSKent Overstreet 2198e7c590ebSKent Overstreet SET_KEY_PTRS(check_key, 1); 2199e7c590ebSKent Overstreet get_random_bytes(&check_key->ptr[0], sizeof(uint64_t)); 2200e7c590ebSKent Overstreet 2201e7c590ebSKent Overstreet SET_PTR_DEV(check_key, 0, PTR_CHECK_DEV); 2202e7c590ebSKent Overstreet 2203e7c590ebSKent Overstreet bch_keylist_add(&insert, check_key); 2204e7c590ebSKent Overstreet 22051b207d80SKent Overstreet ret = bch_btree_insert_node(b, op, &insert, NULL, NULL); 2206e7c590ebSKent Overstreet 2207e7c590ebSKent Overstreet BUG_ON(!ret && !bch_keylist_empty(&insert)); 2208e7c590ebSKent Overstreet out: 2209e7c590ebSKent Overstreet if (upgrade) 2210e7c590ebSKent Overstreet downgrade_write(&b->lock); 2211e7c590ebSKent Overstreet return ret; 2212e7c590ebSKent Overstreet } 2213e7c590ebSKent Overstreet 2214cc7b8819SKent Overstreet struct btree_insert_op { 2215cc7b8819SKent Overstreet struct btree_op op; 2216cc7b8819SKent Overstreet struct keylist *keys; 2217cc7b8819SKent Overstreet atomic_t *journal_ref; 2218cc7b8819SKent Overstreet struct bkey *replace_key; 2219cc7b8819SKent Overstreet }; 2220cc7b8819SKent Overstreet 222108239ca2SWei Yongjun static int btree_insert_fn(struct btree_op *b_op, struct btree *b) 2222cafe5635SKent Overstreet { 2223cc7b8819SKent Overstreet struct btree_insert_op *op = container_of(b_op, 2224cc7b8819SKent Overstreet struct btree_insert_op, op); 2225403b6cdeSKent Overstreet 2226cc7b8819SKent Overstreet int ret = bch_btree_insert_node(b, &op->op, op->keys, 2227cc7b8819SKent Overstreet op->journal_ref, op->replace_key); 2228cc7b8819SKent Overstreet if (ret && !bch_keylist_empty(op->keys)) 2229cc7b8819SKent Overstreet return ret; 2230cc7b8819SKent Overstreet else 2231cc7b8819SKent Overstreet return MAP_DONE; 2232cafe5635SKent Overstreet } 2233cafe5635SKent Overstreet 2234cc7b8819SKent Overstreet int bch_btree_insert(struct cache_set *c, struct keylist *keys, 2235cc7b8819SKent Overstreet atomic_t *journal_ref, struct bkey *replace_key) 2236cafe5635SKent Overstreet { 2237cc7b8819SKent Overstreet struct btree_insert_op op; 2238cafe5635SKent Overstreet int ret = 0; 2239cafe5635SKent Overstreet 2240cc7b8819SKent Overstreet BUG_ON(current->bio_list); 22414f3d4014SKent Overstreet BUG_ON(bch_keylist_empty(keys)); 2242cafe5635SKent Overstreet 2243cc7b8819SKent Overstreet bch_btree_op_init(&op.op, 0); 2244cc7b8819SKent Overstreet op.keys = keys; 2245cc7b8819SKent Overstreet op.journal_ref = journal_ref; 2246cc7b8819SKent Overstreet op.replace_key = replace_key; 2247cafe5635SKent Overstreet 2248cc7b8819SKent Overstreet while (!ret && !bch_keylist_empty(keys)) { 2249cc7b8819SKent Overstreet op.op.lock = 0; 2250cc7b8819SKent Overstreet ret = bch_btree_map_leaf_nodes(&op.op, c, 2251cc7b8819SKent Overstreet &START_KEY(keys->keys), 2252cc7b8819SKent Overstreet btree_insert_fn); 2253cc7b8819SKent Overstreet } 2254cc7b8819SKent Overstreet 2255cc7b8819SKent Overstreet if (ret) { 2256cafe5635SKent Overstreet struct bkey *k; 2257cafe5635SKent Overstreet 22581b207d80SKent Overstreet pr_err("error %i", ret); 2259cafe5635SKent Overstreet 22604f3d4014SKent Overstreet while ((k = bch_keylist_pop(keys))) 22613a3b6a4eSKent Overstreet bkey_put(c, k); 2262cc7b8819SKent Overstreet } else if (op.op.insert_collision) 2263cc7b8819SKent Overstreet ret = -ESRCH; 22646054c6d4SKent Overstreet 2265cafe5635SKent Overstreet return ret; 2266cafe5635SKent Overstreet } 2267cafe5635SKent Overstreet 2268cafe5635SKent Overstreet void bch_btree_set_root(struct btree *b) 2269cafe5635SKent Overstreet { 2270cafe5635SKent Overstreet unsigned i; 2271e49c7c37SKent Overstreet struct closure cl; 2272e49c7c37SKent Overstreet 2273e49c7c37SKent Overstreet closure_init_stack(&cl); 2274cafe5635SKent Overstreet 2275c37511b8SKent Overstreet trace_bcache_btree_set_root(b); 2276c37511b8SKent Overstreet 2277cafe5635SKent Overstreet BUG_ON(!b->written); 2278cafe5635SKent Overstreet 2279cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) 2280cafe5635SKent Overstreet BUG_ON(PTR_BUCKET(b->c, &b->key, i)->prio != BTREE_PRIO); 2281cafe5635SKent Overstreet 2282cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 2283cafe5635SKent Overstreet list_del_init(&b->list); 2284cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 2285cafe5635SKent Overstreet 2286cafe5635SKent Overstreet b->c->root = b; 2287cafe5635SKent Overstreet 2288e49c7c37SKent Overstreet bch_journal_meta(b->c, &cl); 2289e49c7c37SKent Overstreet closure_sync(&cl); 2290cafe5635SKent Overstreet } 2291cafe5635SKent Overstreet 229248dad8baSKent Overstreet /* Map across nodes or keys */ 229348dad8baSKent Overstreet 229448dad8baSKent Overstreet static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op, 229548dad8baSKent Overstreet struct bkey *from, 229648dad8baSKent Overstreet btree_map_nodes_fn *fn, int flags) 229748dad8baSKent Overstreet { 229848dad8baSKent Overstreet int ret = MAP_CONTINUE; 229948dad8baSKent Overstreet 230048dad8baSKent Overstreet if (b->level) { 230148dad8baSKent Overstreet struct bkey *k; 230248dad8baSKent Overstreet struct btree_iter iter; 230348dad8baSKent Overstreet 2304c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, from); 230548dad8baSKent Overstreet 2306a85e968eSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, &b->keys, 230748dad8baSKent Overstreet bch_ptr_bad))) { 230848dad8baSKent Overstreet ret = btree(map_nodes_recurse, k, b, 230948dad8baSKent Overstreet op, from, fn, flags); 231048dad8baSKent Overstreet from = NULL; 231148dad8baSKent Overstreet 231248dad8baSKent Overstreet if (ret != MAP_CONTINUE) 231348dad8baSKent Overstreet return ret; 231448dad8baSKent Overstreet } 231548dad8baSKent Overstreet } 231648dad8baSKent Overstreet 231748dad8baSKent Overstreet if (!b->level || flags == MAP_ALL_NODES) 231848dad8baSKent Overstreet ret = fn(op, b); 231948dad8baSKent Overstreet 232048dad8baSKent Overstreet return ret; 232148dad8baSKent Overstreet } 232248dad8baSKent Overstreet 232348dad8baSKent Overstreet int __bch_btree_map_nodes(struct btree_op *op, struct cache_set *c, 232448dad8baSKent Overstreet struct bkey *from, btree_map_nodes_fn *fn, int flags) 232548dad8baSKent Overstreet { 2326b54d6934SKent Overstreet return btree_root(map_nodes_recurse, c, op, from, fn, flags); 232748dad8baSKent Overstreet } 232848dad8baSKent Overstreet 232948dad8baSKent Overstreet static int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op, 233048dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, 233148dad8baSKent Overstreet int flags) 233248dad8baSKent Overstreet { 233348dad8baSKent Overstreet int ret = MAP_CONTINUE; 233448dad8baSKent Overstreet struct bkey *k; 233548dad8baSKent Overstreet struct btree_iter iter; 233648dad8baSKent Overstreet 2337c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, from); 233848dad8baSKent Overstreet 2339a85e968eSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) { 234048dad8baSKent Overstreet ret = !b->level 234148dad8baSKent Overstreet ? fn(op, b, k) 234248dad8baSKent Overstreet : btree(map_keys_recurse, k, b, op, from, fn, flags); 234348dad8baSKent Overstreet from = NULL; 234448dad8baSKent Overstreet 234548dad8baSKent Overstreet if (ret != MAP_CONTINUE) 234648dad8baSKent Overstreet return ret; 234748dad8baSKent Overstreet } 234848dad8baSKent Overstreet 234948dad8baSKent Overstreet if (!b->level && (flags & MAP_END_KEY)) 235048dad8baSKent Overstreet ret = fn(op, b, &KEY(KEY_INODE(&b->key), 235148dad8baSKent Overstreet KEY_OFFSET(&b->key), 0)); 235248dad8baSKent Overstreet 235348dad8baSKent Overstreet return ret; 235448dad8baSKent Overstreet } 235548dad8baSKent Overstreet 235648dad8baSKent Overstreet int bch_btree_map_keys(struct btree_op *op, struct cache_set *c, 235748dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, int flags) 235848dad8baSKent Overstreet { 2359b54d6934SKent Overstreet return btree_root(map_keys_recurse, c, op, from, fn, flags); 236048dad8baSKent Overstreet } 236148dad8baSKent Overstreet 2362cafe5635SKent Overstreet /* Keybuf code */ 2363cafe5635SKent Overstreet 2364cafe5635SKent Overstreet static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r) 2365cafe5635SKent Overstreet { 2366cafe5635SKent Overstreet /* Overlapping keys compare equal */ 2367cafe5635SKent Overstreet if (bkey_cmp(&l->key, &START_KEY(&r->key)) <= 0) 2368cafe5635SKent Overstreet return -1; 2369cafe5635SKent Overstreet if (bkey_cmp(&START_KEY(&l->key), &r->key) >= 0) 2370cafe5635SKent Overstreet return 1; 2371cafe5635SKent Overstreet return 0; 2372cafe5635SKent Overstreet } 2373cafe5635SKent Overstreet 2374cafe5635SKent Overstreet static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l, 2375cafe5635SKent Overstreet struct keybuf_key *r) 2376cafe5635SKent Overstreet { 2377cafe5635SKent Overstreet return clamp_t(int64_t, bkey_cmp(&l->key, &r->key), -1, 1); 2378cafe5635SKent Overstreet } 2379cafe5635SKent Overstreet 238048dad8baSKent Overstreet struct refill { 238148dad8baSKent Overstreet struct btree_op op; 238248a915a8SKent Overstreet unsigned nr_found; 238348dad8baSKent Overstreet struct keybuf *buf; 238448dad8baSKent Overstreet struct bkey *end; 238548dad8baSKent Overstreet keybuf_pred_fn *pred; 238648dad8baSKent Overstreet }; 238748dad8baSKent Overstreet 238848dad8baSKent Overstreet static int refill_keybuf_fn(struct btree_op *op, struct btree *b, 238948dad8baSKent Overstreet struct bkey *k) 2390cafe5635SKent Overstreet { 239148dad8baSKent Overstreet struct refill *refill = container_of(op, struct refill, op); 239248dad8baSKent Overstreet struct keybuf *buf = refill->buf; 239348dad8baSKent Overstreet int ret = MAP_CONTINUE; 2394cafe5635SKent Overstreet 239548dad8baSKent Overstreet if (bkey_cmp(k, refill->end) >= 0) { 239648dad8baSKent Overstreet ret = MAP_DONE; 239748dad8baSKent Overstreet goto out; 2398cafe5635SKent Overstreet } 2399cafe5635SKent Overstreet 240048dad8baSKent Overstreet if (!KEY_SIZE(k)) /* end key */ 240148dad8baSKent Overstreet goto out; 2402cafe5635SKent Overstreet 240348dad8baSKent Overstreet if (refill->pred(buf, k)) { 2404cafe5635SKent Overstreet struct keybuf_key *w; 2405cafe5635SKent Overstreet 2406cafe5635SKent Overstreet spin_lock(&buf->lock); 2407cafe5635SKent Overstreet 2408cafe5635SKent Overstreet w = array_alloc(&buf->freelist); 240948dad8baSKent Overstreet if (!w) { 241048dad8baSKent Overstreet spin_unlock(&buf->lock); 241148dad8baSKent Overstreet return MAP_DONE; 241248dad8baSKent Overstreet } 2413cafe5635SKent Overstreet 2414cafe5635SKent Overstreet w->private = NULL; 2415cafe5635SKent Overstreet bkey_copy(&w->key, k); 2416cafe5635SKent Overstreet 2417cafe5635SKent Overstreet if (RB_INSERT(&buf->keys, w, node, keybuf_cmp)) 2418cafe5635SKent Overstreet array_free(&buf->freelist, w); 241948a915a8SKent Overstreet else 242048a915a8SKent Overstreet refill->nr_found++; 2421cafe5635SKent Overstreet 242248dad8baSKent Overstreet if (array_freelist_empty(&buf->freelist)) 242348dad8baSKent Overstreet ret = MAP_DONE; 242448dad8baSKent Overstreet 2425cafe5635SKent Overstreet spin_unlock(&buf->lock); 2426cafe5635SKent Overstreet } 242748dad8baSKent Overstreet out: 242848dad8baSKent Overstreet buf->last_scanned = *k; 242948dad8baSKent Overstreet return ret; 2430cafe5635SKent Overstreet } 2431cafe5635SKent Overstreet 2432cafe5635SKent Overstreet void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf, 243372c27061SKent Overstreet struct bkey *end, keybuf_pred_fn *pred) 2434cafe5635SKent Overstreet { 2435cafe5635SKent Overstreet struct bkey start = buf->last_scanned; 243648dad8baSKent Overstreet struct refill refill; 2437cafe5635SKent Overstreet 2438cafe5635SKent Overstreet cond_resched(); 2439cafe5635SKent Overstreet 2440b54d6934SKent Overstreet bch_btree_op_init(&refill.op, -1); 244148a915a8SKent Overstreet refill.nr_found = 0; 244248dad8baSKent Overstreet refill.buf = buf; 244348dad8baSKent Overstreet refill.end = end; 244448dad8baSKent Overstreet refill.pred = pred; 244548dad8baSKent Overstreet 244648dad8baSKent Overstreet bch_btree_map_keys(&refill.op, c, &buf->last_scanned, 244748dad8baSKent Overstreet refill_keybuf_fn, MAP_END_KEY); 2448cafe5635SKent Overstreet 244948a915a8SKent Overstreet trace_bcache_keyscan(refill.nr_found, 2450cafe5635SKent Overstreet KEY_INODE(&start), KEY_OFFSET(&start), 245148a915a8SKent Overstreet KEY_INODE(&buf->last_scanned), 245248a915a8SKent Overstreet KEY_OFFSET(&buf->last_scanned)); 2453cafe5635SKent Overstreet 2454cafe5635SKent Overstreet spin_lock(&buf->lock); 2455cafe5635SKent Overstreet 2456cafe5635SKent Overstreet if (!RB_EMPTY_ROOT(&buf->keys)) { 2457cafe5635SKent Overstreet struct keybuf_key *w; 2458cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2459cafe5635SKent Overstreet buf->start = START_KEY(&w->key); 2460cafe5635SKent Overstreet 2461cafe5635SKent Overstreet w = RB_LAST(&buf->keys, struct keybuf_key, node); 2462cafe5635SKent Overstreet buf->end = w->key; 2463cafe5635SKent Overstreet } else { 2464cafe5635SKent Overstreet buf->start = MAX_KEY; 2465cafe5635SKent Overstreet buf->end = MAX_KEY; 2466cafe5635SKent Overstreet } 2467cafe5635SKent Overstreet 2468cafe5635SKent Overstreet spin_unlock(&buf->lock); 2469cafe5635SKent Overstreet } 2470cafe5635SKent Overstreet 2471cafe5635SKent Overstreet static void __bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2472cafe5635SKent Overstreet { 2473cafe5635SKent Overstreet rb_erase(&w->node, &buf->keys); 2474cafe5635SKent Overstreet array_free(&buf->freelist, w); 2475cafe5635SKent Overstreet } 2476cafe5635SKent Overstreet 2477cafe5635SKent Overstreet void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2478cafe5635SKent Overstreet { 2479cafe5635SKent Overstreet spin_lock(&buf->lock); 2480cafe5635SKent Overstreet __bch_keybuf_del(buf, w); 2481cafe5635SKent Overstreet spin_unlock(&buf->lock); 2482cafe5635SKent Overstreet } 2483cafe5635SKent Overstreet 2484cafe5635SKent Overstreet bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start, 2485cafe5635SKent Overstreet struct bkey *end) 2486cafe5635SKent Overstreet { 2487cafe5635SKent Overstreet bool ret = false; 2488cafe5635SKent Overstreet struct keybuf_key *p, *w, s; 2489cafe5635SKent Overstreet s.key = *start; 2490cafe5635SKent Overstreet 2491cafe5635SKent Overstreet if (bkey_cmp(end, &buf->start) <= 0 || 2492cafe5635SKent Overstreet bkey_cmp(start, &buf->end) >= 0) 2493cafe5635SKent Overstreet return false; 2494cafe5635SKent Overstreet 2495cafe5635SKent Overstreet spin_lock(&buf->lock); 2496cafe5635SKent Overstreet w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp); 2497cafe5635SKent Overstreet 2498cafe5635SKent Overstreet while (w && bkey_cmp(&START_KEY(&w->key), end) < 0) { 2499cafe5635SKent Overstreet p = w; 2500cafe5635SKent Overstreet w = RB_NEXT(w, node); 2501cafe5635SKent Overstreet 2502cafe5635SKent Overstreet if (p->private) 2503cafe5635SKent Overstreet ret = true; 2504cafe5635SKent Overstreet else 2505cafe5635SKent Overstreet __bch_keybuf_del(buf, p); 2506cafe5635SKent Overstreet } 2507cafe5635SKent Overstreet 2508cafe5635SKent Overstreet spin_unlock(&buf->lock); 2509cafe5635SKent Overstreet return ret; 2510cafe5635SKent Overstreet } 2511cafe5635SKent Overstreet 2512cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next(struct keybuf *buf) 2513cafe5635SKent Overstreet { 2514cafe5635SKent Overstreet struct keybuf_key *w; 2515cafe5635SKent Overstreet spin_lock(&buf->lock); 2516cafe5635SKent Overstreet 2517cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2518cafe5635SKent Overstreet 2519cafe5635SKent Overstreet while (w && w->private) 2520cafe5635SKent Overstreet w = RB_NEXT(w, node); 2521cafe5635SKent Overstreet 2522cafe5635SKent Overstreet if (w) 2523cafe5635SKent Overstreet w->private = ERR_PTR(-EINTR); 2524cafe5635SKent Overstreet 2525cafe5635SKent Overstreet spin_unlock(&buf->lock); 2526cafe5635SKent Overstreet return w; 2527cafe5635SKent Overstreet } 2528cafe5635SKent Overstreet 2529cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c, 2530cafe5635SKent Overstreet struct keybuf *buf, 253172c27061SKent Overstreet struct bkey *end, 253272c27061SKent Overstreet keybuf_pred_fn *pred) 2533cafe5635SKent Overstreet { 2534cafe5635SKent Overstreet struct keybuf_key *ret; 2535cafe5635SKent Overstreet 2536cafe5635SKent Overstreet while (1) { 2537cafe5635SKent Overstreet ret = bch_keybuf_next(buf); 2538cafe5635SKent Overstreet if (ret) 2539cafe5635SKent Overstreet break; 2540cafe5635SKent Overstreet 2541cafe5635SKent Overstreet if (bkey_cmp(&buf->last_scanned, end) >= 0) { 2542cafe5635SKent Overstreet pr_debug("scan finished"); 2543cafe5635SKent Overstreet break; 2544cafe5635SKent Overstreet } 2545cafe5635SKent Overstreet 254672c27061SKent Overstreet bch_refill_keybuf(c, buf, end, pred); 2547cafe5635SKent Overstreet } 2548cafe5635SKent Overstreet 2549cafe5635SKent Overstreet return ret; 2550cafe5635SKent Overstreet } 2551cafe5635SKent Overstreet 255272c27061SKent Overstreet void bch_keybuf_init(struct keybuf *buf) 2553cafe5635SKent Overstreet { 2554cafe5635SKent Overstreet buf->last_scanned = MAX_KEY; 2555cafe5635SKent Overstreet buf->keys = RB_ROOT; 2556cafe5635SKent Overstreet 2557cafe5635SKent Overstreet spin_lock_init(&buf->lock); 2558cafe5635SKent Overstreet array_allocator_init(&buf->freelist); 2559cafe5635SKent Overstreet } 2560