1cafe5635SKent Overstreet /* 2cafe5635SKent Overstreet * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com> 3cafe5635SKent Overstreet * 4cafe5635SKent Overstreet * Uses a block device as cache for other block devices; optimized for SSDs. 5cafe5635SKent Overstreet * All allocation is done in buckets, which should match the erase block size 6cafe5635SKent Overstreet * of the device. 7cafe5635SKent Overstreet * 8cafe5635SKent Overstreet * Buckets containing cached data are kept on a heap sorted by priority; 9cafe5635SKent Overstreet * bucket priority is increased on cache hit, and periodically all the buckets 10cafe5635SKent Overstreet * on the heap have their priority scaled down. This currently is just used as 11cafe5635SKent Overstreet * an LRU but in the future should allow for more intelligent heuristics. 12cafe5635SKent Overstreet * 13cafe5635SKent Overstreet * Buckets have an 8 bit counter; freeing is accomplished by incrementing the 14cafe5635SKent Overstreet * counter. Garbage collection is used to remove stale pointers. 15cafe5635SKent Overstreet * 16cafe5635SKent Overstreet * Indexing is done via a btree; nodes are not necessarily fully sorted, rather 17cafe5635SKent Overstreet * as keys are inserted we only sort the pages that have not yet been written. 18cafe5635SKent Overstreet * When garbage collection is run, we resort the entire node. 19cafe5635SKent Overstreet * 20cafe5635SKent Overstreet * All configuration is done via sysfs; see Documentation/bcache.txt. 21cafe5635SKent Overstreet */ 22cafe5635SKent Overstreet 23cafe5635SKent Overstreet #include "bcache.h" 24cafe5635SKent Overstreet #include "btree.h" 25cafe5635SKent Overstreet #include "debug.h" 26279afbadSKent Overstreet #include "writeback.h" 27cafe5635SKent Overstreet 28cafe5635SKent Overstreet #include <linux/slab.h> 29cafe5635SKent Overstreet #include <linux/bitops.h> 3072a44517SKent Overstreet #include <linux/freezer.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> 36cafe5635SKent Overstreet #include <trace/events/bcache.h> 37cafe5635SKent Overstreet 38cafe5635SKent Overstreet /* 39cafe5635SKent Overstreet * Todo: 40cafe5635SKent Overstreet * register_bcache: Return errors out to userspace correctly 41cafe5635SKent Overstreet * 42cafe5635SKent Overstreet * Writeback: don't undirty key until after a cache flush 43cafe5635SKent Overstreet * 44cafe5635SKent Overstreet * Create an iterator for key pointers 45cafe5635SKent Overstreet * 46cafe5635SKent Overstreet * On btree write error, mark bucket such that it won't be freed from the cache 47cafe5635SKent Overstreet * 48cafe5635SKent Overstreet * Journalling: 49cafe5635SKent Overstreet * Check for bad keys in replay 50cafe5635SKent Overstreet * Propagate barriers 51cafe5635SKent Overstreet * Refcount journal entries in journal_replay 52cafe5635SKent Overstreet * 53cafe5635SKent Overstreet * Garbage collection: 54cafe5635SKent Overstreet * Finish incremental gc 55cafe5635SKent Overstreet * Gc should free old UUIDs, data for invalid UUIDs 56cafe5635SKent Overstreet * 57cafe5635SKent Overstreet * Provide a way to list backing device UUIDs we have data cached for, and 58cafe5635SKent Overstreet * probably how long it's been since we've seen them, and a way to invalidate 59cafe5635SKent Overstreet * dirty data for devices that will never be attached again 60cafe5635SKent Overstreet * 61cafe5635SKent Overstreet * Keep 1 min/5 min/15 min statistics of how busy a block device has been, so 62cafe5635SKent Overstreet * that based on that and how much dirty data we have we can keep writeback 63cafe5635SKent Overstreet * from being starved 64cafe5635SKent Overstreet * 65cafe5635SKent Overstreet * Add a tracepoint or somesuch to watch for writeback starvation 66cafe5635SKent Overstreet * 67cafe5635SKent Overstreet * When btree depth > 1 and splitting an interior node, we have to make sure 68cafe5635SKent Overstreet * alloc_bucket() cannot fail. This should be true but is not completely 69cafe5635SKent Overstreet * obvious. 70cafe5635SKent Overstreet * 71cafe5635SKent Overstreet * Make sure all allocations get charged to the root cgroup 72cafe5635SKent Overstreet * 73cafe5635SKent Overstreet * Plugging? 74cafe5635SKent Overstreet * 75cafe5635SKent Overstreet * If data write is less than hard sector size of ssd, round up offset in open 76cafe5635SKent Overstreet * bucket to the next whole sector 77cafe5635SKent Overstreet * 78cafe5635SKent Overstreet * Also lookup by cgroup in get_open_bucket() 79cafe5635SKent Overstreet * 80cafe5635SKent Overstreet * Superblock needs to be fleshed out for multiple cache devices 81cafe5635SKent Overstreet * 82cafe5635SKent Overstreet * Add a sysfs tunable for the number of writeback IOs in flight 83cafe5635SKent Overstreet * 84cafe5635SKent Overstreet * Add a sysfs tunable for the number of open data buckets 85cafe5635SKent Overstreet * 86cafe5635SKent Overstreet * IO tracking: Can we track when one process is doing io on behalf of another? 87cafe5635SKent Overstreet * IO tracking: Don't use just an average, weigh more recent stuff higher 88cafe5635SKent Overstreet * 89cafe5635SKent Overstreet * Test module load/unload 90cafe5635SKent Overstreet */ 91cafe5635SKent Overstreet 92df8e8970SKent Overstreet enum { 93df8e8970SKent Overstreet BTREE_INSERT_STATUS_INSERT, 94df8e8970SKent Overstreet BTREE_INSERT_STATUS_BACK_MERGE, 95df8e8970SKent Overstreet BTREE_INSERT_STATUS_OVERWROTE, 96df8e8970SKent Overstreet BTREE_INSERT_STATUS_FRONT_MERGE, 97df8e8970SKent Overstreet }; 98df8e8970SKent Overstreet 99cafe5635SKent Overstreet #define MAX_NEED_GC 64 100cafe5635SKent Overstreet #define MAX_SAVE_PRIO 72 101cafe5635SKent Overstreet 102cafe5635SKent Overstreet #define PTR_DIRTY_BIT (((uint64_t) 1 << 36)) 103cafe5635SKent Overstreet 104cafe5635SKent Overstreet #define PTR_HASH(c, k) \ 105cafe5635SKent Overstreet (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0)) 106cafe5635SKent Overstreet 107cafe5635SKent Overstreet static struct workqueue_struct *btree_io_wq; 108cafe5635SKent Overstreet 109df8e8970SKent Overstreet static inline bool should_split(struct btree *b) 110df8e8970SKent Overstreet { 111df8e8970SKent Overstreet struct bset *i = write_block(b); 112df8e8970SKent Overstreet return b->written >= btree_blocks(b) || 113df8e8970SKent Overstreet (b->written + __set_blocks(i, i->keys + 15, b->c) 114df8e8970SKent Overstreet > btree_blocks(b)); 115df8e8970SKent Overstreet } 116df8e8970SKent Overstreet 117df8e8970SKent Overstreet #define insert_lock(s, b) ((b)->level <= (s)->lock) 118df8e8970SKent Overstreet 119df8e8970SKent Overstreet /* 120df8e8970SKent Overstreet * These macros are for recursing down the btree - they handle the details of 121df8e8970SKent Overstreet * locking and looking up nodes in the cache for you. They're best treated as 122df8e8970SKent Overstreet * mere syntax when reading code that uses them. 123df8e8970SKent Overstreet * 124df8e8970SKent Overstreet * op->lock determines whether we take a read or a write lock at a given depth. 125df8e8970SKent Overstreet * If you've got a read lock and find that you need a write lock (i.e. you're 126df8e8970SKent Overstreet * going to have to split), set op->lock and return -EINTR; btree_root() will 127df8e8970SKent Overstreet * call you again and you'll have the correct lock. 128df8e8970SKent Overstreet */ 129df8e8970SKent Overstreet 130df8e8970SKent Overstreet /** 131df8e8970SKent Overstreet * btree - recurse down the btree on a specified key 132df8e8970SKent Overstreet * @fn: function to call, which will be passed the child node 133df8e8970SKent Overstreet * @key: key to recurse on 134df8e8970SKent Overstreet * @b: parent btree node 135df8e8970SKent Overstreet * @op: pointer to struct btree_op 136df8e8970SKent Overstreet */ 137df8e8970SKent Overstreet #define btree(fn, key, b, op, ...) \ 138df8e8970SKent Overstreet ({ \ 139df8e8970SKent Overstreet int _r, l = (b)->level - 1; \ 140df8e8970SKent Overstreet bool _w = l <= (op)->lock; \ 141df8e8970SKent Overstreet struct btree *_child = bch_btree_node_get((b)->c, key, l, _w); \ 142df8e8970SKent Overstreet if (!IS_ERR(_child)) { \ 143df8e8970SKent Overstreet _child->parent = (b); \ 144df8e8970SKent Overstreet _r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__); \ 145df8e8970SKent Overstreet rw_unlock(_w, _child); \ 146df8e8970SKent Overstreet } else \ 147df8e8970SKent Overstreet _r = PTR_ERR(_child); \ 148df8e8970SKent Overstreet _r; \ 149df8e8970SKent Overstreet }) 150df8e8970SKent Overstreet 151df8e8970SKent Overstreet /** 152df8e8970SKent Overstreet * btree_root - call a function on the root of the btree 153df8e8970SKent Overstreet * @fn: function to call, which will be passed the child node 154df8e8970SKent Overstreet * @c: cache set 155df8e8970SKent Overstreet * @op: pointer to struct btree_op 156df8e8970SKent Overstreet */ 157df8e8970SKent Overstreet #define btree_root(fn, c, op, ...) \ 158df8e8970SKent Overstreet ({ \ 159df8e8970SKent Overstreet int _r = -EINTR; \ 160df8e8970SKent Overstreet do { \ 161df8e8970SKent Overstreet struct btree *_b = (c)->root; \ 162df8e8970SKent Overstreet bool _w = insert_lock(op, _b); \ 163df8e8970SKent Overstreet rw_lock(_w, _b, _b->level); \ 164df8e8970SKent Overstreet if (_b == (c)->root && \ 165df8e8970SKent Overstreet _w == insert_lock(op, _b)) { \ 166df8e8970SKent Overstreet _b->parent = NULL; \ 167df8e8970SKent Overstreet _r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__); \ 168df8e8970SKent Overstreet } \ 169df8e8970SKent Overstreet rw_unlock(_w, _b); \ 170df8e8970SKent Overstreet bch_cannibalize_unlock(c); \ 171df8e8970SKent Overstreet if (_r == -ENOSPC) { \ 172df8e8970SKent Overstreet wait_event((c)->try_wait, \ 173df8e8970SKent Overstreet !(c)->try_harder); \ 174df8e8970SKent Overstreet _r = -EINTR; \ 175df8e8970SKent Overstreet } \ 176df8e8970SKent Overstreet } while (_r == -EINTR); \ 177df8e8970SKent Overstreet \ 178df8e8970SKent Overstreet _r; \ 179df8e8970SKent Overstreet }) 180df8e8970SKent Overstreet 181cafe5635SKent Overstreet /* Btree key manipulation */ 182cafe5635SKent Overstreet 183e7c590ebSKent Overstreet void __bkey_put(struct cache_set *c, struct bkey *k) 184e7c590ebSKent Overstreet { 185e7c590ebSKent Overstreet unsigned i; 186e7c590ebSKent Overstreet 187e7c590ebSKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) 188e7c590ebSKent Overstreet if (ptr_available(c, k, i)) 189e7c590ebSKent Overstreet atomic_dec_bug(&PTR_BUCKET(c, k, i)->pin); 190e7c590ebSKent Overstreet } 191e7c590ebSKent Overstreet 192cafe5635SKent Overstreet static void bkey_put(struct cache_set *c, struct bkey *k, int level) 193cafe5635SKent Overstreet { 194cafe5635SKent Overstreet if ((level && KEY_OFFSET(k)) || !level) 195cafe5635SKent Overstreet __bkey_put(c, k); 196cafe5635SKent Overstreet } 197cafe5635SKent Overstreet 198cafe5635SKent Overstreet /* Btree IO */ 199cafe5635SKent Overstreet 200cafe5635SKent Overstreet static uint64_t btree_csum_set(struct btree *b, struct bset *i) 201cafe5635SKent Overstreet { 202cafe5635SKent Overstreet uint64_t crc = b->key.ptr[0]; 203cafe5635SKent Overstreet void *data = (void *) i + 8, *end = end(i); 204cafe5635SKent Overstreet 205169ef1cfSKent Overstreet crc = bch_crc64_update(crc, data, end - data); 206c19ed23aSKent Overstreet return crc ^ 0xffffffffffffffffULL; 207cafe5635SKent Overstreet } 208cafe5635SKent Overstreet 209f3059a54SKent Overstreet static void bch_btree_node_read_done(struct btree *b) 210cafe5635SKent Overstreet { 211cafe5635SKent Overstreet const char *err = "bad btree header"; 21257943511SKent Overstreet struct bset *i = b->sets[0].data; 21357943511SKent Overstreet struct btree_iter *iter; 214cafe5635SKent Overstreet 21557943511SKent Overstreet iter = mempool_alloc(b->c->fill_iter, GFP_NOWAIT); 21657943511SKent Overstreet iter->size = b->c->sb.bucket_size / b->c->sb.block_size; 217cafe5635SKent Overstreet iter->used = 0; 218cafe5635SKent Overstreet 21957943511SKent Overstreet if (!i->seq) 220cafe5635SKent Overstreet goto err; 221cafe5635SKent Overstreet 222cafe5635SKent Overstreet for (; 223cafe5635SKent Overstreet b->written < btree_blocks(b) && i->seq == b->sets[0].data->seq; 224cafe5635SKent Overstreet i = write_block(b)) { 225cafe5635SKent Overstreet err = "unsupported bset version"; 226cafe5635SKent Overstreet if (i->version > BCACHE_BSET_VERSION) 227cafe5635SKent Overstreet goto err; 228cafe5635SKent Overstreet 229cafe5635SKent Overstreet err = "bad btree header"; 230cafe5635SKent Overstreet if (b->written + set_blocks(i, b->c) > btree_blocks(b)) 231cafe5635SKent Overstreet goto err; 232cafe5635SKent Overstreet 233cafe5635SKent Overstreet err = "bad magic"; 234cafe5635SKent Overstreet if (i->magic != bset_magic(b->c)) 235cafe5635SKent Overstreet goto err; 236cafe5635SKent Overstreet 237cafe5635SKent Overstreet err = "bad checksum"; 238cafe5635SKent Overstreet switch (i->version) { 239cafe5635SKent Overstreet case 0: 240cafe5635SKent Overstreet if (i->csum != csum_set(i)) 241cafe5635SKent Overstreet goto err; 242cafe5635SKent Overstreet break; 243cafe5635SKent Overstreet case BCACHE_BSET_VERSION: 244cafe5635SKent Overstreet if (i->csum != btree_csum_set(b, i)) 245cafe5635SKent Overstreet goto err; 246cafe5635SKent Overstreet break; 247cafe5635SKent Overstreet } 248cafe5635SKent Overstreet 249cafe5635SKent Overstreet err = "empty set"; 250cafe5635SKent Overstreet if (i != b->sets[0].data && !i->keys) 251cafe5635SKent Overstreet goto err; 252cafe5635SKent Overstreet 253cafe5635SKent Overstreet bch_btree_iter_push(iter, i->start, end(i)); 254cafe5635SKent Overstreet 255cafe5635SKent Overstreet b->written += set_blocks(i, b->c); 256cafe5635SKent Overstreet } 257cafe5635SKent Overstreet 258cafe5635SKent Overstreet err = "corrupted btree"; 259cafe5635SKent Overstreet for (i = write_block(b); 260cafe5635SKent Overstreet index(i, b) < btree_blocks(b); 261cafe5635SKent Overstreet i = ((void *) i) + block_bytes(b->c)) 262cafe5635SKent Overstreet if (i->seq == b->sets[0].data->seq) 263cafe5635SKent Overstreet goto err; 264cafe5635SKent Overstreet 265cafe5635SKent Overstreet bch_btree_sort_and_fix_extents(b, iter); 266cafe5635SKent Overstreet 267cafe5635SKent Overstreet i = b->sets[0].data; 268cafe5635SKent Overstreet err = "short btree key"; 269cafe5635SKent Overstreet if (b->sets[0].size && 270cafe5635SKent Overstreet bkey_cmp(&b->key, &b->sets[0].end) < 0) 271cafe5635SKent Overstreet goto err; 272cafe5635SKent Overstreet 273cafe5635SKent Overstreet if (b->written < btree_blocks(b)) 274cafe5635SKent Overstreet bch_bset_init_next(b); 275cafe5635SKent Overstreet out: 27657943511SKent Overstreet mempool_free(iter, b->c->fill_iter); 27757943511SKent Overstreet return; 278cafe5635SKent Overstreet err: 279cafe5635SKent Overstreet set_btree_node_io_error(b); 28007e86ccbSKent Overstreet bch_cache_set_error(b->c, "%s at bucket %zu, block %zu, %u keys", 281cafe5635SKent Overstreet err, PTR_BUCKET_NR(b->c, &b->key, 0), 282cafe5635SKent Overstreet index(i, b), i->keys); 283cafe5635SKent Overstreet goto out; 284cafe5635SKent Overstreet } 285cafe5635SKent Overstreet 28657943511SKent Overstreet static void btree_node_read_endio(struct bio *bio, int error) 287cafe5635SKent Overstreet { 28857943511SKent Overstreet struct closure *cl = bio->bi_private; 28957943511SKent Overstreet closure_put(cl); 29057943511SKent Overstreet } 291cafe5635SKent Overstreet 29257943511SKent Overstreet void bch_btree_node_read(struct btree *b) 29357943511SKent Overstreet { 29457943511SKent Overstreet uint64_t start_time = local_clock(); 29557943511SKent Overstreet struct closure cl; 29657943511SKent Overstreet struct bio *bio; 297cafe5635SKent Overstreet 298c37511b8SKent Overstreet trace_bcache_btree_read(b); 299c37511b8SKent Overstreet 30057943511SKent Overstreet closure_init_stack(&cl); 301cafe5635SKent Overstreet 30257943511SKent Overstreet bio = bch_bbio_alloc(b->c); 30357943511SKent Overstreet bio->bi_rw = REQ_META|READ_SYNC; 30457943511SKent Overstreet bio->bi_size = KEY_SIZE(&b->key) << 9; 30557943511SKent Overstreet bio->bi_end_io = btree_node_read_endio; 30657943511SKent Overstreet bio->bi_private = &cl; 30757943511SKent Overstreet 30857943511SKent Overstreet bch_bio_map(bio, b->sets[0].data); 30957943511SKent Overstreet 31057943511SKent Overstreet bch_submit_bbio(bio, b->c, &b->key, 0); 31157943511SKent Overstreet closure_sync(&cl); 31257943511SKent Overstreet 31357943511SKent Overstreet if (!test_bit(BIO_UPTODATE, &bio->bi_flags)) 31457943511SKent Overstreet set_btree_node_io_error(b); 31557943511SKent Overstreet 31657943511SKent Overstreet bch_bbio_free(bio, b->c); 31757943511SKent Overstreet 31857943511SKent Overstreet if (btree_node_io_error(b)) 31957943511SKent Overstreet goto err; 32057943511SKent Overstreet 32157943511SKent Overstreet bch_btree_node_read_done(b); 32257943511SKent Overstreet 32357943511SKent Overstreet spin_lock(&b->c->btree_read_time_lock); 32457943511SKent Overstreet bch_time_stats_update(&b->c->btree_read_time, start_time); 32557943511SKent Overstreet spin_unlock(&b->c->btree_read_time_lock); 32657943511SKent Overstreet 32757943511SKent Overstreet return; 32857943511SKent Overstreet err: 32961cbd250SGeert Uytterhoeven bch_cache_set_error(b->c, "io error reading bucket %zu", 33057943511SKent Overstreet PTR_BUCKET_NR(b->c, &b->key, 0)); 331cafe5635SKent Overstreet } 332cafe5635SKent Overstreet 333cafe5635SKent Overstreet static void btree_complete_write(struct btree *b, struct btree_write *w) 334cafe5635SKent Overstreet { 335cafe5635SKent Overstreet if (w->prio_blocked && 336cafe5635SKent Overstreet !atomic_sub_return(w->prio_blocked, &b->c->prio_blocked)) 337119ba0f8SKent Overstreet wake_up_allocators(b->c); 338cafe5635SKent Overstreet 339cafe5635SKent Overstreet if (w->journal) { 340cafe5635SKent Overstreet atomic_dec_bug(w->journal); 341cafe5635SKent Overstreet __closure_wake_up(&b->c->journal.wait); 342cafe5635SKent Overstreet } 343cafe5635SKent Overstreet 344cafe5635SKent Overstreet w->prio_blocked = 0; 345cafe5635SKent Overstreet w->journal = NULL; 346cafe5635SKent Overstreet } 347cafe5635SKent Overstreet 34857943511SKent Overstreet static void __btree_node_write_done(struct closure *cl) 349cafe5635SKent Overstreet { 350cafe5635SKent Overstreet struct btree *b = container_of(cl, struct btree, io.cl); 351cafe5635SKent Overstreet struct btree_write *w = btree_prev_write(b); 352cafe5635SKent Overstreet 353cafe5635SKent Overstreet bch_bbio_free(b->bio, b->c); 354cafe5635SKent Overstreet b->bio = NULL; 355cafe5635SKent Overstreet btree_complete_write(b, w); 356cafe5635SKent Overstreet 357cafe5635SKent Overstreet if (btree_node_dirty(b)) 358cafe5635SKent Overstreet queue_delayed_work(btree_io_wq, &b->work, 359cafe5635SKent Overstreet msecs_to_jiffies(30000)); 360cafe5635SKent Overstreet 361cafe5635SKent Overstreet closure_return(cl); 362cafe5635SKent Overstreet } 363cafe5635SKent Overstreet 36457943511SKent Overstreet static void btree_node_write_done(struct closure *cl) 365cafe5635SKent Overstreet { 366cafe5635SKent Overstreet struct btree *b = container_of(cl, struct btree, io.cl); 367cafe5635SKent Overstreet struct bio_vec *bv; 368cafe5635SKent Overstreet int n; 369cafe5635SKent Overstreet 370cafe5635SKent Overstreet __bio_for_each_segment(bv, b->bio, n, 0) 371cafe5635SKent Overstreet __free_page(bv->bv_page); 372cafe5635SKent Overstreet 37357943511SKent Overstreet __btree_node_write_done(cl); 374cafe5635SKent Overstreet } 375cafe5635SKent Overstreet 37657943511SKent Overstreet static void btree_node_write_endio(struct bio *bio, int error) 37757943511SKent Overstreet { 37857943511SKent Overstreet struct closure *cl = bio->bi_private; 37957943511SKent Overstreet struct btree *b = container_of(cl, struct btree, io.cl); 38057943511SKent Overstreet 38157943511SKent Overstreet if (error) 38257943511SKent Overstreet set_btree_node_io_error(b); 38357943511SKent Overstreet 38457943511SKent Overstreet bch_bbio_count_io_errors(b->c, bio, error, "writing btree"); 38557943511SKent Overstreet closure_put(cl); 38657943511SKent Overstreet } 38757943511SKent Overstreet 38857943511SKent Overstreet static void do_btree_node_write(struct btree *b) 389cafe5635SKent Overstreet { 390cafe5635SKent Overstreet struct closure *cl = &b->io.cl; 391cafe5635SKent Overstreet struct bset *i = b->sets[b->nsets].data; 392cafe5635SKent Overstreet BKEY_PADDED(key) k; 393cafe5635SKent Overstreet 394cafe5635SKent Overstreet i->version = BCACHE_BSET_VERSION; 395cafe5635SKent Overstreet i->csum = btree_csum_set(b, i); 396cafe5635SKent Overstreet 39757943511SKent Overstreet BUG_ON(b->bio); 39857943511SKent Overstreet b->bio = bch_bbio_alloc(b->c); 39957943511SKent Overstreet 40057943511SKent Overstreet b->bio->bi_end_io = btree_node_write_endio; 401faadf0c9SKent Overstreet b->bio->bi_private = cl; 402e49c7c37SKent Overstreet b->bio->bi_rw = REQ_META|WRITE_SYNC|REQ_FUA; 403cafe5635SKent Overstreet b->bio->bi_size = set_blocks(i, b->c) * block_bytes(b->c); 404169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 405cafe5635SKent Overstreet 406e49c7c37SKent Overstreet /* 407e49c7c37SKent Overstreet * If we're appending to a leaf node, we don't technically need FUA - 408e49c7c37SKent Overstreet * this write just needs to be persisted before the next journal write, 409e49c7c37SKent Overstreet * which will be marked FLUSH|FUA. 410e49c7c37SKent Overstreet * 411e49c7c37SKent Overstreet * Similarly if we're writing a new btree root - the pointer is going to 412e49c7c37SKent Overstreet * be in the next journal entry. 413e49c7c37SKent Overstreet * 414e49c7c37SKent Overstreet * But if we're writing a new btree node (that isn't a root) or 415e49c7c37SKent Overstreet * appending to a non leaf btree node, we need either FUA or a flush 416e49c7c37SKent Overstreet * when we write the parent with the new pointer. FUA is cheaper than a 417e49c7c37SKent Overstreet * flush, and writes appending to leaf nodes aren't blocking anything so 418e49c7c37SKent Overstreet * just make all btree node writes FUA to keep things sane. 419e49c7c37SKent Overstreet */ 420e49c7c37SKent Overstreet 421cafe5635SKent Overstreet bkey_copy(&k.key, &b->key); 422cafe5635SKent Overstreet SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) + bset_offset(b, i)); 423cafe5635SKent Overstreet 4248e51e414SKent Overstreet if (!bio_alloc_pages(b->bio, GFP_NOIO)) { 425cafe5635SKent Overstreet int j; 426cafe5635SKent Overstreet struct bio_vec *bv; 427cafe5635SKent Overstreet void *base = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1)); 428cafe5635SKent Overstreet 429cafe5635SKent Overstreet bio_for_each_segment(bv, b->bio, j) 430cafe5635SKent Overstreet memcpy(page_address(bv->bv_page), 431cafe5635SKent Overstreet base + j * PAGE_SIZE, PAGE_SIZE); 432cafe5635SKent Overstreet 433cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 434cafe5635SKent Overstreet 43557943511SKent Overstreet continue_at(cl, btree_node_write_done, NULL); 436cafe5635SKent Overstreet } else { 437cafe5635SKent Overstreet b->bio->bi_vcnt = 0; 438169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 439cafe5635SKent Overstreet 440cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 441cafe5635SKent Overstreet 442cafe5635SKent Overstreet closure_sync(cl); 44357943511SKent Overstreet __btree_node_write_done(cl); 444cafe5635SKent Overstreet } 445cafe5635SKent Overstreet } 446cafe5635SKent Overstreet 44757943511SKent Overstreet void bch_btree_node_write(struct btree *b, struct closure *parent) 448cafe5635SKent Overstreet { 449cafe5635SKent Overstreet struct bset *i = b->sets[b->nsets].data; 450cafe5635SKent Overstreet 451c37511b8SKent Overstreet trace_bcache_btree_write(b); 452c37511b8SKent Overstreet 453cafe5635SKent Overstreet BUG_ON(current->bio_list); 45457943511SKent Overstreet BUG_ON(b->written >= btree_blocks(b)); 45557943511SKent Overstreet BUG_ON(b->written && !i->keys); 45657943511SKent Overstreet BUG_ON(b->sets->data->seq != i->seq); 457c37511b8SKent Overstreet bch_check_key_order(b, i); 458cafe5635SKent Overstreet 459cafe5635SKent Overstreet cancel_delayed_work(&b->work); 460cafe5635SKent Overstreet 46157943511SKent Overstreet /* If caller isn't waiting for write, parent refcount is cache set */ 46257943511SKent Overstreet closure_lock(&b->io, parent ?: &b->c->cl); 46357943511SKent Overstreet 464cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 465cafe5635SKent Overstreet change_bit(BTREE_NODE_write_idx, &b->flags); 466cafe5635SKent Overstreet 46757943511SKent Overstreet do_btree_node_write(b); 468cafe5635SKent Overstreet 469cafe5635SKent Overstreet b->written += set_blocks(i, b->c); 470cafe5635SKent Overstreet atomic_long_add(set_blocks(i, b->c) * b->c->sb.block_size, 471cafe5635SKent Overstreet &PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written); 472cafe5635SKent Overstreet 473cafe5635SKent Overstreet bch_btree_sort_lazy(b); 474cafe5635SKent Overstreet 475cafe5635SKent Overstreet if (b->written < btree_blocks(b)) 476cafe5635SKent Overstreet bch_bset_init_next(b); 477cafe5635SKent Overstreet } 478cafe5635SKent Overstreet 47957943511SKent Overstreet static void btree_node_write_work(struct work_struct *w) 480cafe5635SKent Overstreet { 481cafe5635SKent Overstreet struct btree *b = container_of(to_delayed_work(w), struct btree, work); 482cafe5635SKent Overstreet 48357943511SKent Overstreet rw_lock(true, b, b->level); 484cafe5635SKent Overstreet 485cafe5635SKent Overstreet if (btree_node_dirty(b)) 48657943511SKent Overstreet bch_btree_node_write(b, NULL); 48757943511SKent Overstreet rw_unlock(true, b); 488cafe5635SKent Overstreet } 489cafe5635SKent Overstreet 490c18536a7SKent Overstreet static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref) 491cafe5635SKent Overstreet { 492cafe5635SKent Overstreet struct bset *i = b->sets[b->nsets].data; 493cafe5635SKent Overstreet struct btree_write *w = btree_current_write(b); 494cafe5635SKent Overstreet 49557943511SKent Overstreet BUG_ON(!b->written); 49657943511SKent Overstreet BUG_ON(!i->keys); 497cafe5635SKent Overstreet 49857943511SKent Overstreet if (!btree_node_dirty(b)) 49957943511SKent Overstreet queue_delayed_work(btree_io_wq, &b->work, 30 * HZ); 50057943511SKent Overstreet 501cafe5635SKent Overstreet set_btree_node_dirty(b); 502cafe5635SKent Overstreet 503c18536a7SKent Overstreet if (journal_ref) { 504cafe5635SKent Overstreet if (w->journal && 505c18536a7SKent Overstreet journal_pin_cmp(b->c, w->journal, journal_ref)) { 506cafe5635SKent Overstreet atomic_dec_bug(w->journal); 507cafe5635SKent Overstreet w->journal = NULL; 508cafe5635SKent Overstreet } 509cafe5635SKent Overstreet 510cafe5635SKent Overstreet if (!w->journal) { 511c18536a7SKent Overstreet w->journal = journal_ref; 512cafe5635SKent Overstreet atomic_inc(w->journal); 513cafe5635SKent Overstreet } 514cafe5635SKent Overstreet } 515cafe5635SKent Overstreet 516cafe5635SKent Overstreet /* Force write if set is too big */ 51757943511SKent Overstreet if (set_bytes(i) > PAGE_SIZE - 48 && 51857943511SKent Overstreet !current->bio_list) 51957943511SKent Overstreet bch_btree_node_write(b, NULL); 520cafe5635SKent Overstreet } 521cafe5635SKent Overstreet 522cafe5635SKent Overstreet /* 523cafe5635SKent Overstreet * Btree in memory cache - allocation/freeing 524cafe5635SKent Overstreet * mca -> memory cache 525cafe5635SKent Overstreet */ 526cafe5635SKent Overstreet 527cafe5635SKent Overstreet static void mca_reinit(struct btree *b) 528cafe5635SKent Overstreet { 529cafe5635SKent Overstreet unsigned i; 530cafe5635SKent Overstreet 531cafe5635SKent Overstreet b->flags = 0; 532cafe5635SKent Overstreet b->written = 0; 533cafe5635SKent Overstreet b->nsets = 0; 534cafe5635SKent Overstreet 535cafe5635SKent Overstreet for (i = 0; i < MAX_BSETS; i++) 536cafe5635SKent Overstreet b->sets[i].size = 0; 537cafe5635SKent Overstreet /* 538cafe5635SKent Overstreet * Second loop starts at 1 because b->sets[0]->data is the memory we 539cafe5635SKent Overstreet * allocated 540cafe5635SKent Overstreet */ 541cafe5635SKent Overstreet for (i = 1; i < MAX_BSETS; i++) 542cafe5635SKent Overstreet b->sets[i].data = NULL; 543cafe5635SKent Overstreet } 544cafe5635SKent Overstreet 545cafe5635SKent Overstreet #define mca_reserve(c) (((c->root && c->root->level) \ 546cafe5635SKent Overstreet ? c->root->level : 1) * 8 + 16) 547cafe5635SKent Overstreet #define mca_can_free(c) \ 548cafe5635SKent Overstreet max_t(int, 0, c->bucket_cache_used - mca_reserve(c)) 549cafe5635SKent Overstreet 550cafe5635SKent Overstreet static void mca_data_free(struct btree *b) 551cafe5635SKent Overstreet { 552cafe5635SKent Overstreet struct bset_tree *t = b->sets; 553cafe5635SKent Overstreet BUG_ON(!closure_is_unlocked(&b->io.cl)); 554cafe5635SKent Overstreet 555cafe5635SKent Overstreet if (bset_prev_bytes(b) < PAGE_SIZE) 556cafe5635SKent Overstreet kfree(t->prev); 557cafe5635SKent Overstreet else 558cafe5635SKent Overstreet free_pages((unsigned long) t->prev, 559cafe5635SKent Overstreet get_order(bset_prev_bytes(b))); 560cafe5635SKent Overstreet 561cafe5635SKent Overstreet if (bset_tree_bytes(b) < PAGE_SIZE) 562cafe5635SKent Overstreet kfree(t->tree); 563cafe5635SKent Overstreet else 564cafe5635SKent Overstreet free_pages((unsigned long) t->tree, 565cafe5635SKent Overstreet get_order(bset_tree_bytes(b))); 566cafe5635SKent Overstreet 567cafe5635SKent Overstreet free_pages((unsigned long) t->data, b->page_order); 568cafe5635SKent Overstreet 569cafe5635SKent Overstreet t->prev = NULL; 570cafe5635SKent Overstreet t->tree = NULL; 571cafe5635SKent Overstreet t->data = NULL; 572cafe5635SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 573cafe5635SKent Overstreet b->c->bucket_cache_used--; 574cafe5635SKent Overstreet } 575cafe5635SKent Overstreet 576cafe5635SKent Overstreet static void mca_bucket_free(struct btree *b) 577cafe5635SKent Overstreet { 578cafe5635SKent Overstreet BUG_ON(btree_node_dirty(b)); 579cafe5635SKent Overstreet 580cafe5635SKent Overstreet b->key.ptr[0] = 0; 581cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 582cafe5635SKent Overstreet list_move(&b->list, &b->c->btree_cache_freeable); 583cafe5635SKent Overstreet } 584cafe5635SKent Overstreet 585cafe5635SKent Overstreet static unsigned btree_order(struct bkey *k) 586cafe5635SKent Overstreet { 587cafe5635SKent Overstreet return ilog2(KEY_SIZE(k) / PAGE_SECTORS ?: 1); 588cafe5635SKent Overstreet } 589cafe5635SKent Overstreet 590cafe5635SKent Overstreet static void mca_data_alloc(struct btree *b, struct bkey *k, gfp_t gfp) 591cafe5635SKent Overstreet { 592cafe5635SKent Overstreet struct bset_tree *t = b->sets; 593cafe5635SKent Overstreet BUG_ON(t->data); 594cafe5635SKent Overstreet 595cafe5635SKent Overstreet b->page_order = max_t(unsigned, 596cafe5635SKent Overstreet ilog2(b->c->btree_pages), 597cafe5635SKent Overstreet btree_order(k)); 598cafe5635SKent Overstreet 599cafe5635SKent Overstreet t->data = (void *) __get_free_pages(gfp, b->page_order); 600cafe5635SKent Overstreet if (!t->data) 601cafe5635SKent Overstreet goto err; 602cafe5635SKent Overstreet 603cafe5635SKent Overstreet t->tree = bset_tree_bytes(b) < PAGE_SIZE 604cafe5635SKent Overstreet ? kmalloc(bset_tree_bytes(b), gfp) 605cafe5635SKent Overstreet : (void *) __get_free_pages(gfp, get_order(bset_tree_bytes(b))); 606cafe5635SKent Overstreet if (!t->tree) 607cafe5635SKent Overstreet goto err; 608cafe5635SKent Overstreet 609cafe5635SKent Overstreet t->prev = bset_prev_bytes(b) < PAGE_SIZE 610cafe5635SKent Overstreet ? kmalloc(bset_prev_bytes(b), gfp) 611cafe5635SKent Overstreet : (void *) __get_free_pages(gfp, get_order(bset_prev_bytes(b))); 612cafe5635SKent Overstreet if (!t->prev) 613cafe5635SKent Overstreet goto err; 614cafe5635SKent Overstreet 615cafe5635SKent Overstreet list_move(&b->list, &b->c->btree_cache); 616cafe5635SKent Overstreet b->c->bucket_cache_used++; 617cafe5635SKent Overstreet return; 618cafe5635SKent Overstreet err: 619cafe5635SKent Overstreet mca_data_free(b); 620cafe5635SKent Overstreet } 621cafe5635SKent Overstreet 622cafe5635SKent Overstreet static struct btree *mca_bucket_alloc(struct cache_set *c, 623cafe5635SKent Overstreet struct bkey *k, gfp_t gfp) 624cafe5635SKent Overstreet { 625cafe5635SKent Overstreet struct btree *b = kzalloc(sizeof(struct btree), gfp); 626cafe5635SKent Overstreet if (!b) 627cafe5635SKent Overstreet return NULL; 628cafe5635SKent Overstreet 629cafe5635SKent Overstreet init_rwsem(&b->lock); 630cafe5635SKent Overstreet lockdep_set_novalidate_class(&b->lock); 631cafe5635SKent Overstreet INIT_LIST_HEAD(&b->list); 63257943511SKent Overstreet INIT_DELAYED_WORK(&b->work, btree_node_write_work); 633cafe5635SKent Overstreet b->c = c; 634cafe5635SKent Overstreet closure_init_unlocked(&b->io); 635cafe5635SKent Overstreet 636cafe5635SKent Overstreet mca_data_alloc(b, k, gfp); 637cafe5635SKent Overstreet return b; 638cafe5635SKent Overstreet } 639cafe5635SKent Overstreet 640e8e1d468SKent Overstreet static int mca_reap(struct btree *b, unsigned min_order, bool flush) 641cafe5635SKent Overstreet { 642e8e1d468SKent Overstreet struct closure cl; 643e8e1d468SKent Overstreet 644e8e1d468SKent Overstreet closure_init_stack(&cl); 645cafe5635SKent Overstreet lockdep_assert_held(&b->c->bucket_lock); 646cafe5635SKent Overstreet 647cafe5635SKent Overstreet if (!down_write_trylock(&b->lock)) 648cafe5635SKent Overstreet return -ENOMEM; 649cafe5635SKent Overstreet 650e8e1d468SKent Overstreet BUG_ON(btree_node_dirty(b) && !b->sets[0].data); 651e8e1d468SKent Overstreet 652e8e1d468SKent Overstreet if (b->page_order < min_order || 653e8e1d468SKent Overstreet (!flush && 654e8e1d468SKent Overstreet (btree_node_dirty(b) || 655e8e1d468SKent Overstreet atomic_read(&b->io.cl.remaining) != -1))) { 656cafe5635SKent Overstreet rw_unlock(true, b); 657cafe5635SKent Overstreet return -ENOMEM; 658cafe5635SKent Overstreet } 659cafe5635SKent Overstreet 660e8e1d468SKent Overstreet if (btree_node_dirty(b)) { 661e8e1d468SKent Overstreet bch_btree_node_write(b, &cl); 662e8e1d468SKent Overstreet closure_sync(&cl); 663cafe5635SKent Overstreet } 664cafe5635SKent Overstreet 665e8e1d468SKent Overstreet /* wait for any in flight btree write */ 666faadf0c9SKent Overstreet closure_wait_event(&b->io.wait, &cl, 667e8e1d468SKent Overstreet atomic_read(&b->io.cl.remaining) == -1); 668e8e1d468SKent Overstreet 669cafe5635SKent Overstreet return 0; 670cafe5635SKent Overstreet } 671cafe5635SKent Overstreet 6727dc19d5aSDave Chinner static unsigned long bch_mca_scan(struct shrinker *shrink, 6737dc19d5aSDave Chinner struct shrink_control *sc) 674cafe5635SKent Overstreet { 675cafe5635SKent Overstreet struct cache_set *c = container_of(shrink, struct cache_set, shrink); 676cafe5635SKent Overstreet struct btree *b, *t; 677cafe5635SKent Overstreet unsigned long i, nr = sc->nr_to_scan; 6787dc19d5aSDave Chinner unsigned long freed = 0; 679cafe5635SKent Overstreet 680cafe5635SKent Overstreet if (c->shrinker_disabled) 6817dc19d5aSDave Chinner return SHRINK_STOP; 682cafe5635SKent Overstreet 683cafe5635SKent Overstreet if (c->try_harder) 6847dc19d5aSDave Chinner return SHRINK_STOP; 685cafe5635SKent Overstreet 686cafe5635SKent Overstreet /* Return -1 if we can't do anything right now */ 687a698e08cSKent Overstreet if (sc->gfp_mask & __GFP_IO) 688cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 689cafe5635SKent Overstreet else if (!mutex_trylock(&c->bucket_lock)) 690cafe5635SKent Overstreet return -1; 691cafe5635SKent Overstreet 69236c9ea98SKent Overstreet /* 69336c9ea98SKent Overstreet * It's _really_ critical that we don't free too many btree nodes - we 69436c9ea98SKent Overstreet * have to always leave ourselves a reserve. The reserve is how we 69536c9ea98SKent Overstreet * guarantee that allocating memory for a new btree node can always 69636c9ea98SKent Overstreet * succeed, so that inserting keys into the btree can always succeed and 69736c9ea98SKent Overstreet * IO can always make forward progress: 69836c9ea98SKent Overstreet */ 699cafe5635SKent Overstreet nr /= c->btree_pages; 700cafe5635SKent Overstreet nr = min_t(unsigned long, nr, mca_can_free(c)); 701cafe5635SKent Overstreet 702cafe5635SKent Overstreet i = 0; 703cafe5635SKent Overstreet list_for_each_entry_safe(b, t, &c->btree_cache_freeable, list) { 7047dc19d5aSDave Chinner if (freed >= nr) 705cafe5635SKent Overstreet break; 706cafe5635SKent Overstreet 707cafe5635SKent Overstreet if (++i > 3 && 708e8e1d468SKent Overstreet !mca_reap(b, 0, false)) { 709cafe5635SKent Overstreet mca_data_free(b); 710cafe5635SKent Overstreet rw_unlock(true, b); 7117dc19d5aSDave Chinner freed++; 712cafe5635SKent Overstreet } 713cafe5635SKent Overstreet } 714cafe5635SKent Overstreet 715cafe5635SKent Overstreet /* 716cafe5635SKent Overstreet * Can happen right when we first start up, before we've read in any 717cafe5635SKent Overstreet * btree nodes 718cafe5635SKent Overstreet */ 719cafe5635SKent Overstreet if (list_empty(&c->btree_cache)) 720cafe5635SKent Overstreet goto out; 721cafe5635SKent Overstreet 7227dc19d5aSDave Chinner for (i = 0; (nr--) && i < c->bucket_cache_used; i++) { 723cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 724cafe5635SKent Overstreet list_rotate_left(&c->btree_cache); 725cafe5635SKent Overstreet 726cafe5635SKent Overstreet if (!b->accessed && 727e8e1d468SKent Overstreet !mca_reap(b, 0, false)) { 728cafe5635SKent Overstreet mca_bucket_free(b); 729cafe5635SKent Overstreet mca_data_free(b); 730cafe5635SKent Overstreet rw_unlock(true, b); 7317dc19d5aSDave Chinner freed++; 732cafe5635SKent Overstreet } else 733cafe5635SKent Overstreet b->accessed = 0; 734cafe5635SKent Overstreet } 735cafe5635SKent Overstreet out: 736cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 7377dc19d5aSDave Chinner return freed; 7387dc19d5aSDave Chinner } 7397dc19d5aSDave Chinner 7407dc19d5aSDave Chinner static unsigned long bch_mca_count(struct shrinker *shrink, 7417dc19d5aSDave Chinner struct shrink_control *sc) 7427dc19d5aSDave Chinner { 7437dc19d5aSDave Chinner struct cache_set *c = container_of(shrink, struct cache_set, shrink); 7447dc19d5aSDave Chinner 7457dc19d5aSDave Chinner if (c->shrinker_disabled) 7467dc19d5aSDave Chinner return 0; 7477dc19d5aSDave Chinner 7487dc19d5aSDave Chinner if (c->try_harder) 7497dc19d5aSDave Chinner return 0; 7507dc19d5aSDave Chinner 7517dc19d5aSDave Chinner return mca_can_free(c) * c->btree_pages; 752cafe5635SKent Overstreet } 753cafe5635SKent Overstreet 754cafe5635SKent Overstreet void bch_btree_cache_free(struct cache_set *c) 755cafe5635SKent Overstreet { 756cafe5635SKent Overstreet struct btree *b; 757cafe5635SKent Overstreet struct closure cl; 758cafe5635SKent Overstreet closure_init_stack(&cl); 759cafe5635SKent Overstreet 760cafe5635SKent Overstreet if (c->shrink.list.next) 761cafe5635SKent Overstreet unregister_shrinker(&c->shrink); 762cafe5635SKent Overstreet 763cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 764cafe5635SKent Overstreet 765cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 766cafe5635SKent Overstreet if (c->verify_data) 767cafe5635SKent Overstreet list_move(&c->verify_data->list, &c->btree_cache); 768cafe5635SKent Overstreet #endif 769cafe5635SKent Overstreet 770cafe5635SKent Overstreet list_splice(&c->btree_cache_freeable, 771cafe5635SKent Overstreet &c->btree_cache); 772cafe5635SKent Overstreet 773cafe5635SKent Overstreet while (!list_empty(&c->btree_cache)) { 774cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 775cafe5635SKent Overstreet 776cafe5635SKent Overstreet if (btree_node_dirty(b)) 777cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 778cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 779cafe5635SKent Overstreet 780cafe5635SKent Overstreet mca_data_free(b); 781cafe5635SKent Overstreet } 782cafe5635SKent Overstreet 783cafe5635SKent Overstreet while (!list_empty(&c->btree_cache_freed)) { 784cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache_freed, 785cafe5635SKent Overstreet struct btree, list); 786cafe5635SKent Overstreet list_del(&b->list); 787cafe5635SKent Overstreet cancel_delayed_work_sync(&b->work); 788cafe5635SKent Overstreet kfree(b); 789cafe5635SKent Overstreet } 790cafe5635SKent Overstreet 791cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 792cafe5635SKent Overstreet } 793cafe5635SKent Overstreet 794cafe5635SKent Overstreet int bch_btree_cache_alloc(struct cache_set *c) 795cafe5635SKent Overstreet { 796cafe5635SKent Overstreet unsigned i; 797cafe5635SKent Overstreet 798cafe5635SKent Overstreet for (i = 0; i < mca_reserve(c); i++) 79972a44517SKent Overstreet if (!mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL)) 80072a44517SKent Overstreet return -ENOMEM; 801cafe5635SKent Overstreet 802cafe5635SKent Overstreet list_splice_init(&c->btree_cache, 803cafe5635SKent Overstreet &c->btree_cache_freeable); 804cafe5635SKent Overstreet 805cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 806cafe5635SKent Overstreet mutex_init(&c->verify_lock); 807cafe5635SKent Overstreet 808cafe5635SKent Overstreet c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL); 809cafe5635SKent Overstreet 810cafe5635SKent Overstreet if (c->verify_data && 811cafe5635SKent Overstreet c->verify_data->sets[0].data) 812cafe5635SKent Overstreet list_del_init(&c->verify_data->list); 813cafe5635SKent Overstreet else 814cafe5635SKent Overstreet c->verify_data = NULL; 815cafe5635SKent Overstreet #endif 816cafe5635SKent Overstreet 8177dc19d5aSDave Chinner c->shrink.count_objects = bch_mca_count; 8187dc19d5aSDave Chinner c->shrink.scan_objects = bch_mca_scan; 819cafe5635SKent Overstreet c->shrink.seeks = 4; 820cafe5635SKent Overstreet c->shrink.batch = c->btree_pages * 2; 821cafe5635SKent Overstreet register_shrinker(&c->shrink); 822cafe5635SKent Overstreet 823cafe5635SKent Overstreet return 0; 824cafe5635SKent Overstreet } 825cafe5635SKent Overstreet 826cafe5635SKent Overstreet /* Btree in memory cache - hash table */ 827cafe5635SKent Overstreet 828cafe5635SKent Overstreet static struct hlist_head *mca_hash(struct cache_set *c, struct bkey *k) 829cafe5635SKent Overstreet { 830cafe5635SKent Overstreet return &c->bucket_hash[hash_32(PTR_HASH(c, k), BUCKET_HASH_BITS)]; 831cafe5635SKent Overstreet } 832cafe5635SKent Overstreet 833cafe5635SKent Overstreet static struct btree *mca_find(struct cache_set *c, struct bkey *k) 834cafe5635SKent Overstreet { 835cafe5635SKent Overstreet struct btree *b; 836cafe5635SKent Overstreet 837cafe5635SKent Overstreet rcu_read_lock(); 838cafe5635SKent Overstreet hlist_for_each_entry_rcu(b, mca_hash(c, k), hash) 839cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) == PTR_HASH(c, k)) 840cafe5635SKent Overstreet goto out; 841cafe5635SKent Overstreet b = NULL; 842cafe5635SKent Overstreet out: 843cafe5635SKent Overstreet rcu_read_unlock(); 844cafe5635SKent Overstreet return b; 845cafe5635SKent Overstreet } 846cafe5635SKent Overstreet 847e8e1d468SKent Overstreet static struct btree *mca_cannibalize(struct cache_set *c, struct bkey *k) 848cafe5635SKent Overstreet { 849e8e1d468SKent Overstreet struct btree *b; 850cafe5635SKent Overstreet 851c37511b8SKent Overstreet trace_bcache_btree_cache_cannibalize(c); 852c37511b8SKent Overstreet 853e8e1d468SKent Overstreet if (!c->try_harder) { 854e8e1d468SKent Overstreet c->try_harder = current; 855cafe5635SKent Overstreet c->try_harder_start = local_clock(); 856e8e1d468SKent Overstreet } else if (c->try_harder != current) 857e8e1d468SKent Overstreet return ERR_PTR(-ENOSPC); 858cafe5635SKent Overstreet 859e8e1d468SKent Overstreet list_for_each_entry_reverse(b, &c->btree_cache, list) 860e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), false)) 861e8e1d468SKent Overstreet return b; 862cafe5635SKent Overstreet 863e8e1d468SKent Overstreet list_for_each_entry_reverse(b, &c->btree_cache, list) 864e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), true)) 865e8e1d468SKent Overstreet return b; 866e8e1d468SKent Overstreet 867e8e1d468SKent Overstreet return ERR_PTR(-ENOMEM); 868cafe5635SKent Overstreet } 869cafe5635SKent Overstreet 870cafe5635SKent Overstreet /* 871cafe5635SKent Overstreet * We can only have one thread cannibalizing other cached btree nodes at a time, 872cafe5635SKent Overstreet * or we'll deadlock. We use an open coded mutex to ensure that, which a 873cafe5635SKent Overstreet * cannibalize_bucket() will take. This means every time we unlock the root of 874cafe5635SKent Overstreet * the btree, we need to release this lock if we have it held. 875cafe5635SKent Overstreet */ 876df8e8970SKent Overstreet static void bch_cannibalize_unlock(struct cache_set *c) 877cafe5635SKent Overstreet { 878e8e1d468SKent Overstreet if (c->try_harder == current) { 879169ef1cfSKent Overstreet bch_time_stats_update(&c->try_harder_time, c->try_harder_start); 880cafe5635SKent Overstreet c->try_harder = NULL; 881e8e1d468SKent Overstreet wake_up(&c->try_wait); 882cafe5635SKent Overstreet } 883cafe5635SKent Overstreet } 884cafe5635SKent Overstreet 885e8e1d468SKent Overstreet static struct btree *mca_alloc(struct cache_set *c, struct bkey *k, int level) 886cafe5635SKent Overstreet { 887cafe5635SKent Overstreet struct btree *b; 888cafe5635SKent Overstreet 889e8e1d468SKent Overstreet BUG_ON(current->bio_list); 890e8e1d468SKent Overstreet 891cafe5635SKent Overstreet lockdep_assert_held(&c->bucket_lock); 892cafe5635SKent Overstreet 893cafe5635SKent Overstreet if (mca_find(c, k)) 894cafe5635SKent Overstreet return NULL; 895cafe5635SKent Overstreet 896cafe5635SKent Overstreet /* btree_free() doesn't free memory; it sticks the node on the end of 897cafe5635SKent Overstreet * the list. Check if there's any freed nodes there: 898cafe5635SKent Overstreet */ 899cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freeable, list) 900e8e1d468SKent Overstreet if (!mca_reap(b, btree_order(k), false)) 901cafe5635SKent Overstreet goto out; 902cafe5635SKent Overstreet 903cafe5635SKent Overstreet /* We never free struct btree itself, just the memory that holds the on 904cafe5635SKent Overstreet * disk node. Check the freed list before allocating a new one: 905cafe5635SKent Overstreet */ 906cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freed, list) 907e8e1d468SKent Overstreet if (!mca_reap(b, 0, false)) { 908cafe5635SKent Overstreet mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO); 909cafe5635SKent Overstreet if (!b->sets[0].data) 910cafe5635SKent Overstreet goto err; 911cafe5635SKent Overstreet else 912cafe5635SKent Overstreet goto out; 913cafe5635SKent Overstreet } 914cafe5635SKent Overstreet 915cafe5635SKent Overstreet b = mca_bucket_alloc(c, k, __GFP_NOWARN|GFP_NOIO); 916cafe5635SKent Overstreet if (!b) 917cafe5635SKent Overstreet goto err; 918cafe5635SKent Overstreet 919cafe5635SKent Overstreet BUG_ON(!down_write_trylock(&b->lock)); 920cafe5635SKent Overstreet if (!b->sets->data) 921cafe5635SKent Overstreet goto err; 922cafe5635SKent Overstreet out: 923cafe5635SKent Overstreet BUG_ON(!closure_is_unlocked(&b->io.cl)); 924cafe5635SKent Overstreet 925cafe5635SKent Overstreet bkey_copy(&b->key, k); 926cafe5635SKent Overstreet list_move(&b->list, &c->btree_cache); 927cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 928cafe5635SKent Overstreet hlist_add_head_rcu(&b->hash, mca_hash(c, k)); 929cafe5635SKent Overstreet 930cafe5635SKent Overstreet lock_set_subclass(&b->lock.dep_map, level + 1, _THIS_IP_); 931cafe5635SKent Overstreet b->level = level; 932d6fd3b11SKent Overstreet b->parent = (void *) ~0UL; 933cafe5635SKent Overstreet 934cafe5635SKent Overstreet mca_reinit(b); 935cafe5635SKent Overstreet 936cafe5635SKent Overstreet return b; 937cafe5635SKent Overstreet err: 938cafe5635SKent Overstreet if (b) 939cafe5635SKent Overstreet rw_unlock(true, b); 940cafe5635SKent Overstreet 941e8e1d468SKent Overstreet b = mca_cannibalize(c, k); 942cafe5635SKent Overstreet if (!IS_ERR(b)) 943cafe5635SKent Overstreet goto out; 944cafe5635SKent Overstreet 945cafe5635SKent Overstreet return b; 946cafe5635SKent Overstreet } 947cafe5635SKent Overstreet 948cafe5635SKent Overstreet /** 949cafe5635SKent Overstreet * bch_btree_node_get - find a btree node in the cache and lock it, reading it 950cafe5635SKent Overstreet * in from disk if necessary. 951cafe5635SKent Overstreet * 952b54d6934SKent Overstreet * If IO is necessary and running under generic_make_request, returns -EAGAIN. 953cafe5635SKent Overstreet * 954cafe5635SKent Overstreet * The btree node will have either a read or a write lock held, depending on 955cafe5635SKent Overstreet * level and op->lock. 956cafe5635SKent Overstreet */ 957cafe5635SKent Overstreet struct btree *bch_btree_node_get(struct cache_set *c, struct bkey *k, 958e8e1d468SKent Overstreet int level, bool write) 959cafe5635SKent Overstreet { 960cafe5635SKent Overstreet int i = 0; 961cafe5635SKent Overstreet struct btree *b; 962cafe5635SKent Overstreet 963cafe5635SKent Overstreet BUG_ON(level < 0); 964cafe5635SKent Overstreet retry: 965cafe5635SKent Overstreet b = mca_find(c, k); 966cafe5635SKent Overstreet 967cafe5635SKent Overstreet if (!b) { 96857943511SKent Overstreet if (current->bio_list) 96957943511SKent Overstreet return ERR_PTR(-EAGAIN); 97057943511SKent Overstreet 971cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 972e8e1d468SKent Overstreet b = mca_alloc(c, k, level); 973cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 974cafe5635SKent Overstreet 975cafe5635SKent Overstreet if (!b) 976cafe5635SKent Overstreet goto retry; 977cafe5635SKent Overstreet if (IS_ERR(b)) 978cafe5635SKent Overstreet return b; 979cafe5635SKent Overstreet 98057943511SKent Overstreet bch_btree_node_read(b); 981cafe5635SKent Overstreet 982cafe5635SKent Overstreet if (!write) 983cafe5635SKent Overstreet downgrade_write(&b->lock); 984cafe5635SKent Overstreet } else { 985cafe5635SKent Overstreet rw_lock(write, b, level); 986cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) != PTR_HASH(c, k)) { 987cafe5635SKent Overstreet rw_unlock(write, b); 988cafe5635SKent Overstreet goto retry; 989cafe5635SKent Overstreet } 990cafe5635SKent Overstreet BUG_ON(b->level != level); 991cafe5635SKent Overstreet } 992cafe5635SKent Overstreet 993cafe5635SKent Overstreet b->accessed = 1; 994cafe5635SKent Overstreet 995cafe5635SKent Overstreet for (; i <= b->nsets && b->sets[i].size; i++) { 996cafe5635SKent Overstreet prefetch(b->sets[i].tree); 997cafe5635SKent Overstreet prefetch(b->sets[i].data); 998cafe5635SKent Overstreet } 999cafe5635SKent Overstreet 1000cafe5635SKent Overstreet for (; i <= b->nsets; i++) 1001cafe5635SKent Overstreet prefetch(b->sets[i].data); 1002cafe5635SKent Overstreet 100357943511SKent Overstreet if (btree_node_io_error(b)) { 1004cafe5635SKent Overstreet rw_unlock(write, b); 100557943511SKent Overstreet return ERR_PTR(-EIO); 100657943511SKent Overstreet } 100757943511SKent Overstreet 1008cafe5635SKent Overstreet BUG_ON(!b->written); 1009cafe5635SKent Overstreet 1010cafe5635SKent Overstreet return b; 1011cafe5635SKent Overstreet } 1012cafe5635SKent Overstreet 1013cafe5635SKent Overstreet static void btree_node_prefetch(struct cache_set *c, struct bkey *k, int level) 1014cafe5635SKent Overstreet { 1015cafe5635SKent Overstreet struct btree *b; 1016cafe5635SKent Overstreet 1017cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1018e8e1d468SKent Overstreet b = mca_alloc(c, k, level); 1019cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1020cafe5635SKent Overstreet 1021cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(b)) { 102257943511SKent Overstreet bch_btree_node_read(b); 1023cafe5635SKent Overstreet rw_unlock(true, b); 1024cafe5635SKent Overstreet } 1025cafe5635SKent Overstreet } 1026cafe5635SKent Overstreet 1027cafe5635SKent Overstreet /* Btree alloc */ 1028cafe5635SKent Overstreet 1029e8e1d468SKent Overstreet static void btree_node_free(struct btree *b) 1030cafe5635SKent Overstreet { 1031cafe5635SKent Overstreet unsigned i; 1032cafe5635SKent Overstreet 1033c37511b8SKent Overstreet trace_bcache_btree_node_free(b); 1034c37511b8SKent Overstreet 1035cafe5635SKent Overstreet BUG_ON(b == b->c->root); 1036cafe5635SKent Overstreet 1037cafe5635SKent Overstreet if (btree_node_dirty(b)) 1038cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 1039cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 1040cafe5635SKent Overstreet 1041cafe5635SKent Overstreet cancel_delayed_work(&b->work); 1042cafe5635SKent Overstreet 1043cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 1044cafe5635SKent Overstreet 1045cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) { 1046cafe5635SKent Overstreet BUG_ON(atomic_read(&PTR_BUCKET(b->c, &b->key, i)->pin)); 1047cafe5635SKent Overstreet 1048cafe5635SKent Overstreet bch_inc_gen(PTR_CACHE(b->c, &b->key, i), 1049cafe5635SKent Overstreet PTR_BUCKET(b->c, &b->key, i)); 1050cafe5635SKent Overstreet } 1051cafe5635SKent Overstreet 1052cafe5635SKent Overstreet bch_bucket_free(b->c, &b->key); 1053cafe5635SKent Overstreet mca_bucket_free(b); 1054cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 1055cafe5635SKent Overstreet } 1056cafe5635SKent Overstreet 105735fcd848SKent Overstreet struct btree *bch_btree_node_alloc(struct cache_set *c, int level) 1058cafe5635SKent Overstreet { 1059cafe5635SKent Overstreet BKEY_PADDED(key) k; 1060cafe5635SKent Overstreet struct btree *b = ERR_PTR(-EAGAIN); 1061cafe5635SKent Overstreet 1062cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1063cafe5635SKent Overstreet retry: 106435fcd848SKent Overstreet if (__bch_bucket_alloc_set(c, WATERMARK_METADATA, &k.key, 1, true)) 1065cafe5635SKent Overstreet goto err; 1066cafe5635SKent Overstreet 1067cafe5635SKent Overstreet SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS); 1068cafe5635SKent Overstreet 1069e8e1d468SKent Overstreet b = mca_alloc(c, &k.key, level); 1070cafe5635SKent Overstreet if (IS_ERR(b)) 1071cafe5635SKent Overstreet goto err_free; 1072cafe5635SKent Overstreet 1073cafe5635SKent Overstreet if (!b) { 1074b1a67b0fSKent Overstreet cache_bug(c, 1075b1a67b0fSKent Overstreet "Tried to allocate bucket that was in btree cache"); 1076cafe5635SKent Overstreet __bkey_put(c, &k.key); 1077cafe5635SKent Overstreet goto retry; 1078cafe5635SKent Overstreet } 1079cafe5635SKent Overstreet 1080cafe5635SKent Overstreet b->accessed = 1; 1081cafe5635SKent Overstreet bch_bset_init_next(b); 1082cafe5635SKent Overstreet 1083cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1084c37511b8SKent Overstreet 1085c37511b8SKent Overstreet trace_bcache_btree_node_alloc(b); 1086cafe5635SKent Overstreet return b; 1087cafe5635SKent Overstreet err_free: 1088cafe5635SKent Overstreet bch_bucket_free(c, &k.key); 1089cafe5635SKent Overstreet __bkey_put(c, &k.key); 1090cafe5635SKent Overstreet err: 1091cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1092c37511b8SKent Overstreet 1093c37511b8SKent Overstreet trace_bcache_btree_node_alloc_fail(b); 1094cafe5635SKent Overstreet return b; 1095cafe5635SKent Overstreet } 1096cafe5635SKent Overstreet 109735fcd848SKent Overstreet static struct btree *btree_node_alloc_replacement(struct btree *b) 1098cafe5635SKent Overstreet { 109935fcd848SKent Overstreet struct btree *n = bch_btree_node_alloc(b->c, b->level); 1100cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) 1101cafe5635SKent Overstreet bch_btree_sort_into(b, n); 1102cafe5635SKent Overstreet 1103cafe5635SKent Overstreet return n; 1104cafe5635SKent Overstreet } 1105cafe5635SKent Overstreet 1106cafe5635SKent Overstreet /* Garbage collection */ 1107cafe5635SKent Overstreet 1108cafe5635SKent Overstreet uint8_t __bch_btree_mark_key(struct cache_set *c, int level, struct bkey *k) 1109cafe5635SKent Overstreet { 1110cafe5635SKent Overstreet uint8_t stale = 0; 1111cafe5635SKent Overstreet unsigned i; 1112cafe5635SKent Overstreet struct bucket *g; 1113cafe5635SKent Overstreet 1114cafe5635SKent Overstreet /* 1115cafe5635SKent Overstreet * ptr_invalid() can't return true for the keys that mark btree nodes as 1116cafe5635SKent Overstreet * freed, but since ptr_bad() returns true we'll never actually use them 1117cafe5635SKent Overstreet * for anything and thus we don't want mark their pointers here 1118cafe5635SKent Overstreet */ 1119cafe5635SKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1120cafe5635SKent Overstreet return stale; 1121cafe5635SKent Overstreet 1122cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) { 1123cafe5635SKent Overstreet if (!ptr_available(c, k, i)) 1124cafe5635SKent Overstreet continue; 1125cafe5635SKent Overstreet 1126cafe5635SKent Overstreet g = PTR_BUCKET(c, k, i); 1127cafe5635SKent Overstreet 1128cafe5635SKent Overstreet if (gen_after(g->gc_gen, PTR_GEN(k, i))) 1129cafe5635SKent Overstreet g->gc_gen = PTR_GEN(k, i); 1130cafe5635SKent Overstreet 1131cafe5635SKent Overstreet if (ptr_stale(c, k, i)) { 1132cafe5635SKent Overstreet stale = max(stale, ptr_stale(c, k, i)); 1133cafe5635SKent Overstreet continue; 1134cafe5635SKent Overstreet } 1135cafe5635SKent Overstreet 1136cafe5635SKent Overstreet cache_bug_on(GC_MARK(g) && 1137cafe5635SKent Overstreet (GC_MARK(g) == GC_MARK_METADATA) != (level != 0), 1138cafe5635SKent Overstreet c, "inconsistent ptrs: mark = %llu, level = %i", 1139cafe5635SKent Overstreet GC_MARK(g), level); 1140cafe5635SKent Overstreet 1141cafe5635SKent Overstreet if (level) 1142cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_METADATA); 1143cafe5635SKent Overstreet else if (KEY_DIRTY(k)) 1144cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_DIRTY); 1145cafe5635SKent Overstreet 1146cafe5635SKent Overstreet /* guard against overflow */ 1147cafe5635SKent Overstreet SET_GC_SECTORS_USED(g, min_t(unsigned, 1148cafe5635SKent Overstreet GC_SECTORS_USED(g) + KEY_SIZE(k), 1149cafe5635SKent Overstreet (1 << 14) - 1)); 1150cafe5635SKent Overstreet 1151cafe5635SKent Overstreet BUG_ON(!GC_SECTORS_USED(g)); 1152cafe5635SKent Overstreet } 1153cafe5635SKent Overstreet 1154cafe5635SKent Overstreet return stale; 1155cafe5635SKent Overstreet } 1156cafe5635SKent Overstreet 1157cafe5635SKent Overstreet #define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k) 1158cafe5635SKent Overstreet 1159cafe5635SKent Overstreet static int btree_gc_mark_node(struct btree *b, unsigned *keys, 1160cafe5635SKent Overstreet struct gc_stat *gc) 1161cafe5635SKent Overstreet { 1162cafe5635SKent Overstreet uint8_t stale = 0; 1163cafe5635SKent Overstreet unsigned last_dev = -1; 1164cafe5635SKent Overstreet struct bcache_device *d = NULL; 1165cafe5635SKent Overstreet struct bkey *k; 1166cafe5635SKent Overstreet struct btree_iter iter; 1167cafe5635SKent Overstreet struct bset_tree *t; 1168cafe5635SKent Overstreet 1169cafe5635SKent Overstreet gc->nodes++; 1170cafe5635SKent Overstreet 1171cafe5635SKent Overstreet for_each_key_filter(b, k, &iter, bch_ptr_invalid) { 1172cafe5635SKent Overstreet if (last_dev != KEY_INODE(k)) { 1173cafe5635SKent Overstreet last_dev = KEY_INODE(k); 1174cafe5635SKent Overstreet 1175cafe5635SKent Overstreet d = KEY_INODE(k) < b->c->nr_uuids 1176cafe5635SKent Overstreet ? b->c->devices[last_dev] 1177cafe5635SKent Overstreet : NULL; 1178cafe5635SKent Overstreet } 1179cafe5635SKent Overstreet 1180cafe5635SKent Overstreet stale = max(stale, btree_mark_key(b, k)); 1181cafe5635SKent Overstreet 1182cafe5635SKent Overstreet if (bch_ptr_bad(b, k)) 1183cafe5635SKent Overstreet continue; 1184cafe5635SKent Overstreet 1185cafe5635SKent Overstreet *keys += bkey_u64s(k); 1186cafe5635SKent Overstreet 1187cafe5635SKent Overstreet gc->key_bytes += bkey_u64s(k); 1188cafe5635SKent Overstreet gc->nkeys++; 1189cafe5635SKent Overstreet 1190cafe5635SKent Overstreet gc->data += KEY_SIZE(k); 1191444fc0b6SKent Overstreet if (KEY_DIRTY(k)) 1192cafe5635SKent Overstreet gc->dirty += KEY_SIZE(k); 1193cafe5635SKent Overstreet } 1194cafe5635SKent Overstreet 1195cafe5635SKent Overstreet for (t = b->sets; t <= &b->sets[b->nsets]; t++) 1196cafe5635SKent Overstreet btree_bug_on(t->size && 1197cafe5635SKent Overstreet bset_written(b, t) && 1198cafe5635SKent Overstreet bkey_cmp(&b->key, &t->end) < 0, 1199cafe5635SKent Overstreet b, "found short btree key in gc"); 1200cafe5635SKent Overstreet 1201cafe5635SKent Overstreet return stale; 1202cafe5635SKent Overstreet } 1203cafe5635SKent Overstreet 1204e8e1d468SKent Overstreet static struct btree *btree_gc_alloc(struct btree *b, struct bkey *k) 1205cafe5635SKent Overstreet { 1206cafe5635SKent Overstreet /* 1207cafe5635SKent Overstreet * We block priorities from being written for the duration of garbage 1208cafe5635SKent Overstreet * collection, so we can't sleep in btree_alloc() -> 1209cafe5635SKent Overstreet * bch_bucket_alloc_set(), or we'd risk deadlock - so we don't pass it 1210cafe5635SKent Overstreet * our closure. 1211cafe5635SKent Overstreet */ 121235fcd848SKent Overstreet struct btree *n = btree_node_alloc_replacement(b); 1213cafe5635SKent Overstreet 1214cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 1215cafe5635SKent Overstreet swap(b, n); 121657943511SKent Overstreet __bkey_put(b->c, &b->key); 1217cafe5635SKent Overstreet 1218cafe5635SKent Overstreet memcpy(k->ptr, b->key.ptr, 1219cafe5635SKent Overstreet sizeof(uint64_t) * KEY_PTRS(&b->key)); 1220cafe5635SKent Overstreet 1221e8e1d468SKent Overstreet btree_node_free(n); 1222cafe5635SKent Overstreet up_write(&n->lock); 1223cafe5635SKent Overstreet } 1224cafe5635SKent Overstreet 1225cafe5635SKent Overstreet return b; 1226cafe5635SKent Overstreet } 1227cafe5635SKent Overstreet 1228cafe5635SKent Overstreet /* 1229cafe5635SKent Overstreet * Leaving this at 2 until we've got incremental garbage collection done; it 1230cafe5635SKent Overstreet * could be higher (and has been tested with 4) except that garbage collection 1231cafe5635SKent Overstreet * could take much longer, adversely affecting latency. 1232cafe5635SKent Overstreet */ 1233cafe5635SKent Overstreet #define GC_MERGE_NODES 2U 1234cafe5635SKent Overstreet 1235cafe5635SKent Overstreet struct gc_merge_info { 1236cafe5635SKent Overstreet struct btree *b; 1237cafe5635SKent Overstreet struct bkey *k; 1238cafe5635SKent Overstreet unsigned keys; 1239cafe5635SKent Overstreet }; 1240cafe5635SKent Overstreet 1241e8e1d468SKent Overstreet static void btree_gc_coalesce(struct btree *b, struct gc_stat *gc, 1242e8e1d468SKent Overstreet struct gc_merge_info *r) 1243cafe5635SKent Overstreet { 1244cafe5635SKent Overstreet unsigned nodes = 0, keys = 0, blocks; 1245cafe5635SKent Overstreet int i; 1246b54d6934SKent Overstreet struct closure cl; 1247b54d6934SKent Overstreet 1248b54d6934SKent Overstreet closure_init_stack(&cl); 1249cafe5635SKent Overstreet 1250cafe5635SKent Overstreet while (nodes < GC_MERGE_NODES && r[nodes].b) 1251cafe5635SKent Overstreet keys += r[nodes++].keys; 1252cafe5635SKent Overstreet 1253cafe5635SKent Overstreet blocks = btree_default_blocks(b->c) * 2 / 3; 1254cafe5635SKent Overstreet 1255cafe5635SKent Overstreet if (nodes < 2 || 1256cafe5635SKent Overstreet __set_blocks(b->sets[0].data, keys, b->c) > blocks * (nodes - 1)) 1257cafe5635SKent Overstreet return; 1258cafe5635SKent Overstreet 1259cafe5635SKent Overstreet for (i = nodes - 1; i >= 0; --i) { 1260cafe5635SKent Overstreet if (r[i].b->written) 1261e8e1d468SKent Overstreet r[i].b = btree_gc_alloc(r[i].b, r[i].k); 1262cafe5635SKent Overstreet 1263cafe5635SKent Overstreet if (r[i].b->written) 1264cafe5635SKent Overstreet return; 1265cafe5635SKent Overstreet } 1266cafe5635SKent Overstreet 1267cafe5635SKent Overstreet for (i = nodes - 1; i > 0; --i) { 1268cafe5635SKent Overstreet struct bset *n1 = r[i].b->sets->data; 1269cafe5635SKent Overstreet struct bset *n2 = r[i - 1].b->sets->data; 1270cafe5635SKent Overstreet struct bkey *k, *last = NULL; 1271cafe5635SKent Overstreet 1272cafe5635SKent Overstreet keys = 0; 1273cafe5635SKent Overstreet 1274cafe5635SKent Overstreet if (i == 1) { 1275cafe5635SKent Overstreet /* 1276cafe5635SKent Overstreet * Last node we're not getting rid of - we're getting 1277cafe5635SKent Overstreet * rid of the node at r[0]. Have to try and fit all of 1278cafe5635SKent Overstreet * the remaining keys into this node; we can't ensure 1279cafe5635SKent Overstreet * they will always fit due to rounding and variable 1280cafe5635SKent Overstreet * length keys (shouldn't be possible in practice, 1281cafe5635SKent Overstreet * though) 1282cafe5635SKent Overstreet */ 1283cafe5635SKent Overstreet if (__set_blocks(n1, n1->keys + r->keys, 1284cafe5635SKent Overstreet b->c) > btree_blocks(r[i].b)) 1285cafe5635SKent Overstreet return; 1286cafe5635SKent Overstreet 1287cafe5635SKent Overstreet keys = n2->keys; 1288cafe5635SKent Overstreet last = &r->b->key; 1289cafe5635SKent Overstreet } else 1290cafe5635SKent Overstreet for (k = n2->start; 1291cafe5635SKent Overstreet k < end(n2); 1292cafe5635SKent Overstreet k = bkey_next(k)) { 1293cafe5635SKent Overstreet if (__set_blocks(n1, n1->keys + keys + 1294cafe5635SKent Overstreet bkey_u64s(k), b->c) > blocks) 1295cafe5635SKent Overstreet break; 1296cafe5635SKent Overstreet 1297cafe5635SKent Overstreet last = k; 1298cafe5635SKent Overstreet keys += bkey_u64s(k); 1299cafe5635SKent Overstreet } 1300cafe5635SKent Overstreet 1301cafe5635SKent Overstreet BUG_ON(__set_blocks(n1, n1->keys + keys, 1302cafe5635SKent Overstreet b->c) > btree_blocks(r[i].b)); 1303cafe5635SKent Overstreet 1304cafe5635SKent Overstreet if (last) { 1305cafe5635SKent Overstreet bkey_copy_key(&r[i].b->key, last); 1306cafe5635SKent Overstreet bkey_copy_key(r[i].k, last); 1307cafe5635SKent Overstreet } 1308cafe5635SKent Overstreet 1309cafe5635SKent Overstreet memcpy(end(n1), 1310cafe5635SKent Overstreet n2->start, 1311cafe5635SKent Overstreet (void *) node(n2, keys) - (void *) n2->start); 1312cafe5635SKent Overstreet 1313cafe5635SKent Overstreet n1->keys += keys; 1314cafe5635SKent Overstreet 1315cafe5635SKent Overstreet memmove(n2->start, 1316cafe5635SKent Overstreet node(n2, keys), 1317cafe5635SKent Overstreet (void *) end(n2) - (void *) node(n2, keys)); 1318cafe5635SKent Overstreet 1319cafe5635SKent Overstreet n2->keys -= keys; 1320cafe5635SKent Overstreet 1321cafe5635SKent Overstreet r[i].keys = n1->keys; 1322cafe5635SKent Overstreet r[i - 1].keys = n2->keys; 1323cafe5635SKent Overstreet } 1324cafe5635SKent Overstreet 1325e8e1d468SKent Overstreet btree_node_free(r->b); 1326cafe5635SKent Overstreet up_write(&r->b->lock); 1327cafe5635SKent Overstreet 1328c37511b8SKent Overstreet trace_bcache_btree_gc_coalesce(nodes); 1329cafe5635SKent Overstreet 1330cafe5635SKent Overstreet gc->nodes--; 1331cafe5635SKent Overstreet nodes--; 1332cafe5635SKent Overstreet 1333cafe5635SKent Overstreet memmove(&r[0], &r[1], sizeof(struct gc_merge_info) * nodes); 1334cafe5635SKent Overstreet memset(&r[nodes], 0, sizeof(struct gc_merge_info)); 1335cafe5635SKent Overstreet } 1336cafe5635SKent Overstreet 1337cafe5635SKent Overstreet static int btree_gc_recurse(struct btree *b, struct btree_op *op, 1338cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1339cafe5635SKent Overstreet { 1340cafe5635SKent Overstreet void write(struct btree *r) 1341cafe5635SKent Overstreet { 1342b54d6934SKent Overstreet if (!r->written || btree_node_dirty(r)) 134357943511SKent Overstreet bch_btree_node_write(r, writes); 1344cafe5635SKent Overstreet 1345cafe5635SKent Overstreet up_write(&r->lock); 1346cafe5635SKent Overstreet } 1347cafe5635SKent Overstreet 1348cafe5635SKent Overstreet int ret = 0, stale; 1349cafe5635SKent Overstreet unsigned i; 1350cafe5635SKent Overstreet struct gc_merge_info r[GC_MERGE_NODES]; 1351cafe5635SKent Overstreet 1352cafe5635SKent Overstreet memset(r, 0, sizeof(r)); 1353cafe5635SKent Overstreet 1354cafe5635SKent Overstreet while ((r->k = bch_next_recurse_key(b, &b->c->gc_done))) { 1355e8e1d468SKent Overstreet r->b = bch_btree_node_get(b->c, r->k, b->level - 1, true); 1356cafe5635SKent Overstreet 1357cafe5635SKent Overstreet if (IS_ERR(r->b)) { 1358cafe5635SKent Overstreet ret = PTR_ERR(r->b); 1359cafe5635SKent Overstreet break; 1360cafe5635SKent Overstreet } 1361cafe5635SKent Overstreet 1362cafe5635SKent Overstreet r->keys = 0; 1363cafe5635SKent Overstreet stale = btree_gc_mark_node(r->b, &r->keys, gc); 1364cafe5635SKent Overstreet 1365cafe5635SKent Overstreet if (!b->written && 1366cafe5635SKent Overstreet (r->b->level || stale > 10 || 1367cafe5635SKent Overstreet b->c->gc_always_rewrite)) 1368e8e1d468SKent Overstreet r->b = btree_gc_alloc(r->b, r->k); 1369cafe5635SKent Overstreet 1370cafe5635SKent Overstreet if (r->b->level) 1371cafe5635SKent Overstreet ret = btree_gc_recurse(r->b, op, writes, gc); 1372cafe5635SKent Overstreet 1373cafe5635SKent Overstreet if (ret) { 1374cafe5635SKent Overstreet write(r->b); 1375cafe5635SKent Overstreet break; 1376cafe5635SKent Overstreet } 1377cafe5635SKent Overstreet 1378cafe5635SKent Overstreet bkey_copy_key(&b->c->gc_done, r->k); 1379cafe5635SKent Overstreet 1380cafe5635SKent Overstreet if (!b->written) 1381e8e1d468SKent Overstreet btree_gc_coalesce(b, gc, r); 1382cafe5635SKent Overstreet 1383cafe5635SKent Overstreet if (r[GC_MERGE_NODES - 1].b) 1384cafe5635SKent Overstreet write(r[GC_MERGE_NODES - 1].b); 1385cafe5635SKent Overstreet 1386cafe5635SKent Overstreet memmove(&r[1], &r[0], 1387cafe5635SKent Overstreet sizeof(struct gc_merge_info) * (GC_MERGE_NODES - 1)); 1388cafe5635SKent Overstreet 1389cafe5635SKent Overstreet /* When we've got incremental GC working, we'll want to do 1390cafe5635SKent Overstreet * if (should_resched()) 1391cafe5635SKent Overstreet * return -EAGAIN; 1392cafe5635SKent Overstreet */ 1393cafe5635SKent Overstreet cond_resched(); 1394cafe5635SKent Overstreet #if 0 1395cafe5635SKent Overstreet if (need_resched()) { 1396cafe5635SKent Overstreet ret = -EAGAIN; 1397cafe5635SKent Overstreet break; 1398cafe5635SKent Overstreet } 1399cafe5635SKent Overstreet #endif 1400cafe5635SKent Overstreet } 1401cafe5635SKent Overstreet 1402cafe5635SKent Overstreet for (i = 1; i < GC_MERGE_NODES && r[i].b; i++) 1403cafe5635SKent Overstreet write(r[i].b); 1404cafe5635SKent Overstreet 1405cafe5635SKent Overstreet /* Might have freed some children, must remove their keys */ 1406cafe5635SKent Overstreet if (!b->written) 1407cafe5635SKent Overstreet bch_btree_sort(b); 1408cafe5635SKent Overstreet 1409cafe5635SKent Overstreet return ret; 1410cafe5635SKent Overstreet } 1411cafe5635SKent Overstreet 1412cafe5635SKent Overstreet static int bch_btree_gc_root(struct btree *b, struct btree_op *op, 1413cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1414cafe5635SKent Overstreet { 1415cafe5635SKent Overstreet struct btree *n = NULL; 1416cafe5635SKent Overstreet unsigned keys = 0; 1417cafe5635SKent Overstreet int ret = 0, stale = btree_gc_mark_node(b, &keys, gc); 1418b54d6934SKent Overstreet struct closure cl; 1419b54d6934SKent Overstreet 1420b54d6934SKent Overstreet closure_init_stack(&cl); 1421cafe5635SKent Overstreet 1422cafe5635SKent Overstreet if (b->level || stale > 10) 142335fcd848SKent Overstreet n = btree_node_alloc_replacement(b); 1424cafe5635SKent Overstreet 1425cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) 1426cafe5635SKent Overstreet swap(b, n); 1427cafe5635SKent Overstreet 1428cafe5635SKent Overstreet if (b->level) 1429cafe5635SKent Overstreet ret = btree_gc_recurse(b, op, writes, gc); 1430cafe5635SKent Overstreet 1431cafe5635SKent Overstreet if (!b->written || btree_node_dirty(b)) { 1432b54d6934SKent Overstreet bch_btree_node_write(b, n ? &cl : NULL); 1433cafe5635SKent Overstreet } 1434cafe5635SKent Overstreet 1435cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 1436b54d6934SKent Overstreet closure_sync(&cl); 1437cafe5635SKent Overstreet bch_btree_set_root(b); 1438e8e1d468SKent Overstreet btree_node_free(n); 1439cafe5635SKent Overstreet rw_unlock(true, b); 1440cafe5635SKent Overstreet } 1441cafe5635SKent Overstreet 1442cafe5635SKent Overstreet return ret; 1443cafe5635SKent Overstreet } 1444cafe5635SKent Overstreet 1445cafe5635SKent Overstreet static void btree_gc_start(struct cache_set *c) 1446cafe5635SKent Overstreet { 1447cafe5635SKent Overstreet struct cache *ca; 1448cafe5635SKent Overstreet struct bucket *b; 1449cafe5635SKent Overstreet unsigned i; 1450cafe5635SKent Overstreet 1451cafe5635SKent Overstreet if (!c->gc_mark_valid) 1452cafe5635SKent Overstreet return; 1453cafe5635SKent Overstreet 1454cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1455cafe5635SKent Overstreet 1456cafe5635SKent Overstreet c->gc_mark_valid = 0; 1457cafe5635SKent Overstreet c->gc_done = ZERO_KEY; 1458cafe5635SKent Overstreet 1459cafe5635SKent Overstreet for_each_cache(ca, c, i) 1460cafe5635SKent Overstreet for_each_bucket(b, ca) { 1461cafe5635SKent Overstreet b->gc_gen = b->gen; 146229ebf465SKent Overstreet if (!atomic_read(&b->pin)) { 1463cafe5635SKent Overstreet SET_GC_MARK(b, GC_MARK_RECLAIMABLE); 146429ebf465SKent Overstreet SET_GC_SECTORS_USED(b, 0); 146529ebf465SKent Overstreet } 1466cafe5635SKent Overstreet } 1467cafe5635SKent Overstreet 1468cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1469cafe5635SKent Overstreet } 1470cafe5635SKent Overstreet 1471cafe5635SKent Overstreet size_t bch_btree_gc_finish(struct cache_set *c) 1472cafe5635SKent Overstreet { 1473cafe5635SKent Overstreet size_t available = 0; 1474cafe5635SKent Overstreet struct bucket *b; 1475cafe5635SKent Overstreet struct cache *ca; 1476cafe5635SKent Overstreet unsigned i; 1477cafe5635SKent Overstreet 1478cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1479cafe5635SKent Overstreet 1480cafe5635SKent Overstreet set_gc_sectors(c); 1481cafe5635SKent Overstreet c->gc_mark_valid = 1; 1482cafe5635SKent Overstreet c->need_gc = 0; 1483cafe5635SKent Overstreet 1484cafe5635SKent Overstreet if (c->root) 1485cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&c->root->key); i++) 1486cafe5635SKent Overstreet SET_GC_MARK(PTR_BUCKET(c, &c->root->key, i), 1487cafe5635SKent Overstreet GC_MARK_METADATA); 1488cafe5635SKent Overstreet 1489cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&c->uuid_bucket); i++) 1490cafe5635SKent Overstreet SET_GC_MARK(PTR_BUCKET(c, &c->uuid_bucket, i), 1491cafe5635SKent Overstreet GC_MARK_METADATA); 1492cafe5635SKent Overstreet 1493cafe5635SKent Overstreet for_each_cache(ca, c, i) { 1494cafe5635SKent Overstreet uint64_t *i; 1495cafe5635SKent Overstreet 1496cafe5635SKent Overstreet ca->invalidate_needs_gc = 0; 1497cafe5635SKent Overstreet 1498cafe5635SKent Overstreet for (i = ca->sb.d; i < ca->sb.d + ca->sb.keys; i++) 1499cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1500cafe5635SKent Overstreet 1501cafe5635SKent Overstreet for (i = ca->prio_buckets; 1502cafe5635SKent Overstreet i < ca->prio_buckets + prio_buckets(ca) * 2; i++) 1503cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1504cafe5635SKent Overstreet 1505cafe5635SKent Overstreet for_each_bucket(b, ca) { 1506cafe5635SKent Overstreet b->last_gc = b->gc_gen; 1507cafe5635SKent Overstreet c->need_gc = max(c->need_gc, bucket_gc_gen(b)); 1508cafe5635SKent Overstreet 1509cafe5635SKent Overstreet if (!atomic_read(&b->pin) && 1510cafe5635SKent Overstreet GC_MARK(b) == GC_MARK_RECLAIMABLE) { 1511cafe5635SKent Overstreet available++; 1512cafe5635SKent Overstreet if (!GC_SECTORS_USED(b)) 1513cafe5635SKent Overstreet bch_bucket_add_unused(ca, b); 1514cafe5635SKent Overstreet } 1515cafe5635SKent Overstreet } 1516cafe5635SKent Overstreet } 1517cafe5635SKent Overstreet 1518cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1519cafe5635SKent Overstreet return available; 1520cafe5635SKent Overstreet } 1521cafe5635SKent Overstreet 152272a44517SKent Overstreet static void bch_btree_gc(struct cache_set *c) 1523cafe5635SKent Overstreet { 1524cafe5635SKent Overstreet int ret; 1525cafe5635SKent Overstreet unsigned long available; 1526cafe5635SKent Overstreet struct gc_stat stats; 1527cafe5635SKent Overstreet struct closure writes; 1528cafe5635SKent Overstreet struct btree_op op; 1529cafe5635SKent Overstreet uint64_t start_time = local_clock(); 153057943511SKent Overstreet 1531c37511b8SKent Overstreet trace_bcache_gc_start(c); 1532cafe5635SKent Overstreet 1533cafe5635SKent Overstreet memset(&stats, 0, sizeof(struct gc_stat)); 1534cafe5635SKent Overstreet closure_init_stack(&writes); 1535b54d6934SKent Overstreet bch_btree_op_init(&op, SHRT_MAX); 1536cafe5635SKent Overstreet 1537cafe5635SKent Overstreet btree_gc_start(c); 1538cafe5635SKent Overstreet 153957943511SKent Overstreet atomic_inc(&c->prio_blocked); 154057943511SKent Overstreet 1541cafe5635SKent Overstreet ret = btree_root(gc_root, c, &op, &writes, &stats); 1542cafe5635SKent Overstreet closure_sync(&writes); 1543cafe5635SKent Overstreet 1544cafe5635SKent Overstreet if (ret) { 1545cafe5635SKent Overstreet pr_warn("gc failed!"); 154672a44517SKent Overstreet return; 1547cafe5635SKent Overstreet } 1548cafe5635SKent Overstreet 1549cafe5635SKent Overstreet /* Possibly wait for new UUIDs or whatever to hit disk */ 1550b54d6934SKent Overstreet bch_journal_meta(c, &writes); 1551b54d6934SKent Overstreet closure_sync(&writes); 1552cafe5635SKent Overstreet 1553cafe5635SKent Overstreet available = bch_btree_gc_finish(c); 1554cafe5635SKent Overstreet 155557943511SKent Overstreet atomic_dec(&c->prio_blocked); 155657943511SKent Overstreet wake_up_allocators(c); 155757943511SKent Overstreet 1558169ef1cfSKent Overstreet bch_time_stats_update(&c->btree_gc_time, start_time); 1559cafe5635SKent Overstreet 1560cafe5635SKent Overstreet stats.key_bytes *= sizeof(uint64_t); 1561cafe5635SKent Overstreet stats.dirty <<= 9; 1562cafe5635SKent Overstreet stats.data <<= 9; 1563cafe5635SKent Overstreet stats.in_use = (c->nbuckets - available) * 100 / c->nbuckets; 1564cafe5635SKent Overstreet memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat)); 1565cafe5635SKent Overstreet 1566c37511b8SKent Overstreet trace_bcache_gc_end(c); 1567cafe5635SKent Overstreet 156872a44517SKent Overstreet bch_moving_gc(c); 1569cafe5635SKent Overstreet } 1570cafe5635SKent Overstreet 157172a44517SKent Overstreet static int bch_gc_thread(void *arg) 1572cafe5635SKent Overstreet { 157372a44517SKent Overstreet struct cache_set *c = arg; 157472a44517SKent Overstreet 157572a44517SKent Overstreet while (1) { 157672a44517SKent Overstreet bch_btree_gc(c); 157772a44517SKent Overstreet 157872a44517SKent Overstreet set_current_state(TASK_INTERRUPTIBLE); 157972a44517SKent Overstreet if (kthread_should_stop()) 158072a44517SKent Overstreet break; 158172a44517SKent Overstreet 158272a44517SKent Overstreet try_to_freeze(); 158372a44517SKent Overstreet schedule(); 158472a44517SKent Overstreet } 158572a44517SKent Overstreet 158672a44517SKent Overstreet return 0; 158772a44517SKent Overstreet } 158872a44517SKent Overstreet 158972a44517SKent Overstreet int bch_gc_thread_start(struct cache_set *c) 159072a44517SKent Overstreet { 159172a44517SKent Overstreet c->gc_thread = kthread_create(bch_gc_thread, c, "bcache_gc"); 159272a44517SKent Overstreet if (IS_ERR(c->gc_thread)) 159372a44517SKent Overstreet return PTR_ERR(c->gc_thread); 159472a44517SKent Overstreet 159572a44517SKent Overstreet set_task_state(c->gc_thread, TASK_INTERRUPTIBLE); 159672a44517SKent Overstreet return 0; 1597cafe5635SKent Overstreet } 1598cafe5635SKent Overstreet 1599cafe5635SKent Overstreet /* Initial partial gc */ 1600cafe5635SKent Overstreet 1601cafe5635SKent Overstreet static int bch_btree_check_recurse(struct btree *b, struct btree_op *op, 1602cafe5635SKent Overstreet unsigned long **seen) 1603cafe5635SKent Overstreet { 1604cafe5635SKent Overstreet int ret; 1605cafe5635SKent Overstreet unsigned i; 1606cafe5635SKent Overstreet struct bkey *k; 1607cafe5635SKent Overstreet struct bucket *g; 1608cafe5635SKent Overstreet struct btree_iter iter; 1609cafe5635SKent Overstreet 1610cafe5635SKent Overstreet for_each_key_filter(b, k, &iter, bch_ptr_invalid) { 1611cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) { 1612cafe5635SKent Overstreet if (!ptr_available(b->c, k, i)) 1613cafe5635SKent Overstreet continue; 1614cafe5635SKent Overstreet 1615cafe5635SKent Overstreet g = PTR_BUCKET(b->c, k, i); 1616cafe5635SKent Overstreet 1617cafe5635SKent Overstreet if (!__test_and_set_bit(PTR_BUCKET_NR(b->c, k, i), 1618cafe5635SKent Overstreet seen[PTR_DEV(k, i)]) || 1619cafe5635SKent Overstreet !ptr_stale(b->c, k, i)) { 1620cafe5635SKent Overstreet g->gen = PTR_GEN(k, i); 1621cafe5635SKent Overstreet 1622cafe5635SKent Overstreet if (b->level) 1623cafe5635SKent Overstreet g->prio = BTREE_PRIO; 1624cafe5635SKent Overstreet else if (g->prio == BTREE_PRIO) 1625cafe5635SKent Overstreet g->prio = INITIAL_PRIO; 1626cafe5635SKent Overstreet } 1627cafe5635SKent Overstreet } 1628cafe5635SKent Overstreet 1629cafe5635SKent Overstreet btree_mark_key(b, k); 1630cafe5635SKent Overstreet } 1631cafe5635SKent Overstreet 1632cafe5635SKent Overstreet if (b->level) { 1633cafe5635SKent Overstreet k = bch_next_recurse_key(b, &ZERO_KEY); 1634cafe5635SKent Overstreet 1635cafe5635SKent Overstreet while (k) { 1636cafe5635SKent Overstreet struct bkey *p = bch_next_recurse_key(b, k); 1637cafe5635SKent Overstreet if (p) 1638cafe5635SKent Overstreet btree_node_prefetch(b->c, p, b->level - 1); 1639cafe5635SKent Overstreet 1640cafe5635SKent Overstreet ret = btree(check_recurse, k, b, op, seen); 1641cafe5635SKent Overstreet if (ret) 1642cafe5635SKent Overstreet return ret; 1643cafe5635SKent Overstreet 1644cafe5635SKent Overstreet k = p; 1645cafe5635SKent Overstreet } 1646cafe5635SKent Overstreet } 1647cafe5635SKent Overstreet 1648cafe5635SKent Overstreet return 0; 1649cafe5635SKent Overstreet } 1650cafe5635SKent Overstreet 1651c18536a7SKent Overstreet int bch_btree_check(struct cache_set *c) 1652cafe5635SKent Overstreet { 1653cafe5635SKent Overstreet int ret = -ENOMEM; 1654cafe5635SKent Overstreet unsigned i; 1655cafe5635SKent Overstreet unsigned long *seen[MAX_CACHES_PER_SET]; 1656c18536a7SKent Overstreet struct btree_op op; 1657cafe5635SKent Overstreet 1658cafe5635SKent Overstreet memset(seen, 0, sizeof(seen)); 1659b54d6934SKent Overstreet bch_btree_op_init(&op, SHRT_MAX); 1660cafe5635SKent Overstreet 1661cafe5635SKent Overstreet for (i = 0; c->cache[i]; i++) { 1662cafe5635SKent Overstreet size_t n = DIV_ROUND_UP(c->cache[i]->sb.nbuckets, 8); 1663cafe5635SKent Overstreet seen[i] = kmalloc(n, GFP_KERNEL); 1664cafe5635SKent Overstreet if (!seen[i]) 1665cafe5635SKent Overstreet goto err; 1666cafe5635SKent Overstreet 1667cafe5635SKent Overstreet /* Disables the seen array until prio_read() uses it too */ 1668cafe5635SKent Overstreet memset(seen[i], 0xFF, n); 1669cafe5635SKent Overstreet } 1670cafe5635SKent Overstreet 1671c18536a7SKent Overstreet ret = btree_root(check_recurse, c, &op, seen); 1672cafe5635SKent Overstreet err: 1673cafe5635SKent Overstreet for (i = 0; i < MAX_CACHES_PER_SET; i++) 1674cafe5635SKent Overstreet kfree(seen[i]); 1675cafe5635SKent Overstreet return ret; 1676cafe5635SKent Overstreet } 1677cafe5635SKent Overstreet 1678cafe5635SKent Overstreet /* Btree insertion */ 1679cafe5635SKent Overstreet 1680cafe5635SKent Overstreet static void shift_keys(struct btree *b, struct bkey *where, struct bkey *insert) 1681cafe5635SKent Overstreet { 1682cafe5635SKent Overstreet struct bset *i = b->sets[b->nsets].data; 1683cafe5635SKent Overstreet 1684cafe5635SKent Overstreet memmove((uint64_t *) where + bkey_u64s(insert), 1685cafe5635SKent Overstreet where, 1686cafe5635SKent Overstreet (void *) end(i) - (void *) where); 1687cafe5635SKent Overstreet 1688cafe5635SKent Overstreet i->keys += bkey_u64s(insert); 1689cafe5635SKent Overstreet bkey_copy(where, insert); 1690cafe5635SKent Overstreet bch_bset_fix_lookup_table(b, where); 1691cafe5635SKent Overstreet } 1692cafe5635SKent Overstreet 16931b207d80SKent Overstreet static bool fix_overlapping_extents(struct btree *b, struct bkey *insert, 1694cafe5635SKent Overstreet struct btree_iter *iter, 16951b207d80SKent Overstreet struct bkey *replace_key) 1696cafe5635SKent Overstreet { 1697279afbadSKent Overstreet void subtract_dirty(struct bkey *k, uint64_t offset, int sectors) 1698cafe5635SKent Overstreet { 1699279afbadSKent Overstreet if (KEY_DIRTY(k)) 1700279afbadSKent Overstreet bcache_dev_sectors_dirty_add(b->c, KEY_INODE(k), 1701279afbadSKent Overstreet offset, -sectors); 1702cafe5635SKent Overstreet } 1703cafe5635SKent Overstreet 1704279afbadSKent Overstreet uint64_t old_offset; 1705cafe5635SKent Overstreet unsigned old_size, sectors_found = 0; 1706cafe5635SKent Overstreet 1707cafe5635SKent Overstreet while (1) { 1708cafe5635SKent Overstreet struct bkey *k = bch_btree_iter_next(iter); 1709cafe5635SKent Overstreet if (!k || 1710cafe5635SKent Overstreet bkey_cmp(&START_KEY(k), insert) >= 0) 1711cafe5635SKent Overstreet break; 1712cafe5635SKent Overstreet 1713cafe5635SKent Overstreet if (bkey_cmp(k, &START_KEY(insert)) <= 0) 1714cafe5635SKent Overstreet continue; 1715cafe5635SKent Overstreet 1716279afbadSKent Overstreet old_offset = KEY_START(k); 1717cafe5635SKent Overstreet old_size = KEY_SIZE(k); 1718cafe5635SKent Overstreet 1719cafe5635SKent Overstreet /* 1720cafe5635SKent Overstreet * We might overlap with 0 size extents; we can't skip these 1721cafe5635SKent Overstreet * because if they're in the set we're inserting to we have to 1722cafe5635SKent Overstreet * adjust them so they don't overlap with the key we're 17231b207d80SKent Overstreet * inserting. But we don't want to check them for replace 1724cafe5635SKent Overstreet * operations. 1725cafe5635SKent Overstreet */ 1726cafe5635SKent Overstreet 17271b207d80SKent Overstreet if (replace_key && KEY_SIZE(k)) { 1728cafe5635SKent Overstreet /* 1729cafe5635SKent Overstreet * k might have been split since we inserted/found the 1730cafe5635SKent Overstreet * key we're replacing 1731cafe5635SKent Overstreet */ 1732cafe5635SKent Overstreet unsigned i; 1733cafe5635SKent Overstreet uint64_t offset = KEY_START(k) - 17341b207d80SKent Overstreet KEY_START(replace_key); 1735cafe5635SKent Overstreet 1736cafe5635SKent Overstreet /* But it must be a subset of the replace key */ 17371b207d80SKent Overstreet if (KEY_START(k) < KEY_START(replace_key) || 17381b207d80SKent Overstreet KEY_OFFSET(k) > KEY_OFFSET(replace_key)) 1739cafe5635SKent Overstreet goto check_failed; 1740cafe5635SKent Overstreet 1741cafe5635SKent Overstreet /* We didn't find a key that we were supposed to */ 1742cafe5635SKent Overstreet if (KEY_START(k) > KEY_START(insert) + sectors_found) 1743cafe5635SKent Overstreet goto check_failed; 1744cafe5635SKent Overstreet 17451b207d80SKent Overstreet if (KEY_PTRS(replace_key) != KEY_PTRS(k)) 1746cafe5635SKent Overstreet goto check_failed; 1747cafe5635SKent Overstreet 1748cafe5635SKent Overstreet /* skip past gen */ 1749cafe5635SKent Overstreet offset <<= 8; 1750cafe5635SKent Overstreet 17511b207d80SKent Overstreet BUG_ON(!KEY_PTRS(replace_key)); 1752cafe5635SKent Overstreet 17531b207d80SKent Overstreet for (i = 0; i < KEY_PTRS(replace_key); i++) 17541b207d80SKent Overstreet if (k->ptr[i] != replace_key->ptr[i] + offset) 1755cafe5635SKent Overstreet goto check_failed; 1756cafe5635SKent Overstreet 1757cafe5635SKent Overstreet sectors_found = KEY_OFFSET(k) - KEY_START(insert); 1758cafe5635SKent Overstreet } 1759cafe5635SKent Overstreet 1760cafe5635SKent Overstreet if (bkey_cmp(insert, k) < 0 && 1761cafe5635SKent Overstreet bkey_cmp(&START_KEY(insert), &START_KEY(k)) > 0) { 1762cafe5635SKent Overstreet /* 1763cafe5635SKent Overstreet * We overlapped in the middle of an existing key: that 1764cafe5635SKent Overstreet * means we have to split the old key. But we have to do 1765cafe5635SKent Overstreet * slightly different things depending on whether the 1766cafe5635SKent Overstreet * old key has been written out yet. 1767cafe5635SKent Overstreet */ 1768cafe5635SKent Overstreet 1769cafe5635SKent Overstreet struct bkey *top; 1770cafe5635SKent Overstreet 1771279afbadSKent Overstreet subtract_dirty(k, KEY_START(insert), KEY_SIZE(insert)); 1772cafe5635SKent Overstreet 1773cafe5635SKent Overstreet if (bkey_written(b, k)) { 1774cafe5635SKent Overstreet /* 1775cafe5635SKent Overstreet * We insert a new key to cover the top of the 1776cafe5635SKent Overstreet * old key, and the old key is modified in place 1777cafe5635SKent Overstreet * to represent the bottom split. 1778cafe5635SKent Overstreet * 1779cafe5635SKent Overstreet * It's completely arbitrary whether the new key 1780cafe5635SKent Overstreet * is the top or the bottom, but it has to match 1781cafe5635SKent Overstreet * up with what btree_sort_fixup() does - it 1782cafe5635SKent Overstreet * doesn't check for this kind of overlap, it 1783cafe5635SKent Overstreet * depends on us inserting a new key for the top 1784cafe5635SKent Overstreet * here. 1785cafe5635SKent Overstreet */ 1786cafe5635SKent Overstreet top = bch_bset_search(b, &b->sets[b->nsets], 1787cafe5635SKent Overstreet insert); 1788cafe5635SKent Overstreet shift_keys(b, top, k); 1789cafe5635SKent Overstreet } else { 1790cafe5635SKent Overstreet BKEY_PADDED(key) temp; 1791cafe5635SKent Overstreet bkey_copy(&temp.key, k); 1792cafe5635SKent Overstreet shift_keys(b, k, &temp.key); 1793cafe5635SKent Overstreet top = bkey_next(k); 1794cafe5635SKent Overstreet } 1795cafe5635SKent Overstreet 1796cafe5635SKent Overstreet bch_cut_front(insert, top); 1797cafe5635SKent Overstreet bch_cut_back(&START_KEY(insert), k); 1798cafe5635SKent Overstreet bch_bset_fix_invalidated_key(b, k); 1799cafe5635SKent Overstreet return false; 1800cafe5635SKent Overstreet } 1801cafe5635SKent Overstreet 1802cafe5635SKent Overstreet if (bkey_cmp(insert, k) < 0) { 1803cafe5635SKent Overstreet bch_cut_front(insert, k); 1804cafe5635SKent Overstreet } else { 18051fa8455dSKent Overstreet if (bkey_cmp(&START_KEY(insert), &START_KEY(k)) > 0) 18061fa8455dSKent Overstreet old_offset = KEY_START(insert); 18071fa8455dSKent Overstreet 1808cafe5635SKent Overstreet if (bkey_written(b, k) && 1809cafe5635SKent Overstreet bkey_cmp(&START_KEY(insert), &START_KEY(k)) <= 0) { 1810cafe5635SKent Overstreet /* 1811cafe5635SKent Overstreet * Completely overwrote, so we don't have to 1812cafe5635SKent Overstreet * invalidate the binary search tree 1813cafe5635SKent Overstreet */ 1814cafe5635SKent Overstreet bch_cut_front(k, k); 1815cafe5635SKent Overstreet } else { 1816cafe5635SKent Overstreet __bch_cut_back(&START_KEY(insert), k); 1817cafe5635SKent Overstreet bch_bset_fix_invalidated_key(b, k); 1818cafe5635SKent Overstreet } 1819cafe5635SKent Overstreet } 1820cafe5635SKent Overstreet 1821279afbadSKent Overstreet subtract_dirty(k, old_offset, old_size - KEY_SIZE(k)); 1822cafe5635SKent Overstreet } 1823cafe5635SKent Overstreet 1824cafe5635SKent Overstreet check_failed: 18251b207d80SKent Overstreet if (replace_key) { 1826cafe5635SKent Overstreet if (!sectors_found) { 1827cafe5635SKent Overstreet return true; 1828cafe5635SKent Overstreet } else if (sectors_found < KEY_SIZE(insert)) { 1829cafe5635SKent Overstreet SET_KEY_OFFSET(insert, KEY_OFFSET(insert) - 1830cafe5635SKent Overstreet (KEY_SIZE(insert) - sectors_found)); 1831cafe5635SKent Overstreet SET_KEY_SIZE(insert, sectors_found); 1832cafe5635SKent Overstreet } 1833cafe5635SKent Overstreet } 1834cafe5635SKent Overstreet 1835cafe5635SKent Overstreet return false; 1836cafe5635SKent Overstreet } 1837cafe5635SKent Overstreet 1838cafe5635SKent Overstreet static bool btree_insert_key(struct btree *b, struct btree_op *op, 18391b207d80SKent Overstreet struct bkey *k, struct bkey *replace_key) 1840cafe5635SKent Overstreet { 1841cafe5635SKent Overstreet struct bset *i = b->sets[b->nsets].data; 1842cafe5635SKent Overstreet struct bkey *m, *prev; 184385b1492eSKent Overstreet unsigned status = BTREE_INSERT_STATUS_INSERT; 1844cafe5635SKent Overstreet 1845cafe5635SKent Overstreet BUG_ON(bkey_cmp(k, &b->key) > 0); 1846cafe5635SKent Overstreet BUG_ON(b->level && !KEY_PTRS(k)); 1847cafe5635SKent Overstreet BUG_ON(!b->level && !KEY_OFFSET(k)); 1848cafe5635SKent Overstreet 1849cafe5635SKent Overstreet if (!b->level) { 1850cafe5635SKent Overstreet struct btree_iter iter; 1851cafe5635SKent Overstreet struct bkey search = KEY(KEY_INODE(k), KEY_START(k), 0); 1852cafe5635SKent Overstreet 1853cafe5635SKent Overstreet /* 1854cafe5635SKent Overstreet * bset_search() returns the first key that is strictly greater 1855cafe5635SKent Overstreet * than the search key - but for back merging, we want to find 1856cafe5635SKent Overstreet * the first key that is greater than or equal to KEY_START(k) - 1857cafe5635SKent Overstreet * unless KEY_START(k) is 0. 1858cafe5635SKent Overstreet */ 1859cafe5635SKent Overstreet if (KEY_OFFSET(&search)) 1860cafe5635SKent Overstreet SET_KEY_OFFSET(&search, KEY_OFFSET(&search) - 1); 1861cafe5635SKent Overstreet 1862cafe5635SKent Overstreet prev = NULL; 1863cafe5635SKent Overstreet m = bch_btree_iter_init(b, &iter, &search); 1864cafe5635SKent Overstreet 18651b207d80SKent Overstreet if (fix_overlapping_extents(b, k, &iter, replace_key)) { 18661b207d80SKent Overstreet op->insert_collision = true; 1867cafe5635SKent Overstreet return false; 18681b207d80SKent Overstreet } 1869cafe5635SKent Overstreet 18701fa8455dSKent Overstreet if (KEY_DIRTY(k)) 18711fa8455dSKent Overstreet bcache_dev_sectors_dirty_add(b->c, KEY_INODE(k), 18721fa8455dSKent Overstreet KEY_START(k), KEY_SIZE(k)); 18731fa8455dSKent Overstreet 1874cafe5635SKent Overstreet while (m != end(i) && 1875cafe5635SKent Overstreet bkey_cmp(k, &START_KEY(m)) > 0) 1876cafe5635SKent Overstreet prev = m, m = bkey_next(m); 1877cafe5635SKent Overstreet 1878cafe5635SKent Overstreet if (key_merging_disabled(b->c)) 1879cafe5635SKent Overstreet goto insert; 1880cafe5635SKent Overstreet 1881cafe5635SKent Overstreet /* prev is in the tree, if we merge we're done */ 188285b1492eSKent Overstreet status = BTREE_INSERT_STATUS_BACK_MERGE; 1883cafe5635SKent Overstreet if (prev && 1884cafe5635SKent Overstreet bch_bkey_try_merge(b, prev, k)) 1885cafe5635SKent Overstreet goto merged; 1886cafe5635SKent Overstreet 188785b1492eSKent Overstreet status = BTREE_INSERT_STATUS_OVERWROTE; 1888cafe5635SKent Overstreet if (m != end(i) && 1889cafe5635SKent Overstreet KEY_PTRS(m) == KEY_PTRS(k) && !KEY_SIZE(m)) 1890cafe5635SKent Overstreet goto copy; 1891cafe5635SKent Overstreet 189285b1492eSKent Overstreet status = BTREE_INSERT_STATUS_FRONT_MERGE; 1893cafe5635SKent Overstreet if (m != end(i) && 1894cafe5635SKent Overstreet bch_bkey_try_merge(b, k, m)) 1895cafe5635SKent Overstreet goto copy; 18961b207d80SKent Overstreet } else { 18971b207d80SKent Overstreet BUG_ON(replace_key); 1898cafe5635SKent Overstreet m = bch_bset_search(b, &b->sets[b->nsets], k); 18991b207d80SKent Overstreet } 1900cafe5635SKent Overstreet 1901cafe5635SKent Overstreet insert: shift_keys(b, m, k); 1902cafe5635SKent Overstreet copy: bkey_copy(m, k); 1903cafe5635SKent Overstreet merged: 19041b207d80SKent Overstreet bch_check_keys(b, "%u for %s", status, 19051b207d80SKent Overstreet replace_key ? "replace" : "insert"); 1906cafe5635SKent Overstreet 1907cafe5635SKent Overstreet if (b->level && !KEY_OFFSET(k)) 190857943511SKent Overstreet btree_current_write(b)->prio_blocked++; 1909cafe5635SKent Overstreet 19101b207d80SKent Overstreet trace_bcache_btree_insert_key(b, k, replace_key != NULL, status); 1911cafe5635SKent Overstreet 1912cafe5635SKent Overstreet return true; 1913cafe5635SKent Overstreet } 1914cafe5635SKent Overstreet 191526c949f8SKent Overstreet static bool bch_btree_insert_keys(struct btree *b, struct btree_op *op, 19161b207d80SKent Overstreet struct keylist *insert_keys, 19171b207d80SKent Overstreet struct bkey *replace_key) 1918cafe5635SKent Overstreet { 1919cafe5635SKent Overstreet bool ret = false; 1920cafe5635SKent Overstreet unsigned oldsize = bch_count_data(b); 1921cafe5635SKent Overstreet 192226c949f8SKent Overstreet while (!bch_keylist_empty(insert_keys)) { 1923403b6cdeSKent Overstreet struct bset *i = write_block(b); 1924c2f95ae2SKent Overstreet struct bkey *k = insert_keys->keys; 192526c949f8SKent Overstreet 1926403b6cdeSKent Overstreet if (b->written + __set_blocks(i, i->keys + bkey_u64s(k), b->c) 1927403b6cdeSKent Overstreet > btree_blocks(b)) 1928403b6cdeSKent Overstreet break; 1929403b6cdeSKent Overstreet 1930403b6cdeSKent Overstreet if (bkey_cmp(k, &b->key) <= 0) { 1931cafe5635SKent Overstreet bkey_put(b->c, k, b->level); 193226c949f8SKent Overstreet 19331b207d80SKent Overstreet ret |= btree_insert_key(b, op, k, replace_key); 193426c949f8SKent Overstreet bch_keylist_pop_front(insert_keys); 193526c949f8SKent Overstreet } else if (bkey_cmp(&START_KEY(k), &b->key) < 0) { 193626c949f8SKent Overstreet #if 0 19371b207d80SKent Overstreet if (replace_key) { 193826c949f8SKent Overstreet bkey_put(b->c, k, b->level); 193926c949f8SKent Overstreet bch_keylist_pop_front(insert_keys); 194026c949f8SKent Overstreet op->insert_collision = true; 194126c949f8SKent Overstreet break; 194226c949f8SKent Overstreet } 194326c949f8SKent Overstreet #endif 194426c949f8SKent Overstreet BKEY_PADDED(key) temp; 1945c2f95ae2SKent Overstreet bkey_copy(&temp.key, insert_keys->keys); 194626c949f8SKent Overstreet 194726c949f8SKent Overstreet bch_cut_back(&b->key, &temp.key); 1948c2f95ae2SKent Overstreet bch_cut_front(&b->key, insert_keys->keys); 194926c949f8SKent Overstreet 19501b207d80SKent Overstreet ret |= btree_insert_key(b, op, &temp.key, replace_key); 195126c949f8SKent Overstreet break; 195226c949f8SKent Overstreet } else { 195326c949f8SKent Overstreet break; 195426c949f8SKent Overstreet } 1955cafe5635SKent Overstreet } 1956cafe5635SKent Overstreet 1957403b6cdeSKent Overstreet BUG_ON(!bch_keylist_empty(insert_keys) && b->level); 1958403b6cdeSKent Overstreet 1959cafe5635SKent Overstreet BUG_ON(bch_count_data(b) < oldsize); 1960cafe5635SKent Overstreet return ret; 1961cafe5635SKent Overstreet } 1962cafe5635SKent Overstreet 196326c949f8SKent Overstreet static int btree_split(struct btree *b, struct btree_op *op, 196426c949f8SKent Overstreet struct keylist *insert_keys, 19651b207d80SKent Overstreet struct keylist *parent_keys, 19661b207d80SKent Overstreet struct bkey *replace_key) 1967cafe5635SKent Overstreet { 1968d6fd3b11SKent Overstreet bool split; 1969cafe5635SKent Overstreet struct btree *n1, *n2 = NULL, *n3 = NULL; 1970cafe5635SKent Overstreet uint64_t start_time = local_clock(); 1971b54d6934SKent Overstreet struct closure cl; 1972b54d6934SKent Overstreet 1973b54d6934SKent Overstreet closure_init_stack(&cl); 1974cafe5635SKent Overstreet 197535fcd848SKent Overstreet n1 = btree_node_alloc_replacement(b); 1976cafe5635SKent Overstreet if (IS_ERR(n1)) 1977cafe5635SKent Overstreet goto err; 1978cafe5635SKent Overstreet 1979cafe5635SKent Overstreet split = set_blocks(n1->sets[0].data, n1->c) > (btree_blocks(b) * 4) / 5; 1980cafe5635SKent Overstreet 1981cafe5635SKent Overstreet if (split) { 1982cafe5635SKent Overstreet unsigned keys = 0; 1983cafe5635SKent Overstreet 1984c37511b8SKent Overstreet trace_bcache_btree_node_split(b, n1->sets[0].data->keys); 1985c37511b8SKent Overstreet 198635fcd848SKent Overstreet n2 = bch_btree_node_alloc(b->c, b->level); 1987cafe5635SKent Overstreet if (IS_ERR(n2)) 1988cafe5635SKent Overstreet goto err_free1; 1989cafe5635SKent Overstreet 1990d6fd3b11SKent Overstreet if (!b->parent) { 199135fcd848SKent Overstreet n3 = bch_btree_node_alloc(b->c, b->level + 1); 1992cafe5635SKent Overstreet if (IS_ERR(n3)) 1993cafe5635SKent Overstreet goto err_free2; 1994cafe5635SKent Overstreet } 1995cafe5635SKent Overstreet 19961b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 1997cafe5635SKent Overstreet 1998d6fd3b11SKent Overstreet /* 1999d6fd3b11SKent Overstreet * Has to be a linear search because we don't have an auxiliary 2000cafe5635SKent Overstreet * search tree yet 2001cafe5635SKent Overstreet */ 2002cafe5635SKent Overstreet 2003cafe5635SKent Overstreet while (keys < (n1->sets[0].data->keys * 3) / 5) 2004cafe5635SKent Overstreet keys += bkey_u64s(node(n1->sets[0].data, keys)); 2005cafe5635SKent Overstreet 2006cafe5635SKent Overstreet bkey_copy_key(&n1->key, node(n1->sets[0].data, keys)); 2007cafe5635SKent Overstreet keys += bkey_u64s(node(n1->sets[0].data, keys)); 2008cafe5635SKent Overstreet 2009cafe5635SKent Overstreet n2->sets[0].data->keys = n1->sets[0].data->keys - keys; 2010cafe5635SKent Overstreet n1->sets[0].data->keys = keys; 2011cafe5635SKent Overstreet 2012cafe5635SKent Overstreet memcpy(n2->sets[0].data->start, 2013cafe5635SKent Overstreet end(n1->sets[0].data), 2014cafe5635SKent Overstreet n2->sets[0].data->keys * sizeof(uint64_t)); 2015cafe5635SKent Overstreet 2016cafe5635SKent Overstreet bkey_copy_key(&n2->key, &b->key); 2017cafe5635SKent Overstreet 201826c949f8SKent Overstreet bch_keylist_add(parent_keys, &n2->key); 2019b54d6934SKent Overstreet bch_btree_node_write(n2, &cl); 2020cafe5635SKent Overstreet rw_unlock(true, n2); 2021c37511b8SKent Overstreet } else { 2022c37511b8SKent Overstreet trace_bcache_btree_node_compact(b, n1->sets[0].data->keys); 2023c37511b8SKent Overstreet 20241b207d80SKent Overstreet bch_btree_insert_keys(n1, op, insert_keys, replace_key); 2025c37511b8SKent Overstreet } 2026cafe5635SKent Overstreet 202726c949f8SKent Overstreet bch_keylist_add(parent_keys, &n1->key); 2028b54d6934SKent Overstreet bch_btree_node_write(n1, &cl); 2029cafe5635SKent Overstreet 2030cafe5635SKent Overstreet if (n3) { 2031d6fd3b11SKent Overstreet /* Depth increases, make a new root */ 2032d6fd3b11SKent Overstreet 2033cafe5635SKent Overstreet bkey_copy_key(&n3->key, &MAX_KEY); 20341b207d80SKent Overstreet bch_btree_insert_keys(n3, op, parent_keys, NULL); 2035b54d6934SKent Overstreet bch_btree_node_write(n3, &cl); 2036cafe5635SKent Overstreet 2037b54d6934SKent Overstreet closure_sync(&cl); 2038cafe5635SKent Overstreet bch_btree_set_root(n3); 2039cafe5635SKent Overstreet rw_unlock(true, n3); 2040d6fd3b11SKent Overstreet } else if (!b->parent) { 2041d6fd3b11SKent Overstreet /* Root filled up but didn't need to be split */ 2042d6fd3b11SKent Overstreet 2043c2f95ae2SKent Overstreet bch_keylist_reset(parent_keys); 2044b54d6934SKent Overstreet closure_sync(&cl); 2045cafe5635SKent Overstreet bch_btree_set_root(n1); 2046cafe5635SKent Overstreet } else { 2047cafe5635SKent Overstreet unsigned i; 2048cafe5635SKent Overstreet 204926c949f8SKent Overstreet bkey_copy(parent_keys->top, &b->key); 205026c949f8SKent Overstreet bkey_copy_key(parent_keys->top, &ZERO_KEY); 2051cafe5635SKent Overstreet 2052cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) { 2053cafe5635SKent Overstreet uint8_t g = PTR_BUCKET(b->c, &b->key, i)->gen + 1; 2054cafe5635SKent Overstreet 205526c949f8SKent Overstreet SET_PTR_GEN(parent_keys->top, i, g); 2056cafe5635SKent Overstreet } 2057cafe5635SKent Overstreet 205826c949f8SKent Overstreet bch_keylist_push(parent_keys); 2059b54d6934SKent Overstreet closure_sync(&cl); 2060cafe5635SKent Overstreet atomic_inc(&b->c->prio_blocked); 2061cafe5635SKent Overstreet } 2062cafe5635SKent Overstreet 2063cafe5635SKent Overstreet rw_unlock(true, n1); 2064e8e1d468SKent Overstreet btree_node_free(b); 2065cafe5635SKent Overstreet 2066169ef1cfSKent Overstreet bch_time_stats_update(&b->c->btree_split_time, start_time); 2067cafe5635SKent Overstreet 2068cafe5635SKent Overstreet return 0; 2069cafe5635SKent Overstreet err_free2: 2070cafe5635SKent Overstreet __bkey_put(n2->c, &n2->key); 2071e8e1d468SKent Overstreet btree_node_free(n2); 2072cafe5635SKent Overstreet rw_unlock(true, n2); 2073cafe5635SKent Overstreet err_free1: 2074cafe5635SKent Overstreet __bkey_put(n1->c, &n1->key); 2075e8e1d468SKent Overstreet btree_node_free(n1); 2076cafe5635SKent Overstreet rw_unlock(true, n1); 2077cafe5635SKent Overstreet err: 2078cafe5635SKent Overstreet if (n3 == ERR_PTR(-EAGAIN) || 2079cafe5635SKent Overstreet n2 == ERR_PTR(-EAGAIN) || 2080cafe5635SKent Overstreet n1 == ERR_PTR(-EAGAIN)) 2081cafe5635SKent Overstreet return -EAGAIN; 2082cafe5635SKent Overstreet 2083cafe5635SKent Overstreet pr_warn("couldn't split"); 2084cafe5635SKent Overstreet return -ENOMEM; 2085cafe5635SKent Overstreet } 2086cafe5635SKent Overstreet 208726c949f8SKent Overstreet static int bch_btree_insert_node(struct btree *b, struct btree_op *op, 2088c18536a7SKent Overstreet struct keylist *insert_keys, 20891b207d80SKent Overstreet atomic_t *journal_ref, 20901b207d80SKent Overstreet struct bkey *replace_key) 209126c949f8SKent Overstreet { 209226c949f8SKent Overstreet int ret = 0; 209326c949f8SKent Overstreet struct keylist split_keys; 209426c949f8SKent Overstreet 209526c949f8SKent Overstreet bch_keylist_init(&split_keys); 209626c949f8SKent Overstreet 209726c949f8SKent Overstreet BUG_ON(b->level); 209826c949f8SKent Overstreet 209926c949f8SKent Overstreet do { 21001b207d80SKent Overstreet BUG_ON(b->level && replace_key); 21011b207d80SKent Overstreet 210226c949f8SKent Overstreet if (should_split(b)) { 210326c949f8SKent Overstreet if (current->bio_list) { 210426c949f8SKent Overstreet op->lock = b->c->root->level + 1; 210526c949f8SKent Overstreet ret = -EAGAIN; 210626c949f8SKent Overstreet } else if (op->lock <= b->c->root->level) { 210726c949f8SKent Overstreet op->lock = b->c->root->level + 1; 210826c949f8SKent Overstreet ret = -EINTR; 210926c949f8SKent Overstreet } else { 211026c949f8SKent Overstreet struct btree *parent = b->parent; 211126c949f8SKent Overstreet 211226c949f8SKent Overstreet ret = btree_split(b, op, insert_keys, 21131b207d80SKent Overstreet &split_keys, replace_key); 211426c949f8SKent Overstreet insert_keys = &split_keys; 21151b207d80SKent Overstreet replace_key = NULL; 211626c949f8SKent Overstreet b = parent; 2117403b6cdeSKent Overstreet if (!ret) 2118403b6cdeSKent Overstreet ret = -EINTR; 211926c949f8SKent Overstreet } 212026c949f8SKent Overstreet } else { 212126c949f8SKent Overstreet BUG_ON(write_block(b) != b->sets[b->nsets].data); 212226c949f8SKent Overstreet 21231b207d80SKent Overstreet if (bch_btree_insert_keys(b, op, insert_keys, 21241b207d80SKent Overstreet replace_key)) { 2125b54d6934SKent Overstreet if (!b->level) { 2126c18536a7SKent Overstreet bch_btree_leaf_dirty(b, journal_ref); 2127b54d6934SKent Overstreet } else { 2128b54d6934SKent Overstreet struct closure cl; 2129b54d6934SKent Overstreet 2130b54d6934SKent Overstreet closure_init_stack(&cl); 2131b54d6934SKent Overstreet bch_btree_node_write(b, &cl); 2132b54d6934SKent Overstreet closure_sync(&cl); 2133b54d6934SKent Overstreet } 213426c949f8SKent Overstreet } 213526c949f8SKent Overstreet } 213626c949f8SKent Overstreet } while (!bch_keylist_empty(&split_keys)); 213726c949f8SKent Overstreet 213826c949f8SKent Overstreet return ret; 213926c949f8SKent Overstreet } 214026c949f8SKent Overstreet 2141e7c590ebSKent Overstreet int bch_btree_insert_check_key(struct btree *b, struct btree_op *op, 2142e7c590ebSKent Overstreet struct bkey *check_key) 2143e7c590ebSKent Overstreet { 2144e7c590ebSKent Overstreet int ret = -EINTR; 2145e7c590ebSKent Overstreet uint64_t btree_ptr = b->key.ptr[0]; 2146e7c590ebSKent Overstreet unsigned long seq = b->seq; 2147e7c590ebSKent Overstreet struct keylist insert; 2148e7c590ebSKent Overstreet bool upgrade = op->lock == -1; 2149e7c590ebSKent Overstreet 2150e7c590ebSKent Overstreet bch_keylist_init(&insert); 2151e7c590ebSKent Overstreet 2152e7c590ebSKent Overstreet if (upgrade) { 2153e7c590ebSKent Overstreet rw_unlock(false, b); 2154e7c590ebSKent Overstreet rw_lock(true, b, b->level); 2155e7c590ebSKent Overstreet 2156e7c590ebSKent Overstreet if (b->key.ptr[0] != btree_ptr || 2157e7c590ebSKent Overstreet b->seq != seq + 1) 2158e7c590ebSKent Overstreet goto out; 2159e7c590ebSKent Overstreet } 2160e7c590ebSKent Overstreet 2161e7c590ebSKent Overstreet SET_KEY_PTRS(check_key, 1); 2162e7c590ebSKent Overstreet get_random_bytes(&check_key->ptr[0], sizeof(uint64_t)); 2163e7c590ebSKent Overstreet 2164e7c590ebSKent Overstreet SET_PTR_DEV(check_key, 0, PTR_CHECK_DEV); 2165e7c590ebSKent Overstreet 2166e7c590ebSKent Overstreet bch_keylist_add(&insert, check_key); 2167e7c590ebSKent Overstreet 21681b207d80SKent Overstreet ret = bch_btree_insert_node(b, op, &insert, NULL, NULL); 2169e7c590ebSKent Overstreet 2170e7c590ebSKent Overstreet BUG_ON(!ret && !bch_keylist_empty(&insert)); 2171e7c590ebSKent Overstreet out: 2172e7c590ebSKent Overstreet if (upgrade) 2173e7c590ebSKent Overstreet downgrade_write(&b->lock); 2174e7c590ebSKent Overstreet return ret; 2175e7c590ebSKent Overstreet } 2176e7c590ebSKent Overstreet 21774f3d4014SKent Overstreet static int bch_btree_insert_recurse(struct btree *b, struct btree_op *op, 21781b207d80SKent Overstreet struct keylist *keys, atomic_t *journal_ref, 21791b207d80SKent Overstreet struct bkey *replace_key) 2180cafe5635SKent Overstreet { 21814f3d4014SKent Overstreet if (bch_keylist_empty(keys)) 2182403b6cdeSKent Overstreet return 0; 2183403b6cdeSKent Overstreet 2184cafe5635SKent Overstreet if (b->level) { 21854f3d4014SKent Overstreet struct bkey *k; 2186cafe5635SKent Overstreet 2187c2f95ae2SKent Overstreet k = bch_next_recurse_key(b, &START_KEY(keys->keys)); 2188cafe5635SKent Overstreet if (!k) { 2189cafe5635SKent Overstreet btree_bug(b, "no key to recurse on at level %i/%i", 2190cafe5635SKent Overstreet b->level, b->c->root->level); 2191cafe5635SKent Overstreet 2192c2f95ae2SKent Overstreet bch_keylist_reset(keys); 2193cafe5635SKent Overstreet return -EIO; 2194cafe5635SKent Overstreet } 2195cafe5635SKent Overstreet 21961b207d80SKent Overstreet return btree(insert_recurse, k, b, op, keys, 21971b207d80SKent Overstreet journal_ref, replace_key); 219826c949f8SKent Overstreet } else { 21991b207d80SKent Overstreet return bch_btree_insert_node(b, op, keys, 22001b207d80SKent Overstreet journal_ref, replace_key); 2201cafe5635SKent Overstreet } 2202cafe5635SKent Overstreet } 2203cafe5635SKent Overstreet 22044f3d4014SKent Overstreet int bch_btree_insert(struct btree_op *op, struct cache_set *c, 22051b207d80SKent Overstreet struct keylist *keys, atomic_t *journal_ref, 22061b207d80SKent Overstreet struct bkey *replace_key) 2207cafe5635SKent Overstreet { 2208cafe5635SKent Overstreet int ret = 0; 2209cafe5635SKent Overstreet 22104f3d4014SKent Overstreet BUG_ON(bch_keylist_empty(keys)); 2211cafe5635SKent Overstreet 22124f3d4014SKent Overstreet while (!bch_keylist_empty(keys)) { 2213cafe5635SKent Overstreet op->lock = 0; 22141b207d80SKent Overstreet ret = btree_root(insert_recurse, c, op, keys, 22151b207d80SKent Overstreet journal_ref, replace_key); 2216cafe5635SKent Overstreet 2217cafe5635SKent Overstreet if (ret == -EAGAIN) { 2218b54d6934SKent Overstreet BUG(); 2219cafe5635SKent Overstreet ret = 0; 2220cafe5635SKent Overstreet } else if (ret) { 2221cafe5635SKent Overstreet struct bkey *k; 2222cafe5635SKent Overstreet 22231b207d80SKent Overstreet pr_err("error %i", ret); 2224cafe5635SKent Overstreet 22254f3d4014SKent Overstreet while ((k = bch_keylist_pop(keys))) 2226cafe5635SKent Overstreet bkey_put(c, k, 0); 2227cafe5635SKent Overstreet } 2228cafe5635SKent Overstreet } 2229cafe5635SKent Overstreet 2230*6054c6d4SKent Overstreet if (op->insert_collision) 2231*6054c6d4SKent Overstreet return -ESRCH; 2232*6054c6d4SKent Overstreet 2233cafe5635SKent Overstreet return ret; 2234cafe5635SKent Overstreet } 2235cafe5635SKent Overstreet 2236cafe5635SKent Overstreet void bch_btree_set_root(struct btree *b) 2237cafe5635SKent Overstreet { 2238cafe5635SKent Overstreet unsigned i; 2239e49c7c37SKent Overstreet struct closure cl; 2240e49c7c37SKent Overstreet 2241e49c7c37SKent Overstreet closure_init_stack(&cl); 2242cafe5635SKent Overstreet 2243c37511b8SKent Overstreet trace_bcache_btree_set_root(b); 2244c37511b8SKent Overstreet 2245cafe5635SKent Overstreet BUG_ON(!b->written); 2246cafe5635SKent Overstreet 2247cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) 2248cafe5635SKent Overstreet BUG_ON(PTR_BUCKET(b->c, &b->key, i)->prio != BTREE_PRIO); 2249cafe5635SKent Overstreet 2250cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 2251cafe5635SKent Overstreet list_del_init(&b->list); 2252cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 2253cafe5635SKent Overstreet 2254cafe5635SKent Overstreet b->c->root = b; 2255cafe5635SKent Overstreet __bkey_put(b->c, &b->key); 2256cafe5635SKent Overstreet 2257e49c7c37SKent Overstreet bch_journal_meta(b->c, &cl); 2258e49c7c37SKent Overstreet closure_sync(&cl); 2259cafe5635SKent Overstreet } 2260cafe5635SKent Overstreet 226148dad8baSKent Overstreet /* Map across nodes or keys */ 226248dad8baSKent Overstreet 226348dad8baSKent Overstreet static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op, 226448dad8baSKent Overstreet struct bkey *from, 226548dad8baSKent Overstreet btree_map_nodes_fn *fn, int flags) 226648dad8baSKent Overstreet { 226748dad8baSKent Overstreet int ret = MAP_CONTINUE; 226848dad8baSKent Overstreet 226948dad8baSKent Overstreet if (b->level) { 227048dad8baSKent Overstreet struct bkey *k; 227148dad8baSKent Overstreet struct btree_iter iter; 227248dad8baSKent Overstreet 227348dad8baSKent Overstreet bch_btree_iter_init(b, &iter, from); 227448dad8baSKent Overstreet 227548dad8baSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, b, 227648dad8baSKent Overstreet bch_ptr_bad))) { 227748dad8baSKent Overstreet ret = btree(map_nodes_recurse, k, b, 227848dad8baSKent Overstreet op, from, fn, flags); 227948dad8baSKent Overstreet from = NULL; 228048dad8baSKent Overstreet 228148dad8baSKent Overstreet if (ret != MAP_CONTINUE) 228248dad8baSKent Overstreet return ret; 228348dad8baSKent Overstreet } 228448dad8baSKent Overstreet } 228548dad8baSKent Overstreet 228648dad8baSKent Overstreet if (!b->level || flags == MAP_ALL_NODES) 228748dad8baSKent Overstreet ret = fn(op, b); 228848dad8baSKent Overstreet 228948dad8baSKent Overstreet return ret; 229048dad8baSKent Overstreet } 229148dad8baSKent Overstreet 229248dad8baSKent Overstreet int __bch_btree_map_nodes(struct btree_op *op, struct cache_set *c, 229348dad8baSKent Overstreet struct bkey *from, btree_map_nodes_fn *fn, int flags) 229448dad8baSKent Overstreet { 2295b54d6934SKent Overstreet return btree_root(map_nodes_recurse, c, op, from, fn, flags); 229648dad8baSKent Overstreet } 229748dad8baSKent Overstreet 229848dad8baSKent Overstreet static int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op, 229948dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, 230048dad8baSKent Overstreet int flags) 230148dad8baSKent Overstreet { 230248dad8baSKent Overstreet int ret = MAP_CONTINUE; 230348dad8baSKent Overstreet struct bkey *k; 230448dad8baSKent Overstreet struct btree_iter iter; 230548dad8baSKent Overstreet 230648dad8baSKent Overstreet bch_btree_iter_init(b, &iter, from); 230748dad8baSKent Overstreet 230848dad8baSKent Overstreet while ((k = bch_btree_iter_next_filter(&iter, b, bch_ptr_bad))) { 230948dad8baSKent Overstreet ret = !b->level 231048dad8baSKent Overstreet ? fn(op, b, k) 231148dad8baSKent Overstreet : btree(map_keys_recurse, k, b, op, from, fn, flags); 231248dad8baSKent Overstreet from = NULL; 231348dad8baSKent Overstreet 231448dad8baSKent Overstreet if (ret != MAP_CONTINUE) 231548dad8baSKent Overstreet return ret; 231648dad8baSKent Overstreet } 231748dad8baSKent Overstreet 231848dad8baSKent Overstreet if (!b->level && (flags & MAP_END_KEY)) 231948dad8baSKent Overstreet ret = fn(op, b, &KEY(KEY_INODE(&b->key), 232048dad8baSKent Overstreet KEY_OFFSET(&b->key), 0)); 232148dad8baSKent Overstreet 232248dad8baSKent Overstreet return ret; 232348dad8baSKent Overstreet } 232448dad8baSKent Overstreet 232548dad8baSKent Overstreet int bch_btree_map_keys(struct btree_op *op, struct cache_set *c, 232648dad8baSKent Overstreet struct bkey *from, btree_map_keys_fn *fn, int flags) 232748dad8baSKent Overstreet { 2328b54d6934SKent Overstreet return btree_root(map_keys_recurse, c, op, from, fn, flags); 232948dad8baSKent Overstreet } 233048dad8baSKent Overstreet 2331cafe5635SKent Overstreet /* Keybuf code */ 2332cafe5635SKent Overstreet 2333cafe5635SKent Overstreet static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r) 2334cafe5635SKent Overstreet { 2335cafe5635SKent Overstreet /* Overlapping keys compare equal */ 2336cafe5635SKent Overstreet if (bkey_cmp(&l->key, &START_KEY(&r->key)) <= 0) 2337cafe5635SKent Overstreet return -1; 2338cafe5635SKent Overstreet if (bkey_cmp(&START_KEY(&l->key), &r->key) >= 0) 2339cafe5635SKent Overstreet return 1; 2340cafe5635SKent Overstreet return 0; 2341cafe5635SKent Overstreet } 2342cafe5635SKent Overstreet 2343cafe5635SKent Overstreet static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l, 2344cafe5635SKent Overstreet struct keybuf_key *r) 2345cafe5635SKent Overstreet { 2346cafe5635SKent Overstreet return clamp_t(int64_t, bkey_cmp(&l->key, &r->key), -1, 1); 2347cafe5635SKent Overstreet } 2348cafe5635SKent Overstreet 234948dad8baSKent Overstreet struct refill { 235048dad8baSKent Overstreet struct btree_op op; 235148dad8baSKent Overstreet struct keybuf *buf; 235248dad8baSKent Overstreet struct bkey *end; 235348dad8baSKent Overstreet keybuf_pred_fn *pred; 235448dad8baSKent Overstreet }; 235548dad8baSKent Overstreet 235648dad8baSKent Overstreet static int refill_keybuf_fn(struct btree_op *op, struct btree *b, 235748dad8baSKent Overstreet struct bkey *k) 2358cafe5635SKent Overstreet { 235948dad8baSKent Overstreet struct refill *refill = container_of(op, struct refill, op); 236048dad8baSKent Overstreet struct keybuf *buf = refill->buf; 236148dad8baSKent Overstreet int ret = MAP_CONTINUE; 2362cafe5635SKent Overstreet 236348dad8baSKent Overstreet if (bkey_cmp(k, refill->end) >= 0) { 236448dad8baSKent Overstreet ret = MAP_DONE; 236548dad8baSKent Overstreet goto out; 2366cafe5635SKent Overstreet } 2367cafe5635SKent Overstreet 236848dad8baSKent Overstreet if (!KEY_SIZE(k)) /* end key */ 236948dad8baSKent Overstreet goto out; 2370cafe5635SKent Overstreet 237148dad8baSKent Overstreet if (refill->pred(buf, k)) { 2372cafe5635SKent Overstreet struct keybuf_key *w; 2373cafe5635SKent Overstreet 2374cafe5635SKent Overstreet spin_lock(&buf->lock); 2375cafe5635SKent Overstreet 2376cafe5635SKent Overstreet w = array_alloc(&buf->freelist); 237748dad8baSKent Overstreet if (!w) { 237848dad8baSKent Overstreet spin_unlock(&buf->lock); 237948dad8baSKent Overstreet return MAP_DONE; 238048dad8baSKent Overstreet } 2381cafe5635SKent Overstreet 2382cafe5635SKent Overstreet w->private = NULL; 2383cafe5635SKent Overstreet bkey_copy(&w->key, k); 2384cafe5635SKent Overstreet 2385cafe5635SKent Overstreet if (RB_INSERT(&buf->keys, w, node, keybuf_cmp)) 2386cafe5635SKent Overstreet array_free(&buf->freelist, w); 2387cafe5635SKent Overstreet 238848dad8baSKent Overstreet if (array_freelist_empty(&buf->freelist)) 238948dad8baSKent Overstreet ret = MAP_DONE; 239048dad8baSKent Overstreet 2391cafe5635SKent Overstreet spin_unlock(&buf->lock); 2392cafe5635SKent Overstreet } 239348dad8baSKent Overstreet out: 239448dad8baSKent Overstreet buf->last_scanned = *k; 239548dad8baSKent Overstreet return ret; 2396cafe5635SKent Overstreet } 2397cafe5635SKent Overstreet 2398cafe5635SKent Overstreet void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf, 239972c27061SKent Overstreet struct bkey *end, keybuf_pred_fn *pred) 2400cafe5635SKent Overstreet { 2401cafe5635SKent Overstreet struct bkey start = buf->last_scanned; 240248dad8baSKent Overstreet struct refill refill; 2403cafe5635SKent Overstreet 2404cafe5635SKent Overstreet cond_resched(); 2405cafe5635SKent Overstreet 2406b54d6934SKent Overstreet bch_btree_op_init(&refill.op, -1); 240748dad8baSKent Overstreet refill.buf = buf; 240848dad8baSKent Overstreet refill.end = end; 240948dad8baSKent Overstreet refill.pred = pred; 241048dad8baSKent Overstreet 241148dad8baSKent Overstreet bch_btree_map_keys(&refill.op, c, &buf->last_scanned, 241248dad8baSKent Overstreet refill_keybuf_fn, MAP_END_KEY); 2413cafe5635SKent Overstreet 2414cafe5635SKent Overstreet pr_debug("found %s keys from %llu:%llu to %llu:%llu", 2415cafe5635SKent Overstreet RB_EMPTY_ROOT(&buf->keys) ? "no" : 2416cafe5635SKent Overstreet array_freelist_empty(&buf->freelist) ? "some" : "a few", 2417cafe5635SKent Overstreet KEY_INODE(&start), KEY_OFFSET(&start), 2418cafe5635SKent Overstreet KEY_INODE(&buf->last_scanned), KEY_OFFSET(&buf->last_scanned)); 2419cafe5635SKent Overstreet 2420cafe5635SKent Overstreet spin_lock(&buf->lock); 2421cafe5635SKent Overstreet 2422cafe5635SKent Overstreet if (!RB_EMPTY_ROOT(&buf->keys)) { 2423cafe5635SKent Overstreet struct keybuf_key *w; 2424cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2425cafe5635SKent Overstreet buf->start = START_KEY(&w->key); 2426cafe5635SKent Overstreet 2427cafe5635SKent Overstreet w = RB_LAST(&buf->keys, struct keybuf_key, node); 2428cafe5635SKent Overstreet buf->end = w->key; 2429cafe5635SKent Overstreet } else { 2430cafe5635SKent Overstreet buf->start = MAX_KEY; 2431cafe5635SKent Overstreet buf->end = MAX_KEY; 2432cafe5635SKent Overstreet } 2433cafe5635SKent Overstreet 2434cafe5635SKent Overstreet spin_unlock(&buf->lock); 2435cafe5635SKent Overstreet } 2436cafe5635SKent Overstreet 2437cafe5635SKent Overstreet static void __bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2438cafe5635SKent Overstreet { 2439cafe5635SKent Overstreet rb_erase(&w->node, &buf->keys); 2440cafe5635SKent Overstreet array_free(&buf->freelist, w); 2441cafe5635SKent Overstreet } 2442cafe5635SKent Overstreet 2443cafe5635SKent Overstreet void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2444cafe5635SKent Overstreet { 2445cafe5635SKent Overstreet spin_lock(&buf->lock); 2446cafe5635SKent Overstreet __bch_keybuf_del(buf, w); 2447cafe5635SKent Overstreet spin_unlock(&buf->lock); 2448cafe5635SKent Overstreet } 2449cafe5635SKent Overstreet 2450cafe5635SKent Overstreet bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start, 2451cafe5635SKent Overstreet struct bkey *end) 2452cafe5635SKent Overstreet { 2453cafe5635SKent Overstreet bool ret = false; 2454cafe5635SKent Overstreet struct keybuf_key *p, *w, s; 2455cafe5635SKent Overstreet s.key = *start; 2456cafe5635SKent Overstreet 2457cafe5635SKent Overstreet if (bkey_cmp(end, &buf->start) <= 0 || 2458cafe5635SKent Overstreet bkey_cmp(start, &buf->end) >= 0) 2459cafe5635SKent Overstreet return false; 2460cafe5635SKent Overstreet 2461cafe5635SKent Overstreet spin_lock(&buf->lock); 2462cafe5635SKent Overstreet w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp); 2463cafe5635SKent Overstreet 2464cafe5635SKent Overstreet while (w && bkey_cmp(&START_KEY(&w->key), end) < 0) { 2465cafe5635SKent Overstreet p = w; 2466cafe5635SKent Overstreet w = RB_NEXT(w, node); 2467cafe5635SKent Overstreet 2468cafe5635SKent Overstreet if (p->private) 2469cafe5635SKent Overstreet ret = true; 2470cafe5635SKent Overstreet else 2471cafe5635SKent Overstreet __bch_keybuf_del(buf, p); 2472cafe5635SKent Overstreet } 2473cafe5635SKent Overstreet 2474cafe5635SKent Overstreet spin_unlock(&buf->lock); 2475cafe5635SKent Overstreet return ret; 2476cafe5635SKent Overstreet } 2477cafe5635SKent Overstreet 2478cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next(struct keybuf *buf) 2479cafe5635SKent Overstreet { 2480cafe5635SKent Overstreet struct keybuf_key *w; 2481cafe5635SKent Overstreet spin_lock(&buf->lock); 2482cafe5635SKent Overstreet 2483cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2484cafe5635SKent Overstreet 2485cafe5635SKent Overstreet while (w && w->private) 2486cafe5635SKent Overstreet w = RB_NEXT(w, node); 2487cafe5635SKent Overstreet 2488cafe5635SKent Overstreet if (w) 2489cafe5635SKent Overstreet w->private = ERR_PTR(-EINTR); 2490cafe5635SKent Overstreet 2491cafe5635SKent Overstreet spin_unlock(&buf->lock); 2492cafe5635SKent Overstreet return w; 2493cafe5635SKent Overstreet } 2494cafe5635SKent Overstreet 2495cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c, 2496cafe5635SKent Overstreet struct keybuf *buf, 249772c27061SKent Overstreet struct bkey *end, 249872c27061SKent Overstreet keybuf_pred_fn *pred) 2499cafe5635SKent Overstreet { 2500cafe5635SKent Overstreet struct keybuf_key *ret; 2501cafe5635SKent Overstreet 2502cafe5635SKent Overstreet while (1) { 2503cafe5635SKent Overstreet ret = bch_keybuf_next(buf); 2504cafe5635SKent Overstreet if (ret) 2505cafe5635SKent Overstreet break; 2506cafe5635SKent Overstreet 2507cafe5635SKent Overstreet if (bkey_cmp(&buf->last_scanned, end) >= 0) { 2508cafe5635SKent Overstreet pr_debug("scan finished"); 2509cafe5635SKent Overstreet break; 2510cafe5635SKent Overstreet } 2511cafe5635SKent Overstreet 251272c27061SKent Overstreet bch_refill_keybuf(c, buf, end, pred); 2513cafe5635SKent Overstreet } 2514cafe5635SKent Overstreet 2515cafe5635SKent Overstreet return ret; 2516cafe5635SKent Overstreet } 2517cafe5635SKent Overstreet 251872c27061SKent Overstreet void bch_keybuf_init(struct keybuf *buf) 2519cafe5635SKent Overstreet { 2520cafe5635SKent Overstreet buf->last_scanned = MAX_KEY; 2521cafe5635SKent Overstreet buf->keys = RB_ROOT; 2522cafe5635SKent Overstreet 2523cafe5635SKent Overstreet spin_lock_init(&buf->lock); 2524cafe5635SKent Overstreet array_allocator_init(&buf->freelist); 2525cafe5635SKent Overstreet } 2526cafe5635SKent Overstreet 2527cafe5635SKent Overstreet void bch_btree_exit(void) 2528cafe5635SKent Overstreet { 2529cafe5635SKent Overstreet if (btree_io_wq) 2530cafe5635SKent Overstreet destroy_workqueue(btree_io_wq); 2531cafe5635SKent Overstreet } 2532cafe5635SKent Overstreet 2533cafe5635SKent Overstreet int __init bch_btree_init(void) 2534cafe5635SKent Overstreet { 253572a44517SKent Overstreet btree_io_wq = create_singlethread_workqueue("bch_btree_io"); 253672a44517SKent Overstreet if (!btree_io_wq) 2537cafe5635SKent Overstreet return -ENOMEM; 2538cafe5635SKent Overstreet 2539cafe5635SKent Overstreet return 0; 2540cafe5635SKent Overstreet } 2541