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> 3850a260e8SColy Li #include <linux/delay.h> 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 937f4a59deSTang Junhui #define MAX_GC_TIMES 100 945c25c4fcSTang Junhui #define MIN_GC_NODES 100 955c25c4fcSTang Junhui #define GC_SLEEP_MS 100 96cafe5635SKent Overstreet 97cafe5635SKent Overstreet #define PTR_DIRTY_BIT (((uint64_t) 1 << 36)) 98cafe5635SKent Overstreet 99cafe5635SKent Overstreet #define PTR_HASH(c, k) \ 100cafe5635SKent Overstreet (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0)) 101cafe5635SKent Overstreet 102df8e8970SKent Overstreet #define insert_lock(s, b) ((b)->level <= (s)->lock) 103df8e8970SKent Overstreet 104df8e8970SKent Overstreet 105a85e968eSKent Overstreet static inline struct bset *write_block(struct btree *b) 106a85e968eSKent Overstreet { 107a85e968eSKent Overstreet return ((void *) btree_bset_first(b)) + b->written * block_bytes(b->c); 108a85e968eSKent Overstreet } 109a85e968eSKent Overstreet 1102a285686SKent Overstreet static void bch_btree_init_next(struct btree *b) 1112a285686SKent Overstreet { 1122a285686SKent Overstreet /* If not a leaf node, always sort */ 1132a285686SKent Overstreet if (b->level && b->keys.nsets) 1142a285686SKent Overstreet bch_btree_sort(&b->keys, &b->c->sort); 1152a285686SKent Overstreet else 1162a285686SKent Overstreet bch_btree_sort_lazy(&b->keys, &b->c->sort); 1172a285686SKent Overstreet 1182a285686SKent Overstreet if (b->written < btree_blocks(b)) 1192a285686SKent Overstreet bch_bset_init_next(&b->keys, write_block(b), 1202a285686SKent Overstreet bset_magic(&b->c->sb)); 1212a285686SKent Overstreet 1222a285686SKent Overstreet } 1232a285686SKent Overstreet 124cafe5635SKent Overstreet /* Btree key manipulation */ 125cafe5635SKent Overstreet 1263a3b6a4eSKent Overstreet void bkey_put(struct cache_set *c, struct bkey *k) 127e7c590ebSKent Overstreet { 1286f10f7d1SColy Li unsigned int i; 129e7c590ebSKent Overstreet 130e7c590ebSKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 131e7c590ebSKent Overstreet if (ptr_available(c, k, i)) 132e7c590ebSKent Overstreet atomic_dec_bug(&PTR_BUCKET(c, k, i)->pin); 133e7c590ebSKent Overstreet } 134e7c590ebSKent Overstreet 135cafe5635SKent Overstreet /* Btree IO */ 136cafe5635SKent Overstreet 137cafe5635SKent Overstreet static uint64_t btree_csum_set(struct btree *b, struct bset *i) 138cafe5635SKent Overstreet { 139cafe5635SKent Overstreet uint64_t crc = b->key.ptr[0]; 140fafff81cSKent Overstreet void *data = (void *) i + 8, *end = bset_bkey_last(i); 141cafe5635SKent Overstreet 142169ef1cfSKent Overstreet crc = bch_crc64_update(crc, data, end - data); 143c19ed23aSKent Overstreet return crc ^ 0xffffffffffffffffULL; 144cafe5635SKent Overstreet } 145cafe5635SKent Overstreet 14678b77bf8SKent Overstreet void bch_btree_node_read_done(struct btree *b) 147cafe5635SKent Overstreet { 148cafe5635SKent Overstreet const char *err = "bad btree header"; 149ee811287SKent Overstreet struct bset *i = btree_bset_first(b); 15057943511SKent Overstreet struct btree_iter *iter; 151cafe5635SKent Overstreet 152d2f96f48SShenghui Wang /* 153d2f96f48SShenghui Wang * c->fill_iter can allocate an iterator with more memory space 154d2f96f48SShenghui Wang * than static MAX_BSETS. 155d2f96f48SShenghui Wang * See the comment arount cache_set->fill_iter. 156d2f96f48SShenghui Wang */ 157d19936a2SKent Overstreet iter = mempool_alloc(&b->c->fill_iter, GFP_NOIO); 15857943511SKent Overstreet iter->size = b->c->sb.bucket_size / b->c->sb.block_size; 159cafe5635SKent Overstreet iter->used = 0; 160cafe5635SKent Overstreet 161280481d0SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 162c052dd9aSKent Overstreet iter->b = &b->keys; 163280481d0SKent Overstreet #endif 164280481d0SKent Overstreet 16557943511SKent Overstreet if (!i->seq) 166cafe5635SKent Overstreet goto err; 167cafe5635SKent Overstreet 168cafe5635SKent Overstreet for (; 169a85e968eSKent Overstreet b->written < btree_blocks(b) && i->seq == b->keys.set[0].data->seq; 170cafe5635SKent Overstreet i = write_block(b)) { 171cafe5635SKent Overstreet err = "unsupported bset version"; 172cafe5635SKent Overstreet if (i->version > BCACHE_BSET_VERSION) 173cafe5635SKent Overstreet goto err; 174cafe5635SKent Overstreet 175cafe5635SKent Overstreet err = "bad btree header"; 176ee811287SKent Overstreet if (b->written + set_blocks(i, block_bytes(b->c)) > 177ee811287SKent Overstreet btree_blocks(b)) 178cafe5635SKent Overstreet goto err; 179cafe5635SKent Overstreet 180cafe5635SKent Overstreet err = "bad magic"; 18181ab4190SKent Overstreet if (i->magic != bset_magic(&b->c->sb)) 182cafe5635SKent Overstreet goto err; 183cafe5635SKent Overstreet 184cafe5635SKent Overstreet err = "bad checksum"; 185cafe5635SKent Overstreet switch (i->version) { 186cafe5635SKent Overstreet case 0: 187cafe5635SKent Overstreet if (i->csum != csum_set(i)) 188cafe5635SKent Overstreet goto err; 189cafe5635SKent Overstreet break; 190cafe5635SKent Overstreet case BCACHE_BSET_VERSION: 191cafe5635SKent Overstreet if (i->csum != btree_csum_set(b, i)) 192cafe5635SKent Overstreet goto err; 193cafe5635SKent Overstreet break; 194cafe5635SKent Overstreet } 195cafe5635SKent Overstreet 196cafe5635SKent Overstreet err = "empty set"; 197a85e968eSKent Overstreet if (i != b->keys.set[0].data && !i->keys) 198cafe5635SKent Overstreet goto err; 199cafe5635SKent Overstreet 200fafff81cSKent Overstreet bch_btree_iter_push(iter, i->start, bset_bkey_last(i)); 201cafe5635SKent Overstreet 202ee811287SKent Overstreet b->written += set_blocks(i, block_bytes(b->c)); 203cafe5635SKent Overstreet } 204cafe5635SKent Overstreet 205cafe5635SKent Overstreet err = "corrupted btree"; 206cafe5635SKent Overstreet for (i = write_block(b); 207a85e968eSKent Overstreet bset_sector_offset(&b->keys, i) < KEY_SIZE(&b->key); 208cafe5635SKent Overstreet i = ((void *) i) + block_bytes(b->c)) 209a85e968eSKent Overstreet if (i->seq == b->keys.set[0].data->seq) 210cafe5635SKent Overstreet goto err; 211cafe5635SKent Overstreet 212a85e968eSKent Overstreet bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort); 213cafe5635SKent Overstreet 214a85e968eSKent Overstreet i = b->keys.set[0].data; 215cafe5635SKent Overstreet err = "short btree key"; 216a85e968eSKent Overstreet if (b->keys.set[0].size && 217a85e968eSKent Overstreet bkey_cmp(&b->key, &b->keys.set[0].end) < 0) 218cafe5635SKent Overstreet goto err; 219cafe5635SKent Overstreet 220cafe5635SKent Overstreet if (b->written < btree_blocks(b)) 221a85e968eSKent Overstreet bch_bset_init_next(&b->keys, write_block(b), 222a85e968eSKent Overstreet bset_magic(&b->c->sb)); 223cafe5635SKent Overstreet out: 224d19936a2SKent Overstreet mempool_free(iter, &b->c->fill_iter); 22557943511SKent Overstreet return; 226cafe5635SKent Overstreet err: 227cafe5635SKent Overstreet set_btree_node_io_error(b); 22888b9f8c4SKent Overstreet bch_cache_set_error(b->c, "%s at bucket %zu, block %u, %u keys", 229cafe5635SKent Overstreet err, PTR_BUCKET_NR(b->c, &b->key, 0), 23088b9f8c4SKent Overstreet bset_block_offset(b, i), i->keys); 231cafe5635SKent Overstreet goto out; 232cafe5635SKent Overstreet } 233cafe5635SKent Overstreet 2344246a0b6SChristoph Hellwig static void btree_node_read_endio(struct bio *bio) 235cafe5635SKent Overstreet { 23657943511SKent Overstreet struct closure *cl = bio->bi_private; 2371fae7cf0SColy Li 23857943511SKent Overstreet closure_put(cl); 23957943511SKent Overstreet } 240cafe5635SKent Overstreet 24178b77bf8SKent Overstreet static void bch_btree_node_read(struct btree *b) 24257943511SKent Overstreet { 24357943511SKent Overstreet uint64_t start_time = local_clock(); 24457943511SKent Overstreet struct closure cl; 24557943511SKent Overstreet struct bio *bio; 246cafe5635SKent Overstreet 247c37511b8SKent Overstreet trace_bcache_btree_read(b); 248c37511b8SKent Overstreet 24957943511SKent Overstreet closure_init_stack(&cl); 250cafe5635SKent Overstreet 25157943511SKent Overstreet bio = bch_bbio_alloc(b->c); 2524f024f37SKent Overstreet bio->bi_iter.bi_size = KEY_SIZE(&b->key) << 9; 25357943511SKent Overstreet bio->bi_end_io = btree_node_read_endio; 25457943511SKent Overstreet bio->bi_private = &cl; 25570fd7614SChristoph Hellwig bio->bi_opf = REQ_OP_READ | REQ_META; 25657943511SKent Overstreet 257a85e968eSKent Overstreet bch_bio_map(bio, b->keys.set[0].data); 25857943511SKent Overstreet 25957943511SKent Overstreet bch_submit_bbio(bio, b->c, &b->key, 0); 26057943511SKent Overstreet closure_sync(&cl); 26157943511SKent Overstreet 2624e4cbee9SChristoph Hellwig if (bio->bi_status) 26357943511SKent Overstreet set_btree_node_io_error(b); 26457943511SKent Overstreet 26557943511SKent Overstreet bch_bbio_free(bio, b->c); 26657943511SKent Overstreet 26757943511SKent Overstreet if (btree_node_io_error(b)) 26857943511SKent Overstreet goto err; 26957943511SKent Overstreet 27057943511SKent Overstreet bch_btree_node_read_done(b); 27157943511SKent Overstreet bch_time_stats_update(&b->c->btree_read_time, start_time); 27257943511SKent Overstreet 27357943511SKent Overstreet return; 27457943511SKent Overstreet err: 27561cbd250SGeert Uytterhoeven bch_cache_set_error(b->c, "io error reading bucket %zu", 27657943511SKent Overstreet PTR_BUCKET_NR(b->c, &b->key, 0)); 277cafe5635SKent Overstreet } 278cafe5635SKent Overstreet 279cafe5635SKent Overstreet static void btree_complete_write(struct btree *b, struct btree_write *w) 280cafe5635SKent Overstreet { 281cafe5635SKent Overstreet if (w->prio_blocked && 282cafe5635SKent Overstreet !atomic_sub_return(w->prio_blocked, &b->c->prio_blocked)) 283119ba0f8SKent Overstreet wake_up_allocators(b->c); 284cafe5635SKent Overstreet 285cafe5635SKent Overstreet if (w->journal) { 286cafe5635SKent Overstreet atomic_dec_bug(w->journal); 287cafe5635SKent Overstreet __closure_wake_up(&b->c->journal.wait); 288cafe5635SKent Overstreet } 289cafe5635SKent Overstreet 290cafe5635SKent Overstreet w->prio_blocked = 0; 291cafe5635SKent Overstreet w->journal = NULL; 292cafe5635SKent Overstreet } 293cafe5635SKent Overstreet 294cb7a583eSKent Overstreet static void btree_node_write_unlock(struct closure *cl) 295cb7a583eSKent Overstreet { 296cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 297cb7a583eSKent Overstreet 298cb7a583eSKent Overstreet up(&b->io_mutex); 299cb7a583eSKent Overstreet } 300cb7a583eSKent Overstreet 30157943511SKent Overstreet static void __btree_node_write_done(struct closure *cl) 302cafe5635SKent Overstreet { 303cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 304cafe5635SKent Overstreet struct btree_write *w = btree_prev_write(b); 305cafe5635SKent Overstreet 306cafe5635SKent Overstreet bch_bbio_free(b->bio, b->c); 307cafe5635SKent Overstreet b->bio = NULL; 308cafe5635SKent Overstreet btree_complete_write(b, w); 309cafe5635SKent Overstreet 310cafe5635SKent Overstreet if (btree_node_dirty(b)) 31156b30770SKent Overstreet schedule_delayed_work(&b->work, 30 * HZ); 312cafe5635SKent Overstreet 313cb7a583eSKent Overstreet closure_return_with_destructor(cl, btree_node_write_unlock); 314cafe5635SKent Overstreet } 315cafe5635SKent Overstreet 31657943511SKent Overstreet static void btree_node_write_done(struct closure *cl) 317cafe5635SKent Overstreet { 318cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 319cafe5635SKent Overstreet 320491221f8SGuoqing Jiang bio_free_pages(b->bio); 32157943511SKent Overstreet __btree_node_write_done(cl); 322cafe5635SKent Overstreet } 323cafe5635SKent Overstreet 3244246a0b6SChristoph Hellwig static void btree_node_write_endio(struct bio *bio) 32557943511SKent Overstreet { 32657943511SKent Overstreet struct closure *cl = bio->bi_private; 327cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 32857943511SKent Overstreet 3294e4cbee9SChristoph Hellwig if (bio->bi_status) 33057943511SKent Overstreet set_btree_node_io_error(b); 33157943511SKent Overstreet 3324e4cbee9SChristoph Hellwig bch_bbio_count_io_errors(b->c, bio, bio->bi_status, "writing btree"); 33357943511SKent Overstreet closure_put(cl); 33457943511SKent Overstreet } 33557943511SKent Overstreet 33657943511SKent Overstreet static void do_btree_node_write(struct btree *b) 337cafe5635SKent Overstreet { 338cb7a583eSKent Overstreet struct closure *cl = &b->io; 339ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 340cafe5635SKent Overstreet BKEY_PADDED(key) k; 341cafe5635SKent Overstreet 342cafe5635SKent Overstreet i->version = BCACHE_BSET_VERSION; 343cafe5635SKent Overstreet i->csum = btree_csum_set(b, i); 344cafe5635SKent Overstreet 34557943511SKent Overstreet BUG_ON(b->bio); 34657943511SKent Overstreet b->bio = bch_bbio_alloc(b->c); 34757943511SKent Overstreet 34857943511SKent Overstreet b->bio->bi_end_io = btree_node_write_endio; 349faadf0c9SKent Overstreet b->bio->bi_private = cl; 350ee811287SKent Overstreet b->bio->bi_iter.bi_size = roundup(set_bytes(i), block_bytes(b->c)); 35170fd7614SChristoph Hellwig b->bio->bi_opf = REQ_OP_WRITE | REQ_META | REQ_FUA; 352169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 353cafe5635SKent Overstreet 354e49c7c37SKent Overstreet /* 355e49c7c37SKent Overstreet * If we're appending to a leaf node, we don't technically need FUA - 356e49c7c37SKent Overstreet * this write just needs to be persisted before the next journal write, 357e49c7c37SKent Overstreet * which will be marked FLUSH|FUA. 358e49c7c37SKent Overstreet * 359e49c7c37SKent Overstreet * Similarly if we're writing a new btree root - the pointer is going to 360e49c7c37SKent Overstreet * be in the next journal entry. 361e49c7c37SKent Overstreet * 362e49c7c37SKent Overstreet * But if we're writing a new btree node (that isn't a root) or 363e49c7c37SKent Overstreet * appending to a non leaf btree node, we need either FUA or a flush 364e49c7c37SKent Overstreet * when we write the parent with the new pointer. FUA is cheaper than a 365e49c7c37SKent Overstreet * flush, and writes appending to leaf nodes aren't blocking anything so 366e49c7c37SKent Overstreet * just make all btree node writes FUA to keep things sane. 367e49c7c37SKent Overstreet */ 368e49c7c37SKent Overstreet 369cafe5635SKent Overstreet bkey_copy(&k.key, &b->key); 370ee811287SKent Overstreet SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) + 371a85e968eSKent Overstreet bset_sector_offset(&b->keys, i)); 372cafe5635SKent Overstreet 37325d8be77SMing Lei if (!bch_bio_alloc_pages(b->bio, __GFP_NOWARN|GFP_NOWAIT)) { 374cafe5635SKent Overstreet struct bio_vec *bv; 375f936b06aSChristoph Hellwig void *addr = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1)); 3766dc4f100SMing Lei struct bvec_iter_all iter_all; 377cafe5635SKent Overstreet 3782b070cfeSChristoph Hellwig bio_for_each_segment_all(bv, b->bio, iter_all) { 379f936b06aSChristoph Hellwig memcpy(page_address(bv->bv_page), addr, PAGE_SIZE); 380f936b06aSChristoph Hellwig addr += PAGE_SIZE; 381f936b06aSChristoph Hellwig } 382cafe5635SKent Overstreet 383cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 384cafe5635SKent Overstreet 38557943511SKent Overstreet continue_at(cl, btree_node_write_done, NULL); 386cafe5635SKent Overstreet } else { 387b0d30981SColy Li /* 388b0d30981SColy Li * No problem for multipage bvec since the bio is 389b0d30981SColy Li * just allocated 390b0d30981SColy Li */ 391cafe5635SKent Overstreet b->bio->bi_vcnt = 0; 392169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 393cafe5635SKent Overstreet 394cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 395cafe5635SKent Overstreet 396cafe5635SKent Overstreet closure_sync(cl); 397cb7a583eSKent Overstreet continue_at_nobarrier(cl, __btree_node_write_done, NULL); 398cafe5635SKent Overstreet } 399cafe5635SKent Overstreet } 400cafe5635SKent Overstreet 4012a285686SKent Overstreet void __bch_btree_node_write(struct btree *b, struct closure *parent) 402cafe5635SKent Overstreet { 403ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 404cafe5635SKent Overstreet 4052a285686SKent Overstreet lockdep_assert_held(&b->write_lock); 4062a285686SKent Overstreet 407c37511b8SKent Overstreet trace_bcache_btree_write(b); 408c37511b8SKent Overstreet 409cafe5635SKent Overstreet BUG_ON(current->bio_list); 41057943511SKent Overstreet BUG_ON(b->written >= btree_blocks(b)); 41157943511SKent Overstreet BUG_ON(b->written && !i->keys); 412ee811287SKent Overstreet BUG_ON(btree_bset_first(b)->seq != i->seq); 413dc9d98d6SKent Overstreet bch_check_keys(&b->keys, "writing"); 414cafe5635SKent Overstreet 415cafe5635SKent Overstreet cancel_delayed_work(&b->work); 416cafe5635SKent Overstreet 41757943511SKent Overstreet /* If caller isn't waiting for write, parent refcount is cache set */ 418cb7a583eSKent Overstreet down(&b->io_mutex); 419cb7a583eSKent Overstreet closure_init(&b->io, parent ?: &b->c->cl); 42057943511SKent Overstreet 421cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 422cafe5635SKent Overstreet change_bit(BTREE_NODE_write_idx, &b->flags); 423cafe5635SKent Overstreet 42457943511SKent Overstreet do_btree_node_write(b); 425cafe5635SKent Overstreet 426ee811287SKent Overstreet atomic_long_add(set_blocks(i, block_bytes(b->c)) * b->c->sb.block_size, 427cafe5635SKent Overstreet &PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written); 428cafe5635SKent Overstreet 429a85e968eSKent Overstreet b->written += set_blocks(i, block_bytes(b->c)); 4302a285686SKent Overstreet } 431a85e968eSKent Overstreet 4322a285686SKent Overstreet void bch_btree_node_write(struct btree *b, struct closure *parent) 4332a285686SKent Overstreet { 4346f10f7d1SColy Li unsigned int nsets = b->keys.nsets; 4352a285686SKent Overstreet 4362a285686SKent Overstreet lockdep_assert_held(&b->lock); 4372a285686SKent Overstreet 4382a285686SKent Overstreet __bch_btree_node_write(b, parent); 439cafe5635SKent Overstreet 44078b77bf8SKent Overstreet /* 44178b77bf8SKent Overstreet * do verify if there was more than one set initially (i.e. we did a 44278b77bf8SKent Overstreet * sort) and we sorted down to a single set: 44378b77bf8SKent Overstreet */ 4442a285686SKent Overstreet if (nsets && !b->keys.nsets) 44578b77bf8SKent Overstreet bch_btree_verify(b); 44678b77bf8SKent Overstreet 4472a285686SKent Overstreet bch_btree_init_next(b); 448cafe5635SKent Overstreet } 449cafe5635SKent Overstreet 450f269af5aSKent Overstreet static void bch_btree_node_write_sync(struct btree *b) 451f269af5aSKent Overstreet { 452f269af5aSKent Overstreet struct closure cl; 453f269af5aSKent Overstreet 454f269af5aSKent Overstreet closure_init_stack(&cl); 4552a285686SKent Overstreet 4562a285686SKent Overstreet mutex_lock(&b->write_lock); 457f269af5aSKent Overstreet bch_btree_node_write(b, &cl); 4582a285686SKent Overstreet mutex_unlock(&b->write_lock); 4592a285686SKent Overstreet 460f269af5aSKent Overstreet closure_sync(&cl); 461f269af5aSKent Overstreet } 462f269af5aSKent Overstreet 46357943511SKent Overstreet static void btree_node_write_work(struct work_struct *w) 464cafe5635SKent Overstreet { 465cafe5635SKent Overstreet struct btree *b = container_of(to_delayed_work(w), struct btree, work); 466cafe5635SKent Overstreet 4672a285686SKent Overstreet mutex_lock(&b->write_lock); 468cafe5635SKent Overstreet if (btree_node_dirty(b)) 4692a285686SKent Overstreet __bch_btree_node_write(b, NULL); 4702a285686SKent Overstreet mutex_unlock(&b->write_lock); 471cafe5635SKent Overstreet } 472cafe5635SKent Overstreet 473c18536a7SKent Overstreet static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref) 474cafe5635SKent Overstreet { 475ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 476cafe5635SKent Overstreet struct btree_write *w = btree_current_write(b); 477cafe5635SKent Overstreet 4782a285686SKent Overstreet lockdep_assert_held(&b->write_lock); 4792a285686SKent Overstreet 48057943511SKent Overstreet BUG_ON(!b->written); 48157943511SKent Overstreet BUG_ON(!i->keys); 482cafe5635SKent Overstreet 48357943511SKent Overstreet if (!btree_node_dirty(b)) 48456b30770SKent Overstreet schedule_delayed_work(&b->work, 30 * HZ); 48557943511SKent Overstreet 486cafe5635SKent Overstreet set_btree_node_dirty(b); 487cafe5635SKent Overstreet 4885dccefd3SColy Li /* 4895dccefd3SColy Li * w->journal is always the oldest journal pin of all bkeys 4905dccefd3SColy Li * in the leaf node, to make sure the oldest jset seq won't 4915dccefd3SColy Li * be increased before this btree node is flushed. 4925dccefd3SColy Li */ 493c18536a7SKent Overstreet if (journal_ref) { 494cafe5635SKent Overstreet if (w->journal && 495c18536a7SKent Overstreet journal_pin_cmp(b->c, w->journal, journal_ref)) { 496cafe5635SKent Overstreet atomic_dec_bug(w->journal); 497cafe5635SKent Overstreet w->journal = NULL; 498cafe5635SKent Overstreet } 499cafe5635SKent Overstreet 500cafe5635SKent Overstreet if (!w->journal) { 501c18536a7SKent Overstreet w->journal = journal_ref; 502cafe5635SKent Overstreet atomic_inc(w->journal); 503cafe5635SKent Overstreet } 504cafe5635SKent Overstreet } 505cafe5635SKent Overstreet 506cafe5635SKent Overstreet /* Force write if set is too big */ 50757943511SKent Overstreet if (set_bytes(i) > PAGE_SIZE - 48 && 50857943511SKent Overstreet !current->bio_list) 50957943511SKent Overstreet bch_btree_node_write(b, NULL); 510cafe5635SKent Overstreet } 511cafe5635SKent Overstreet 512cafe5635SKent Overstreet /* 513cafe5635SKent Overstreet * Btree in memory cache - allocation/freeing 514cafe5635SKent Overstreet * mca -> memory cache 515cafe5635SKent Overstreet */ 516cafe5635SKent Overstreet 517*7e59c506SDongsheng Yang #define mca_reserve(c) (((!IS_ERR_OR_NULL(c->root) && c->root->level) \ 518cafe5635SKent Overstreet ? c->root->level : 1) * 8 + 16) 519cafe5635SKent Overstreet #define mca_can_free(c) \ 5200a63b66dSKent Overstreet max_t(int, 0, c->btree_cache_used - mca_reserve(c)) 521cafe5635SKent Overstreet 522cafe5635SKent Overstreet static void mca_data_free(struct btree *b) 523cafe5635SKent Overstreet { 524cb7a583eSKent Overstreet BUG_ON(b->io_mutex.count != 1); 525cafe5635SKent Overstreet 526a85e968eSKent Overstreet bch_btree_keys_free(&b->keys); 527cafe5635SKent Overstreet 5280a63b66dSKent Overstreet b->c->btree_cache_used--; 529ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 530cafe5635SKent Overstreet } 531cafe5635SKent Overstreet 532cafe5635SKent Overstreet static void mca_bucket_free(struct btree *b) 533cafe5635SKent Overstreet { 534cafe5635SKent Overstreet BUG_ON(btree_node_dirty(b)); 535cafe5635SKent Overstreet 536cafe5635SKent Overstreet b->key.ptr[0] = 0; 537cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 538cafe5635SKent Overstreet list_move(&b->list, &b->c->btree_cache_freeable); 539cafe5635SKent Overstreet } 540cafe5635SKent Overstreet 5416f10f7d1SColy Li static unsigned int btree_order(struct bkey *k) 542cafe5635SKent Overstreet { 543cafe5635SKent Overstreet return ilog2(KEY_SIZE(k) / PAGE_SECTORS ?: 1); 544cafe5635SKent Overstreet } 545cafe5635SKent Overstreet 546cafe5635SKent Overstreet static void mca_data_alloc(struct btree *b, struct bkey *k, gfp_t gfp) 547cafe5635SKent Overstreet { 548a85e968eSKent Overstreet if (!bch_btree_keys_alloc(&b->keys, 5496f10f7d1SColy Li max_t(unsigned int, 550cafe5635SKent Overstreet ilog2(b->c->btree_pages), 551ee811287SKent Overstreet btree_order(k)), 552ee811287SKent Overstreet gfp)) { 5530a63b66dSKent Overstreet b->c->btree_cache_used++; 554ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache); 555ee811287SKent Overstreet } else { 556ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 557ee811287SKent Overstreet } 558cafe5635SKent Overstreet } 559cafe5635SKent Overstreet 560cafe5635SKent Overstreet static struct btree *mca_bucket_alloc(struct cache_set *c, 561cafe5635SKent Overstreet struct bkey *k, gfp_t gfp) 562cafe5635SKent Overstreet { 563bd9026c8SColy Li /* 564bd9026c8SColy Li * kzalloc() is necessary here for initialization, 565bd9026c8SColy Li * see code comments in bch_btree_keys_init(). 566bd9026c8SColy Li */ 567cafe5635SKent Overstreet struct btree *b = kzalloc(sizeof(struct btree), gfp); 5681fae7cf0SColy Li 569cafe5635SKent Overstreet if (!b) 570cafe5635SKent Overstreet return NULL; 571cafe5635SKent Overstreet 572cafe5635SKent Overstreet init_rwsem(&b->lock); 573cafe5635SKent Overstreet lockdep_set_novalidate_class(&b->lock); 5742a285686SKent Overstreet mutex_init(&b->write_lock); 5752a285686SKent Overstreet lockdep_set_novalidate_class(&b->write_lock); 576cafe5635SKent Overstreet INIT_LIST_HEAD(&b->list); 57757943511SKent Overstreet INIT_DELAYED_WORK(&b->work, btree_node_write_work); 578cafe5635SKent Overstreet b->c = c; 579cb7a583eSKent Overstreet sema_init(&b->io_mutex, 1); 580cafe5635SKent Overstreet 581cafe5635SKent Overstreet mca_data_alloc(b, k, gfp); 582cafe5635SKent Overstreet return b; 583cafe5635SKent Overstreet } 584cafe5635SKent Overstreet 5856f10f7d1SColy Li static int mca_reap(struct btree *b, unsigned int min_order, bool flush) 586cafe5635SKent Overstreet { 587e8e1d468SKent Overstreet struct closure cl; 588e8e1d468SKent Overstreet 589e8e1d468SKent Overstreet closure_init_stack(&cl); 590cafe5635SKent Overstreet lockdep_assert_held(&b->c->bucket_lock); 591cafe5635SKent Overstreet 592cafe5635SKent Overstreet if (!down_write_trylock(&b->lock)) 593cafe5635SKent Overstreet return -ENOMEM; 594cafe5635SKent Overstreet 595a85e968eSKent Overstreet BUG_ON(btree_node_dirty(b) && !b->keys.set[0].data); 596e8e1d468SKent Overstreet 597a85e968eSKent Overstreet if (b->keys.page_order < min_order) 598cb7a583eSKent Overstreet goto out_unlock; 599cb7a583eSKent Overstreet 600cb7a583eSKent Overstreet if (!flush) { 601cb7a583eSKent Overstreet if (btree_node_dirty(b)) 602cb7a583eSKent Overstreet goto out_unlock; 603cb7a583eSKent Overstreet 604cb7a583eSKent Overstreet if (down_trylock(&b->io_mutex)) 605cb7a583eSKent Overstreet goto out_unlock; 606cb7a583eSKent Overstreet up(&b->io_mutex); 607cafe5635SKent Overstreet } 608cafe5635SKent Overstreet 60950a260e8SColy Li retry: 61041508bb7SColy Li /* 61141508bb7SColy Li * BTREE_NODE_dirty might be cleared in btree_flush_btree() by 61241508bb7SColy Li * __bch_btree_node_write(). To avoid an extra flush, acquire 61341508bb7SColy Li * b->write_lock before checking BTREE_NODE_dirty bit. 61441508bb7SColy Li */ 6152a285686SKent Overstreet mutex_lock(&b->write_lock); 61650a260e8SColy Li /* 61750a260e8SColy Li * If this btree node is selected in btree_flush_write() by journal 61850a260e8SColy Li * code, delay and retry until the node is flushed by journal code 61950a260e8SColy Li * and BTREE_NODE_journal_flush bit cleared by btree_flush_write(). 62050a260e8SColy Li */ 62150a260e8SColy Li if (btree_node_journal_flush(b)) { 62246f5aa88SJoe Perches pr_debug("bnode %p is flushing by journal, retry\n", b); 62350a260e8SColy Li mutex_unlock(&b->write_lock); 62450a260e8SColy Li udelay(1); 62550a260e8SColy Li goto retry; 62650a260e8SColy Li } 62750a260e8SColy Li 628f269af5aSKent Overstreet if (btree_node_dirty(b)) 6292a285686SKent Overstreet __bch_btree_node_write(b, &cl); 6302a285686SKent Overstreet mutex_unlock(&b->write_lock); 6312a285686SKent Overstreet 6322a285686SKent Overstreet closure_sync(&cl); 633cafe5635SKent Overstreet 634e8e1d468SKent Overstreet /* wait for any in flight btree write */ 635cb7a583eSKent Overstreet down(&b->io_mutex); 636cb7a583eSKent Overstreet up(&b->io_mutex); 637e8e1d468SKent Overstreet 638cafe5635SKent Overstreet return 0; 639cb7a583eSKent Overstreet out_unlock: 640cb7a583eSKent Overstreet rw_unlock(true, b); 641cb7a583eSKent Overstreet return -ENOMEM; 642cafe5635SKent Overstreet } 643cafe5635SKent Overstreet 6447dc19d5aSDave Chinner static unsigned long bch_mca_scan(struct shrinker *shrink, 6457dc19d5aSDave Chinner struct shrink_control *sc) 646cafe5635SKent Overstreet { 647cafe5635SKent Overstreet struct cache_set *c = container_of(shrink, struct cache_set, shrink); 648cafe5635SKent Overstreet struct btree *b, *t; 649cafe5635SKent Overstreet unsigned long i, nr = sc->nr_to_scan; 6507dc19d5aSDave Chinner unsigned long freed = 0; 651ca71df31STang Junhui unsigned int btree_cache_used; 652cafe5635SKent Overstreet 653cafe5635SKent Overstreet if (c->shrinker_disabled) 6547dc19d5aSDave Chinner return SHRINK_STOP; 655cafe5635SKent Overstreet 6560a63b66dSKent Overstreet if (c->btree_cache_alloc_lock) 6577dc19d5aSDave Chinner return SHRINK_STOP; 658cafe5635SKent Overstreet 659cafe5635SKent Overstreet /* Return -1 if we can't do anything right now */ 660a698e08cSKent Overstreet if (sc->gfp_mask & __GFP_IO) 661cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 662cafe5635SKent Overstreet else if (!mutex_trylock(&c->bucket_lock)) 663cafe5635SKent Overstreet return -1; 664cafe5635SKent Overstreet 66536c9ea98SKent Overstreet /* 66636c9ea98SKent Overstreet * It's _really_ critical that we don't free too many btree nodes - we 66736c9ea98SKent Overstreet * have to always leave ourselves a reserve. The reserve is how we 66836c9ea98SKent Overstreet * guarantee that allocating memory for a new btree node can always 66936c9ea98SKent Overstreet * succeed, so that inserting keys into the btree can always succeed and 67036c9ea98SKent Overstreet * IO can always make forward progress: 67136c9ea98SKent Overstreet */ 672cafe5635SKent Overstreet nr /= c->btree_pages; 6739fcc34b1SColy Li if (nr == 0) 6749fcc34b1SColy Li nr = 1; 675cafe5635SKent Overstreet nr = min_t(unsigned long, nr, mca_can_free(c)); 676cafe5635SKent Overstreet 677cafe5635SKent Overstreet i = 0; 678ca71df31STang Junhui btree_cache_used = c->btree_cache_used; 679d5c9c470SColy Li list_for_each_entry_safe_reverse(b, t, &c->btree_cache_freeable, list) { 680ca71df31STang Junhui if (nr <= 0) 681ca71df31STang Junhui goto out; 682cafe5635SKent Overstreet 683d5c9c470SColy Li if (!mca_reap(b, 0, false)) { 684cafe5635SKent Overstreet mca_data_free(b); 685cafe5635SKent Overstreet rw_unlock(true, b); 6867dc19d5aSDave Chinner freed++; 687cafe5635SKent Overstreet } 688ca71df31STang Junhui nr--; 689d5c9c470SColy Li i++; 690cafe5635SKent Overstreet } 691cafe5635SKent Overstreet 692e3de0446SColy Li list_for_each_entry_safe_reverse(b, t, &c->btree_cache, list) { 693e3de0446SColy Li if (nr <= 0 || i >= btree_cache_used) 694cafe5635SKent Overstreet goto out; 695cafe5635SKent Overstreet 696125d98edSColy Li if (!mca_reap(b, 0, false)) { 697cafe5635SKent Overstreet mca_bucket_free(b); 698cafe5635SKent Overstreet mca_data_free(b); 699cafe5635SKent Overstreet rw_unlock(true, b); 7007dc19d5aSDave Chinner freed++; 701125d98edSColy Li } 702e3de0446SColy Li 703e3de0446SColy Li nr--; 704e3de0446SColy Li i++; 705cafe5635SKent Overstreet } 706cafe5635SKent Overstreet out: 707cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 708f3641c3aSTang Junhui return freed * c->btree_pages; 7097dc19d5aSDave Chinner } 7107dc19d5aSDave Chinner 7117dc19d5aSDave Chinner static unsigned long bch_mca_count(struct shrinker *shrink, 7127dc19d5aSDave Chinner struct shrink_control *sc) 7137dc19d5aSDave Chinner { 7147dc19d5aSDave Chinner struct cache_set *c = container_of(shrink, struct cache_set, shrink); 7157dc19d5aSDave Chinner 7167dc19d5aSDave Chinner if (c->shrinker_disabled) 7177dc19d5aSDave Chinner return 0; 7187dc19d5aSDave Chinner 7190a63b66dSKent Overstreet if (c->btree_cache_alloc_lock) 7207dc19d5aSDave Chinner return 0; 7217dc19d5aSDave Chinner 7227dc19d5aSDave Chinner return mca_can_free(c) * c->btree_pages; 723cafe5635SKent Overstreet } 724cafe5635SKent Overstreet 725cafe5635SKent Overstreet void bch_btree_cache_free(struct cache_set *c) 726cafe5635SKent Overstreet { 727cafe5635SKent Overstreet struct btree *b; 728cafe5635SKent Overstreet struct closure cl; 7291fae7cf0SColy Li 730cafe5635SKent Overstreet closure_init_stack(&cl); 731cafe5635SKent Overstreet 732cafe5635SKent Overstreet if (c->shrink.list.next) 733cafe5635SKent Overstreet unregister_shrinker(&c->shrink); 734cafe5635SKent Overstreet 735cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 736cafe5635SKent Overstreet 737cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 738cafe5635SKent Overstreet if (c->verify_data) 739cafe5635SKent Overstreet list_move(&c->verify_data->list, &c->btree_cache); 74078b77bf8SKent Overstreet 741bf6af170SColy Li free_pages((unsigned long) c->verify_ondisk, ilog2(meta_bucket_pages(&c->sb))); 742cafe5635SKent Overstreet #endif 743cafe5635SKent Overstreet 744cafe5635SKent Overstreet list_splice(&c->btree_cache_freeable, 745cafe5635SKent Overstreet &c->btree_cache); 746cafe5635SKent Overstreet 747cafe5635SKent Overstreet while (!list_empty(&c->btree_cache)) { 748cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 749cafe5635SKent Overstreet 75041508bb7SColy Li /* 75141508bb7SColy Li * This function is called by cache_set_free(), no I/O 75241508bb7SColy Li * request on cache now, it is unnecessary to acquire 75341508bb7SColy Li * b->write_lock before clearing BTREE_NODE_dirty anymore. 75441508bb7SColy Li */ 755e5ec5f47SColy Li if (btree_node_dirty(b)) { 756cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 757cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 758e5ec5f47SColy Li } 759cafe5635SKent Overstreet mca_data_free(b); 760cafe5635SKent Overstreet } 761cafe5635SKent Overstreet 762cafe5635SKent Overstreet while (!list_empty(&c->btree_cache_freed)) { 763cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache_freed, 764cafe5635SKent Overstreet struct btree, list); 765cafe5635SKent Overstreet list_del(&b->list); 766cafe5635SKent Overstreet cancel_delayed_work_sync(&b->work); 767cafe5635SKent Overstreet kfree(b); 768cafe5635SKent Overstreet } 769cafe5635SKent Overstreet 770cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 771cafe5635SKent Overstreet } 772cafe5635SKent Overstreet 773cafe5635SKent Overstreet int bch_btree_cache_alloc(struct cache_set *c) 774cafe5635SKent Overstreet { 7756f10f7d1SColy Li unsigned int i; 776cafe5635SKent Overstreet 777cafe5635SKent Overstreet for (i = 0; i < mca_reserve(c); i++) 77872a44517SKent Overstreet if (!mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL)) 77972a44517SKent Overstreet return -ENOMEM; 780cafe5635SKent Overstreet 781cafe5635SKent Overstreet list_splice_init(&c->btree_cache, 782cafe5635SKent Overstreet &c->btree_cache_freeable); 783cafe5635SKent Overstreet 784cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 785cafe5635SKent Overstreet mutex_init(&c->verify_lock); 786cafe5635SKent Overstreet 78778b77bf8SKent Overstreet c->verify_ondisk = (void *) 788bf6af170SColy Li __get_free_pages(GFP_KERNEL|__GFP_COMP, ilog2(meta_bucket_pages(&c->sb))); 789bf6af170SColy Li if (!c->verify_ondisk) { 790bf6af170SColy Li /* 791bf6af170SColy Li * Don't worry about the mca_rereserve buckets 792bf6af170SColy Li * allocated in previous for-loop, they will be 793bf6af170SColy Li * handled properly in bch_cache_set_unregister(). 794bf6af170SColy Li */ 795bf6af170SColy Li return -ENOMEM; 796bf6af170SColy Li } 79778b77bf8SKent Overstreet 798cafe5635SKent Overstreet c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL); 799cafe5635SKent Overstreet 800cafe5635SKent Overstreet if (c->verify_data && 801a85e968eSKent Overstreet c->verify_data->keys.set->data) 802cafe5635SKent Overstreet list_del_init(&c->verify_data->list); 803cafe5635SKent Overstreet else 804cafe5635SKent Overstreet c->verify_data = NULL; 805cafe5635SKent Overstreet #endif 806cafe5635SKent Overstreet 8077dc19d5aSDave Chinner c->shrink.count_objects = bch_mca_count; 8087dc19d5aSDave Chinner c->shrink.scan_objects = bch_mca_scan; 809cafe5635SKent Overstreet c->shrink.seeks = 4; 810cafe5635SKent Overstreet c->shrink.batch = c->btree_pages * 2; 8116c4ca1e3SMichael Lyle 8126c4ca1e3SMichael Lyle if (register_shrinker(&c->shrink)) 81346f5aa88SJoe Perches pr_warn("bcache: %s: could not register shrinker\n", 8146c4ca1e3SMichael Lyle __func__); 815cafe5635SKent Overstreet 816cafe5635SKent Overstreet return 0; 817cafe5635SKent Overstreet } 818cafe5635SKent Overstreet 819cafe5635SKent Overstreet /* Btree in memory cache - hash table */ 820cafe5635SKent Overstreet 821cafe5635SKent Overstreet static struct hlist_head *mca_hash(struct cache_set *c, struct bkey *k) 822cafe5635SKent Overstreet { 823cafe5635SKent Overstreet return &c->bucket_hash[hash_32(PTR_HASH(c, k), BUCKET_HASH_BITS)]; 824cafe5635SKent Overstreet } 825cafe5635SKent Overstreet 826cafe5635SKent Overstreet static struct btree *mca_find(struct cache_set *c, struct bkey *k) 827cafe5635SKent Overstreet { 828cafe5635SKent Overstreet struct btree *b; 829cafe5635SKent Overstreet 830cafe5635SKent Overstreet rcu_read_lock(); 831cafe5635SKent Overstreet hlist_for_each_entry_rcu(b, mca_hash(c, k), hash) 832cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) == PTR_HASH(c, k)) 833cafe5635SKent Overstreet goto out; 834cafe5635SKent Overstreet b = NULL; 835cafe5635SKent Overstreet out: 836cafe5635SKent Overstreet rcu_read_unlock(); 837cafe5635SKent Overstreet return b; 838cafe5635SKent Overstreet } 839cafe5635SKent Overstreet 8400a63b66dSKent Overstreet static int mca_cannibalize_lock(struct cache_set *c, struct btree_op *op) 8410a63b66dSKent Overstreet { 84234cf78bfSGuoju Fang spin_lock(&c->btree_cannibalize_lock); 84334cf78bfSGuoju Fang if (likely(c->btree_cache_alloc_lock == NULL)) { 84434cf78bfSGuoju Fang c->btree_cache_alloc_lock = current; 84534cf78bfSGuoju Fang } else if (c->btree_cache_alloc_lock != current) { 8460a63b66dSKent Overstreet if (op) 8470a63b66dSKent Overstreet prepare_to_wait(&c->btree_cache_wait, &op->wait, 8480a63b66dSKent Overstreet TASK_UNINTERRUPTIBLE); 84934cf78bfSGuoju Fang spin_unlock(&c->btree_cannibalize_lock); 8500a63b66dSKent Overstreet return -EINTR; 8510a63b66dSKent Overstreet } 85234cf78bfSGuoju Fang spin_unlock(&c->btree_cannibalize_lock); 8530a63b66dSKent Overstreet 8540a63b66dSKent Overstreet return 0; 8550a63b66dSKent Overstreet } 8560a63b66dSKent Overstreet 8570a63b66dSKent Overstreet static struct btree *mca_cannibalize(struct cache_set *c, struct btree_op *op, 8580a63b66dSKent Overstreet struct bkey *k) 859cafe5635SKent Overstreet { 860e8e1d468SKent Overstreet struct btree *b; 861cafe5635SKent Overstreet 862c37511b8SKent Overstreet trace_bcache_btree_cache_cannibalize(c); 863c37511b8SKent Overstreet 8640a63b66dSKent Overstreet if (mca_cannibalize_lock(c, op)) 8650a63b66dSKent Overstreet return ERR_PTR(-EINTR); 866cafe5635SKent Overstreet 867e8e1d468SKent Overstreet list_for_each_entry_reverse(b, &c->btree_cache, list) 868e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), false)) 869e8e1d468SKent Overstreet return b; 870cafe5635SKent Overstreet 871e8e1d468SKent Overstreet list_for_each_entry_reverse(b, &c->btree_cache, list) 872e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), true)) 873e8e1d468SKent Overstreet return b; 874e8e1d468SKent Overstreet 8750a63b66dSKent Overstreet WARN(1, "btree cache cannibalize failed\n"); 876e8e1d468SKent Overstreet return ERR_PTR(-ENOMEM); 877cafe5635SKent Overstreet } 878cafe5635SKent Overstreet 879cafe5635SKent Overstreet /* 880cafe5635SKent Overstreet * We can only have one thread cannibalizing other cached btree nodes at a time, 881cafe5635SKent Overstreet * or we'll deadlock. We use an open coded mutex to ensure that, which a 882cafe5635SKent Overstreet * cannibalize_bucket() will take. This means every time we unlock the root of 883cafe5635SKent Overstreet * the btree, we need to release this lock if we have it held. 884cafe5635SKent Overstreet */ 885df8e8970SKent Overstreet static void bch_cannibalize_unlock(struct cache_set *c) 886cafe5635SKent Overstreet { 88734cf78bfSGuoju Fang spin_lock(&c->btree_cannibalize_lock); 8880a63b66dSKent Overstreet if (c->btree_cache_alloc_lock == current) { 8890a63b66dSKent Overstreet c->btree_cache_alloc_lock = NULL; 8900a63b66dSKent Overstreet wake_up(&c->btree_cache_wait); 891cafe5635SKent Overstreet } 89234cf78bfSGuoju Fang spin_unlock(&c->btree_cannibalize_lock); 893cafe5635SKent Overstreet } 894cafe5635SKent Overstreet 8950a63b66dSKent Overstreet static struct btree *mca_alloc(struct cache_set *c, struct btree_op *op, 8960a63b66dSKent Overstreet struct bkey *k, int level) 897cafe5635SKent Overstreet { 898cafe5635SKent Overstreet struct btree *b; 899cafe5635SKent Overstreet 900e8e1d468SKent Overstreet BUG_ON(current->bio_list); 901e8e1d468SKent Overstreet 902cafe5635SKent Overstreet lockdep_assert_held(&c->bucket_lock); 903cafe5635SKent Overstreet 904cafe5635SKent Overstreet if (mca_find(c, k)) 905cafe5635SKent Overstreet return NULL; 906cafe5635SKent Overstreet 907cafe5635SKent Overstreet /* btree_free() doesn't free memory; it sticks the node on the end of 908cafe5635SKent Overstreet * the list. Check if there's any freed nodes there: 909cafe5635SKent Overstreet */ 910cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freeable, list) 911e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), false)) 912cafe5635SKent Overstreet goto out; 913cafe5635SKent Overstreet 914cafe5635SKent Overstreet /* We never free struct btree itself, just the memory that holds the on 915cafe5635SKent Overstreet * disk node. Check the freed list before allocating a new one: 916cafe5635SKent Overstreet */ 917cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freed, list) 918e8e1d468SKent Overstreet if (!mca_reap(b, 0, false)) { 919cafe5635SKent Overstreet mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO); 920a85e968eSKent Overstreet if (!b->keys.set[0].data) 921cafe5635SKent Overstreet goto err; 922cafe5635SKent Overstreet else 923cafe5635SKent Overstreet goto out; 924cafe5635SKent Overstreet } 925cafe5635SKent Overstreet 926cafe5635SKent Overstreet b = mca_bucket_alloc(c, k, __GFP_NOWARN|GFP_NOIO); 927cafe5635SKent Overstreet if (!b) 928cafe5635SKent Overstreet goto err; 929cafe5635SKent Overstreet 930cafe5635SKent Overstreet BUG_ON(!down_write_trylock(&b->lock)); 931a85e968eSKent Overstreet if (!b->keys.set->data) 932cafe5635SKent Overstreet goto err; 933cafe5635SKent Overstreet out: 934cb7a583eSKent Overstreet BUG_ON(b->io_mutex.count != 1); 935cafe5635SKent Overstreet 936cafe5635SKent Overstreet bkey_copy(&b->key, k); 937cafe5635SKent Overstreet list_move(&b->list, &c->btree_cache); 938cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 939cafe5635SKent Overstreet hlist_add_head_rcu(&b->hash, mca_hash(c, k)); 940cafe5635SKent Overstreet 941cafe5635SKent Overstreet lock_set_subclass(&b->lock.dep_map, level + 1, _THIS_IP_); 942d6fd3b11SKent Overstreet b->parent = (void *) ~0UL; 943a85e968eSKent Overstreet b->flags = 0; 944a85e968eSKent Overstreet b->written = 0; 945a85e968eSKent Overstreet b->level = level; 946cafe5635SKent Overstreet 94765d45231SKent Overstreet if (!b->level) 948a85e968eSKent Overstreet bch_btree_keys_init(&b->keys, &bch_extent_keys_ops, 949a85e968eSKent Overstreet &b->c->expensive_debug_checks); 95065d45231SKent Overstreet else 951a85e968eSKent Overstreet bch_btree_keys_init(&b->keys, &bch_btree_keys_ops, 952a85e968eSKent Overstreet &b->c->expensive_debug_checks); 953cafe5635SKent Overstreet 954cafe5635SKent Overstreet return b; 955cafe5635SKent Overstreet err: 956cafe5635SKent Overstreet if (b) 957cafe5635SKent Overstreet rw_unlock(true, b); 958cafe5635SKent Overstreet 9590a63b66dSKent Overstreet b = mca_cannibalize(c, op, k); 960cafe5635SKent Overstreet if (!IS_ERR(b)) 961cafe5635SKent Overstreet goto out; 962cafe5635SKent Overstreet 963cafe5635SKent Overstreet return b; 964cafe5635SKent Overstreet } 965cafe5635SKent Overstreet 96647344e33SBart Van Assche /* 967cafe5635SKent Overstreet * bch_btree_node_get - find a btree node in the cache and lock it, reading it 968cafe5635SKent Overstreet * in from disk if necessary. 969cafe5635SKent Overstreet * 970ed00aabdSChristoph Hellwig * If IO is necessary and running under submit_bio_noacct, returns -EAGAIN. 971cafe5635SKent Overstreet * 972cafe5635SKent Overstreet * The btree node will have either a read or a write lock held, depending on 973cafe5635SKent Overstreet * level and op->lock. 974cafe5635SKent Overstreet */ 9750a63b66dSKent Overstreet struct btree *bch_btree_node_get(struct cache_set *c, struct btree_op *op, 9762452cc89SSlava Pestov struct bkey *k, int level, bool write, 9772452cc89SSlava Pestov struct btree *parent) 978cafe5635SKent Overstreet { 979cafe5635SKent Overstreet int i = 0; 980cafe5635SKent Overstreet struct btree *b; 981cafe5635SKent Overstreet 982cafe5635SKent Overstreet BUG_ON(level < 0); 983cafe5635SKent Overstreet retry: 984cafe5635SKent Overstreet b = mca_find(c, k); 985cafe5635SKent Overstreet 986cafe5635SKent Overstreet if (!b) { 98757943511SKent Overstreet if (current->bio_list) 98857943511SKent Overstreet return ERR_PTR(-EAGAIN); 98957943511SKent Overstreet 990cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 9910a63b66dSKent Overstreet b = mca_alloc(c, op, k, level); 992cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 993cafe5635SKent Overstreet 994cafe5635SKent Overstreet if (!b) 995cafe5635SKent Overstreet goto retry; 996cafe5635SKent Overstreet if (IS_ERR(b)) 997cafe5635SKent Overstreet return b; 998cafe5635SKent Overstreet 99957943511SKent Overstreet bch_btree_node_read(b); 1000cafe5635SKent Overstreet 1001cafe5635SKent Overstreet if (!write) 1002cafe5635SKent Overstreet downgrade_write(&b->lock); 1003cafe5635SKent Overstreet } else { 1004cafe5635SKent Overstreet rw_lock(write, b, level); 1005cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) != PTR_HASH(c, k)) { 1006cafe5635SKent Overstreet rw_unlock(write, b); 1007cafe5635SKent Overstreet goto retry; 1008cafe5635SKent Overstreet } 1009cafe5635SKent Overstreet BUG_ON(b->level != level); 1010cafe5635SKent Overstreet } 1011cafe5635SKent Overstreet 1012c2e8dcf7SColy Li if (btree_node_io_error(b)) { 1013c2e8dcf7SColy Li rw_unlock(write, b); 1014c2e8dcf7SColy Li return ERR_PTR(-EIO); 1015c2e8dcf7SColy Li } 1016c2e8dcf7SColy Li 1017c2e8dcf7SColy Li BUG_ON(!b->written); 1018c2e8dcf7SColy Li 10192452cc89SSlava Pestov b->parent = parent; 1020cafe5635SKent Overstreet 1021a85e968eSKent Overstreet for (; i <= b->keys.nsets && b->keys.set[i].size; i++) { 1022a85e968eSKent Overstreet prefetch(b->keys.set[i].tree); 1023a85e968eSKent Overstreet prefetch(b->keys.set[i].data); 1024cafe5635SKent Overstreet } 1025cafe5635SKent Overstreet 1026a85e968eSKent Overstreet for (; i <= b->keys.nsets; i++) 1027a85e968eSKent Overstreet prefetch(b->keys.set[i].data); 1028cafe5635SKent Overstreet 1029cafe5635SKent Overstreet return b; 1030cafe5635SKent Overstreet } 1031cafe5635SKent Overstreet 10322452cc89SSlava Pestov static void btree_node_prefetch(struct btree *parent, struct bkey *k) 1033cafe5635SKent Overstreet { 1034cafe5635SKent Overstreet struct btree *b; 1035cafe5635SKent Overstreet 10362452cc89SSlava Pestov mutex_lock(&parent->c->bucket_lock); 10372452cc89SSlava Pestov b = mca_alloc(parent->c, NULL, k, parent->level - 1); 10382452cc89SSlava Pestov mutex_unlock(&parent->c->bucket_lock); 1039cafe5635SKent Overstreet 1040cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(b)) { 10412452cc89SSlava Pestov b->parent = parent; 104257943511SKent Overstreet bch_btree_node_read(b); 1043cafe5635SKent Overstreet rw_unlock(true, b); 1044cafe5635SKent Overstreet } 1045cafe5635SKent Overstreet } 1046cafe5635SKent Overstreet 1047cafe5635SKent Overstreet /* Btree alloc */ 1048cafe5635SKent Overstreet 1049e8e1d468SKent Overstreet static void btree_node_free(struct btree *b) 1050cafe5635SKent Overstreet { 1051c37511b8SKent Overstreet trace_bcache_btree_node_free(b); 1052c37511b8SKent Overstreet 1053cafe5635SKent Overstreet BUG_ON(b == b->c->root); 1054cafe5635SKent Overstreet 105550a260e8SColy Li retry: 10562a285686SKent Overstreet mutex_lock(&b->write_lock); 105750a260e8SColy Li /* 105850a260e8SColy Li * If the btree node is selected and flushing in btree_flush_write(), 105950a260e8SColy Li * delay and retry until the BTREE_NODE_journal_flush bit cleared, 106050a260e8SColy Li * then it is safe to free the btree node here. Otherwise this btree 106150a260e8SColy Li * node will be in race condition. 106250a260e8SColy Li */ 106350a260e8SColy Li if (btree_node_journal_flush(b)) { 106450a260e8SColy Li mutex_unlock(&b->write_lock); 106546f5aa88SJoe Perches pr_debug("bnode %p journal_flush set, retry\n", b); 106650a260e8SColy Li udelay(1); 106750a260e8SColy Li goto retry; 106850a260e8SColy Li } 10692a285686SKent Overstreet 1070e5ec5f47SColy Li if (btree_node_dirty(b)) { 1071cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 1072cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 1073e5ec5f47SColy Li } 1074cafe5635SKent Overstreet 10752a285686SKent Overstreet mutex_unlock(&b->write_lock); 10762a285686SKent Overstreet 1077cafe5635SKent Overstreet cancel_delayed_work(&b->work); 1078cafe5635SKent Overstreet 1079cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 1080cafe5635SKent Overstreet bch_bucket_free(b->c, &b->key); 1081cafe5635SKent Overstreet mca_bucket_free(b); 1082cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 1083cafe5635SKent Overstreet } 1084cafe5635SKent Overstreet 1085c5aa4a31SSlava Pestov struct btree *__bch_btree_node_alloc(struct cache_set *c, struct btree_op *op, 10862452cc89SSlava Pestov int level, bool wait, 10872452cc89SSlava Pestov struct btree *parent) 1088cafe5635SKent Overstreet { 1089cafe5635SKent Overstreet BKEY_PADDED(key) k; 1090cafe5635SKent Overstreet struct btree *b = ERR_PTR(-EAGAIN); 1091cafe5635SKent Overstreet 1092cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1093cafe5635SKent Overstreet retry: 1094c5aa4a31SSlava Pestov if (__bch_bucket_alloc_set(c, RESERVE_BTREE, &k.key, 1, wait)) 1095cafe5635SKent Overstreet goto err; 1096cafe5635SKent Overstreet 10973a3b6a4eSKent Overstreet bkey_put(c, &k.key); 1098cafe5635SKent Overstreet SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS); 1099cafe5635SKent Overstreet 11000a63b66dSKent Overstreet b = mca_alloc(c, op, &k.key, level); 1101cafe5635SKent Overstreet if (IS_ERR(b)) 1102cafe5635SKent Overstreet goto err_free; 1103cafe5635SKent Overstreet 1104cafe5635SKent Overstreet if (!b) { 1105b1a67b0fSKent Overstreet cache_bug(c, 1106b1a67b0fSKent Overstreet "Tried to allocate bucket that was in btree cache"); 1107cafe5635SKent Overstreet goto retry; 1108cafe5635SKent Overstreet } 1109cafe5635SKent Overstreet 11102452cc89SSlava Pestov b->parent = parent; 1111a85e968eSKent Overstreet bch_bset_init_next(&b->keys, b->keys.set->data, bset_magic(&b->c->sb)); 1112cafe5635SKent Overstreet 1113cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1114c37511b8SKent Overstreet 1115c37511b8SKent Overstreet trace_bcache_btree_node_alloc(b); 1116cafe5635SKent Overstreet return b; 1117cafe5635SKent Overstreet err_free: 1118cafe5635SKent Overstreet bch_bucket_free(c, &k.key); 1119cafe5635SKent Overstreet err: 1120cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1121c37511b8SKent Overstreet 1122913dc33fSSlava Pestov trace_bcache_btree_node_alloc_fail(c); 1123cafe5635SKent Overstreet return b; 1124cafe5635SKent Overstreet } 1125cafe5635SKent Overstreet 1126c5aa4a31SSlava Pestov static struct btree *bch_btree_node_alloc(struct cache_set *c, 11272452cc89SSlava Pestov struct btree_op *op, int level, 11282452cc89SSlava Pestov struct btree *parent) 1129c5aa4a31SSlava Pestov { 11302452cc89SSlava Pestov return __bch_btree_node_alloc(c, op, level, op != NULL, parent); 1131c5aa4a31SSlava Pestov } 1132c5aa4a31SSlava Pestov 11330a63b66dSKent Overstreet static struct btree *btree_node_alloc_replacement(struct btree *b, 11340a63b66dSKent Overstreet struct btree_op *op) 1135cafe5635SKent Overstreet { 11362452cc89SSlava Pestov struct btree *n = bch_btree_node_alloc(b->c, op, b->level, b->parent); 11371fae7cf0SColy Li 113867539e85SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 11392a285686SKent Overstreet mutex_lock(&n->write_lock); 114089ebb4a2SKent Overstreet bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort); 114167539e85SKent Overstreet bkey_copy_key(&n->key, &b->key); 11422a285686SKent Overstreet mutex_unlock(&n->write_lock); 114367539e85SKent Overstreet } 1144cafe5635SKent Overstreet 1145cafe5635SKent Overstreet return n; 1146cafe5635SKent Overstreet } 1147cafe5635SKent Overstreet 11488835c123SKent Overstreet static void make_btree_freeing_key(struct btree *b, struct bkey *k) 11498835c123SKent Overstreet { 11506f10f7d1SColy Li unsigned int i; 11518835c123SKent Overstreet 115205335cffSKent Overstreet mutex_lock(&b->c->bucket_lock); 115305335cffSKent Overstreet 115405335cffSKent Overstreet atomic_inc(&b->c->prio_blocked); 115505335cffSKent Overstreet 11568835c123SKent Overstreet bkey_copy(k, &b->key); 11578835c123SKent Overstreet bkey_copy_key(k, &ZERO_KEY); 11588835c123SKent Overstreet 115905335cffSKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 116005335cffSKent Overstreet SET_PTR_GEN(k, i, 116105335cffSKent Overstreet bch_inc_gen(PTR_CACHE(b->c, &b->key, i), 116205335cffSKent Overstreet PTR_BUCKET(b->c, &b->key, i))); 11638835c123SKent Overstreet 116405335cffSKent Overstreet mutex_unlock(&b->c->bucket_lock); 11658835c123SKent Overstreet } 11668835c123SKent Overstreet 116778365411SKent Overstreet static int btree_check_reserve(struct btree *b, struct btree_op *op) 116878365411SKent Overstreet { 116978365411SKent Overstreet struct cache_set *c = b->c; 117078365411SKent Overstreet struct cache *ca; 11716f10f7d1SColy Li unsigned int i, reserve = (c->root->level - b->level) * 2 + 1; 117278365411SKent Overstreet 117378365411SKent Overstreet mutex_lock(&c->bucket_lock); 117478365411SKent Overstreet 117578365411SKent Overstreet for_each_cache(ca, c, i) 117678365411SKent Overstreet if (fifo_used(&ca->free[RESERVE_BTREE]) < reserve) { 117778365411SKent Overstreet if (op) 11780a63b66dSKent Overstreet prepare_to_wait(&c->btree_cache_wait, &op->wait, 117978365411SKent Overstreet TASK_UNINTERRUPTIBLE); 11800a63b66dSKent Overstreet mutex_unlock(&c->bucket_lock); 11810a63b66dSKent Overstreet return -EINTR; 118278365411SKent Overstreet } 118378365411SKent Overstreet 118478365411SKent Overstreet mutex_unlock(&c->bucket_lock); 11850a63b66dSKent Overstreet 11860a63b66dSKent Overstreet return mca_cannibalize_lock(b->c, op); 118778365411SKent Overstreet } 118878365411SKent Overstreet 1189cafe5635SKent Overstreet /* Garbage collection */ 1190cafe5635SKent Overstreet 1191487dded8SKent Overstreet static uint8_t __bch_btree_mark_key(struct cache_set *c, int level, 1192487dded8SKent Overstreet struct bkey *k) 1193cafe5635SKent Overstreet { 1194cafe5635SKent Overstreet uint8_t stale = 0; 11956f10f7d1SColy Li unsigned int i; 1196cafe5635SKent Overstreet struct bucket *g; 1197cafe5635SKent Overstreet 1198cafe5635SKent Overstreet /* 1199cafe5635SKent Overstreet * ptr_invalid() can't return true for the keys that mark btree nodes as 1200cafe5635SKent Overstreet * freed, but since ptr_bad() returns true we'll never actually use them 1201cafe5635SKent Overstreet * for anything and thus we don't want mark their pointers here 1202cafe5635SKent Overstreet */ 1203cafe5635SKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1204cafe5635SKent Overstreet return stale; 1205cafe5635SKent Overstreet 1206cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) { 1207cafe5635SKent Overstreet if (!ptr_available(c, k, i)) 1208cafe5635SKent Overstreet continue; 1209cafe5635SKent Overstreet 1210cafe5635SKent Overstreet g = PTR_BUCKET(c, k, i); 1211cafe5635SKent Overstreet 12123a2fd9d5SKent Overstreet if (gen_after(g->last_gc, PTR_GEN(k, i))) 12133a2fd9d5SKent Overstreet g->last_gc = PTR_GEN(k, i); 1214cafe5635SKent Overstreet 1215cafe5635SKent Overstreet if (ptr_stale(c, k, i)) { 1216cafe5635SKent Overstreet stale = max(stale, ptr_stale(c, k, i)); 1217cafe5635SKent Overstreet continue; 1218cafe5635SKent Overstreet } 1219cafe5635SKent Overstreet 1220cafe5635SKent Overstreet cache_bug_on(GC_MARK(g) && 1221cafe5635SKent Overstreet (GC_MARK(g) == GC_MARK_METADATA) != (level != 0), 1222cafe5635SKent Overstreet c, "inconsistent ptrs: mark = %llu, level = %i", 1223cafe5635SKent Overstreet GC_MARK(g), level); 1224cafe5635SKent Overstreet 1225cafe5635SKent Overstreet if (level) 1226cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_METADATA); 1227cafe5635SKent Overstreet else if (KEY_DIRTY(k)) 1228cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_DIRTY); 12294fe6a816SKent Overstreet else if (!GC_MARK(g)) 12304fe6a816SKent Overstreet SET_GC_MARK(g, GC_MARK_RECLAIMABLE); 1231cafe5635SKent Overstreet 1232cafe5635SKent Overstreet /* guard against overflow */ 12336f10f7d1SColy Li SET_GC_SECTORS_USED(g, min_t(unsigned int, 1234cafe5635SKent Overstreet GC_SECTORS_USED(g) + KEY_SIZE(k), 123594717447SDarrick J. Wong MAX_GC_SECTORS_USED)); 1236cafe5635SKent Overstreet 1237cafe5635SKent Overstreet BUG_ON(!GC_SECTORS_USED(g)); 1238cafe5635SKent Overstreet } 1239cafe5635SKent Overstreet 1240cafe5635SKent Overstreet return stale; 1241cafe5635SKent Overstreet } 1242cafe5635SKent Overstreet 1243cafe5635SKent Overstreet #define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k) 1244cafe5635SKent Overstreet 1245487dded8SKent Overstreet void bch_initial_mark_key(struct cache_set *c, int level, struct bkey *k) 1246487dded8SKent Overstreet { 12476f10f7d1SColy Li unsigned int i; 1248487dded8SKent Overstreet 1249487dded8SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 1250487dded8SKent Overstreet if (ptr_available(c, k, i) && 1251487dded8SKent Overstreet !ptr_stale(c, k, i)) { 1252487dded8SKent Overstreet struct bucket *b = PTR_BUCKET(c, k, i); 1253487dded8SKent Overstreet 1254487dded8SKent Overstreet b->gen = PTR_GEN(k, i); 1255487dded8SKent Overstreet 1256487dded8SKent Overstreet if (level && bkey_cmp(k, &ZERO_KEY)) 1257487dded8SKent Overstreet b->prio = BTREE_PRIO; 1258487dded8SKent Overstreet else if (!level && b->prio == BTREE_PRIO) 1259487dded8SKent Overstreet b->prio = INITIAL_PRIO; 1260487dded8SKent Overstreet } 1261487dded8SKent Overstreet 1262487dded8SKent Overstreet __bch_btree_mark_key(c, level, k); 1263487dded8SKent Overstreet } 1264487dded8SKent Overstreet 1265d44c2f9eSTang Junhui void bch_update_bucket_in_use(struct cache_set *c, struct gc_stat *stats) 1266d44c2f9eSTang Junhui { 1267d44c2f9eSTang Junhui stats->in_use = (c->nbuckets - c->avail_nbuckets) * 100 / c->nbuckets; 1268d44c2f9eSTang Junhui } 1269d44c2f9eSTang Junhui 1270a1f0358bSKent Overstreet static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc) 1271cafe5635SKent Overstreet { 1272cafe5635SKent Overstreet uint8_t stale = 0; 12736f10f7d1SColy Li unsigned int keys = 0, good_keys = 0; 1274cafe5635SKent Overstreet struct bkey *k; 1275cafe5635SKent Overstreet struct btree_iter iter; 1276cafe5635SKent Overstreet struct bset_tree *t; 1277cafe5635SKent Overstreet 1278cafe5635SKent Overstreet gc->nodes++; 1279cafe5635SKent Overstreet 1280c052dd9aSKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) { 1281cafe5635SKent Overstreet stale = max(stale, btree_mark_key(b, k)); 1282a1f0358bSKent Overstreet keys++; 1283cafe5635SKent Overstreet 1284a85e968eSKent Overstreet if (bch_ptr_bad(&b->keys, k)) 1285cafe5635SKent Overstreet continue; 1286cafe5635SKent Overstreet 1287cafe5635SKent Overstreet gc->key_bytes += bkey_u64s(k); 1288cafe5635SKent Overstreet gc->nkeys++; 1289a1f0358bSKent Overstreet good_keys++; 1290cafe5635SKent Overstreet 1291cafe5635SKent Overstreet gc->data += KEY_SIZE(k); 1292cafe5635SKent Overstreet } 1293cafe5635SKent Overstreet 1294a85e968eSKent Overstreet for (t = b->keys.set; t <= &b->keys.set[b->keys.nsets]; t++) 1295cafe5635SKent Overstreet btree_bug_on(t->size && 1296a85e968eSKent Overstreet bset_written(&b->keys, t) && 1297cafe5635SKent Overstreet bkey_cmp(&b->key, &t->end) < 0, 1298cafe5635SKent Overstreet b, "found short btree key in gc"); 1299cafe5635SKent Overstreet 1300a1f0358bSKent Overstreet if (b->c->gc_always_rewrite) 1301a1f0358bSKent Overstreet return true; 1302a1f0358bSKent Overstreet 1303a1f0358bSKent Overstreet if (stale > 10) 1304a1f0358bSKent Overstreet return true; 1305a1f0358bSKent Overstreet 1306a1f0358bSKent Overstreet if ((keys - good_keys) * 2 > keys) 1307a1f0358bSKent Overstreet return true; 1308a1f0358bSKent Overstreet 1309a1f0358bSKent Overstreet return false; 1310cafe5635SKent Overstreet } 1311cafe5635SKent Overstreet 1312a1f0358bSKent Overstreet #define GC_MERGE_NODES 4U 1313cafe5635SKent Overstreet 1314cafe5635SKent Overstreet struct gc_merge_info { 1315cafe5635SKent Overstreet struct btree *b; 13166f10f7d1SColy Li unsigned int keys; 1317cafe5635SKent Overstreet }; 1318cafe5635SKent Overstreet 1319fc2d5988SColy Li static int bch_btree_insert_node(struct btree *b, struct btree_op *op, 1320fc2d5988SColy Li struct keylist *insert_keys, 1321fc2d5988SColy Li atomic_t *journal_ref, 1322fc2d5988SColy Li struct bkey *replace_key); 1323a1f0358bSKent Overstreet 1324a1f0358bSKent Overstreet static int btree_gc_coalesce(struct btree *b, struct btree_op *op, 13250a63b66dSKent Overstreet struct gc_stat *gc, struct gc_merge_info *r) 1326cafe5635SKent Overstreet { 13276f10f7d1SColy Li unsigned int i, nodes = 0, keys = 0, blocks; 1328a1f0358bSKent Overstreet struct btree *new_nodes[GC_MERGE_NODES]; 13290a63b66dSKent Overstreet struct keylist keylist; 1330b54d6934SKent Overstreet struct closure cl; 1331a1f0358bSKent Overstreet struct bkey *k; 1332b54d6934SKent Overstreet 13330a63b66dSKent Overstreet bch_keylist_init(&keylist); 13340a63b66dSKent Overstreet 13350a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 13360a63b66dSKent Overstreet return 0; 13370a63b66dSKent Overstreet 1338a1f0358bSKent Overstreet memset(new_nodes, 0, sizeof(new_nodes)); 1339b54d6934SKent Overstreet closure_init_stack(&cl); 1340cafe5635SKent Overstreet 1341a1f0358bSKent Overstreet while (nodes < GC_MERGE_NODES && !IS_ERR_OR_NULL(r[nodes].b)) 1342cafe5635SKent Overstreet keys += r[nodes++].keys; 1343cafe5635SKent Overstreet 1344cafe5635SKent Overstreet blocks = btree_default_blocks(b->c) * 2 / 3; 1345cafe5635SKent Overstreet 1346cafe5635SKent Overstreet if (nodes < 2 || 1347a85e968eSKent Overstreet __set_blocks(b->keys.set[0].data, keys, 1348ee811287SKent Overstreet block_bytes(b->c)) > blocks * (nodes - 1)) 1349a1f0358bSKent Overstreet return 0; 1350cafe5635SKent Overstreet 1351a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 13520a63b66dSKent Overstreet new_nodes[i] = btree_node_alloc_replacement(r[i].b, NULL); 1353a1f0358bSKent Overstreet if (IS_ERR_OR_NULL(new_nodes[i])) 1354a1f0358bSKent Overstreet goto out_nocoalesce; 1355cafe5635SKent Overstreet } 1356cafe5635SKent Overstreet 13570a63b66dSKent Overstreet /* 13580a63b66dSKent Overstreet * We have to check the reserve here, after we've allocated our new 13590a63b66dSKent Overstreet * nodes, to make sure the insert below will succeed - we also check 13600a63b66dSKent Overstreet * before as an optimization to potentially avoid a bunch of expensive 13610a63b66dSKent Overstreet * allocs/sorts 13620a63b66dSKent Overstreet */ 13630a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 13640a63b66dSKent Overstreet goto out_nocoalesce; 13650a63b66dSKent Overstreet 13662a285686SKent Overstreet for (i = 0; i < nodes; i++) 13672a285686SKent Overstreet mutex_lock(&new_nodes[i]->write_lock); 13682a285686SKent Overstreet 1369cafe5635SKent Overstreet for (i = nodes - 1; i > 0; --i) { 1370ee811287SKent Overstreet struct bset *n1 = btree_bset_first(new_nodes[i]); 1371ee811287SKent Overstreet struct bset *n2 = btree_bset_first(new_nodes[i - 1]); 1372cafe5635SKent Overstreet struct bkey *k, *last = NULL; 1373cafe5635SKent Overstreet 1374cafe5635SKent Overstreet keys = 0; 1375cafe5635SKent Overstreet 1376a1f0358bSKent Overstreet if (i > 1) { 1377cafe5635SKent Overstreet for (k = n2->start; 1378fafff81cSKent Overstreet k < bset_bkey_last(n2); 1379cafe5635SKent Overstreet k = bkey_next(k)) { 1380cafe5635SKent Overstreet if (__set_blocks(n1, n1->keys + keys + 1381ee811287SKent Overstreet bkey_u64s(k), 1382ee811287SKent Overstreet block_bytes(b->c)) > blocks) 1383cafe5635SKent Overstreet break; 1384cafe5635SKent Overstreet 1385cafe5635SKent Overstreet last = k; 1386cafe5635SKent Overstreet keys += bkey_u64s(k); 1387cafe5635SKent Overstreet } 1388a1f0358bSKent Overstreet } else { 1389a1f0358bSKent Overstreet /* 1390a1f0358bSKent Overstreet * Last node we're not getting rid of - we're getting 1391a1f0358bSKent Overstreet * rid of the node at r[0]. Have to try and fit all of 1392a1f0358bSKent Overstreet * the remaining keys into this node; we can't ensure 1393a1f0358bSKent Overstreet * they will always fit due to rounding and variable 1394a1f0358bSKent Overstreet * length keys (shouldn't be possible in practice, 1395a1f0358bSKent Overstreet * though) 1396a1f0358bSKent Overstreet */ 1397a1f0358bSKent Overstreet if (__set_blocks(n1, n1->keys + n2->keys, 1398ee811287SKent Overstreet block_bytes(b->c)) > 1399ee811287SKent Overstreet btree_blocks(new_nodes[i])) 1400be23e837SZhiqiang Liu goto out_unlock_nocoalesce; 1401a1f0358bSKent Overstreet 1402a1f0358bSKent Overstreet keys = n2->keys; 1403a1f0358bSKent Overstreet /* Take the key of the node we're getting rid of */ 1404a1f0358bSKent Overstreet last = &r->b->key; 1405a1f0358bSKent Overstreet } 1406cafe5635SKent Overstreet 1407ee811287SKent Overstreet BUG_ON(__set_blocks(n1, n1->keys + keys, block_bytes(b->c)) > 1408ee811287SKent Overstreet btree_blocks(new_nodes[i])); 1409cafe5635SKent Overstreet 1410a1f0358bSKent Overstreet if (last) 1411a1f0358bSKent Overstreet bkey_copy_key(&new_nodes[i]->key, last); 1412cafe5635SKent Overstreet 1413fafff81cSKent Overstreet memcpy(bset_bkey_last(n1), 1414cafe5635SKent Overstreet n2->start, 1415fafff81cSKent Overstreet (void *) bset_bkey_idx(n2, keys) - (void *) n2->start); 1416cafe5635SKent Overstreet 1417cafe5635SKent Overstreet n1->keys += keys; 1418a1f0358bSKent Overstreet r[i].keys = n1->keys; 1419cafe5635SKent Overstreet 1420cafe5635SKent Overstreet memmove(n2->start, 1421fafff81cSKent Overstreet bset_bkey_idx(n2, keys), 1422fafff81cSKent Overstreet (void *) bset_bkey_last(n2) - 1423fafff81cSKent Overstreet (void *) bset_bkey_idx(n2, keys)); 1424cafe5635SKent Overstreet 1425cafe5635SKent Overstreet n2->keys -= keys; 1426cafe5635SKent Overstreet 14270a63b66dSKent Overstreet if (__bch_keylist_realloc(&keylist, 1428085d2a3dSKent Overstreet bkey_u64s(&new_nodes[i]->key))) 1429be23e837SZhiqiang Liu goto out_unlock_nocoalesce; 1430a1f0358bSKent Overstreet 1431a1f0358bSKent Overstreet bch_btree_node_write(new_nodes[i], &cl); 14320a63b66dSKent Overstreet bch_keylist_add(&keylist, &new_nodes[i]->key); 1433cafe5635SKent Overstreet } 1434cafe5635SKent Overstreet 14352a285686SKent Overstreet for (i = 0; i < nodes; i++) 14362a285686SKent Overstreet mutex_unlock(&new_nodes[i]->write_lock); 14372a285686SKent Overstreet 143805335cffSKent Overstreet closure_sync(&cl); 143905335cffSKent Overstreet 144005335cffSKent Overstreet /* We emptied out this node */ 144105335cffSKent Overstreet BUG_ON(btree_bset_first(new_nodes[0])->keys); 144205335cffSKent Overstreet btree_node_free(new_nodes[0]); 144305335cffSKent Overstreet rw_unlock(true, new_nodes[0]); 1444400ffaa2SSlava Pestov new_nodes[0] = NULL; 144505335cffSKent Overstreet 1446a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 14470a63b66dSKent Overstreet if (__bch_keylist_realloc(&keylist, bkey_u64s(&r[i].b->key))) 1448a1f0358bSKent Overstreet goto out_nocoalesce; 1449a1f0358bSKent Overstreet 14500a63b66dSKent Overstreet make_btree_freeing_key(r[i].b, keylist.top); 14510a63b66dSKent Overstreet bch_keylist_push(&keylist); 1452a1f0358bSKent Overstreet } 1453a1f0358bSKent Overstreet 14540a63b66dSKent Overstreet bch_btree_insert_node(b, op, &keylist, NULL, NULL); 14550a63b66dSKent Overstreet BUG_ON(!bch_keylist_empty(&keylist)); 1456a1f0358bSKent Overstreet 1457a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 1458a1f0358bSKent Overstreet btree_node_free(r[i].b); 1459a1f0358bSKent Overstreet rw_unlock(true, r[i].b); 1460a1f0358bSKent Overstreet 1461a1f0358bSKent Overstreet r[i].b = new_nodes[i]; 1462a1f0358bSKent Overstreet } 1463a1f0358bSKent Overstreet 1464a1f0358bSKent Overstreet memmove(r, r + 1, sizeof(r[0]) * (nodes - 1)); 1465a1f0358bSKent Overstreet r[nodes - 1].b = ERR_PTR(-EINTR); 1466cafe5635SKent Overstreet 1467c37511b8SKent Overstreet trace_bcache_btree_gc_coalesce(nodes); 1468cafe5635SKent Overstreet gc->nodes--; 1469cafe5635SKent Overstreet 14700a63b66dSKent Overstreet bch_keylist_free(&keylist); 14710a63b66dSKent Overstreet 1472a1f0358bSKent Overstreet /* Invalidated our iterator */ 1473a1f0358bSKent Overstreet return -EINTR; 1474a1f0358bSKent Overstreet 1475be23e837SZhiqiang Liu out_unlock_nocoalesce: 1476be23e837SZhiqiang Liu for (i = 0; i < nodes; i++) 1477be23e837SZhiqiang Liu mutex_unlock(&new_nodes[i]->write_lock); 1478be23e837SZhiqiang Liu 1479a1f0358bSKent Overstreet out_nocoalesce: 1480a1f0358bSKent Overstreet closure_sync(&cl); 1481a1f0358bSKent Overstreet 14820a63b66dSKent Overstreet while ((k = bch_keylist_pop(&keylist))) 1483a1f0358bSKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1484a1f0358bSKent Overstreet atomic_dec(&b->c->prio_blocked); 1485f16277caSShenghui Wang bch_keylist_free(&keylist); 1486a1f0358bSKent Overstreet 1487a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) 1488a1f0358bSKent Overstreet if (!IS_ERR_OR_NULL(new_nodes[i])) { 1489a1f0358bSKent Overstreet btree_node_free(new_nodes[i]); 1490a1f0358bSKent Overstreet rw_unlock(true, new_nodes[i]); 1491a1f0358bSKent Overstreet } 1492a1f0358bSKent Overstreet return 0; 1493a1f0358bSKent Overstreet } 1494a1f0358bSKent Overstreet 14950a63b66dSKent Overstreet static int btree_gc_rewrite_node(struct btree *b, struct btree_op *op, 14960a63b66dSKent Overstreet struct btree *replace) 14970a63b66dSKent Overstreet { 14980a63b66dSKent Overstreet struct keylist keys; 14990a63b66dSKent Overstreet struct btree *n; 15000a63b66dSKent Overstreet 15010a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 15020a63b66dSKent Overstreet return 0; 15030a63b66dSKent Overstreet 15040a63b66dSKent Overstreet n = btree_node_alloc_replacement(replace, NULL); 15050a63b66dSKent Overstreet 15060a63b66dSKent Overstreet /* recheck reserve after allocating replacement node */ 15070a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) { 15080a63b66dSKent Overstreet btree_node_free(n); 15090a63b66dSKent Overstreet rw_unlock(true, n); 15100a63b66dSKent Overstreet return 0; 15110a63b66dSKent Overstreet } 15120a63b66dSKent Overstreet 15130a63b66dSKent Overstreet bch_btree_node_write_sync(n); 15140a63b66dSKent Overstreet 15150a63b66dSKent Overstreet bch_keylist_init(&keys); 15160a63b66dSKent Overstreet bch_keylist_add(&keys, &n->key); 15170a63b66dSKent Overstreet 15180a63b66dSKent Overstreet make_btree_freeing_key(replace, keys.top); 15190a63b66dSKent Overstreet bch_keylist_push(&keys); 15200a63b66dSKent Overstreet 15210a63b66dSKent Overstreet bch_btree_insert_node(b, op, &keys, NULL, NULL); 15220a63b66dSKent Overstreet BUG_ON(!bch_keylist_empty(&keys)); 15230a63b66dSKent Overstreet 15240a63b66dSKent Overstreet btree_node_free(replace); 15250a63b66dSKent Overstreet rw_unlock(true, n); 15260a63b66dSKent Overstreet 15270a63b66dSKent Overstreet /* Invalidated our iterator */ 15280a63b66dSKent Overstreet return -EINTR; 15290a63b66dSKent Overstreet } 15300a63b66dSKent Overstreet 15316f10f7d1SColy Li static unsigned int btree_gc_count_keys(struct btree *b) 1532a1f0358bSKent Overstreet { 1533a1f0358bSKent Overstreet struct bkey *k; 1534a1f0358bSKent Overstreet struct btree_iter iter; 15356f10f7d1SColy Li unsigned int ret = 0; 1536a1f0358bSKent Overstreet 1537c052dd9aSKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad) 1538a1f0358bSKent Overstreet ret += bkey_u64s(k); 1539a1f0358bSKent Overstreet 1540a1f0358bSKent Overstreet return ret; 1541cafe5635SKent Overstreet } 1542cafe5635SKent Overstreet 15437f4a59deSTang Junhui static size_t btree_gc_min_nodes(struct cache_set *c) 15447f4a59deSTang Junhui { 15457f4a59deSTang Junhui size_t min_nodes; 15467f4a59deSTang Junhui 15477f4a59deSTang Junhui /* 15487f4a59deSTang Junhui * Since incremental GC would stop 100ms when front 15497f4a59deSTang Junhui * side I/O comes, so when there are many btree nodes, 15507f4a59deSTang Junhui * if GC only processes constant (100) nodes each time, 15517f4a59deSTang Junhui * GC would last a long time, and the front side I/Os 15527f4a59deSTang Junhui * would run out of the buckets (since no new bucket 15537f4a59deSTang Junhui * can be allocated during GC), and be blocked again. 15547f4a59deSTang Junhui * So GC should not process constant nodes, but varied 15557f4a59deSTang Junhui * nodes according to the number of btree nodes, which 15567f4a59deSTang Junhui * realized by dividing GC into constant(100) times, 15577f4a59deSTang Junhui * so when there are many btree nodes, GC can process 15587f4a59deSTang Junhui * more nodes each time, otherwise, GC will process less 15597f4a59deSTang Junhui * nodes each time (but no less than MIN_GC_NODES) 15607f4a59deSTang Junhui */ 15617f4a59deSTang Junhui min_nodes = c->gc_stats.nodes / MAX_GC_TIMES; 15627f4a59deSTang Junhui if (min_nodes < MIN_GC_NODES) 15637f4a59deSTang Junhui min_nodes = MIN_GC_NODES; 15647f4a59deSTang Junhui 15657f4a59deSTang Junhui return min_nodes; 15667f4a59deSTang Junhui } 15677f4a59deSTang Junhui 15687f4a59deSTang Junhui 1569cafe5635SKent Overstreet static int btree_gc_recurse(struct btree *b, struct btree_op *op, 1570cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1571cafe5635SKent Overstreet { 1572a1f0358bSKent Overstreet int ret = 0; 1573a1f0358bSKent Overstreet bool should_rewrite; 1574a1f0358bSKent Overstreet struct bkey *k; 1575a1f0358bSKent Overstreet struct btree_iter iter; 1576cafe5635SKent Overstreet struct gc_merge_info r[GC_MERGE_NODES]; 15772a285686SKent Overstreet struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1; 1578cafe5635SKent Overstreet 1579c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done); 1580cafe5635SKent Overstreet 15812a285686SKent Overstreet for (i = r; i < r + ARRAY_SIZE(r); i++) 15822a285686SKent Overstreet i->b = ERR_PTR(-EINTR); 1583cafe5635SKent Overstreet 1584a1f0358bSKent Overstreet while (1) { 1585a85e968eSKent Overstreet k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad); 1586a1f0358bSKent Overstreet if (k) { 15870a63b66dSKent Overstreet r->b = bch_btree_node_get(b->c, op, k, b->level - 1, 15882452cc89SSlava Pestov true, b); 1589cafe5635SKent Overstreet if (IS_ERR(r->b)) { 1590cafe5635SKent Overstreet ret = PTR_ERR(r->b); 1591cafe5635SKent Overstreet break; 1592cafe5635SKent Overstreet } 1593cafe5635SKent Overstreet 1594a1f0358bSKent Overstreet r->keys = btree_gc_count_keys(r->b); 1595cafe5635SKent Overstreet 15960a63b66dSKent Overstreet ret = btree_gc_coalesce(b, op, gc, r); 1597a1f0358bSKent Overstreet if (ret) 1598cafe5635SKent Overstreet break; 1599cafe5635SKent Overstreet } 1600cafe5635SKent Overstreet 1601a1f0358bSKent Overstreet if (!last->b) 1602a1f0358bSKent Overstreet break; 1603cafe5635SKent Overstreet 1604a1f0358bSKent Overstreet if (!IS_ERR(last->b)) { 1605a1f0358bSKent Overstreet should_rewrite = btree_gc_mark_node(last->b, gc); 16060a63b66dSKent Overstreet if (should_rewrite) { 16070a63b66dSKent Overstreet ret = btree_gc_rewrite_node(b, op, last->b); 16080a63b66dSKent Overstreet if (ret) 1609a1f0358bSKent Overstreet break; 1610a1f0358bSKent Overstreet } 1611a1f0358bSKent Overstreet 1612a1f0358bSKent Overstreet if (last->b->level) { 1613a1f0358bSKent Overstreet ret = btree_gc_recurse(last->b, op, writes, gc); 1614a1f0358bSKent Overstreet if (ret) 1615a1f0358bSKent Overstreet break; 1616a1f0358bSKent Overstreet } 1617a1f0358bSKent Overstreet 1618a1f0358bSKent Overstreet bkey_copy_key(&b->c->gc_done, &last->b->key); 1619a1f0358bSKent Overstreet 1620a1f0358bSKent Overstreet /* 1621a1f0358bSKent Overstreet * Must flush leaf nodes before gc ends, since replace 1622a1f0358bSKent Overstreet * operations aren't journalled 1623cafe5635SKent Overstreet */ 16242a285686SKent Overstreet mutex_lock(&last->b->write_lock); 1625a1f0358bSKent Overstreet if (btree_node_dirty(last->b)) 1626a1f0358bSKent Overstreet bch_btree_node_write(last->b, writes); 16272a285686SKent Overstreet mutex_unlock(&last->b->write_lock); 1628a1f0358bSKent Overstreet rw_unlock(true, last->b); 1629a1f0358bSKent Overstreet } 1630a1f0358bSKent Overstreet 1631a1f0358bSKent Overstreet memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1)); 1632a1f0358bSKent Overstreet r->b = NULL; 1633a1f0358bSKent Overstreet 16345c25c4fcSTang Junhui if (atomic_read(&b->c->search_inflight) && 16357f4a59deSTang Junhui gc->nodes >= gc->nodes_pre + btree_gc_min_nodes(b->c)) { 16365c25c4fcSTang Junhui gc->nodes_pre = gc->nodes; 16375c25c4fcSTang Junhui ret = -EAGAIN; 16385c25c4fcSTang Junhui break; 16395c25c4fcSTang Junhui } 16405c25c4fcSTang Junhui 1641cafe5635SKent Overstreet if (need_resched()) { 1642cafe5635SKent Overstreet ret = -EAGAIN; 1643cafe5635SKent Overstreet break; 1644cafe5635SKent Overstreet } 1645cafe5635SKent Overstreet } 1646cafe5635SKent Overstreet 16472a285686SKent Overstreet for (i = r; i < r + ARRAY_SIZE(r); i++) 16482a285686SKent Overstreet if (!IS_ERR_OR_NULL(i->b)) { 16492a285686SKent Overstreet mutex_lock(&i->b->write_lock); 16502a285686SKent Overstreet if (btree_node_dirty(i->b)) 16512a285686SKent Overstreet bch_btree_node_write(i->b, writes); 16522a285686SKent Overstreet mutex_unlock(&i->b->write_lock); 16532a285686SKent Overstreet rw_unlock(true, i->b); 1654a1f0358bSKent Overstreet } 1655cafe5635SKent Overstreet 1656cafe5635SKent Overstreet return ret; 1657cafe5635SKent Overstreet } 1658cafe5635SKent Overstreet 1659cafe5635SKent Overstreet static int bch_btree_gc_root(struct btree *b, struct btree_op *op, 1660cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1661cafe5635SKent Overstreet { 1662cafe5635SKent Overstreet struct btree *n = NULL; 1663a1f0358bSKent Overstreet int ret = 0; 1664a1f0358bSKent Overstreet bool should_rewrite; 1665cafe5635SKent Overstreet 1666a1f0358bSKent Overstreet should_rewrite = btree_gc_mark_node(b, gc); 1667a1f0358bSKent Overstreet if (should_rewrite) { 16680a63b66dSKent Overstreet n = btree_node_alloc_replacement(b, NULL); 1669cafe5635SKent Overstreet 1670cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 1671a1f0358bSKent Overstreet bch_btree_node_write_sync(n); 16722a285686SKent Overstreet 1673a1f0358bSKent Overstreet bch_btree_set_root(n); 1674a1f0358bSKent Overstreet btree_node_free(b); 1675a1f0358bSKent Overstreet rw_unlock(true, n); 1676a1f0358bSKent Overstreet 1677a1f0358bSKent Overstreet return -EINTR; 1678cafe5635SKent Overstreet } 1679a1f0358bSKent Overstreet } 1680a1f0358bSKent Overstreet 1681487dded8SKent Overstreet __bch_btree_mark_key(b->c, b->level + 1, &b->key); 1682487dded8SKent Overstreet 1683a1f0358bSKent Overstreet if (b->level) { 1684a1f0358bSKent Overstreet ret = btree_gc_recurse(b, op, writes, gc); 1685a1f0358bSKent Overstreet if (ret) 1686a1f0358bSKent Overstreet return ret; 1687a1f0358bSKent Overstreet } 1688a1f0358bSKent Overstreet 1689a1f0358bSKent Overstreet bkey_copy_key(&b->c->gc_done, &b->key); 1690cafe5635SKent Overstreet 1691cafe5635SKent Overstreet return ret; 1692cafe5635SKent Overstreet } 1693cafe5635SKent Overstreet 1694cafe5635SKent Overstreet static void btree_gc_start(struct cache_set *c) 1695cafe5635SKent Overstreet { 1696cafe5635SKent Overstreet struct cache *ca; 1697cafe5635SKent Overstreet struct bucket *b; 16986f10f7d1SColy Li unsigned int i; 1699cafe5635SKent Overstreet 1700cafe5635SKent Overstreet if (!c->gc_mark_valid) 1701cafe5635SKent Overstreet return; 1702cafe5635SKent Overstreet 1703cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1704cafe5635SKent Overstreet 1705cafe5635SKent Overstreet c->gc_mark_valid = 0; 1706cafe5635SKent Overstreet c->gc_done = ZERO_KEY; 1707cafe5635SKent Overstreet 1708cafe5635SKent Overstreet for_each_cache(ca, c, i) 1709cafe5635SKent Overstreet for_each_bucket(b, ca) { 17103a2fd9d5SKent Overstreet b->last_gc = b->gen; 171129ebf465SKent Overstreet if (!atomic_read(&b->pin)) { 17124fe6a816SKent Overstreet SET_GC_MARK(b, 0); 171329ebf465SKent Overstreet SET_GC_SECTORS_USED(b, 0); 171429ebf465SKent Overstreet } 1715cafe5635SKent Overstreet } 1716cafe5635SKent Overstreet 1717cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1718cafe5635SKent Overstreet } 1719cafe5635SKent Overstreet 1720d44c2f9eSTang Junhui static void bch_btree_gc_finish(struct cache_set *c) 1721cafe5635SKent Overstreet { 1722cafe5635SKent Overstreet struct bucket *b; 1723cafe5635SKent Overstreet struct cache *ca; 17246f10f7d1SColy Li unsigned int i; 1725cafe5635SKent Overstreet 1726cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1727cafe5635SKent Overstreet 1728cafe5635SKent Overstreet set_gc_sectors(c); 1729cafe5635SKent Overstreet c->gc_mark_valid = 1; 1730cafe5635SKent Overstreet c->need_gc = 0; 1731cafe5635SKent Overstreet 1732cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&c->uuid_bucket); i++) 1733cafe5635SKent Overstreet SET_GC_MARK(PTR_BUCKET(c, &c->uuid_bucket, i), 1734cafe5635SKent Overstreet GC_MARK_METADATA); 1735cafe5635SKent Overstreet 1736bf0a628aSNicholas Swenson /* don't reclaim buckets to which writeback keys point */ 1737bf0a628aSNicholas Swenson rcu_read_lock(); 17382831231dSColy Li for (i = 0; i < c->devices_max_used; i++) { 1739bf0a628aSNicholas Swenson struct bcache_device *d = c->devices[i]; 1740bf0a628aSNicholas Swenson struct cached_dev *dc; 1741bf0a628aSNicholas Swenson struct keybuf_key *w, *n; 17426f10f7d1SColy Li unsigned int j; 1743bf0a628aSNicholas Swenson 1744bf0a628aSNicholas Swenson if (!d || UUID_FLASH_ONLY(&c->uuids[i])) 1745bf0a628aSNicholas Swenson continue; 1746bf0a628aSNicholas Swenson dc = container_of(d, struct cached_dev, disk); 1747bf0a628aSNicholas Swenson 1748bf0a628aSNicholas Swenson spin_lock(&dc->writeback_keys.lock); 1749bf0a628aSNicholas Swenson rbtree_postorder_for_each_entry_safe(w, n, 1750bf0a628aSNicholas Swenson &dc->writeback_keys.keys, node) 1751bf0a628aSNicholas Swenson for (j = 0; j < KEY_PTRS(&w->key); j++) 1752bf0a628aSNicholas Swenson SET_GC_MARK(PTR_BUCKET(c, &w->key, j), 1753bf0a628aSNicholas Swenson GC_MARK_DIRTY); 1754bf0a628aSNicholas Swenson spin_unlock(&dc->writeback_keys.lock); 1755bf0a628aSNicholas Swenson } 1756bf0a628aSNicholas Swenson rcu_read_unlock(); 1757bf0a628aSNicholas Swenson 1758d44c2f9eSTang Junhui c->avail_nbuckets = 0; 1759cafe5635SKent Overstreet for_each_cache(ca, c, i) { 1760cafe5635SKent Overstreet uint64_t *i; 1761cafe5635SKent Overstreet 1762cafe5635SKent Overstreet ca->invalidate_needs_gc = 0; 1763cafe5635SKent Overstreet 1764cafe5635SKent Overstreet for (i = ca->sb.d; i < ca->sb.d + ca->sb.keys; i++) 1765cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1766cafe5635SKent Overstreet 1767cafe5635SKent Overstreet for (i = ca->prio_buckets; 1768cafe5635SKent Overstreet i < ca->prio_buckets + prio_buckets(ca) * 2; i++) 1769cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1770cafe5635SKent Overstreet 1771cafe5635SKent Overstreet for_each_bucket(b, ca) { 1772cafe5635SKent Overstreet c->need_gc = max(c->need_gc, bucket_gc_gen(b)); 1773cafe5635SKent Overstreet 17744fe6a816SKent Overstreet if (atomic_read(&b->pin)) 17754fe6a816SKent Overstreet continue; 17764fe6a816SKent Overstreet 17774fe6a816SKent Overstreet BUG_ON(!GC_MARK(b) && GC_SECTORS_USED(b)); 17784fe6a816SKent Overstreet 17794fe6a816SKent Overstreet if (!GC_MARK(b) || GC_MARK(b) == GC_MARK_RECLAIMABLE) 1780d44c2f9eSTang Junhui c->avail_nbuckets++; 1781cafe5635SKent Overstreet } 1782cafe5635SKent Overstreet } 1783cafe5635SKent Overstreet 1784cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1785cafe5635SKent Overstreet } 1786cafe5635SKent Overstreet 178772a44517SKent Overstreet static void bch_btree_gc(struct cache_set *c) 1788cafe5635SKent Overstreet { 1789cafe5635SKent Overstreet int ret; 1790cafe5635SKent Overstreet struct gc_stat stats; 1791cafe5635SKent Overstreet struct closure writes; 1792cafe5635SKent Overstreet struct btree_op op; 1793cafe5635SKent Overstreet uint64_t start_time = local_clock(); 179457943511SKent Overstreet 1795c37511b8SKent Overstreet trace_bcache_gc_start(c); 1796cafe5635SKent Overstreet 1797cafe5635SKent Overstreet memset(&stats, 0, sizeof(struct gc_stat)); 1798cafe5635SKent Overstreet closure_init_stack(&writes); 1799b54d6934SKent Overstreet bch_btree_op_init(&op, SHRT_MAX); 1800cafe5635SKent Overstreet 1801cafe5635SKent Overstreet btree_gc_start(c); 1802cafe5635SKent Overstreet 1803771f393eSColy Li /* if CACHE_SET_IO_DISABLE set, gc thread should stop too */ 1804a1f0358bSKent Overstreet do { 1805feac1a70SColy Li ret = bcache_btree_root(gc_root, c, &op, &writes, &stats); 1806cafe5635SKent Overstreet closure_sync(&writes); 1807c5f1e5adSKent Overstreet cond_resched(); 1808cafe5635SKent Overstreet 18095c25c4fcSTang Junhui if (ret == -EAGAIN) 18105c25c4fcSTang Junhui schedule_timeout_interruptible(msecs_to_jiffies 18115c25c4fcSTang Junhui (GC_SLEEP_MS)); 18125c25c4fcSTang Junhui else if (ret) 181346f5aa88SJoe Perches pr_warn("gc failed!\n"); 1814771f393eSColy Li } while (ret && !test_bit(CACHE_SET_IO_DISABLE, &c->flags)); 1815cafe5635SKent Overstreet 1816d44c2f9eSTang Junhui bch_btree_gc_finish(c); 181757943511SKent Overstreet wake_up_allocators(c); 181857943511SKent Overstreet 1819169ef1cfSKent Overstreet bch_time_stats_update(&c->btree_gc_time, start_time); 1820cafe5635SKent Overstreet 1821cafe5635SKent Overstreet stats.key_bytes *= sizeof(uint64_t); 1822cafe5635SKent Overstreet stats.data <<= 9; 1823d44c2f9eSTang Junhui bch_update_bucket_in_use(c, &stats); 1824cafe5635SKent Overstreet memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat)); 1825cafe5635SKent Overstreet 1826c37511b8SKent Overstreet trace_bcache_gc_end(c); 1827cafe5635SKent Overstreet 182872a44517SKent Overstreet bch_moving_gc(c); 1829cafe5635SKent Overstreet } 1830cafe5635SKent Overstreet 1831be628be0SKent Overstreet static bool gc_should_run(struct cache_set *c) 1832cafe5635SKent Overstreet { 1833a1f0358bSKent Overstreet struct cache *ca; 18346f10f7d1SColy Li unsigned int i; 183572a44517SKent Overstreet 1836be628be0SKent Overstreet for_each_cache(ca, c, i) 1837be628be0SKent Overstreet if (ca->invalidate_needs_gc) 1838be628be0SKent Overstreet return true; 183972a44517SKent Overstreet 1840be628be0SKent Overstreet if (atomic_read(&c->sectors_to_gc) < 0) 1841be628be0SKent Overstreet return true; 1842be628be0SKent Overstreet 1843be628be0SKent Overstreet return false; 1844be628be0SKent Overstreet } 1845be628be0SKent Overstreet 1846be628be0SKent Overstreet static int bch_gc_thread(void *arg) 1847be628be0SKent Overstreet { 1848be628be0SKent Overstreet struct cache_set *c = arg; 1849be628be0SKent Overstreet 1850be628be0SKent Overstreet while (1) { 1851be628be0SKent Overstreet wait_event_interruptible(c->gc_wait, 1852771f393eSColy Li kthread_should_stop() || 1853771f393eSColy Li test_bit(CACHE_SET_IO_DISABLE, &c->flags) || 1854771f393eSColy Li gc_should_run(c)); 1855be628be0SKent Overstreet 1856771f393eSColy Li if (kthread_should_stop() || 1857771f393eSColy Li test_bit(CACHE_SET_IO_DISABLE, &c->flags)) 185872a44517SKent Overstreet break; 185972a44517SKent Overstreet 1860be628be0SKent Overstreet set_gc_sectors(c); 1861be628be0SKent Overstreet bch_btree_gc(c); 186272a44517SKent Overstreet } 186372a44517SKent Overstreet 1864771f393eSColy Li wait_for_kthread_stop(); 186572a44517SKent Overstreet return 0; 186672a44517SKent Overstreet } 186772a44517SKent Overstreet 186872a44517SKent Overstreet int bch_gc_thread_start(struct cache_set *c) 186972a44517SKent Overstreet { 1870be628be0SKent Overstreet c->gc_thread = kthread_run(bch_gc_thread, c, "bcache_gc"); 18719d134117SVasyl Gomonovych return PTR_ERR_OR_ZERO(c->gc_thread); 1872cafe5635SKent Overstreet } 1873cafe5635SKent Overstreet 1874cafe5635SKent Overstreet /* Initial partial gc */ 1875cafe5635SKent Overstreet 1876487dded8SKent Overstreet static int bch_btree_check_recurse(struct btree *b, struct btree_op *op) 1877cafe5635SKent Overstreet { 187850310164SKent Overstreet int ret = 0; 187950310164SKent Overstreet struct bkey *k, *p = NULL; 1880cafe5635SKent Overstreet struct btree_iter iter; 1881cafe5635SKent Overstreet 1882487dded8SKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) 1883487dded8SKent Overstreet bch_initial_mark_key(b->c, b->level, k); 1884cafe5635SKent Overstreet 1885487dded8SKent Overstreet bch_initial_mark_key(b->c, b->level + 1, &b->key); 1886cafe5635SKent Overstreet 1887cafe5635SKent Overstreet if (b->level) { 1888c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, NULL); 1889cafe5635SKent Overstreet 189050310164SKent Overstreet do { 1891a85e968eSKent Overstreet k = bch_btree_iter_next_filter(&iter, &b->keys, 1892a85e968eSKent Overstreet bch_ptr_bad); 18937f4a59deSTang Junhui if (k) { 18942452cc89SSlava Pestov btree_node_prefetch(b, k); 18957f4a59deSTang Junhui /* 18967f4a59deSTang Junhui * initiallize c->gc_stats.nodes 18977f4a59deSTang Junhui * for incremental GC 18987f4a59deSTang Junhui */ 18997f4a59deSTang Junhui b->c->gc_stats.nodes++; 19007f4a59deSTang Junhui } 190150310164SKent Overstreet 1902cafe5635SKent Overstreet if (p) 1903feac1a70SColy Li ret = bcache_btree(check_recurse, p, b, op); 1904cafe5635SKent Overstreet 190550310164SKent Overstreet p = k; 190650310164SKent Overstreet } while (p && !ret); 1907cafe5635SKent Overstreet } 1908cafe5635SKent Overstreet 1909487dded8SKent Overstreet return ret; 1910cafe5635SKent Overstreet } 1911cafe5635SKent Overstreet 19128e710227SColy Li 19138e710227SColy Li static int bch_btree_check_thread(void *arg) 1914cafe5635SKent Overstreet { 19158e710227SColy Li int ret; 19168e710227SColy Li struct btree_check_info *info = arg; 19178e710227SColy Li struct btree_check_state *check_state = info->state; 19188e710227SColy Li struct cache_set *c = check_state->c; 19198e710227SColy Li struct btree_iter iter; 19208e710227SColy Li struct bkey *k, *p; 19218e710227SColy Li int cur_idx, prev_idx, skip_nr; 19228e710227SColy Li 19238e710227SColy Li k = p = NULL; 19248e710227SColy Li cur_idx = prev_idx = 0; 19258e710227SColy Li ret = 0; 19268e710227SColy Li 19278e710227SColy Li /* root node keys are checked before thread created */ 19288e710227SColy Li bch_btree_iter_init(&c->root->keys, &iter, NULL); 19298e710227SColy Li k = bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad); 19308e710227SColy Li BUG_ON(!k); 19318e710227SColy Li 19328e710227SColy Li p = k; 19338e710227SColy Li while (k) { 19348e710227SColy Li /* 19358e710227SColy Li * Fetch a root node key index, skip the keys which 19368e710227SColy Li * should be fetched by other threads, then check the 19378e710227SColy Li * sub-tree indexed by the fetched key. 19388e710227SColy Li */ 19398e710227SColy Li spin_lock(&check_state->idx_lock); 19408e710227SColy Li cur_idx = check_state->key_idx; 19418e710227SColy Li check_state->key_idx++; 19428e710227SColy Li spin_unlock(&check_state->idx_lock); 19438e710227SColy Li 19448e710227SColy Li skip_nr = cur_idx - prev_idx; 19458e710227SColy Li 19468e710227SColy Li while (skip_nr) { 19478e710227SColy Li k = bch_btree_iter_next_filter(&iter, 19488e710227SColy Li &c->root->keys, 19498e710227SColy Li bch_ptr_bad); 19508e710227SColy Li if (k) 19518e710227SColy Li p = k; 19528e710227SColy Li else { 19538e710227SColy Li /* 19548e710227SColy Li * No more keys to check in root node, 19558e710227SColy Li * current checking threads are enough, 19568e710227SColy Li * stop creating more. 19578e710227SColy Li */ 19588e710227SColy Li atomic_set(&check_state->enough, 1); 19598e710227SColy Li /* Update check_state->enough earlier */ 1960eb9b6666SColy Li smp_mb__after_atomic(); 19618e710227SColy Li goto out; 19628e710227SColy Li } 19638e710227SColy Li skip_nr--; 19648e710227SColy Li cond_resched(); 19658e710227SColy Li } 19668e710227SColy Li 19678e710227SColy Li if (p) { 1968c18536a7SKent Overstreet struct btree_op op; 1969cafe5635SKent Overstreet 19708e710227SColy Li btree_node_prefetch(c->root, p); 19718e710227SColy Li c->gc_stats.nodes++; 19728e710227SColy Li bch_btree_op_init(&op, 0); 19738e710227SColy Li ret = bcache_btree(check_recurse, p, c->root, &op); 19748e710227SColy Li if (ret) 19758e710227SColy Li goto out; 19768e710227SColy Li } 19778e710227SColy Li p = NULL; 19788e710227SColy Li prev_idx = cur_idx; 19798e710227SColy Li cond_resched(); 19808e710227SColy Li } 1981cafe5635SKent Overstreet 19828e710227SColy Li out: 19838e710227SColy Li info->result = ret; 19848e710227SColy Li /* update check_state->started among all CPUs */ 1985eb9b6666SColy Li smp_mb__before_atomic(); 19868e710227SColy Li if (atomic_dec_and_test(&check_state->started)) 19878e710227SColy Li wake_up(&check_state->wait); 19888e710227SColy Li 19898e710227SColy Li return ret; 19908e710227SColy Li } 19918e710227SColy Li 19928e710227SColy Li 19938e710227SColy Li 19948e710227SColy Li static int bch_btree_chkthread_nr(void) 19958e710227SColy Li { 19968e710227SColy Li int n = num_online_cpus()/2; 19978e710227SColy Li 19988e710227SColy Li if (n == 0) 19998e710227SColy Li n = 1; 20008e710227SColy Li else if (n > BCH_BTR_CHKTHREAD_MAX) 20018e710227SColy Li n = BCH_BTR_CHKTHREAD_MAX; 20028e710227SColy Li 20038e710227SColy Li return n; 20048e710227SColy Li } 20058e710227SColy Li 20068e710227SColy Li int bch_btree_check(struct cache_set *c) 20078e710227SColy Li { 20088e710227SColy Li int ret = 0; 20098e710227SColy Li int i; 20108e710227SColy Li struct bkey *k = NULL; 20118e710227SColy Li struct btree_iter iter; 20128e710227SColy Li struct btree_check_state *check_state; 20138e710227SColy Li char name[32]; 20148e710227SColy Li 20158e710227SColy Li /* check and mark root node keys */ 20168e710227SColy Li for_each_key_filter(&c->root->keys, k, &iter, bch_ptr_invalid) 20178e710227SColy Li bch_initial_mark_key(c, c->root->level, k); 20188e710227SColy Li 20198e710227SColy Li bch_initial_mark_key(c, c->root->level + 1, &c->root->key); 20208e710227SColy Li 20218e710227SColy Li if (c->root->level == 0) 20228e710227SColy Li return 0; 20238e710227SColy Li 20248e710227SColy Li check_state = kzalloc(sizeof(struct btree_check_state), GFP_KERNEL); 20258e710227SColy Li if (!check_state) 20268e710227SColy Li return -ENOMEM; 20278e710227SColy Li 20288e710227SColy Li check_state->c = c; 20298e710227SColy Li check_state->total_threads = bch_btree_chkthread_nr(); 20308e710227SColy Li check_state->key_idx = 0; 20318e710227SColy Li spin_lock_init(&check_state->idx_lock); 20328e710227SColy Li atomic_set(&check_state->started, 0); 20338e710227SColy Li atomic_set(&check_state->enough, 0); 20348e710227SColy Li init_waitqueue_head(&check_state->wait); 20358e710227SColy Li 20368e710227SColy Li /* 20378e710227SColy Li * Run multiple threads to check btree nodes in parallel, 20388e710227SColy Li * if check_state->enough is non-zero, it means current 20398e710227SColy Li * running check threads are enough, unncessary to create 20408e710227SColy Li * more. 20418e710227SColy Li */ 20428e710227SColy Li for (i = 0; i < check_state->total_threads; i++) { 20438e710227SColy Li /* fetch latest check_state->enough earlier */ 2044eb9b6666SColy Li smp_mb__before_atomic(); 20458e710227SColy Li if (atomic_read(&check_state->enough)) 20468e710227SColy Li break; 20478e710227SColy Li 20488e710227SColy Li check_state->infos[i].result = 0; 20498e710227SColy Li check_state->infos[i].state = check_state; 20508e710227SColy Li snprintf(name, sizeof(name), "bch_btrchk[%u]", i); 20518e710227SColy Li atomic_inc(&check_state->started); 20528e710227SColy Li 20538e710227SColy Li check_state->infos[i].thread = 20548e710227SColy Li kthread_run(bch_btree_check_thread, 20558e710227SColy Li &check_state->infos[i], 20568e710227SColy Li name); 20578e710227SColy Li if (IS_ERR(check_state->infos[i].thread)) { 205846f5aa88SJoe Perches pr_err("fails to run thread bch_btrchk[%d]\n", i); 20598e710227SColy Li for (--i; i >= 0; i--) 20608e710227SColy Li kthread_stop(check_state->infos[i].thread); 20618e710227SColy Li ret = -ENOMEM; 20628e710227SColy Li goto out; 20638e710227SColy Li } 20648e710227SColy Li } 20658e710227SColy Li 20668e710227SColy Li wait_event_interruptible(check_state->wait, 20678e710227SColy Li atomic_read(&check_state->started) == 0 || 20688e710227SColy Li test_bit(CACHE_SET_IO_DISABLE, &c->flags)); 20698e710227SColy Li 20708e710227SColy Li for (i = 0; i < check_state->total_threads; i++) { 20718e710227SColy Li if (check_state->infos[i].result) { 20728e710227SColy Li ret = check_state->infos[i].result; 20738e710227SColy Li goto out; 20748e710227SColy Li } 20758e710227SColy Li } 20768e710227SColy Li 20778e710227SColy Li out: 20788e710227SColy Li kfree(check_state); 20798e710227SColy Li return ret; 2080cafe5635SKent Overstreet } 2081cafe5635SKent Overstreet 20822531d9eeSKent Overstreet void bch_initial_gc_finish(struct cache_set *c) 20832531d9eeSKent Overstreet { 20842531d9eeSKent Overstreet struct cache *ca; 20852531d9eeSKent Overstreet struct bucket *b; 20866f10f7d1SColy Li unsigned int i; 20872531d9eeSKent Overstreet 20882531d9eeSKent Overstreet bch_btree_gc_finish(c); 20892531d9eeSKent Overstreet 20902531d9eeSKent Overstreet mutex_lock(&c->bucket_lock); 20912531d9eeSKent Overstreet 20922531d9eeSKent Overstreet /* 20932531d9eeSKent Overstreet * We need to put some unused buckets directly on the prio freelist in 20942531d9eeSKent Overstreet * order to get the allocator thread started - it needs freed buckets in 20952531d9eeSKent Overstreet * order to rewrite the prios and gens, and it needs to rewrite prios 20962531d9eeSKent Overstreet * and gens in order to free buckets. 20972531d9eeSKent Overstreet * 20982531d9eeSKent Overstreet * This is only safe for buckets that have no live data in them, which 20992531d9eeSKent Overstreet * there should always be some of. 21002531d9eeSKent Overstreet */ 21012531d9eeSKent Overstreet for_each_cache(ca, c, i) { 21022531d9eeSKent Overstreet for_each_bucket(b, ca) { 2103682811b3STang Junhui if (fifo_full(&ca->free[RESERVE_PRIO]) && 2104682811b3STang Junhui fifo_full(&ca->free[RESERVE_BTREE])) 21052531d9eeSKent Overstreet break; 21062531d9eeSKent Overstreet 21072531d9eeSKent Overstreet if (bch_can_invalidate_bucket(ca, b) && 21082531d9eeSKent Overstreet !GC_MARK(b)) { 21092531d9eeSKent Overstreet __bch_invalidate_one_bucket(ca, b); 2110682811b3STang Junhui if (!fifo_push(&ca->free[RESERVE_PRIO], 2111682811b3STang Junhui b - ca->buckets)) 2112682811b3STang Junhui fifo_push(&ca->free[RESERVE_BTREE], 21132531d9eeSKent Overstreet b - ca->buckets); 21142531d9eeSKent Overstreet } 21152531d9eeSKent Overstreet } 21162531d9eeSKent Overstreet } 21172531d9eeSKent Overstreet 21182531d9eeSKent Overstreet mutex_unlock(&c->bucket_lock); 21192531d9eeSKent Overstreet } 21202531d9eeSKent Overstreet 2121cafe5635SKent Overstreet /* Btree insertion */ 2122cafe5635SKent Overstreet 2123829a60b9SKent Overstreet static bool btree_insert_key(struct btree *b, struct bkey *k, 21241b207d80SKent Overstreet struct bkey *replace_key) 2125cafe5635SKent Overstreet { 21266f10f7d1SColy Li unsigned int status; 2127cafe5635SKent Overstreet 2128cafe5635SKent Overstreet BUG_ON(bkey_cmp(k, &b->key) > 0); 2129cafe5635SKent Overstreet 2130829a60b9SKent Overstreet status = bch_btree_insert_key(&b->keys, k, replace_key); 2131829a60b9SKent Overstreet if (status != BTREE_INSERT_STATUS_NO_INSERT) { 2132dc9d98d6SKent Overstreet bch_check_keys(&b->keys, "%u for %s", status, 21331b207d80SKent Overstreet replace_key ? "replace" : "insert"); 2134cafe5635SKent Overstreet 2135829a60b9SKent Overstreet trace_bcache_btree_insert_key(b, k, replace_key != NULL, 2136829a60b9SKent Overstreet status); 2137cafe5635SKent Overstreet return true; 2138829a60b9SKent Overstreet } else 2139829a60b9SKent Overstreet return false; 2140cafe5635SKent Overstreet } 2141cafe5635SKent Overstreet 214259158fdeSKent Overstreet static size_t insert_u64s_remaining(struct btree *b) 214359158fdeSKent Overstreet { 21443572324aSKent Overstreet long ret = bch_btree_keys_u64s_remaining(&b->keys); 214559158fdeSKent Overstreet 214659158fdeSKent Overstreet /* 214759158fdeSKent Overstreet * Might land in the middle of an existing extent and have to split it 214859158fdeSKent Overstreet */ 214959158fdeSKent Overstreet if (b->keys.ops->is_extents) 215059158fdeSKent Overstreet ret -= KEY_MAX_U64S; 215159158fdeSKent Overstreet 215259158fdeSKent Overstreet return max(ret, 0L); 215359158fdeSKent Overstreet } 215459158fdeSKent Overstreet 215526c949f8SKent Overstreet static bool bch_btree_insert_keys(struct btree *b, struct btree_op *op, 21561b207d80SKent Overstreet struct keylist *insert_keys, 21571b207d80SKent Overstreet struct bkey *replace_key) 2158cafe5635SKent Overstreet { 2159cafe5635SKent Overstreet bool ret = false; 2160dc9d98d6SKent Overstreet int oldsize = bch_count_data(&b->keys); 2161cafe5635SKent Overstreet 216226c949f8SKent Overstreet while (!bch_keylist_empty(insert_keys)) { 2163c2f95ae2SKent Overstreet struct bkey *k = insert_keys->keys; 216426c949f8SKent Overstreet 216559158fdeSKent Overstreet if (bkey_u64s(k) > insert_u64s_remaining(b)) 2166403b6cdeSKent Overstreet break; 2167403b6cdeSKent Overstreet 2168403b6cdeSKent Overstreet if (bkey_cmp(k, &b->key) <= 0) { 21693a3b6a4eSKent Overstreet if (!b->level) 21703a3b6a4eSKent Overstreet bkey_put(b->c, k); 217126c949f8SKent Overstreet 2172829a60b9SKent Overstreet ret |= btree_insert_key(b, k, replace_key); 217326c949f8SKent Overstreet bch_keylist_pop_front(insert_keys); 217426c949f8SKent Overstreet } else if (bkey_cmp(&START_KEY(k), &b->key) < 0) { 217526c949f8SKent Overstreet BKEY_PADDED(key) temp; 2176c2f95ae2SKent Overstreet bkey_copy(&temp.key, insert_keys->keys); 217726c949f8SKent Overstreet 217826c949f8SKent Overstreet bch_cut_back(&b->key, &temp.key); 2179c2f95ae2SKent Overstreet bch_cut_front(&b->key, insert_keys->keys); 218026c949f8SKent Overstreet 2181829a60b9SKent Overstreet ret |= btree_insert_key(b, &temp.key, replace_key); 218226c949f8SKent Overstreet break; 218326c949f8SKent Overstreet } else { 218426c949f8SKent Overstreet break; 218526c949f8SKent Overstreet } 2186cafe5635SKent Overstreet } 2187cafe5635SKent Overstreet 2188829a60b9SKent Overstreet if (!ret) 2189829a60b9SKent Overstreet op->insert_collision = true; 2190829a60b9SKent Overstreet 2191403b6cdeSKent Overstreet BUG_ON(!bch_keylist_empty(insert_keys) && b->level); 2192403b6cdeSKent Overstreet 2193dc9d98d6SKent Overstreet BUG_ON(bch_count_data(&b->keys) < oldsize); 2194cafe5635SKent Overstreet return ret; 2195cafe5635SKent Overstreet } 2196cafe5635SKent Overstreet 219726c949f8SKent Overstreet static int btree_split(struct btree *b, struct btree_op *op, 219826c949f8SKent Overstreet struct keylist *insert_keys, 21991b207d80SKent Overstreet struct bkey *replace_key) 2200cafe5635SKent Overstreet { 2201d6fd3b11SKent Overstreet bool split; 2202cafe5635SKent Overstreet struct btree *n1, *n2 = NULL, *n3 = NULL; 2203cafe5635SKent Overstreet uint64_t start_time = local_clock(); 2204b54d6934SKent Overstreet struct closure cl; 220517e21a9fSKent Overstreet struct keylist parent_keys; 2206b54d6934SKent Overstreet 2207b54d6934SKent Overstreet closure_init_stack(&cl); 220817e21a9fSKent Overstreet bch_keylist_init(&parent_keys); 2209cafe5635SKent Overstreet 22100a63b66dSKent Overstreet if (btree_check_reserve(b, op)) { 22110a63b66dSKent Overstreet if (!b->level) 221278365411SKent Overstreet return -EINTR; 22130a63b66dSKent Overstreet else 22140a63b66dSKent Overstreet WARN(1, "insufficient reserve for split\n"); 22150a63b66dSKent Overstreet } 221678365411SKent Overstreet 22170a63b66dSKent Overstreet n1 = btree_node_alloc_replacement(b, op); 2218cafe5635SKent Overstreet if (IS_ERR(n1)) 2219cafe5635SKent Overstreet goto err; 2220cafe5635SKent Overstreet 2221ee811287SKent Overstreet split = set_blocks(btree_bset_first(n1), 2222ee811287SKent Overstreet block_bytes(n1->c)) > (btree_blocks(b) * 4) / 5; 2223cafe5635SKent Overstreet 2224cafe5635SKent Overstreet if (split) { 22256f10f7d1SColy Li unsigned int keys = 0; 2226cafe5635SKent Overstreet 2227ee811287SKent Overstreet trace_bcache_btree_node_split(b, btree_bset_first(n1)->keys); 2228c37511b8SKent Overstreet 22292452cc89SSlava Pestov n2 = bch_btree_node_alloc(b->c, op, b->level, b->parent); 2230cafe5635SKent Overstreet if (IS_ERR(n2)) 2231cafe5635SKent Overstreet goto err_free1; 2232cafe5635SKent Overstreet 2233d6fd3b11SKent Overstreet if (!b->parent) { 22342452cc89SSlava Pestov n3 = bch_btree_node_alloc(b->c, op, b->level + 1, NULL); 2235cafe5635SKent Overstreet if (IS_ERR(n3)) 2236cafe5635SKent Overstreet goto err_free2; 2237cafe5635SKent Overstreet } 2238cafe5635SKent Overstreet 22392a285686SKent Overstreet mutex_lock(&n1->write_lock); 22402a285686SKent Overstreet mutex_lock(&n2->write_lock); 22412a285686SKent Overstreet 22421b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 2243cafe5635SKent Overstreet 2244d6fd3b11SKent Overstreet /* 2245d6fd3b11SKent Overstreet * Has to be a linear search because we don't have an auxiliary 2246cafe5635SKent Overstreet * search tree yet 2247cafe5635SKent Overstreet */ 2248cafe5635SKent Overstreet 2249ee811287SKent Overstreet while (keys < (btree_bset_first(n1)->keys * 3) / 5) 2250ee811287SKent Overstreet keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), 2251fafff81cSKent Overstreet keys)); 2252cafe5635SKent Overstreet 2253fafff81cSKent Overstreet bkey_copy_key(&n1->key, 2254ee811287SKent Overstreet bset_bkey_idx(btree_bset_first(n1), keys)); 2255ee811287SKent Overstreet keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), keys)); 2256cafe5635SKent Overstreet 2257ee811287SKent Overstreet btree_bset_first(n2)->keys = btree_bset_first(n1)->keys - keys; 2258ee811287SKent Overstreet btree_bset_first(n1)->keys = keys; 2259cafe5635SKent Overstreet 2260ee811287SKent Overstreet memcpy(btree_bset_first(n2)->start, 2261ee811287SKent Overstreet bset_bkey_last(btree_bset_first(n1)), 2262ee811287SKent Overstreet btree_bset_first(n2)->keys * sizeof(uint64_t)); 2263cafe5635SKent Overstreet 2264cafe5635SKent Overstreet bkey_copy_key(&n2->key, &b->key); 2265cafe5635SKent Overstreet 226617e21a9fSKent Overstreet bch_keylist_add(&parent_keys, &n2->key); 2267b54d6934SKent Overstreet bch_btree_node_write(n2, &cl); 22682a285686SKent Overstreet mutex_unlock(&n2->write_lock); 2269cafe5635SKent Overstreet rw_unlock(true, n2); 2270c37511b8SKent Overstreet } else { 2271ee811287SKent Overstreet trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys); 2272c37511b8SKent Overstreet 22732a285686SKent Overstreet mutex_lock(&n1->write_lock); 22741b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 2275c37511b8SKent Overstreet } 2276cafe5635SKent Overstreet 227717e21a9fSKent Overstreet bch_keylist_add(&parent_keys, &n1->key); 2278b54d6934SKent Overstreet bch_btree_node_write(n1, &cl); 22792a285686SKent Overstreet mutex_unlock(&n1->write_lock); 2280cafe5635SKent Overstreet 2281cafe5635SKent Overstreet if (n3) { 2282d6fd3b11SKent Overstreet /* Depth increases, make a new root */ 22832a285686SKent Overstreet mutex_lock(&n3->write_lock); 2284cafe5635SKent Overstreet bkey_copy_key(&n3->key, &MAX_KEY); 228517e21a9fSKent Overstreet bch_btree_insert_keys(n3, op, &parent_keys, NULL); 2286b54d6934SKent Overstreet bch_btree_node_write(n3, &cl); 22872a285686SKent Overstreet mutex_unlock(&n3->write_lock); 2288cafe5635SKent Overstreet 2289b54d6934SKent Overstreet closure_sync(&cl); 2290cafe5635SKent Overstreet bch_btree_set_root(n3); 2291cafe5635SKent Overstreet rw_unlock(true, n3); 2292d6fd3b11SKent Overstreet } else if (!b->parent) { 2293d6fd3b11SKent Overstreet /* Root filled up but didn't need to be split */ 2294b54d6934SKent Overstreet closure_sync(&cl); 2295cafe5635SKent Overstreet bch_btree_set_root(n1); 2296cafe5635SKent Overstreet } else { 229717e21a9fSKent Overstreet /* Split a non root node */ 2298b54d6934SKent Overstreet closure_sync(&cl); 229917e21a9fSKent Overstreet make_btree_freeing_key(b, parent_keys.top); 230017e21a9fSKent Overstreet bch_keylist_push(&parent_keys); 230117e21a9fSKent Overstreet 230217e21a9fSKent Overstreet bch_btree_insert_node(b->parent, op, &parent_keys, NULL, NULL); 230317e21a9fSKent Overstreet BUG_ON(!bch_keylist_empty(&parent_keys)); 2304cafe5635SKent Overstreet } 2305cafe5635SKent Overstreet 230605335cffSKent Overstreet btree_node_free(b); 2307cafe5635SKent Overstreet rw_unlock(true, n1); 2308cafe5635SKent Overstreet 2309169ef1cfSKent Overstreet bch_time_stats_update(&b->c->btree_split_time, start_time); 2310cafe5635SKent Overstreet 2311cafe5635SKent Overstreet return 0; 2312cafe5635SKent Overstreet err_free2: 23135f5837d2SKent Overstreet bkey_put(b->c, &n2->key); 2314e8e1d468SKent Overstreet btree_node_free(n2); 2315cafe5635SKent Overstreet rw_unlock(true, n2); 2316cafe5635SKent Overstreet err_free1: 23175f5837d2SKent Overstreet bkey_put(b->c, &n1->key); 2318e8e1d468SKent Overstreet btree_node_free(n1); 2319cafe5635SKent Overstreet rw_unlock(true, n1); 2320cafe5635SKent Overstreet err: 23210a63b66dSKent Overstreet WARN(1, "bcache: btree split failed (level %u)", b->level); 23225f5837d2SKent Overstreet 2323cafe5635SKent Overstreet if (n3 == ERR_PTR(-EAGAIN) || 2324cafe5635SKent Overstreet n2 == ERR_PTR(-EAGAIN) || 2325cafe5635SKent Overstreet n1 == ERR_PTR(-EAGAIN)) 2326cafe5635SKent Overstreet return -EAGAIN; 2327cafe5635SKent Overstreet 2328cafe5635SKent Overstreet return -ENOMEM; 2329cafe5635SKent Overstreet } 2330cafe5635SKent Overstreet 233126c949f8SKent Overstreet static int bch_btree_insert_node(struct btree *b, struct btree_op *op, 2332c18536a7SKent Overstreet struct keylist *insert_keys, 23331b207d80SKent Overstreet atomic_t *journal_ref, 23341b207d80SKent Overstreet struct bkey *replace_key) 233526c949f8SKent Overstreet { 23362a285686SKent Overstreet struct closure cl; 23372a285686SKent Overstreet 23381b207d80SKent Overstreet BUG_ON(b->level && replace_key); 23391b207d80SKent Overstreet 23402a285686SKent Overstreet closure_init_stack(&cl); 23412a285686SKent Overstreet 23422a285686SKent Overstreet mutex_lock(&b->write_lock); 23432a285686SKent Overstreet 23442a285686SKent Overstreet if (write_block(b) != btree_bset_last(b) && 23452a285686SKent Overstreet b->keys.last_set_unwritten) 23462a285686SKent Overstreet bch_btree_init_next(b); /* just wrote a set */ 23472a285686SKent Overstreet 234859158fdeSKent Overstreet if (bch_keylist_nkeys(insert_keys) > insert_u64s_remaining(b)) { 23492a285686SKent Overstreet mutex_unlock(&b->write_lock); 23502a285686SKent Overstreet goto split; 23512a285686SKent Overstreet } 23522a285686SKent Overstreet 23532a285686SKent Overstreet BUG_ON(write_block(b) != btree_bset_last(b)); 23542a285686SKent Overstreet 23552a285686SKent Overstreet if (bch_btree_insert_keys(b, op, insert_keys, replace_key)) { 23562a285686SKent Overstreet if (!b->level) 23572a285686SKent Overstreet bch_btree_leaf_dirty(b, journal_ref); 23582a285686SKent Overstreet else 23592a285686SKent Overstreet bch_btree_node_write(b, &cl); 23602a285686SKent Overstreet } 23612a285686SKent Overstreet 23622a285686SKent Overstreet mutex_unlock(&b->write_lock); 23632a285686SKent Overstreet 23642a285686SKent Overstreet /* wait for btree node write if necessary, after unlock */ 23652a285686SKent Overstreet closure_sync(&cl); 23662a285686SKent Overstreet 23672a285686SKent Overstreet return 0; 23682a285686SKent Overstreet split: 236926c949f8SKent Overstreet if (current->bio_list) { 237026c949f8SKent Overstreet op->lock = b->c->root->level + 1; 237117e21a9fSKent Overstreet return -EAGAIN; 237226c949f8SKent Overstreet } else if (op->lock <= b->c->root->level) { 237326c949f8SKent Overstreet op->lock = b->c->root->level + 1; 237417e21a9fSKent Overstreet return -EINTR; 237526c949f8SKent Overstreet } else { 237617e21a9fSKent Overstreet /* Invalidated all iterators */ 23773b3e9e50SKent Overstreet int ret = btree_split(b, op, insert_keys, replace_key); 23783b3e9e50SKent Overstreet 23792a285686SKent Overstreet if (bch_keylist_empty(insert_keys)) 238017e21a9fSKent Overstreet return 0; 23812a285686SKent Overstreet else if (!ret) 23822a285686SKent Overstreet return -EINTR; 23832a285686SKent Overstreet return ret; 238417e21a9fSKent Overstreet } 238526c949f8SKent Overstreet } 238626c949f8SKent Overstreet 2387e7c590ebSKent Overstreet int bch_btree_insert_check_key(struct btree *b, struct btree_op *op, 2388e7c590ebSKent Overstreet struct bkey *check_key) 2389e7c590ebSKent Overstreet { 2390e7c590ebSKent Overstreet int ret = -EINTR; 2391e7c590ebSKent Overstreet uint64_t btree_ptr = b->key.ptr[0]; 2392e7c590ebSKent Overstreet unsigned long seq = b->seq; 2393e7c590ebSKent Overstreet struct keylist insert; 2394e7c590ebSKent Overstreet bool upgrade = op->lock == -1; 2395e7c590ebSKent Overstreet 2396e7c590ebSKent Overstreet bch_keylist_init(&insert); 2397e7c590ebSKent Overstreet 2398e7c590ebSKent Overstreet if (upgrade) { 2399e7c590ebSKent Overstreet rw_unlock(false, b); 2400e7c590ebSKent Overstreet rw_lock(true, b, b->level); 2401e7c590ebSKent Overstreet 2402e7c590ebSKent Overstreet if (b->key.ptr[0] != btree_ptr || 24032ef9ccbfSZheng Liu b->seq != seq + 1) { 24042ef9ccbfSZheng Liu op->lock = b->level; 2405e7c590ebSKent Overstreet goto out; 2406e7c590ebSKent Overstreet } 24072ef9ccbfSZheng Liu } 2408e7c590ebSKent Overstreet 2409e7c590ebSKent Overstreet SET_KEY_PTRS(check_key, 1); 2410e7c590ebSKent Overstreet get_random_bytes(&check_key->ptr[0], sizeof(uint64_t)); 2411e7c590ebSKent Overstreet 2412e7c590ebSKent Overstreet SET_PTR_DEV(check_key, 0, PTR_CHECK_DEV); 2413e7c590ebSKent Overstreet 2414e7c590ebSKent Overstreet bch_keylist_add(&insert, check_key); 2415e7c590ebSKent Overstreet 24161b207d80SKent Overstreet ret = bch_btree_insert_node(b, op, &insert, NULL, NULL); 2417e7c590ebSKent Overstreet 2418e7c590ebSKent Overstreet BUG_ON(!ret && !bch_keylist_empty(&insert)); 2419e7c590ebSKent Overstreet out: 2420e7c590ebSKent Overstreet if (upgrade) 2421e7c590ebSKent Overstreet downgrade_write(&b->lock); 2422e7c590ebSKent Overstreet return ret; 2423e7c590ebSKent Overstreet } 2424e7c590ebSKent Overstreet 2425cc7b8819SKent Overstreet struct btree_insert_op { 2426cc7b8819SKent Overstreet struct btree_op op; 2427cc7b8819SKent Overstreet struct keylist *keys; 2428cc7b8819SKent Overstreet atomic_t *journal_ref; 2429cc7b8819SKent Overstreet struct bkey *replace_key; 2430cc7b8819SKent Overstreet }; 2431cc7b8819SKent Overstreet 243208239ca2SWei Yongjun static int btree_insert_fn(struct btree_op *b_op, struct btree *b) 2433cafe5635SKent Overstreet { 2434cc7b8819SKent Overstreet struct btree_insert_op *op = container_of(b_op, 2435cc7b8819SKent Overstreet struct btree_insert_op, op); 2436403b6cdeSKent Overstreet 2437cc7b8819SKent Overstreet int ret = bch_btree_insert_node(b, &op->op, op->keys, 2438cc7b8819SKent Overstreet op->journal_ref, op->replace_key); 2439cc7b8819SKent Overstreet if (ret && !bch_keylist_empty(op->keys)) 2440cc7b8819SKent Overstreet return ret; 2441cc7b8819SKent Overstreet else 2442cc7b8819SKent Overstreet return MAP_DONE; 2443cafe5635SKent Overstreet } 2444cafe5635SKent Overstreet 2445cc7b8819SKent Overstreet int bch_btree_insert(struct cache_set *c, struct keylist *keys, 2446cc7b8819SKent Overstreet atomic_t *journal_ref, struct bkey *replace_key) 2447cafe5635SKent Overstreet { 2448cc7b8819SKent Overstreet struct btree_insert_op op; 2449cafe5635SKent Overstreet int ret = 0; 2450cafe5635SKent Overstreet 2451cc7b8819SKent Overstreet BUG_ON(current->bio_list); 24524f3d4014SKent Overstreet BUG_ON(bch_keylist_empty(keys)); 2453cafe5635SKent Overstreet 2454cc7b8819SKent Overstreet bch_btree_op_init(&op.op, 0); 2455cc7b8819SKent Overstreet op.keys = keys; 2456cc7b8819SKent Overstreet op.journal_ref = journal_ref; 2457cc7b8819SKent Overstreet op.replace_key = replace_key; 2458cafe5635SKent Overstreet 2459cc7b8819SKent Overstreet while (!ret && !bch_keylist_empty(keys)) { 2460cc7b8819SKent Overstreet op.op.lock = 0; 2461cc7b8819SKent Overstreet ret = bch_btree_map_leaf_nodes(&op.op, c, 2462cc7b8819SKent Overstreet &START_KEY(keys->keys), 2463cc7b8819SKent Overstreet btree_insert_fn); 2464cc7b8819SKent Overstreet } 2465cc7b8819SKent Overstreet 2466cc7b8819SKent Overstreet if (ret) { 2467cafe5635SKent Overstreet struct bkey *k; 2468cafe5635SKent Overstreet 246946f5aa88SJoe Perches pr_err("error %i\n", ret); 2470cafe5635SKent Overstreet 24714f3d4014SKent Overstreet while ((k = bch_keylist_pop(keys))) 24723a3b6a4eSKent Overstreet bkey_put(c, k); 2473cc7b8819SKent Overstreet } else if (op.op.insert_collision) 2474cc7b8819SKent Overstreet ret = -ESRCH; 24756054c6d4SKent Overstreet 2476cafe5635SKent Overstreet return ret; 2477cafe5635SKent Overstreet } 2478cafe5635SKent Overstreet 2479cafe5635SKent Overstreet void bch_btree_set_root(struct btree *b) 2480cafe5635SKent Overstreet { 24816f10f7d1SColy Li unsigned int i; 2482e49c7c37SKent Overstreet struct closure cl; 2483e49c7c37SKent Overstreet 2484e49c7c37SKent Overstreet closure_init_stack(&cl); 2485cafe5635SKent Overstreet 2486c37511b8SKent Overstreet trace_bcache_btree_set_root(b); 2487c37511b8SKent Overstreet 2488cafe5635SKent Overstreet BUG_ON(!b->written); 2489cafe5635SKent Overstreet 2490cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) 2491cafe5635SKent Overstreet BUG_ON(PTR_BUCKET(b->c, &b->key, i)->prio != BTREE_PRIO); 2492cafe5635SKent Overstreet 2493cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 2494cafe5635SKent Overstreet list_del_init(&b->list); 2495cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 2496cafe5635SKent Overstreet 2497cafe5635SKent Overstreet b->c->root = b; 2498cafe5635SKent Overstreet 2499e49c7c37SKent Overstreet bch_journal_meta(b->c, &cl); 2500e49c7c37SKent Overstreet closure_sync(&cl); 2501cafe5635SKent Overstreet } 2502cafe5635SKent Overstreet 250348dad8baSKent Overstreet /* Map across nodes or keys */ 250448dad8baSKent Overstreet 250548dad8baSKent Overstreet static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op, 250648dad8baSKent Overstreet struct bkey *from, 250748dad8baSKent Overstreet btree_map_nodes_fn *fn, int flags) 250848dad8baSKent Overstreet { 250948dad8baSKent Overstreet int ret = MAP_CONTINUE; 251048dad8baSKent Overstreet 251148dad8baSKent Overstreet if (b->level) { 251248dad8baSKent Overstreet struct bkey *k; 251348dad8baSKent Overstreet struct btree_iter iter; 251448dad8baSKent Overstreet 2515c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, from); 251648dad8baSKent Overstreet 2517a85e968eSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, &b->keys, 251848dad8baSKent Overstreet bch_ptr_bad))) { 2519feac1a70SColy Li ret = bcache_btree(map_nodes_recurse, k, b, 252048dad8baSKent Overstreet op, from, fn, flags); 252148dad8baSKent Overstreet from = NULL; 252248dad8baSKent Overstreet 252348dad8baSKent Overstreet if (ret != MAP_CONTINUE) 252448dad8baSKent Overstreet return ret; 252548dad8baSKent Overstreet } 252648dad8baSKent Overstreet } 252748dad8baSKent Overstreet 252848dad8baSKent Overstreet if (!b->level || flags == MAP_ALL_NODES) 252948dad8baSKent Overstreet ret = fn(op, b); 253048dad8baSKent Overstreet 253148dad8baSKent Overstreet return ret; 253248dad8baSKent Overstreet } 253348dad8baSKent Overstreet 253448dad8baSKent Overstreet int __bch_btree_map_nodes(struct btree_op *op, struct cache_set *c, 253548dad8baSKent Overstreet struct bkey *from, btree_map_nodes_fn *fn, int flags) 253648dad8baSKent Overstreet { 2537feac1a70SColy Li return bcache_btree_root(map_nodes_recurse, c, op, from, fn, flags); 253848dad8baSKent Overstreet } 253948dad8baSKent Overstreet 2540253a99d9SColy Li int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op, 254148dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, 254248dad8baSKent Overstreet int flags) 254348dad8baSKent Overstreet { 254448dad8baSKent Overstreet int ret = MAP_CONTINUE; 254548dad8baSKent Overstreet struct bkey *k; 254648dad8baSKent Overstreet struct btree_iter iter; 254748dad8baSKent Overstreet 2548c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, from); 254948dad8baSKent Overstreet 2550a85e968eSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) { 255148dad8baSKent Overstreet ret = !b->level 255248dad8baSKent Overstreet ? fn(op, b, k) 2553feac1a70SColy Li : bcache_btree(map_keys_recurse, k, 2554feac1a70SColy Li b, op, from, fn, flags); 255548dad8baSKent Overstreet from = NULL; 255648dad8baSKent Overstreet 255748dad8baSKent Overstreet if (ret != MAP_CONTINUE) 255848dad8baSKent Overstreet return ret; 255948dad8baSKent Overstreet } 256048dad8baSKent Overstreet 256148dad8baSKent Overstreet if (!b->level && (flags & MAP_END_KEY)) 256248dad8baSKent Overstreet ret = fn(op, b, &KEY(KEY_INODE(&b->key), 256348dad8baSKent Overstreet KEY_OFFSET(&b->key), 0)); 256448dad8baSKent Overstreet 256548dad8baSKent Overstreet return ret; 256648dad8baSKent Overstreet } 256748dad8baSKent Overstreet 256848dad8baSKent Overstreet int bch_btree_map_keys(struct btree_op *op, struct cache_set *c, 256948dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, int flags) 257048dad8baSKent Overstreet { 2571feac1a70SColy Li return bcache_btree_root(map_keys_recurse, c, op, from, fn, flags); 257248dad8baSKent Overstreet } 257348dad8baSKent Overstreet 2574cafe5635SKent Overstreet /* Keybuf code */ 2575cafe5635SKent Overstreet 2576cafe5635SKent Overstreet static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r) 2577cafe5635SKent Overstreet { 2578cafe5635SKent Overstreet /* Overlapping keys compare equal */ 2579cafe5635SKent Overstreet if (bkey_cmp(&l->key, &START_KEY(&r->key)) <= 0) 2580cafe5635SKent Overstreet return -1; 2581cafe5635SKent Overstreet if (bkey_cmp(&START_KEY(&l->key), &r->key) >= 0) 2582cafe5635SKent Overstreet return 1; 2583cafe5635SKent Overstreet return 0; 2584cafe5635SKent Overstreet } 2585cafe5635SKent Overstreet 2586cafe5635SKent Overstreet static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l, 2587cafe5635SKent Overstreet struct keybuf_key *r) 2588cafe5635SKent Overstreet { 2589cafe5635SKent Overstreet return clamp_t(int64_t, bkey_cmp(&l->key, &r->key), -1, 1); 2590cafe5635SKent Overstreet } 2591cafe5635SKent Overstreet 259248dad8baSKent Overstreet struct refill { 259348dad8baSKent Overstreet struct btree_op op; 25946f10f7d1SColy Li unsigned int nr_found; 259548dad8baSKent Overstreet struct keybuf *buf; 259648dad8baSKent Overstreet struct bkey *end; 259748dad8baSKent Overstreet keybuf_pred_fn *pred; 259848dad8baSKent Overstreet }; 259948dad8baSKent Overstreet 260048dad8baSKent Overstreet static int refill_keybuf_fn(struct btree_op *op, struct btree *b, 260148dad8baSKent Overstreet struct bkey *k) 2602cafe5635SKent Overstreet { 260348dad8baSKent Overstreet struct refill *refill = container_of(op, struct refill, op); 260448dad8baSKent Overstreet struct keybuf *buf = refill->buf; 260548dad8baSKent Overstreet int ret = MAP_CONTINUE; 2606cafe5635SKent Overstreet 26072d6cb6edSTang Junhui if (bkey_cmp(k, refill->end) > 0) { 260848dad8baSKent Overstreet ret = MAP_DONE; 260948dad8baSKent Overstreet goto out; 2610cafe5635SKent Overstreet } 2611cafe5635SKent Overstreet 261248dad8baSKent Overstreet if (!KEY_SIZE(k)) /* end key */ 261348dad8baSKent Overstreet goto out; 2614cafe5635SKent Overstreet 261548dad8baSKent Overstreet if (refill->pred(buf, k)) { 2616cafe5635SKent Overstreet struct keybuf_key *w; 2617cafe5635SKent Overstreet 2618cafe5635SKent Overstreet spin_lock(&buf->lock); 2619cafe5635SKent Overstreet 2620cafe5635SKent Overstreet w = array_alloc(&buf->freelist); 262148dad8baSKent Overstreet if (!w) { 262248dad8baSKent Overstreet spin_unlock(&buf->lock); 262348dad8baSKent Overstreet return MAP_DONE; 262448dad8baSKent Overstreet } 2625cafe5635SKent Overstreet 2626cafe5635SKent Overstreet w->private = NULL; 2627cafe5635SKent Overstreet bkey_copy(&w->key, k); 2628cafe5635SKent Overstreet 2629cafe5635SKent Overstreet if (RB_INSERT(&buf->keys, w, node, keybuf_cmp)) 2630cafe5635SKent Overstreet array_free(&buf->freelist, w); 263148a915a8SKent Overstreet else 263248a915a8SKent Overstreet refill->nr_found++; 2633cafe5635SKent Overstreet 263448dad8baSKent Overstreet if (array_freelist_empty(&buf->freelist)) 263548dad8baSKent Overstreet ret = MAP_DONE; 263648dad8baSKent Overstreet 2637cafe5635SKent Overstreet spin_unlock(&buf->lock); 2638cafe5635SKent Overstreet } 263948dad8baSKent Overstreet out: 264048dad8baSKent Overstreet buf->last_scanned = *k; 264148dad8baSKent Overstreet return ret; 2642cafe5635SKent Overstreet } 2643cafe5635SKent Overstreet 2644cafe5635SKent Overstreet void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf, 264572c27061SKent Overstreet struct bkey *end, keybuf_pred_fn *pred) 2646cafe5635SKent Overstreet { 2647cafe5635SKent Overstreet struct bkey start = buf->last_scanned; 264848dad8baSKent Overstreet struct refill refill; 2649cafe5635SKent Overstreet 2650cafe5635SKent Overstreet cond_resched(); 2651cafe5635SKent Overstreet 2652b54d6934SKent Overstreet bch_btree_op_init(&refill.op, -1); 265348a915a8SKent Overstreet refill.nr_found = 0; 265448dad8baSKent Overstreet refill.buf = buf; 265548dad8baSKent Overstreet refill.end = end; 265648dad8baSKent Overstreet refill.pred = pred; 265748dad8baSKent Overstreet 265848dad8baSKent Overstreet bch_btree_map_keys(&refill.op, c, &buf->last_scanned, 265948dad8baSKent Overstreet refill_keybuf_fn, MAP_END_KEY); 2660cafe5635SKent Overstreet 266148a915a8SKent Overstreet trace_bcache_keyscan(refill.nr_found, 2662cafe5635SKent Overstreet KEY_INODE(&start), KEY_OFFSET(&start), 266348a915a8SKent Overstreet KEY_INODE(&buf->last_scanned), 266448a915a8SKent Overstreet KEY_OFFSET(&buf->last_scanned)); 2665cafe5635SKent Overstreet 2666cafe5635SKent Overstreet spin_lock(&buf->lock); 2667cafe5635SKent Overstreet 2668cafe5635SKent Overstreet if (!RB_EMPTY_ROOT(&buf->keys)) { 2669cafe5635SKent Overstreet struct keybuf_key *w; 26701fae7cf0SColy Li 2671cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2672cafe5635SKent Overstreet buf->start = START_KEY(&w->key); 2673cafe5635SKent Overstreet 2674cafe5635SKent Overstreet w = RB_LAST(&buf->keys, struct keybuf_key, node); 2675cafe5635SKent Overstreet buf->end = w->key; 2676cafe5635SKent Overstreet } else { 2677cafe5635SKent Overstreet buf->start = MAX_KEY; 2678cafe5635SKent Overstreet buf->end = MAX_KEY; 2679cafe5635SKent Overstreet } 2680cafe5635SKent Overstreet 2681cafe5635SKent Overstreet spin_unlock(&buf->lock); 2682cafe5635SKent Overstreet } 2683cafe5635SKent Overstreet 2684cafe5635SKent Overstreet static void __bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2685cafe5635SKent Overstreet { 2686cafe5635SKent Overstreet rb_erase(&w->node, &buf->keys); 2687cafe5635SKent Overstreet array_free(&buf->freelist, w); 2688cafe5635SKent Overstreet } 2689cafe5635SKent Overstreet 2690cafe5635SKent Overstreet void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2691cafe5635SKent Overstreet { 2692cafe5635SKent Overstreet spin_lock(&buf->lock); 2693cafe5635SKent Overstreet __bch_keybuf_del(buf, w); 2694cafe5635SKent Overstreet spin_unlock(&buf->lock); 2695cafe5635SKent Overstreet } 2696cafe5635SKent Overstreet 2697cafe5635SKent Overstreet bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start, 2698cafe5635SKent Overstreet struct bkey *end) 2699cafe5635SKent Overstreet { 2700cafe5635SKent Overstreet bool ret = false; 2701cafe5635SKent Overstreet struct keybuf_key *p, *w, s; 27021fae7cf0SColy Li 2703cafe5635SKent Overstreet s.key = *start; 2704cafe5635SKent Overstreet 2705cafe5635SKent Overstreet if (bkey_cmp(end, &buf->start) <= 0 || 2706cafe5635SKent Overstreet bkey_cmp(start, &buf->end) >= 0) 2707cafe5635SKent Overstreet return false; 2708cafe5635SKent Overstreet 2709cafe5635SKent Overstreet spin_lock(&buf->lock); 2710cafe5635SKent Overstreet w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp); 2711cafe5635SKent Overstreet 2712cafe5635SKent Overstreet while (w && bkey_cmp(&START_KEY(&w->key), end) < 0) { 2713cafe5635SKent Overstreet p = w; 2714cafe5635SKent Overstreet w = RB_NEXT(w, node); 2715cafe5635SKent Overstreet 2716cafe5635SKent Overstreet if (p->private) 2717cafe5635SKent Overstreet ret = true; 2718cafe5635SKent Overstreet else 2719cafe5635SKent Overstreet __bch_keybuf_del(buf, p); 2720cafe5635SKent Overstreet } 2721cafe5635SKent Overstreet 2722cafe5635SKent Overstreet spin_unlock(&buf->lock); 2723cafe5635SKent Overstreet return ret; 2724cafe5635SKent Overstreet } 2725cafe5635SKent Overstreet 2726cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next(struct keybuf *buf) 2727cafe5635SKent Overstreet { 2728cafe5635SKent Overstreet struct keybuf_key *w; 27291fae7cf0SColy Li 2730cafe5635SKent Overstreet spin_lock(&buf->lock); 2731cafe5635SKent Overstreet 2732cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2733cafe5635SKent Overstreet 2734cafe5635SKent Overstreet while (w && w->private) 2735cafe5635SKent Overstreet w = RB_NEXT(w, node); 2736cafe5635SKent Overstreet 2737cafe5635SKent Overstreet if (w) 2738cafe5635SKent Overstreet w->private = ERR_PTR(-EINTR); 2739cafe5635SKent Overstreet 2740cafe5635SKent Overstreet spin_unlock(&buf->lock); 2741cafe5635SKent Overstreet return w; 2742cafe5635SKent Overstreet } 2743cafe5635SKent Overstreet 2744cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c, 2745cafe5635SKent Overstreet struct keybuf *buf, 274672c27061SKent Overstreet struct bkey *end, 274772c27061SKent Overstreet keybuf_pred_fn *pred) 2748cafe5635SKent Overstreet { 2749cafe5635SKent Overstreet struct keybuf_key *ret; 2750cafe5635SKent Overstreet 2751cafe5635SKent Overstreet while (1) { 2752cafe5635SKent Overstreet ret = bch_keybuf_next(buf); 2753cafe5635SKent Overstreet if (ret) 2754cafe5635SKent Overstreet break; 2755cafe5635SKent Overstreet 2756cafe5635SKent Overstreet if (bkey_cmp(&buf->last_scanned, end) >= 0) { 275746f5aa88SJoe Perches pr_debug("scan finished\n"); 2758cafe5635SKent Overstreet break; 2759cafe5635SKent Overstreet } 2760cafe5635SKent Overstreet 276172c27061SKent Overstreet bch_refill_keybuf(c, buf, end, pred); 2762cafe5635SKent Overstreet } 2763cafe5635SKent Overstreet 2764cafe5635SKent Overstreet return ret; 2765cafe5635SKent Overstreet } 2766cafe5635SKent Overstreet 276772c27061SKent Overstreet void bch_keybuf_init(struct keybuf *buf) 2768cafe5635SKent Overstreet { 2769cafe5635SKent Overstreet buf->last_scanned = MAX_KEY; 2770cafe5635SKent Overstreet buf->keys = RB_ROOT; 2771cafe5635SKent Overstreet 2772cafe5635SKent Overstreet spin_lock_init(&buf->lock); 2773cafe5635SKent Overstreet array_allocator_init(&buf->freelist); 2774cafe5635SKent Overstreet } 2775