2845 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>4 *5 * Uses a block device as cache for other block devices; optimized for SSDs.6 * All allocation is done in buckets, which should match the erase block size7 * of the device.8 *9 * Buckets containing cached data are kept on a heap sorted by priority;10 * bucket priority is increased on cache hit, and periodically all the buckets11 * on the heap have their priority scaled down. This currently is just used as12 * an LRU but in the future should allow for more intelligent heuristics.13 *14 * Buckets have an 8 bit counter; freeing is accomplished by incrementing the15 * counter. Garbage collection is used to remove stale pointers.16 *17 * Indexing is done via a btree; nodes are not necessarily fully sorted, rather18 * as keys are inserted we only sort the pages that have not yet been written.19 * When garbage collection is run, we resort the entire node.20 *21 * All configuration is done via sysfs; see Documentation/admin-guide/bcache.rst.22 */23 24#include "bcache.h"25#include "btree.h"26#include "debug.h"27#include "extents.h"28 29#include <linux/slab.h>30#include <linux/bitops.h>31#include <linux/hash.h>32#include <linux/kthread.h>33#include <linux/prefetch.h>34#include <linux/random.h>35#include <linux/rcupdate.h>36#include <linux/sched/clock.h>37#include <linux/rculist.h>38#include <linux/delay.h>39#include <trace/events/bcache.h>40 41/*42 * Todo:43 * register_bcache: Return errors out to userspace correctly44 *45 * Writeback: don't undirty key until after a cache flush46 *47 * Create an iterator for key pointers48 *49 * On btree write error, mark bucket such that it won't be freed from the cache50 *51 * Journalling:52 * Check for bad keys in replay53 * Propagate barriers54 * Refcount journal entries in journal_replay55 *56 * Garbage collection:57 * Finish incremental gc58 * Gc should free old UUIDs, data for invalid UUIDs59 *60 * Provide a way to list backing device UUIDs we have data cached for, and61 * probably how long it's been since we've seen them, and a way to invalidate62 * dirty data for devices that will never be attached again63 *64 * Keep 1 min/5 min/15 min statistics of how busy a block device has been, so65 * that based on that and how much dirty data we have we can keep writeback66 * from being starved67 *68 * Add a tracepoint or somesuch to watch for writeback starvation69 *70 * When btree depth > 1 and splitting an interior node, we have to make sure71 * alloc_bucket() cannot fail. This should be true but is not completely72 * obvious.73 *74 * Plugging?75 *76 * If data write is less than hard sector size of ssd, round up offset in open77 * bucket to the next whole sector78 *79 * Superblock needs to be fleshed out for multiple cache devices80 *81 * Add a sysfs tunable for the number of writeback IOs in flight82 *83 * Add a sysfs tunable for the number of open data buckets84 *85 * IO tracking: Can we track when one process is doing io on behalf of another?86 * IO tracking: Don't use just an average, weigh more recent stuff higher87 *88 * Test module load/unload89 */90 91#define MAX_NEED_GC 6492#define MAX_SAVE_PRIO 7293#define MAX_GC_TIMES 10094#define MIN_GC_NODES 10095#define GC_SLEEP_MS 10096 97#define PTR_DIRTY_BIT (((uint64_t) 1 << 36))98 99#define PTR_HASH(c, k) \100 (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0))101 102static struct workqueue_struct *btree_io_wq;103 104#define insert_lock(s, b) ((b)->level <= (s)->lock)105 106 107static inline struct bset *write_block(struct btree *b)108{109 return ((void *) btree_bset_first(b)) + b->written * block_bytes(b->c->cache);110}111 112static void bch_btree_init_next(struct btree *b)113{114 /* If not a leaf node, always sort */115 if (b->level && b->keys.nsets)116 bch_btree_sort(&b->keys, &b->c->sort);117 else118 bch_btree_sort_lazy(&b->keys, &b->c->sort);119 120 if (b->written < btree_blocks(b))121 bch_bset_init_next(&b->keys, write_block(b),122 bset_magic(&b->c->cache->sb));123 124}125 126/* Btree key manipulation */127 128void bkey_put(struct cache_set *c, struct bkey *k)129{130 unsigned int i;131 132 for (i = 0; i < KEY_PTRS(k); i++)133 if (ptr_available(c, k, i))134 atomic_dec_bug(&PTR_BUCKET(c, k, i)->pin);135}136 137/* Btree IO */138 139static uint64_t btree_csum_set(struct btree *b, struct bset *i)140{141 uint64_t crc = b->key.ptr[0];142 void *data = (void *) i + 8, *end = bset_bkey_last(i);143 144 crc = crc64_be(crc, data, end - data);145 return crc ^ 0xffffffffffffffffULL;146}147 148void bch_btree_node_read_done(struct btree *b)149{150 const char *err = "bad btree header";151 struct bset *i = btree_bset_first(b);152 struct btree_iter iter;153 154 /*155 * c->fill_iter can allocate an iterator with more memory space156 * than static MAX_BSETS.157 * See the comment arount cache_set->fill_iter.158 */159 iter.heap.data = mempool_alloc(&b->c->fill_iter, GFP_NOIO);160 iter.heap.size = b->c->cache->sb.bucket_size / b->c->cache->sb.block_size;161 iter.heap.nr = 0;162 163#ifdef CONFIG_BCACHE_DEBUG164 iter.b = &b->keys;165#endif166 167 if (!i->seq)168 goto err;169 170 for (;171 b->written < btree_blocks(b) && i->seq == b->keys.set[0].data->seq;172 i = write_block(b)) {173 err = "unsupported bset version";174 if (i->version > BCACHE_BSET_VERSION)175 goto err;176 177 err = "bad btree header";178 if (b->written + set_blocks(i, block_bytes(b->c->cache)) >179 btree_blocks(b))180 goto err;181 182 err = "bad magic";183 if (i->magic != bset_magic(&b->c->cache->sb))184 goto err;185 186 err = "bad checksum";187 switch (i->version) {188 case 0:189 if (i->csum != csum_set(i))190 goto err;191 break;192 case BCACHE_BSET_VERSION:193 if (i->csum != btree_csum_set(b, i))194 goto err;195 break;196 }197 198 err = "empty set";199 if (i != b->keys.set[0].data && !i->keys)200 goto err;201 202 bch_btree_iter_push(&iter, i->start, bset_bkey_last(i));203 204 b->written += set_blocks(i, block_bytes(b->c->cache));205 }206 207 err = "corrupted btree";208 for (i = write_block(b);209 bset_sector_offset(&b->keys, i) < KEY_SIZE(&b->key);210 i = ((void *) i) + block_bytes(b->c->cache))211 if (i->seq == b->keys.set[0].data->seq)212 goto err;213 214 bch_btree_sort_and_fix_extents(&b->keys, &iter, &b->c->sort);215 216 i = b->keys.set[0].data;217 err = "short btree key";218 if (b->keys.set[0].size &&219 bkey_cmp(&b->key, &b->keys.set[0].end) < 0)220 goto err;221 222 if (b->written < btree_blocks(b))223 bch_bset_init_next(&b->keys, write_block(b),224 bset_magic(&b->c->cache->sb));225out:226 mempool_free(iter.heap.data, &b->c->fill_iter);227 return;228err:229 set_btree_node_io_error(b);230 bch_cache_set_error(b->c, "%s at bucket %zu, block %u, %u keys",231 err, PTR_BUCKET_NR(b->c, &b->key, 0),232 bset_block_offset(b, i), i->keys);233 goto out;234}235 236static void btree_node_read_endio(struct bio *bio)237{238 struct closure *cl = bio->bi_private;239 240 closure_put(cl);241}242 243static void bch_btree_node_read(struct btree *b)244{245 uint64_t start_time = local_clock();246 struct closure cl;247 struct bio *bio;248 249 trace_bcache_btree_read(b);250 251 closure_init_stack(&cl);252 253 bio = bch_bbio_alloc(b->c);254 bio->bi_iter.bi_size = KEY_SIZE(&b->key) << 9;255 bio->bi_end_io = btree_node_read_endio;256 bio->bi_private = &cl;257 bio->bi_opf = REQ_OP_READ | REQ_META;258 259 bch_bio_map(bio, b->keys.set[0].data);260 261 bch_submit_bbio(bio, b->c, &b->key, 0);262 closure_sync(&cl);263 264 if (bio->bi_status)265 set_btree_node_io_error(b);266 267 bch_bbio_free(bio, b->c);268 269 if (btree_node_io_error(b))270 goto err;271 272 bch_btree_node_read_done(b);273 bch_time_stats_update(&b->c->btree_read_time, start_time);274 275 return;276err:277 bch_cache_set_error(b->c, "io error reading bucket %zu",278 PTR_BUCKET_NR(b->c, &b->key, 0));279}280 281static void btree_complete_write(struct btree *b, struct btree_write *w)282{283 if (w->prio_blocked &&284 !atomic_sub_return(w->prio_blocked, &b->c->prio_blocked))285 wake_up_allocators(b->c);286 287 if (w->journal) {288 atomic_dec_bug(w->journal);289 __closure_wake_up(&b->c->journal.wait);290 }291 292 w->prio_blocked = 0;293 w->journal = NULL;294}295 296static CLOSURE_CALLBACK(btree_node_write_unlock)297{298 closure_type(b, struct btree, io);299 300 up(&b->io_mutex);301}302 303static CLOSURE_CALLBACK(__btree_node_write_done)304{305 closure_type(b, struct btree, io);306 struct btree_write *w = btree_prev_write(b);307 308 bch_bbio_free(b->bio, b->c);309 b->bio = NULL;310 btree_complete_write(b, w);311 312 if (btree_node_dirty(b))313 queue_delayed_work(btree_io_wq, &b->work, 30 * HZ);314 315 closure_return_with_destructor(cl, btree_node_write_unlock);316}317 318static CLOSURE_CALLBACK(btree_node_write_done)319{320 closure_type(b, struct btree, io);321 322 bio_free_pages(b->bio);323 __btree_node_write_done(&cl->work);324}325 326static void btree_node_write_endio(struct bio *bio)327{328 struct closure *cl = bio->bi_private;329 struct btree *b = container_of(cl, struct btree, io);330 331 if (bio->bi_status)332 set_btree_node_io_error(b);333 334 bch_bbio_count_io_errors(b->c, bio, bio->bi_status, "writing btree");335 closure_put(cl);336}337 338static void do_btree_node_write(struct btree *b)339{340 struct closure *cl = &b->io;341 struct bset *i = btree_bset_last(b);342 BKEY_PADDED(key) k;343 344 i->version = BCACHE_BSET_VERSION;345 i->csum = btree_csum_set(b, i);346 347 BUG_ON(b->bio);348 b->bio = bch_bbio_alloc(b->c);349 350 b->bio->bi_end_io = btree_node_write_endio;351 b->bio->bi_private = cl;352 b->bio->bi_iter.bi_size = roundup(set_bytes(i), block_bytes(b->c->cache));353 b->bio->bi_opf = REQ_OP_WRITE | REQ_META | REQ_FUA;354 bch_bio_map(b->bio, i);355 356 /*357 * If we're appending to a leaf node, we don't technically need FUA -358 * this write just needs to be persisted before the next journal write,359 * which will be marked FLUSH|FUA.360 *361 * Similarly if we're writing a new btree root - the pointer is going to362 * be in the next journal entry.363 *364 * But if we're writing a new btree node (that isn't a root) or365 * appending to a non leaf btree node, we need either FUA or a flush366 * when we write the parent with the new pointer. FUA is cheaper than a367 * flush, and writes appending to leaf nodes aren't blocking anything so368 * just make all btree node writes FUA to keep things sane.369 */370 371 bkey_copy(&k.key, &b->key);372 SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) +373 bset_sector_offset(&b->keys, i));374 375 if (!bch_bio_alloc_pages(b->bio, __GFP_NOWARN|GFP_NOWAIT)) {376 struct bio_vec *bv;377 void *addr = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1));378 struct bvec_iter_all iter_all;379 380 bio_for_each_segment_all(bv, b->bio, iter_all) {381 memcpy(page_address(bv->bv_page), addr, PAGE_SIZE);382 addr += PAGE_SIZE;383 }384 385 bch_submit_bbio(b->bio, b->c, &k.key, 0);386 387 continue_at(cl, btree_node_write_done, NULL);388 } else {389 /*390 * No problem for multipage bvec since the bio is391 * just allocated392 */393 b->bio->bi_vcnt = 0;394 bch_bio_map(b->bio, i);395 396 bch_submit_bbio(b->bio, b->c, &k.key, 0);397 398 closure_sync(cl);399 continue_at_nobarrier(cl, __btree_node_write_done, NULL);400 }401}402 403void __bch_btree_node_write(struct btree *b, struct closure *parent)404{405 struct bset *i = btree_bset_last(b);406 407 lockdep_assert_held(&b->write_lock);408 409 trace_bcache_btree_write(b);410 411 BUG_ON(current->bio_list);412 BUG_ON(b->written >= btree_blocks(b));413 BUG_ON(b->written && !i->keys);414 BUG_ON(btree_bset_first(b)->seq != i->seq);415 bch_check_keys(&b->keys, "writing");416 417 cancel_delayed_work(&b->work);418 419 /* If caller isn't waiting for write, parent refcount is cache set */420 down(&b->io_mutex);421 closure_init(&b->io, parent ?: &b->c->cl);422 423 clear_bit(BTREE_NODE_dirty, &b->flags);424 change_bit(BTREE_NODE_write_idx, &b->flags);425 426 do_btree_node_write(b);427 428 atomic_long_add(set_blocks(i, block_bytes(b->c->cache)) * b->c->cache->sb.block_size,429 &b->c->cache->btree_sectors_written);430 431 b->written += set_blocks(i, block_bytes(b->c->cache));432}433 434void bch_btree_node_write(struct btree *b, struct closure *parent)435{436 unsigned int nsets = b->keys.nsets;437 438 lockdep_assert_held(&b->lock);439 440 __bch_btree_node_write(b, parent);441 442 /*443 * do verify if there was more than one set initially (i.e. we did a444 * sort) and we sorted down to a single set:445 */446 if (nsets && !b->keys.nsets)447 bch_btree_verify(b);448 449 bch_btree_init_next(b);450}451 452static void bch_btree_node_write_sync(struct btree *b)453{454 struct closure cl;455 456 closure_init_stack(&cl);457 458 mutex_lock(&b->write_lock);459 bch_btree_node_write(b, &cl);460 mutex_unlock(&b->write_lock);461 462 closure_sync(&cl);463}464 465static void btree_node_write_work(struct work_struct *w)466{467 struct btree *b = container_of(to_delayed_work(w), struct btree, work);468 469 mutex_lock(&b->write_lock);470 if (btree_node_dirty(b))471 __bch_btree_node_write(b, NULL);472 mutex_unlock(&b->write_lock);473}474 475static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref)476{477 struct bset *i = btree_bset_last(b);478 struct btree_write *w = btree_current_write(b);479 480 lockdep_assert_held(&b->write_lock);481 482 BUG_ON(!b->written);483 BUG_ON(!i->keys);484 485 if (!btree_node_dirty(b))486 queue_delayed_work(btree_io_wq, &b->work, 30 * HZ);487 488 set_btree_node_dirty(b);489 490 /*491 * w->journal is always the oldest journal pin of all bkeys492 * in the leaf node, to make sure the oldest jset seq won't493 * be increased before this btree node is flushed.494 */495 if (journal_ref) {496 if (w->journal &&497 journal_pin_cmp(b->c, w->journal, journal_ref)) {498 atomic_dec_bug(w->journal);499 w->journal = NULL;500 }501 502 if (!w->journal) {503 w->journal = journal_ref;504 atomic_inc(w->journal);505 }506 }507 508 /* Force write if set is too big */509 if (set_bytes(i) > PAGE_SIZE - 48 &&510 !current->bio_list)511 bch_btree_node_write(b, NULL);512}513 514/*515 * Btree in memory cache - allocation/freeing516 * mca -> memory cache517 */518 519#define mca_reserve(c) (((!IS_ERR_OR_NULL(c->root) && c->root->level) \520 ? c->root->level : 1) * 8 + 16)521#define mca_can_free(c) \522 max_t(int, 0, c->btree_cache_used - mca_reserve(c))523 524static void mca_data_free(struct btree *b)525{526 BUG_ON(b->io_mutex.count != 1);527 528 bch_btree_keys_free(&b->keys);529 530 b->c->btree_cache_used--;531 list_move(&b->list, &b->c->btree_cache_freed);532}533 534static void mca_bucket_free(struct btree *b)535{536 BUG_ON(btree_node_dirty(b));537 538 b->key.ptr[0] = 0;539 hlist_del_init_rcu(&b->hash);540 list_move(&b->list, &b->c->btree_cache_freeable);541}542 543static unsigned int btree_order(struct bkey *k)544{545 return ilog2(KEY_SIZE(k) / PAGE_SECTORS ?: 1);546}547 548static void mca_data_alloc(struct btree *b, struct bkey *k, gfp_t gfp)549{550 if (!bch_btree_keys_alloc(&b->keys,551 max_t(unsigned int,552 ilog2(b->c->btree_pages),553 btree_order(k)),554 gfp)) {555 b->c->btree_cache_used++;556 list_move(&b->list, &b->c->btree_cache);557 } else {558 list_move(&b->list, &b->c->btree_cache_freed);559 }560}561 562#define cmp_int(l, r) ((l > r) - (l < r))563 564#ifdef CONFIG_PROVE_LOCKING565static int btree_lock_cmp_fn(const struct lockdep_map *_a,566 const struct lockdep_map *_b)567{568 const struct btree *a = container_of(_a, struct btree, lock.dep_map);569 const struct btree *b = container_of(_b, struct btree, lock.dep_map);570 571 return -cmp_int(a->level, b->level) ?: bkey_cmp(&a->key, &b->key);572}573 574static void btree_lock_print_fn(const struct lockdep_map *map)575{576 const struct btree *b = container_of(map, struct btree, lock.dep_map);577 578 printk(KERN_CONT " l=%u %llu:%llu", b->level,579 KEY_INODE(&b->key), KEY_OFFSET(&b->key));580}581#endif582 583static struct btree *mca_bucket_alloc(struct cache_set *c,584 struct bkey *k, gfp_t gfp)585{586 /*587 * kzalloc() is necessary here for initialization,588 * see code comments in bch_btree_keys_init().589 */590 struct btree *b = kzalloc(sizeof(struct btree), gfp);591 592 if (!b)593 return NULL;594 595 init_rwsem(&b->lock);596 lock_set_cmp_fn(&b->lock, btree_lock_cmp_fn, btree_lock_print_fn);597 mutex_init(&b->write_lock);598 lockdep_set_novalidate_class(&b->write_lock);599 INIT_LIST_HEAD(&b->list);600 INIT_DELAYED_WORK(&b->work, btree_node_write_work);601 b->c = c;602 sema_init(&b->io_mutex, 1);603 604 mca_data_alloc(b, k, gfp);605 return b;606}607 608static int mca_reap(struct btree *b, unsigned int min_order, bool flush)609{610 struct closure cl;611 612 closure_init_stack(&cl);613 lockdep_assert_held(&b->c->bucket_lock);614 615 if (!down_write_trylock(&b->lock))616 return -ENOMEM;617 618 BUG_ON(btree_node_dirty(b) && !b->keys.set[0].data);619 620 if (b->keys.page_order < min_order)621 goto out_unlock;622 623 if (!flush) {624 if (btree_node_dirty(b))625 goto out_unlock;626 627 if (down_trylock(&b->io_mutex))628 goto out_unlock;629 up(&b->io_mutex);630 }631 632retry:633 /*634 * BTREE_NODE_dirty might be cleared in btree_flush_btree() by635 * __bch_btree_node_write(). To avoid an extra flush, acquire636 * b->write_lock before checking BTREE_NODE_dirty bit.637 */638 mutex_lock(&b->write_lock);639 /*640 * If this btree node is selected in btree_flush_write() by journal641 * code, delay and retry until the node is flushed by journal code642 * and BTREE_NODE_journal_flush bit cleared by btree_flush_write().643 */644 if (btree_node_journal_flush(b)) {645 pr_debug("bnode %p is flushing by journal, retry\n", b);646 mutex_unlock(&b->write_lock);647 udelay(1);648 goto retry;649 }650 651 if (btree_node_dirty(b))652 __bch_btree_node_write(b, &cl);653 mutex_unlock(&b->write_lock);654 655 closure_sync(&cl);656 657 /* wait for any in flight btree write */658 down(&b->io_mutex);659 up(&b->io_mutex);660 661 return 0;662out_unlock:663 rw_unlock(true, b);664 return -ENOMEM;665}666 667static unsigned long bch_mca_scan(struct shrinker *shrink,668 struct shrink_control *sc)669{670 struct cache_set *c = shrink->private_data;671 struct btree *b, *t;672 unsigned long i, nr = sc->nr_to_scan;673 unsigned long freed = 0;674 unsigned int btree_cache_used;675 676 if (c->shrinker_disabled)677 return SHRINK_STOP;678 679 if (c->btree_cache_alloc_lock)680 return SHRINK_STOP;681 682 /* Return -1 if we can't do anything right now */683 if (sc->gfp_mask & __GFP_IO)684 mutex_lock(&c->bucket_lock);685 else if (!mutex_trylock(&c->bucket_lock))686 return -1;687 688 /*689 * It's _really_ critical that we don't free too many btree nodes - we690 * have to always leave ourselves a reserve. The reserve is how we691 * guarantee that allocating memory for a new btree node can always692 * succeed, so that inserting keys into the btree can always succeed and693 * IO can always make forward progress:694 */695 nr /= c->btree_pages;696 if (nr == 0)697 nr = 1;698 nr = min_t(unsigned long, nr, mca_can_free(c));699 700 i = 0;701 btree_cache_used = c->btree_cache_used;702 list_for_each_entry_safe_reverse(b, t, &c->btree_cache_freeable, list) {703 if (nr <= 0)704 goto out;705 706 if (!mca_reap(b, 0, false)) {707 mca_data_free(b);708 rw_unlock(true, b);709 freed++;710 }711 nr--;712 i++;713 }714 715 list_for_each_entry_safe_reverse(b, t, &c->btree_cache, list) {716 if (nr <= 0 || i >= btree_cache_used)717 goto out;718 719 if (!mca_reap(b, 0, false)) {720 mca_bucket_free(b);721 mca_data_free(b);722 rw_unlock(true, b);723 freed++;724 }725 726 nr--;727 i++;728 }729out:730 mutex_unlock(&c->bucket_lock);731 return freed * c->btree_pages;732}733 734static unsigned long bch_mca_count(struct shrinker *shrink,735 struct shrink_control *sc)736{737 struct cache_set *c = shrink->private_data;738 739 if (c->shrinker_disabled)740 return 0;741 742 if (c->btree_cache_alloc_lock)743 return 0;744 745 return mca_can_free(c) * c->btree_pages;746}747 748void bch_btree_cache_free(struct cache_set *c)749{750 struct btree *b;751 struct closure cl;752 753 closure_init_stack(&cl);754 755 if (c->shrink)756 shrinker_free(c->shrink);757 758 mutex_lock(&c->bucket_lock);759 760#ifdef CONFIG_BCACHE_DEBUG761 if (c->verify_data)762 list_move(&c->verify_data->list, &c->btree_cache);763 764 free_pages((unsigned long) c->verify_ondisk, ilog2(meta_bucket_pages(&c->cache->sb)));765#endif766 767 list_splice(&c->btree_cache_freeable,768 &c->btree_cache);769 770 while (!list_empty(&c->btree_cache)) {771 b = list_first_entry(&c->btree_cache, struct btree, list);772 773 /*774 * This function is called by cache_set_free(), no I/O775 * request on cache now, it is unnecessary to acquire776 * b->write_lock before clearing BTREE_NODE_dirty anymore.777 */778 if (btree_node_dirty(b)) {779 btree_complete_write(b, btree_current_write(b));780 clear_bit(BTREE_NODE_dirty, &b->flags);781 }782 mca_data_free(b);783 }784 785 while (!list_empty(&c->btree_cache_freed)) {786 b = list_first_entry(&c->btree_cache_freed,787 struct btree, list);788 list_del(&b->list);789 cancel_delayed_work_sync(&b->work);790 kfree(b);791 }792 793 mutex_unlock(&c->bucket_lock);794}795 796int bch_btree_cache_alloc(struct cache_set *c)797{798 unsigned int i;799 800 for (i = 0; i < mca_reserve(c); i++)801 if (!mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL))802 return -ENOMEM;803 804 list_splice_init(&c->btree_cache,805 &c->btree_cache_freeable);806 807#ifdef CONFIG_BCACHE_DEBUG808 mutex_init(&c->verify_lock);809 810 c->verify_ondisk = (void *)811 __get_free_pages(GFP_KERNEL|__GFP_COMP,812 ilog2(meta_bucket_pages(&c->cache->sb)));813 if (!c->verify_ondisk) {814 /*815 * Don't worry about the mca_rereserve buckets816 * allocated in previous for-loop, they will be817 * handled properly in bch_cache_set_unregister().818 */819 return -ENOMEM;820 }821 822 c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL);823 824 if (c->verify_data &&825 c->verify_data->keys.set->data)826 list_del_init(&c->verify_data->list);827 else828 c->verify_data = NULL;829#endif830 831 c->shrink = shrinker_alloc(0, "md-bcache:%pU", c->set_uuid);832 if (!c->shrink) {833 pr_warn("bcache: %s: could not allocate shrinker\n", __func__);834 return 0;835 }836 837 c->shrink->count_objects = bch_mca_count;838 c->shrink->scan_objects = bch_mca_scan;839 c->shrink->seeks = 4;840 c->shrink->batch = c->btree_pages * 2;841 c->shrink->private_data = c;842 843 shrinker_register(c->shrink);844 845 return 0;846}847 848/* Btree in memory cache - hash table */849 850static struct hlist_head *mca_hash(struct cache_set *c, struct bkey *k)851{852 return &c->bucket_hash[hash_32(PTR_HASH(c, k), BUCKET_HASH_BITS)];853}854 855static struct btree *mca_find(struct cache_set *c, struct bkey *k)856{857 struct btree *b;858 859 rcu_read_lock();860 hlist_for_each_entry_rcu(b, mca_hash(c, k), hash)861 if (PTR_HASH(c, &b->key) == PTR_HASH(c, k))862 goto out;863 b = NULL;864out:865 rcu_read_unlock();866 return b;867}868 869static int mca_cannibalize_lock(struct cache_set *c, struct btree_op *op)870{871 spin_lock(&c->btree_cannibalize_lock);872 if (likely(c->btree_cache_alloc_lock == NULL)) {873 c->btree_cache_alloc_lock = current;874 } else if (c->btree_cache_alloc_lock != current) {875 if (op)876 prepare_to_wait(&c->btree_cache_wait, &op->wait,877 TASK_UNINTERRUPTIBLE);878 spin_unlock(&c->btree_cannibalize_lock);879 return -EINTR;880 }881 spin_unlock(&c->btree_cannibalize_lock);882 883 return 0;884}885 886static struct btree *mca_cannibalize(struct cache_set *c, struct btree_op *op,887 struct bkey *k)888{889 struct btree *b;890 891 trace_bcache_btree_cache_cannibalize(c);892 893 if (mca_cannibalize_lock(c, op))894 return ERR_PTR(-EINTR);895 896 list_for_each_entry_reverse(b, &c->btree_cache, list)897 if (!mca_reap(b, btree_order(k), false))898 return b;899 900 list_for_each_entry_reverse(b, &c->btree_cache, list)901 if (!mca_reap(b, btree_order(k), true))902 return b;903 904 WARN(1, "btree cache cannibalize failed\n");905 return ERR_PTR(-ENOMEM);906}907 908/*909 * We can only have one thread cannibalizing other cached btree nodes at a time,910 * or we'll deadlock. We use an open coded mutex to ensure that, which a911 * cannibalize_bucket() will take. This means every time we unlock the root of912 * the btree, we need to release this lock if we have it held.913 */914void bch_cannibalize_unlock(struct cache_set *c)915{916 spin_lock(&c->btree_cannibalize_lock);917 if (c->btree_cache_alloc_lock == current) {918 c->btree_cache_alloc_lock = NULL;919 wake_up(&c->btree_cache_wait);920 }921 spin_unlock(&c->btree_cannibalize_lock);922}923 924static struct btree *mca_alloc(struct cache_set *c, struct btree_op *op,925 struct bkey *k, int level)926{927 struct btree *b;928 929 BUG_ON(current->bio_list);930 931 lockdep_assert_held(&c->bucket_lock);932 933 if (mca_find(c, k))934 return NULL;935 936 /* btree_free() doesn't free memory; it sticks the node on the end of937 * the list. Check if there's any freed nodes there:938 */939 list_for_each_entry(b, &c->btree_cache_freeable, list)940 if (!mca_reap(b, btree_order(k), false))941 goto out;942 943 /* We never free struct btree itself, just the memory that holds the on944 * disk node. Check the freed list before allocating a new one:945 */946 list_for_each_entry(b, &c->btree_cache_freed, list)947 if (!mca_reap(b, 0, false)) {948 mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO);949 if (!b->keys.set[0].data)950 goto err;951 else952 goto out;953 }954 955 b = mca_bucket_alloc(c, k, __GFP_NOWARN|GFP_NOIO);956 if (!b)957 goto err;958 959 BUG_ON(!down_write_trylock(&b->lock));960 if (!b->keys.set->data)961 goto err;962out:963 BUG_ON(b->io_mutex.count != 1);964 965 bkey_copy(&b->key, k);966 list_move(&b->list, &c->btree_cache);967 hlist_del_init_rcu(&b->hash);968 hlist_add_head_rcu(&b->hash, mca_hash(c, k));969 970 lock_set_subclass(&b->lock.dep_map, level + 1, _THIS_IP_);971 b->parent = (void *) ~0UL;972 b->flags = 0;973 b->written = 0;974 b->level = level;975 976 if (!b->level)977 bch_btree_keys_init(&b->keys, &bch_extent_keys_ops,978 &b->c->expensive_debug_checks);979 else980 bch_btree_keys_init(&b->keys, &bch_btree_keys_ops,981 &b->c->expensive_debug_checks);982 983 return b;984err:985 if (b)986 rw_unlock(true, b);987 988 b = mca_cannibalize(c, op, k);989 if (!IS_ERR(b))990 goto out;991 992 return b;993}994 995/*996 * bch_btree_node_get - find a btree node in the cache and lock it, reading it997 * in from disk if necessary.998 *999 * If IO is necessary and running under submit_bio_noacct, returns -EAGAIN.1000 *1001 * The btree node will have either a read or a write lock held, depending on1002 * level and op->lock.1003 *1004 * Note: Only error code or btree pointer will be returned, it is unncessary1005 * for callers to check NULL pointer.1006 */1007struct btree *bch_btree_node_get(struct cache_set *c, struct btree_op *op,1008 struct bkey *k, int level, bool write,1009 struct btree *parent)1010{1011 int i = 0;1012 struct btree *b;1013 1014 BUG_ON(level < 0);1015retry:1016 b = mca_find(c, k);1017 1018 if (!b) {1019 if (current->bio_list)1020 return ERR_PTR(-EAGAIN);1021 1022 mutex_lock(&c->bucket_lock);1023 b = mca_alloc(c, op, k, level);1024 mutex_unlock(&c->bucket_lock);1025 1026 if (!b)1027 goto retry;1028 if (IS_ERR(b))1029 return b;1030 1031 bch_btree_node_read(b);1032 1033 if (!write)1034 downgrade_write(&b->lock);1035 } else {1036 rw_lock(write, b, level);1037 if (PTR_HASH(c, &b->key) != PTR_HASH(c, k)) {1038 rw_unlock(write, b);1039 goto retry;1040 }1041 BUG_ON(b->level != level);1042 }1043 1044 if (btree_node_io_error(b)) {1045 rw_unlock(write, b);1046 return ERR_PTR(-EIO);1047 }1048 1049 BUG_ON(!b->written);1050 1051 b->parent = parent;1052 1053 for (; i <= b->keys.nsets && b->keys.set[i].size; i++) {1054 prefetch(b->keys.set[i].tree);1055 prefetch(b->keys.set[i].data);1056 }1057 1058 for (; i <= b->keys.nsets; i++)1059 prefetch(b->keys.set[i].data);1060 1061 return b;1062}1063 1064static void btree_node_prefetch(struct btree *parent, struct bkey *k)1065{1066 struct btree *b;1067 1068 mutex_lock(&parent->c->bucket_lock);1069 b = mca_alloc(parent->c, NULL, k, parent->level - 1);1070 mutex_unlock(&parent->c->bucket_lock);1071 1072 if (!IS_ERR_OR_NULL(b)) {1073 b->parent = parent;1074 bch_btree_node_read(b);1075 rw_unlock(true, b);1076 }1077}1078 1079/* Btree alloc */1080 1081static void btree_node_free(struct btree *b)1082{1083 trace_bcache_btree_node_free(b);1084 1085 BUG_ON(b == b->c->root);1086 1087retry:1088 mutex_lock(&b->write_lock);1089 /*1090 * If the btree node is selected and flushing in btree_flush_write(),1091 * delay and retry until the BTREE_NODE_journal_flush bit cleared,1092 * then it is safe to free the btree node here. Otherwise this btree1093 * node will be in race condition.1094 */1095 if (btree_node_journal_flush(b)) {1096 mutex_unlock(&b->write_lock);1097 pr_debug("bnode %p journal_flush set, retry\n", b);1098 udelay(1);1099 goto retry;1100 }1101 1102 if (btree_node_dirty(b)) {1103 btree_complete_write(b, btree_current_write(b));1104 clear_bit(BTREE_NODE_dirty, &b->flags);1105 }1106 1107 mutex_unlock(&b->write_lock);1108 1109 cancel_delayed_work(&b->work);1110 1111 mutex_lock(&b->c->bucket_lock);1112 bch_bucket_free(b->c, &b->key);1113 mca_bucket_free(b);1114 mutex_unlock(&b->c->bucket_lock);1115}1116 1117/*1118 * Only error code or btree pointer will be returned, it is unncessary for1119 * callers to check NULL pointer.1120 */1121struct btree *__bch_btree_node_alloc(struct cache_set *c, struct btree_op *op,1122 int level, bool wait,1123 struct btree *parent)1124{1125 BKEY_PADDED(key) k;1126 struct btree *b;1127 1128 mutex_lock(&c->bucket_lock);1129retry:1130 /* return ERR_PTR(-EAGAIN) when it fails */1131 b = ERR_PTR(-EAGAIN);1132 if (__bch_bucket_alloc_set(c, RESERVE_BTREE, &k.key, wait))1133 goto err;1134 1135 bkey_put(c, &k.key);1136 SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS);1137 1138 b = mca_alloc(c, op, &k.key, level);1139 if (IS_ERR(b))1140 goto err_free;1141 1142 if (!b) {1143 cache_bug(c,1144 "Tried to allocate bucket that was in btree cache");1145 goto retry;1146 }1147 1148 b->parent = parent;1149 bch_bset_init_next(&b->keys, b->keys.set->data, bset_magic(&b->c->cache->sb));1150 1151 mutex_unlock(&c->bucket_lock);1152 1153 trace_bcache_btree_node_alloc(b);1154 return b;1155err_free:1156 bch_bucket_free(c, &k.key);1157err:1158 mutex_unlock(&c->bucket_lock);1159 1160 trace_bcache_btree_node_alloc_fail(c);1161 return b;1162}1163 1164static struct btree *bch_btree_node_alloc(struct cache_set *c,1165 struct btree_op *op, int level,1166 struct btree *parent)1167{1168 return __bch_btree_node_alloc(c, op, level, op != NULL, parent);1169}1170 1171static struct btree *btree_node_alloc_replacement(struct btree *b,1172 struct btree_op *op)1173{1174 struct btree *n = bch_btree_node_alloc(b->c, op, b->level, b->parent);1175 1176 if (!IS_ERR(n)) {1177 mutex_lock(&n->write_lock);1178 bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort);1179 bkey_copy_key(&n->key, &b->key);1180 mutex_unlock(&n->write_lock);1181 }1182 1183 return n;1184}1185 1186static void make_btree_freeing_key(struct btree *b, struct bkey *k)1187{1188 unsigned int i;1189 1190 mutex_lock(&b->c->bucket_lock);1191 1192 atomic_inc(&b->c->prio_blocked);1193 1194 bkey_copy(k, &b->key);1195 bkey_copy_key(k, &ZERO_KEY);1196 1197 for (i = 0; i < KEY_PTRS(k); i++)1198 SET_PTR_GEN(k, i,1199 bch_inc_gen(b->c->cache,1200 PTR_BUCKET(b->c, &b->key, i)));1201 1202 mutex_unlock(&b->c->bucket_lock);1203}1204 1205static int btree_check_reserve(struct btree *b, struct btree_op *op)1206{1207 struct cache_set *c = b->c;1208 struct cache *ca = c->cache;1209 unsigned int reserve = (c->root->level - b->level) * 2 + 1;1210 1211 mutex_lock(&c->bucket_lock);1212 1213 if (fifo_used(&ca->free[RESERVE_BTREE]) < reserve) {1214 if (op)1215 prepare_to_wait(&c->btree_cache_wait, &op->wait,1216 TASK_UNINTERRUPTIBLE);1217 mutex_unlock(&c->bucket_lock);1218 return -EINTR;1219 }1220 1221 mutex_unlock(&c->bucket_lock);1222 1223 return mca_cannibalize_lock(b->c, op);1224}1225 1226/* Garbage collection */1227 1228static uint8_t __bch_btree_mark_key(struct cache_set *c, int level,1229 struct bkey *k)1230{1231 uint8_t stale = 0;1232 unsigned int i;1233 struct bucket *g;1234 1235 /*1236 * ptr_invalid() can't return true for the keys that mark btree nodes as1237 * freed, but since ptr_bad() returns true we'll never actually use them1238 * for anything and thus we don't want mark their pointers here1239 */1240 if (!bkey_cmp(k, &ZERO_KEY))1241 return stale;1242 1243 for (i = 0; i < KEY_PTRS(k); i++) {1244 if (!ptr_available(c, k, i))1245 continue;1246 1247 g = PTR_BUCKET(c, k, i);1248 1249 if (gen_after(g->last_gc, PTR_GEN(k, i)))1250 g->last_gc = PTR_GEN(k, i);1251 1252 if (ptr_stale(c, k, i)) {1253 stale = max(stale, ptr_stale(c, k, i));1254 continue;1255 }1256 1257 cache_bug_on(GC_MARK(g) &&1258 (GC_MARK(g) == GC_MARK_METADATA) != (level != 0),1259 c, "inconsistent ptrs: mark = %llu, level = %i",1260 GC_MARK(g), level);1261 1262 if (level)1263 SET_GC_MARK(g, GC_MARK_METADATA);1264 else if (KEY_DIRTY(k))1265 SET_GC_MARK(g, GC_MARK_DIRTY);1266 else if (!GC_MARK(g))1267 SET_GC_MARK(g, GC_MARK_RECLAIMABLE);1268 1269 /* guard against overflow */1270 SET_GC_SECTORS_USED(g, min_t(unsigned int,1271 GC_SECTORS_USED(g) + KEY_SIZE(k),1272 MAX_GC_SECTORS_USED));1273 1274 BUG_ON(!GC_SECTORS_USED(g));1275 }1276 1277 return stale;1278}1279 1280#define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k)1281 1282void bch_initial_mark_key(struct cache_set *c, int level, struct bkey *k)1283{1284 unsigned int i;1285 1286 for (i = 0; i < KEY_PTRS(k); i++)1287 if (ptr_available(c, k, i) &&1288 !ptr_stale(c, k, i)) {1289 struct bucket *b = PTR_BUCKET(c, k, i);1290 1291 b->gen = PTR_GEN(k, i);1292 1293 if (level && bkey_cmp(k, &ZERO_KEY))1294 b->prio = BTREE_PRIO;1295 else if (!level && b->prio == BTREE_PRIO)1296 b->prio = INITIAL_PRIO;1297 }1298 1299 __bch_btree_mark_key(c, level, k);1300}1301 1302void bch_update_bucket_in_use(struct cache_set *c, struct gc_stat *stats)1303{1304 stats->in_use = (c->nbuckets - c->avail_nbuckets) * 100 / c->nbuckets;1305}1306 1307static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc)1308{1309 uint8_t stale = 0;1310 unsigned int keys = 0, good_keys = 0;1311 struct bkey *k;1312 struct btree_iter iter;1313 struct bset_tree *t;1314 1315 min_heap_init(&iter.heap, NULL, MAX_BSETS);1316 1317 gc->nodes++;1318 1319 for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) {1320 stale = max(stale, btree_mark_key(b, k));1321 keys++;1322 1323 if (bch_ptr_bad(&b->keys, k))1324 continue;1325 1326 gc->key_bytes += bkey_u64s(k);1327 gc->nkeys++;1328 good_keys++;1329 1330 gc->data += KEY_SIZE(k);1331 }1332 1333 for (t = b->keys.set; t <= &b->keys.set[b->keys.nsets]; t++)1334 btree_bug_on(t->size &&1335 bset_written(&b->keys, t) &&1336 bkey_cmp(&b->key, &t->end) < 0,1337 b, "found short btree key in gc");1338 1339 if (b->c->gc_always_rewrite)1340 return true;1341 1342 if (stale > 10)1343 return true;1344 1345 if ((keys - good_keys) * 2 > keys)1346 return true;1347 1348 return false;1349}1350 1351#define GC_MERGE_NODES 4U1352 1353struct gc_merge_info {1354 struct btree *b;1355 unsigned int keys;1356};1357 1358static int bch_btree_insert_node(struct btree *b, struct btree_op *op,1359 struct keylist *insert_keys,1360 atomic_t *journal_ref,1361 struct bkey *replace_key);1362 1363static int btree_gc_coalesce(struct btree *b, struct btree_op *op,1364 struct gc_stat *gc, struct gc_merge_info *r)1365{1366 unsigned int i, nodes = 0, keys = 0, blocks;1367 struct btree *new_nodes[GC_MERGE_NODES];1368 struct keylist keylist;1369 struct closure cl;1370 struct bkey *k;1371 1372 bch_keylist_init(&keylist);1373 1374 if (btree_check_reserve(b, NULL))1375 return 0;1376 1377 memset(new_nodes, 0, sizeof(new_nodes));1378 closure_init_stack(&cl);1379 1380 while (nodes < GC_MERGE_NODES && !IS_ERR_OR_NULL(r[nodes].b))1381 keys += r[nodes++].keys;1382 1383 blocks = btree_default_blocks(b->c) * 2 / 3;1384 1385 if (nodes < 2 ||1386 __set_blocks(b->keys.set[0].data, keys,1387 block_bytes(b->c->cache)) > blocks * (nodes - 1))1388 return 0;1389 1390 for (i = 0; i < nodes; i++) {1391 new_nodes[i] = btree_node_alloc_replacement(r[i].b, NULL);1392 if (IS_ERR(new_nodes[i]))1393 goto out_nocoalesce;1394 }1395 1396 /*1397 * We have to check the reserve here, after we've allocated our new1398 * nodes, to make sure the insert below will succeed - we also check1399 * before as an optimization to potentially avoid a bunch of expensive1400 * allocs/sorts1401 */1402 if (btree_check_reserve(b, NULL))1403 goto out_nocoalesce;1404 1405 for (i = 0; i < nodes; i++)1406 mutex_lock(&new_nodes[i]->write_lock);1407 1408 for (i = nodes - 1; i > 0; --i) {1409 struct bset *n1 = btree_bset_first(new_nodes[i]);1410 struct bset *n2 = btree_bset_first(new_nodes[i - 1]);1411 struct bkey *k, *last = NULL;1412 1413 keys = 0;1414 1415 if (i > 1) {1416 for (k = n2->start;1417 k < bset_bkey_last(n2);1418 k = bkey_next(k)) {1419 if (__set_blocks(n1, n1->keys + keys +1420 bkey_u64s(k),1421 block_bytes(b->c->cache)) > blocks)1422 break;1423 1424 last = k;1425 keys += bkey_u64s(k);1426 }1427 } else {1428 /*1429 * Last node we're not getting rid of - we're getting1430 * rid of the node at r[0]. Have to try and fit all of1431 * the remaining keys into this node; we can't ensure1432 * they will always fit due to rounding and variable1433 * length keys (shouldn't be possible in practice,1434 * though)1435 */1436 if (__set_blocks(n1, n1->keys + n2->keys,1437 block_bytes(b->c->cache)) >1438 btree_blocks(new_nodes[i]))1439 goto out_unlock_nocoalesce;1440 1441 keys = n2->keys;1442 /* Take the key of the node we're getting rid of */1443 last = &r->b->key;1444 }1445 1446 BUG_ON(__set_blocks(n1, n1->keys + keys, block_bytes(b->c->cache)) >1447 btree_blocks(new_nodes[i]));1448 1449 if (last)1450 bkey_copy_key(&new_nodes[i]->key, last);1451 1452 memcpy(bset_bkey_last(n1),1453 n2->start,1454 (void *) bset_bkey_idx(n2, keys) - (void *) n2->start);1455 1456 n1->keys += keys;1457 r[i].keys = n1->keys;1458 1459 memmove(n2->start,1460 bset_bkey_idx(n2, keys),1461 (void *) bset_bkey_last(n2) -1462 (void *) bset_bkey_idx(n2, keys));1463 1464 n2->keys -= keys;1465 1466 if (__bch_keylist_realloc(&keylist,1467 bkey_u64s(&new_nodes[i]->key)))1468 goto out_unlock_nocoalesce;1469 1470 bch_btree_node_write(new_nodes[i], &cl);1471 bch_keylist_add(&keylist, &new_nodes[i]->key);1472 }1473 1474 for (i = 0; i < nodes; i++)1475 mutex_unlock(&new_nodes[i]->write_lock);1476 1477 closure_sync(&cl);1478 1479 /* We emptied out this node */1480 BUG_ON(btree_bset_first(new_nodes[0])->keys);1481 btree_node_free(new_nodes[0]);1482 rw_unlock(true, new_nodes[0]);1483 new_nodes[0] = NULL;1484 1485 for (i = 0; i < nodes; i++) {1486 if (__bch_keylist_realloc(&keylist, bkey_u64s(&r[i].b->key)))1487 goto out_nocoalesce;1488 1489 make_btree_freeing_key(r[i].b, keylist.top);1490 bch_keylist_push(&keylist);1491 }1492 1493 bch_btree_insert_node(b, op, &keylist, NULL, NULL);1494 BUG_ON(!bch_keylist_empty(&keylist));1495 1496 for (i = 0; i < nodes; i++) {1497 btree_node_free(r[i].b);1498 rw_unlock(true, r[i].b);1499 1500 r[i].b = new_nodes[i];1501 }1502 1503 memmove(r, r + 1, sizeof(r[0]) * (nodes - 1));1504 r[nodes - 1].b = ERR_PTR(-EINTR);1505 1506 trace_bcache_btree_gc_coalesce(nodes);1507 gc->nodes--;1508 1509 bch_keylist_free(&keylist);1510 1511 /* Invalidated our iterator */1512 return -EINTR;1513 1514out_unlock_nocoalesce:1515 for (i = 0; i < nodes; i++)1516 mutex_unlock(&new_nodes[i]->write_lock);1517 1518out_nocoalesce:1519 closure_sync(&cl);1520 1521 while ((k = bch_keylist_pop(&keylist)))1522 if (!bkey_cmp(k, &ZERO_KEY))1523 atomic_dec(&b->c->prio_blocked);1524 bch_keylist_free(&keylist);1525 1526 for (i = 0; i < nodes; i++)1527 if (!IS_ERR_OR_NULL(new_nodes[i])) {1528 btree_node_free(new_nodes[i]);1529 rw_unlock(true, new_nodes[i]);1530 }1531 return 0;1532}1533 1534static int btree_gc_rewrite_node(struct btree *b, struct btree_op *op,1535 struct btree *replace)1536{1537 struct keylist keys;1538 struct btree *n;1539 1540 if (btree_check_reserve(b, NULL))1541 return 0;1542 1543 n = btree_node_alloc_replacement(replace, NULL);1544 if (IS_ERR(n))1545 return 0;1546 1547 /* recheck reserve after allocating replacement node */1548 if (btree_check_reserve(b, NULL)) {1549 btree_node_free(n);1550 rw_unlock(true, n);1551 return 0;1552 }1553 1554 bch_btree_node_write_sync(n);1555 1556 bch_keylist_init(&keys);1557 bch_keylist_add(&keys, &n->key);1558 1559 make_btree_freeing_key(replace, keys.top);1560 bch_keylist_push(&keys);1561 1562 bch_btree_insert_node(b, op, &keys, NULL, NULL);1563 BUG_ON(!bch_keylist_empty(&keys));1564 1565 btree_node_free(replace);1566 rw_unlock(true, n);1567 1568 /* Invalidated our iterator */1569 return -EINTR;1570}1571 1572static unsigned int btree_gc_count_keys(struct btree *b)1573{1574 struct bkey *k;1575 struct btree_iter iter;1576 unsigned int ret = 0;1577 1578 min_heap_init(&iter.heap, NULL, MAX_BSETS);1579 1580 for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad)1581 ret += bkey_u64s(k);1582 1583 return ret;1584}1585 1586static size_t btree_gc_min_nodes(struct cache_set *c)1587{1588 size_t min_nodes;1589 1590 /*1591 * Since incremental GC would stop 100ms when front1592 * side I/O comes, so when there are many btree nodes,1593 * if GC only processes constant (100) nodes each time,1594 * GC would last a long time, and the front side I/Os1595 * would run out of the buckets (since no new bucket1596 * can be allocated during GC), and be blocked again.1597 * So GC should not process constant nodes, but varied1598 * nodes according to the number of btree nodes, which1599 * realized by dividing GC into constant(100) times,1600 * so when there are many btree nodes, GC can process1601 * more nodes each time, otherwise, GC will process less1602 * nodes each time (but no less than MIN_GC_NODES)1603 */1604 min_nodes = c->gc_stats.nodes / MAX_GC_TIMES;1605 if (min_nodes < MIN_GC_NODES)1606 min_nodes = MIN_GC_NODES;1607 1608 return min_nodes;1609}1610 1611 1612static int btree_gc_recurse(struct btree *b, struct btree_op *op,1613 struct closure *writes, struct gc_stat *gc)1614{1615 int ret = 0;1616 bool should_rewrite;1617 struct bkey *k;1618 struct btree_iter iter;1619 struct gc_merge_info r[GC_MERGE_NODES];1620 struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1;1621 1622 min_heap_init(&iter.heap, NULL, MAX_BSETS);1623 bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done);1624 1625 for (i = r; i < r + ARRAY_SIZE(r); i++)1626 i->b = ERR_PTR(-EINTR);1627 1628 while (1) {1629 k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad);1630 if (k) {1631 r->b = bch_btree_node_get(b->c, op, k, b->level - 1,1632 true, b);1633 if (IS_ERR(r->b)) {1634 ret = PTR_ERR(r->b);1635 break;1636 }1637 1638 r->keys = btree_gc_count_keys(r->b);1639 1640 ret = btree_gc_coalesce(b, op, gc, r);1641 if (ret)1642 break;1643 }1644 1645 if (!last->b)1646 break;1647 1648 if (!IS_ERR(last->b)) {1649 should_rewrite = btree_gc_mark_node(last->b, gc);1650 if (should_rewrite) {1651 ret = btree_gc_rewrite_node(b, op, last->b);1652 if (ret)1653 break;1654 }1655 1656 if (last->b->level) {1657 ret = btree_gc_recurse(last->b, op, writes, gc);1658 if (ret)1659 break;1660 }1661 1662 bkey_copy_key(&b->c->gc_done, &last->b->key);1663 1664 /*1665 * Must flush leaf nodes before gc ends, since replace1666 * operations aren't journalled1667 */1668 mutex_lock(&last->b->write_lock);1669 if (btree_node_dirty(last->b))1670 bch_btree_node_write(last->b, writes);1671 mutex_unlock(&last->b->write_lock);1672 rw_unlock(true, last->b);1673 }1674 1675 memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1));1676 r->b = NULL;1677 1678 if (atomic_read(&b->c->search_inflight) &&1679 gc->nodes >= gc->nodes_pre + btree_gc_min_nodes(b->c)) {1680 gc->nodes_pre = gc->nodes;1681 ret = -EAGAIN;1682 break;1683 }1684 1685 if (need_resched()) {1686 ret = -EAGAIN;1687 break;1688 }1689 }1690 1691 for (i = r; i < r + ARRAY_SIZE(r); i++)1692 if (!IS_ERR_OR_NULL(i->b)) {1693 mutex_lock(&i->b->write_lock);1694 if (btree_node_dirty(i->b))1695 bch_btree_node_write(i->b, writes);1696 mutex_unlock(&i->b->write_lock);1697 rw_unlock(true, i->b);1698 }1699 1700 return ret;1701}1702 1703static int bch_btree_gc_root(struct btree *b, struct btree_op *op,1704 struct closure *writes, struct gc_stat *gc)1705{1706 struct btree *n = NULL;1707 int ret = 0;1708 bool should_rewrite;1709 1710 should_rewrite = btree_gc_mark_node(b, gc);1711 if (should_rewrite) {1712 n = btree_node_alloc_replacement(b, NULL);1713 1714 if (!IS_ERR(n)) {1715 bch_btree_node_write_sync(n);1716 1717 bch_btree_set_root(n);1718 btree_node_free(b);1719 rw_unlock(true, n);1720 1721 return -EINTR;1722 }1723 }1724 1725 __bch_btree_mark_key(b->c, b->level + 1, &b->key);1726 1727 if (b->level) {1728 ret = btree_gc_recurse(b, op, writes, gc);1729 if (ret)1730 return ret;1731 }1732 1733 bkey_copy_key(&b->c->gc_done, &b->key);1734 1735 return ret;1736}1737 1738static void btree_gc_start(struct cache_set *c)1739{1740 struct cache *ca;1741 struct bucket *b;1742 1743 if (!c->gc_mark_valid)1744 return;1745 1746 mutex_lock(&c->bucket_lock);1747 1748 c->gc_done = ZERO_KEY;1749 1750 ca = c->cache;1751 for_each_bucket(b, ca) {1752 b->last_gc = b->gen;1753 if (bch_can_invalidate_bucket(ca, b))1754 b->reclaimable_in_gc = 1;1755 if (!atomic_read(&b->pin)) {1756 SET_GC_MARK(b, 0);1757 SET_GC_SECTORS_USED(b, 0);1758 }1759 }1760 1761 c->gc_mark_valid = 0;1762 mutex_unlock(&c->bucket_lock);1763}1764 1765static void bch_btree_gc_finish(struct cache_set *c)1766{1767 struct bucket *b;1768 struct cache *ca;1769 unsigned int i, j;1770 uint64_t *k;1771 1772 mutex_lock(&c->bucket_lock);1773 1774 set_gc_sectors(c);1775 c->gc_mark_valid = 1;1776 c->need_gc = 0;1777 1778 for (i = 0; i < KEY_PTRS(&c->uuid_bucket); i++)1779 SET_GC_MARK(PTR_BUCKET(c, &c->uuid_bucket, i),1780 GC_MARK_METADATA);1781 1782 /* don't reclaim buckets to which writeback keys point */1783 rcu_read_lock();1784 for (i = 0; i < c->devices_max_used; i++) {1785 struct bcache_device *d = c->devices[i];1786 struct cached_dev *dc;1787 struct keybuf_key *w, *n;1788 1789 if (!d || UUID_FLASH_ONLY(&c->uuids[i]))1790 continue;1791 dc = container_of(d, struct cached_dev, disk);1792 1793 spin_lock(&dc->writeback_keys.lock);1794 rbtree_postorder_for_each_entry_safe(w, n,1795 &dc->writeback_keys.keys, node)1796 for (j = 0; j < KEY_PTRS(&w->key); j++)1797 SET_GC_MARK(PTR_BUCKET(c, &w->key, j),1798 GC_MARK_DIRTY);1799 spin_unlock(&dc->writeback_keys.lock);1800 }1801 rcu_read_unlock();1802 1803 c->avail_nbuckets = 0;1804 1805 ca = c->cache;1806 ca->invalidate_needs_gc = 0;1807 1808 for (k = ca->sb.d; k < ca->sb.d + ca->sb.keys; k++)1809 SET_GC_MARK(ca->buckets + *k, GC_MARK_METADATA);1810 1811 for (k = ca->prio_buckets;1812 k < ca->prio_buckets + prio_buckets(ca) * 2; k++)1813 SET_GC_MARK(ca->buckets + *k, GC_MARK_METADATA);1814 1815 for_each_bucket(b, ca) {1816 c->need_gc = max(c->need_gc, bucket_gc_gen(b));1817 1818 if (b->reclaimable_in_gc)1819 b->reclaimable_in_gc = 0;1820 1821 if (atomic_read(&b->pin))1822 continue;1823 1824 BUG_ON(!GC_MARK(b) && GC_SECTORS_USED(b));1825 1826 if (!GC_MARK(b) || GC_MARK(b) == GC_MARK_RECLAIMABLE)1827 c->avail_nbuckets++;1828 }1829 1830 mutex_unlock(&c->bucket_lock);1831}1832 1833static void bch_btree_gc(struct cache_set *c)1834{1835 int ret;1836 struct gc_stat stats;1837 struct closure writes;1838 struct btree_op op;1839 uint64_t start_time = local_clock();1840 1841 trace_bcache_gc_start(c);1842 1843 memset(&stats, 0, sizeof(struct gc_stat));1844 closure_init_stack(&writes);1845 bch_btree_op_init(&op, SHRT_MAX);1846 1847 btree_gc_start(c);1848 1849 /* if CACHE_SET_IO_DISABLE set, gc thread should stop too */1850 do {1851 ret = bcache_btree_root(gc_root, c, &op, &writes, &stats);1852 closure_sync(&writes);1853 cond_resched();1854 1855 if (ret == -EAGAIN)1856 schedule_timeout_interruptible(msecs_to_jiffies1857 (GC_SLEEP_MS));1858 else if (ret)1859 pr_warn("gc failed!\n");1860 } while (ret && !test_bit(CACHE_SET_IO_DISABLE, &c->flags));1861 1862 bch_btree_gc_finish(c);1863 wake_up_allocators(c);1864 1865 bch_time_stats_update(&c->btree_gc_time, start_time);1866 1867 stats.key_bytes *= sizeof(uint64_t);1868 stats.data <<= 9;1869 bch_update_bucket_in_use(c, &stats);1870 memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat));1871 1872 trace_bcache_gc_end(c);1873 1874 bch_moving_gc(c);1875}1876 1877static bool gc_should_run(struct cache_set *c)1878{1879 struct cache *ca = c->cache;1880 1881 if (ca->invalidate_needs_gc)1882 return true;1883 1884 if (atomic_read(&c->sectors_to_gc) < 0)1885 return true;1886 1887 return false;1888}1889 1890static int bch_gc_thread(void *arg)1891{1892 struct cache_set *c = arg;1893 1894 while (1) {1895 wait_event_interruptible(c->gc_wait,1896 kthread_should_stop() ||1897 test_bit(CACHE_SET_IO_DISABLE, &c->flags) ||1898 gc_should_run(c));1899 1900 if (kthread_should_stop() ||1901 test_bit(CACHE_SET_IO_DISABLE, &c->flags))1902 break;1903 1904 set_gc_sectors(c);1905 bch_btree_gc(c);1906 }1907 1908 wait_for_kthread_stop();1909 return 0;1910}1911 1912int bch_gc_thread_start(struct cache_set *c)1913{1914 c->gc_thread = kthread_run(bch_gc_thread, c, "bcache_gc");1915 return PTR_ERR_OR_ZERO(c->gc_thread);1916}1917 1918/* Initial partial gc */1919 1920static int bch_btree_check_recurse(struct btree *b, struct btree_op *op)1921{1922 int ret = 0;1923 struct bkey *k, *p = NULL;1924 struct btree_iter iter;1925 1926 min_heap_init(&iter.heap, NULL, MAX_BSETS);1927 1928 for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid)1929 bch_initial_mark_key(b->c, b->level, k);1930 1931 bch_initial_mark_key(b->c, b->level + 1, &b->key);1932 1933 if (b->level) {1934 bch_btree_iter_init(&b->keys, &iter, NULL);1935 1936 do {1937 k = bch_btree_iter_next_filter(&iter, &b->keys,1938 bch_ptr_bad);1939 if (k) {1940 btree_node_prefetch(b, k);1941 /*1942 * initiallize c->gc_stats.nodes1943 * for incremental GC1944 */1945 b->c->gc_stats.nodes++;1946 }1947 1948 if (p)1949 ret = bcache_btree(check_recurse, p, b, op);1950 1951 p = k;1952 } while (p && !ret);1953 }1954 1955 return ret;1956}1957 1958 1959static int bch_btree_check_thread(void *arg)1960{1961 int ret;1962 struct btree_check_info *info = arg;1963 struct btree_check_state *check_state = info->state;1964 struct cache_set *c = check_state->c;1965 struct btree_iter iter;1966 struct bkey *k, *p;1967 int cur_idx, prev_idx, skip_nr;1968 1969 k = p = NULL;1970 cur_idx = prev_idx = 0;1971 ret = 0;1972 1973 min_heap_init(&iter.heap, NULL, MAX_BSETS);1974 1975 /* root node keys are checked before thread created */1976 bch_btree_iter_init(&c->root->keys, &iter, NULL);1977 k = bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad);1978 BUG_ON(!k);1979 1980 p = k;1981 while (k) {1982 /*1983 * Fetch a root node key index, skip the keys which1984 * should be fetched by other threads, then check the1985 * sub-tree indexed by the fetched key.1986 */1987 spin_lock(&check_state->idx_lock);1988 cur_idx = check_state->key_idx;1989 check_state->key_idx++;1990 spin_unlock(&check_state->idx_lock);1991 1992 skip_nr = cur_idx - prev_idx;1993 1994 while (skip_nr) {1995 k = bch_btree_iter_next_filter(&iter,1996 &c->root->keys,1997 bch_ptr_bad);1998 if (k)1999 p = k;2000 else {2001 /*2002 * No more keys to check in root node,2003 * current checking threads are enough,2004 * stop creating more.2005 */2006 atomic_set(&check_state->enough, 1);2007 /* Update check_state->enough earlier */2008 smp_mb__after_atomic();2009 goto out;2010 }2011 skip_nr--;2012 cond_resched();2013 }2014 2015 if (p) {2016 struct btree_op op;2017 2018 btree_node_prefetch(c->root, p);2019 c->gc_stats.nodes++;2020 bch_btree_op_init(&op, 0);2021 ret = bcache_btree(check_recurse, p, c->root, &op);2022 /*2023 * The op may be added to cache_set's btree_cache_wait2024 * in mca_cannibalize(), must ensure it is removed from2025 * the list and release btree_cache_alloc_lock before2026 * free op memory.2027 * Otherwise, the btree_cache_wait will be damaged.2028 */2029 bch_cannibalize_unlock(c);2030 finish_wait(&c->btree_cache_wait, &(&op)->wait);2031 if (ret)2032 goto out;2033 }2034 p = NULL;2035 prev_idx = cur_idx;2036 cond_resched();2037 }2038 2039out:2040 info->result = ret;2041 /* update check_state->started among all CPUs */2042 smp_mb__before_atomic();2043 if (atomic_dec_and_test(&check_state->started))2044 wake_up(&check_state->wait);2045 2046 return ret;2047}2048 2049 2050 2051static int bch_btree_chkthread_nr(void)2052{2053 int n = num_online_cpus()/2;2054 2055 if (n == 0)2056 n = 1;2057 else if (n > BCH_BTR_CHKTHREAD_MAX)2058 n = BCH_BTR_CHKTHREAD_MAX;2059 2060 return n;2061}2062 2063int bch_btree_check(struct cache_set *c)2064{2065 int ret = 0;2066 int i;2067 struct bkey *k = NULL;2068 struct btree_iter iter;2069 struct btree_check_state check_state;2070 2071 min_heap_init(&iter.heap, NULL, MAX_BSETS);2072 2073 /* check and mark root node keys */2074 for_each_key_filter(&c->root->keys, k, &iter, bch_ptr_invalid)2075 bch_initial_mark_key(c, c->root->level, k);2076 2077 bch_initial_mark_key(c, c->root->level + 1, &c->root->key);2078 2079 if (c->root->level == 0)2080 return 0;2081 2082 memset(&check_state, 0, sizeof(struct btree_check_state));2083 check_state.c = c;2084 check_state.total_threads = bch_btree_chkthread_nr();2085 check_state.key_idx = 0;2086 spin_lock_init(&check_state.idx_lock);2087 atomic_set(&check_state.started, 0);2088 atomic_set(&check_state.enough, 0);2089 init_waitqueue_head(&check_state.wait);2090 2091 rw_lock(0, c->root, c->root->level);2092 /*2093 * Run multiple threads to check btree nodes in parallel,2094 * if check_state.enough is non-zero, it means current2095 * running check threads are enough, unncessary to create2096 * more.2097 */2098 for (i = 0; i < check_state.total_threads; i++) {2099 /* fetch latest check_state.enough earlier */2100 smp_mb__before_atomic();2101 if (atomic_read(&check_state.enough))2102 break;2103 2104 check_state.infos[i].result = 0;2105 check_state.infos[i].state = &check_state;2106 2107 check_state.infos[i].thread =2108 kthread_run(bch_btree_check_thread,2109 &check_state.infos[i],2110 "bch_btrchk[%d]", i);2111 if (IS_ERR(check_state.infos[i].thread)) {2112 pr_err("fails to run thread bch_btrchk[%d]\n", i);2113 for (--i; i >= 0; i--)2114 kthread_stop(check_state.infos[i].thread);2115 ret = -ENOMEM;2116 goto out;2117 }2118 atomic_inc(&check_state.started);2119 }2120 2121 /*2122 * Must wait for all threads to stop.2123 */2124 wait_event(check_state.wait, atomic_read(&check_state.started) == 0);2125 2126 for (i = 0; i < check_state.total_threads; i++) {2127 if (check_state.infos[i].result) {2128 ret = check_state.infos[i].result;2129 goto out;2130 }2131 }2132 2133out:2134 rw_unlock(0, c->root);2135 return ret;2136}2137 2138void bch_initial_gc_finish(struct cache_set *c)2139{2140 struct cache *ca = c->cache;2141 struct bucket *b;2142 2143 bch_btree_gc_finish(c);2144 2145 mutex_lock(&c->bucket_lock);2146 2147 /*2148 * We need to put some unused buckets directly on the prio freelist in2149 * order to get the allocator thread started - it needs freed buckets in2150 * order to rewrite the prios and gens, and it needs to rewrite prios2151 * and gens in order to free buckets.2152 *2153 * This is only safe for buckets that have no live data in them, which2154 * there should always be some of.2155 */2156 for_each_bucket(b, ca) {2157 if (fifo_full(&ca->free[RESERVE_PRIO]) &&2158 fifo_full(&ca->free[RESERVE_BTREE]))2159 break;2160 2161 if (bch_can_invalidate_bucket(ca, b) &&2162 !GC_MARK(b)) {2163 __bch_invalidate_one_bucket(ca, b);2164 if (!fifo_push(&ca->free[RESERVE_PRIO],2165 b - ca->buckets))2166 fifo_push(&ca->free[RESERVE_BTREE],2167 b - ca->buckets);2168 }2169 }2170 2171 mutex_unlock(&c->bucket_lock);2172}2173 2174/* Btree insertion */2175 2176static bool btree_insert_key(struct btree *b, struct bkey *k,2177 struct bkey *replace_key)2178{2179 unsigned int status;2180 2181 BUG_ON(bkey_cmp(k, &b->key) > 0);2182 2183 status = bch_btree_insert_key(&b->keys, k, replace_key);2184 if (status != BTREE_INSERT_STATUS_NO_INSERT) {2185 bch_check_keys(&b->keys, "%u for %s", status,2186 replace_key ? "replace" : "insert");2187 2188 trace_bcache_btree_insert_key(b, k, replace_key != NULL,2189 status);2190 return true;2191 } else2192 return false;2193}2194 2195static size_t insert_u64s_remaining(struct btree *b)2196{2197 long ret = bch_btree_keys_u64s_remaining(&b->keys);2198 2199 /*2200 * Might land in the middle of an existing extent and have to split it2201 */2202 if (b->keys.ops->is_extents)2203 ret -= KEY_MAX_U64S;2204 2205 return max(ret, 0L);2206}2207 2208static bool bch_btree_insert_keys(struct btree *b, struct btree_op *op,2209 struct keylist *insert_keys,2210 struct bkey *replace_key)2211{2212 bool ret = false;2213 int oldsize = bch_count_data(&b->keys);2214 2215 while (!bch_keylist_empty(insert_keys)) {2216 struct bkey *k = insert_keys->keys;2217 2218 if (bkey_u64s(k) > insert_u64s_remaining(b))2219 break;2220 2221 if (bkey_cmp(k, &b->key) <= 0) {2222 if (!b->level)2223 bkey_put(b->c, k);2224 2225 ret |= btree_insert_key(b, k, replace_key);2226 bch_keylist_pop_front(insert_keys);2227 } else if (bkey_cmp(&START_KEY(k), &b->key) < 0) {2228 BKEY_PADDED(key) temp;2229 bkey_copy(&temp.key, insert_keys->keys);2230 2231 bch_cut_back(&b->key, &temp.key);2232 bch_cut_front(&b->key, insert_keys->keys);2233 2234 ret |= btree_insert_key(b, &temp.key, replace_key);2235 break;2236 } else {2237 break;2238 }2239 }2240 2241 if (!ret)2242 op->insert_collision = true;2243 2244 BUG_ON(!bch_keylist_empty(insert_keys) && b->level);2245 2246 BUG_ON(bch_count_data(&b->keys) < oldsize);2247 return ret;2248}2249 2250static int btree_split(struct btree *b, struct btree_op *op,2251 struct keylist *insert_keys,2252 struct bkey *replace_key)2253{2254 bool split;2255 struct btree *n1, *n2 = NULL, *n3 = NULL;2256 uint64_t start_time = local_clock();2257 struct closure cl;2258 struct keylist parent_keys;2259 2260 closure_init_stack(&cl);2261 bch_keylist_init(&parent_keys);2262 2263 if (btree_check_reserve(b, op)) {2264 if (!b->level)2265 return -EINTR;2266 else2267 WARN(1, "insufficient reserve for split\n");2268 }2269 2270 n1 = btree_node_alloc_replacement(b, op);2271 if (IS_ERR(n1))2272 goto err;2273 2274 split = set_blocks(btree_bset_first(n1),2275 block_bytes(n1->c->cache)) > (btree_blocks(b) * 4) / 5;2276 2277 if (split) {2278 unsigned int keys = 0;2279 2280 trace_bcache_btree_node_split(b, btree_bset_first(n1)->keys);2281 2282 n2 = bch_btree_node_alloc(b->c, op, b->level, b->parent);2283 if (IS_ERR(n2))2284 goto err_free1;2285 2286 if (!b->parent) {2287 n3 = bch_btree_node_alloc(b->c, op, b->level + 1, NULL);2288 if (IS_ERR(n3))2289 goto err_free2;2290 }2291 2292 mutex_lock(&n1->write_lock);2293 mutex_lock(&n2->write_lock);2294 2295 bch_btree_insert_keys(n1, op, insert_keys, replace_key);2296 2297 /*2298 * Has to be a linear search because we don't have an auxiliary2299 * search tree yet2300 */2301 2302 while (keys < (btree_bset_first(n1)->keys * 3) / 5)2303 keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1),2304 keys));2305 2306 bkey_copy_key(&n1->key,2307 bset_bkey_idx(btree_bset_first(n1), keys));2308 keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), keys));2309 2310 btree_bset_first(n2)->keys = btree_bset_first(n1)->keys - keys;2311 btree_bset_first(n1)->keys = keys;2312 2313 memcpy(btree_bset_first(n2)->start,2314 bset_bkey_last(btree_bset_first(n1)),2315 btree_bset_first(n2)->keys * sizeof(uint64_t));2316 2317 bkey_copy_key(&n2->key, &b->key);2318 2319 bch_keylist_add(&parent_keys, &n2->key);2320 bch_btree_node_write(n2, &cl);2321 mutex_unlock(&n2->write_lock);2322 rw_unlock(true, n2);2323 } else {2324 trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys);2325 2326 mutex_lock(&n1->write_lock);2327 bch_btree_insert_keys(n1, op, insert_keys, replace_key);2328 }2329 2330 bch_keylist_add(&parent_keys, &n1->key);2331 bch_btree_node_write(n1, &cl);2332 mutex_unlock(&n1->write_lock);2333 2334 if (n3) {2335 /* Depth increases, make a new root */2336 mutex_lock(&n3->write_lock);2337 bkey_copy_key(&n3->key, &MAX_KEY);2338 bch_btree_insert_keys(n3, op, &parent_keys, NULL);2339 bch_btree_node_write(n3, &cl);2340 mutex_unlock(&n3->write_lock);2341 2342 closure_sync(&cl);2343 bch_btree_set_root(n3);2344 rw_unlock(true, n3);2345 } else if (!b->parent) {2346 /* Root filled up but didn't need to be split */2347 closure_sync(&cl);2348 bch_btree_set_root(n1);2349 } else {2350 /* Split a non root node */2351 closure_sync(&cl);2352 make_btree_freeing_key(b, parent_keys.top);2353 bch_keylist_push(&parent_keys);2354 2355 bch_btree_insert_node(b->parent, op, &parent_keys, NULL, NULL);2356 BUG_ON(!bch_keylist_empty(&parent_keys));2357 }2358 2359 btree_node_free(b);2360 rw_unlock(true, n1);2361 2362 bch_time_stats_update(&b->c->btree_split_time, start_time);2363 2364 return 0;2365err_free2:2366 bkey_put(b->c, &n2->key);2367 btree_node_free(n2);2368 rw_unlock(true, n2);2369err_free1:2370 bkey_put(b->c, &n1->key);2371 btree_node_free(n1);2372 rw_unlock(true, n1);2373err:2374 WARN(1, "bcache: btree split failed (level %u)", b->level);2375 2376 if (n3 == ERR_PTR(-EAGAIN) ||2377 n2 == ERR_PTR(-EAGAIN) ||2378 n1 == ERR_PTR(-EAGAIN))2379 return -EAGAIN;2380 2381 return -ENOMEM;2382}2383 2384static int bch_btree_insert_node(struct btree *b, struct btree_op *op,2385 struct keylist *insert_keys,2386 atomic_t *journal_ref,2387 struct bkey *replace_key)2388{2389 struct closure cl;2390 2391 BUG_ON(b->level && replace_key);2392 2393 closure_init_stack(&cl);2394 2395 mutex_lock(&b->write_lock);2396 2397 if (write_block(b) != btree_bset_last(b) &&2398 b->keys.last_set_unwritten)2399 bch_btree_init_next(b); /* just wrote a set */2400 2401 if (bch_keylist_nkeys(insert_keys) > insert_u64s_remaining(b)) {2402 mutex_unlock(&b->write_lock);2403 goto split;2404 }2405 2406 BUG_ON(write_block(b) != btree_bset_last(b));2407 2408 if (bch_btree_insert_keys(b, op, insert_keys, replace_key)) {2409 if (!b->level)2410 bch_btree_leaf_dirty(b, journal_ref);2411 else2412 bch_btree_node_write(b, &cl);2413 }2414 2415 mutex_unlock(&b->write_lock);2416 2417 /* wait for btree node write if necessary, after unlock */2418 closure_sync(&cl);2419 2420 return 0;2421split:2422 if (current->bio_list) {2423 op->lock = b->c->root->level + 1;2424 return -EAGAIN;2425 } else if (op->lock <= b->c->root->level) {2426 op->lock = b->c->root->level + 1;2427 return -EINTR;2428 } else {2429 /* Invalidated all iterators */2430 int ret = btree_split(b, op, insert_keys, replace_key);2431 2432 if (bch_keylist_empty(insert_keys))2433 return 0;2434 else if (!ret)2435 return -EINTR;2436 return ret;2437 }2438}2439 2440int bch_btree_insert_check_key(struct btree *b, struct btree_op *op,2441 struct bkey *check_key)2442{2443 int ret = -EINTR;2444 uint64_t btree_ptr = b->key.ptr[0];2445 unsigned long seq = b->seq;2446 struct keylist insert;2447 bool upgrade = op->lock == -1;2448 2449 bch_keylist_init(&insert);2450 2451 if (upgrade) {2452 rw_unlock(false, b);2453 rw_lock(true, b, b->level);2454 2455 if (b->key.ptr[0] != btree_ptr ||2456 b->seq != seq + 1) {2457 op->lock = b->level;2458 goto out;2459 }2460 }2461 2462 SET_KEY_PTRS(check_key, 1);2463 get_random_bytes(&check_key->ptr[0], sizeof(uint64_t));2464 2465 SET_PTR_DEV(check_key, 0, PTR_CHECK_DEV);2466 2467 bch_keylist_add(&insert, check_key);2468 2469 ret = bch_btree_insert_node(b, op, &insert, NULL, NULL);2470 2471 BUG_ON(!ret && !bch_keylist_empty(&insert));2472out:2473 if (upgrade)2474 downgrade_write(&b->lock);2475 return ret;2476}2477 2478struct btree_insert_op {2479 struct btree_op op;2480 struct keylist *keys;2481 atomic_t *journal_ref;2482 struct bkey *replace_key;2483};2484 2485static int btree_insert_fn(struct btree_op *b_op, struct btree *b)2486{2487 struct btree_insert_op *op = container_of(b_op,2488 struct btree_insert_op, op);2489 2490 int ret = bch_btree_insert_node(b, &op->op, op->keys,2491 op->journal_ref, op->replace_key);2492 if (ret && !bch_keylist_empty(op->keys))2493 return ret;2494 else2495 return MAP_DONE;2496}2497 2498int bch_btree_insert(struct cache_set *c, struct keylist *keys,2499 atomic_t *journal_ref, struct bkey *replace_key)2500{2501 struct btree_insert_op op;2502 int ret = 0;2503 2504 BUG_ON(current->bio_list);2505 BUG_ON(bch_keylist_empty(keys));2506 2507 bch_btree_op_init(&op.op, 0);2508 op.keys = keys;2509 op.journal_ref = journal_ref;2510 op.replace_key = replace_key;2511 2512 while (!ret && !bch_keylist_empty(keys)) {2513 op.op.lock = 0;2514 ret = bch_btree_map_leaf_nodes(&op.op, c,2515 &START_KEY(keys->keys),2516 btree_insert_fn);2517 }2518 2519 if (ret) {2520 struct bkey *k;2521 2522 pr_err("error %i\n", ret);2523 2524 while ((k = bch_keylist_pop(keys)))2525 bkey_put(c, k);2526 } else if (op.op.insert_collision)2527 ret = -ESRCH;2528 2529 return ret;2530}2531 2532void bch_btree_set_root(struct btree *b)2533{2534 unsigned int i;2535 struct closure cl;2536 2537 closure_init_stack(&cl);2538 2539 trace_bcache_btree_set_root(b);2540 2541 BUG_ON(!b->written);2542 2543 for (i = 0; i < KEY_PTRS(&b->key); i++)2544 BUG_ON(PTR_BUCKET(b->c, &b->key, i)->prio != BTREE_PRIO);2545 2546 mutex_lock(&b->c->bucket_lock);2547 list_del_init(&b->list);2548 mutex_unlock(&b->c->bucket_lock);2549 2550 b->c->root = b;2551 2552 bch_journal_meta(b->c, &cl);2553 closure_sync(&cl);2554}2555 2556/* Map across nodes or keys */2557 2558static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op,2559 struct bkey *from,2560 btree_map_nodes_fn *fn, int flags)2561{2562 int ret = MAP_CONTINUE;2563 2564 if (b->level) {2565 struct bkey *k;2566 struct btree_iter iter;2567 2568 min_heap_init(&iter.heap, NULL, MAX_BSETS);2569 bch_btree_iter_init(&b->keys, &iter, from);2570 2571 while ((k = bch_btree_iter_next_filter(&iter, &b->keys,2572 bch_ptr_bad))) {2573 ret = bcache_btree(map_nodes_recurse, k, b,2574 op, from, fn, flags);2575 from = NULL;2576 2577 if (ret != MAP_CONTINUE)2578 return ret;2579 }2580 }2581 2582 if (!b->level || flags == MAP_ALL_NODES)2583 ret = fn(op, b);2584 2585 return ret;2586}2587 2588int __bch_btree_map_nodes(struct btree_op *op, struct cache_set *c,2589 struct bkey *from, btree_map_nodes_fn *fn, int flags)2590{2591 return bcache_btree_root(map_nodes_recurse, c, op, from, fn, flags);2592}2593 2594int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op,2595 struct bkey *from, btree_map_keys_fn *fn,2596 int flags)2597{2598 int ret = MAP_CONTINUE;2599 struct bkey *k;2600 struct btree_iter iter;2601 2602 min_heap_init(&iter.heap, NULL, MAX_BSETS);2603 bch_btree_iter_init(&b->keys, &iter, from);2604 2605 while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) {2606 ret = !b->level2607 ? fn(op, b, k)2608 : bcache_btree(map_keys_recurse, k,2609 b, op, from, fn, flags);2610 from = NULL;2611 2612 if (ret != MAP_CONTINUE)2613 return ret;2614 }2615 2616 if (!b->level && (flags & MAP_END_KEY))2617 ret = fn(op, b, &KEY(KEY_INODE(&b->key),2618 KEY_OFFSET(&b->key), 0));2619 2620 return ret;2621}2622 2623int bch_btree_map_keys(struct btree_op *op, struct cache_set *c,2624 struct bkey *from, btree_map_keys_fn *fn, int flags)2625{2626 return bcache_btree_root(map_keys_recurse, c, op, from, fn, flags);2627}2628 2629/* Keybuf code */2630 2631static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r)2632{2633 /* Overlapping keys compare equal */2634 if (bkey_cmp(&l->key, &START_KEY(&r->key)) <= 0)2635 return -1;2636 if (bkey_cmp(&START_KEY(&l->key), &r->key) >= 0)2637 return 1;2638 return 0;2639}2640 2641static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l,2642 struct keybuf_key *r)2643{2644 return clamp_t(int64_t, bkey_cmp(&l->key, &r->key), -1, 1);2645}2646 2647struct refill {2648 struct btree_op op;2649 unsigned int nr_found;2650 struct keybuf *buf;2651 struct bkey *end;2652 keybuf_pred_fn *pred;2653};2654 2655static int refill_keybuf_fn(struct btree_op *op, struct btree *b,2656 struct bkey *k)2657{2658 struct refill *refill = container_of(op, struct refill, op);2659 struct keybuf *buf = refill->buf;2660 int ret = MAP_CONTINUE;2661 2662 if (bkey_cmp(k, refill->end) > 0) {2663 ret = MAP_DONE;2664 goto out;2665 }2666 2667 if (!KEY_SIZE(k)) /* end key */2668 goto out;2669 2670 if (refill->pred(buf, k)) {2671 struct keybuf_key *w;2672 2673 spin_lock(&buf->lock);2674 2675 w = array_alloc(&buf->freelist);2676 if (!w) {2677 spin_unlock(&buf->lock);2678 return MAP_DONE;2679 }2680 2681 w->private = NULL;2682 bkey_copy(&w->key, k);2683 2684 if (RB_INSERT(&buf->keys, w, node, keybuf_cmp))2685 array_free(&buf->freelist, w);2686 else2687 refill->nr_found++;2688 2689 if (array_freelist_empty(&buf->freelist))2690 ret = MAP_DONE;2691 2692 spin_unlock(&buf->lock);2693 }2694out:2695 buf->last_scanned = *k;2696 return ret;2697}2698 2699void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf,2700 struct bkey *end, keybuf_pred_fn *pred)2701{2702 struct bkey start = buf->last_scanned;2703 struct refill refill;2704 2705 cond_resched();2706 2707 bch_btree_op_init(&refill.op, -1);2708 refill.nr_found = 0;2709 refill.buf = buf;2710 refill.end = end;2711 refill.pred = pred;2712 2713 bch_btree_map_keys(&refill.op, c, &buf->last_scanned,2714 refill_keybuf_fn, MAP_END_KEY);2715 2716 trace_bcache_keyscan(refill.nr_found,2717 KEY_INODE(&start), KEY_OFFSET(&start),2718 KEY_INODE(&buf->last_scanned),2719 KEY_OFFSET(&buf->last_scanned));2720 2721 spin_lock(&buf->lock);2722 2723 if (!RB_EMPTY_ROOT(&buf->keys)) {2724 struct keybuf_key *w;2725 2726 w = RB_FIRST(&buf->keys, struct keybuf_key, node);2727 buf->start = START_KEY(&w->key);2728 2729 w = RB_LAST(&buf->keys, struct keybuf_key, node);2730 buf->end = w->key;2731 } else {2732 buf->start = MAX_KEY;2733 buf->end = MAX_KEY;2734 }2735 2736 spin_unlock(&buf->lock);2737}2738 2739static void __bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w)2740{2741 rb_erase(&w->node, &buf->keys);2742 array_free(&buf->freelist, w);2743}2744 2745void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w)2746{2747 spin_lock(&buf->lock);2748 __bch_keybuf_del(buf, w);2749 spin_unlock(&buf->lock);2750}2751 2752bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start,2753 struct bkey *end)2754{2755 bool ret = false;2756 struct keybuf_key *p, *w, s;2757 2758 s.key = *start;2759 2760 if (bkey_cmp(end, &buf->start) <= 0 ||2761 bkey_cmp(start, &buf->end) >= 0)2762 return false;2763 2764 spin_lock(&buf->lock);2765 w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp);2766 2767 while (w && bkey_cmp(&START_KEY(&w->key), end) < 0) {2768 p = w;2769 w = RB_NEXT(w, node);2770 2771 if (p->private)2772 ret = true;2773 else2774 __bch_keybuf_del(buf, p);2775 }2776 2777 spin_unlock(&buf->lock);2778 return ret;2779}2780 2781struct keybuf_key *bch_keybuf_next(struct keybuf *buf)2782{2783 struct keybuf_key *w;2784 2785 spin_lock(&buf->lock);2786 2787 w = RB_FIRST(&buf->keys, struct keybuf_key, node);2788 2789 while (w && w->private)2790 w = RB_NEXT(w, node);2791 2792 if (w)2793 w->private = ERR_PTR(-EINTR);2794 2795 spin_unlock(&buf->lock);2796 return w;2797}2798 2799struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c,2800 struct keybuf *buf,2801 struct bkey *end,2802 keybuf_pred_fn *pred)2803{2804 struct keybuf_key *ret;2805 2806 while (1) {2807 ret = bch_keybuf_next(buf);2808 if (ret)2809 break;2810 2811 if (bkey_cmp(&buf->last_scanned, end) >= 0) {2812 pr_debug("scan finished\n");2813 break;2814 }2815 2816 bch_refill_keybuf(c, buf, end, pred);2817 }2818 2819 return ret;2820}2821 2822void bch_keybuf_init(struct keybuf *buf)2823{2824 buf->last_scanned = MAX_KEY;2825 buf->keys = RB_ROOT;2826 2827 spin_lock_init(&buf->lock);2828 array_allocator_init(&buf->freelist);2829}2830 2831void bch_btree_exit(void)2832{2833 if (btree_io_wq)2834 destroy_workqueue(btree_io_wq);2835}2836 2837int __init bch_btree_init(void)2838{2839 btree_io_wq = alloc_workqueue("bch_btree_io", WQ_MEM_RECLAIM, 0);2840 if (!btree_io_wq)2841 return -ENOMEM;2842 2843 return 0;2844}2845