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 /* 105df8e8970SKent Overstreet * These macros are for recursing down the btree - they handle the details of 106df8e8970SKent Overstreet * locking and looking up nodes in the cache for you. They're best treated as 107df8e8970SKent Overstreet * mere syntax when reading code that uses them. 108df8e8970SKent Overstreet * 109df8e8970SKent Overstreet * op->lock determines whether we take a read or a write lock at a given depth. 110df8e8970SKent Overstreet * If you've got a read lock and find that you need a write lock (i.e. you're 111df8e8970SKent Overstreet * going to have to split), set op->lock and return -EINTR; btree_root() will 112df8e8970SKent Overstreet * call you again and you'll have the correct lock. 113df8e8970SKent Overstreet */ 114df8e8970SKent Overstreet 115df8e8970SKent Overstreet /** 116df8e8970SKent Overstreet * btree - recurse down the btree on a specified key 117df8e8970SKent Overstreet * @fn: function to call, which will be passed the child node 118df8e8970SKent Overstreet * @key: key to recurse on 119df8e8970SKent Overstreet * @b: parent btree node 120df8e8970SKent Overstreet * @op: pointer to struct btree_op 121df8e8970SKent Overstreet */ 122df8e8970SKent Overstreet #define btree(fn, key, b, op, ...) \ 123df8e8970SKent Overstreet ({ \ 124df8e8970SKent Overstreet int _r, l = (b)->level - 1; \ 125df8e8970SKent Overstreet bool _w = l <= (op)->lock; \ 1262452cc89SSlava Pestov struct btree *_child = bch_btree_node_get((b)->c, op, key, l, \ 1272452cc89SSlava Pestov _w, b); \ 128df8e8970SKent Overstreet if (!IS_ERR(_child)) { \ 129df8e8970SKent Overstreet _r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__); \ 130df8e8970SKent Overstreet rw_unlock(_w, _child); \ 131df8e8970SKent Overstreet } else \ 132df8e8970SKent Overstreet _r = PTR_ERR(_child); \ 133df8e8970SKent Overstreet _r; \ 134df8e8970SKent Overstreet }) 135df8e8970SKent Overstreet 136df8e8970SKent Overstreet /** 137df8e8970SKent Overstreet * btree_root - call a function on the root of the btree 138df8e8970SKent Overstreet * @fn: function to call, which will be passed the child node 139df8e8970SKent Overstreet * @c: cache set 140df8e8970SKent Overstreet * @op: pointer to struct btree_op 141df8e8970SKent Overstreet */ 142df8e8970SKent Overstreet #define btree_root(fn, c, op, ...) \ 143df8e8970SKent Overstreet ({ \ 144df8e8970SKent Overstreet int _r = -EINTR; \ 145df8e8970SKent Overstreet do { \ 146df8e8970SKent Overstreet struct btree *_b = (c)->root; \ 147df8e8970SKent Overstreet bool _w = insert_lock(op, _b); \ 148df8e8970SKent Overstreet rw_lock(_w, _b, _b->level); \ 149df8e8970SKent Overstreet if (_b == (c)->root && \ 150df8e8970SKent Overstreet _w == insert_lock(op, _b)) { \ 151df8e8970SKent Overstreet _r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__); \ 152df8e8970SKent Overstreet } \ 153df8e8970SKent Overstreet rw_unlock(_w, _b); \ 1540a63b66dSKent Overstreet bch_cannibalize_unlock(c); \ 15578365411SKent Overstreet if (_r == -EINTR) \ 15678365411SKent Overstreet schedule(); \ 157df8e8970SKent Overstreet } while (_r == -EINTR); \ 158df8e8970SKent Overstreet \ 1590a63b66dSKent Overstreet finish_wait(&(c)->btree_cache_wait, &(op)->wait); \ 160df8e8970SKent Overstreet _r; \ 161df8e8970SKent Overstreet }) 162df8e8970SKent Overstreet 163a85e968eSKent Overstreet static inline struct bset *write_block(struct btree *b) 164a85e968eSKent Overstreet { 165a85e968eSKent Overstreet return ((void *) btree_bset_first(b)) + b->written * block_bytes(b->c); 166a85e968eSKent Overstreet } 167a85e968eSKent Overstreet 1682a285686SKent Overstreet static void bch_btree_init_next(struct btree *b) 1692a285686SKent Overstreet { 1702a285686SKent Overstreet /* If not a leaf node, always sort */ 1712a285686SKent Overstreet if (b->level && b->keys.nsets) 1722a285686SKent Overstreet bch_btree_sort(&b->keys, &b->c->sort); 1732a285686SKent Overstreet else 1742a285686SKent Overstreet bch_btree_sort_lazy(&b->keys, &b->c->sort); 1752a285686SKent Overstreet 1762a285686SKent Overstreet if (b->written < btree_blocks(b)) 1772a285686SKent Overstreet bch_bset_init_next(&b->keys, write_block(b), 1782a285686SKent Overstreet bset_magic(&b->c->sb)); 1792a285686SKent Overstreet 1802a285686SKent Overstreet } 1812a285686SKent Overstreet 182cafe5635SKent Overstreet /* Btree key manipulation */ 183cafe5635SKent Overstreet 1843a3b6a4eSKent Overstreet void bkey_put(struct cache_set *c, struct bkey *k) 185e7c590ebSKent Overstreet { 1866f10f7d1SColy Li unsigned int i; 187e7c590ebSKent Overstreet 188e7c590ebSKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 189e7c590ebSKent Overstreet if (ptr_available(c, k, i)) 190e7c590ebSKent Overstreet atomic_dec_bug(&PTR_BUCKET(c, k, i)->pin); 191e7c590ebSKent Overstreet } 192e7c590ebSKent Overstreet 193cafe5635SKent Overstreet /* Btree IO */ 194cafe5635SKent Overstreet 195cafe5635SKent Overstreet static uint64_t btree_csum_set(struct btree *b, struct bset *i) 196cafe5635SKent Overstreet { 197cafe5635SKent Overstreet uint64_t crc = b->key.ptr[0]; 198fafff81cSKent Overstreet void *data = (void *) i + 8, *end = bset_bkey_last(i); 199cafe5635SKent Overstreet 200169ef1cfSKent Overstreet crc = bch_crc64_update(crc, data, end - data); 201c19ed23aSKent Overstreet return crc ^ 0xffffffffffffffffULL; 202cafe5635SKent Overstreet } 203cafe5635SKent Overstreet 20478b77bf8SKent Overstreet void bch_btree_node_read_done(struct btree *b) 205cafe5635SKent Overstreet { 206cafe5635SKent Overstreet const char *err = "bad btree header"; 207ee811287SKent Overstreet struct bset *i = btree_bset_first(b); 20857943511SKent Overstreet struct btree_iter *iter; 209cafe5635SKent Overstreet 210d2f96f48SShenghui Wang /* 211d2f96f48SShenghui Wang * c->fill_iter can allocate an iterator with more memory space 212d2f96f48SShenghui Wang * than static MAX_BSETS. 213d2f96f48SShenghui Wang * See the comment arount cache_set->fill_iter. 214d2f96f48SShenghui Wang */ 215d19936a2SKent Overstreet iter = mempool_alloc(&b->c->fill_iter, GFP_NOIO); 21657943511SKent Overstreet iter->size = b->c->sb.bucket_size / b->c->sb.block_size; 217cafe5635SKent Overstreet iter->used = 0; 218cafe5635SKent Overstreet 219280481d0SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 220c052dd9aSKent Overstreet iter->b = &b->keys; 221280481d0SKent Overstreet #endif 222280481d0SKent Overstreet 22357943511SKent Overstreet if (!i->seq) 224cafe5635SKent Overstreet goto err; 225cafe5635SKent Overstreet 226cafe5635SKent Overstreet for (; 227a85e968eSKent Overstreet b->written < btree_blocks(b) && i->seq == b->keys.set[0].data->seq; 228cafe5635SKent Overstreet i = write_block(b)) { 229cafe5635SKent Overstreet err = "unsupported bset version"; 230cafe5635SKent Overstreet if (i->version > BCACHE_BSET_VERSION) 231cafe5635SKent Overstreet goto err; 232cafe5635SKent Overstreet 233cafe5635SKent Overstreet err = "bad btree header"; 234ee811287SKent Overstreet if (b->written + set_blocks(i, block_bytes(b->c)) > 235ee811287SKent Overstreet btree_blocks(b)) 236cafe5635SKent Overstreet goto err; 237cafe5635SKent Overstreet 238cafe5635SKent Overstreet err = "bad magic"; 23981ab4190SKent Overstreet if (i->magic != bset_magic(&b->c->sb)) 240cafe5635SKent Overstreet goto err; 241cafe5635SKent Overstreet 242cafe5635SKent Overstreet err = "bad checksum"; 243cafe5635SKent Overstreet switch (i->version) { 244cafe5635SKent Overstreet case 0: 245cafe5635SKent Overstreet if (i->csum != csum_set(i)) 246cafe5635SKent Overstreet goto err; 247cafe5635SKent Overstreet break; 248cafe5635SKent Overstreet case BCACHE_BSET_VERSION: 249cafe5635SKent Overstreet if (i->csum != btree_csum_set(b, i)) 250cafe5635SKent Overstreet goto err; 251cafe5635SKent Overstreet break; 252cafe5635SKent Overstreet } 253cafe5635SKent Overstreet 254cafe5635SKent Overstreet err = "empty set"; 255a85e968eSKent Overstreet if (i != b->keys.set[0].data && !i->keys) 256cafe5635SKent Overstreet goto err; 257cafe5635SKent Overstreet 258fafff81cSKent Overstreet bch_btree_iter_push(iter, i->start, bset_bkey_last(i)); 259cafe5635SKent Overstreet 260ee811287SKent Overstreet b->written += set_blocks(i, block_bytes(b->c)); 261cafe5635SKent Overstreet } 262cafe5635SKent Overstreet 263cafe5635SKent Overstreet err = "corrupted btree"; 264cafe5635SKent Overstreet for (i = write_block(b); 265a85e968eSKent Overstreet bset_sector_offset(&b->keys, i) < KEY_SIZE(&b->key); 266cafe5635SKent Overstreet i = ((void *) i) + block_bytes(b->c)) 267a85e968eSKent Overstreet if (i->seq == b->keys.set[0].data->seq) 268cafe5635SKent Overstreet goto err; 269cafe5635SKent Overstreet 270a85e968eSKent Overstreet bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort); 271cafe5635SKent Overstreet 272a85e968eSKent Overstreet i = b->keys.set[0].data; 273cafe5635SKent Overstreet err = "short btree key"; 274a85e968eSKent Overstreet if (b->keys.set[0].size && 275a85e968eSKent Overstreet bkey_cmp(&b->key, &b->keys.set[0].end) < 0) 276cafe5635SKent Overstreet goto err; 277cafe5635SKent Overstreet 278cafe5635SKent Overstreet if (b->written < btree_blocks(b)) 279a85e968eSKent Overstreet bch_bset_init_next(&b->keys, write_block(b), 280a85e968eSKent Overstreet bset_magic(&b->c->sb)); 281cafe5635SKent Overstreet out: 282d19936a2SKent Overstreet mempool_free(iter, &b->c->fill_iter); 28357943511SKent Overstreet return; 284cafe5635SKent Overstreet err: 285cafe5635SKent Overstreet set_btree_node_io_error(b); 28688b9f8c4SKent Overstreet bch_cache_set_error(b->c, "%s at bucket %zu, block %u, %u keys", 287cafe5635SKent Overstreet err, PTR_BUCKET_NR(b->c, &b->key, 0), 28888b9f8c4SKent Overstreet bset_block_offset(b, i), i->keys); 289cafe5635SKent Overstreet goto out; 290cafe5635SKent Overstreet } 291cafe5635SKent Overstreet 2924246a0b6SChristoph Hellwig static void btree_node_read_endio(struct bio *bio) 293cafe5635SKent Overstreet { 29457943511SKent Overstreet struct closure *cl = bio->bi_private; 2951fae7cf0SColy Li 29657943511SKent Overstreet closure_put(cl); 29757943511SKent Overstreet } 298cafe5635SKent Overstreet 29978b77bf8SKent Overstreet static void bch_btree_node_read(struct btree *b) 30057943511SKent Overstreet { 30157943511SKent Overstreet uint64_t start_time = local_clock(); 30257943511SKent Overstreet struct closure cl; 30357943511SKent Overstreet struct bio *bio; 304cafe5635SKent Overstreet 305c37511b8SKent Overstreet trace_bcache_btree_read(b); 306c37511b8SKent Overstreet 30757943511SKent Overstreet closure_init_stack(&cl); 308cafe5635SKent Overstreet 30957943511SKent Overstreet bio = bch_bbio_alloc(b->c); 3104f024f37SKent Overstreet bio->bi_iter.bi_size = KEY_SIZE(&b->key) << 9; 31157943511SKent Overstreet bio->bi_end_io = btree_node_read_endio; 31257943511SKent Overstreet bio->bi_private = &cl; 31370fd7614SChristoph Hellwig bio->bi_opf = REQ_OP_READ | REQ_META; 31457943511SKent Overstreet 315a85e968eSKent Overstreet bch_bio_map(bio, b->keys.set[0].data); 31657943511SKent Overstreet 31757943511SKent Overstreet bch_submit_bbio(bio, b->c, &b->key, 0); 31857943511SKent Overstreet closure_sync(&cl); 31957943511SKent Overstreet 3204e4cbee9SChristoph Hellwig if (bio->bi_status) 32157943511SKent Overstreet set_btree_node_io_error(b); 32257943511SKent Overstreet 32357943511SKent Overstreet bch_bbio_free(bio, b->c); 32457943511SKent Overstreet 32557943511SKent Overstreet if (btree_node_io_error(b)) 32657943511SKent Overstreet goto err; 32757943511SKent Overstreet 32857943511SKent Overstreet bch_btree_node_read_done(b); 32957943511SKent Overstreet bch_time_stats_update(&b->c->btree_read_time, start_time); 33057943511SKent Overstreet 33157943511SKent Overstreet return; 33257943511SKent Overstreet err: 33361cbd250SGeert Uytterhoeven bch_cache_set_error(b->c, "io error reading bucket %zu", 33457943511SKent Overstreet PTR_BUCKET_NR(b->c, &b->key, 0)); 335cafe5635SKent Overstreet } 336cafe5635SKent Overstreet 337cafe5635SKent Overstreet static void btree_complete_write(struct btree *b, struct btree_write *w) 338cafe5635SKent Overstreet { 339cafe5635SKent Overstreet if (w->prio_blocked && 340cafe5635SKent Overstreet !atomic_sub_return(w->prio_blocked, &b->c->prio_blocked)) 341119ba0f8SKent Overstreet wake_up_allocators(b->c); 342cafe5635SKent Overstreet 343cafe5635SKent Overstreet if (w->journal) { 344cafe5635SKent Overstreet atomic_dec_bug(w->journal); 345cafe5635SKent Overstreet __closure_wake_up(&b->c->journal.wait); 346cafe5635SKent Overstreet } 347cafe5635SKent Overstreet 348cafe5635SKent Overstreet w->prio_blocked = 0; 349cafe5635SKent Overstreet w->journal = NULL; 350cafe5635SKent Overstreet } 351cafe5635SKent Overstreet 352cb7a583eSKent Overstreet static void btree_node_write_unlock(struct closure *cl) 353cb7a583eSKent Overstreet { 354cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 355cb7a583eSKent Overstreet 356cb7a583eSKent Overstreet up(&b->io_mutex); 357cb7a583eSKent Overstreet } 358cb7a583eSKent Overstreet 35957943511SKent Overstreet static void __btree_node_write_done(struct closure *cl) 360cafe5635SKent Overstreet { 361cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 362cafe5635SKent Overstreet struct btree_write *w = btree_prev_write(b); 363cafe5635SKent Overstreet 364cafe5635SKent Overstreet bch_bbio_free(b->bio, b->c); 365cafe5635SKent Overstreet b->bio = NULL; 366cafe5635SKent Overstreet btree_complete_write(b, w); 367cafe5635SKent Overstreet 368cafe5635SKent Overstreet if (btree_node_dirty(b)) 36956b30770SKent Overstreet schedule_delayed_work(&b->work, 30 * HZ); 370cafe5635SKent Overstreet 371cb7a583eSKent Overstreet closure_return_with_destructor(cl, btree_node_write_unlock); 372cafe5635SKent Overstreet } 373cafe5635SKent Overstreet 37457943511SKent Overstreet static void btree_node_write_done(struct closure *cl) 375cafe5635SKent Overstreet { 376cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 377cafe5635SKent Overstreet 378491221f8SGuoqing Jiang bio_free_pages(b->bio); 37957943511SKent Overstreet __btree_node_write_done(cl); 380cafe5635SKent Overstreet } 381cafe5635SKent Overstreet 3824246a0b6SChristoph Hellwig static void btree_node_write_endio(struct bio *bio) 38357943511SKent Overstreet { 38457943511SKent Overstreet struct closure *cl = bio->bi_private; 385cb7a583eSKent Overstreet struct btree *b = container_of(cl, struct btree, io); 38657943511SKent Overstreet 3874e4cbee9SChristoph Hellwig if (bio->bi_status) 38857943511SKent Overstreet set_btree_node_io_error(b); 38957943511SKent Overstreet 3904e4cbee9SChristoph Hellwig bch_bbio_count_io_errors(b->c, bio, bio->bi_status, "writing btree"); 39157943511SKent Overstreet closure_put(cl); 39257943511SKent Overstreet } 39357943511SKent Overstreet 39457943511SKent Overstreet static void do_btree_node_write(struct btree *b) 395cafe5635SKent Overstreet { 396cb7a583eSKent Overstreet struct closure *cl = &b->io; 397ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 398cafe5635SKent Overstreet BKEY_PADDED(key) k; 399cafe5635SKent Overstreet 400cafe5635SKent Overstreet i->version = BCACHE_BSET_VERSION; 401cafe5635SKent Overstreet i->csum = btree_csum_set(b, i); 402cafe5635SKent Overstreet 40357943511SKent Overstreet BUG_ON(b->bio); 40457943511SKent Overstreet b->bio = bch_bbio_alloc(b->c); 40557943511SKent Overstreet 40657943511SKent Overstreet b->bio->bi_end_io = btree_node_write_endio; 407faadf0c9SKent Overstreet b->bio->bi_private = cl; 408ee811287SKent Overstreet b->bio->bi_iter.bi_size = roundup(set_bytes(i), block_bytes(b->c)); 40970fd7614SChristoph Hellwig b->bio->bi_opf = REQ_OP_WRITE | REQ_META | REQ_FUA; 410169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 411cafe5635SKent Overstreet 412e49c7c37SKent Overstreet /* 413e49c7c37SKent Overstreet * If we're appending to a leaf node, we don't technically need FUA - 414e49c7c37SKent Overstreet * this write just needs to be persisted before the next journal write, 415e49c7c37SKent Overstreet * which will be marked FLUSH|FUA. 416e49c7c37SKent Overstreet * 417e49c7c37SKent Overstreet * Similarly if we're writing a new btree root - the pointer is going to 418e49c7c37SKent Overstreet * be in the next journal entry. 419e49c7c37SKent Overstreet * 420e49c7c37SKent Overstreet * But if we're writing a new btree node (that isn't a root) or 421e49c7c37SKent Overstreet * appending to a non leaf btree node, we need either FUA or a flush 422e49c7c37SKent Overstreet * when we write the parent with the new pointer. FUA is cheaper than a 423e49c7c37SKent Overstreet * flush, and writes appending to leaf nodes aren't blocking anything so 424e49c7c37SKent Overstreet * just make all btree node writes FUA to keep things sane. 425e49c7c37SKent Overstreet */ 426e49c7c37SKent Overstreet 427cafe5635SKent Overstreet bkey_copy(&k.key, &b->key); 428ee811287SKent Overstreet SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) + 429a85e968eSKent Overstreet bset_sector_offset(&b->keys, i)); 430cafe5635SKent Overstreet 43125d8be77SMing Lei if (!bch_bio_alloc_pages(b->bio, __GFP_NOWARN|GFP_NOWAIT)) { 432cafe5635SKent Overstreet struct bio_vec *bv; 433f936b06aSChristoph Hellwig void *addr = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1)); 4346dc4f100SMing Lei struct bvec_iter_all iter_all; 435cafe5635SKent Overstreet 4362b070cfeSChristoph Hellwig bio_for_each_segment_all(bv, b->bio, iter_all) { 437f936b06aSChristoph Hellwig memcpy(page_address(bv->bv_page), addr, PAGE_SIZE); 438f936b06aSChristoph Hellwig addr += PAGE_SIZE; 439f936b06aSChristoph Hellwig } 440cafe5635SKent Overstreet 441cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 442cafe5635SKent Overstreet 44357943511SKent Overstreet continue_at(cl, btree_node_write_done, NULL); 444cafe5635SKent Overstreet } else { 445b0d30981SColy Li /* 446b0d30981SColy Li * No problem for multipage bvec since the bio is 447b0d30981SColy Li * just allocated 448b0d30981SColy Li */ 449cafe5635SKent Overstreet b->bio->bi_vcnt = 0; 450169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 451cafe5635SKent Overstreet 452cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 453cafe5635SKent Overstreet 454cafe5635SKent Overstreet closure_sync(cl); 455cb7a583eSKent Overstreet continue_at_nobarrier(cl, __btree_node_write_done, NULL); 456cafe5635SKent Overstreet } 457cafe5635SKent Overstreet } 458cafe5635SKent Overstreet 4592a285686SKent Overstreet void __bch_btree_node_write(struct btree *b, struct closure *parent) 460cafe5635SKent Overstreet { 461ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 462cafe5635SKent Overstreet 4632a285686SKent Overstreet lockdep_assert_held(&b->write_lock); 4642a285686SKent Overstreet 465c37511b8SKent Overstreet trace_bcache_btree_write(b); 466c37511b8SKent Overstreet 467cafe5635SKent Overstreet BUG_ON(current->bio_list); 46857943511SKent Overstreet BUG_ON(b->written >= btree_blocks(b)); 46957943511SKent Overstreet BUG_ON(b->written && !i->keys); 470ee811287SKent Overstreet BUG_ON(btree_bset_first(b)->seq != i->seq); 471dc9d98d6SKent Overstreet bch_check_keys(&b->keys, "writing"); 472cafe5635SKent Overstreet 473cafe5635SKent Overstreet cancel_delayed_work(&b->work); 474cafe5635SKent Overstreet 47557943511SKent Overstreet /* If caller isn't waiting for write, parent refcount is cache set */ 476cb7a583eSKent Overstreet down(&b->io_mutex); 477cb7a583eSKent Overstreet closure_init(&b->io, parent ?: &b->c->cl); 47857943511SKent Overstreet 479cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 480cafe5635SKent Overstreet change_bit(BTREE_NODE_write_idx, &b->flags); 481cafe5635SKent Overstreet 48257943511SKent Overstreet do_btree_node_write(b); 483cafe5635SKent Overstreet 484ee811287SKent Overstreet atomic_long_add(set_blocks(i, block_bytes(b->c)) * b->c->sb.block_size, 485cafe5635SKent Overstreet &PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written); 486cafe5635SKent Overstreet 487a85e968eSKent Overstreet b->written += set_blocks(i, block_bytes(b->c)); 4882a285686SKent Overstreet } 489a85e968eSKent Overstreet 4902a285686SKent Overstreet void bch_btree_node_write(struct btree *b, struct closure *parent) 4912a285686SKent Overstreet { 4926f10f7d1SColy Li unsigned int nsets = b->keys.nsets; 4932a285686SKent Overstreet 4942a285686SKent Overstreet lockdep_assert_held(&b->lock); 4952a285686SKent Overstreet 4962a285686SKent Overstreet __bch_btree_node_write(b, parent); 497cafe5635SKent Overstreet 49878b77bf8SKent Overstreet /* 49978b77bf8SKent Overstreet * do verify if there was more than one set initially (i.e. we did a 50078b77bf8SKent Overstreet * sort) and we sorted down to a single set: 50178b77bf8SKent Overstreet */ 5022a285686SKent Overstreet if (nsets && !b->keys.nsets) 50378b77bf8SKent Overstreet bch_btree_verify(b); 50478b77bf8SKent Overstreet 5052a285686SKent Overstreet bch_btree_init_next(b); 506cafe5635SKent Overstreet } 507cafe5635SKent Overstreet 508f269af5aSKent Overstreet static void bch_btree_node_write_sync(struct btree *b) 509f269af5aSKent Overstreet { 510f269af5aSKent Overstreet struct closure cl; 511f269af5aSKent Overstreet 512f269af5aSKent Overstreet closure_init_stack(&cl); 5132a285686SKent Overstreet 5142a285686SKent Overstreet mutex_lock(&b->write_lock); 515f269af5aSKent Overstreet bch_btree_node_write(b, &cl); 5162a285686SKent Overstreet mutex_unlock(&b->write_lock); 5172a285686SKent Overstreet 518f269af5aSKent Overstreet closure_sync(&cl); 519f269af5aSKent Overstreet } 520f269af5aSKent Overstreet 52157943511SKent Overstreet static void btree_node_write_work(struct work_struct *w) 522cafe5635SKent Overstreet { 523cafe5635SKent Overstreet struct btree *b = container_of(to_delayed_work(w), struct btree, work); 524cafe5635SKent Overstreet 5252a285686SKent Overstreet mutex_lock(&b->write_lock); 526cafe5635SKent Overstreet if (btree_node_dirty(b)) 5272a285686SKent Overstreet __bch_btree_node_write(b, NULL); 5282a285686SKent Overstreet mutex_unlock(&b->write_lock); 529cafe5635SKent Overstreet } 530cafe5635SKent Overstreet 531c18536a7SKent Overstreet static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref) 532cafe5635SKent Overstreet { 533ee811287SKent Overstreet struct bset *i = btree_bset_last(b); 534cafe5635SKent Overstreet struct btree_write *w = btree_current_write(b); 535cafe5635SKent Overstreet 5362a285686SKent Overstreet lockdep_assert_held(&b->write_lock); 5372a285686SKent Overstreet 53857943511SKent Overstreet BUG_ON(!b->written); 53957943511SKent Overstreet BUG_ON(!i->keys); 540cafe5635SKent Overstreet 54157943511SKent Overstreet if (!btree_node_dirty(b)) 54256b30770SKent Overstreet schedule_delayed_work(&b->work, 30 * HZ); 54357943511SKent Overstreet 544cafe5635SKent Overstreet set_btree_node_dirty(b); 545cafe5635SKent Overstreet 5465dccefd3SColy Li /* 5475dccefd3SColy Li * w->journal is always the oldest journal pin of all bkeys 5485dccefd3SColy Li * in the leaf node, to make sure the oldest jset seq won't 5495dccefd3SColy Li * be increased before this btree node is flushed. 5505dccefd3SColy Li */ 551c18536a7SKent Overstreet if (journal_ref) { 552cafe5635SKent Overstreet if (w->journal && 553c18536a7SKent Overstreet journal_pin_cmp(b->c, w->journal, journal_ref)) { 554cafe5635SKent Overstreet atomic_dec_bug(w->journal); 555cafe5635SKent Overstreet w->journal = NULL; 556cafe5635SKent Overstreet } 557cafe5635SKent Overstreet 558cafe5635SKent Overstreet if (!w->journal) { 559c18536a7SKent Overstreet w->journal = journal_ref; 560cafe5635SKent Overstreet atomic_inc(w->journal); 561cafe5635SKent Overstreet } 562cafe5635SKent Overstreet } 563cafe5635SKent Overstreet 564cafe5635SKent Overstreet /* Force write if set is too big */ 56557943511SKent Overstreet if (set_bytes(i) > PAGE_SIZE - 48 && 56657943511SKent Overstreet !current->bio_list) 56757943511SKent Overstreet bch_btree_node_write(b, NULL); 568cafe5635SKent Overstreet } 569cafe5635SKent Overstreet 570cafe5635SKent Overstreet /* 571cafe5635SKent Overstreet * Btree in memory cache - allocation/freeing 572cafe5635SKent Overstreet * mca -> memory cache 573cafe5635SKent Overstreet */ 574cafe5635SKent Overstreet 575cafe5635SKent Overstreet #define mca_reserve(c) (((c->root && c->root->level) \ 576cafe5635SKent Overstreet ? c->root->level : 1) * 8 + 16) 577cafe5635SKent Overstreet #define mca_can_free(c) \ 5780a63b66dSKent Overstreet max_t(int, 0, c->btree_cache_used - mca_reserve(c)) 579cafe5635SKent Overstreet 580cafe5635SKent Overstreet static void mca_data_free(struct btree *b) 581cafe5635SKent Overstreet { 582cb7a583eSKent Overstreet BUG_ON(b->io_mutex.count != 1); 583cafe5635SKent Overstreet 584a85e968eSKent Overstreet bch_btree_keys_free(&b->keys); 585cafe5635SKent Overstreet 5860a63b66dSKent Overstreet b->c->btree_cache_used--; 587ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 588cafe5635SKent Overstreet } 589cafe5635SKent Overstreet 590cafe5635SKent Overstreet static void mca_bucket_free(struct btree *b) 591cafe5635SKent Overstreet { 592cafe5635SKent Overstreet BUG_ON(btree_node_dirty(b)); 593cafe5635SKent Overstreet 594cafe5635SKent Overstreet b->key.ptr[0] = 0; 595cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 596cafe5635SKent Overstreet list_move(&b->list, &b->c->btree_cache_freeable); 597cafe5635SKent Overstreet } 598cafe5635SKent Overstreet 5996f10f7d1SColy Li static unsigned int btree_order(struct bkey *k) 600cafe5635SKent Overstreet { 601cafe5635SKent Overstreet return ilog2(KEY_SIZE(k) / PAGE_SECTORS ?: 1); 602cafe5635SKent Overstreet } 603cafe5635SKent Overstreet 604cafe5635SKent Overstreet static void mca_data_alloc(struct btree *b, struct bkey *k, gfp_t gfp) 605cafe5635SKent Overstreet { 606a85e968eSKent Overstreet if (!bch_btree_keys_alloc(&b->keys, 6076f10f7d1SColy Li max_t(unsigned int, 608cafe5635SKent Overstreet ilog2(b->c->btree_pages), 609ee811287SKent Overstreet btree_order(k)), 610ee811287SKent Overstreet gfp)) { 6110a63b66dSKent Overstreet b->c->btree_cache_used++; 612ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache); 613ee811287SKent Overstreet } else { 614ee811287SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 615ee811287SKent Overstreet } 616cafe5635SKent Overstreet } 617cafe5635SKent Overstreet 618cafe5635SKent Overstreet static struct btree *mca_bucket_alloc(struct cache_set *c, 619cafe5635SKent Overstreet struct bkey *k, gfp_t gfp) 620cafe5635SKent Overstreet { 621bd9026c8SColy Li /* 622bd9026c8SColy Li * kzalloc() is necessary here for initialization, 623bd9026c8SColy Li * see code comments in bch_btree_keys_init(). 624bd9026c8SColy Li */ 625cafe5635SKent Overstreet struct btree *b = kzalloc(sizeof(struct btree), gfp); 6261fae7cf0SColy Li 627cafe5635SKent Overstreet if (!b) 628cafe5635SKent Overstreet return NULL; 629cafe5635SKent Overstreet 630cafe5635SKent Overstreet init_rwsem(&b->lock); 631cafe5635SKent Overstreet lockdep_set_novalidate_class(&b->lock); 6322a285686SKent Overstreet mutex_init(&b->write_lock); 6332a285686SKent Overstreet lockdep_set_novalidate_class(&b->write_lock); 634cafe5635SKent Overstreet INIT_LIST_HEAD(&b->list); 63557943511SKent Overstreet INIT_DELAYED_WORK(&b->work, btree_node_write_work); 636cafe5635SKent Overstreet b->c = c; 637cb7a583eSKent Overstreet sema_init(&b->io_mutex, 1); 638cafe5635SKent Overstreet 639cafe5635SKent Overstreet mca_data_alloc(b, k, gfp); 640cafe5635SKent Overstreet return b; 641cafe5635SKent Overstreet } 642cafe5635SKent Overstreet 6436f10f7d1SColy Li static int mca_reap(struct btree *b, unsigned int min_order, bool flush) 644cafe5635SKent Overstreet { 645e8e1d468SKent Overstreet struct closure cl; 646e8e1d468SKent Overstreet 647e8e1d468SKent Overstreet closure_init_stack(&cl); 648cafe5635SKent Overstreet lockdep_assert_held(&b->c->bucket_lock); 649cafe5635SKent Overstreet 650cafe5635SKent Overstreet if (!down_write_trylock(&b->lock)) 651cafe5635SKent Overstreet return -ENOMEM; 652cafe5635SKent Overstreet 653a85e968eSKent Overstreet BUG_ON(btree_node_dirty(b) && !b->keys.set[0].data); 654e8e1d468SKent Overstreet 655a85e968eSKent Overstreet if (b->keys.page_order < min_order) 656cb7a583eSKent Overstreet goto out_unlock; 657cb7a583eSKent Overstreet 658cb7a583eSKent Overstreet if (!flush) { 659cb7a583eSKent Overstreet if (btree_node_dirty(b)) 660cb7a583eSKent Overstreet goto out_unlock; 661cb7a583eSKent Overstreet 662cb7a583eSKent Overstreet if (down_trylock(&b->io_mutex)) 663cb7a583eSKent Overstreet goto out_unlock; 664cb7a583eSKent Overstreet up(&b->io_mutex); 665cafe5635SKent Overstreet } 666cafe5635SKent Overstreet 66750a260e8SColy Li retry: 66841508bb7SColy Li /* 66941508bb7SColy Li * BTREE_NODE_dirty might be cleared in btree_flush_btree() by 67041508bb7SColy Li * __bch_btree_node_write(). To avoid an extra flush, acquire 67141508bb7SColy Li * b->write_lock before checking BTREE_NODE_dirty bit. 67241508bb7SColy Li */ 6732a285686SKent Overstreet mutex_lock(&b->write_lock); 67450a260e8SColy Li /* 67550a260e8SColy Li * If this btree node is selected in btree_flush_write() by journal 67650a260e8SColy Li * code, delay and retry until the node is flushed by journal code 67750a260e8SColy Li * and BTREE_NODE_journal_flush bit cleared by btree_flush_write(). 67850a260e8SColy Li */ 67950a260e8SColy Li if (btree_node_journal_flush(b)) { 68050a260e8SColy Li pr_debug("bnode %p is flushing by journal, retry", b); 68150a260e8SColy Li mutex_unlock(&b->write_lock); 68250a260e8SColy Li udelay(1); 68350a260e8SColy Li goto retry; 68450a260e8SColy Li } 68550a260e8SColy Li 686f269af5aSKent Overstreet if (btree_node_dirty(b)) 6872a285686SKent Overstreet __bch_btree_node_write(b, &cl); 6882a285686SKent Overstreet mutex_unlock(&b->write_lock); 6892a285686SKent Overstreet 6902a285686SKent Overstreet closure_sync(&cl); 691cafe5635SKent Overstreet 692e8e1d468SKent Overstreet /* wait for any in flight btree write */ 693cb7a583eSKent Overstreet down(&b->io_mutex); 694cb7a583eSKent Overstreet up(&b->io_mutex); 695e8e1d468SKent Overstreet 696cafe5635SKent Overstreet return 0; 697cb7a583eSKent Overstreet out_unlock: 698cb7a583eSKent Overstreet rw_unlock(true, b); 699cb7a583eSKent Overstreet return -ENOMEM; 700cafe5635SKent Overstreet } 701cafe5635SKent Overstreet 7027dc19d5aSDave Chinner static unsigned long bch_mca_scan(struct shrinker *shrink, 7037dc19d5aSDave Chinner struct shrink_control *sc) 704cafe5635SKent Overstreet { 705cafe5635SKent Overstreet struct cache_set *c = container_of(shrink, struct cache_set, shrink); 706cafe5635SKent Overstreet struct btree *b, *t; 707cafe5635SKent Overstreet unsigned long i, nr = sc->nr_to_scan; 7087dc19d5aSDave Chinner unsigned long freed = 0; 709ca71df31STang Junhui unsigned int btree_cache_used; 710cafe5635SKent Overstreet 711cafe5635SKent Overstreet if (c->shrinker_disabled) 7127dc19d5aSDave Chinner return SHRINK_STOP; 713cafe5635SKent Overstreet 7140a63b66dSKent Overstreet if (c->btree_cache_alloc_lock) 7157dc19d5aSDave Chinner return SHRINK_STOP; 716cafe5635SKent Overstreet 717cafe5635SKent Overstreet /* Return -1 if we can't do anything right now */ 718a698e08cSKent Overstreet if (sc->gfp_mask & __GFP_IO) 719cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 720cafe5635SKent Overstreet else if (!mutex_trylock(&c->bucket_lock)) 721cafe5635SKent Overstreet return -1; 722cafe5635SKent Overstreet 72336c9ea98SKent Overstreet /* 72436c9ea98SKent Overstreet * It's _really_ critical that we don't free too many btree nodes - we 72536c9ea98SKent Overstreet * have to always leave ourselves a reserve. The reserve is how we 72636c9ea98SKent Overstreet * guarantee that allocating memory for a new btree node can always 72736c9ea98SKent Overstreet * succeed, so that inserting keys into the btree can always succeed and 72836c9ea98SKent Overstreet * IO can always make forward progress: 72936c9ea98SKent Overstreet */ 730cafe5635SKent Overstreet nr /= c->btree_pages; 7319fcc34b1SColy Li if (nr == 0) 7329fcc34b1SColy Li nr = 1; 733cafe5635SKent Overstreet nr = min_t(unsigned long, nr, mca_can_free(c)); 734cafe5635SKent Overstreet 735cafe5635SKent Overstreet i = 0; 736ca71df31STang Junhui btree_cache_used = c->btree_cache_used; 737*d5c9c470SColy Li list_for_each_entry_safe_reverse(b, t, &c->btree_cache_freeable, list) { 738ca71df31STang Junhui if (nr <= 0) 739ca71df31STang Junhui goto out; 740cafe5635SKent Overstreet 741*d5c9c470SColy Li if (!mca_reap(b, 0, false)) { 742cafe5635SKent Overstreet mca_data_free(b); 743cafe5635SKent Overstreet rw_unlock(true, b); 7447dc19d5aSDave Chinner freed++; 745cafe5635SKent Overstreet } 746ca71df31STang Junhui nr--; 747*d5c9c470SColy Li i++; 748cafe5635SKent Overstreet } 749cafe5635SKent Overstreet 750ca71df31STang Junhui for (; (nr--) && i < btree_cache_used; i++) { 751cafe5635SKent Overstreet if (list_empty(&c->btree_cache)) 752cafe5635SKent Overstreet goto out; 753cafe5635SKent Overstreet 754cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 755cafe5635SKent Overstreet list_rotate_left(&c->btree_cache); 756cafe5635SKent Overstreet 757125d98edSColy Li if (!mca_reap(b, 0, false)) { 758cafe5635SKent Overstreet mca_bucket_free(b); 759cafe5635SKent Overstreet mca_data_free(b); 760cafe5635SKent Overstreet rw_unlock(true, b); 7617dc19d5aSDave Chinner freed++; 762125d98edSColy Li } 763cafe5635SKent Overstreet } 764cafe5635SKent Overstreet out: 765cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 766f3641c3aSTang Junhui return freed * c->btree_pages; 7677dc19d5aSDave Chinner } 7687dc19d5aSDave Chinner 7697dc19d5aSDave Chinner static unsigned long bch_mca_count(struct shrinker *shrink, 7707dc19d5aSDave Chinner struct shrink_control *sc) 7717dc19d5aSDave Chinner { 7727dc19d5aSDave Chinner struct cache_set *c = container_of(shrink, struct cache_set, shrink); 7737dc19d5aSDave Chinner 7747dc19d5aSDave Chinner if (c->shrinker_disabled) 7757dc19d5aSDave Chinner return 0; 7767dc19d5aSDave Chinner 7770a63b66dSKent Overstreet if (c->btree_cache_alloc_lock) 7787dc19d5aSDave Chinner return 0; 7797dc19d5aSDave Chinner 7807dc19d5aSDave Chinner return mca_can_free(c) * c->btree_pages; 781cafe5635SKent Overstreet } 782cafe5635SKent Overstreet 783cafe5635SKent Overstreet void bch_btree_cache_free(struct cache_set *c) 784cafe5635SKent Overstreet { 785cafe5635SKent Overstreet struct btree *b; 786cafe5635SKent Overstreet struct closure cl; 7871fae7cf0SColy Li 788cafe5635SKent Overstreet closure_init_stack(&cl); 789cafe5635SKent Overstreet 790cafe5635SKent Overstreet if (c->shrink.list.next) 791cafe5635SKent Overstreet unregister_shrinker(&c->shrink); 792cafe5635SKent Overstreet 793cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 794cafe5635SKent Overstreet 795cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 796cafe5635SKent Overstreet if (c->verify_data) 797cafe5635SKent Overstreet list_move(&c->verify_data->list, &c->btree_cache); 79878b77bf8SKent Overstreet 79978b77bf8SKent Overstreet free_pages((unsigned long) c->verify_ondisk, ilog2(bucket_pages(c))); 800cafe5635SKent Overstreet #endif 801cafe5635SKent Overstreet 802cafe5635SKent Overstreet list_splice(&c->btree_cache_freeable, 803cafe5635SKent Overstreet &c->btree_cache); 804cafe5635SKent Overstreet 805cafe5635SKent Overstreet while (!list_empty(&c->btree_cache)) { 806cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 807cafe5635SKent Overstreet 80841508bb7SColy Li /* 80941508bb7SColy Li * This function is called by cache_set_free(), no I/O 81041508bb7SColy Li * request on cache now, it is unnecessary to acquire 81141508bb7SColy Li * b->write_lock before clearing BTREE_NODE_dirty anymore. 81241508bb7SColy Li */ 813e5ec5f47SColy Li if (btree_node_dirty(b)) { 814cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 815cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 816e5ec5f47SColy Li } 817cafe5635SKent Overstreet mca_data_free(b); 818cafe5635SKent Overstreet } 819cafe5635SKent Overstreet 820cafe5635SKent Overstreet while (!list_empty(&c->btree_cache_freed)) { 821cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache_freed, 822cafe5635SKent Overstreet struct btree, list); 823cafe5635SKent Overstreet list_del(&b->list); 824cafe5635SKent Overstreet cancel_delayed_work_sync(&b->work); 825cafe5635SKent Overstreet kfree(b); 826cafe5635SKent Overstreet } 827cafe5635SKent Overstreet 828cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 829cafe5635SKent Overstreet } 830cafe5635SKent Overstreet 831cafe5635SKent Overstreet int bch_btree_cache_alloc(struct cache_set *c) 832cafe5635SKent Overstreet { 8336f10f7d1SColy Li unsigned int i; 834cafe5635SKent Overstreet 835cafe5635SKent Overstreet for (i = 0; i < mca_reserve(c); i++) 83672a44517SKent Overstreet if (!mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL)) 83772a44517SKent Overstreet return -ENOMEM; 838cafe5635SKent Overstreet 839cafe5635SKent Overstreet list_splice_init(&c->btree_cache, 840cafe5635SKent Overstreet &c->btree_cache_freeable); 841cafe5635SKent Overstreet 842cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 843cafe5635SKent Overstreet mutex_init(&c->verify_lock); 844cafe5635SKent Overstreet 84578b77bf8SKent Overstreet c->verify_ondisk = (void *) 84678b77bf8SKent Overstreet __get_free_pages(GFP_KERNEL, ilog2(bucket_pages(c))); 84778b77bf8SKent Overstreet 848cafe5635SKent Overstreet c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL); 849cafe5635SKent Overstreet 850cafe5635SKent Overstreet if (c->verify_data && 851a85e968eSKent Overstreet c->verify_data->keys.set->data) 852cafe5635SKent Overstreet list_del_init(&c->verify_data->list); 853cafe5635SKent Overstreet else 854cafe5635SKent Overstreet c->verify_data = NULL; 855cafe5635SKent Overstreet #endif 856cafe5635SKent Overstreet 8577dc19d5aSDave Chinner c->shrink.count_objects = bch_mca_count; 8587dc19d5aSDave Chinner c->shrink.scan_objects = bch_mca_scan; 859cafe5635SKent Overstreet c->shrink.seeks = 4; 860cafe5635SKent Overstreet c->shrink.batch = c->btree_pages * 2; 8616c4ca1e3SMichael Lyle 8626c4ca1e3SMichael Lyle if (register_shrinker(&c->shrink)) 8636c4ca1e3SMichael Lyle pr_warn("bcache: %s: could not register shrinker", 8646c4ca1e3SMichael Lyle __func__); 865cafe5635SKent Overstreet 866cafe5635SKent Overstreet return 0; 867cafe5635SKent Overstreet } 868cafe5635SKent Overstreet 869cafe5635SKent Overstreet /* Btree in memory cache - hash table */ 870cafe5635SKent Overstreet 871cafe5635SKent Overstreet static struct hlist_head *mca_hash(struct cache_set *c, struct bkey *k) 872cafe5635SKent Overstreet { 873cafe5635SKent Overstreet return &c->bucket_hash[hash_32(PTR_HASH(c, k), BUCKET_HASH_BITS)]; 874cafe5635SKent Overstreet } 875cafe5635SKent Overstreet 876cafe5635SKent Overstreet static struct btree *mca_find(struct cache_set *c, struct bkey *k) 877cafe5635SKent Overstreet { 878cafe5635SKent Overstreet struct btree *b; 879cafe5635SKent Overstreet 880cafe5635SKent Overstreet rcu_read_lock(); 881cafe5635SKent Overstreet hlist_for_each_entry_rcu(b, mca_hash(c, k), hash) 882cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) == PTR_HASH(c, k)) 883cafe5635SKent Overstreet goto out; 884cafe5635SKent Overstreet b = NULL; 885cafe5635SKent Overstreet out: 886cafe5635SKent Overstreet rcu_read_unlock(); 887cafe5635SKent Overstreet return b; 888cafe5635SKent Overstreet } 889cafe5635SKent Overstreet 8900a63b66dSKent Overstreet static int mca_cannibalize_lock(struct cache_set *c, struct btree_op *op) 8910a63b66dSKent Overstreet { 89234cf78bfSGuoju Fang spin_lock(&c->btree_cannibalize_lock); 89334cf78bfSGuoju Fang if (likely(c->btree_cache_alloc_lock == NULL)) { 89434cf78bfSGuoju Fang c->btree_cache_alloc_lock = current; 89534cf78bfSGuoju Fang } else if (c->btree_cache_alloc_lock != current) { 8960a63b66dSKent Overstreet if (op) 8970a63b66dSKent Overstreet prepare_to_wait(&c->btree_cache_wait, &op->wait, 8980a63b66dSKent Overstreet TASK_UNINTERRUPTIBLE); 89934cf78bfSGuoju Fang spin_unlock(&c->btree_cannibalize_lock); 9000a63b66dSKent Overstreet return -EINTR; 9010a63b66dSKent Overstreet } 90234cf78bfSGuoju Fang spin_unlock(&c->btree_cannibalize_lock); 9030a63b66dSKent Overstreet 9040a63b66dSKent Overstreet return 0; 9050a63b66dSKent Overstreet } 9060a63b66dSKent Overstreet 9070a63b66dSKent Overstreet static struct btree *mca_cannibalize(struct cache_set *c, struct btree_op *op, 9080a63b66dSKent Overstreet struct bkey *k) 909cafe5635SKent Overstreet { 910e8e1d468SKent Overstreet struct btree *b; 911cafe5635SKent Overstreet 912c37511b8SKent Overstreet trace_bcache_btree_cache_cannibalize(c); 913c37511b8SKent Overstreet 9140a63b66dSKent Overstreet if (mca_cannibalize_lock(c, op)) 9150a63b66dSKent Overstreet return ERR_PTR(-EINTR); 916cafe5635SKent Overstreet 917e8e1d468SKent Overstreet list_for_each_entry_reverse(b, &c->btree_cache, list) 918e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), false)) 919e8e1d468SKent Overstreet return b; 920cafe5635SKent Overstreet 921e8e1d468SKent Overstreet list_for_each_entry_reverse(b, &c->btree_cache, list) 922e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), true)) 923e8e1d468SKent Overstreet return b; 924e8e1d468SKent Overstreet 9250a63b66dSKent Overstreet WARN(1, "btree cache cannibalize failed\n"); 926e8e1d468SKent Overstreet return ERR_PTR(-ENOMEM); 927cafe5635SKent Overstreet } 928cafe5635SKent Overstreet 929cafe5635SKent Overstreet /* 930cafe5635SKent Overstreet * We can only have one thread cannibalizing other cached btree nodes at a time, 931cafe5635SKent Overstreet * or we'll deadlock. We use an open coded mutex to ensure that, which a 932cafe5635SKent Overstreet * cannibalize_bucket() will take. This means every time we unlock the root of 933cafe5635SKent Overstreet * the btree, we need to release this lock if we have it held. 934cafe5635SKent Overstreet */ 935df8e8970SKent Overstreet static void bch_cannibalize_unlock(struct cache_set *c) 936cafe5635SKent Overstreet { 93734cf78bfSGuoju Fang spin_lock(&c->btree_cannibalize_lock); 9380a63b66dSKent Overstreet if (c->btree_cache_alloc_lock == current) { 9390a63b66dSKent Overstreet c->btree_cache_alloc_lock = NULL; 9400a63b66dSKent Overstreet wake_up(&c->btree_cache_wait); 941cafe5635SKent Overstreet } 94234cf78bfSGuoju Fang spin_unlock(&c->btree_cannibalize_lock); 943cafe5635SKent Overstreet } 944cafe5635SKent Overstreet 9450a63b66dSKent Overstreet static struct btree *mca_alloc(struct cache_set *c, struct btree_op *op, 9460a63b66dSKent Overstreet struct bkey *k, int level) 947cafe5635SKent Overstreet { 948cafe5635SKent Overstreet struct btree *b; 949cafe5635SKent Overstreet 950e8e1d468SKent Overstreet BUG_ON(current->bio_list); 951e8e1d468SKent Overstreet 952cafe5635SKent Overstreet lockdep_assert_held(&c->bucket_lock); 953cafe5635SKent Overstreet 954cafe5635SKent Overstreet if (mca_find(c, k)) 955cafe5635SKent Overstreet return NULL; 956cafe5635SKent Overstreet 957cafe5635SKent Overstreet /* btree_free() doesn't free memory; it sticks the node on the end of 958cafe5635SKent Overstreet * the list. Check if there's any freed nodes there: 959cafe5635SKent Overstreet */ 960cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freeable, list) 961e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), false)) 962cafe5635SKent Overstreet goto out; 963cafe5635SKent Overstreet 964cafe5635SKent Overstreet /* We never free struct btree itself, just the memory that holds the on 965cafe5635SKent Overstreet * disk node. Check the freed list before allocating a new one: 966cafe5635SKent Overstreet */ 967cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freed, list) 968e8e1d468SKent Overstreet if (!mca_reap(b, 0, false)) { 969cafe5635SKent Overstreet mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO); 970a85e968eSKent Overstreet if (!b->keys.set[0].data) 971cafe5635SKent Overstreet goto err; 972cafe5635SKent Overstreet else 973cafe5635SKent Overstreet goto out; 974cafe5635SKent Overstreet } 975cafe5635SKent Overstreet 976cafe5635SKent Overstreet b = mca_bucket_alloc(c, k, __GFP_NOWARN|GFP_NOIO); 977cafe5635SKent Overstreet if (!b) 978cafe5635SKent Overstreet goto err; 979cafe5635SKent Overstreet 980cafe5635SKent Overstreet BUG_ON(!down_write_trylock(&b->lock)); 981a85e968eSKent Overstreet if (!b->keys.set->data) 982cafe5635SKent Overstreet goto err; 983cafe5635SKent Overstreet out: 984cb7a583eSKent Overstreet BUG_ON(b->io_mutex.count != 1); 985cafe5635SKent Overstreet 986cafe5635SKent Overstreet bkey_copy(&b->key, k); 987cafe5635SKent Overstreet list_move(&b->list, &c->btree_cache); 988cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 989cafe5635SKent Overstreet hlist_add_head_rcu(&b->hash, mca_hash(c, k)); 990cafe5635SKent Overstreet 991cafe5635SKent Overstreet lock_set_subclass(&b->lock.dep_map, level + 1, _THIS_IP_); 992d6fd3b11SKent Overstreet b->parent = (void *) ~0UL; 993a85e968eSKent Overstreet b->flags = 0; 994a85e968eSKent Overstreet b->written = 0; 995a85e968eSKent Overstreet b->level = level; 996cafe5635SKent Overstreet 99765d45231SKent Overstreet if (!b->level) 998a85e968eSKent Overstreet bch_btree_keys_init(&b->keys, &bch_extent_keys_ops, 999a85e968eSKent Overstreet &b->c->expensive_debug_checks); 100065d45231SKent Overstreet else 1001a85e968eSKent Overstreet bch_btree_keys_init(&b->keys, &bch_btree_keys_ops, 1002a85e968eSKent Overstreet &b->c->expensive_debug_checks); 1003cafe5635SKent Overstreet 1004cafe5635SKent Overstreet return b; 1005cafe5635SKent Overstreet err: 1006cafe5635SKent Overstreet if (b) 1007cafe5635SKent Overstreet rw_unlock(true, b); 1008cafe5635SKent Overstreet 10090a63b66dSKent Overstreet b = mca_cannibalize(c, op, k); 1010cafe5635SKent Overstreet if (!IS_ERR(b)) 1011cafe5635SKent Overstreet goto out; 1012cafe5635SKent Overstreet 1013cafe5635SKent Overstreet return b; 1014cafe5635SKent Overstreet } 1015cafe5635SKent Overstreet 101647344e33SBart Van Assche /* 1017cafe5635SKent Overstreet * bch_btree_node_get - find a btree node in the cache and lock it, reading it 1018cafe5635SKent Overstreet * in from disk if necessary. 1019cafe5635SKent Overstreet * 1020b54d6934SKent Overstreet * If IO is necessary and running under generic_make_request, returns -EAGAIN. 1021cafe5635SKent Overstreet * 1022cafe5635SKent Overstreet * The btree node will have either a read or a write lock held, depending on 1023cafe5635SKent Overstreet * level and op->lock. 1024cafe5635SKent Overstreet */ 10250a63b66dSKent Overstreet struct btree *bch_btree_node_get(struct cache_set *c, struct btree_op *op, 10262452cc89SSlava Pestov struct bkey *k, int level, bool write, 10272452cc89SSlava Pestov struct btree *parent) 1028cafe5635SKent Overstreet { 1029cafe5635SKent Overstreet int i = 0; 1030cafe5635SKent Overstreet struct btree *b; 1031cafe5635SKent Overstreet 1032cafe5635SKent Overstreet BUG_ON(level < 0); 1033cafe5635SKent Overstreet retry: 1034cafe5635SKent Overstreet b = mca_find(c, k); 1035cafe5635SKent Overstreet 1036cafe5635SKent Overstreet if (!b) { 103757943511SKent Overstreet if (current->bio_list) 103857943511SKent Overstreet return ERR_PTR(-EAGAIN); 103957943511SKent Overstreet 1040cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 10410a63b66dSKent Overstreet b = mca_alloc(c, op, k, level); 1042cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1043cafe5635SKent Overstreet 1044cafe5635SKent Overstreet if (!b) 1045cafe5635SKent Overstreet goto retry; 1046cafe5635SKent Overstreet if (IS_ERR(b)) 1047cafe5635SKent Overstreet return b; 1048cafe5635SKent Overstreet 104957943511SKent Overstreet bch_btree_node_read(b); 1050cafe5635SKent Overstreet 1051cafe5635SKent Overstreet if (!write) 1052cafe5635SKent Overstreet downgrade_write(&b->lock); 1053cafe5635SKent Overstreet } else { 1054cafe5635SKent Overstreet rw_lock(write, b, level); 1055cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) != PTR_HASH(c, k)) { 1056cafe5635SKent Overstreet rw_unlock(write, b); 1057cafe5635SKent Overstreet goto retry; 1058cafe5635SKent Overstreet } 1059cafe5635SKent Overstreet BUG_ON(b->level != level); 1060cafe5635SKent Overstreet } 1061cafe5635SKent Overstreet 1062c2e8dcf7SColy Li if (btree_node_io_error(b)) { 1063c2e8dcf7SColy Li rw_unlock(write, b); 1064c2e8dcf7SColy Li return ERR_PTR(-EIO); 1065c2e8dcf7SColy Li } 1066c2e8dcf7SColy Li 1067c2e8dcf7SColy Li BUG_ON(!b->written); 1068c2e8dcf7SColy Li 10692452cc89SSlava Pestov b->parent = parent; 1070cafe5635SKent Overstreet 1071a85e968eSKent Overstreet for (; i <= b->keys.nsets && b->keys.set[i].size; i++) { 1072a85e968eSKent Overstreet prefetch(b->keys.set[i].tree); 1073a85e968eSKent Overstreet prefetch(b->keys.set[i].data); 1074cafe5635SKent Overstreet } 1075cafe5635SKent Overstreet 1076a85e968eSKent Overstreet for (; i <= b->keys.nsets; i++) 1077a85e968eSKent Overstreet prefetch(b->keys.set[i].data); 1078cafe5635SKent Overstreet 1079cafe5635SKent Overstreet return b; 1080cafe5635SKent Overstreet } 1081cafe5635SKent Overstreet 10822452cc89SSlava Pestov static void btree_node_prefetch(struct btree *parent, struct bkey *k) 1083cafe5635SKent Overstreet { 1084cafe5635SKent Overstreet struct btree *b; 1085cafe5635SKent Overstreet 10862452cc89SSlava Pestov mutex_lock(&parent->c->bucket_lock); 10872452cc89SSlava Pestov b = mca_alloc(parent->c, NULL, k, parent->level - 1); 10882452cc89SSlava Pestov mutex_unlock(&parent->c->bucket_lock); 1089cafe5635SKent Overstreet 1090cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(b)) { 10912452cc89SSlava Pestov b->parent = parent; 109257943511SKent Overstreet bch_btree_node_read(b); 1093cafe5635SKent Overstreet rw_unlock(true, b); 1094cafe5635SKent Overstreet } 1095cafe5635SKent Overstreet } 1096cafe5635SKent Overstreet 1097cafe5635SKent Overstreet /* Btree alloc */ 1098cafe5635SKent Overstreet 1099e8e1d468SKent Overstreet static void btree_node_free(struct btree *b) 1100cafe5635SKent Overstreet { 1101c37511b8SKent Overstreet trace_bcache_btree_node_free(b); 1102c37511b8SKent Overstreet 1103cafe5635SKent Overstreet BUG_ON(b == b->c->root); 1104cafe5635SKent Overstreet 110550a260e8SColy Li retry: 11062a285686SKent Overstreet mutex_lock(&b->write_lock); 110750a260e8SColy Li /* 110850a260e8SColy Li * If the btree node is selected and flushing in btree_flush_write(), 110950a260e8SColy Li * delay and retry until the BTREE_NODE_journal_flush bit cleared, 111050a260e8SColy Li * then it is safe to free the btree node here. Otherwise this btree 111150a260e8SColy Li * node will be in race condition. 111250a260e8SColy Li */ 111350a260e8SColy Li if (btree_node_journal_flush(b)) { 111450a260e8SColy Li mutex_unlock(&b->write_lock); 111550a260e8SColy Li pr_debug("bnode %p journal_flush set, retry", b); 111650a260e8SColy Li udelay(1); 111750a260e8SColy Li goto retry; 111850a260e8SColy Li } 11192a285686SKent Overstreet 1120e5ec5f47SColy Li if (btree_node_dirty(b)) { 1121cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 1122cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 1123e5ec5f47SColy Li } 1124cafe5635SKent Overstreet 11252a285686SKent Overstreet mutex_unlock(&b->write_lock); 11262a285686SKent Overstreet 1127cafe5635SKent Overstreet cancel_delayed_work(&b->work); 1128cafe5635SKent Overstreet 1129cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 1130cafe5635SKent Overstreet bch_bucket_free(b->c, &b->key); 1131cafe5635SKent Overstreet mca_bucket_free(b); 1132cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 1133cafe5635SKent Overstreet } 1134cafe5635SKent Overstreet 1135c5aa4a31SSlava Pestov struct btree *__bch_btree_node_alloc(struct cache_set *c, struct btree_op *op, 11362452cc89SSlava Pestov int level, bool wait, 11372452cc89SSlava Pestov struct btree *parent) 1138cafe5635SKent Overstreet { 1139cafe5635SKent Overstreet BKEY_PADDED(key) k; 1140cafe5635SKent Overstreet struct btree *b = ERR_PTR(-EAGAIN); 1141cafe5635SKent Overstreet 1142cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1143cafe5635SKent Overstreet retry: 1144c5aa4a31SSlava Pestov if (__bch_bucket_alloc_set(c, RESERVE_BTREE, &k.key, 1, wait)) 1145cafe5635SKent Overstreet goto err; 1146cafe5635SKent Overstreet 11473a3b6a4eSKent Overstreet bkey_put(c, &k.key); 1148cafe5635SKent Overstreet SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS); 1149cafe5635SKent Overstreet 11500a63b66dSKent Overstreet b = mca_alloc(c, op, &k.key, level); 1151cafe5635SKent Overstreet if (IS_ERR(b)) 1152cafe5635SKent Overstreet goto err_free; 1153cafe5635SKent Overstreet 1154cafe5635SKent Overstreet if (!b) { 1155b1a67b0fSKent Overstreet cache_bug(c, 1156b1a67b0fSKent Overstreet "Tried to allocate bucket that was in btree cache"); 1157cafe5635SKent Overstreet goto retry; 1158cafe5635SKent Overstreet } 1159cafe5635SKent Overstreet 11602452cc89SSlava Pestov b->parent = parent; 1161a85e968eSKent Overstreet bch_bset_init_next(&b->keys, b->keys.set->data, bset_magic(&b->c->sb)); 1162cafe5635SKent Overstreet 1163cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1164c37511b8SKent Overstreet 1165c37511b8SKent Overstreet trace_bcache_btree_node_alloc(b); 1166cafe5635SKent Overstreet return b; 1167cafe5635SKent Overstreet err_free: 1168cafe5635SKent Overstreet bch_bucket_free(c, &k.key); 1169cafe5635SKent Overstreet err: 1170cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1171c37511b8SKent Overstreet 1172913dc33fSSlava Pestov trace_bcache_btree_node_alloc_fail(c); 1173cafe5635SKent Overstreet return b; 1174cafe5635SKent Overstreet } 1175cafe5635SKent Overstreet 1176c5aa4a31SSlava Pestov static struct btree *bch_btree_node_alloc(struct cache_set *c, 11772452cc89SSlava Pestov struct btree_op *op, int level, 11782452cc89SSlava Pestov struct btree *parent) 1179c5aa4a31SSlava Pestov { 11802452cc89SSlava Pestov return __bch_btree_node_alloc(c, op, level, op != NULL, parent); 1181c5aa4a31SSlava Pestov } 1182c5aa4a31SSlava Pestov 11830a63b66dSKent Overstreet static struct btree *btree_node_alloc_replacement(struct btree *b, 11840a63b66dSKent Overstreet struct btree_op *op) 1185cafe5635SKent Overstreet { 11862452cc89SSlava Pestov struct btree *n = bch_btree_node_alloc(b->c, op, b->level, b->parent); 11871fae7cf0SColy Li 118867539e85SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 11892a285686SKent Overstreet mutex_lock(&n->write_lock); 119089ebb4a2SKent Overstreet bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort); 119167539e85SKent Overstreet bkey_copy_key(&n->key, &b->key); 11922a285686SKent Overstreet mutex_unlock(&n->write_lock); 119367539e85SKent Overstreet } 1194cafe5635SKent Overstreet 1195cafe5635SKent Overstreet return n; 1196cafe5635SKent Overstreet } 1197cafe5635SKent Overstreet 11988835c123SKent Overstreet static void make_btree_freeing_key(struct btree *b, struct bkey *k) 11998835c123SKent Overstreet { 12006f10f7d1SColy Li unsigned int i; 12018835c123SKent Overstreet 120205335cffSKent Overstreet mutex_lock(&b->c->bucket_lock); 120305335cffSKent Overstreet 120405335cffSKent Overstreet atomic_inc(&b->c->prio_blocked); 120505335cffSKent Overstreet 12068835c123SKent Overstreet bkey_copy(k, &b->key); 12078835c123SKent Overstreet bkey_copy_key(k, &ZERO_KEY); 12088835c123SKent Overstreet 120905335cffSKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 121005335cffSKent Overstreet SET_PTR_GEN(k, i, 121105335cffSKent Overstreet bch_inc_gen(PTR_CACHE(b->c, &b->key, i), 121205335cffSKent Overstreet PTR_BUCKET(b->c, &b->key, i))); 12138835c123SKent Overstreet 121405335cffSKent Overstreet mutex_unlock(&b->c->bucket_lock); 12158835c123SKent Overstreet } 12168835c123SKent Overstreet 121778365411SKent Overstreet static int btree_check_reserve(struct btree *b, struct btree_op *op) 121878365411SKent Overstreet { 121978365411SKent Overstreet struct cache_set *c = b->c; 122078365411SKent Overstreet struct cache *ca; 12216f10f7d1SColy Li unsigned int i, reserve = (c->root->level - b->level) * 2 + 1; 122278365411SKent Overstreet 122378365411SKent Overstreet mutex_lock(&c->bucket_lock); 122478365411SKent Overstreet 122578365411SKent Overstreet for_each_cache(ca, c, i) 122678365411SKent Overstreet if (fifo_used(&ca->free[RESERVE_BTREE]) < reserve) { 122778365411SKent Overstreet if (op) 12280a63b66dSKent Overstreet prepare_to_wait(&c->btree_cache_wait, &op->wait, 122978365411SKent Overstreet TASK_UNINTERRUPTIBLE); 12300a63b66dSKent Overstreet mutex_unlock(&c->bucket_lock); 12310a63b66dSKent Overstreet return -EINTR; 123278365411SKent Overstreet } 123378365411SKent Overstreet 123478365411SKent Overstreet mutex_unlock(&c->bucket_lock); 12350a63b66dSKent Overstreet 12360a63b66dSKent Overstreet return mca_cannibalize_lock(b->c, op); 123778365411SKent Overstreet } 123878365411SKent Overstreet 1239cafe5635SKent Overstreet /* Garbage collection */ 1240cafe5635SKent Overstreet 1241487dded8SKent Overstreet static uint8_t __bch_btree_mark_key(struct cache_set *c, int level, 1242487dded8SKent Overstreet struct bkey *k) 1243cafe5635SKent Overstreet { 1244cafe5635SKent Overstreet uint8_t stale = 0; 12456f10f7d1SColy Li unsigned int i; 1246cafe5635SKent Overstreet struct bucket *g; 1247cafe5635SKent Overstreet 1248cafe5635SKent Overstreet /* 1249cafe5635SKent Overstreet * ptr_invalid() can't return true for the keys that mark btree nodes as 1250cafe5635SKent Overstreet * freed, but since ptr_bad() returns true we'll never actually use them 1251cafe5635SKent Overstreet * for anything and thus we don't want mark their pointers here 1252cafe5635SKent Overstreet */ 1253cafe5635SKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1254cafe5635SKent Overstreet return stale; 1255cafe5635SKent Overstreet 1256cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) { 1257cafe5635SKent Overstreet if (!ptr_available(c, k, i)) 1258cafe5635SKent Overstreet continue; 1259cafe5635SKent Overstreet 1260cafe5635SKent Overstreet g = PTR_BUCKET(c, k, i); 1261cafe5635SKent Overstreet 12623a2fd9d5SKent Overstreet if (gen_after(g->last_gc, PTR_GEN(k, i))) 12633a2fd9d5SKent Overstreet g->last_gc = PTR_GEN(k, i); 1264cafe5635SKent Overstreet 1265cafe5635SKent Overstreet if (ptr_stale(c, k, i)) { 1266cafe5635SKent Overstreet stale = max(stale, ptr_stale(c, k, i)); 1267cafe5635SKent Overstreet continue; 1268cafe5635SKent Overstreet } 1269cafe5635SKent Overstreet 1270cafe5635SKent Overstreet cache_bug_on(GC_MARK(g) && 1271cafe5635SKent Overstreet (GC_MARK(g) == GC_MARK_METADATA) != (level != 0), 1272cafe5635SKent Overstreet c, "inconsistent ptrs: mark = %llu, level = %i", 1273cafe5635SKent Overstreet GC_MARK(g), level); 1274cafe5635SKent Overstreet 1275cafe5635SKent Overstreet if (level) 1276cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_METADATA); 1277cafe5635SKent Overstreet else if (KEY_DIRTY(k)) 1278cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_DIRTY); 12794fe6a816SKent Overstreet else if (!GC_MARK(g)) 12804fe6a816SKent Overstreet SET_GC_MARK(g, GC_MARK_RECLAIMABLE); 1281cafe5635SKent Overstreet 1282cafe5635SKent Overstreet /* guard against overflow */ 12836f10f7d1SColy Li SET_GC_SECTORS_USED(g, min_t(unsigned int, 1284cafe5635SKent Overstreet GC_SECTORS_USED(g) + KEY_SIZE(k), 128594717447SDarrick J. Wong MAX_GC_SECTORS_USED)); 1286cafe5635SKent Overstreet 1287cafe5635SKent Overstreet BUG_ON(!GC_SECTORS_USED(g)); 1288cafe5635SKent Overstreet } 1289cafe5635SKent Overstreet 1290cafe5635SKent Overstreet return stale; 1291cafe5635SKent Overstreet } 1292cafe5635SKent Overstreet 1293cafe5635SKent Overstreet #define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k) 1294cafe5635SKent Overstreet 1295487dded8SKent Overstreet void bch_initial_mark_key(struct cache_set *c, int level, struct bkey *k) 1296487dded8SKent Overstreet { 12976f10f7d1SColy Li unsigned int i; 1298487dded8SKent Overstreet 1299487dded8SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 1300487dded8SKent Overstreet if (ptr_available(c, k, i) && 1301487dded8SKent Overstreet !ptr_stale(c, k, i)) { 1302487dded8SKent Overstreet struct bucket *b = PTR_BUCKET(c, k, i); 1303487dded8SKent Overstreet 1304487dded8SKent Overstreet b->gen = PTR_GEN(k, i); 1305487dded8SKent Overstreet 1306487dded8SKent Overstreet if (level && bkey_cmp(k, &ZERO_KEY)) 1307487dded8SKent Overstreet b->prio = BTREE_PRIO; 1308487dded8SKent Overstreet else if (!level && b->prio == BTREE_PRIO) 1309487dded8SKent Overstreet b->prio = INITIAL_PRIO; 1310487dded8SKent Overstreet } 1311487dded8SKent Overstreet 1312487dded8SKent Overstreet __bch_btree_mark_key(c, level, k); 1313487dded8SKent Overstreet } 1314487dded8SKent Overstreet 1315d44c2f9eSTang Junhui void bch_update_bucket_in_use(struct cache_set *c, struct gc_stat *stats) 1316d44c2f9eSTang Junhui { 1317d44c2f9eSTang Junhui stats->in_use = (c->nbuckets - c->avail_nbuckets) * 100 / c->nbuckets; 1318d44c2f9eSTang Junhui } 1319d44c2f9eSTang Junhui 1320a1f0358bSKent Overstreet static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc) 1321cafe5635SKent Overstreet { 1322cafe5635SKent Overstreet uint8_t stale = 0; 13236f10f7d1SColy Li unsigned int keys = 0, good_keys = 0; 1324cafe5635SKent Overstreet struct bkey *k; 1325cafe5635SKent Overstreet struct btree_iter iter; 1326cafe5635SKent Overstreet struct bset_tree *t; 1327cafe5635SKent Overstreet 1328cafe5635SKent Overstreet gc->nodes++; 1329cafe5635SKent Overstreet 1330c052dd9aSKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) { 1331cafe5635SKent Overstreet stale = max(stale, btree_mark_key(b, k)); 1332a1f0358bSKent Overstreet keys++; 1333cafe5635SKent Overstreet 1334a85e968eSKent Overstreet if (bch_ptr_bad(&b->keys, k)) 1335cafe5635SKent Overstreet continue; 1336cafe5635SKent Overstreet 1337cafe5635SKent Overstreet gc->key_bytes += bkey_u64s(k); 1338cafe5635SKent Overstreet gc->nkeys++; 1339a1f0358bSKent Overstreet good_keys++; 1340cafe5635SKent Overstreet 1341cafe5635SKent Overstreet gc->data += KEY_SIZE(k); 1342cafe5635SKent Overstreet } 1343cafe5635SKent Overstreet 1344a85e968eSKent Overstreet for (t = b->keys.set; t <= &b->keys.set[b->keys.nsets]; t++) 1345cafe5635SKent Overstreet btree_bug_on(t->size && 1346a85e968eSKent Overstreet bset_written(&b->keys, t) && 1347cafe5635SKent Overstreet bkey_cmp(&b->key, &t->end) < 0, 1348cafe5635SKent Overstreet b, "found short btree key in gc"); 1349cafe5635SKent Overstreet 1350a1f0358bSKent Overstreet if (b->c->gc_always_rewrite) 1351a1f0358bSKent Overstreet return true; 1352a1f0358bSKent Overstreet 1353a1f0358bSKent Overstreet if (stale > 10) 1354a1f0358bSKent Overstreet return true; 1355a1f0358bSKent Overstreet 1356a1f0358bSKent Overstreet if ((keys - good_keys) * 2 > keys) 1357a1f0358bSKent Overstreet return true; 1358a1f0358bSKent Overstreet 1359a1f0358bSKent Overstreet return false; 1360cafe5635SKent Overstreet } 1361cafe5635SKent Overstreet 1362a1f0358bSKent Overstreet #define GC_MERGE_NODES 4U 1363cafe5635SKent Overstreet 1364cafe5635SKent Overstreet struct gc_merge_info { 1365cafe5635SKent Overstreet struct btree *b; 13666f10f7d1SColy Li unsigned int keys; 1367cafe5635SKent Overstreet }; 1368cafe5635SKent Overstreet 1369fc2d5988SColy Li static int bch_btree_insert_node(struct btree *b, struct btree_op *op, 1370fc2d5988SColy Li struct keylist *insert_keys, 1371fc2d5988SColy Li atomic_t *journal_ref, 1372fc2d5988SColy Li struct bkey *replace_key); 1373a1f0358bSKent Overstreet 1374a1f0358bSKent Overstreet static int btree_gc_coalesce(struct btree *b, struct btree_op *op, 13750a63b66dSKent Overstreet struct gc_stat *gc, struct gc_merge_info *r) 1376cafe5635SKent Overstreet { 13776f10f7d1SColy Li unsigned int i, nodes = 0, keys = 0, blocks; 1378a1f0358bSKent Overstreet struct btree *new_nodes[GC_MERGE_NODES]; 13790a63b66dSKent Overstreet struct keylist keylist; 1380b54d6934SKent Overstreet struct closure cl; 1381a1f0358bSKent Overstreet struct bkey *k; 1382b54d6934SKent Overstreet 13830a63b66dSKent Overstreet bch_keylist_init(&keylist); 13840a63b66dSKent Overstreet 13850a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 13860a63b66dSKent Overstreet return 0; 13870a63b66dSKent Overstreet 1388a1f0358bSKent Overstreet memset(new_nodes, 0, sizeof(new_nodes)); 1389b54d6934SKent Overstreet closure_init_stack(&cl); 1390cafe5635SKent Overstreet 1391a1f0358bSKent Overstreet while (nodes < GC_MERGE_NODES && !IS_ERR_OR_NULL(r[nodes].b)) 1392cafe5635SKent Overstreet keys += r[nodes++].keys; 1393cafe5635SKent Overstreet 1394cafe5635SKent Overstreet blocks = btree_default_blocks(b->c) * 2 / 3; 1395cafe5635SKent Overstreet 1396cafe5635SKent Overstreet if (nodes < 2 || 1397a85e968eSKent Overstreet __set_blocks(b->keys.set[0].data, keys, 1398ee811287SKent Overstreet block_bytes(b->c)) > blocks * (nodes - 1)) 1399a1f0358bSKent Overstreet return 0; 1400cafe5635SKent Overstreet 1401a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 14020a63b66dSKent Overstreet new_nodes[i] = btree_node_alloc_replacement(r[i].b, NULL); 1403a1f0358bSKent Overstreet if (IS_ERR_OR_NULL(new_nodes[i])) 1404a1f0358bSKent Overstreet goto out_nocoalesce; 1405cafe5635SKent Overstreet } 1406cafe5635SKent Overstreet 14070a63b66dSKent Overstreet /* 14080a63b66dSKent Overstreet * We have to check the reserve here, after we've allocated our new 14090a63b66dSKent Overstreet * nodes, to make sure the insert below will succeed - we also check 14100a63b66dSKent Overstreet * before as an optimization to potentially avoid a bunch of expensive 14110a63b66dSKent Overstreet * allocs/sorts 14120a63b66dSKent Overstreet */ 14130a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 14140a63b66dSKent Overstreet goto out_nocoalesce; 14150a63b66dSKent Overstreet 14162a285686SKent Overstreet for (i = 0; i < nodes; i++) 14172a285686SKent Overstreet mutex_lock(&new_nodes[i]->write_lock); 14182a285686SKent Overstreet 1419cafe5635SKent Overstreet for (i = nodes - 1; i > 0; --i) { 1420ee811287SKent Overstreet struct bset *n1 = btree_bset_first(new_nodes[i]); 1421ee811287SKent Overstreet struct bset *n2 = btree_bset_first(new_nodes[i - 1]); 1422cafe5635SKent Overstreet struct bkey *k, *last = NULL; 1423cafe5635SKent Overstreet 1424cafe5635SKent Overstreet keys = 0; 1425cafe5635SKent Overstreet 1426a1f0358bSKent Overstreet if (i > 1) { 1427cafe5635SKent Overstreet for (k = n2->start; 1428fafff81cSKent Overstreet k < bset_bkey_last(n2); 1429cafe5635SKent Overstreet k = bkey_next(k)) { 1430cafe5635SKent Overstreet if (__set_blocks(n1, n1->keys + keys + 1431ee811287SKent Overstreet bkey_u64s(k), 1432ee811287SKent Overstreet block_bytes(b->c)) > blocks) 1433cafe5635SKent Overstreet break; 1434cafe5635SKent Overstreet 1435cafe5635SKent Overstreet last = k; 1436cafe5635SKent Overstreet keys += bkey_u64s(k); 1437cafe5635SKent Overstreet } 1438a1f0358bSKent Overstreet } else { 1439a1f0358bSKent Overstreet /* 1440a1f0358bSKent Overstreet * Last node we're not getting rid of - we're getting 1441a1f0358bSKent Overstreet * rid of the node at r[0]. Have to try and fit all of 1442a1f0358bSKent Overstreet * the remaining keys into this node; we can't ensure 1443a1f0358bSKent Overstreet * they will always fit due to rounding and variable 1444a1f0358bSKent Overstreet * length keys (shouldn't be possible in practice, 1445a1f0358bSKent Overstreet * though) 1446a1f0358bSKent Overstreet */ 1447a1f0358bSKent Overstreet if (__set_blocks(n1, n1->keys + n2->keys, 1448ee811287SKent Overstreet block_bytes(b->c)) > 1449ee811287SKent Overstreet btree_blocks(new_nodes[i])) 1450a1f0358bSKent Overstreet goto out_nocoalesce; 1451a1f0358bSKent Overstreet 1452a1f0358bSKent Overstreet keys = n2->keys; 1453a1f0358bSKent Overstreet /* Take the key of the node we're getting rid of */ 1454a1f0358bSKent Overstreet last = &r->b->key; 1455a1f0358bSKent Overstreet } 1456cafe5635SKent Overstreet 1457ee811287SKent Overstreet BUG_ON(__set_blocks(n1, n1->keys + keys, block_bytes(b->c)) > 1458ee811287SKent Overstreet btree_blocks(new_nodes[i])); 1459cafe5635SKent Overstreet 1460a1f0358bSKent Overstreet if (last) 1461a1f0358bSKent Overstreet bkey_copy_key(&new_nodes[i]->key, last); 1462cafe5635SKent Overstreet 1463fafff81cSKent Overstreet memcpy(bset_bkey_last(n1), 1464cafe5635SKent Overstreet n2->start, 1465fafff81cSKent Overstreet (void *) bset_bkey_idx(n2, keys) - (void *) n2->start); 1466cafe5635SKent Overstreet 1467cafe5635SKent Overstreet n1->keys += keys; 1468a1f0358bSKent Overstreet r[i].keys = n1->keys; 1469cafe5635SKent Overstreet 1470cafe5635SKent Overstreet memmove(n2->start, 1471fafff81cSKent Overstreet bset_bkey_idx(n2, keys), 1472fafff81cSKent Overstreet (void *) bset_bkey_last(n2) - 1473fafff81cSKent Overstreet (void *) bset_bkey_idx(n2, keys)); 1474cafe5635SKent Overstreet 1475cafe5635SKent Overstreet n2->keys -= keys; 1476cafe5635SKent Overstreet 14770a63b66dSKent Overstreet if (__bch_keylist_realloc(&keylist, 1478085d2a3dSKent Overstreet bkey_u64s(&new_nodes[i]->key))) 1479a1f0358bSKent Overstreet goto out_nocoalesce; 1480a1f0358bSKent Overstreet 1481a1f0358bSKent Overstreet bch_btree_node_write(new_nodes[i], &cl); 14820a63b66dSKent Overstreet bch_keylist_add(&keylist, &new_nodes[i]->key); 1483cafe5635SKent Overstreet } 1484cafe5635SKent Overstreet 14852a285686SKent Overstreet for (i = 0; i < nodes; i++) 14862a285686SKent Overstreet mutex_unlock(&new_nodes[i]->write_lock); 14872a285686SKent Overstreet 148805335cffSKent Overstreet closure_sync(&cl); 148905335cffSKent Overstreet 149005335cffSKent Overstreet /* We emptied out this node */ 149105335cffSKent Overstreet BUG_ON(btree_bset_first(new_nodes[0])->keys); 149205335cffSKent Overstreet btree_node_free(new_nodes[0]); 149305335cffSKent Overstreet rw_unlock(true, new_nodes[0]); 1494400ffaa2SSlava Pestov new_nodes[0] = NULL; 149505335cffSKent Overstreet 1496a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 14970a63b66dSKent Overstreet if (__bch_keylist_realloc(&keylist, bkey_u64s(&r[i].b->key))) 1498a1f0358bSKent Overstreet goto out_nocoalesce; 1499a1f0358bSKent Overstreet 15000a63b66dSKent Overstreet make_btree_freeing_key(r[i].b, keylist.top); 15010a63b66dSKent Overstreet bch_keylist_push(&keylist); 1502a1f0358bSKent Overstreet } 1503a1f0358bSKent Overstreet 15040a63b66dSKent Overstreet bch_btree_insert_node(b, op, &keylist, NULL, NULL); 15050a63b66dSKent Overstreet BUG_ON(!bch_keylist_empty(&keylist)); 1506a1f0358bSKent Overstreet 1507a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) { 1508a1f0358bSKent Overstreet btree_node_free(r[i].b); 1509a1f0358bSKent Overstreet rw_unlock(true, r[i].b); 1510a1f0358bSKent Overstreet 1511a1f0358bSKent Overstreet r[i].b = new_nodes[i]; 1512a1f0358bSKent Overstreet } 1513a1f0358bSKent Overstreet 1514a1f0358bSKent Overstreet memmove(r, r + 1, sizeof(r[0]) * (nodes - 1)); 1515a1f0358bSKent Overstreet r[nodes - 1].b = ERR_PTR(-EINTR); 1516cafe5635SKent Overstreet 1517c37511b8SKent Overstreet trace_bcache_btree_gc_coalesce(nodes); 1518cafe5635SKent Overstreet gc->nodes--; 1519cafe5635SKent Overstreet 15200a63b66dSKent Overstreet bch_keylist_free(&keylist); 15210a63b66dSKent Overstreet 1522a1f0358bSKent Overstreet /* Invalidated our iterator */ 1523a1f0358bSKent Overstreet return -EINTR; 1524a1f0358bSKent Overstreet 1525a1f0358bSKent Overstreet out_nocoalesce: 1526a1f0358bSKent Overstreet closure_sync(&cl); 1527a1f0358bSKent Overstreet 15280a63b66dSKent Overstreet while ((k = bch_keylist_pop(&keylist))) 1529a1f0358bSKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1530a1f0358bSKent Overstreet atomic_dec(&b->c->prio_blocked); 1531f16277caSShenghui Wang bch_keylist_free(&keylist); 1532a1f0358bSKent Overstreet 1533a1f0358bSKent Overstreet for (i = 0; i < nodes; i++) 1534a1f0358bSKent Overstreet if (!IS_ERR_OR_NULL(new_nodes[i])) { 1535a1f0358bSKent Overstreet btree_node_free(new_nodes[i]); 1536a1f0358bSKent Overstreet rw_unlock(true, new_nodes[i]); 1537a1f0358bSKent Overstreet } 1538a1f0358bSKent Overstreet return 0; 1539a1f0358bSKent Overstreet } 1540a1f0358bSKent Overstreet 15410a63b66dSKent Overstreet static int btree_gc_rewrite_node(struct btree *b, struct btree_op *op, 15420a63b66dSKent Overstreet struct btree *replace) 15430a63b66dSKent Overstreet { 15440a63b66dSKent Overstreet struct keylist keys; 15450a63b66dSKent Overstreet struct btree *n; 15460a63b66dSKent Overstreet 15470a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) 15480a63b66dSKent Overstreet return 0; 15490a63b66dSKent Overstreet 15500a63b66dSKent Overstreet n = btree_node_alloc_replacement(replace, NULL); 15510a63b66dSKent Overstreet 15520a63b66dSKent Overstreet /* recheck reserve after allocating replacement node */ 15530a63b66dSKent Overstreet if (btree_check_reserve(b, NULL)) { 15540a63b66dSKent Overstreet btree_node_free(n); 15550a63b66dSKent Overstreet rw_unlock(true, n); 15560a63b66dSKent Overstreet return 0; 15570a63b66dSKent Overstreet } 15580a63b66dSKent Overstreet 15590a63b66dSKent Overstreet bch_btree_node_write_sync(n); 15600a63b66dSKent Overstreet 15610a63b66dSKent Overstreet bch_keylist_init(&keys); 15620a63b66dSKent Overstreet bch_keylist_add(&keys, &n->key); 15630a63b66dSKent Overstreet 15640a63b66dSKent Overstreet make_btree_freeing_key(replace, keys.top); 15650a63b66dSKent Overstreet bch_keylist_push(&keys); 15660a63b66dSKent Overstreet 15670a63b66dSKent Overstreet bch_btree_insert_node(b, op, &keys, NULL, NULL); 15680a63b66dSKent Overstreet BUG_ON(!bch_keylist_empty(&keys)); 15690a63b66dSKent Overstreet 15700a63b66dSKent Overstreet btree_node_free(replace); 15710a63b66dSKent Overstreet rw_unlock(true, n); 15720a63b66dSKent Overstreet 15730a63b66dSKent Overstreet /* Invalidated our iterator */ 15740a63b66dSKent Overstreet return -EINTR; 15750a63b66dSKent Overstreet } 15760a63b66dSKent Overstreet 15776f10f7d1SColy Li static unsigned int btree_gc_count_keys(struct btree *b) 1578a1f0358bSKent Overstreet { 1579a1f0358bSKent Overstreet struct bkey *k; 1580a1f0358bSKent Overstreet struct btree_iter iter; 15816f10f7d1SColy Li unsigned int ret = 0; 1582a1f0358bSKent Overstreet 1583c052dd9aSKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad) 1584a1f0358bSKent Overstreet ret += bkey_u64s(k); 1585a1f0358bSKent Overstreet 1586a1f0358bSKent Overstreet return ret; 1587cafe5635SKent Overstreet } 1588cafe5635SKent Overstreet 15897f4a59deSTang Junhui static size_t btree_gc_min_nodes(struct cache_set *c) 15907f4a59deSTang Junhui { 15917f4a59deSTang Junhui size_t min_nodes; 15927f4a59deSTang Junhui 15937f4a59deSTang Junhui /* 15947f4a59deSTang Junhui * Since incremental GC would stop 100ms when front 15957f4a59deSTang Junhui * side I/O comes, so when there are many btree nodes, 15967f4a59deSTang Junhui * if GC only processes constant (100) nodes each time, 15977f4a59deSTang Junhui * GC would last a long time, and the front side I/Os 15987f4a59deSTang Junhui * would run out of the buckets (since no new bucket 15997f4a59deSTang Junhui * can be allocated during GC), and be blocked again. 16007f4a59deSTang Junhui * So GC should not process constant nodes, but varied 16017f4a59deSTang Junhui * nodes according to the number of btree nodes, which 16027f4a59deSTang Junhui * realized by dividing GC into constant(100) times, 16037f4a59deSTang Junhui * so when there are many btree nodes, GC can process 16047f4a59deSTang Junhui * more nodes each time, otherwise, GC will process less 16057f4a59deSTang Junhui * nodes each time (but no less than MIN_GC_NODES) 16067f4a59deSTang Junhui */ 16077f4a59deSTang Junhui min_nodes = c->gc_stats.nodes / MAX_GC_TIMES; 16087f4a59deSTang Junhui if (min_nodes < MIN_GC_NODES) 16097f4a59deSTang Junhui min_nodes = MIN_GC_NODES; 16107f4a59deSTang Junhui 16117f4a59deSTang Junhui return min_nodes; 16127f4a59deSTang Junhui } 16137f4a59deSTang Junhui 16147f4a59deSTang Junhui 1615cafe5635SKent Overstreet static int btree_gc_recurse(struct btree *b, struct btree_op *op, 1616cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1617cafe5635SKent Overstreet { 1618a1f0358bSKent Overstreet int ret = 0; 1619a1f0358bSKent Overstreet bool should_rewrite; 1620a1f0358bSKent Overstreet struct bkey *k; 1621a1f0358bSKent Overstreet struct btree_iter iter; 1622cafe5635SKent Overstreet struct gc_merge_info r[GC_MERGE_NODES]; 16232a285686SKent Overstreet struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1; 1624cafe5635SKent Overstreet 1625c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done); 1626cafe5635SKent Overstreet 16272a285686SKent Overstreet for (i = r; i < r + ARRAY_SIZE(r); i++) 16282a285686SKent Overstreet i->b = ERR_PTR(-EINTR); 1629cafe5635SKent Overstreet 1630a1f0358bSKent Overstreet while (1) { 1631a85e968eSKent Overstreet k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad); 1632a1f0358bSKent Overstreet if (k) { 16330a63b66dSKent Overstreet r->b = bch_btree_node_get(b->c, op, k, b->level - 1, 16342452cc89SSlava Pestov true, b); 1635cafe5635SKent Overstreet if (IS_ERR(r->b)) { 1636cafe5635SKent Overstreet ret = PTR_ERR(r->b); 1637cafe5635SKent Overstreet break; 1638cafe5635SKent Overstreet } 1639cafe5635SKent Overstreet 1640a1f0358bSKent Overstreet r->keys = btree_gc_count_keys(r->b); 1641cafe5635SKent Overstreet 16420a63b66dSKent Overstreet ret = btree_gc_coalesce(b, op, gc, r); 1643a1f0358bSKent Overstreet if (ret) 1644cafe5635SKent Overstreet break; 1645cafe5635SKent Overstreet } 1646cafe5635SKent Overstreet 1647a1f0358bSKent Overstreet if (!last->b) 1648a1f0358bSKent Overstreet break; 1649cafe5635SKent Overstreet 1650a1f0358bSKent Overstreet if (!IS_ERR(last->b)) { 1651a1f0358bSKent Overstreet should_rewrite = btree_gc_mark_node(last->b, gc); 16520a63b66dSKent Overstreet if (should_rewrite) { 16530a63b66dSKent Overstreet ret = btree_gc_rewrite_node(b, op, last->b); 16540a63b66dSKent Overstreet if (ret) 1655a1f0358bSKent Overstreet break; 1656a1f0358bSKent Overstreet } 1657a1f0358bSKent Overstreet 1658a1f0358bSKent Overstreet if (last->b->level) { 1659a1f0358bSKent Overstreet ret = btree_gc_recurse(last->b, op, writes, gc); 1660a1f0358bSKent Overstreet if (ret) 1661a1f0358bSKent Overstreet break; 1662a1f0358bSKent Overstreet } 1663a1f0358bSKent Overstreet 1664a1f0358bSKent Overstreet bkey_copy_key(&b->c->gc_done, &last->b->key); 1665a1f0358bSKent Overstreet 1666a1f0358bSKent Overstreet /* 1667a1f0358bSKent Overstreet * Must flush leaf nodes before gc ends, since replace 1668a1f0358bSKent Overstreet * operations aren't journalled 1669cafe5635SKent Overstreet */ 16702a285686SKent Overstreet mutex_lock(&last->b->write_lock); 1671a1f0358bSKent Overstreet if (btree_node_dirty(last->b)) 1672a1f0358bSKent Overstreet bch_btree_node_write(last->b, writes); 16732a285686SKent Overstreet mutex_unlock(&last->b->write_lock); 1674a1f0358bSKent Overstreet rw_unlock(true, last->b); 1675a1f0358bSKent Overstreet } 1676a1f0358bSKent Overstreet 1677a1f0358bSKent Overstreet memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1)); 1678a1f0358bSKent Overstreet r->b = NULL; 1679a1f0358bSKent Overstreet 16805c25c4fcSTang Junhui if (atomic_read(&b->c->search_inflight) && 16817f4a59deSTang Junhui gc->nodes >= gc->nodes_pre + btree_gc_min_nodes(b->c)) { 16825c25c4fcSTang Junhui gc->nodes_pre = gc->nodes; 16835c25c4fcSTang Junhui ret = -EAGAIN; 16845c25c4fcSTang Junhui break; 16855c25c4fcSTang Junhui } 16865c25c4fcSTang Junhui 1687cafe5635SKent Overstreet if (need_resched()) { 1688cafe5635SKent Overstreet ret = -EAGAIN; 1689cafe5635SKent Overstreet break; 1690cafe5635SKent Overstreet } 1691cafe5635SKent Overstreet } 1692cafe5635SKent Overstreet 16932a285686SKent Overstreet for (i = r; i < r + ARRAY_SIZE(r); i++) 16942a285686SKent Overstreet if (!IS_ERR_OR_NULL(i->b)) { 16952a285686SKent Overstreet mutex_lock(&i->b->write_lock); 16962a285686SKent Overstreet if (btree_node_dirty(i->b)) 16972a285686SKent Overstreet bch_btree_node_write(i->b, writes); 16982a285686SKent Overstreet mutex_unlock(&i->b->write_lock); 16992a285686SKent Overstreet rw_unlock(true, i->b); 1700a1f0358bSKent Overstreet } 1701cafe5635SKent Overstreet 1702cafe5635SKent Overstreet return ret; 1703cafe5635SKent Overstreet } 1704cafe5635SKent Overstreet 1705cafe5635SKent Overstreet static int bch_btree_gc_root(struct btree *b, struct btree_op *op, 1706cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1707cafe5635SKent Overstreet { 1708cafe5635SKent Overstreet struct btree *n = NULL; 1709a1f0358bSKent Overstreet int ret = 0; 1710a1f0358bSKent Overstreet bool should_rewrite; 1711cafe5635SKent Overstreet 1712a1f0358bSKent Overstreet should_rewrite = btree_gc_mark_node(b, gc); 1713a1f0358bSKent Overstreet if (should_rewrite) { 17140a63b66dSKent Overstreet n = btree_node_alloc_replacement(b, NULL); 1715cafe5635SKent Overstreet 1716cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 1717a1f0358bSKent Overstreet bch_btree_node_write_sync(n); 17182a285686SKent Overstreet 1719a1f0358bSKent Overstreet bch_btree_set_root(n); 1720a1f0358bSKent Overstreet btree_node_free(b); 1721a1f0358bSKent Overstreet rw_unlock(true, n); 1722a1f0358bSKent Overstreet 1723a1f0358bSKent Overstreet return -EINTR; 1724cafe5635SKent Overstreet } 1725a1f0358bSKent Overstreet } 1726a1f0358bSKent Overstreet 1727487dded8SKent Overstreet __bch_btree_mark_key(b->c, b->level + 1, &b->key); 1728487dded8SKent Overstreet 1729a1f0358bSKent Overstreet if (b->level) { 1730a1f0358bSKent Overstreet ret = btree_gc_recurse(b, op, writes, gc); 1731a1f0358bSKent Overstreet if (ret) 1732a1f0358bSKent Overstreet return ret; 1733a1f0358bSKent Overstreet } 1734a1f0358bSKent Overstreet 1735a1f0358bSKent Overstreet bkey_copy_key(&b->c->gc_done, &b->key); 1736cafe5635SKent Overstreet 1737cafe5635SKent Overstreet return ret; 1738cafe5635SKent Overstreet } 1739cafe5635SKent Overstreet 1740cafe5635SKent Overstreet static void btree_gc_start(struct cache_set *c) 1741cafe5635SKent Overstreet { 1742cafe5635SKent Overstreet struct cache *ca; 1743cafe5635SKent Overstreet struct bucket *b; 17446f10f7d1SColy Li unsigned int i; 1745cafe5635SKent Overstreet 1746cafe5635SKent Overstreet if (!c->gc_mark_valid) 1747cafe5635SKent Overstreet return; 1748cafe5635SKent Overstreet 1749cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1750cafe5635SKent Overstreet 1751cafe5635SKent Overstreet c->gc_mark_valid = 0; 1752cafe5635SKent Overstreet c->gc_done = ZERO_KEY; 1753cafe5635SKent Overstreet 1754cafe5635SKent Overstreet for_each_cache(ca, c, i) 1755cafe5635SKent Overstreet for_each_bucket(b, ca) { 17563a2fd9d5SKent Overstreet b->last_gc = b->gen; 175729ebf465SKent Overstreet if (!atomic_read(&b->pin)) { 17584fe6a816SKent Overstreet SET_GC_MARK(b, 0); 175929ebf465SKent Overstreet SET_GC_SECTORS_USED(b, 0); 176029ebf465SKent Overstreet } 1761cafe5635SKent Overstreet } 1762cafe5635SKent Overstreet 1763cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1764cafe5635SKent Overstreet } 1765cafe5635SKent Overstreet 1766d44c2f9eSTang Junhui static void bch_btree_gc_finish(struct cache_set *c) 1767cafe5635SKent Overstreet { 1768cafe5635SKent Overstreet struct bucket *b; 1769cafe5635SKent Overstreet struct cache *ca; 17706f10f7d1SColy Li unsigned int i; 1771cafe5635SKent Overstreet 1772cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1773cafe5635SKent Overstreet 1774cafe5635SKent Overstreet set_gc_sectors(c); 1775cafe5635SKent Overstreet c->gc_mark_valid = 1; 1776cafe5635SKent Overstreet c->need_gc = 0; 1777cafe5635SKent Overstreet 1778cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&c->uuid_bucket); i++) 1779cafe5635SKent Overstreet SET_GC_MARK(PTR_BUCKET(c, &c->uuid_bucket, i), 1780cafe5635SKent Overstreet GC_MARK_METADATA); 1781cafe5635SKent Overstreet 1782bf0a628aSNicholas Swenson /* don't reclaim buckets to which writeback keys point */ 1783bf0a628aSNicholas Swenson rcu_read_lock(); 17842831231dSColy Li for (i = 0; i < c->devices_max_used; i++) { 1785bf0a628aSNicholas Swenson struct bcache_device *d = c->devices[i]; 1786bf0a628aSNicholas Swenson struct cached_dev *dc; 1787bf0a628aSNicholas Swenson struct keybuf_key *w, *n; 17886f10f7d1SColy Li unsigned int j; 1789bf0a628aSNicholas Swenson 1790bf0a628aSNicholas Swenson if (!d || UUID_FLASH_ONLY(&c->uuids[i])) 1791bf0a628aSNicholas Swenson continue; 1792bf0a628aSNicholas Swenson dc = container_of(d, struct cached_dev, disk); 1793bf0a628aSNicholas Swenson 1794bf0a628aSNicholas Swenson spin_lock(&dc->writeback_keys.lock); 1795bf0a628aSNicholas Swenson rbtree_postorder_for_each_entry_safe(w, n, 1796bf0a628aSNicholas Swenson &dc->writeback_keys.keys, node) 1797bf0a628aSNicholas Swenson for (j = 0; j < KEY_PTRS(&w->key); j++) 1798bf0a628aSNicholas Swenson SET_GC_MARK(PTR_BUCKET(c, &w->key, j), 1799bf0a628aSNicholas Swenson GC_MARK_DIRTY); 1800bf0a628aSNicholas Swenson spin_unlock(&dc->writeback_keys.lock); 1801bf0a628aSNicholas Swenson } 1802bf0a628aSNicholas Swenson rcu_read_unlock(); 1803bf0a628aSNicholas Swenson 1804d44c2f9eSTang Junhui c->avail_nbuckets = 0; 1805cafe5635SKent Overstreet for_each_cache(ca, c, i) { 1806cafe5635SKent Overstreet uint64_t *i; 1807cafe5635SKent Overstreet 1808cafe5635SKent Overstreet ca->invalidate_needs_gc = 0; 1809cafe5635SKent Overstreet 1810cafe5635SKent Overstreet for (i = ca->sb.d; i < ca->sb.d + ca->sb.keys; i++) 1811cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1812cafe5635SKent Overstreet 1813cafe5635SKent Overstreet for (i = ca->prio_buckets; 1814cafe5635SKent Overstreet i < ca->prio_buckets + prio_buckets(ca) * 2; i++) 1815cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1816cafe5635SKent Overstreet 1817cafe5635SKent Overstreet for_each_bucket(b, ca) { 1818cafe5635SKent Overstreet c->need_gc = max(c->need_gc, bucket_gc_gen(b)); 1819cafe5635SKent Overstreet 18204fe6a816SKent Overstreet if (atomic_read(&b->pin)) 18214fe6a816SKent Overstreet continue; 18224fe6a816SKent Overstreet 18234fe6a816SKent Overstreet BUG_ON(!GC_MARK(b) && GC_SECTORS_USED(b)); 18244fe6a816SKent Overstreet 18254fe6a816SKent Overstreet if (!GC_MARK(b) || GC_MARK(b) == GC_MARK_RECLAIMABLE) 1826d44c2f9eSTang Junhui c->avail_nbuckets++; 1827cafe5635SKent Overstreet } 1828cafe5635SKent Overstreet } 1829cafe5635SKent Overstreet 1830cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1831cafe5635SKent Overstreet } 1832cafe5635SKent Overstreet 183372a44517SKent Overstreet static void bch_btree_gc(struct cache_set *c) 1834cafe5635SKent Overstreet { 1835cafe5635SKent Overstreet int ret; 1836cafe5635SKent Overstreet struct gc_stat stats; 1837cafe5635SKent Overstreet struct closure writes; 1838cafe5635SKent Overstreet struct btree_op op; 1839cafe5635SKent Overstreet uint64_t start_time = local_clock(); 184057943511SKent Overstreet 1841c37511b8SKent Overstreet trace_bcache_gc_start(c); 1842cafe5635SKent Overstreet 1843cafe5635SKent Overstreet memset(&stats, 0, sizeof(struct gc_stat)); 1844cafe5635SKent Overstreet closure_init_stack(&writes); 1845b54d6934SKent Overstreet bch_btree_op_init(&op, SHRT_MAX); 1846cafe5635SKent Overstreet 1847cafe5635SKent Overstreet btree_gc_start(c); 1848cafe5635SKent Overstreet 1849771f393eSColy Li /* if CACHE_SET_IO_DISABLE set, gc thread should stop too */ 1850a1f0358bSKent Overstreet do { 1851cafe5635SKent Overstreet ret = btree_root(gc_root, c, &op, &writes, &stats); 1852cafe5635SKent Overstreet closure_sync(&writes); 1853c5f1e5adSKent Overstreet cond_resched(); 1854cafe5635SKent Overstreet 18555c25c4fcSTang Junhui if (ret == -EAGAIN) 18565c25c4fcSTang Junhui schedule_timeout_interruptible(msecs_to_jiffies 18575c25c4fcSTang Junhui (GC_SLEEP_MS)); 18585c25c4fcSTang Junhui else if (ret) 1859cafe5635SKent Overstreet pr_warn("gc failed!"); 1860771f393eSColy Li } while (ret && !test_bit(CACHE_SET_IO_DISABLE, &c->flags)); 1861cafe5635SKent Overstreet 1862d44c2f9eSTang Junhui bch_btree_gc_finish(c); 186357943511SKent Overstreet wake_up_allocators(c); 186457943511SKent Overstreet 1865169ef1cfSKent Overstreet bch_time_stats_update(&c->btree_gc_time, start_time); 1866cafe5635SKent Overstreet 1867cafe5635SKent Overstreet stats.key_bytes *= sizeof(uint64_t); 1868cafe5635SKent Overstreet stats.data <<= 9; 1869d44c2f9eSTang Junhui bch_update_bucket_in_use(c, &stats); 1870cafe5635SKent Overstreet memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat)); 1871cafe5635SKent Overstreet 1872c37511b8SKent Overstreet trace_bcache_gc_end(c); 1873cafe5635SKent Overstreet 187472a44517SKent Overstreet bch_moving_gc(c); 1875cafe5635SKent Overstreet } 1876cafe5635SKent Overstreet 1877be628be0SKent Overstreet static bool gc_should_run(struct cache_set *c) 1878cafe5635SKent Overstreet { 1879a1f0358bSKent Overstreet struct cache *ca; 18806f10f7d1SColy Li unsigned int i; 188172a44517SKent Overstreet 1882be628be0SKent Overstreet for_each_cache(ca, c, i) 1883be628be0SKent Overstreet if (ca->invalidate_needs_gc) 1884be628be0SKent Overstreet return true; 188572a44517SKent Overstreet 1886be628be0SKent Overstreet if (atomic_read(&c->sectors_to_gc) < 0) 1887be628be0SKent Overstreet return true; 1888be628be0SKent Overstreet 1889be628be0SKent Overstreet return false; 1890be628be0SKent Overstreet } 1891be628be0SKent Overstreet 1892be628be0SKent Overstreet static int bch_gc_thread(void *arg) 1893be628be0SKent Overstreet { 1894be628be0SKent Overstreet struct cache_set *c = arg; 1895be628be0SKent Overstreet 1896be628be0SKent Overstreet while (1) { 1897be628be0SKent Overstreet wait_event_interruptible(c->gc_wait, 1898771f393eSColy Li kthread_should_stop() || 1899771f393eSColy Li test_bit(CACHE_SET_IO_DISABLE, &c->flags) || 1900771f393eSColy Li gc_should_run(c)); 1901be628be0SKent Overstreet 1902771f393eSColy Li if (kthread_should_stop() || 1903771f393eSColy Li test_bit(CACHE_SET_IO_DISABLE, &c->flags)) 190472a44517SKent Overstreet break; 190572a44517SKent Overstreet 1906be628be0SKent Overstreet set_gc_sectors(c); 1907be628be0SKent Overstreet bch_btree_gc(c); 190872a44517SKent Overstreet } 190972a44517SKent Overstreet 1910771f393eSColy Li wait_for_kthread_stop(); 191172a44517SKent Overstreet return 0; 191272a44517SKent Overstreet } 191372a44517SKent Overstreet 191472a44517SKent Overstreet int bch_gc_thread_start(struct cache_set *c) 191572a44517SKent Overstreet { 1916be628be0SKent Overstreet c->gc_thread = kthread_run(bch_gc_thread, c, "bcache_gc"); 19179d134117SVasyl Gomonovych return PTR_ERR_OR_ZERO(c->gc_thread); 1918cafe5635SKent Overstreet } 1919cafe5635SKent Overstreet 1920cafe5635SKent Overstreet /* Initial partial gc */ 1921cafe5635SKent Overstreet 1922487dded8SKent Overstreet static int bch_btree_check_recurse(struct btree *b, struct btree_op *op) 1923cafe5635SKent Overstreet { 192450310164SKent Overstreet int ret = 0; 192550310164SKent Overstreet struct bkey *k, *p = NULL; 1926cafe5635SKent Overstreet struct btree_iter iter; 1927cafe5635SKent Overstreet 1928487dded8SKent Overstreet for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) 1929487dded8SKent Overstreet bch_initial_mark_key(b->c, b->level, k); 1930cafe5635SKent Overstreet 1931487dded8SKent Overstreet bch_initial_mark_key(b->c, b->level + 1, &b->key); 1932cafe5635SKent Overstreet 1933cafe5635SKent Overstreet if (b->level) { 1934c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, NULL); 1935cafe5635SKent Overstreet 193650310164SKent Overstreet do { 1937a85e968eSKent Overstreet k = bch_btree_iter_next_filter(&iter, &b->keys, 1938a85e968eSKent Overstreet bch_ptr_bad); 19397f4a59deSTang Junhui if (k) { 19402452cc89SSlava Pestov btree_node_prefetch(b, k); 19417f4a59deSTang Junhui /* 19427f4a59deSTang Junhui * initiallize c->gc_stats.nodes 19437f4a59deSTang Junhui * for incremental GC 19447f4a59deSTang Junhui */ 19457f4a59deSTang Junhui b->c->gc_stats.nodes++; 19467f4a59deSTang Junhui } 194750310164SKent Overstreet 1948cafe5635SKent Overstreet if (p) 1949487dded8SKent Overstreet ret = btree(check_recurse, p, b, op); 1950cafe5635SKent Overstreet 195150310164SKent Overstreet p = k; 195250310164SKent Overstreet } while (p && !ret); 1953cafe5635SKent Overstreet } 1954cafe5635SKent Overstreet 1955487dded8SKent Overstreet return ret; 1956cafe5635SKent Overstreet } 1957cafe5635SKent Overstreet 1958c18536a7SKent Overstreet int bch_btree_check(struct cache_set *c) 1959cafe5635SKent Overstreet { 1960c18536a7SKent Overstreet struct btree_op op; 1961cafe5635SKent Overstreet 1962b54d6934SKent Overstreet bch_btree_op_init(&op, SHRT_MAX); 1963cafe5635SKent Overstreet 1964487dded8SKent Overstreet return btree_root(check_recurse, c, &op); 1965cafe5635SKent Overstreet } 1966cafe5635SKent Overstreet 19672531d9eeSKent Overstreet void bch_initial_gc_finish(struct cache_set *c) 19682531d9eeSKent Overstreet { 19692531d9eeSKent Overstreet struct cache *ca; 19702531d9eeSKent Overstreet struct bucket *b; 19716f10f7d1SColy Li unsigned int i; 19722531d9eeSKent Overstreet 19732531d9eeSKent Overstreet bch_btree_gc_finish(c); 19742531d9eeSKent Overstreet 19752531d9eeSKent Overstreet mutex_lock(&c->bucket_lock); 19762531d9eeSKent Overstreet 19772531d9eeSKent Overstreet /* 19782531d9eeSKent Overstreet * We need to put some unused buckets directly on the prio freelist in 19792531d9eeSKent Overstreet * order to get the allocator thread started - it needs freed buckets in 19802531d9eeSKent Overstreet * order to rewrite the prios and gens, and it needs to rewrite prios 19812531d9eeSKent Overstreet * and gens in order to free buckets. 19822531d9eeSKent Overstreet * 19832531d9eeSKent Overstreet * This is only safe for buckets that have no live data in them, which 19842531d9eeSKent Overstreet * there should always be some of. 19852531d9eeSKent Overstreet */ 19862531d9eeSKent Overstreet for_each_cache(ca, c, i) { 19872531d9eeSKent Overstreet for_each_bucket(b, ca) { 1988682811b3STang Junhui if (fifo_full(&ca->free[RESERVE_PRIO]) && 1989682811b3STang Junhui fifo_full(&ca->free[RESERVE_BTREE])) 19902531d9eeSKent Overstreet break; 19912531d9eeSKent Overstreet 19922531d9eeSKent Overstreet if (bch_can_invalidate_bucket(ca, b) && 19932531d9eeSKent Overstreet !GC_MARK(b)) { 19942531d9eeSKent Overstreet __bch_invalidate_one_bucket(ca, b); 1995682811b3STang Junhui if (!fifo_push(&ca->free[RESERVE_PRIO], 1996682811b3STang Junhui b - ca->buckets)) 1997682811b3STang Junhui fifo_push(&ca->free[RESERVE_BTREE], 19982531d9eeSKent Overstreet b - ca->buckets); 19992531d9eeSKent Overstreet } 20002531d9eeSKent Overstreet } 20012531d9eeSKent Overstreet } 20022531d9eeSKent Overstreet 20032531d9eeSKent Overstreet mutex_unlock(&c->bucket_lock); 20042531d9eeSKent Overstreet } 20052531d9eeSKent Overstreet 2006cafe5635SKent Overstreet /* Btree insertion */ 2007cafe5635SKent Overstreet 2008829a60b9SKent Overstreet static bool btree_insert_key(struct btree *b, struct bkey *k, 20091b207d80SKent Overstreet struct bkey *replace_key) 2010cafe5635SKent Overstreet { 20116f10f7d1SColy Li unsigned int status; 2012cafe5635SKent Overstreet 2013cafe5635SKent Overstreet BUG_ON(bkey_cmp(k, &b->key) > 0); 2014cafe5635SKent Overstreet 2015829a60b9SKent Overstreet status = bch_btree_insert_key(&b->keys, k, replace_key); 2016829a60b9SKent Overstreet if (status != BTREE_INSERT_STATUS_NO_INSERT) { 2017dc9d98d6SKent Overstreet bch_check_keys(&b->keys, "%u for %s", status, 20181b207d80SKent Overstreet replace_key ? "replace" : "insert"); 2019cafe5635SKent Overstreet 2020829a60b9SKent Overstreet trace_bcache_btree_insert_key(b, k, replace_key != NULL, 2021829a60b9SKent Overstreet status); 2022cafe5635SKent Overstreet return true; 2023829a60b9SKent Overstreet } else 2024829a60b9SKent Overstreet return false; 2025cafe5635SKent Overstreet } 2026cafe5635SKent Overstreet 202759158fdeSKent Overstreet static size_t insert_u64s_remaining(struct btree *b) 202859158fdeSKent Overstreet { 20293572324aSKent Overstreet long ret = bch_btree_keys_u64s_remaining(&b->keys); 203059158fdeSKent Overstreet 203159158fdeSKent Overstreet /* 203259158fdeSKent Overstreet * Might land in the middle of an existing extent and have to split it 203359158fdeSKent Overstreet */ 203459158fdeSKent Overstreet if (b->keys.ops->is_extents) 203559158fdeSKent Overstreet ret -= KEY_MAX_U64S; 203659158fdeSKent Overstreet 203759158fdeSKent Overstreet return max(ret, 0L); 203859158fdeSKent Overstreet } 203959158fdeSKent Overstreet 204026c949f8SKent Overstreet static bool bch_btree_insert_keys(struct btree *b, struct btree_op *op, 20411b207d80SKent Overstreet struct keylist *insert_keys, 20421b207d80SKent Overstreet struct bkey *replace_key) 2043cafe5635SKent Overstreet { 2044cafe5635SKent Overstreet bool ret = false; 2045dc9d98d6SKent Overstreet int oldsize = bch_count_data(&b->keys); 2046cafe5635SKent Overstreet 204726c949f8SKent Overstreet while (!bch_keylist_empty(insert_keys)) { 2048c2f95ae2SKent Overstreet struct bkey *k = insert_keys->keys; 204926c949f8SKent Overstreet 205059158fdeSKent Overstreet if (bkey_u64s(k) > insert_u64s_remaining(b)) 2051403b6cdeSKent Overstreet break; 2052403b6cdeSKent Overstreet 2053403b6cdeSKent Overstreet if (bkey_cmp(k, &b->key) <= 0) { 20543a3b6a4eSKent Overstreet if (!b->level) 20553a3b6a4eSKent Overstreet bkey_put(b->c, k); 205626c949f8SKent Overstreet 2057829a60b9SKent Overstreet ret |= btree_insert_key(b, k, replace_key); 205826c949f8SKent Overstreet bch_keylist_pop_front(insert_keys); 205926c949f8SKent Overstreet } else if (bkey_cmp(&START_KEY(k), &b->key) < 0) { 206026c949f8SKent Overstreet BKEY_PADDED(key) temp; 2061c2f95ae2SKent Overstreet bkey_copy(&temp.key, insert_keys->keys); 206226c949f8SKent Overstreet 206326c949f8SKent Overstreet bch_cut_back(&b->key, &temp.key); 2064c2f95ae2SKent Overstreet bch_cut_front(&b->key, insert_keys->keys); 206526c949f8SKent Overstreet 2066829a60b9SKent Overstreet ret |= btree_insert_key(b, &temp.key, replace_key); 206726c949f8SKent Overstreet break; 206826c949f8SKent Overstreet } else { 206926c949f8SKent Overstreet break; 207026c949f8SKent Overstreet } 2071cafe5635SKent Overstreet } 2072cafe5635SKent Overstreet 2073829a60b9SKent Overstreet if (!ret) 2074829a60b9SKent Overstreet op->insert_collision = true; 2075829a60b9SKent Overstreet 2076403b6cdeSKent Overstreet BUG_ON(!bch_keylist_empty(insert_keys) && b->level); 2077403b6cdeSKent Overstreet 2078dc9d98d6SKent Overstreet BUG_ON(bch_count_data(&b->keys) < oldsize); 2079cafe5635SKent Overstreet return ret; 2080cafe5635SKent Overstreet } 2081cafe5635SKent Overstreet 208226c949f8SKent Overstreet static int btree_split(struct btree *b, struct btree_op *op, 208326c949f8SKent Overstreet struct keylist *insert_keys, 20841b207d80SKent Overstreet struct bkey *replace_key) 2085cafe5635SKent Overstreet { 2086d6fd3b11SKent Overstreet bool split; 2087cafe5635SKent Overstreet struct btree *n1, *n2 = NULL, *n3 = NULL; 2088cafe5635SKent Overstreet uint64_t start_time = local_clock(); 2089b54d6934SKent Overstreet struct closure cl; 209017e21a9fSKent Overstreet struct keylist parent_keys; 2091b54d6934SKent Overstreet 2092b54d6934SKent Overstreet closure_init_stack(&cl); 209317e21a9fSKent Overstreet bch_keylist_init(&parent_keys); 2094cafe5635SKent Overstreet 20950a63b66dSKent Overstreet if (btree_check_reserve(b, op)) { 20960a63b66dSKent Overstreet if (!b->level) 209778365411SKent Overstreet return -EINTR; 20980a63b66dSKent Overstreet else 20990a63b66dSKent Overstreet WARN(1, "insufficient reserve for split\n"); 21000a63b66dSKent Overstreet } 210178365411SKent Overstreet 21020a63b66dSKent Overstreet n1 = btree_node_alloc_replacement(b, op); 2103cafe5635SKent Overstreet if (IS_ERR(n1)) 2104cafe5635SKent Overstreet goto err; 2105cafe5635SKent Overstreet 2106ee811287SKent Overstreet split = set_blocks(btree_bset_first(n1), 2107ee811287SKent Overstreet block_bytes(n1->c)) > (btree_blocks(b) * 4) / 5; 2108cafe5635SKent Overstreet 2109cafe5635SKent Overstreet if (split) { 21106f10f7d1SColy Li unsigned int keys = 0; 2111cafe5635SKent Overstreet 2112ee811287SKent Overstreet trace_bcache_btree_node_split(b, btree_bset_first(n1)->keys); 2113c37511b8SKent Overstreet 21142452cc89SSlava Pestov n2 = bch_btree_node_alloc(b->c, op, b->level, b->parent); 2115cafe5635SKent Overstreet if (IS_ERR(n2)) 2116cafe5635SKent Overstreet goto err_free1; 2117cafe5635SKent Overstreet 2118d6fd3b11SKent Overstreet if (!b->parent) { 21192452cc89SSlava Pestov n3 = bch_btree_node_alloc(b->c, op, b->level + 1, NULL); 2120cafe5635SKent Overstreet if (IS_ERR(n3)) 2121cafe5635SKent Overstreet goto err_free2; 2122cafe5635SKent Overstreet } 2123cafe5635SKent Overstreet 21242a285686SKent Overstreet mutex_lock(&n1->write_lock); 21252a285686SKent Overstreet mutex_lock(&n2->write_lock); 21262a285686SKent Overstreet 21271b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 2128cafe5635SKent Overstreet 2129d6fd3b11SKent Overstreet /* 2130d6fd3b11SKent Overstreet * Has to be a linear search because we don't have an auxiliary 2131cafe5635SKent Overstreet * search tree yet 2132cafe5635SKent Overstreet */ 2133cafe5635SKent Overstreet 2134ee811287SKent Overstreet while (keys < (btree_bset_first(n1)->keys * 3) / 5) 2135ee811287SKent Overstreet keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), 2136fafff81cSKent Overstreet keys)); 2137cafe5635SKent Overstreet 2138fafff81cSKent Overstreet bkey_copy_key(&n1->key, 2139ee811287SKent Overstreet bset_bkey_idx(btree_bset_first(n1), keys)); 2140ee811287SKent Overstreet keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), keys)); 2141cafe5635SKent Overstreet 2142ee811287SKent Overstreet btree_bset_first(n2)->keys = btree_bset_first(n1)->keys - keys; 2143ee811287SKent Overstreet btree_bset_first(n1)->keys = keys; 2144cafe5635SKent Overstreet 2145ee811287SKent Overstreet memcpy(btree_bset_first(n2)->start, 2146ee811287SKent Overstreet bset_bkey_last(btree_bset_first(n1)), 2147ee811287SKent Overstreet btree_bset_first(n2)->keys * sizeof(uint64_t)); 2148cafe5635SKent Overstreet 2149cafe5635SKent Overstreet bkey_copy_key(&n2->key, &b->key); 2150cafe5635SKent Overstreet 215117e21a9fSKent Overstreet bch_keylist_add(&parent_keys, &n2->key); 2152b54d6934SKent Overstreet bch_btree_node_write(n2, &cl); 21532a285686SKent Overstreet mutex_unlock(&n2->write_lock); 2154cafe5635SKent Overstreet rw_unlock(true, n2); 2155c37511b8SKent Overstreet } else { 2156ee811287SKent Overstreet trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys); 2157c37511b8SKent Overstreet 21582a285686SKent Overstreet mutex_lock(&n1->write_lock); 21591b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 2160c37511b8SKent Overstreet } 2161cafe5635SKent Overstreet 216217e21a9fSKent Overstreet bch_keylist_add(&parent_keys, &n1->key); 2163b54d6934SKent Overstreet bch_btree_node_write(n1, &cl); 21642a285686SKent Overstreet mutex_unlock(&n1->write_lock); 2165cafe5635SKent Overstreet 2166cafe5635SKent Overstreet if (n3) { 2167d6fd3b11SKent Overstreet /* Depth increases, make a new root */ 21682a285686SKent Overstreet mutex_lock(&n3->write_lock); 2169cafe5635SKent Overstreet bkey_copy_key(&n3->key, &MAX_KEY); 217017e21a9fSKent Overstreet bch_btree_insert_keys(n3, op, &parent_keys, NULL); 2171b54d6934SKent Overstreet bch_btree_node_write(n3, &cl); 21722a285686SKent Overstreet mutex_unlock(&n3->write_lock); 2173cafe5635SKent Overstreet 2174b54d6934SKent Overstreet closure_sync(&cl); 2175cafe5635SKent Overstreet bch_btree_set_root(n3); 2176cafe5635SKent Overstreet rw_unlock(true, n3); 2177d6fd3b11SKent Overstreet } else if (!b->parent) { 2178d6fd3b11SKent Overstreet /* Root filled up but didn't need to be split */ 2179b54d6934SKent Overstreet closure_sync(&cl); 2180cafe5635SKent Overstreet bch_btree_set_root(n1); 2181cafe5635SKent Overstreet } else { 218217e21a9fSKent Overstreet /* Split a non root node */ 2183b54d6934SKent Overstreet closure_sync(&cl); 218417e21a9fSKent Overstreet make_btree_freeing_key(b, parent_keys.top); 218517e21a9fSKent Overstreet bch_keylist_push(&parent_keys); 218617e21a9fSKent Overstreet 218717e21a9fSKent Overstreet bch_btree_insert_node(b->parent, op, &parent_keys, NULL, NULL); 218817e21a9fSKent Overstreet BUG_ON(!bch_keylist_empty(&parent_keys)); 2189cafe5635SKent Overstreet } 2190cafe5635SKent Overstreet 219105335cffSKent Overstreet btree_node_free(b); 2192cafe5635SKent Overstreet rw_unlock(true, n1); 2193cafe5635SKent Overstreet 2194169ef1cfSKent Overstreet bch_time_stats_update(&b->c->btree_split_time, start_time); 2195cafe5635SKent Overstreet 2196cafe5635SKent Overstreet return 0; 2197cafe5635SKent Overstreet err_free2: 21985f5837d2SKent Overstreet bkey_put(b->c, &n2->key); 2199e8e1d468SKent Overstreet btree_node_free(n2); 2200cafe5635SKent Overstreet rw_unlock(true, n2); 2201cafe5635SKent Overstreet err_free1: 22025f5837d2SKent Overstreet bkey_put(b->c, &n1->key); 2203e8e1d468SKent Overstreet btree_node_free(n1); 2204cafe5635SKent Overstreet rw_unlock(true, n1); 2205cafe5635SKent Overstreet err: 22060a63b66dSKent Overstreet WARN(1, "bcache: btree split failed (level %u)", b->level); 22075f5837d2SKent Overstreet 2208cafe5635SKent Overstreet if (n3 == ERR_PTR(-EAGAIN) || 2209cafe5635SKent Overstreet n2 == ERR_PTR(-EAGAIN) || 2210cafe5635SKent Overstreet n1 == ERR_PTR(-EAGAIN)) 2211cafe5635SKent Overstreet return -EAGAIN; 2212cafe5635SKent Overstreet 2213cafe5635SKent Overstreet return -ENOMEM; 2214cafe5635SKent Overstreet } 2215cafe5635SKent Overstreet 221626c949f8SKent Overstreet static int bch_btree_insert_node(struct btree *b, struct btree_op *op, 2217c18536a7SKent Overstreet struct keylist *insert_keys, 22181b207d80SKent Overstreet atomic_t *journal_ref, 22191b207d80SKent Overstreet struct bkey *replace_key) 222026c949f8SKent Overstreet { 22212a285686SKent Overstreet struct closure cl; 22222a285686SKent Overstreet 22231b207d80SKent Overstreet BUG_ON(b->level && replace_key); 22241b207d80SKent Overstreet 22252a285686SKent Overstreet closure_init_stack(&cl); 22262a285686SKent Overstreet 22272a285686SKent Overstreet mutex_lock(&b->write_lock); 22282a285686SKent Overstreet 22292a285686SKent Overstreet if (write_block(b) != btree_bset_last(b) && 22302a285686SKent Overstreet b->keys.last_set_unwritten) 22312a285686SKent Overstreet bch_btree_init_next(b); /* just wrote a set */ 22322a285686SKent Overstreet 223359158fdeSKent Overstreet if (bch_keylist_nkeys(insert_keys) > insert_u64s_remaining(b)) { 22342a285686SKent Overstreet mutex_unlock(&b->write_lock); 22352a285686SKent Overstreet goto split; 22362a285686SKent Overstreet } 22372a285686SKent Overstreet 22382a285686SKent Overstreet BUG_ON(write_block(b) != btree_bset_last(b)); 22392a285686SKent Overstreet 22402a285686SKent Overstreet if (bch_btree_insert_keys(b, op, insert_keys, replace_key)) { 22412a285686SKent Overstreet if (!b->level) 22422a285686SKent Overstreet bch_btree_leaf_dirty(b, journal_ref); 22432a285686SKent Overstreet else 22442a285686SKent Overstreet bch_btree_node_write(b, &cl); 22452a285686SKent Overstreet } 22462a285686SKent Overstreet 22472a285686SKent Overstreet mutex_unlock(&b->write_lock); 22482a285686SKent Overstreet 22492a285686SKent Overstreet /* wait for btree node write if necessary, after unlock */ 22502a285686SKent Overstreet closure_sync(&cl); 22512a285686SKent Overstreet 22522a285686SKent Overstreet return 0; 22532a285686SKent Overstreet split: 225426c949f8SKent Overstreet if (current->bio_list) { 225526c949f8SKent Overstreet op->lock = b->c->root->level + 1; 225617e21a9fSKent Overstreet return -EAGAIN; 225726c949f8SKent Overstreet } else if (op->lock <= b->c->root->level) { 225826c949f8SKent Overstreet op->lock = b->c->root->level + 1; 225917e21a9fSKent Overstreet return -EINTR; 226026c949f8SKent Overstreet } else { 226117e21a9fSKent Overstreet /* Invalidated all iterators */ 22623b3e9e50SKent Overstreet int ret = btree_split(b, op, insert_keys, replace_key); 22633b3e9e50SKent Overstreet 22642a285686SKent Overstreet if (bch_keylist_empty(insert_keys)) 226517e21a9fSKent Overstreet return 0; 22662a285686SKent Overstreet else if (!ret) 22672a285686SKent Overstreet return -EINTR; 22682a285686SKent Overstreet return ret; 226917e21a9fSKent Overstreet } 227026c949f8SKent Overstreet } 227126c949f8SKent Overstreet 2272e7c590ebSKent Overstreet int bch_btree_insert_check_key(struct btree *b, struct btree_op *op, 2273e7c590ebSKent Overstreet struct bkey *check_key) 2274e7c590ebSKent Overstreet { 2275e7c590ebSKent Overstreet int ret = -EINTR; 2276e7c590ebSKent Overstreet uint64_t btree_ptr = b->key.ptr[0]; 2277e7c590ebSKent Overstreet unsigned long seq = b->seq; 2278e7c590ebSKent Overstreet struct keylist insert; 2279e7c590ebSKent Overstreet bool upgrade = op->lock == -1; 2280e7c590ebSKent Overstreet 2281e7c590ebSKent Overstreet bch_keylist_init(&insert); 2282e7c590ebSKent Overstreet 2283e7c590ebSKent Overstreet if (upgrade) { 2284e7c590ebSKent Overstreet rw_unlock(false, b); 2285e7c590ebSKent Overstreet rw_lock(true, b, b->level); 2286e7c590ebSKent Overstreet 2287e7c590ebSKent Overstreet if (b->key.ptr[0] != btree_ptr || 22882ef9ccbfSZheng Liu b->seq != seq + 1) { 22892ef9ccbfSZheng Liu op->lock = b->level; 2290e7c590ebSKent Overstreet goto out; 2291e7c590ebSKent Overstreet } 22922ef9ccbfSZheng Liu } 2293e7c590ebSKent Overstreet 2294e7c590ebSKent Overstreet SET_KEY_PTRS(check_key, 1); 2295e7c590ebSKent Overstreet get_random_bytes(&check_key->ptr[0], sizeof(uint64_t)); 2296e7c590ebSKent Overstreet 2297e7c590ebSKent Overstreet SET_PTR_DEV(check_key, 0, PTR_CHECK_DEV); 2298e7c590ebSKent Overstreet 2299e7c590ebSKent Overstreet bch_keylist_add(&insert, check_key); 2300e7c590ebSKent Overstreet 23011b207d80SKent Overstreet ret = bch_btree_insert_node(b, op, &insert, NULL, NULL); 2302e7c590ebSKent Overstreet 2303e7c590ebSKent Overstreet BUG_ON(!ret && !bch_keylist_empty(&insert)); 2304e7c590ebSKent Overstreet out: 2305e7c590ebSKent Overstreet if (upgrade) 2306e7c590ebSKent Overstreet downgrade_write(&b->lock); 2307e7c590ebSKent Overstreet return ret; 2308e7c590ebSKent Overstreet } 2309e7c590ebSKent Overstreet 2310cc7b8819SKent Overstreet struct btree_insert_op { 2311cc7b8819SKent Overstreet struct btree_op op; 2312cc7b8819SKent Overstreet struct keylist *keys; 2313cc7b8819SKent Overstreet atomic_t *journal_ref; 2314cc7b8819SKent Overstreet struct bkey *replace_key; 2315cc7b8819SKent Overstreet }; 2316cc7b8819SKent Overstreet 231708239ca2SWei Yongjun static int btree_insert_fn(struct btree_op *b_op, struct btree *b) 2318cafe5635SKent Overstreet { 2319cc7b8819SKent Overstreet struct btree_insert_op *op = container_of(b_op, 2320cc7b8819SKent Overstreet struct btree_insert_op, op); 2321403b6cdeSKent Overstreet 2322cc7b8819SKent Overstreet int ret = bch_btree_insert_node(b, &op->op, op->keys, 2323cc7b8819SKent Overstreet op->journal_ref, op->replace_key); 2324cc7b8819SKent Overstreet if (ret && !bch_keylist_empty(op->keys)) 2325cc7b8819SKent Overstreet return ret; 2326cc7b8819SKent Overstreet else 2327cc7b8819SKent Overstreet return MAP_DONE; 2328cafe5635SKent Overstreet } 2329cafe5635SKent Overstreet 2330cc7b8819SKent Overstreet int bch_btree_insert(struct cache_set *c, struct keylist *keys, 2331cc7b8819SKent Overstreet atomic_t *journal_ref, struct bkey *replace_key) 2332cafe5635SKent Overstreet { 2333cc7b8819SKent Overstreet struct btree_insert_op op; 2334cafe5635SKent Overstreet int ret = 0; 2335cafe5635SKent Overstreet 2336cc7b8819SKent Overstreet BUG_ON(current->bio_list); 23374f3d4014SKent Overstreet BUG_ON(bch_keylist_empty(keys)); 2338cafe5635SKent Overstreet 2339cc7b8819SKent Overstreet bch_btree_op_init(&op.op, 0); 2340cc7b8819SKent Overstreet op.keys = keys; 2341cc7b8819SKent Overstreet op.journal_ref = journal_ref; 2342cc7b8819SKent Overstreet op.replace_key = replace_key; 2343cafe5635SKent Overstreet 2344cc7b8819SKent Overstreet while (!ret && !bch_keylist_empty(keys)) { 2345cc7b8819SKent Overstreet op.op.lock = 0; 2346cc7b8819SKent Overstreet ret = bch_btree_map_leaf_nodes(&op.op, c, 2347cc7b8819SKent Overstreet &START_KEY(keys->keys), 2348cc7b8819SKent Overstreet btree_insert_fn); 2349cc7b8819SKent Overstreet } 2350cc7b8819SKent Overstreet 2351cc7b8819SKent Overstreet if (ret) { 2352cafe5635SKent Overstreet struct bkey *k; 2353cafe5635SKent Overstreet 23541b207d80SKent Overstreet pr_err("error %i", ret); 2355cafe5635SKent Overstreet 23564f3d4014SKent Overstreet while ((k = bch_keylist_pop(keys))) 23573a3b6a4eSKent Overstreet bkey_put(c, k); 2358cc7b8819SKent Overstreet } else if (op.op.insert_collision) 2359cc7b8819SKent Overstreet ret = -ESRCH; 23606054c6d4SKent Overstreet 2361cafe5635SKent Overstreet return ret; 2362cafe5635SKent Overstreet } 2363cafe5635SKent Overstreet 2364cafe5635SKent Overstreet void bch_btree_set_root(struct btree *b) 2365cafe5635SKent Overstreet { 23666f10f7d1SColy Li unsigned int i; 2367e49c7c37SKent Overstreet struct closure cl; 2368e49c7c37SKent Overstreet 2369e49c7c37SKent Overstreet closure_init_stack(&cl); 2370cafe5635SKent Overstreet 2371c37511b8SKent Overstreet trace_bcache_btree_set_root(b); 2372c37511b8SKent Overstreet 2373cafe5635SKent Overstreet BUG_ON(!b->written); 2374cafe5635SKent Overstreet 2375cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) 2376cafe5635SKent Overstreet BUG_ON(PTR_BUCKET(b->c, &b->key, i)->prio != BTREE_PRIO); 2377cafe5635SKent Overstreet 2378cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 2379cafe5635SKent Overstreet list_del_init(&b->list); 2380cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 2381cafe5635SKent Overstreet 2382cafe5635SKent Overstreet b->c->root = b; 2383cafe5635SKent Overstreet 2384e49c7c37SKent Overstreet bch_journal_meta(b->c, &cl); 2385e49c7c37SKent Overstreet closure_sync(&cl); 2386cafe5635SKent Overstreet } 2387cafe5635SKent Overstreet 238848dad8baSKent Overstreet /* Map across nodes or keys */ 238948dad8baSKent Overstreet 239048dad8baSKent Overstreet static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op, 239148dad8baSKent Overstreet struct bkey *from, 239248dad8baSKent Overstreet btree_map_nodes_fn *fn, int flags) 239348dad8baSKent Overstreet { 239448dad8baSKent Overstreet int ret = MAP_CONTINUE; 239548dad8baSKent Overstreet 239648dad8baSKent Overstreet if (b->level) { 239748dad8baSKent Overstreet struct bkey *k; 239848dad8baSKent Overstreet struct btree_iter iter; 239948dad8baSKent Overstreet 2400c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, from); 240148dad8baSKent Overstreet 2402a85e968eSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, &b->keys, 240348dad8baSKent Overstreet bch_ptr_bad))) { 240448dad8baSKent Overstreet ret = btree(map_nodes_recurse, k, b, 240548dad8baSKent Overstreet op, from, fn, flags); 240648dad8baSKent Overstreet from = NULL; 240748dad8baSKent Overstreet 240848dad8baSKent Overstreet if (ret != MAP_CONTINUE) 240948dad8baSKent Overstreet return ret; 241048dad8baSKent Overstreet } 241148dad8baSKent Overstreet } 241248dad8baSKent Overstreet 241348dad8baSKent Overstreet if (!b->level || flags == MAP_ALL_NODES) 241448dad8baSKent Overstreet ret = fn(op, b); 241548dad8baSKent Overstreet 241648dad8baSKent Overstreet return ret; 241748dad8baSKent Overstreet } 241848dad8baSKent Overstreet 241948dad8baSKent Overstreet int __bch_btree_map_nodes(struct btree_op *op, struct cache_set *c, 242048dad8baSKent Overstreet struct bkey *from, btree_map_nodes_fn *fn, int flags) 242148dad8baSKent Overstreet { 2422b54d6934SKent Overstreet return btree_root(map_nodes_recurse, c, op, from, fn, flags); 242348dad8baSKent Overstreet } 242448dad8baSKent Overstreet 242548dad8baSKent Overstreet static int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op, 242648dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, 242748dad8baSKent Overstreet int flags) 242848dad8baSKent Overstreet { 242948dad8baSKent Overstreet int ret = MAP_CONTINUE; 243048dad8baSKent Overstreet struct bkey *k; 243148dad8baSKent Overstreet struct btree_iter iter; 243248dad8baSKent Overstreet 2433c052dd9aSKent Overstreet bch_btree_iter_init(&b->keys, &iter, from); 243448dad8baSKent Overstreet 2435a85e968eSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) { 243648dad8baSKent Overstreet ret = !b->level 243748dad8baSKent Overstreet ? fn(op, b, k) 243848dad8baSKent Overstreet : btree(map_keys_recurse, k, b, op, from, fn, flags); 243948dad8baSKent Overstreet from = NULL; 244048dad8baSKent Overstreet 244148dad8baSKent Overstreet if (ret != MAP_CONTINUE) 244248dad8baSKent Overstreet return ret; 244348dad8baSKent Overstreet } 244448dad8baSKent Overstreet 244548dad8baSKent Overstreet if (!b->level && (flags & MAP_END_KEY)) 244648dad8baSKent Overstreet ret = fn(op, b, &KEY(KEY_INODE(&b->key), 244748dad8baSKent Overstreet KEY_OFFSET(&b->key), 0)); 244848dad8baSKent Overstreet 244948dad8baSKent Overstreet return ret; 245048dad8baSKent Overstreet } 245148dad8baSKent Overstreet 245248dad8baSKent Overstreet int bch_btree_map_keys(struct btree_op *op, struct cache_set *c, 245348dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, int flags) 245448dad8baSKent Overstreet { 2455b54d6934SKent Overstreet return btree_root(map_keys_recurse, c, op, from, fn, flags); 245648dad8baSKent Overstreet } 245748dad8baSKent Overstreet 2458cafe5635SKent Overstreet /* Keybuf code */ 2459cafe5635SKent Overstreet 2460cafe5635SKent Overstreet static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r) 2461cafe5635SKent Overstreet { 2462cafe5635SKent Overstreet /* Overlapping keys compare equal */ 2463cafe5635SKent Overstreet if (bkey_cmp(&l->key, &START_KEY(&r->key)) <= 0) 2464cafe5635SKent Overstreet return -1; 2465cafe5635SKent Overstreet if (bkey_cmp(&START_KEY(&l->key), &r->key) >= 0) 2466cafe5635SKent Overstreet return 1; 2467cafe5635SKent Overstreet return 0; 2468cafe5635SKent Overstreet } 2469cafe5635SKent Overstreet 2470cafe5635SKent Overstreet static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l, 2471cafe5635SKent Overstreet struct keybuf_key *r) 2472cafe5635SKent Overstreet { 2473cafe5635SKent Overstreet return clamp_t(int64_t, bkey_cmp(&l->key, &r->key), -1, 1); 2474cafe5635SKent Overstreet } 2475cafe5635SKent Overstreet 247648dad8baSKent Overstreet struct refill { 247748dad8baSKent Overstreet struct btree_op op; 24786f10f7d1SColy Li unsigned int nr_found; 247948dad8baSKent Overstreet struct keybuf *buf; 248048dad8baSKent Overstreet struct bkey *end; 248148dad8baSKent Overstreet keybuf_pred_fn *pred; 248248dad8baSKent Overstreet }; 248348dad8baSKent Overstreet 248448dad8baSKent Overstreet static int refill_keybuf_fn(struct btree_op *op, struct btree *b, 248548dad8baSKent Overstreet struct bkey *k) 2486cafe5635SKent Overstreet { 248748dad8baSKent Overstreet struct refill *refill = container_of(op, struct refill, op); 248848dad8baSKent Overstreet struct keybuf *buf = refill->buf; 248948dad8baSKent Overstreet int ret = MAP_CONTINUE; 2490cafe5635SKent Overstreet 24912d6cb6edSTang Junhui if (bkey_cmp(k, refill->end) > 0) { 249248dad8baSKent Overstreet ret = MAP_DONE; 249348dad8baSKent Overstreet goto out; 2494cafe5635SKent Overstreet } 2495cafe5635SKent Overstreet 249648dad8baSKent Overstreet if (!KEY_SIZE(k)) /* end key */ 249748dad8baSKent Overstreet goto out; 2498cafe5635SKent Overstreet 249948dad8baSKent Overstreet if (refill->pred(buf, k)) { 2500cafe5635SKent Overstreet struct keybuf_key *w; 2501cafe5635SKent Overstreet 2502cafe5635SKent Overstreet spin_lock(&buf->lock); 2503cafe5635SKent Overstreet 2504cafe5635SKent Overstreet w = array_alloc(&buf->freelist); 250548dad8baSKent Overstreet if (!w) { 250648dad8baSKent Overstreet spin_unlock(&buf->lock); 250748dad8baSKent Overstreet return MAP_DONE; 250848dad8baSKent Overstreet } 2509cafe5635SKent Overstreet 2510cafe5635SKent Overstreet w->private = NULL; 2511cafe5635SKent Overstreet bkey_copy(&w->key, k); 2512cafe5635SKent Overstreet 2513cafe5635SKent Overstreet if (RB_INSERT(&buf->keys, w, node, keybuf_cmp)) 2514cafe5635SKent Overstreet array_free(&buf->freelist, w); 251548a915a8SKent Overstreet else 251648a915a8SKent Overstreet refill->nr_found++; 2517cafe5635SKent Overstreet 251848dad8baSKent Overstreet if (array_freelist_empty(&buf->freelist)) 251948dad8baSKent Overstreet ret = MAP_DONE; 252048dad8baSKent Overstreet 2521cafe5635SKent Overstreet spin_unlock(&buf->lock); 2522cafe5635SKent Overstreet } 252348dad8baSKent Overstreet out: 252448dad8baSKent Overstreet buf->last_scanned = *k; 252548dad8baSKent Overstreet return ret; 2526cafe5635SKent Overstreet } 2527cafe5635SKent Overstreet 2528cafe5635SKent Overstreet void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf, 252972c27061SKent Overstreet struct bkey *end, keybuf_pred_fn *pred) 2530cafe5635SKent Overstreet { 2531cafe5635SKent Overstreet struct bkey start = buf->last_scanned; 253248dad8baSKent Overstreet struct refill refill; 2533cafe5635SKent Overstreet 2534cafe5635SKent Overstreet cond_resched(); 2535cafe5635SKent Overstreet 2536b54d6934SKent Overstreet bch_btree_op_init(&refill.op, -1); 253748a915a8SKent Overstreet refill.nr_found = 0; 253848dad8baSKent Overstreet refill.buf = buf; 253948dad8baSKent Overstreet refill.end = end; 254048dad8baSKent Overstreet refill.pred = pred; 254148dad8baSKent Overstreet 254248dad8baSKent Overstreet bch_btree_map_keys(&refill.op, c, &buf->last_scanned, 254348dad8baSKent Overstreet refill_keybuf_fn, MAP_END_KEY); 2544cafe5635SKent Overstreet 254548a915a8SKent Overstreet trace_bcache_keyscan(refill.nr_found, 2546cafe5635SKent Overstreet KEY_INODE(&start), KEY_OFFSET(&start), 254748a915a8SKent Overstreet KEY_INODE(&buf->last_scanned), 254848a915a8SKent Overstreet KEY_OFFSET(&buf->last_scanned)); 2549cafe5635SKent Overstreet 2550cafe5635SKent Overstreet spin_lock(&buf->lock); 2551cafe5635SKent Overstreet 2552cafe5635SKent Overstreet if (!RB_EMPTY_ROOT(&buf->keys)) { 2553cafe5635SKent Overstreet struct keybuf_key *w; 25541fae7cf0SColy Li 2555cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2556cafe5635SKent Overstreet buf->start = START_KEY(&w->key); 2557cafe5635SKent Overstreet 2558cafe5635SKent Overstreet w = RB_LAST(&buf->keys, struct keybuf_key, node); 2559cafe5635SKent Overstreet buf->end = w->key; 2560cafe5635SKent Overstreet } else { 2561cafe5635SKent Overstreet buf->start = MAX_KEY; 2562cafe5635SKent Overstreet buf->end = MAX_KEY; 2563cafe5635SKent Overstreet } 2564cafe5635SKent Overstreet 2565cafe5635SKent Overstreet spin_unlock(&buf->lock); 2566cafe5635SKent Overstreet } 2567cafe5635SKent Overstreet 2568cafe5635SKent Overstreet static void __bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2569cafe5635SKent Overstreet { 2570cafe5635SKent Overstreet rb_erase(&w->node, &buf->keys); 2571cafe5635SKent Overstreet array_free(&buf->freelist, w); 2572cafe5635SKent Overstreet } 2573cafe5635SKent Overstreet 2574cafe5635SKent Overstreet void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2575cafe5635SKent Overstreet { 2576cafe5635SKent Overstreet spin_lock(&buf->lock); 2577cafe5635SKent Overstreet __bch_keybuf_del(buf, w); 2578cafe5635SKent Overstreet spin_unlock(&buf->lock); 2579cafe5635SKent Overstreet } 2580cafe5635SKent Overstreet 2581cafe5635SKent Overstreet bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start, 2582cafe5635SKent Overstreet struct bkey *end) 2583cafe5635SKent Overstreet { 2584cafe5635SKent Overstreet bool ret = false; 2585cafe5635SKent Overstreet struct keybuf_key *p, *w, s; 25861fae7cf0SColy Li 2587cafe5635SKent Overstreet s.key = *start; 2588cafe5635SKent Overstreet 2589cafe5635SKent Overstreet if (bkey_cmp(end, &buf->start) <= 0 || 2590cafe5635SKent Overstreet bkey_cmp(start, &buf->end) >= 0) 2591cafe5635SKent Overstreet return false; 2592cafe5635SKent Overstreet 2593cafe5635SKent Overstreet spin_lock(&buf->lock); 2594cafe5635SKent Overstreet w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp); 2595cafe5635SKent Overstreet 2596cafe5635SKent Overstreet while (w && bkey_cmp(&START_KEY(&w->key), end) < 0) { 2597cafe5635SKent Overstreet p = w; 2598cafe5635SKent Overstreet w = RB_NEXT(w, node); 2599cafe5635SKent Overstreet 2600cafe5635SKent Overstreet if (p->private) 2601cafe5635SKent Overstreet ret = true; 2602cafe5635SKent Overstreet else 2603cafe5635SKent Overstreet __bch_keybuf_del(buf, p); 2604cafe5635SKent Overstreet } 2605cafe5635SKent Overstreet 2606cafe5635SKent Overstreet spin_unlock(&buf->lock); 2607cafe5635SKent Overstreet return ret; 2608cafe5635SKent Overstreet } 2609cafe5635SKent Overstreet 2610cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next(struct keybuf *buf) 2611cafe5635SKent Overstreet { 2612cafe5635SKent Overstreet struct keybuf_key *w; 26131fae7cf0SColy Li 2614cafe5635SKent Overstreet spin_lock(&buf->lock); 2615cafe5635SKent Overstreet 2616cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2617cafe5635SKent Overstreet 2618cafe5635SKent Overstreet while (w && w->private) 2619cafe5635SKent Overstreet w = RB_NEXT(w, node); 2620cafe5635SKent Overstreet 2621cafe5635SKent Overstreet if (w) 2622cafe5635SKent Overstreet w->private = ERR_PTR(-EINTR); 2623cafe5635SKent Overstreet 2624cafe5635SKent Overstreet spin_unlock(&buf->lock); 2625cafe5635SKent Overstreet return w; 2626cafe5635SKent Overstreet } 2627cafe5635SKent Overstreet 2628cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c, 2629cafe5635SKent Overstreet struct keybuf *buf, 263072c27061SKent Overstreet struct bkey *end, 263172c27061SKent Overstreet keybuf_pred_fn *pred) 2632cafe5635SKent Overstreet { 2633cafe5635SKent Overstreet struct keybuf_key *ret; 2634cafe5635SKent Overstreet 2635cafe5635SKent Overstreet while (1) { 2636cafe5635SKent Overstreet ret = bch_keybuf_next(buf); 2637cafe5635SKent Overstreet if (ret) 2638cafe5635SKent Overstreet break; 2639cafe5635SKent Overstreet 2640cafe5635SKent Overstreet if (bkey_cmp(&buf->last_scanned, end) >= 0) { 2641cafe5635SKent Overstreet pr_debug("scan finished"); 2642cafe5635SKent Overstreet break; 2643cafe5635SKent Overstreet } 2644cafe5635SKent Overstreet 264572c27061SKent Overstreet bch_refill_keybuf(c, buf, end, pred); 2646cafe5635SKent Overstreet } 2647cafe5635SKent Overstreet 2648cafe5635SKent Overstreet return ret; 2649cafe5635SKent Overstreet } 2650cafe5635SKent Overstreet 265172c27061SKent Overstreet void bch_keybuf_init(struct keybuf *buf) 2652cafe5635SKent Overstreet { 2653cafe5635SKent Overstreet buf->last_scanned = MAX_KEY; 2654cafe5635SKent Overstreet buf->keys = RB_ROOT; 2655cafe5635SKent Overstreet 2656cafe5635SKent Overstreet spin_lock_init(&buf->lock); 2657cafe5635SKent Overstreet array_allocator_init(&buf->freelist); 2658cafe5635SKent Overstreet } 2659