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" 26cafe5635SKent Overstreet #include "request.h" 27cafe5635SKent Overstreet 28cafe5635SKent Overstreet #include <linux/slab.h> 29cafe5635SKent Overstreet #include <linux/bitops.h> 30cafe5635SKent Overstreet #include <linux/hash.h> 31cd953ed0SGeert Uytterhoeven #include <linux/prefetch.h> 32cafe5635SKent Overstreet #include <linux/random.h> 33cafe5635SKent Overstreet #include <linux/rcupdate.h> 34cafe5635SKent Overstreet #include <trace/events/bcache.h> 35cafe5635SKent Overstreet 36cafe5635SKent Overstreet /* 37cafe5635SKent Overstreet * Todo: 38cafe5635SKent Overstreet * register_bcache: Return errors out to userspace correctly 39cafe5635SKent Overstreet * 40cafe5635SKent Overstreet * Writeback: don't undirty key until after a cache flush 41cafe5635SKent Overstreet * 42cafe5635SKent Overstreet * Create an iterator for key pointers 43cafe5635SKent Overstreet * 44cafe5635SKent Overstreet * On btree write error, mark bucket such that it won't be freed from the cache 45cafe5635SKent Overstreet * 46cafe5635SKent Overstreet * Journalling: 47cafe5635SKent Overstreet * Check for bad keys in replay 48cafe5635SKent Overstreet * Propagate barriers 49cafe5635SKent Overstreet * Refcount journal entries in journal_replay 50cafe5635SKent Overstreet * 51cafe5635SKent Overstreet * Garbage collection: 52cafe5635SKent Overstreet * Finish incremental gc 53cafe5635SKent Overstreet * Gc should free old UUIDs, data for invalid UUIDs 54cafe5635SKent Overstreet * 55cafe5635SKent Overstreet * Provide a way to list backing device UUIDs we have data cached for, and 56cafe5635SKent Overstreet * probably how long it's been since we've seen them, and a way to invalidate 57cafe5635SKent Overstreet * dirty data for devices that will never be attached again 58cafe5635SKent Overstreet * 59cafe5635SKent Overstreet * Keep 1 min/5 min/15 min statistics of how busy a block device has been, so 60cafe5635SKent Overstreet * that based on that and how much dirty data we have we can keep writeback 61cafe5635SKent Overstreet * from being starved 62cafe5635SKent Overstreet * 63cafe5635SKent Overstreet * Add a tracepoint or somesuch to watch for writeback starvation 64cafe5635SKent Overstreet * 65cafe5635SKent Overstreet * When btree depth > 1 and splitting an interior node, we have to make sure 66cafe5635SKent Overstreet * alloc_bucket() cannot fail. This should be true but is not completely 67cafe5635SKent Overstreet * obvious. 68cafe5635SKent Overstreet * 69cafe5635SKent Overstreet * Make sure all allocations get charged to the root cgroup 70cafe5635SKent Overstreet * 71cafe5635SKent Overstreet * Plugging? 72cafe5635SKent Overstreet * 73cafe5635SKent Overstreet * If data write is less than hard sector size of ssd, round up offset in open 74cafe5635SKent Overstreet * bucket to the next whole sector 75cafe5635SKent Overstreet * 76cafe5635SKent Overstreet * Also lookup by cgroup in get_open_bucket() 77cafe5635SKent Overstreet * 78cafe5635SKent Overstreet * Superblock needs to be fleshed out for multiple cache devices 79cafe5635SKent Overstreet * 80cafe5635SKent Overstreet * Add a sysfs tunable for the number of writeback IOs in flight 81cafe5635SKent Overstreet * 82cafe5635SKent Overstreet * Add a sysfs tunable for the number of open data buckets 83cafe5635SKent Overstreet * 84cafe5635SKent Overstreet * IO tracking: Can we track when one process is doing io on behalf of another? 85cafe5635SKent Overstreet * IO tracking: Don't use just an average, weigh more recent stuff higher 86cafe5635SKent Overstreet * 87cafe5635SKent Overstreet * Test module load/unload 88cafe5635SKent Overstreet */ 89cafe5635SKent Overstreet 90cafe5635SKent Overstreet static const char * const op_types[] = { 91cafe5635SKent Overstreet "insert", "replace" 92cafe5635SKent Overstreet }; 93cafe5635SKent Overstreet 94cafe5635SKent Overstreet static const char *op_type(struct btree_op *op) 95cafe5635SKent Overstreet { 96cafe5635SKent Overstreet return op_types[op->type]; 97cafe5635SKent Overstreet } 98cafe5635SKent 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 struct workqueue_struct *bch_gc_wq; 108cafe5635SKent Overstreet static struct workqueue_struct *btree_io_wq; 109cafe5635SKent Overstreet 110cafe5635SKent Overstreet void bch_btree_op_init_stack(struct btree_op *op) 111cafe5635SKent Overstreet { 112cafe5635SKent Overstreet memset(op, 0, sizeof(struct btree_op)); 113cafe5635SKent Overstreet closure_init_stack(&op->cl); 114cafe5635SKent Overstreet op->lock = -1; 115cafe5635SKent Overstreet bch_keylist_init(&op->keys); 116cafe5635SKent Overstreet } 117cafe5635SKent Overstreet 118cafe5635SKent Overstreet /* Btree key manipulation */ 119cafe5635SKent Overstreet 120cafe5635SKent Overstreet static void bkey_put(struct cache_set *c, struct bkey *k, int level) 121cafe5635SKent Overstreet { 122cafe5635SKent Overstreet if ((level && KEY_OFFSET(k)) || !level) 123cafe5635SKent Overstreet __bkey_put(c, k); 124cafe5635SKent Overstreet } 125cafe5635SKent Overstreet 126cafe5635SKent Overstreet /* Btree IO */ 127cafe5635SKent Overstreet 128cafe5635SKent Overstreet static uint64_t btree_csum_set(struct btree *b, struct bset *i) 129cafe5635SKent Overstreet { 130cafe5635SKent Overstreet uint64_t crc = b->key.ptr[0]; 131cafe5635SKent Overstreet void *data = (void *) i + 8, *end = end(i); 132cafe5635SKent Overstreet 133169ef1cfSKent Overstreet crc = bch_crc64_update(crc, data, end - data); 134c19ed23aSKent Overstreet return crc ^ 0xffffffffffffffffULL; 135cafe5635SKent Overstreet } 136cafe5635SKent Overstreet 137cafe5635SKent Overstreet static void btree_bio_endio(struct bio *bio, int error) 138cafe5635SKent Overstreet { 139cafe5635SKent Overstreet struct closure *cl = bio->bi_private; 140cafe5635SKent Overstreet struct btree *b = container_of(cl, struct btree, io.cl); 141cafe5635SKent Overstreet 142cafe5635SKent Overstreet if (error) 143cafe5635SKent Overstreet set_btree_node_io_error(b); 144cafe5635SKent Overstreet 145cafe5635SKent Overstreet bch_bbio_count_io_errors(b->c, bio, error, (bio->bi_rw & WRITE) 146cafe5635SKent Overstreet ? "writing btree" : "reading btree"); 147cafe5635SKent Overstreet closure_put(cl); 148cafe5635SKent Overstreet } 149cafe5635SKent Overstreet 150cafe5635SKent Overstreet static void btree_bio_init(struct btree *b) 151cafe5635SKent Overstreet { 152cafe5635SKent Overstreet BUG_ON(b->bio); 153cafe5635SKent Overstreet b->bio = bch_bbio_alloc(b->c); 154cafe5635SKent Overstreet 155cafe5635SKent Overstreet b->bio->bi_end_io = btree_bio_endio; 156cafe5635SKent Overstreet b->bio->bi_private = &b->io.cl; 157cafe5635SKent Overstreet } 158cafe5635SKent Overstreet 159cafe5635SKent Overstreet void bch_btree_read_done(struct closure *cl) 160cafe5635SKent Overstreet { 161cafe5635SKent Overstreet struct btree *b = container_of(cl, struct btree, io.cl); 162cafe5635SKent Overstreet struct bset *i = b->sets[0].data; 163cafe5635SKent Overstreet struct btree_iter *iter = b->c->fill_iter; 164cafe5635SKent Overstreet const char *err = "bad btree header"; 165cafe5635SKent Overstreet BUG_ON(b->nsets || b->written); 166cafe5635SKent Overstreet 167cafe5635SKent Overstreet bch_bbio_free(b->bio, b->c); 168cafe5635SKent Overstreet b->bio = NULL; 169cafe5635SKent Overstreet 170cafe5635SKent Overstreet mutex_lock(&b->c->fill_lock); 171cafe5635SKent Overstreet iter->used = 0; 172cafe5635SKent Overstreet 173cafe5635SKent Overstreet if (btree_node_io_error(b) || 174cafe5635SKent Overstreet !i->seq) 175cafe5635SKent Overstreet goto err; 176cafe5635SKent Overstreet 177cafe5635SKent Overstreet for (; 178cafe5635SKent Overstreet b->written < btree_blocks(b) && i->seq == b->sets[0].data->seq; 179cafe5635SKent Overstreet i = write_block(b)) { 180cafe5635SKent Overstreet err = "unsupported bset version"; 181cafe5635SKent Overstreet if (i->version > BCACHE_BSET_VERSION) 182cafe5635SKent Overstreet goto err; 183cafe5635SKent Overstreet 184cafe5635SKent Overstreet err = "bad btree header"; 185cafe5635SKent Overstreet if (b->written + set_blocks(i, b->c) > btree_blocks(b)) 186cafe5635SKent Overstreet goto err; 187cafe5635SKent Overstreet 188cafe5635SKent Overstreet err = "bad magic"; 189cafe5635SKent Overstreet if (i->magic != bset_magic(b->c)) 190cafe5635SKent Overstreet goto err; 191cafe5635SKent Overstreet 192cafe5635SKent Overstreet err = "bad checksum"; 193cafe5635SKent Overstreet switch (i->version) { 194cafe5635SKent Overstreet case 0: 195cafe5635SKent Overstreet if (i->csum != csum_set(i)) 196cafe5635SKent Overstreet goto err; 197cafe5635SKent Overstreet break; 198cafe5635SKent Overstreet case BCACHE_BSET_VERSION: 199cafe5635SKent Overstreet if (i->csum != btree_csum_set(b, i)) 200cafe5635SKent Overstreet goto err; 201cafe5635SKent Overstreet break; 202cafe5635SKent Overstreet } 203cafe5635SKent Overstreet 204cafe5635SKent Overstreet err = "empty set"; 205cafe5635SKent Overstreet if (i != b->sets[0].data && !i->keys) 206cafe5635SKent Overstreet goto err; 207cafe5635SKent Overstreet 208cafe5635SKent Overstreet bch_btree_iter_push(iter, i->start, end(i)); 209cafe5635SKent Overstreet 210cafe5635SKent Overstreet b->written += set_blocks(i, b->c); 211cafe5635SKent Overstreet } 212cafe5635SKent Overstreet 213cafe5635SKent Overstreet err = "corrupted btree"; 214cafe5635SKent Overstreet for (i = write_block(b); 215cafe5635SKent Overstreet index(i, b) < btree_blocks(b); 216cafe5635SKent Overstreet i = ((void *) i) + block_bytes(b->c)) 217cafe5635SKent Overstreet if (i->seq == b->sets[0].data->seq) 218cafe5635SKent Overstreet goto err; 219cafe5635SKent Overstreet 220cafe5635SKent Overstreet bch_btree_sort_and_fix_extents(b, iter); 221cafe5635SKent Overstreet 222cafe5635SKent Overstreet i = b->sets[0].data; 223cafe5635SKent Overstreet err = "short btree key"; 224cafe5635SKent Overstreet if (b->sets[0].size && 225cafe5635SKent Overstreet bkey_cmp(&b->key, &b->sets[0].end) < 0) 226cafe5635SKent Overstreet goto err; 227cafe5635SKent Overstreet 228cafe5635SKent Overstreet if (b->written < btree_blocks(b)) 229cafe5635SKent Overstreet bch_bset_init_next(b); 230cafe5635SKent Overstreet out: 231cafe5635SKent Overstreet 232cafe5635SKent Overstreet mutex_unlock(&b->c->fill_lock); 233cafe5635SKent Overstreet 234cafe5635SKent Overstreet spin_lock(&b->c->btree_read_time_lock); 235169ef1cfSKent Overstreet bch_time_stats_update(&b->c->btree_read_time, b->io_start_time); 236cafe5635SKent Overstreet spin_unlock(&b->c->btree_read_time_lock); 237cafe5635SKent Overstreet 238cafe5635SKent Overstreet smp_wmb(); /* read_done is our write lock */ 239cafe5635SKent Overstreet set_btree_node_read_done(b); 240cafe5635SKent Overstreet 241cafe5635SKent Overstreet closure_return(cl); 242cafe5635SKent Overstreet err: 243cafe5635SKent Overstreet set_btree_node_io_error(b); 24407e86ccbSKent Overstreet bch_cache_set_error(b->c, "%s at bucket %zu, block %zu, %u keys", 245cafe5635SKent Overstreet err, PTR_BUCKET_NR(b->c, &b->key, 0), 246cafe5635SKent Overstreet index(i, b), i->keys); 247cafe5635SKent Overstreet goto out; 248cafe5635SKent Overstreet } 249cafe5635SKent Overstreet 250cafe5635SKent Overstreet void bch_btree_read(struct btree *b) 251cafe5635SKent Overstreet { 252cafe5635SKent Overstreet BUG_ON(b->nsets || b->written); 253cafe5635SKent Overstreet 254cafe5635SKent Overstreet if (!closure_trylock(&b->io.cl, &b->c->cl)) 255cafe5635SKent Overstreet BUG(); 256cafe5635SKent Overstreet 257cafe5635SKent Overstreet b->io_start_time = local_clock(); 258cafe5635SKent Overstreet 259cafe5635SKent Overstreet btree_bio_init(b); 260cafe5635SKent Overstreet b->bio->bi_rw = REQ_META|READ_SYNC; 261cafe5635SKent Overstreet b->bio->bi_size = KEY_SIZE(&b->key) << 9; 262cafe5635SKent Overstreet 263169ef1cfSKent Overstreet bch_bio_map(b->bio, b->sets[0].data); 264cafe5635SKent Overstreet 265cafe5635SKent Overstreet pr_debug("%s", pbtree(b)); 266cafe5635SKent Overstreet trace_bcache_btree_read(b->bio); 267cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &b->key, 0); 268cafe5635SKent Overstreet 269cafe5635SKent Overstreet continue_at(&b->io.cl, bch_btree_read_done, system_wq); 270cafe5635SKent Overstreet } 271cafe5635SKent Overstreet 272cafe5635SKent Overstreet static void btree_complete_write(struct btree *b, struct btree_write *w) 273cafe5635SKent Overstreet { 274cafe5635SKent Overstreet if (w->prio_blocked && 275cafe5635SKent Overstreet !atomic_sub_return(w->prio_blocked, &b->c->prio_blocked)) 276*119ba0f8SKent Overstreet wake_up_allocators(b->c); 277cafe5635SKent Overstreet 278cafe5635SKent Overstreet if (w->journal) { 279cafe5635SKent Overstreet atomic_dec_bug(w->journal); 280cafe5635SKent Overstreet __closure_wake_up(&b->c->journal.wait); 281cafe5635SKent Overstreet } 282cafe5635SKent Overstreet 283cafe5635SKent Overstreet if (w->owner) 284cafe5635SKent Overstreet closure_put(w->owner); 285cafe5635SKent Overstreet 286cafe5635SKent Overstreet w->prio_blocked = 0; 287cafe5635SKent Overstreet w->journal = NULL; 288cafe5635SKent Overstreet w->owner = NULL; 289cafe5635SKent Overstreet } 290cafe5635SKent Overstreet 291cafe5635SKent Overstreet static void __btree_write_done(struct closure *cl) 292cafe5635SKent Overstreet { 293cafe5635SKent Overstreet struct btree *b = container_of(cl, struct btree, io.cl); 294cafe5635SKent Overstreet struct btree_write *w = btree_prev_write(b); 295cafe5635SKent Overstreet 296cafe5635SKent Overstreet bch_bbio_free(b->bio, b->c); 297cafe5635SKent Overstreet b->bio = NULL; 298cafe5635SKent Overstreet btree_complete_write(b, w); 299cafe5635SKent Overstreet 300cafe5635SKent Overstreet if (btree_node_dirty(b)) 301cafe5635SKent Overstreet queue_delayed_work(btree_io_wq, &b->work, 302cafe5635SKent Overstreet msecs_to_jiffies(30000)); 303cafe5635SKent Overstreet 304cafe5635SKent Overstreet closure_return(cl); 305cafe5635SKent Overstreet } 306cafe5635SKent Overstreet 307cafe5635SKent Overstreet static void btree_write_done(struct closure *cl) 308cafe5635SKent Overstreet { 309cafe5635SKent Overstreet struct btree *b = container_of(cl, struct btree, io.cl); 310cafe5635SKent Overstreet struct bio_vec *bv; 311cafe5635SKent Overstreet int n; 312cafe5635SKent Overstreet 313cafe5635SKent Overstreet __bio_for_each_segment(bv, b->bio, n, 0) 314cafe5635SKent Overstreet __free_page(bv->bv_page); 315cafe5635SKent Overstreet 316cafe5635SKent Overstreet __btree_write_done(cl); 317cafe5635SKent Overstreet } 318cafe5635SKent Overstreet 319cafe5635SKent Overstreet static void do_btree_write(struct btree *b) 320cafe5635SKent Overstreet { 321cafe5635SKent Overstreet struct closure *cl = &b->io.cl; 322cafe5635SKent Overstreet struct bset *i = b->sets[b->nsets].data; 323cafe5635SKent Overstreet BKEY_PADDED(key) k; 324cafe5635SKent Overstreet 325cafe5635SKent Overstreet i->version = BCACHE_BSET_VERSION; 326cafe5635SKent Overstreet i->csum = btree_csum_set(b, i); 327cafe5635SKent Overstreet 328cafe5635SKent Overstreet btree_bio_init(b); 329cafe5635SKent Overstreet b->bio->bi_rw = REQ_META|WRITE_SYNC; 330cafe5635SKent Overstreet b->bio->bi_size = set_blocks(i, b->c) * block_bytes(b->c); 331169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 332cafe5635SKent Overstreet 333cafe5635SKent Overstreet bkey_copy(&k.key, &b->key); 334cafe5635SKent Overstreet SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) + bset_offset(b, i)); 335cafe5635SKent Overstreet 336169ef1cfSKent Overstreet if (!bch_bio_alloc_pages(b->bio, GFP_NOIO)) { 337cafe5635SKent Overstreet int j; 338cafe5635SKent Overstreet struct bio_vec *bv; 339cafe5635SKent Overstreet void *base = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1)); 340cafe5635SKent Overstreet 341cafe5635SKent Overstreet bio_for_each_segment(bv, b->bio, j) 342cafe5635SKent Overstreet memcpy(page_address(bv->bv_page), 343cafe5635SKent Overstreet base + j * PAGE_SIZE, PAGE_SIZE); 344cafe5635SKent Overstreet 345cafe5635SKent Overstreet trace_bcache_btree_write(b->bio); 346cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 347cafe5635SKent Overstreet 348cafe5635SKent Overstreet continue_at(cl, btree_write_done, NULL); 349cafe5635SKent Overstreet } else { 350cafe5635SKent Overstreet b->bio->bi_vcnt = 0; 351169ef1cfSKent Overstreet bch_bio_map(b->bio, i); 352cafe5635SKent Overstreet 353cafe5635SKent Overstreet trace_bcache_btree_write(b->bio); 354cafe5635SKent Overstreet bch_submit_bbio(b->bio, b->c, &k.key, 0); 355cafe5635SKent Overstreet 356cafe5635SKent Overstreet closure_sync(cl); 357cafe5635SKent Overstreet __btree_write_done(cl); 358cafe5635SKent Overstreet } 359cafe5635SKent Overstreet } 360cafe5635SKent Overstreet 361cafe5635SKent Overstreet static void __btree_write(struct btree *b) 362cafe5635SKent Overstreet { 363cafe5635SKent Overstreet struct bset *i = b->sets[b->nsets].data; 364cafe5635SKent Overstreet 365cafe5635SKent Overstreet BUG_ON(current->bio_list); 366cafe5635SKent Overstreet 367cafe5635SKent Overstreet closure_lock(&b->io, &b->c->cl); 368cafe5635SKent Overstreet cancel_delayed_work(&b->work); 369cafe5635SKent Overstreet 370cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 371cafe5635SKent Overstreet change_bit(BTREE_NODE_write_idx, &b->flags); 372cafe5635SKent Overstreet 373cafe5635SKent Overstreet bch_check_key_order(b, i); 374cafe5635SKent Overstreet BUG_ON(b->written && !i->keys); 375cafe5635SKent Overstreet 376cafe5635SKent Overstreet do_btree_write(b); 377cafe5635SKent Overstreet 378cafe5635SKent Overstreet pr_debug("%s block %i keys %i", pbtree(b), b->written, i->keys); 379cafe5635SKent Overstreet 380cafe5635SKent Overstreet b->written += set_blocks(i, b->c); 381cafe5635SKent Overstreet atomic_long_add(set_blocks(i, b->c) * b->c->sb.block_size, 382cafe5635SKent Overstreet &PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written); 383cafe5635SKent Overstreet 384cafe5635SKent Overstreet bch_btree_sort_lazy(b); 385cafe5635SKent Overstreet 386cafe5635SKent Overstreet if (b->written < btree_blocks(b)) 387cafe5635SKent Overstreet bch_bset_init_next(b); 388cafe5635SKent Overstreet } 389cafe5635SKent Overstreet 390cafe5635SKent Overstreet static void btree_write_work(struct work_struct *w) 391cafe5635SKent Overstreet { 392cafe5635SKent Overstreet struct btree *b = container_of(to_delayed_work(w), struct btree, work); 393cafe5635SKent Overstreet 394cafe5635SKent Overstreet down_write(&b->lock); 395cafe5635SKent Overstreet 396cafe5635SKent Overstreet if (btree_node_dirty(b)) 397cafe5635SKent Overstreet __btree_write(b); 398cafe5635SKent Overstreet up_write(&b->lock); 399cafe5635SKent Overstreet } 400cafe5635SKent Overstreet 401cafe5635SKent Overstreet void bch_btree_write(struct btree *b, bool now, struct btree_op *op) 402cafe5635SKent Overstreet { 403cafe5635SKent Overstreet struct bset *i = b->sets[b->nsets].data; 404cafe5635SKent Overstreet struct btree_write *w = btree_current_write(b); 405cafe5635SKent Overstreet 406cafe5635SKent Overstreet BUG_ON(b->written && 407cafe5635SKent Overstreet (b->written >= btree_blocks(b) || 408cafe5635SKent Overstreet i->seq != b->sets[0].data->seq || 409cafe5635SKent Overstreet !i->keys)); 410cafe5635SKent Overstreet 411cafe5635SKent Overstreet if (!btree_node_dirty(b)) { 412cafe5635SKent Overstreet set_btree_node_dirty(b); 413cafe5635SKent Overstreet queue_delayed_work(btree_io_wq, &b->work, 414cafe5635SKent Overstreet msecs_to_jiffies(30000)); 415cafe5635SKent Overstreet } 416cafe5635SKent Overstreet 417cafe5635SKent Overstreet w->prio_blocked += b->prio_blocked; 418cafe5635SKent Overstreet b->prio_blocked = 0; 419cafe5635SKent Overstreet 420cafe5635SKent Overstreet if (op && op->journal && !b->level) { 421cafe5635SKent Overstreet if (w->journal && 422cafe5635SKent Overstreet journal_pin_cmp(b->c, w, op)) { 423cafe5635SKent Overstreet atomic_dec_bug(w->journal); 424cafe5635SKent Overstreet w->journal = NULL; 425cafe5635SKent Overstreet } 426cafe5635SKent Overstreet 427cafe5635SKent Overstreet if (!w->journal) { 428cafe5635SKent Overstreet w->journal = op->journal; 429cafe5635SKent Overstreet atomic_inc(w->journal); 430cafe5635SKent Overstreet } 431cafe5635SKent Overstreet } 432cafe5635SKent Overstreet 433cafe5635SKent Overstreet if (current->bio_list) 434cafe5635SKent Overstreet return; 435cafe5635SKent Overstreet 436cafe5635SKent Overstreet /* Force write if set is too big */ 437cafe5635SKent Overstreet if (now || 438cafe5635SKent Overstreet b->level || 439cafe5635SKent Overstreet set_bytes(i) > PAGE_SIZE - 48) { 440cafe5635SKent Overstreet if (op && now) { 441cafe5635SKent Overstreet /* Must wait on multiple writes */ 442cafe5635SKent Overstreet BUG_ON(w->owner); 443cafe5635SKent Overstreet w->owner = &op->cl; 444cafe5635SKent Overstreet closure_get(&op->cl); 445cafe5635SKent Overstreet } 446cafe5635SKent Overstreet 447cafe5635SKent Overstreet __btree_write(b); 448cafe5635SKent Overstreet } 449cafe5635SKent Overstreet BUG_ON(!b->written); 450cafe5635SKent Overstreet } 451cafe5635SKent Overstreet 452cafe5635SKent Overstreet /* 453cafe5635SKent Overstreet * Btree in memory cache - allocation/freeing 454cafe5635SKent Overstreet * mca -> memory cache 455cafe5635SKent Overstreet */ 456cafe5635SKent Overstreet 457cafe5635SKent Overstreet static void mca_reinit(struct btree *b) 458cafe5635SKent Overstreet { 459cafe5635SKent Overstreet unsigned i; 460cafe5635SKent Overstreet 461cafe5635SKent Overstreet b->flags = 0; 462cafe5635SKent Overstreet b->written = 0; 463cafe5635SKent Overstreet b->nsets = 0; 464cafe5635SKent Overstreet 465cafe5635SKent Overstreet for (i = 0; i < MAX_BSETS; i++) 466cafe5635SKent Overstreet b->sets[i].size = 0; 467cafe5635SKent Overstreet /* 468cafe5635SKent Overstreet * Second loop starts at 1 because b->sets[0]->data is the memory we 469cafe5635SKent Overstreet * allocated 470cafe5635SKent Overstreet */ 471cafe5635SKent Overstreet for (i = 1; i < MAX_BSETS; i++) 472cafe5635SKent Overstreet b->sets[i].data = NULL; 473cafe5635SKent Overstreet } 474cafe5635SKent Overstreet 475cafe5635SKent Overstreet #define mca_reserve(c) (((c->root && c->root->level) \ 476cafe5635SKent Overstreet ? c->root->level : 1) * 8 + 16) 477cafe5635SKent Overstreet #define mca_can_free(c) \ 478cafe5635SKent Overstreet max_t(int, 0, c->bucket_cache_used - mca_reserve(c)) 479cafe5635SKent Overstreet 480cafe5635SKent Overstreet static void mca_data_free(struct btree *b) 481cafe5635SKent Overstreet { 482cafe5635SKent Overstreet struct bset_tree *t = b->sets; 483cafe5635SKent Overstreet BUG_ON(!closure_is_unlocked(&b->io.cl)); 484cafe5635SKent Overstreet 485cafe5635SKent Overstreet if (bset_prev_bytes(b) < PAGE_SIZE) 486cafe5635SKent Overstreet kfree(t->prev); 487cafe5635SKent Overstreet else 488cafe5635SKent Overstreet free_pages((unsigned long) t->prev, 489cafe5635SKent Overstreet get_order(bset_prev_bytes(b))); 490cafe5635SKent Overstreet 491cafe5635SKent Overstreet if (bset_tree_bytes(b) < PAGE_SIZE) 492cafe5635SKent Overstreet kfree(t->tree); 493cafe5635SKent Overstreet else 494cafe5635SKent Overstreet free_pages((unsigned long) t->tree, 495cafe5635SKent Overstreet get_order(bset_tree_bytes(b))); 496cafe5635SKent Overstreet 497cafe5635SKent Overstreet free_pages((unsigned long) t->data, b->page_order); 498cafe5635SKent Overstreet 499cafe5635SKent Overstreet t->prev = NULL; 500cafe5635SKent Overstreet t->tree = NULL; 501cafe5635SKent Overstreet t->data = NULL; 502cafe5635SKent Overstreet list_move(&b->list, &b->c->btree_cache_freed); 503cafe5635SKent Overstreet b->c->bucket_cache_used--; 504cafe5635SKent Overstreet } 505cafe5635SKent Overstreet 506cafe5635SKent Overstreet static void mca_bucket_free(struct btree *b) 507cafe5635SKent Overstreet { 508cafe5635SKent Overstreet BUG_ON(btree_node_dirty(b)); 509cafe5635SKent Overstreet 510cafe5635SKent Overstreet b->key.ptr[0] = 0; 511cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 512cafe5635SKent Overstreet list_move(&b->list, &b->c->btree_cache_freeable); 513cafe5635SKent Overstreet } 514cafe5635SKent Overstreet 515cafe5635SKent Overstreet static unsigned btree_order(struct bkey *k) 516cafe5635SKent Overstreet { 517cafe5635SKent Overstreet return ilog2(KEY_SIZE(k) / PAGE_SECTORS ?: 1); 518cafe5635SKent Overstreet } 519cafe5635SKent Overstreet 520cafe5635SKent Overstreet static void mca_data_alloc(struct btree *b, struct bkey *k, gfp_t gfp) 521cafe5635SKent Overstreet { 522cafe5635SKent Overstreet struct bset_tree *t = b->sets; 523cafe5635SKent Overstreet BUG_ON(t->data); 524cafe5635SKent Overstreet 525cafe5635SKent Overstreet b->page_order = max_t(unsigned, 526cafe5635SKent Overstreet ilog2(b->c->btree_pages), 527cafe5635SKent Overstreet btree_order(k)); 528cafe5635SKent Overstreet 529cafe5635SKent Overstreet t->data = (void *) __get_free_pages(gfp, b->page_order); 530cafe5635SKent Overstreet if (!t->data) 531cafe5635SKent Overstreet goto err; 532cafe5635SKent Overstreet 533cafe5635SKent Overstreet t->tree = bset_tree_bytes(b) < PAGE_SIZE 534cafe5635SKent Overstreet ? kmalloc(bset_tree_bytes(b), gfp) 535cafe5635SKent Overstreet : (void *) __get_free_pages(gfp, get_order(bset_tree_bytes(b))); 536cafe5635SKent Overstreet if (!t->tree) 537cafe5635SKent Overstreet goto err; 538cafe5635SKent Overstreet 539cafe5635SKent Overstreet t->prev = bset_prev_bytes(b) < PAGE_SIZE 540cafe5635SKent Overstreet ? kmalloc(bset_prev_bytes(b), gfp) 541cafe5635SKent Overstreet : (void *) __get_free_pages(gfp, get_order(bset_prev_bytes(b))); 542cafe5635SKent Overstreet if (!t->prev) 543cafe5635SKent Overstreet goto err; 544cafe5635SKent Overstreet 545cafe5635SKent Overstreet list_move(&b->list, &b->c->btree_cache); 546cafe5635SKent Overstreet b->c->bucket_cache_used++; 547cafe5635SKent Overstreet return; 548cafe5635SKent Overstreet err: 549cafe5635SKent Overstreet mca_data_free(b); 550cafe5635SKent Overstreet } 551cafe5635SKent Overstreet 552cafe5635SKent Overstreet static struct btree *mca_bucket_alloc(struct cache_set *c, 553cafe5635SKent Overstreet struct bkey *k, gfp_t gfp) 554cafe5635SKent Overstreet { 555cafe5635SKent Overstreet struct btree *b = kzalloc(sizeof(struct btree), gfp); 556cafe5635SKent Overstreet if (!b) 557cafe5635SKent Overstreet return NULL; 558cafe5635SKent Overstreet 559cafe5635SKent Overstreet init_rwsem(&b->lock); 560cafe5635SKent Overstreet lockdep_set_novalidate_class(&b->lock); 561cafe5635SKent Overstreet INIT_LIST_HEAD(&b->list); 562cafe5635SKent Overstreet INIT_DELAYED_WORK(&b->work, btree_write_work); 563cafe5635SKent Overstreet b->c = c; 564cafe5635SKent Overstreet closure_init_unlocked(&b->io); 565cafe5635SKent Overstreet 566cafe5635SKent Overstreet mca_data_alloc(b, k, gfp); 567cafe5635SKent Overstreet return b; 568cafe5635SKent Overstreet } 569cafe5635SKent Overstreet 570cafe5635SKent Overstreet static int mca_reap(struct btree *b, struct closure *cl, unsigned min_order) 571cafe5635SKent Overstreet { 572cafe5635SKent Overstreet lockdep_assert_held(&b->c->bucket_lock); 573cafe5635SKent Overstreet 574cafe5635SKent Overstreet if (!down_write_trylock(&b->lock)) 575cafe5635SKent Overstreet return -ENOMEM; 576cafe5635SKent Overstreet 577cafe5635SKent Overstreet if (b->page_order < min_order) { 578cafe5635SKent Overstreet rw_unlock(true, b); 579cafe5635SKent Overstreet return -ENOMEM; 580cafe5635SKent Overstreet } 581cafe5635SKent Overstreet 582cafe5635SKent Overstreet BUG_ON(btree_node_dirty(b) && !b->sets[0].data); 583cafe5635SKent Overstreet 584cafe5635SKent Overstreet if (cl && btree_node_dirty(b)) 585cafe5635SKent Overstreet bch_btree_write(b, true, NULL); 586cafe5635SKent Overstreet 587cafe5635SKent Overstreet if (cl) 588cafe5635SKent Overstreet closure_wait_event_async(&b->io.wait, cl, 589cafe5635SKent Overstreet atomic_read(&b->io.cl.remaining) == -1); 590cafe5635SKent Overstreet 591cafe5635SKent Overstreet if (btree_node_dirty(b) || 592cafe5635SKent Overstreet !closure_is_unlocked(&b->io.cl) || 593cafe5635SKent Overstreet work_pending(&b->work.work)) { 594cafe5635SKent Overstreet rw_unlock(true, b); 595cafe5635SKent Overstreet return -EAGAIN; 596cafe5635SKent Overstreet } 597cafe5635SKent Overstreet 598cafe5635SKent Overstreet return 0; 599cafe5635SKent Overstreet } 600cafe5635SKent Overstreet 601cafe5635SKent Overstreet static int bch_mca_shrink(struct shrinker *shrink, struct shrink_control *sc) 602cafe5635SKent Overstreet { 603cafe5635SKent Overstreet struct cache_set *c = container_of(shrink, struct cache_set, shrink); 604cafe5635SKent Overstreet struct btree *b, *t; 605cafe5635SKent Overstreet unsigned long i, nr = sc->nr_to_scan; 606cafe5635SKent Overstreet 607cafe5635SKent Overstreet if (c->shrinker_disabled) 608cafe5635SKent Overstreet return 0; 609cafe5635SKent Overstreet 610cafe5635SKent Overstreet if (c->try_harder) 611cafe5635SKent Overstreet return 0; 612cafe5635SKent Overstreet 613cafe5635SKent Overstreet /* 614cafe5635SKent Overstreet * If nr == 0, we're supposed to return the number of items we have 615cafe5635SKent Overstreet * cached. Not allowed to return -1. 616cafe5635SKent Overstreet */ 617cafe5635SKent Overstreet if (!nr) 618cafe5635SKent Overstreet return mca_can_free(c) * c->btree_pages; 619cafe5635SKent Overstreet 620cafe5635SKent Overstreet /* Return -1 if we can't do anything right now */ 621cafe5635SKent Overstreet if (sc->gfp_mask & __GFP_WAIT) 622cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 623cafe5635SKent Overstreet else if (!mutex_trylock(&c->bucket_lock)) 624cafe5635SKent Overstreet return -1; 625cafe5635SKent Overstreet 626cafe5635SKent Overstreet nr /= c->btree_pages; 627cafe5635SKent Overstreet nr = min_t(unsigned long, nr, mca_can_free(c)); 628cafe5635SKent Overstreet 629cafe5635SKent Overstreet i = 0; 630cafe5635SKent Overstreet list_for_each_entry_safe(b, t, &c->btree_cache_freeable, list) { 631cafe5635SKent Overstreet if (!nr) 632cafe5635SKent Overstreet break; 633cafe5635SKent Overstreet 634cafe5635SKent Overstreet if (++i > 3 && 635cafe5635SKent Overstreet !mca_reap(b, NULL, 0)) { 636cafe5635SKent Overstreet mca_data_free(b); 637cafe5635SKent Overstreet rw_unlock(true, b); 638cafe5635SKent Overstreet --nr; 639cafe5635SKent Overstreet } 640cafe5635SKent Overstreet } 641cafe5635SKent Overstreet 642cafe5635SKent Overstreet /* 643cafe5635SKent Overstreet * Can happen right when we first start up, before we've read in any 644cafe5635SKent Overstreet * btree nodes 645cafe5635SKent Overstreet */ 646cafe5635SKent Overstreet if (list_empty(&c->btree_cache)) 647cafe5635SKent Overstreet goto out; 648cafe5635SKent Overstreet 649cafe5635SKent Overstreet for (i = 0; nr && i < c->bucket_cache_used; i++) { 650cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 651cafe5635SKent Overstreet list_rotate_left(&c->btree_cache); 652cafe5635SKent Overstreet 653cafe5635SKent Overstreet if (!b->accessed && 654cafe5635SKent Overstreet !mca_reap(b, NULL, 0)) { 655cafe5635SKent Overstreet mca_bucket_free(b); 656cafe5635SKent Overstreet mca_data_free(b); 657cafe5635SKent Overstreet rw_unlock(true, b); 658cafe5635SKent Overstreet --nr; 659cafe5635SKent Overstreet } else 660cafe5635SKent Overstreet b->accessed = 0; 661cafe5635SKent Overstreet } 662cafe5635SKent Overstreet out: 663cafe5635SKent Overstreet nr = mca_can_free(c) * c->btree_pages; 664cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 665cafe5635SKent Overstreet return nr; 666cafe5635SKent Overstreet } 667cafe5635SKent Overstreet 668cafe5635SKent Overstreet void bch_btree_cache_free(struct cache_set *c) 669cafe5635SKent Overstreet { 670cafe5635SKent Overstreet struct btree *b; 671cafe5635SKent Overstreet struct closure cl; 672cafe5635SKent Overstreet closure_init_stack(&cl); 673cafe5635SKent Overstreet 674cafe5635SKent Overstreet if (c->shrink.list.next) 675cafe5635SKent Overstreet unregister_shrinker(&c->shrink); 676cafe5635SKent Overstreet 677cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 678cafe5635SKent Overstreet 679cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 680cafe5635SKent Overstreet if (c->verify_data) 681cafe5635SKent Overstreet list_move(&c->verify_data->list, &c->btree_cache); 682cafe5635SKent Overstreet #endif 683cafe5635SKent Overstreet 684cafe5635SKent Overstreet list_splice(&c->btree_cache_freeable, 685cafe5635SKent Overstreet &c->btree_cache); 686cafe5635SKent Overstreet 687cafe5635SKent Overstreet while (!list_empty(&c->btree_cache)) { 688cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache, struct btree, list); 689cafe5635SKent Overstreet 690cafe5635SKent Overstreet if (btree_node_dirty(b)) 691cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 692cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 693cafe5635SKent Overstreet 694cafe5635SKent Overstreet mca_data_free(b); 695cafe5635SKent Overstreet } 696cafe5635SKent Overstreet 697cafe5635SKent Overstreet while (!list_empty(&c->btree_cache_freed)) { 698cafe5635SKent Overstreet b = list_first_entry(&c->btree_cache_freed, 699cafe5635SKent Overstreet struct btree, list); 700cafe5635SKent Overstreet list_del(&b->list); 701cafe5635SKent Overstreet cancel_delayed_work_sync(&b->work); 702cafe5635SKent Overstreet kfree(b); 703cafe5635SKent Overstreet } 704cafe5635SKent Overstreet 705cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 706cafe5635SKent Overstreet } 707cafe5635SKent Overstreet 708cafe5635SKent Overstreet int bch_btree_cache_alloc(struct cache_set *c) 709cafe5635SKent Overstreet { 710cafe5635SKent Overstreet unsigned i; 711cafe5635SKent Overstreet 712cafe5635SKent Overstreet /* XXX: doesn't check for errors */ 713cafe5635SKent Overstreet 714cafe5635SKent Overstreet closure_init_unlocked(&c->gc); 715cafe5635SKent Overstreet 716cafe5635SKent Overstreet for (i = 0; i < mca_reserve(c); i++) 717cafe5635SKent Overstreet mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL); 718cafe5635SKent Overstreet 719cafe5635SKent Overstreet list_splice_init(&c->btree_cache, 720cafe5635SKent Overstreet &c->btree_cache_freeable); 721cafe5635SKent Overstreet 722cafe5635SKent Overstreet #ifdef CONFIG_BCACHE_DEBUG 723cafe5635SKent Overstreet mutex_init(&c->verify_lock); 724cafe5635SKent Overstreet 725cafe5635SKent Overstreet c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL); 726cafe5635SKent Overstreet 727cafe5635SKent Overstreet if (c->verify_data && 728cafe5635SKent Overstreet c->verify_data->sets[0].data) 729cafe5635SKent Overstreet list_del_init(&c->verify_data->list); 730cafe5635SKent Overstreet else 731cafe5635SKent Overstreet c->verify_data = NULL; 732cafe5635SKent Overstreet #endif 733cafe5635SKent Overstreet 734cafe5635SKent Overstreet c->shrink.shrink = bch_mca_shrink; 735cafe5635SKent Overstreet c->shrink.seeks = 4; 736cafe5635SKent Overstreet c->shrink.batch = c->btree_pages * 2; 737cafe5635SKent Overstreet register_shrinker(&c->shrink); 738cafe5635SKent Overstreet 739cafe5635SKent Overstreet return 0; 740cafe5635SKent Overstreet } 741cafe5635SKent Overstreet 742cafe5635SKent Overstreet /* Btree in memory cache - hash table */ 743cafe5635SKent Overstreet 744cafe5635SKent Overstreet static struct hlist_head *mca_hash(struct cache_set *c, struct bkey *k) 745cafe5635SKent Overstreet { 746cafe5635SKent Overstreet return &c->bucket_hash[hash_32(PTR_HASH(c, k), BUCKET_HASH_BITS)]; 747cafe5635SKent Overstreet } 748cafe5635SKent Overstreet 749cafe5635SKent Overstreet static struct btree *mca_find(struct cache_set *c, struct bkey *k) 750cafe5635SKent Overstreet { 751cafe5635SKent Overstreet struct btree *b; 752cafe5635SKent Overstreet 753cafe5635SKent Overstreet rcu_read_lock(); 754cafe5635SKent Overstreet hlist_for_each_entry_rcu(b, mca_hash(c, k), hash) 755cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) == PTR_HASH(c, k)) 756cafe5635SKent Overstreet goto out; 757cafe5635SKent Overstreet b = NULL; 758cafe5635SKent Overstreet out: 759cafe5635SKent Overstreet rcu_read_unlock(); 760cafe5635SKent Overstreet return b; 761cafe5635SKent Overstreet } 762cafe5635SKent Overstreet 763cafe5635SKent Overstreet static struct btree *mca_cannibalize(struct cache_set *c, struct bkey *k, 764cafe5635SKent Overstreet int level, struct closure *cl) 765cafe5635SKent Overstreet { 766cafe5635SKent Overstreet int ret = -ENOMEM; 767cafe5635SKent Overstreet struct btree *i; 768cafe5635SKent Overstreet 769cafe5635SKent Overstreet if (!cl) 770cafe5635SKent Overstreet return ERR_PTR(-ENOMEM); 771cafe5635SKent Overstreet 772cafe5635SKent Overstreet /* 773cafe5635SKent Overstreet * Trying to free up some memory - i.e. reuse some btree nodes - may 774cafe5635SKent Overstreet * require initiating IO to flush the dirty part of the node. If we're 775cafe5635SKent Overstreet * running under generic_make_request(), that IO will never finish and 776cafe5635SKent Overstreet * we would deadlock. Returning -EAGAIN causes the cache lookup code to 777cafe5635SKent Overstreet * punt to workqueue and retry. 778cafe5635SKent Overstreet */ 779cafe5635SKent Overstreet if (current->bio_list) 780cafe5635SKent Overstreet return ERR_PTR(-EAGAIN); 781cafe5635SKent Overstreet 782cafe5635SKent Overstreet if (c->try_harder && c->try_harder != cl) { 783cafe5635SKent Overstreet closure_wait_event_async(&c->try_wait, cl, !c->try_harder); 784cafe5635SKent Overstreet return ERR_PTR(-EAGAIN); 785cafe5635SKent Overstreet } 786cafe5635SKent Overstreet 787cafe5635SKent Overstreet /* XXX: tracepoint */ 788cafe5635SKent Overstreet c->try_harder = cl; 789cafe5635SKent Overstreet c->try_harder_start = local_clock(); 790cafe5635SKent Overstreet retry: 791cafe5635SKent Overstreet list_for_each_entry_reverse(i, &c->btree_cache, list) { 792cafe5635SKent Overstreet int r = mca_reap(i, cl, btree_order(k)); 793cafe5635SKent Overstreet if (!r) 794cafe5635SKent Overstreet return i; 795cafe5635SKent Overstreet if (r != -ENOMEM) 796cafe5635SKent Overstreet ret = r; 797cafe5635SKent Overstreet } 798cafe5635SKent Overstreet 799cafe5635SKent Overstreet if (ret == -EAGAIN && 800cafe5635SKent Overstreet closure_blocking(cl)) { 801cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 802cafe5635SKent Overstreet closure_sync(cl); 803cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 804cafe5635SKent Overstreet goto retry; 805cafe5635SKent Overstreet } 806cafe5635SKent Overstreet 807cafe5635SKent Overstreet return ERR_PTR(ret); 808cafe5635SKent Overstreet } 809cafe5635SKent Overstreet 810cafe5635SKent Overstreet /* 811cafe5635SKent Overstreet * We can only have one thread cannibalizing other cached btree nodes at a time, 812cafe5635SKent Overstreet * or we'll deadlock. We use an open coded mutex to ensure that, which a 813cafe5635SKent Overstreet * cannibalize_bucket() will take. This means every time we unlock the root of 814cafe5635SKent Overstreet * the btree, we need to release this lock if we have it held. 815cafe5635SKent Overstreet */ 816cafe5635SKent Overstreet void bch_cannibalize_unlock(struct cache_set *c, struct closure *cl) 817cafe5635SKent Overstreet { 818cafe5635SKent Overstreet if (c->try_harder == cl) { 819169ef1cfSKent Overstreet bch_time_stats_update(&c->try_harder_time, c->try_harder_start); 820cafe5635SKent Overstreet c->try_harder = NULL; 821cafe5635SKent Overstreet __closure_wake_up(&c->try_wait); 822cafe5635SKent Overstreet } 823cafe5635SKent Overstreet } 824cafe5635SKent Overstreet 825cafe5635SKent Overstreet static struct btree *mca_alloc(struct cache_set *c, struct bkey *k, 826cafe5635SKent Overstreet int level, struct closure *cl) 827cafe5635SKent Overstreet { 828cafe5635SKent Overstreet struct btree *b; 829cafe5635SKent Overstreet 830cafe5635SKent Overstreet lockdep_assert_held(&c->bucket_lock); 831cafe5635SKent Overstreet 832cafe5635SKent Overstreet if (mca_find(c, k)) 833cafe5635SKent Overstreet return NULL; 834cafe5635SKent Overstreet 835cafe5635SKent Overstreet /* btree_free() doesn't free memory; it sticks the node on the end of 836cafe5635SKent Overstreet * the list. Check if there's any freed nodes there: 837cafe5635SKent Overstreet */ 838cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freeable, list) 839cafe5635SKent Overstreet if (!mca_reap(b, NULL, btree_order(k))) 840cafe5635SKent Overstreet goto out; 841cafe5635SKent Overstreet 842cafe5635SKent Overstreet /* We never free struct btree itself, just the memory that holds the on 843cafe5635SKent Overstreet * disk node. Check the freed list before allocating a new one: 844cafe5635SKent Overstreet */ 845cafe5635SKent Overstreet list_for_each_entry(b, &c->btree_cache_freed, list) 846cafe5635SKent Overstreet if (!mca_reap(b, NULL, 0)) { 847cafe5635SKent Overstreet mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO); 848cafe5635SKent Overstreet if (!b->sets[0].data) 849cafe5635SKent Overstreet goto err; 850cafe5635SKent Overstreet else 851cafe5635SKent Overstreet goto out; 852cafe5635SKent Overstreet } 853cafe5635SKent Overstreet 854cafe5635SKent Overstreet b = mca_bucket_alloc(c, k, __GFP_NOWARN|GFP_NOIO); 855cafe5635SKent Overstreet if (!b) 856cafe5635SKent Overstreet goto err; 857cafe5635SKent Overstreet 858cafe5635SKent Overstreet BUG_ON(!down_write_trylock(&b->lock)); 859cafe5635SKent Overstreet if (!b->sets->data) 860cafe5635SKent Overstreet goto err; 861cafe5635SKent Overstreet out: 862cafe5635SKent Overstreet BUG_ON(!closure_is_unlocked(&b->io.cl)); 863cafe5635SKent Overstreet 864cafe5635SKent Overstreet bkey_copy(&b->key, k); 865cafe5635SKent Overstreet list_move(&b->list, &c->btree_cache); 866cafe5635SKent Overstreet hlist_del_init_rcu(&b->hash); 867cafe5635SKent Overstreet hlist_add_head_rcu(&b->hash, mca_hash(c, k)); 868cafe5635SKent Overstreet 869cafe5635SKent Overstreet lock_set_subclass(&b->lock.dep_map, level + 1, _THIS_IP_); 870cafe5635SKent Overstreet b->level = level; 871cafe5635SKent Overstreet 872cafe5635SKent Overstreet mca_reinit(b); 873cafe5635SKent Overstreet 874cafe5635SKent Overstreet return b; 875cafe5635SKent Overstreet err: 876cafe5635SKent Overstreet if (b) 877cafe5635SKent Overstreet rw_unlock(true, b); 878cafe5635SKent Overstreet 879cafe5635SKent Overstreet b = mca_cannibalize(c, k, level, cl); 880cafe5635SKent Overstreet if (!IS_ERR(b)) 881cafe5635SKent Overstreet goto out; 882cafe5635SKent Overstreet 883cafe5635SKent Overstreet return b; 884cafe5635SKent Overstreet } 885cafe5635SKent Overstreet 886cafe5635SKent Overstreet /** 887cafe5635SKent Overstreet * bch_btree_node_get - find a btree node in the cache and lock it, reading it 888cafe5635SKent Overstreet * in from disk if necessary. 889cafe5635SKent Overstreet * 890cafe5635SKent Overstreet * If IO is necessary, it uses the closure embedded in struct btree_op to wait; 891cafe5635SKent Overstreet * if that closure is in non blocking mode, will return -EAGAIN. 892cafe5635SKent Overstreet * 893cafe5635SKent Overstreet * The btree node will have either a read or a write lock held, depending on 894cafe5635SKent Overstreet * level and op->lock. 895cafe5635SKent Overstreet */ 896cafe5635SKent Overstreet struct btree *bch_btree_node_get(struct cache_set *c, struct bkey *k, 897cafe5635SKent Overstreet int level, struct btree_op *op) 898cafe5635SKent Overstreet { 899cafe5635SKent Overstreet int i = 0; 900cafe5635SKent Overstreet bool write = level <= op->lock; 901cafe5635SKent Overstreet struct btree *b; 902cafe5635SKent Overstreet 903cafe5635SKent Overstreet BUG_ON(level < 0); 904cafe5635SKent Overstreet retry: 905cafe5635SKent Overstreet b = mca_find(c, k); 906cafe5635SKent Overstreet 907cafe5635SKent Overstreet if (!b) { 908cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 909cafe5635SKent Overstreet b = mca_alloc(c, k, level, &op->cl); 910cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 911cafe5635SKent Overstreet 912cafe5635SKent Overstreet if (!b) 913cafe5635SKent Overstreet goto retry; 914cafe5635SKent Overstreet if (IS_ERR(b)) 915cafe5635SKent Overstreet return b; 916cafe5635SKent Overstreet 917cafe5635SKent Overstreet bch_btree_read(b); 918cafe5635SKent Overstreet 919cafe5635SKent Overstreet if (!write) 920cafe5635SKent Overstreet downgrade_write(&b->lock); 921cafe5635SKent Overstreet } else { 922cafe5635SKent Overstreet rw_lock(write, b, level); 923cafe5635SKent Overstreet if (PTR_HASH(c, &b->key) != PTR_HASH(c, k)) { 924cafe5635SKent Overstreet rw_unlock(write, b); 925cafe5635SKent Overstreet goto retry; 926cafe5635SKent Overstreet } 927cafe5635SKent Overstreet BUG_ON(b->level != level); 928cafe5635SKent Overstreet } 929cafe5635SKent Overstreet 930cafe5635SKent Overstreet b->accessed = 1; 931cafe5635SKent Overstreet 932cafe5635SKent Overstreet for (; i <= b->nsets && b->sets[i].size; i++) { 933cafe5635SKent Overstreet prefetch(b->sets[i].tree); 934cafe5635SKent Overstreet prefetch(b->sets[i].data); 935cafe5635SKent Overstreet } 936cafe5635SKent Overstreet 937cafe5635SKent Overstreet for (; i <= b->nsets; i++) 938cafe5635SKent Overstreet prefetch(b->sets[i].data); 939cafe5635SKent Overstreet 940cafe5635SKent Overstreet if (!closure_wait_event(&b->io.wait, &op->cl, 941cafe5635SKent Overstreet btree_node_read_done(b))) { 942cafe5635SKent Overstreet rw_unlock(write, b); 943cafe5635SKent Overstreet b = ERR_PTR(-EAGAIN); 944cafe5635SKent Overstreet } else if (btree_node_io_error(b)) { 945cafe5635SKent Overstreet rw_unlock(write, b); 946cafe5635SKent Overstreet b = ERR_PTR(-EIO); 947cafe5635SKent Overstreet } else 948cafe5635SKent Overstreet BUG_ON(!b->written); 949cafe5635SKent Overstreet 950cafe5635SKent Overstreet return b; 951cafe5635SKent Overstreet } 952cafe5635SKent Overstreet 953cafe5635SKent Overstreet static void btree_node_prefetch(struct cache_set *c, struct bkey *k, int level) 954cafe5635SKent Overstreet { 955cafe5635SKent Overstreet struct btree *b; 956cafe5635SKent Overstreet 957cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 958cafe5635SKent Overstreet b = mca_alloc(c, k, level, NULL); 959cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 960cafe5635SKent Overstreet 961cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(b)) { 962cafe5635SKent Overstreet bch_btree_read(b); 963cafe5635SKent Overstreet rw_unlock(true, b); 964cafe5635SKent Overstreet } 965cafe5635SKent Overstreet } 966cafe5635SKent Overstreet 967cafe5635SKent Overstreet /* Btree alloc */ 968cafe5635SKent Overstreet 969cafe5635SKent Overstreet static void btree_node_free(struct btree *b, struct btree_op *op) 970cafe5635SKent Overstreet { 971cafe5635SKent Overstreet unsigned i; 972cafe5635SKent Overstreet 973cafe5635SKent Overstreet /* 974cafe5635SKent Overstreet * The BUG_ON() in btree_node_get() implies that we must have a write 975cafe5635SKent Overstreet * lock on parent to free or even invalidate a node 976cafe5635SKent Overstreet */ 977cafe5635SKent Overstreet BUG_ON(op->lock <= b->level); 978cafe5635SKent Overstreet BUG_ON(b == b->c->root); 979cafe5635SKent Overstreet pr_debug("bucket %s", pbtree(b)); 980cafe5635SKent Overstreet 981cafe5635SKent Overstreet if (btree_node_dirty(b)) 982cafe5635SKent Overstreet btree_complete_write(b, btree_current_write(b)); 983cafe5635SKent Overstreet clear_bit(BTREE_NODE_dirty, &b->flags); 984cafe5635SKent Overstreet 985cafe5635SKent Overstreet if (b->prio_blocked && 986cafe5635SKent Overstreet !atomic_sub_return(b->prio_blocked, &b->c->prio_blocked)) 987*119ba0f8SKent Overstreet wake_up_allocators(b->c); 988cafe5635SKent Overstreet 989cafe5635SKent Overstreet b->prio_blocked = 0; 990cafe5635SKent Overstreet 991cafe5635SKent Overstreet cancel_delayed_work(&b->work); 992cafe5635SKent Overstreet 993cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 994cafe5635SKent Overstreet 995cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) { 996cafe5635SKent Overstreet BUG_ON(atomic_read(&PTR_BUCKET(b->c, &b->key, i)->pin)); 997cafe5635SKent Overstreet 998cafe5635SKent Overstreet bch_inc_gen(PTR_CACHE(b->c, &b->key, i), 999cafe5635SKent Overstreet PTR_BUCKET(b->c, &b->key, i)); 1000cafe5635SKent Overstreet } 1001cafe5635SKent Overstreet 1002cafe5635SKent Overstreet bch_bucket_free(b->c, &b->key); 1003cafe5635SKent Overstreet mca_bucket_free(b); 1004cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 1005cafe5635SKent Overstreet } 1006cafe5635SKent Overstreet 1007cafe5635SKent Overstreet struct btree *bch_btree_node_alloc(struct cache_set *c, int level, 1008cafe5635SKent Overstreet struct closure *cl) 1009cafe5635SKent Overstreet { 1010cafe5635SKent Overstreet BKEY_PADDED(key) k; 1011cafe5635SKent Overstreet struct btree *b = ERR_PTR(-EAGAIN); 1012cafe5635SKent Overstreet 1013cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1014cafe5635SKent Overstreet retry: 1015cafe5635SKent Overstreet if (__bch_bucket_alloc_set(c, WATERMARK_METADATA, &k.key, 1, cl)) 1016cafe5635SKent Overstreet goto err; 1017cafe5635SKent Overstreet 1018cafe5635SKent Overstreet SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS); 1019cafe5635SKent Overstreet 1020cafe5635SKent Overstreet b = mca_alloc(c, &k.key, level, cl); 1021cafe5635SKent Overstreet if (IS_ERR(b)) 1022cafe5635SKent Overstreet goto err_free; 1023cafe5635SKent Overstreet 1024cafe5635SKent Overstreet if (!b) { 1025b1a67b0fSKent Overstreet cache_bug(c, 1026b1a67b0fSKent Overstreet "Tried to allocate bucket that was in btree cache"); 1027cafe5635SKent Overstreet __bkey_put(c, &k.key); 1028cafe5635SKent Overstreet goto retry; 1029cafe5635SKent Overstreet } 1030cafe5635SKent Overstreet 1031cafe5635SKent Overstreet set_btree_node_read_done(b); 1032cafe5635SKent Overstreet b->accessed = 1; 1033cafe5635SKent Overstreet bch_bset_init_next(b); 1034cafe5635SKent Overstreet 1035cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1036cafe5635SKent Overstreet return b; 1037cafe5635SKent Overstreet err_free: 1038cafe5635SKent Overstreet bch_bucket_free(c, &k.key); 1039cafe5635SKent Overstreet __bkey_put(c, &k.key); 1040cafe5635SKent Overstreet err: 1041cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1042cafe5635SKent Overstreet return b; 1043cafe5635SKent Overstreet } 1044cafe5635SKent Overstreet 1045cafe5635SKent Overstreet static struct btree *btree_node_alloc_replacement(struct btree *b, 1046cafe5635SKent Overstreet struct closure *cl) 1047cafe5635SKent Overstreet { 1048cafe5635SKent Overstreet struct btree *n = bch_btree_node_alloc(b->c, b->level, cl); 1049cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) 1050cafe5635SKent Overstreet bch_btree_sort_into(b, n); 1051cafe5635SKent Overstreet 1052cafe5635SKent Overstreet return n; 1053cafe5635SKent Overstreet } 1054cafe5635SKent Overstreet 1055cafe5635SKent Overstreet /* Garbage collection */ 1056cafe5635SKent Overstreet 1057cafe5635SKent Overstreet uint8_t __bch_btree_mark_key(struct cache_set *c, int level, struct bkey *k) 1058cafe5635SKent Overstreet { 1059cafe5635SKent Overstreet uint8_t stale = 0; 1060cafe5635SKent Overstreet unsigned i; 1061cafe5635SKent Overstreet struct bucket *g; 1062cafe5635SKent Overstreet 1063cafe5635SKent Overstreet /* 1064cafe5635SKent Overstreet * ptr_invalid() can't return true for the keys that mark btree nodes as 1065cafe5635SKent Overstreet * freed, but since ptr_bad() returns true we'll never actually use them 1066cafe5635SKent Overstreet * for anything and thus we don't want mark their pointers here 1067cafe5635SKent Overstreet */ 1068cafe5635SKent Overstreet if (!bkey_cmp(k, &ZERO_KEY)) 1069cafe5635SKent Overstreet return stale; 1070cafe5635SKent Overstreet 1071cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) { 1072cafe5635SKent Overstreet if (!ptr_available(c, k, i)) 1073cafe5635SKent Overstreet continue; 1074cafe5635SKent Overstreet 1075cafe5635SKent Overstreet g = PTR_BUCKET(c, k, i); 1076cafe5635SKent Overstreet 1077cafe5635SKent Overstreet if (gen_after(g->gc_gen, PTR_GEN(k, i))) 1078cafe5635SKent Overstreet g->gc_gen = PTR_GEN(k, i); 1079cafe5635SKent Overstreet 1080cafe5635SKent Overstreet if (ptr_stale(c, k, i)) { 1081cafe5635SKent Overstreet stale = max(stale, ptr_stale(c, k, i)); 1082cafe5635SKent Overstreet continue; 1083cafe5635SKent Overstreet } 1084cafe5635SKent Overstreet 1085cafe5635SKent Overstreet cache_bug_on(GC_MARK(g) && 1086cafe5635SKent Overstreet (GC_MARK(g) == GC_MARK_METADATA) != (level != 0), 1087cafe5635SKent Overstreet c, "inconsistent ptrs: mark = %llu, level = %i", 1088cafe5635SKent Overstreet GC_MARK(g), level); 1089cafe5635SKent Overstreet 1090cafe5635SKent Overstreet if (level) 1091cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_METADATA); 1092cafe5635SKent Overstreet else if (KEY_DIRTY(k)) 1093cafe5635SKent Overstreet SET_GC_MARK(g, GC_MARK_DIRTY); 1094cafe5635SKent Overstreet 1095cafe5635SKent Overstreet /* guard against overflow */ 1096cafe5635SKent Overstreet SET_GC_SECTORS_USED(g, min_t(unsigned, 1097cafe5635SKent Overstreet GC_SECTORS_USED(g) + KEY_SIZE(k), 1098cafe5635SKent Overstreet (1 << 14) - 1)); 1099cafe5635SKent Overstreet 1100cafe5635SKent Overstreet BUG_ON(!GC_SECTORS_USED(g)); 1101cafe5635SKent Overstreet } 1102cafe5635SKent Overstreet 1103cafe5635SKent Overstreet return stale; 1104cafe5635SKent Overstreet } 1105cafe5635SKent Overstreet 1106cafe5635SKent Overstreet #define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k) 1107cafe5635SKent Overstreet 1108cafe5635SKent Overstreet static int btree_gc_mark_node(struct btree *b, unsigned *keys, 1109cafe5635SKent Overstreet struct gc_stat *gc) 1110cafe5635SKent Overstreet { 1111cafe5635SKent Overstreet uint8_t stale = 0; 1112cafe5635SKent Overstreet unsigned last_dev = -1; 1113cafe5635SKent Overstreet struct bcache_device *d = NULL; 1114cafe5635SKent Overstreet struct bkey *k; 1115cafe5635SKent Overstreet struct btree_iter iter; 1116cafe5635SKent Overstreet struct bset_tree *t; 1117cafe5635SKent Overstreet 1118cafe5635SKent Overstreet gc->nodes++; 1119cafe5635SKent Overstreet 1120cafe5635SKent Overstreet for_each_key_filter(b, k, &iter, bch_ptr_invalid) { 1121cafe5635SKent Overstreet if (last_dev != KEY_INODE(k)) { 1122cafe5635SKent Overstreet last_dev = KEY_INODE(k); 1123cafe5635SKent Overstreet 1124cafe5635SKent Overstreet d = KEY_INODE(k) < b->c->nr_uuids 1125cafe5635SKent Overstreet ? b->c->devices[last_dev] 1126cafe5635SKent Overstreet : NULL; 1127cafe5635SKent Overstreet } 1128cafe5635SKent Overstreet 1129cafe5635SKent Overstreet stale = max(stale, btree_mark_key(b, k)); 1130cafe5635SKent Overstreet 1131cafe5635SKent Overstreet if (bch_ptr_bad(b, k)) 1132cafe5635SKent Overstreet continue; 1133cafe5635SKent Overstreet 1134cafe5635SKent Overstreet *keys += bkey_u64s(k); 1135cafe5635SKent Overstreet 1136cafe5635SKent Overstreet gc->key_bytes += bkey_u64s(k); 1137cafe5635SKent Overstreet gc->nkeys++; 1138cafe5635SKent Overstreet 1139cafe5635SKent Overstreet gc->data += KEY_SIZE(k); 1140cafe5635SKent Overstreet if (KEY_DIRTY(k)) { 1141cafe5635SKent Overstreet gc->dirty += KEY_SIZE(k); 1142cafe5635SKent Overstreet if (d) 1143cafe5635SKent Overstreet d->sectors_dirty_gc += KEY_SIZE(k); 1144cafe5635SKent Overstreet } 1145cafe5635SKent Overstreet } 1146cafe5635SKent Overstreet 1147cafe5635SKent Overstreet for (t = b->sets; t <= &b->sets[b->nsets]; t++) 1148cafe5635SKent Overstreet btree_bug_on(t->size && 1149cafe5635SKent Overstreet bset_written(b, t) && 1150cafe5635SKent Overstreet bkey_cmp(&b->key, &t->end) < 0, 1151cafe5635SKent Overstreet b, "found short btree key in gc"); 1152cafe5635SKent Overstreet 1153cafe5635SKent Overstreet return stale; 1154cafe5635SKent Overstreet } 1155cafe5635SKent Overstreet 1156cafe5635SKent Overstreet static struct btree *btree_gc_alloc(struct btree *b, struct bkey *k, 1157cafe5635SKent Overstreet struct btree_op *op) 1158cafe5635SKent Overstreet { 1159cafe5635SKent Overstreet /* 1160cafe5635SKent Overstreet * We block priorities from being written for the duration of garbage 1161cafe5635SKent Overstreet * collection, so we can't sleep in btree_alloc() -> 1162cafe5635SKent Overstreet * bch_bucket_alloc_set(), or we'd risk deadlock - so we don't pass it 1163cafe5635SKent Overstreet * our closure. 1164cafe5635SKent Overstreet */ 1165cafe5635SKent Overstreet struct btree *n = btree_node_alloc_replacement(b, NULL); 1166cafe5635SKent Overstreet 1167cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 1168cafe5635SKent Overstreet swap(b, n); 1169cafe5635SKent Overstreet 1170cafe5635SKent Overstreet memcpy(k->ptr, b->key.ptr, 1171cafe5635SKent Overstreet sizeof(uint64_t) * KEY_PTRS(&b->key)); 1172cafe5635SKent Overstreet 1173cafe5635SKent Overstreet __bkey_put(b->c, &b->key); 1174cafe5635SKent Overstreet atomic_inc(&b->c->prio_blocked); 1175cafe5635SKent Overstreet b->prio_blocked++; 1176cafe5635SKent Overstreet 1177cafe5635SKent Overstreet btree_node_free(n, op); 1178cafe5635SKent Overstreet up_write(&n->lock); 1179cafe5635SKent Overstreet } 1180cafe5635SKent Overstreet 1181cafe5635SKent Overstreet return b; 1182cafe5635SKent Overstreet } 1183cafe5635SKent Overstreet 1184cafe5635SKent Overstreet /* 1185cafe5635SKent Overstreet * Leaving this at 2 until we've got incremental garbage collection done; it 1186cafe5635SKent Overstreet * could be higher (and has been tested with 4) except that garbage collection 1187cafe5635SKent Overstreet * could take much longer, adversely affecting latency. 1188cafe5635SKent Overstreet */ 1189cafe5635SKent Overstreet #define GC_MERGE_NODES 2U 1190cafe5635SKent Overstreet 1191cafe5635SKent Overstreet struct gc_merge_info { 1192cafe5635SKent Overstreet struct btree *b; 1193cafe5635SKent Overstreet struct bkey *k; 1194cafe5635SKent Overstreet unsigned keys; 1195cafe5635SKent Overstreet }; 1196cafe5635SKent Overstreet 1197cafe5635SKent Overstreet static void btree_gc_coalesce(struct btree *b, struct btree_op *op, 1198cafe5635SKent Overstreet struct gc_stat *gc, struct gc_merge_info *r) 1199cafe5635SKent Overstreet { 1200cafe5635SKent Overstreet unsigned nodes = 0, keys = 0, blocks; 1201cafe5635SKent Overstreet int i; 1202cafe5635SKent Overstreet 1203cafe5635SKent Overstreet while (nodes < GC_MERGE_NODES && r[nodes].b) 1204cafe5635SKent Overstreet keys += r[nodes++].keys; 1205cafe5635SKent Overstreet 1206cafe5635SKent Overstreet blocks = btree_default_blocks(b->c) * 2 / 3; 1207cafe5635SKent Overstreet 1208cafe5635SKent Overstreet if (nodes < 2 || 1209cafe5635SKent Overstreet __set_blocks(b->sets[0].data, keys, b->c) > blocks * (nodes - 1)) 1210cafe5635SKent Overstreet return; 1211cafe5635SKent Overstreet 1212cafe5635SKent Overstreet for (i = nodes - 1; i >= 0; --i) { 1213cafe5635SKent Overstreet if (r[i].b->written) 1214cafe5635SKent Overstreet r[i].b = btree_gc_alloc(r[i].b, r[i].k, op); 1215cafe5635SKent Overstreet 1216cafe5635SKent Overstreet if (r[i].b->written) 1217cafe5635SKent Overstreet return; 1218cafe5635SKent Overstreet } 1219cafe5635SKent Overstreet 1220cafe5635SKent Overstreet for (i = nodes - 1; i > 0; --i) { 1221cafe5635SKent Overstreet struct bset *n1 = r[i].b->sets->data; 1222cafe5635SKent Overstreet struct bset *n2 = r[i - 1].b->sets->data; 1223cafe5635SKent Overstreet struct bkey *k, *last = NULL; 1224cafe5635SKent Overstreet 1225cafe5635SKent Overstreet keys = 0; 1226cafe5635SKent Overstreet 1227cafe5635SKent Overstreet if (i == 1) { 1228cafe5635SKent Overstreet /* 1229cafe5635SKent Overstreet * Last node we're not getting rid of - we're getting 1230cafe5635SKent Overstreet * rid of the node at r[0]. Have to try and fit all of 1231cafe5635SKent Overstreet * the remaining keys into this node; we can't ensure 1232cafe5635SKent Overstreet * they will always fit due to rounding and variable 1233cafe5635SKent Overstreet * length keys (shouldn't be possible in practice, 1234cafe5635SKent Overstreet * though) 1235cafe5635SKent Overstreet */ 1236cafe5635SKent Overstreet if (__set_blocks(n1, n1->keys + r->keys, 1237cafe5635SKent Overstreet b->c) > btree_blocks(r[i].b)) 1238cafe5635SKent Overstreet return; 1239cafe5635SKent Overstreet 1240cafe5635SKent Overstreet keys = n2->keys; 1241cafe5635SKent Overstreet last = &r->b->key; 1242cafe5635SKent Overstreet } else 1243cafe5635SKent Overstreet for (k = n2->start; 1244cafe5635SKent Overstreet k < end(n2); 1245cafe5635SKent Overstreet k = bkey_next(k)) { 1246cafe5635SKent Overstreet if (__set_blocks(n1, n1->keys + keys + 1247cafe5635SKent Overstreet bkey_u64s(k), b->c) > blocks) 1248cafe5635SKent Overstreet break; 1249cafe5635SKent Overstreet 1250cafe5635SKent Overstreet last = k; 1251cafe5635SKent Overstreet keys += bkey_u64s(k); 1252cafe5635SKent Overstreet } 1253cafe5635SKent Overstreet 1254cafe5635SKent Overstreet BUG_ON(__set_blocks(n1, n1->keys + keys, 1255cafe5635SKent Overstreet b->c) > btree_blocks(r[i].b)); 1256cafe5635SKent Overstreet 1257cafe5635SKent Overstreet if (last) { 1258cafe5635SKent Overstreet bkey_copy_key(&r[i].b->key, last); 1259cafe5635SKent Overstreet bkey_copy_key(r[i].k, last); 1260cafe5635SKent Overstreet } 1261cafe5635SKent Overstreet 1262cafe5635SKent Overstreet memcpy(end(n1), 1263cafe5635SKent Overstreet n2->start, 1264cafe5635SKent Overstreet (void *) node(n2, keys) - (void *) n2->start); 1265cafe5635SKent Overstreet 1266cafe5635SKent Overstreet n1->keys += keys; 1267cafe5635SKent Overstreet 1268cafe5635SKent Overstreet memmove(n2->start, 1269cafe5635SKent Overstreet node(n2, keys), 1270cafe5635SKent Overstreet (void *) end(n2) - (void *) node(n2, keys)); 1271cafe5635SKent Overstreet 1272cafe5635SKent Overstreet n2->keys -= keys; 1273cafe5635SKent Overstreet 1274cafe5635SKent Overstreet r[i].keys = n1->keys; 1275cafe5635SKent Overstreet r[i - 1].keys = n2->keys; 1276cafe5635SKent Overstreet } 1277cafe5635SKent Overstreet 1278cafe5635SKent Overstreet btree_node_free(r->b, op); 1279cafe5635SKent Overstreet up_write(&r->b->lock); 1280cafe5635SKent Overstreet 1281cafe5635SKent Overstreet pr_debug("coalesced %u nodes", nodes); 1282cafe5635SKent Overstreet 1283cafe5635SKent Overstreet gc->nodes--; 1284cafe5635SKent Overstreet nodes--; 1285cafe5635SKent Overstreet 1286cafe5635SKent Overstreet memmove(&r[0], &r[1], sizeof(struct gc_merge_info) * nodes); 1287cafe5635SKent Overstreet memset(&r[nodes], 0, sizeof(struct gc_merge_info)); 1288cafe5635SKent Overstreet } 1289cafe5635SKent Overstreet 1290cafe5635SKent Overstreet static int btree_gc_recurse(struct btree *b, struct btree_op *op, 1291cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1292cafe5635SKent Overstreet { 1293cafe5635SKent Overstreet void write(struct btree *r) 1294cafe5635SKent Overstreet { 1295cafe5635SKent Overstreet if (!r->written) 1296cafe5635SKent Overstreet bch_btree_write(r, true, op); 1297cafe5635SKent Overstreet else if (btree_node_dirty(r)) { 1298cafe5635SKent Overstreet BUG_ON(btree_current_write(r)->owner); 1299cafe5635SKent Overstreet btree_current_write(r)->owner = writes; 1300cafe5635SKent Overstreet closure_get(writes); 1301cafe5635SKent Overstreet 1302cafe5635SKent Overstreet bch_btree_write(r, true, NULL); 1303cafe5635SKent Overstreet } 1304cafe5635SKent Overstreet 1305cafe5635SKent Overstreet up_write(&r->lock); 1306cafe5635SKent Overstreet } 1307cafe5635SKent Overstreet 1308cafe5635SKent Overstreet int ret = 0, stale; 1309cafe5635SKent Overstreet unsigned i; 1310cafe5635SKent Overstreet struct gc_merge_info r[GC_MERGE_NODES]; 1311cafe5635SKent Overstreet 1312cafe5635SKent Overstreet memset(r, 0, sizeof(r)); 1313cafe5635SKent Overstreet 1314cafe5635SKent Overstreet while ((r->k = bch_next_recurse_key(b, &b->c->gc_done))) { 1315cafe5635SKent Overstreet r->b = bch_btree_node_get(b->c, r->k, b->level - 1, op); 1316cafe5635SKent Overstreet 1317cafe5635SKent Overstreet if (IS_ERR(r->b)) { 1318cafe5635SKent Overstreet ret = PTR_ERR(r->b); 1319cafe5635SKent Overstreet break; 1320cafe5635SKent Overstreet } 1321cafe5635SKent Overstreet 1322cafe5635SKent Overstreet r->keys = 0; 1323cafe5635SKent Overstreet stale = btree_gc_mark_node(r->b, &r->keys, gc); 1324cafe5635SKent Overstreet 1325cafe5635SKent Overstreet if (!b->written && 1326cafe5635SKent Overstreet (r->b->level || stale > 10 || 1327cafe5635SKent Overstreet b->c->gc_always_rewrite)) 1328cafe5635SKent Overstreet r->b = btree_gc_alloc(r->b, r->k, op); 1329cafe5635SKent Overstreet 1330cafe5635SKent Overstreet if (r->b->level) 1331cafe5635SKent Overstreet ret = btree_gc_recurse(r->b, op, writes, gc); 1332cafe5635SKent Overstreet 1333cafe5635SKent Overstreet if (ret) { 1334cafe5635SKent Overstreet write(r->b); 1335cafe5635SKent Overstreet break; 1336cafe5635SKent Overstreet } 1337cafe5635SKent Overstreet 1338cafe5635SKent Overstreet bkey_copy_key(&b->c->gc_done, r->k); 1339cafe5635SKent Overstreet 1340cafe5635SKent Overstreet if (!b->written) 1341cafe5635SKent Overstreet btree_gc_coalesce(b, op, gc, r); 1342cafe5635SKent Overstreet 1343cafe5635SKent Overstreet if (r[GC_MERGE_NODES - 1].b) 1344cafe5635SKent Overstreet write(r[GC_MERGE_NODES - 1].b); 1345cafe5635SKent Overstreet 1346cafe5635SKent Overstreet memmove(&r[1], &r[0], 1347cafe5635SKent Overstreet sizeof(struct gc_merge_info) * (GC_MERGE_NODES - 1)); 1348cafe5635SKent Overstreet 1349cafe5635SKent Overstreet /* When we've got incremental GC working, we'll want to do 1350cafe5635SKent Overstreet * if (should_resched()) 1351cafe5635SKent Overstreet * return -EAGAIN; 1352cafe5635SKent Overstreet */ 1353cafe5635SKent Overstreet cond_resched(); 1354cafe5635SKent Overstreet #if 0 1355cafe5635SKent Overstreet if (need_resched()) { 1356cafe5635SKent Overstreet ret = -EAGAIN; 1357cafe5635SKent Overstreet break; 1358cafe5635SKent Overstreet } 1359cafe5635SKent Overstreet #endif 1360cafe5635SKent Overstreet } 1361cafe5635SKent Overstreet 1362cafe5635SKent Overstreet for (i = 1; i < GC_MERGE_NODES && r[i].b; i++) 1363cafe5635SKent Overstreet write(r[i].b); 1364cafe5635SKent Overstreet 1365cafe5635SKent Overstreet /* Might have freed some children, must remove their keys */ 1366cafe5635SKent Overstreet if (!b->written) 1367cafe5635SKent Overstreet bch_btree_sort(b); 1368cafe5635SKent Overstreet 1369cafe5635SKent Overstreet return ret; 1370cafe5635SKent Overstreet } 1371cafe5635SKent Overstreet 1372cafe5635SKent Overstreet static int bch_btree_gc_root(struct btree *b, struct btree_op *op, 1373cafe5635SKent Overstreet struct closure *writes, struct gc_stat *gc) 1374cafe5635SKent Overstreet { 1375cafe5635SKent Overstreet struct btree *n = NULL; 1376cafe5635SKent Overstreet unsigned keys = 0; 1377cafe5635SKent Overstreet int ret = 0, stale = btree_gc_mark_node(b, &keys, gc); 1378cafe5635SKent Overstreet 1379cafe5635SKent Overstreet if (b->level || stale > 10) 1380cafe5635SKent Overstreet n = btree_node_alloc_replacement(b, NULL); 1381cafe5635SKent Overstreet 1382cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) 1383cafe5635SKent Overstreet swap(b, n); 1384cafe5635SKent Overstreet 1385cafe5635SKent Overstreet if (b->level) 1386cafe5635SKent Overstreet ret = btree_gc_recurse(b, op, writes, gc); 1387cafe5635SKent Overstreet 1388cafe5635SKent Overstreet if (!b->written || btree_node_dirty(b)) { 1389cafe5635SKent Overstreet atomic_inc(&b->c->prio_blocked); 1390cafe5635SKent Overstreet b->prio_blocked++; 1391cafe5635SKent Overstreet bch_btree_write(b, true, n ? op : NULL); 1392cafe5635SKent Overstreet } 1393cafe5635SKent Overstreet 1394cafe5635SKent Overstreet if (!IS_ERR_OR_NULL(n)) { 1395cafe5635SKent Overstreet closure_sync(&op->cl); 1396cafe5635SKent Overstreet bch_btree_set_root(b); 1397cafe5635SKent Overstreet btree_node_free(n, op); 1398cafe5635SKent Overstreet rw_unlock(true, b); 1399cafe5635SKent Overstreet } 1400cafe5635SKent Overstreet 1401cafe5635SKent Overstreet return ret; 1402cafe5635SKent Overstreet } 1403cafe5635SKent Overstreet 1404cafe5635SKent Overstreet static void btree_gc_start(struct cache_set *c) 1405cafe5635SKent Overstreet { 1406cafe5635SKent Overstreet struct cache *ca; 1407cafe5635SKent Overstreet struct bucket *b; 1408cafe5635SKent Overstreet struct bcache_device **d; 1409cafe5635SKent Overstreet unsigned i; 1410cafe5635SKent Overstreet 1411cafe5635SKent Overstreet if (!c->gc_mark_valid) 1412cafe5635SKent Overstreet return; 1413cafe5635SKent Overstreet 1414cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1415cafe5635SKent Overstreet 1416cafe5635SKent Overstreet c->gc_mark_valid = 0; 1417cafe5635SKent Overstreet c->gc_done = ZERO_KEY; 1418cafe5635SKent Overstreet 1419cafe5635SKent Overstreet for_each_cache(ca, c, i) 1420cafe5635SKent Overstreet for_each_bucket(b, ca) { 1421cafe5635SKent Overstreet b->gc_gen = b->gen; 1422cafe5635SKent Overstreet if (!atomic_read(&b->pin)) 1423cafe5635SKent Overstreet SET_GC_MARK(b, GC_MARK_RECLAIMABLE); 1424cafe5635SKent Overstreet } 1425cafe5635SKent Overstreet 1426cafe5635SKent Overstreet for (d = c->devices; 1427cafe5635SKent Overstreet d < c->devices + c->nr_uuids; 1428cafe5635SKent Overstreet d++) 1429cafe5635SKent Overstreet if (*d) 1430cafe5635SKent Overstreet (*d)->sectors_dirty_gc = 0; 1431cafe5635SKent Overstreet 1432cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1433cafe5635SKent Overstreet } 1434cafe5635SKent Overstreet 1435cafe5635SKent Overstreet size_t bch_btree_gc_finish(struct cache_set *c) 1436cafe5635SKent Overstreet { 1437cafe5635SKent Overstreet size_t available = 0; 1438cafe5635SKent Overstreet struct bucket *b; 1439cafe5635SKent Overstreet struct cache *ca; 1440cafe5635SKent Overstreet struct bcache_device **d; 1441cafe5635SKent Overstreet unsigned i; 1442cafe5635SKent Overstreet 1443cafe5635SKent Overstreet mutex_lock(&c->bucket_lock); 1444cafe5635SKent Overstreet 1445cafe5635SKent Overstreet set_gc_sectors(c); 1446cafe5635SKent Overstreet c->gc_mark_valid = 1; 1447cafe5635SKent Overstreet c->need_gc = 0; 1448cafe5635SKent Overstreet 1449cafe5635SKent Overstreet if (c->root) 1450cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&c->root->key); i++) 1451cafe5635SKent Overstreet SET_GC_MARK(PTR_BUCKET(c, &c->root->key, i), 1452cafe5635SKent Overstreet GC_MARK_METADATA); 1453cafe5635SKent Overstreet 1454cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&c->uuid_bucket); i++) 1455cafe5635SKent Overstreet SET_GC_MARK(PTR_BUCKET(c, &c->uuid_bucket, i), 1456cafe5635SKent Overstreet GC_MARK_METADATA); 1457cafe5635SKent Overstreet 1458cafe5635SKent Overstreet for_each_cache(ca, c, i) { 1459cafe5635SKent Overstreet uint64_t *i; 1460cafe5635SKent Overstreet 1461cafe5635SKent Overstreet ca->invalidate_needs_gc = 0; 1462cafe5635SKent Overstreet 1463cafe5635SKent Overstreet for (i = ca->sb.d; i < ca->sb.d + ca->sb.keys; i++) 1464cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1465cafe5635SKent Overstreet 1466cafe5635SKent Overstreet for (i = ca->prio_buckets; 1467cafe5635SKent Overstreet i < ca->prio_buckets + prio_buckets(ca) * 2; i++) 1468cafe5635SKent Overstreet SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA); 1469cafe5635SKent Overstreet 1470cafe5635SKent Overstreet for_each_bucket(b, ca) { 1471cafe5635SKent Overstreet b->last_gc = b->gc_gen; 1472cafe5635SKent Overstreet c->need_gc = max(c->need_gc, bucket_gc_gen(b)); 1473cafe5635SKent Overstreet 1474cafe5635SKent Overstreet if (!atomic_read(&b->pin) && 1475cafe5635SKent Overstreet GC_MARK(b) == GC_MARK_RECLAIMABLE) { 1476cafe5635SKent Overstreet available++; 1477cafe5635SKent Overstreet if (!GC_SECTORS_USED(b)) 1478cafe5635SKent Overstreet bch_bucket_add_unused(ca, b); 1479cafe5635SKent Overstreet } 1480cafe5635SKent Overstreet } 1481cafe5635SKent Overstreet } 1482cafe5635SKent Overstreet 1483cafe5635SKent Overstreet for (d = c->devices; 1484cafe5635SKent Overstreet d < c->devices + c->nr_uuids; 1485cafe5635SKent Overstreet d++) 1486cafe5635SKent Overstreet if (*d) { 1487cafe5635SKent Overstreet unsigned long last = 1488cafe5635SKent Overstreet atomic_long_read(&((*d)->sectors_dirty)); 1489cafe5635SKent Overstreet long difference = (*d)->sectors_dirty_gc - last; 1490cafe5635SKent Overstreet 1491cafe5635SKent Overstreet pr_debug("sectors dirty off by %li", difference); 1492cafe5635SKent Overstreet 1493cafe5635SKent Overstreet (*d)->sectors_dirty_last += difference; 1494cafe5635SKent Overstreet 1495cafe5635SKent Overstreet atomic_long_set(&((*d)->sectors_dirty), 1496cafe5635SKent Overstreet (*d)->sectors_dirty_gc); 1497cafe5635SKent Overstreet } 1498cafe5635SKent Overstreet 1499cafe5635SKent Overstreet mutex_unlock(&c->bucket_lock); 1500cafe5635SKent Overstreet return available; 1501cafe5635SKent Overstreet } 1502cafe5635SKent Overstreet 1503cafe5635SKent Overstreet static void bch_btree_gc(struct closure *cl) 1504cafe5635SKent Overstreet { 1505cafe5635SKent Overstreet struct cache_set *c = container_of(cl, struct cache_set, gc.cl); 1506cafe5635SKent Overstreet int ret; 1507cafe5635SKent Overstreet unsigned long available; 1508cafe5635SKent Overstreet struct gc_stat stats; 1509cafe5635SKent Overstreet struct closure writes; 1510cafe5635SKent Overstreet struct btree_op op; 1511cafe5635SKent Overstreet 1512cafe5635SKent Overstreet uint64_t start_time = local_clock(); 1513cafe5635SKent Overstreet trace_bcache_gc_start(c->sb.set_uuid); 1514cafe5635SKent Overstreet blktrace_msg_all(c, "Starting gc"); 1515cafe5635SKent Overstreet 1516cafe5635SKent Overstreet memset(&stats, 0, sizeof(struct gc_stat)); 1517cafe5635SKent Overstreet closure_init_stack(&writes); 1518cafe5635SKent Overstreet bch_btree_op_init_stack(&op); 1519cafe5635SKent Overstreet op.lock = SHRT_MAX; 1520cafe5635SKent Overstreet 1521cafe5635SKent Overstreet btree_gc_start(c); 1522cafe5635SKent Overstreet 1523cafe5635SKent Overstreet ret = btree_root(gc_root, c, &op, &writes, &stats); 1524cafe5635SKent Overstreet closure_sync(&op.cl); 1525cafe5635SKent Overstreet closure_sync(&writes); 1526cafe5635SKent Overstreet 1527cafe5635SKent Overstreet if (ret) { 1528cafe5635SKent Overstreet blktrace_msg_all(c, "Stopped gc"); 1529cafe5635SKent Overstreet pr_warn("gc failed!"); 1530cafe5635SKent Overstreet 1531cafe5635SKent Overstreet continue_at(cl, bch_btree_gc, bch_gc_wq); 1532cafe5635SKent Overstreet } 1533cafe5635SKent Overstreet 1534cafe5635SKent Overstreet /* Possibly wait for new UUIDs or whatever to hit disk */ 1535cafe5635SKent Overstreet bch_journal_meta(c, &op.cl); 1536cafe5635SKent Overstreet closure_sync(&op.cl); 1537cafe5635SKent Overstreet 1538cafe5635SKent Overstreet available = bch_btree_gc_finish(c); 1539cafe5635SKent Overstreet 1540169ef1cfSKent Overstreet bch_time_stats_update(&c->btree_gc_time, start_time); 1541cafe5635SKent Overstreet 1542cafe5635SKent Overstreet stats.key_bytes *= sizeof(uint64_t); 1543cafe5635SKent Overstreet stats.dirty <<= 9; 1544cafe5635SKent Overstreet stats.data <<= 9; 1545cafe5635SKent Overstreet stats.in_use = (c->nbuckets - available) * 100 / c->nbuckets; 1546cafe5635SKent Overstreet memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat)); 1547cafe5635SKent Overstreet blktrace_msg_all(c, "Finished gc"); 1548cafe5635SKent Overstreet 1549cafe5635SKent Overstreet trace_bcache_gc_end(c->sb.set_uuid); 1550*119ba0f8SKent Overstreet wake_up_allocators(c); 1551cafe5635SKent Overstreet 1552cafe5635SKent Overstreet continue_at(cl, bch_moving_gc, bch_gc_wq); 1553cafe5635SKent Overstreet } 1554cafe5635SKent Overstreet 1555cafe5635SKent Overstreet void bch_queue_gc(struct cache_set *c) 1556cafe5635SKent Overstreet { 1557cafe5635SKent Overstreet closure_trylock_call(&c->gc.cl, bch_btree_gc, bch_gc_wq, &c->cl); 1558cafe5635SKent Overstreet } 1559cafe5635SKent Overstreet 1560cafe5635SKent Overstreet /* Initial partial gc */ 1561cafe5635SKent Overstreet 1562cafe5635SKent Overstreet static int bch_btree_check_recurse(struct btree *b, struct btree_op *op, 1563cafe5635SKent Overstreet unsigned long **seen) 1564cafe5635SKent Overstreet { 1565cafe5635SKent Overstreet int ret; 1566cafe5635SKent Overstreet unsigned i; 1567cafe5635SKent Overstreet struct bkey *k; 1568cafe5635SKent Overstreet struct bucket *g; 1569cafe5635SKent Overstreet struct btree_iter iter; 1570cafe5635SKent Overstreet 1571cafe5635SKent Overstreet for_each_key_filter(b, k, &iter, bch_ptr_invalid) { 1572cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(k); i++) { 1573cafe5635SKent Overstreet if (!ptr_available(b->c, k, i)) 1574cafe5635SKent Overstreet continue; 1575cafe5635SKent Overstreet 1576cafe5635SKent Overstreet g = PTR_BUCKET(b->c, k, i); 1577cafe5635SKent Overstreet 1578cafe5635SKent Overstreet if (!__test_and_set_bit(PTR_BUCKET_NR(b->c, k, i), 1579cafe5635SKent Overstreet seen[PTR_DEV(k, i)]) || 1580cafe5635SKent Overstreet !ptr_stale(b->c, k, i)) { 1581cafe5635SKent Overstreet g->gen = PTR_GEN(k, i); 1582cafe5635SKent Overstreet 1583cafe5635SKent Overstreet if (b->level) 1584cafe5635SKent Overstreet g->prio = BTREE_PRIO; 1585cafe5635SKent Overstreet else if (g->prio == BTREE_PRIO) 1586cafe5635SKent Overstreet g->prio = INITIAL_PRIO; 1587cafe5635SKent Overstreet } 1588cafe5635SKent Overstreet } 1589cafe5635SKent Overstreet 1590cafe5635SKent Overstreet btree_mark_key(b, k); 1591cafe5635SKent Overstreet } 1592cafe5635SKent Overstreet 1593cafe5635SKent Overstreet if (b->level) { 1594cafe5635SKent Overstreet k = bch_next_recurse_key(b, &ZERO_KEY); 1595cafe5635SKent Overstreet 1596cafe5635SKent Overstreet while (k) { 1597cafe5635SKent Overstreet struct bkey *p = bch_next_recurse_key(b, k); 1598cafe5635SKent Overstreet if (p) 1599cafe5635SKent Overstreet btree_node_prefetch(b->c, p, b->level - 1); 1600cafe5635SKent Overstreet 1601cafe5635SKent Overstreet ret = btree(check_recurse, k, b, op, seen); 1602cafe5635SKent Overstreet if (ret) 1603cafe5635SKent Overstreet return ret; 1604cafe5635SKent Overstreet 1605cafe5635SKent Overstreet k = p; 1606cafe5635SKent Overstreet } 1607cafe5635SKent Overstreet } 1608cafe5635SKent Overstreet 1609cafe5635SKent Overstreet return 0; 1610cafe5635SKent Overstreet } 1611cafe5635SKent Overstreet 1612cafe5635SKent Overstreet int bch_btree_check(struct cache_set *c, struct btree_op *op) 1613cafe5635SKent Overstreet { 1614cafe5635SKent Overstreet int ret = -ENOMEM; 1615cafe5635SKent Overstreet unsigned i; 1616cafe5635SKent Overstreet unsigned long *seen[MAX_CACHES_PER_SET]; 1617cafe5635SKent Overstreet 1618cafe5635SKent Overstreet memset(seen, 0, sizeof(seen)); 1619cafe5635SKent Overstreet 1620cafe5635SKent Overstreet for (i = 0; c->cache[i]; i++) { 1621cafe5635SKent Overstreet size_t n = DIV_ROUND_UP(c->cache[i]->sb.nbuckets, 8); 1622cafe5635SKent Overstreet seen[i] = kmalloc(n, GFP_KERNEL); 1623cafe5635SKent Overstreet if (!seen[i]) 1624cafe5635SKent Overstreet goto err; 1625cafe5635SKent Overstreet 1626cafe5635SKent Overstreet /* Disables the seen array until prio_read() uses it too */ 1627cafe5635SKent Overstreet memset(seen[i], 0xFF, n); 1628cafe5635SKent Overstreet } 1629cafe5635SKent Overstreet 1630cafe5635SKent Overstreet ret = btree_root(check_recurse, c, op, seen); 1631cafe5635SKent Overstreet err: 1632cafe5635SKent Overstreet for (i = 0; i < MAX_CACHES_PER_SET; i++) 1633cafe5635SKent Overstreet kfree(seen[i]); 1634cafe5635SKent Overstreet return ret; 1635cafe5635SKent Overstreet } 1636cafe5635SKent Overstreet 1637cafe5635SKent Overstreet /* Btree insertion */ 1638cafe5635SKent Overstreet 1639cafe5635SKent Overstreet static void shift_keys(struct btree *b, struct bkey *where, struct bkey *insert) 1640cafe5635SKent Overstreet { 1641cafe5635SKent Overstreet struct bset *i = b->sets[b->nsets].data; 1642cafe5635SKent Overstreet 1643cafe5635SKent Overstreet memmove((uint64_t *) where + bkey_u64s(insert), 1644cafe5635SKent Overstreet where, 1645cafe5635SKent Overstreet (void *) end(i) - (void *) where); 1646cafe5635SKent Overstreet 1647cafe5635SKent Overstreet i->keys += bkey_u64s(insert); 1648cafe5635SKent Overstreet bkey_copy(where, insert); 1649cafe5635SKent Overstreet bch_bset_fix_lookup_table(b, where); 1650cafe5635SKent Overstreet } 1651cafe5635SKent Overstreet 1652cafe5635SKent Overstreet static bool fix_overlapping_extents(struct btree *b, 1653cafe5635SKent Overstreet struct bkey *insert, 1654cafe5635SKent Overstreet struct btree_iter *iter, 1655cafe5635SKent Overstreet struct btree_op *op) 1656cafe5635SKent Overstreet { 1657cafe5635SKent Overstreet void subtract_dirty(struct bkey *k, int sectors) 1658cafe5635SKent Overstreet { 1659cafe5635SKent Overstreet struct bcache_device *d = b->c->devices[KEY_INODE(k)]; 1660cafe5635SKent Overstreet 1661cafe5635SKent Overstreet if (KEY_DIRTY(k) && d) 1662cafe5635SKent Overstreet atomic_long_sub(sectors, &d->sectors_dirty); 1663cafe5635SKent Overstreet } 1664cafe5635SKent Overstreet 1665cafe5635SKent Overstreet unsigned old_size, sectors_found = 0; 1666cafe5635SKent Overstreet 1667cafe5635SKent Overstreet while (1) { 1668cafe5635SKent Overstreet struct bkey *k = bch_btree_iter_next(iter); 1669cafe5635SKent Overstreet if (!k || 1670cafe5635SKent Overstreet bkey_cmp(&START_KEY(k), insert) >= 0) 1671cafe5635SKent Overstreet break; 1672cafe5635SKent Overstreet 1673cafe5635SKent Overstreet if (bkey_cmp(k, &START_KEY(insert)) <= 0) 1674cafe5635SKent Overstreet continue; 1675cafe5635SKent Overstreet 1676cafe5635SKent Overstreet old_size = KEY_SIZE(k); 1677cafe5635SKent Overstreet 1678cafe5635SKent Overstreet /* 1679cafe5635SKent Overstreet * We might overlap with 0 size extents; we can't skip these 1680cafe5635SKent Overstreet * because if they're in the set we're inserting to we have to 1681cafe5635SKent Overstreet * adjust them so they don't overlap with the key we're 1682cafe5635SKent Overstreet * inserting. But we don't want to check them for BTREE_REPLACE 1683cafe5635SKent Overstreet * operations. 1684cafe5635SKent Overstreet */ 1685cafe5635SKent Overstreet 1686cafe5635SKent Overstreet if (op->type == BTREE_REPLACE && 1687cafe5635SKent Overstreet KEY_SIZE(k)) { 1688cafe5635SKent Overstreet /* 1689cafe5635SKent Overstreet * k might have been split since we inserted/found the 1690cafe5635SKent Overstreet * key we're replacing 1691cafe5635SKent Overstreet */ 1692cafe5635SKent Overstreet unsigned i; 1693cafe5635SKent Overstreet uint64_t offset = KEY_START(k) - 1694cafe5635SKent Overstreet KEY_START(&op->replace); 1695cafe5635SKent Overstreet 1696cafe5635SKent Overstreet /* But it must be a subset of the replace key */ 1697cafe5635SKent Overstreet if (KEY_START(k) < KEY_START(&op->replace) || 1698cafe5635SKent Overstreet KEY_OFFSET(k) > KEY_OFFSET(&op->replace)) 1699cafe5635SKent Overstreet goto check_failed; 1700cafe5635SKent Overstreet 1701cafe5635SKent Overstreet /* We didn't find a key that we were supposed to */ 1702cafe5635SKent Overstreet if (KEY_START(k) > KEY_START(insert) + sectors_found) 1703cafe5635SKent Overstreet goto check_failed; 1704cafe5635SKent Overstreet 1705cafe5635SKent Overstreet if (KEY_PTRS(&op->replace) != KEY_PTRS(k)) 1706cafe5635SKent Overstreet goto check_failed; 1707cafe5635SKent Overstreet 1708cafe5635SKent Overstreet /* skip past gen */ 1709cafe5635SKent Overstreet offset <<= 8; 1710cafe5635SKent Overstreet 1711cafe5635SKent Overstreet BUG_ON(!KEY_PTRS(&op->replace)); 1712cafe5635SKent Overstreet 1713cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&op->replace); i++) 1714cafe5635SKent Overstreet if (k->ptr[i] != op->replace.ptr[i] + offset) 1715cafe5635SKent Overstreet goto check_failed; 1716cafe5635SKent Overstreet 1717cafe5635SKent Overstreet sectors_found = KEY_OFFSET(k) - KEY_START(insert); 1718cafe5635SKent Overstreet } 1719cafe5635SKent Overstreet 1720cafe5635SKent Overstreet if (bkey_cmp(insert, k) < 0 && 1721cafe5635SKent Overstreet bkey_cmp(&START_KEY(insert), &START_KEY(k)) > 0) { 1722cafe5635SKent Overstreet /* 1723cafe5635SKent Overstreet * We overlapped in the middle of an existing key: that 1724cafe5635SKent Overstreet * means we have to split the old key. But we have to do 1725cafe5635SKent Overstreet * slightly different things depending on whether the 1726cafe5635SKent Overstreet * old key has been written out yet. 1727cafe5635SKent Overstreet */ 1728cafe5635SKent Overstreet 1729cafe5635SKent Overstreet struct bkey *top; 1730cafe5635SKent Overstreet 1731cafe5635SKent Overstreet subtract_dirty(k, KEY_SIZE(insert)); 1732cafe5635SKent Overstreet 1733cafe5635SKent Overstreet if (bkey_written(b, k)) { 1734cafe5635SKent Overstreet /* 1735cafe5635SKent Overstreet * We insert a new key to cover the top of the 1736cafe5635SKent Overstreet * old key, and the old key is modified in place 1737cafe5635SKent Overstreet * to represent the bottom split. 1738cafe5635SKent Overstreet * 1739cafe5635SKent Overstreet * It's completely arbitrary whether the new key 1740cafe5635SKent Overstreet * is the top or the bottom, but it has to match 1741cafe5635SKent Overstreet * up with what btree_sort_fixup() does - it 1742cafe5635SKent Overstreet * doesn't check for this kind of overlap, it 1743cafe5635SKent Overstreet * depends on us inserting a new key for the top 1744cafe5635SKent Overstreet * here. 1745cafe5635SKent Overstreet */ 1746cafe5635SKent Overstreet top = bch_bset_search(b, &b->sets[b->nsets], 1747cafe5635SKent Overstreet insert); 1748cafe5635SKent Overstreet shift_keys(b, top, k); 1749cafe5635SKent Overstreet } else { 1750cafe5635SKent Overstreet BKEY_PADDED(key) temp; 1751cafe5635SKent Overstreet bkey_copy(&temp.key, k); 1752cafe5635SKent Overstreet shift_keys(b, k, &temp.key); 1753cafe5635SKent Overstreet top = bkey_next(k); 1754cafe5635SKent Overstreet } 1755cafe5635SKent Overstreet 1756cafe5635SKent Overstreet bch_cut_front(insert, top); 1757cafe5635SKent Overstreet bch_cut_back(&START_KEY(insert), k); 1758cafe5635SKent Overstreet bch_bset_fix_invalidated_key(b, k); 1759cafe5635SKent Overstreet return false; 1760cafe5635SKent Overstreet } 1761cafe5635SKent Overstreet 1762cafe5635SKent Overstreet if (bkey_cmp(insert, k) < 0) { 1763cafe5635SKent Overstreet bch_cut_front(insert, k); 1764cafe5635SKent Overstreet } else { 1765cafe5635SKent Overstreet if (bkey_written(b, k) && 1766cafe5635SKent Overstreet bkey_cmp(&START_KEY(insert), &START_KEY(k)) <= 0) { 1767cafe5635SKent Overstreet /* 1768cafe5635SKent Overstreet * Completely overwrote, so we don't have to 1769cafe5635SKent Overstreet * invalidate the binary search tree 1770cafe5635SKent Overstreet */ 1771cafe5635SKent Overstreet bch_cut_front(k, k); 1772cafe5635SKent Overstreet } else { 1773cafe5635SKent Overstreet __bch_cut_back(&START_KEY(insert), k); 1774cafe5635SKent Overstreet bch_bset_fix_invalidated_key(b, k); 1775cafe5635SKent Overstreet } 1776cafe5635SKent Overstreet } 1777cafe5635SKent Overstreet 1778cafe5635SKent Overstreet subtract_dirty(k, old_size - KEY_SIZE(k)); 1779cafe5635SKent Overstreet } 1780cafe5635SKent Overstreet 1781cafe5635SKent Overstreet check_failed: 1782cafe5635SKent Overstreet if (op->type == BTREE_REPLACE) { 1783cafe5635SKent Overstreet if (!sectors_found) { 1784cafe5635SKent Overstreet op->insert_collision = true; 1785cafe5635SKent Overstreet return true; 1786cafe5635SKent Overstreet } else if (sectors_found < KEY_SIZE(insert)) { 1787cafe5635SKent Overstreet SET_KEY_OFFSET(insert, KEY_OFFSET(insert) - 1788cafe5635SKent Overstreet (KEY_SIZE(insert) - sectors_found)); 1789cafe5635SKent Overstreet SET_KEY_SIZE(insert, sectors_found); 1790cafe5635SKent Overstreet } 1791cafe5635SKent Overstreet } 1792cafe5635SKent Overstreet 1793cafe5635SKent Overstreet return false; 1794cafe5635SKent Overstreet } 1795cafe5635SKent Overstreet 1796cafe5635SKent Overstreet static bool btree_insert_key(struct btree *b, struct btree_op *op, 1797cafe5635SKent Overstreet struct bkey *k) 1798cafe5635SKent Overstreet { 1799cafe5635SKent Overstreet struct bset *i = b->sets[b->nsets].data; 1800cafe5635SKent Overstreet struct bkey *m, *prev; 1801cafe5635SKent Overstreet const char *status = "insert"; 1802cafe5635SKent Overstreet 1803cafe5635SKent Overstreet BUG_ON(bkey_cmp(k, &b->key) > 0); 1804cafe5635SKent Overstreet BUG_ON(b->level && !KEY_PTRS(k)); 1805cafe5635SKent Overstreet BUG_ON(!b->level && !KEY_OFFSET(k)); 1806cafe5635SKent Overstreet 1807cafe5635SKent Overstreet if (!b->level) { 1808cafe5635SKent Overstreet struct btree_iter iter; 1809cafe5635SKent Overstreet struct bkey search = KEY(KEY_INODE(k), KEY_START(k), 0); 1810cafe5635SKent Overstreet 1811cafe5635SKent Overstreet /* 1812cafe5635SKent Overstreet * bset_search() returns the first key that is strictly greater 1813cafe5635SKent Overstreet * than the search key - but for back merging, we want to find 1814cafe5635SKent Overstreet * the first key that is greater than or equal to KEY_START(k) - 1815cafe5635SKent Overstreet * unless KEY_START(k) is 0. 1816cafe5635SKent Overstreet */ 1817cafe5635SKent Overstreet if (KEY_OFFSET(&search)) 1818cafe5635SKent Overstreet SET_KEY_OFFSET(&search, KEY_OFFSET(&search) - 1); 1819cafe5635SKent Overstreet 1820cafe5635SKent Overstreet prev = NULL; 1821cafe5635SKent Overstreet m = bch_btree_iter_init(b, &iter, &search); 1822cafe5635SKent Overstreet 1823cafe5635SKent Overstreet if (fix_overlapping_extents(b, k, &iter, op)) 1824cafe5635SKent Overstreet return false; 1825cafe5635SKent Overstreet 1826cafe5635SKent Overstreet while (m != end(i) && 1827cafe5635SKent Overstreet bkey_cmp(k, &START_KEY(m)) > 0) 1828cafe5635SKent Overstreet prev = m, m = bkey_next(m); 1829cafe5635SKent Overstreet 1830cafe5635SKent Overstreet if (key_merging_disabled(b->c)) 1831cafe5635SKent Overstreet goto insert; 1832cafe5635SKent Overstreet 1833cafe5635SKent Overstreet /* prev is in the tree, if we merge we're done */ 1834cafe5635SKent Overstreet status = "back merging"; 1835cafe5635SKent Overstreet if (prev && 1836cafe5635SKent Overstreet bch_bkey_try_merge(b, prev, k)) 1837cafe5635SKent Overstreet goto merged; 1838cafe5635SKent Overstreet 1839cafe5635SKent Overstreet status = "overwrote front"; 1840cafe5635SKent Overstreet if (m != end(i) && 1841cafe5635SKent Overstreet KEY_PTRS(m) == KEY_PTRS(k) && !KEY_SIZE(m)) 1842cafe5635SKent Overstreet goto copy; 1843cafe5635SKent Overstreet 1844cafe5635SKent Overstreet status = "front merge"; 1845cafe5635SKent Overstreet if (m != end(i) && 1846cafe5635SKent Overstreet bch_bkey_try_merge(b, k, m)) 1847cafe5635SKent Overstreet goto copy; 1848cafe5635SKent Overstreet } else 1849cafe5635SKent Overstreet m = bch_bset_search(b, &b->sets[b->nsets], k); 1850cafe5635SKent Overstreet 1851cafe5635SKent Overstreet insert: shift_keys(b, m, k); 1852cafe5635SKent Overstreet copy: bkey_copy(m, k); 1853cafe5635SKent Overstreet merged: 1854cafe5635SKent Overstreet bch_check_keys(b, "%s for %s at %s: %s", status, 1855cafe5635SKent Overstreet op_type(op), pbtree(b), pkey(k)); 1856cafe5635SKent Overstreet bch_check_key_order_msg(b, i, "%s for %s at %s: %s", status, 1857cafe5635SKent Overstreet op_type(op), pbtree(b), pkey(k)); 1858cafe5635SKent Overstreet 1859cafe5635SKent Overstreet if (b->level && !KEY_OFFSET(k)) 1860cafe5635SKent Overstreet b->prio_blocked++; 1861cafe5635SKent Overstreet 1862cafe5635SKent Overstreet pr_debug("%s for %s at %s: %s", status, 1863cafe5635SKent Overstreet op_type(op), pbtree(b), pkey(k)); 1864cafe5635SKent Overstreet 1865cafe5635SKent Overstreet return true; 1866cafe5635SKent Overstreet } 1867cafe5635SKent Overstreet 1868cafe5635SKent Overstreet bool bch_btree_insert_keys(struct btree *b, struct btree_op *op) 1869cafe5635SKent Overstreet { 1870cafe5635SKent Overstreet bool ret = false; 1871cafe5635SKent Overstreet struct bkey *k; 1872cafe5635SKent Overstreet unsigned oldsize = bch_count_data(b); 1873cafe5635SKent Overstreet 1874cafe5635SKent Overstreet while ((k = bch_keylist_pop(&op->keys))) { 1875cafe5635SKent Overstreet bkey_put(b->c, k, b->level); 1876cafe5635SKent Overstreet ret |= btree_insert_key(b, op, k); 1877cafe5635SKent Overstreet } 1878cafe5635SKent Overstreet 1879cafe5635SKent Overstreet BUG_ON(bch_count_data(b) < oldsize); 1880cafe5635SKent Overstreet return ret; 1881cafe5635SKent Overstreet } 1882cafe5635SKent Overstreet 1883cafe5635SKent Overstreet bool bch_btree_insert_check_key(struct btree *b, struct btree_op *op, 1884cafe5635SKent Overstreet struct bio *bio) 1885cafe5635SKent Overstreet { 1886cafe5635SKent Overstreet bool ret = false; 1887cafe5635SKent Overstreet uint64_t btree_ptr = b->key.ptr[0]; 1888cafe5635SKent Overstreet unsigned long seq = b->seq; 1889cafe5635SKent Overstreet BKEY_PADDED(k) tmp; 1890cafe5635SKent Overstreet 1891cafe5635SKent Overstreet rw_unlock(false, b); 1892cafe5635SKent Overstreet rw_lock(true, b, b->level); 1893cafe5635SKent Overstreet 1894cafe5635SKent Overstreet if (b->key.ptr[0] != btree_ptr || 1895cafe5635SKent Overstreet b->seq != seq + 1 || 1896cafe5635SKent Overstreet should_split(b)) 1897cafe5635SKent Overstreet goto out; 1898cafe5635SKent Overstreet 1899cafe5635SKent Overstreet op->replace = KEY(op->inode, bio_end(bio), bio_sectors(bio)); 1900cafe5635SKent Overstreet 1901cafe5635SKent Overstreet SET_KEY_PTRS(&op->replace, 1); 1902cafe5635SKent Overstreet get_random_bytes(&op->replace.ptr[0], sizeof(uint64_t)); 1903cafe5635SKent Overstreet 1904cafe5635SKent Overstreet SET_PTR_DEV(&op->replace, 0, PTR_CHECK_DEV); 1905cafe5635SKent Overstreet 1906cafe5635SKent Overstreet bkey_copy(&tmp.k, &op->replace); 1907cafe5635SKent Overstreet 1908cafe5635SKent Overstreet BUG_ON(op->type != BTREE_INSERT); 1909cafe5635SKent Overstreet BUG_ON(!btree_insert_key(b, op, &tmp.k)); 1910cafe5635SKent Overstreet bch_btree_write(b, false, NULL); 1911cafe5635SKent Overstreet ret = true; 1912cafe5635SKent Overstreet out: 1913cafe5635SKent Overstreet downgrade_write(&b->lock); 1914cafe5635SKent Overstreet return ret; 1915cafe5635SKent Overstreet } 1916cafe5635SKent Overstreet 1917cafe5635SKent Overstreet static int btree_split(struct btree *b, struct btree_op *op) 1918cafe5635SKent Overstreet { 1919cafe5635SKent Overstreet bool split, root = b == b->c->root; 1920cafe5635SKent Overstreet struct btree *n1, *n2 = NULL, *n3 = NULL; 1921cafe5635SKent Overstreet uint64_t start_time = local_clock(); 1922cafe5635SKent Overstreet 1923cafe5635SKent Overstreet if (b->level) 1924cafe5635SKent Overstreet set_closure_blocking(&op->cl); 1925cafe5635SKent Overstreet 1926cafe5635SKent Overstreet n1 = btree_node_alloc_replacement(b, &op->cl); 1927cafe5635SKent Overstreet if (IS_ERR(n1)) 1928cafe5635SKent Overstreet goto err; 1929cafe5635SKent Overstreet 1930cafe5635SKent Overstreet split = set_blocks(n1->sets[0].data, n1->c) > (btree_blocks(b) * 4) / 5; 1931cafe5635SKent Overstreet 1932cafe5635SKent Overstreet pr_debug("%ssplitting at %s keys %i", split ? "" : "not ", 1933cafe5635SKent Overstreet pbtree(b), n1->sets[0].data->keys); 1934cafe5635SKent Overstreet 1935cafe5635SKent Overstreet if (split) { 1936cafe5635SKent Overstreet unsigned keys = 0; 1937cafe5635SKent Overstreet 1938cafe5635SKent Overstreet n2 = bch_btree_node_alloc(b->c, b->level, &op->cl); 1939cafe5635SKent Overstreet if (IS_ERR(n2)) 1940cafe5635SKent Overstreet goto err_free1; 1941cafe5635SKent Overstreet 1942cafe5635SKent Overstreet if (root) { 1943cafe5635SKent Overstreet n3 = bch_btree_node_alloc(b->c, b->level + 1, &op->cl); 1944cafe5635SKent Overstreet if (IS_ERR(n3)) 1945cafe5635SKent Overstreet goto err_free2; 1946cafe5635SKent Overstreet } 1947cafe5635SKent Overstreet 1948cafe5635SKent Overstreet bch_btree_insert_keys(n1, op); 1949cafe5635SKent Overstreet 1950cafe5635SKent Overstreet /* Has to be a linear search because we don't have an auxiliary 1951cafe5635SKent Overstreet * search tree yet 1952cafe5635SKent Overstreet */ 1953cafe5635SKent Overstreet 1954cafe5635SKent Overstreet while (keys < (n1->sets[0].data->keys * 3) / 5) 1955cafe5635SKent Overstreet keys += bkey_u64s(node(n1->sets[0].data, keys)); 1956cafe5635SKent Overstreet 1957cafe5635SKent Overstreet bkey_copy_key(&n1->key, node(n1->sets[0].data, keys)); 1958cafe5635SKent Overstreet keys += bkey_u64s(node(n1->sets[0].data, keys)); 1959cafe5635SKent Overstreet 1960cafe5635SKent Overstreet n2->sets[0].data->keys = n1->sets[0].data->keys - keys; 1961cafe5635SKent Overstreet n1->sets[0].data->keys = keys; 1962cafe5635SKent Overstreet 1963cafe5635SKent Overstreet memcpy(n2->sets[0].data->start, 1964cafe5635SKent Overstreet end(n1->sets[0].data), 1965cafe5635SKent Overstreet n2->sets[0].data->keys * sizeof(uint64_t)); 1966cafe5635SKent Overstreet 1967cafe5635SKent Overstreet bkey_copy_key(&n2->key, &b->key); 1968cafe5635SKent Overstreet 1969cafe5635SKent Overstreet bch_keylist_add(&op->keys, &n2->key); 1970cafe5635SKent Overstreet bch_btree_write(n2, true, op); 1971cafe5635SKent Overstreet rw_unlock(true, n2); 1972cafe5635SKent Overstreet } else 1973cafe5635SKent Overstreet bch_btree_insert_keys(n1, op); 1974cafe5635SKent Overstreet 1975cafe5635SKent Overstreet bch_keylist_add(&op->keys, &n1->key); 1976cafe5635SKent Overstreet bch_btree_write(n1, true, op); 1977cafe5635SKent Overstreet 1978cafe5635SKent Overstreet if (n3) { 1979cafe5635SKent Overstreet bkey_copy_key(&n3->key, &MAX_KEY); 1980cafe5635SKent Overstreet bch_btree_insert_keys(n3, op); 1981cafe5635SKent Overstreet bch_btree_write(n3, true, op); 1982cafe5635SKent Overstreet 1983cafe5635SKent Overstreet closure_sync(&op->cl); 1984cafe5635SKent Overstreet bch_btree_set_root(n3); 1985cafe5635SKent Overstreet rw_unlock(true, n3); 1986cafe5635SKent Overstreet } else if (root) { 1987cafe5635SKent Overstreet op->keys.top = op->keys.bottom; 1988cafe5635SKent Overstreet closure_sync(&op->cl); 1989cafe5635SKent Overstreet bch_btree_set_root(n1); 1990cafe5635SKent Overstreet } else { 1991cafe5635SKent Overstreet unsigned i; 1992cafe5635SKent Overstreet 1993cafe5635SKent Overstreet bkey_copy(op->keys.top, &b->key); 1994cafe5635SKent Overstreet bkey_copy_key(op->keys.top, &ZERO_KEY); 1995cafe5635SKent Overstreet 1996cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) { 1997cafe5635SKent Overstreet uint8_t g = PTR_BUCKET(b->c, &b->key, i)->gen + 1; 1998cafe5635SKent Overstreet 1999cafe5635SKent Overstreet SET_PTR_GEN(op->keys.top, i, g); 2000cafe5635SKent Overstreet } 2001cafe5635SKent Overstreet 2002cafe5635SKent Overstreet bch_keylist_push(&op->keys); 2003cafe5635SKent Overstreet closure_sync(&op->cl); 2004cafe5635SKent Overstreet atomic_inc(&b->c->prio_blocked); 2005cafe5635SKent Overstreet } 2006cafe5635SKent Overstreet 2007cafe5635SKent Overstreet rw_unlock(true, n1); 2008cafe5635SKent Overstreet btree_node_free(b, op); 2009cafe5635SKent Overstreet 2010169ef1cfSKent Overstreet bch_time_stats_update(&b->c->btree_split_time, start_time); 2011cafe5635SKent Overstreet 2012cafe5635SKent Overstreet return 0; 2013cafe5635SKent Overstreet err_free2: 2014cafe5635SKent Overstreet __bkey_put(n2->c, &n2->key); 2015cafe5635SKent Overstreet btree_node_free(n2, op); 2016cafe5635SKent Overstreet rw_unlock(true, n2); 2017cafe5635SKent Overstreet err_free1: 2018cafe5635SKent Overstreet __bkey_put(n1->c, &n1->key); 2019cafe5635SKent Overstreet btree_node_free(n1, op); 2020cafe5635SKent Overstreet rw_unlock(true, n1); 2021cafe5635SKent Overstreet err: 2022cafe5635SKent Overstreet if (n3 == ERR_PTR(-EAGAIN) || 2023cafe5635SKent Overstreet n2 == ERR_PTR(-EAGAIN) || 2024cafe5635SKent Overstreet n1 == ERR_PTR(-EAGAIN)) 2025cafe5635SKent Overstreet return -EAGAIN; 2026cafe5635SKent Overstreet 2027cafe5635SKent Overstreet pr_warn("couldn't split"); 2028cafe5635SKent Overstreet return -ENOMEM; 2029cafe5635SKent Overstreet } 2030cafe5635SKent Overstreet 2031cafe5635SKent Overstreet static int bch_btree_insert_recurse(struct btree *b, struct btree_op *op, 2032cafe5635SKent Overstreet struct keylist *stack_keys) 2033cafe5635SKent Overstreet { 2034cafe5635SKent Overstreet if (b->level) { 2035cafe5635SKent Overstreet int ret; 2036cafe5635SKent Overstreet struct bkey *insert = op->keys.bottom; 2037cafe5635SKent Overstreet struct bkey *k = bch_next_recurse_key(b, &START_KEY(insert)); 2038cafe5635SKent Overstreet 2039cafe5635SKent Overstreet if (!k) { 2040cafe5635SKent Overstreet btree_bug(b, "no key to recurse on at level %i/%i", 2041cafe5635SKent Overstreet b->level, b->c->root->level); 2042cafe5635SKent Overstreet 2043cafe5635SKent Overstreet op->keys.top = op->keys.bottom; 2044cafe5635SKent Overstreet return -EIO; 2045cafe5635SKent Overstreet } 2046cafe5635SKent Overstreet 2047cafe5635SKent Overstreet if (bkey_cmp(insert, k) > 0) { 2048cafe5635SKent Overstreet unsigned i; 2049cafe5635SKent Overstreet 2050cafe5635SKent Overstreet if (op->type == BTREE_REPLACE) { 2051cafe5635SKent Overstreet __bkey_put(b->c, insert); 2052cafe5635SKent Overstreet op->keys.top = op->keys.bottom; 2053cafe5635SKent Overstreet op->insert_collision = true; 2054cafe5635SKent Overstreet return 0; 2055cafe5635SKent Overstreet } 2056cafe5635SKent Overstreet 2057cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(insert); i++) 2058cafe5635SKent Overstreet atomic_inc(&PTR_BUCKET(b->c, insert, i)->pin); 2059cafe5635SKent Overstreet 2060cafe5635SKent Overstreet bkey_copy(stack_keys->top, insert); 2061cafe5635SKent Overstreet 2062cafe5635SKent Overstreet bch_cut_back(k, insert); 2063cafe5635SKent Overstreet bch_cut_front(k, stack_keys->top); 2064cafe5635SKent Overstreet 2065cafe5635SKent Overstreet bch_keylist_push(stack_keys); 2066cafe5635SKent Overstreet } 2067cafe5635SKent Overstreet 2068cafe5635SKent Overstreet ret = btree(insert_recurse, k, b, op, stack_keys); 2069cafe5635SKent Overstreet if (ret) 2070cafe5635SKent Overstreet return ret; 2071cafe5635SKent Overstreet } 2072cafe5635SKent Overstreet 2073cafe5635SKent Overstreet if (!bch_keylist_empty(&op->keys)) { 2074cafe5635SKent Overstreet if (should_split(b)) { 2075cafe5635SKent Overstreet if (op->lock <= b->c->root->level) { 2076cafe5635SKent Overstreet BUG_ON(b->level); 2077cafe5635SKent Overstreet op->lock = b->c->root->level + 1; 2078cafe5635SKent Overstreet return -EINTR; 2079cafe5635SKent Overstreet } 2080cafe5635SKent Overstreet return btree_split(b, op); 2081cafe5635SKent Overstreet } 2082cafe5635SKent Overstreet 2083cafe5635SKent Overstreet BUG_ON(write_block(b) != b->sets[b->nsets].data); 2084cafe5635SKent Overstreet 2085cafe5635SKent Overstreet if (bch_btree_insert_keys(b, op)) 2086cafe5635SKent Overstreet bch_btree_write(b, false, op); 2087cafe5635SKent Overstreet } 2088cafe5635SKent Overstreet 2089cafe5635SKent Overstreet return 0; 2090cafe5635SKent Overstreet } 2091cafe5635SKent Overstreet 2092cafe5635SKent Overstreet int bch_btree_insert(struct btree_op *op, struct cache_set *c) 2093cafe5635SKent Overstreet { 2094cafe5635SKent Overstreet int ret = 0; 2095cafe5635SKent Overstreet struct keylist stack_keys; 2096cafe5635SKent Overstreet 2097cafe5635SKent Overstreet /* 2098cafe5635SKent Overstreet * Don't want to block with the btree locked unless we have to, 2099cafe5635SKent Overstreet * otherwise we get deadlocks with try_harder and between split/gc 2100cafe5635SKent Overstreet */ 2101cafe5635SKent Overstreet clear_closure_blocking(&op->cl); 2102cafe5635SKent Overstreet 2103cafe5635SKent Overstreet BUG_ON(bch_keylist_empty(&op->keys)); 2104cafe5635SKent Overstreet bch_keylist_copy(&stack_keys, &op->keys); 2105cafe5635SKent Overstreet bch_keylist_init(&op->keys); 2106cafe5635SKent Overstreet 2107cafe5635SKent Overstreet while (!bch_keylist_empty(&stack_keys) || 2108cafe5635SKent Overstreet !bch_keylist_empty(&op->keys)) { 2109cafe5635SKent Overstreet if (bch_keylist_empty(&op->keys)) { 2110cafe5635SKent Overstreet bch_keylist_add(&op->keys, 2111cafe5635SKent Overstreet bch_keylist_pop(&stack_keys)); 2112cafe5635SKent Overstreet op->lock = 0; 2113cafe5635SKent Overstreet } 2114cafe5635SKent Overstreet 2115cafe5635SKent Overstreet ret = btree_root(insert_recurse, c, op, &stack_keys); 2116cafe5635SKent Overstreet 2117cafe5635SKent Overstreet if (ret == -EAGAIN) { 2118cafe5635SKent Overstreet ret = 0; 2119cafe5635SKent Overstreet closure_sync(&op->cl); 2120cafe5635SKent Overstreet } else if (ret) { 2121cafe5635SKent Overstreet struct bkey *k; 2122cafe5635SKent Overstreet 2123cafe5635SKent Overstreet pr_err("error %i trying to insert key for %s", 2124cafe5635SKent Overstreet ret, op_type(op)); 2125cafe5635SKent Overstreet 2126cafe5635SKent Overstreet while ((k = bch_keylist_pop(&stack_keys) ?: 2127cafe5635SKent Overstreet bch_keylist_pop(&op->keys))) 2128cafe5635SKent Overstreet bkey_put(c, k, 0); 2129cafe5635SKent Overstreet } 2130cafe5635SKent Overstreet } 2131cafe5635SKent Overstreet 2132cafe5635SKent Overstreet bch_keylist_free(&stack_keys); 2133cafe5635SKent Overstreet 2134cafe5635SKent Overstreet if (op->journal) 2135cafe5635SKent Overstreet atomic_dec_bug(op->journal); 2136cafe5635SKent Overstreet op->journal = NULL; 2137cafe5635SKent Overstreet return ret; 2138cafe5635SKent Overstreet } 2139cafe5635SKent Overstreet 2140cafe5635SKent Overstreet void bch_btree_set_root(struct btree *b) 2141cafe5635SKent Overstreet { 2142cafe5635SKent Overstreet unsigned i; 2143cafe5635SKent Overstreet 2144cafe5635SKent Overstreet BUG_ON(!b->written); 2145cafe5635SKent Overstreet 2146cafe5635SKent Overstreet for (i = 0; i < KEY_PTRS(&b->key); i++) 2147cafe5635SKent Overstreet BUG_ON(PTR_BUCKET(b->c, &b->key, i)->prio != BTREE_PRIO); 2148cafe5635SKent Overstreet 2149cafe5635SKent Overstreet mutex_lock(&b->c->bucket_lock); 2150cafe5635SKent Overstreet list_del_init(&b->list); 2151cafe5635SKent Overstreet mutex_unlock(&b->c->bucket_lock); 2152cafe5635SKent Overstreet 2153cafe5635SKent Overstreet b->c->root = b; 2154cafe5635SKent Overstreet __bkey_put(b->c, &b->key); 2155cafe5635SKent Overstreet 2156cafe5635SKent Overstreet bch_journal_meta(b->c, NULL); 2157cafe5635SKent Overstreet pr_debug("%s for %pf", pbtree(b), __builtin_return_address(0)); 2158cafe5635SKent Overstreet } 2159cafe5635SKent Overstreet 2160cafe5635SKent Overstreet /* Cache lookup */ 2161cafe5635SKent Overstreet 2162cafe5635SKent Overstreet static int submit_partial_cache_miss(struct btree *b, struct btree_op *op, 2163cafe5635SKent Overstreet struct bkey *k) 2164cafe5635SKent Overstreet { 2165cafe5635SKent Overstreet struct search *s = container_of(op, struct search, op); 2166cafe5635SKent Overstreet struct bio *bio = &s->bio.bio; 2167cafe5635SKent Overstreet int ret = 0; 2168cafe5635SKent Overstreet 2169cafe5635SKent Overstreet while (!ret && 2170cafe5635SKent Overstreet !op->lookup_done) { 2171cafe5635SKent Overstreet unsigned sectors = INT_MAX; 2172cafe5635SKent Overstreet 2173cafe5635SKent Overstreet if (KEY_INODE(k) == op->inode) { 2174cafe5635SKent Overstreet if (KEY_START(k) <= bio->bi_sector) 2175cafe5635SKent Overstreet break; 2176cafe5635SKent Overstreet 2177cafe5635SKent Overstreet sectors = min_t(uint64_t, sectors, 2178cafe5635SKent Overstreet KEY_START(k) - bio->bi_sector); 2179cafe5635SKent Overstreet } 2180cafe5635SKent Overstreet 2181cafe5635SKent Overstreet ret = s->d->cache_miss(b, s, bio, sectors); 2182cafe5635SKent Overstreet } 2183cafe5635SKent Overstreet 2184cafe5635SKent Overstreet return ret; 2185cafe5635SKent Overstreet } 2186cafe5635SKent Overstreet 2187cafe5635SKent Overstreet /* 2188cafe5635SKent Overstreet * Read from a single key, handling the initial cache miss if the key starts in 2189cafe5635SKent Overstreet * the middle of the bio 2190cafe5635SKent Overstreet */ 2191cafe5635SKent Overstreet static int submit_partial_cache_hit(struct btree *b, struct btree_op *op, 2192cafe5635SKent Overstreet struct bkey *k) 2193cafe5635SKent Overstreet { 2194cafe5635SKent Overstreet struct search *s = container_of(op, struct search, op); 2195cafe5635SKent Overstreet struct bio *bio = &s->bio.bio; 2196cafe5635SKent Overstreet unsigned ptr; 2197cafe5635SKent Overstreet struct bio *n; 2198cafe5635SKent Overstreet 2199cafe5635SKent Overstreet int ret = submit_partial_cache_miss(b, op, k); 2200cafe5635SKent Overstreet if (ret || op->lookup_done) 2201cafe5635SKent Overstreet return ret; 2202cafe5635SKent Overstreet 2203cafe5635SKent Overstreet /* XXX: figure out best pointer - for multiple cache devices */ 2204cafe5635SKent Overstreet ptr = 0; 2205cafe5635SKent Overstreet 2206cafe5635SKent Overstreet PTR_BUCKET(b->c, k, ptr)->prio = INITIAL_PRIO; 2207cafe5635SKent Overstreet 2208cafe5635SKent Overstreet while (!op->lookup_done && 2209cafe5635SKent Overstreet KEY_INODE(k) == op->inode && 2210cafe5635SKent Overstreet bio->bi_sector < KEY_OFFSET(k)) { 2211cafe5635SKent Overstreet struct bkey *bio_key; 2212cafe5635SKent Overstreet sector_t sector = PTR_OFFSET(k, ptr) + 2213cafe5635SKent Overstreet (bio->bi_sector - KEY_START(k)); 2214cafe5635SKent Overstreet unsigned sectors = min_t(uint64_t, INT_MAX, 2215cafe5635SKent Overstreet KEY_OFFSET(k) - bio->bi_sector); 2216cafe5635SKent Overstreet 2217cafe5635SKent Overstreet n = bch_bio_split(bio, sectors, GFP_NOIO, s->d->bio_split); 2218cafe5635SKent Overstreet if (!n) 2219cafe5635SKent Overstreet return -EAGAIN; 2220cafe5635SKent Overstreet 2221cafe5635SKent Overstreet if (n == bio) 2222cafe5635SKent Overstreet op->lookup_done = true; 2223cafe5635SKent Overstreet 2224cafe5635SKent Overstreet bio_key = &container_of(n, struct bbio, bio)->key; 2225cafe5635SKent Overstreet 2226cafe5635SKent Overstreet /* 2227cafe5635SKent Overstreet * The bucket we're reading from might be reused while our bio 2228cafe5635SKent Overstreet * is in flight, and we could then end up reading the wrong 2229cafe5635SKent Overstreet * data. 2230cafe5635SKent Overstreet * 2231cafe5635SKent Overstreet * We guard against this by checking (in cache_read_endio()) if 2232cafe5635SKent Overstreet * the pointer is stale again; if so, we treat it as an error 2233cafe5635SKent Overstreet * and reread from the backing device (but we don't pass that 2234cafe5635SKent Overstreet * error up anywhere). 2235cafe5635SKent Overstreet */ 2236cafe5635SKent Overstreet 2237cafe5635SKent Overstreet bch_bkey_copy_single_ptr(bio_key, k, ptr); 2238cafe5635SKent Overstreet SET_PTR_OFFSET(bio_key, 0, sector); 2239cafe5635SKent Overstreet 2240cafe5635SKent Overstreet n->bi_end_io = bch_cache_read_endio; 2241cafe5635SKent Overstreet n->bi_private = &s->cl; 2242cafe5635SKent Overstreet 2243cafe5635SKent Overstreet trace_bcache_cache_hit(n); 2244cafe5635SKent Overstreet __bch_submit_bbio(n, b->c); 2245cafe5635SKent Overstreet } 2246cafe5635SKent Overstreet 2247cafe5635SKent Overstreet return 0; 2248cafe5635SKent Overstreet } 2249cafe5635SKent Overstreet 2250cafe5635SKent Overstreet int bch_btree_search_recurse(struct btree *b, struct btree_op *op) 2251cafe5635SKent Overstreet { 2252cafe5635SKent Overstreet struct search *s = container_of(op, struct search, op); 2253cafe5635SKent Overstreet struct bio *bio = &s->bio.bio; 2254cafe5635SKent Overstreet 2255cafe5635SKent Overstreet int ret = 0; 2256cafe5635SKent Overstreet struct bkey *k; 2257cafe5635SKent Overstreet struct btree_iter iter; 2258cafe5635SKent Overstreet bch_btree_iter_init(b, &iter, &KEY(op->inode, bio->bi_sector, 0)); 2259cafe5635SKent Overstreet 2260cafe5635SKent Overstreet pr_debug("at %s searching for %u:%llu", pbtree(b), op->inode, 2261cafe5635SKent Overstreet (uint64_t) bio->bi_sector); 2262cafe5635SKent Overstreet 2263cafe5635SKent Overstreet do { 2264cafe5635SKent Overstreet k = bch_btree_iter_next_filter(&iter, b, bch_ptr_bad); 2265cafe5635SKent Overstreet if (!k) { 2266cafe5635SKent Overstreet /* 2267cafe5635SKent Overstreet * b->key would be exactly what we want, except that 2268cafe5635SKent Overstreet * pointers to btree nodes have nonzero size - we 2269cafe5635SKent Overstreet * wouldn't go far enough 2270cafe5635SKent Overstreet */ 2271cafe5635SKent Overstreet 2272cafe5635SKent Overstreet ret = submit_partial_cache_miss(b, op, 2273cafe5635SKent Overstreet &KEY(KEY_INODE(&b->key), 2274cafe5635SKent Overstreet KEY_OFFSET(&b->key), 0)); 2275cafe5635SKent Overstreet break; 2276cafe5635SKent Overstreet } 2277cafe5635SKent Overstreet 2278cafe5635SKent Overstreet ret = b->level 2279cafe5635SKent Overstreet ? btree(search_recurse, k, b, op) 2280cafe5635SKent Overstreet : submit_partial_cache_hit(b, op, k); 2281cafe5635SKent Overstreet } while (!ret && 2282cafe5635SKent Overstreet !op->lookup_done); 2283cafe5635SKent Overstreet 2284cafe5635SKent Overstreet return ret; 2285cafe5635SKent Overstreet } 2286cafe5635SKent Overstreet 2287cafe5635SKent Overstreet /* Keybuf code */ 2288cafe5635SKent Overstreet 2289cafe5635SKent Overstreet static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r) 2290cafe5635SKent Overstreet { 2291cafe5635SKent Overstreet /* Overlapping keys compare equal */ 2292cafe5635SKent Overstreet if (bkey_cmp(&l->key, &START_KEY(&r->key)) <= 0) 2293cafe5635SKent Overstreet return -1; 2294cafe5635SKent Overstreet if (bkey_cmp(&START_KEY(&l->key), &r->key) >= 0) 2295cafe5635SKent Overstreet return 1; 2296cafe5635SKent Overstreet return 0; 2297cafe5635SKent Overstreet } 2298cafe5635SKent Overstreet 2299cafe5635SKent Overstreet static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l, 2300cafe5635SKent Overstreet struct keybuf_key *r) 2301cafe5635SKent Overstreet { 2302cafe5635SKent Overstreet return clamp_t(int64_t, bkey_cmp(&l->key, &r->key), -1, 1); 2303cafe5635SKent Overstreet } 2304cafe5635SKent Overstreet 2305cafe5635SKent Overstreet static int bch_btree_refill_keybuf(struct btree *b, struct btree_op *op, 2306cafe5635SKent Overstreet struct keybuf *buf, struct bkey *end) 2307cafe5635SKent Overstreet { 2308cafe5635SKent Overstreet struct btree_iter iter; 2309cafe5635SKent Overstreet bch_btree_iter_init(b, &iter, &buf->last_scanned); 2310cafe5635SKent Overstreet 2311cafe5635SKent Overstreet while (!array_freelist_empty(&buf->freelist)) { 2312cafe5635SKent Overstreet struct bkey *k = bch_btree_iter_next_filter(&iter, b, 2313cafe5635SKent Overstreet bch_ptr_bad); 2314cafe5635SKent Overstreet 2315cafe5635SKent Overstreet if (!b->level) { 2316cafe5635SKent Overstreet if (!k) { 2317cafe5635SKent Overstreet buf->last_scanned = b->key; 2318cafe5635SKent Overstreet break; 2319cafe5635SKent Overstreet } 2320cafe5635SKent Overstreet 2321cafe5635SKent Overstreet buf->last_scanned = *k; 2322cafe5635SKent Overstreet if (bkey_cmp(&buf->last_scanned, end) >= 0) 2323cafe5635SKent Overstreet break; 2324cafe5635SKent Overstreet 2325cafe5635SKent Overstreet if (buf->key_predicate(buf, k)) { 2326cafe5635SKent Overstreet struct keybuf_key *w; 2327cafe5635SKent Overstreet 2328cafe5635SKent Overstreet pr_debug("%s", pkey(k)); 2329cafe5635SKent Overstreet 2330cafe5635SKent Overstreet spin_lock(&buf->lock); 2331cafe5635SKent Overstreet 2332cafe5635SKent Overstreet w = array_alloc(&buf->freelist); 2333cafe5635SKent Overstreet 2334cafe5635SKent Overstreet w->private = NULL; 2335cafe5635SKent Overstreet bkey_copy(&w->key, k); 2336cafe5635SKent Overstreet 2337cafe5635SKent Overstreet if (RB_INSERT(&buf->keys, w, node, keybuf_cmp)) 2338cafe5635SKent Overstreet array_free(&buf->freelist, w); 2339cafe5635SKent Overstreet 2340cafe5635SKent Overstreet spin_unlock(&buf->lock); 2341cafe5635SKent Overstreet } 2342cafe5635SKent Overstreet } else { 2343cafe5635SKent Overstreet if (!k) 2344cafe5635SKent Overstreet break; 2345cafe5635SKent Overstreet 2346cafe5635SKent Overstreet btree(refill_keybuf, k, b, op, buf, end); 2347cafe5635SKent Overstreet /* 2348cafe5635SKent Overstreet * Might get an error here, but can't really do anything 2349cafe5635SKent Overstreet * and it'll get logged elsewhere. Just read what we 2350cafe5635SKent Overstreet * can. 2351cafe5635SKent Overstreet */ 2352cafe5635SKent Overstreet 2353cafe5635SKent Overstreet if (bkey_cmp(&buf->last_scanned, end) >= 0) 2354cafe5635SKent Overstreet break; 2355cafe5635SKent Overstreet 2356cafe5635SKent Overstreet cond_resched(); 2357cafe5635SKent Overstreet } 2358cafe5635SKent Overstreet } 2359cafe5635SKent Overstreet 2360cafe5635SKent Overstreet return 0; 2361cafe5635SKent Overstreet } 2362cafe5635SKent Overstreet 2363cafe5635SKent Overstreet void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf, 2364cafe5635SKent Overstreet struct bkey *end) 2365cafe5635SKent Overstreet { 2366cafe5635SKent Overstreet struct bkey start = buf->last_scanned; 2367cafe5635SKent Overstreet struct btree_op op; 2368cafe5635SKent Overstreet bch_btree_op_init_stack(&op); 2369cafe5635SKent Overstreet 2370cafe5635SKent Overstreet cond_resched(); 2371cafe5635SKent Overstreet 2372cafe5635SKent Overstreet btree_root(refill_keybuf, c, &op, buf, end); 2373cafe5635SKent Overstreet closure_sync(&op.cl); 2374cafe5635SKent Overstreet 2375cafe5635SKent Overstreet pr_debug("found %s keys from %llu:%llu to %llu:%llu", 2376cafe5635SKent Overstreet RB_EMPTY_ROOT(&buf->keys) ? "no" : 2377cafe5635SKent Overstreet array_freelist_empty(&buf->freelist) ? "some" : "a few", 2378cafe5635SKent Overstreet KEY_INODE(&start), KEY_OFFSET(&start), 2379cafe5635SKent Overstreet KEY_INODE(&buf->last_scanned), KEY_OFFSET(&buf->last_scanned)); 2380cafe5635SKent Overstreet 2381cafe5635SKent Overstreet spin_lock(&buf->lock); 2382cafe5635SKent Overstreet 2383cafe5635SKent Overstreet if (!RB_EMPTY_ROOT(&buf->keys)) { 2384cafe5635SKent Overstreet struct keybuf_key *w; 2385cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2386cafe5635SKent Overstreet buf->start = START_KEY(&w->key); 2387cafe5635SKent Overstreet 2388cafe5635SKent Overstreet w = RB_LAST(&buf->keys, struct keybuf_key, node); 2389cafe5635SKent Overstreet buf->end = w->key; 2390cafe5635SKent Overstreet } else { 2391cafe5635SKent Overstreet buf->start = MAX_KEY; 2392cafe5635SKent Overstreet buf->end = MAX_KEY; 2393cafe5635SKent Overstreet } 2394cafe5635SKent Overstreet 2395cafe5635SKent Overstreet spin_unlock(&buf->lock); 2396cafe5635SKent Overstreet } 2397cafe5635SKent Overstreet 2398cafe5635SKent Overstreet static void __bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2399cafe5635SKent Overstreet { 2400cafe5635SKent Overstreet rb_erase(&w->node, &buf->keys); 2401cafe5635SKent Overstreet array_free(&buf->freelist, w); 2402cafe5635SKent Overstreet } 2403cafe5635SKent Overstreet 2404cafe5635SKent Overstreet void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w) 2405cafe5635SKent Overstreet { 2406cafe5635SKent Overstreet spin_lock(&buf->lock); 2407cafe5635SKent Overstreet __bch_keybuf_del(buf, w); 2408cafe5635SKent Overstreet spin_unlock(&buf->lock); 2409cafe5635SKent Overstreet } 2410cafe5635SKent Overstreet 2411cafe5635SKent Overstreet bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start, 2412cafe5635SKent Overstreet struct bkey *end) 2413cafe5635SKent Overstreet { 2414cafe5635SKent Overstreet bool ret = false; 2415cafe5635SKent Overstreet struct keybuf_key *p, *w, s; 2416cafe5635SKent Overstreet s.key = *start; 2417cafe5635SKent Overstreet 2418cafe5635SKent Overstreet if (bkey_cmp(end, &buf->start) <= 0 || 2419cafe5635SKent Overstreet bkey_cmp(start, &buf->end) >= 0) 2420cafe5635SKent Overstreet return false; 2421cafe5635SKent Overstreet 2422cafe5635SKent Overstreet spin_lock(&buf->lock); 2423cafe5635SKent Overstreet w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp); 2424cafe5635SKent Overstreet 2425cafe5635SKent Overstreet while (w && bkey_cmp(&START_KEY(&w->key), end) < 0) { 2426cafe5635SKent Overstreet p = w; 2427cafe5635SKent Overstreet w = RB_NEXT(w, node); 2428cafe5635SKent Overstreet 2429cafe5635SKent Overstreet if (p->private) 2430cafe5635SKent Overstreet ret = true; 2431cafe5635SKent Overstreet else 2432cafe5635SKent Overstreet __bch_keybuf_del(buf, p); 2433cafe5635SKent Overstreet } 2434cafe5635SKent Overstreet 2435cafe5635SKent Overstreet spin_unlock(&buf->lock); 2436cafe5635SKent Overstreet return ret; 2437cafe5635SKent Overstreet } 2438cafe5635SKent Overstreet 2439cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next(struct keybuf *buf) 2440cafe5635SKent Overstreet { 2441cafe5635SKent Overstreet struct keybuf_key *w; 2442cafe5635SKent Overstreet spin_lock(&buf->lock); 2443cafe5635SKent Overstreet 2444cafe5635SKent Overstreet w = RB_FIRST(&buf->keys, struct keybuf_key, node); 2445cafe5635SKent Overstreet 2446cafe5635SKent Overstreet while (w && w->private) 2447cafe5635SKent Overstreet w = RB_NEXT(w, node); 2448cafe5635SKent Overstreet 2449cafe5635SKent Overstreet if (w) 2450cafe5635SKent Overstreet w->private = ERR_PTR(-EINTR); 2451cafe5635SKent Overstreet 2452cafe5635SKent Overstreet spin_unlock(&buf->lock); 2453cafe5635SKent Overstreet return w; 2454cafe5635SKent Overstreet } 2455cafe5635SKent Overstreet 2456cafe5635SKent Overstreet struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c, 2457cafe5635SKent Overstreet struct keybuf *buf, 2458cafe5635SKent Overstreet struct bkey *end) 2459cafe5635SKent Overstreet { 2460cafe5635SKent Overstreet struct keybuf_key *ret; 2461cafe5635SKent Overstreet 2462cafe5635SKent Overstreet while (1) { 2463cafe5635SKent Overstreet ret = bch_keybuf_next(buf); 2464cafe5635SKent Overstreet if (ret) 2465cafe5635SKent Overstreet break; 2466cafe5635SKent Overstreet 2467cafe5635SKent Overstreet if (bkey_cmp(&buf->last_scanned, end) >= 0) { 2468cafe5635SKent Overstreet pr_debug("scan finished"); 2469cafe5635SKent Overstreet break; 2470cafe5635SKent Overstreet } 2471cafe5635SKent Overstreet 2472cafe5635SKent Overstreet bch_refill_keybuf(c, buf, end); 2473cafe5635SKent Overstreet } 2474cafe5635SKent Overstreet 2475cafe5635SKent Overstreet return ret; 2476cafe5635SKent Overstreet } 2477cafe5635SKent Overstreet 2478cafe5635SKent Overstreet void bch_keybuf_init(struct keybuf *buf, keybuf_pred_fn *fn) 2479cafe5635SKent Overstreet { 2480cafe5635SKent Overstreet buf->key_predicate = fn; 2481cafe5635SKent Overstreet buf->last_scanned = MAX_KEY; 2482cafe5635SKent Overstreet buf->keys = RB_ROOT; 2483cafe5635SKent Overstreet 2484cafe5635SKent Overstreet spin_lock_init(&buf->lock); 2485cafe5635SKent Overstreet array_allocator_init(&buf->freelist); 2486cafe5635SKent Overstreet } 2487cafe5635SKent Overstreet 2488cafe5635SKent Overstreet void bch_btree_exit(void) 2489cafe5635SKent Overstreet { 2490cafe5635SKent Overstreet if (btree_io_wq) 2491cafe5635SKent Overstreet destroy_workqueue(btree_io_wq); 2492cafe5635SKent Overstreet if (bch_gc_wq) 2493cafe5635SKent Overstreet destroy_workqueue(bch_gc_wq); 2494cafe5635SKent Overstreet } 2495cafe5635SKent Overstreet 2496cafe5635SKent Overstreet int __init bch_btree_init(void) 2497cafe5635SKent Overstreet { 2498cafe5635SKent Overstreet if (!(bch_gc_wq = create_singlethread_workqueue("bch_btree_gc")) || 2499cafe5635SKent Overstreet !(btree_io_wq = create_singlethread_workqueue("bch_btree_io"))) 2500cafe5635SKent Overstreet return -ENOMEM; 2501cafe5635SKent Overstreet 2502cafe5635SKent Overstreet return 0; 2503cafe5635SKent Overstreet } 2504