btree.c 56.7 KB
Newer Older
K
Kent Overstreet 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
/*
 * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>
 *
 * Uses a block device as cache for other block devices; optimized for SSDs.
 * All allocation is done in buckets, which should match the erase block size
 * of the device.
 *
 * Buckets containing cached data are kept on a heap sorted by priority;
 * bucket priority is increased on cache hit, and periodically all the buckets
 * on the heap have their priority scaled down. This currently is just used as
 * an LRU but in the future should allow for more intelligent heuristics.
 *
 * Buckets have an 8 bit counter; freeing is accomplished by incrementing the
 * counter. Garbage collection is used to remove stale pointers.
 *
 * Indexing is done via a btree; nodes are not necessarily fully sorted, rather
 * as keys are inserted we only sort the pages that have not yet been written.
 * When garbage collection is run, we resort the entire node.
 *
 * All configuration is done via sysfs; see Documentation/bcache.txt.
 */

#include "bcache.h"
#include "btree.h"
#include "debug.h"
26
#include "extents.h"
K
Kent Overstreet 已提交
27 28 29 30

#include <linux/slab.h>
#include <linux/bitops.h>
#include <linux/hash.h>
K
Kent Overstreet 已提交
31
#include <linux/kthread.h>
32
#include <linux/prefetch.h>
K
Kent Overstreet 已提交
33 34
#include <linux/random.h>
#include <linux/rcupdate.h>
35
#include <linux/sched/clock.h>
K
Kent Overstreet 已提交
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
#include <trace/events/bcache.h>

/*
 * Todo:
 * register_bcache: Return errors out to userspace correctly
 *
 * Writeback: don't undirty key until after a cache flush
 *
 * Create an iterator for key pointers
 *
 * On btree write error, mark bucket such that it won't be freed from the cache
 *
 * Journalling:
 *   Check for bad keys in replay
 *   Propagate barriers
 *   Refcount journal entries in journal_replay
 *
 * Garbage collection:
 *   Finish incremental gc
 *   Gc should free old UUIDs, data for invalid UUIDs
 *
 * Provide a way to list backing device UUIDs we have data cached for, and
 * probably how long it's been since we've seen them, and a way to invalidate
 * dirty data for devices that will never be attached again
 *
 * Keep 1 min/5 min/15 min statistics of how busy a block device has been, so
 * that based on that and how much dirty data we have we can keep writeback
 * from being starved
 *
 * Add a tracepoint or somesuch to watch for writeback starvation
 *
 * When btree depth > 1 and splitting an interior node, we have to make sure
 * alloc_bucket() cannot fail. This should be true but is not completely
 * obvious.
 *
 * Plugging?
 *
 * If data write is less than hard sector size of ssd, round up offset in open
 * bucket to the next whole sector
 *
 * Superblock needs to be fleshed out for multiple cache devices
 *
 * Add a sysfs tunable for the number of writeback IOs in flight
 *
 * Add a sysfs tunable for the number of open data buckets
 *
 * IO tracking: Can we track when one process is doing io on behalf of another?
 * IO tracking: Don't use just an average, weigh more recent stuff higher
 *
 * Test module load/unload
 */

#define MAX_NEED_GC		64
#define MAX_SAVE_PRIO		72

#define PTR_DIRTY_BIT		(((uint64_t) 1 << 36))

#define PTR_HASH(c, k)							\
	(((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0))

96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
#define insert_lock(s, b)	((b)->level <= (s)->lock)

/*
 * These macros are for recursing down the btree - they handle the details of
 * locking and looking up nodes in the cache for you. They're best treated as
 * mere syntax when reading code that uses them.
 *
 * op->lock determines whether we take a read or a write lock at a given depth.
 * If you've got a read lock and find that you need a write lock (i.e. you're
 * going to have to split), set op->lock and return -EINTR; btree_root() will
 * call you again and you'll have the correct lock.
 */

/**
 * btree - recurse down the btree on a specified key
 * @fn:		function to call, which will be passed the child node
 * @key:	key to recurse on
 * @b:		parent btree node
 * @op:		pointer to struct btree_op
 */
#define btree(fn, key, b, op, ...)					\
({									\
	int _r, l = (b)->level - 1;					\
	bool _w = l <= (op)->lock;					\
120 121
	struct btree *_child = bch_btree_node_get((b)->c, op, key, l,	\
						  _w, b);		\
122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
	if (!IS_ERR(_child)) {						\
		_r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__);	\
		rw_unlock(_w, _child);					\
	} else								\
		_r = PTR_ERR(_child);					\
	_r;								\
})

/**
 * btree_root - call a function on the root of the btree
 * @fn:		function to call, which will be passed the child node
 * @c:		cache set
 * @op:		pointer to struct btree_op
 */
#define btree_root(fn, c, op, ...)					\
({									\
	int _r = -EINTR;						\
	do {								\
		struct btree *_b = (c)->root;				\
		bool _w = insert_lock(op, _b);				\
		rw_lock(_w, _b, _b->level);				\
		if (_b == (c)->root &&					\
		    _w == insert_lock(op, _b)) {			\
			_r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__);	\
		}							\
		rw_unlock(_w, _b);					\
148
		bch_cannibalize_unlock(c);				\
149 150
		if (_r == -EINTR)					\
			schedule();					\
151 152
	} while (_r == -EINTR);						\
									\
153
	finish_wait(&(c)->btree_cache_wait, &(op)->wait);		\
154 155 156
	_r;								\
})

K
Kent Overstreet 已提交
157 158 159 160 161
static inline struct bset *write_block(struct btree *b)
{
	return ((void *) btree_bset_first(b)) + b->written * block_bytes(b->c);
}

K
Kent Overstreet 已提交
162 163 164 165 166 167 168 169 170 171 172 173 174 175
static void bch_btree_init_next(struct btree *b)
{
	/* If not a leaf node, always sort */
	if (b->level && b->keys.nsets)
		bch_btree_sort(&b->keys, &b->c->sort);
	else
		bch_btree_sort_lazy(&b->keys, &b->c->sort);

	if (b->written < btree_blocks(b))
		bch_bset_init_next(&b->keys, write_block(b),
				   bset_magic(&b->c->sb));

}

K
Kent Overstreet 已提交
176 177
/* Btree key manipulation */

178
void bkey_put(struct cache_set *c, struct bkey *k)
179 180 181 182 183 184 185 186
{
	unsigned i;

	for (i = 0; i < KEY_PTRS(k); i++)
		if (ptr_available(c, k, i))
			atomic_dec_bug(&PTR_BUCKET(c, k, i)->pin);
}

K
Kent Overstreet 已提交
187 188 189 190 191
/* Btree IO */

static uint64_t btree_csum_set(struct btree *b, struct bset *i)
{
	uint64_t crc = b->key.ptr[0];
K
Kent Overstreet 已提交
192
	void *data = (void *) i + 8, *end = bset_bkey_last(i);
K
Kent Overstreet 已提交
193

194
	crc = bch_crc64_update(crc, data, end - data);
K
Kent Overstreet 已提交
195
	return crc ^ 0xffffffffffffffffULL;
K
Kent Overstreet 已提交
196 197
}

198
void bch_btree_node_read_done(struct btree *b)
K
Kent Overstreet 已提交
199 200
{
	const char *err = "bad btree header";
201
	struct bset *i = btree_bset_first(b);
K
Kent Overstreet 已提交
202
	struct btree_iter *iter;
K
Kent Overstreet 已提交
203

204
	iter = mempool_alloc(b->c->fill_iter, GFP_NOIO);
K
Kent Overstreet 已提交
205
	iter->size = b->c->sb.bucket_size / b->c->sb.block_size;
K
Kent Overstreet 已提交
206 207
	iter->used = 0;

K
Kent Overstreet 已提交
208
#ifdef CONFIG_BCACHE_DEBUG
209
	iter->b = &b->keys;
K
Kent Overstreet 已提交
210 211
#endif

K
Kent Overstreet 已提交
212
	if (!i->seq)
K
Kent Overstreet 已提交
213 214 215
		goto err;

	for (;
K
Kent Overstreet 已提交
216
	     b->written < btree_blocks(b) && i->seq == b->keys.set[0].data->seq;
K
Kent Overstreet 已提交
217 218 219 220 221 222
	     i = write_block(b)) {
		err = "unsupported bset version";
		if (i->version > BCACHE_BSET_VERSION)
			goto err;

		err = "bad btree header";
223 224
		if (b->written + set_blocks(i, block_bytes(b->c)) >
		    btree_blocks(b))
K
Kent Overstreet 已提交
225 226 227
			goto err;

		err = "bad magic";
228
		if (i->magic != bset_magic(&b->c->sb))
K
Kent Overstreet 已提交
229 230 231 232 233 234 235 236 237 238 239 240 241 242 243
			goto err;

		err = "bad checksum";
		switch (i->version) {
		case 0:
			if (i->csum != csum_set(i))
				goto err;
			break;
		case BCACHE_BSET_VERSION:
			if (i->csum != btree_csum_set(b, i))
				goto err;
			break;
		}

		err = "empty set";
K
Kent Overstreet 已提交
244
		if (i != b->keys.set[0].data && !i->keys)
K
Kent Overstreet 已提交
245 246
			goto err;

K
Kent Overstreet 已提交
247
		bch_btree_iter_push(iter, i->start, bset_bkey_last(i));
K
Kent Overstreet 已提交
248

249
		b->written += set_blocks(i, block_bytes(b->c));
K
Kent Overstreet 已提交
250 251 252 253
	}

	err = "corrupted btree";
	for (i = write_block(b);
K
Kent Overstreet 已提交
254
	     bset_sector_offset(&b->keys, i) < KEY_SIZE(&b->key);
K
Kent Overstreet 已提交
255
	     i = ((void *) i) + block_bytes(b->c))
K
Kent Overstreet 已提交
256
		if (i->seq == b->keys.set[0].data->seq)
K
Kent Overstreet 已提交
257 258
			goto err;

K
Kent Overstreet 已提交
259
	bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort);
K
Kent Overstreet 已提交
260

K
Kent Overstreet 已提交
261
	i = b->keys.set[0].data;
K
Kent Overstreet 已提交
262
	err = "short btree key";
K
Kent Overstreet 已提交
263 264
	if (b->keys.set[0].size &&
	    bkey_cmp(&b->key, &b->keys.set[0].end) < 0)
K
Kent Overstreet 已提交
265 266 267
		goto err;

	if (b->written < btree_blocks(b))
K
Kent Overstreet 已提交
268 269
		bch_bset_init_next(&b->keys, write_block(b),
				   bset_magic(&b->c->sb));
K
Kent Overstreet 已提交
270
out:
K
Kent Overstreet 已提交
271 272
	mempool_free(iter, b->c->fill_iter);
	return;
K
Kent Overstreet 已提交
273 274
err:
	set_btree_node_io_error(b);
K
Kent Overstreet 已提交
275
	bch_cache_set_error(b->c, "%s at bucket %zu, block %u, %u keys",
K
Kent Overstreet 已提交
276
			    err, PTR_BUCKET_NR(b->c, &b->key, 0),
K
Kent Overstreet 已提交
277
			    bset_block_offset(b, i), i->keys);
K
Kent Overstreet 已提交
278 279 280
	goto out;
}

281
static void btree_node_read_endio(struct bio *bio)
K
Kent Overstreet 已提交
282
{
K
Kent Overstreet 已提交
283 284 285
	struct closure *cl = bio->bi_private;
	closure_put(cl);
}
K
Kent Overstreet 已提交
286

287
static void bch_btree_node_read(struct btree *b)
K
Kent Overstreet 已提交
288 289 290 291
{
	uint64_t start_time = local_clock();
	struct closure cl;
	struct bio *bio;
K
Kent Overstreet 已提交
292

K
Kent Overstreet 已提交
293 294
	trace_bcache_btree_read(b);

K
Kent Overstreet 已提交
295
	closure_init_stack(&cl);
K
Kent Overstreet 已提交
296

K
Kent Overstreet 已提交
297
	bio = bch_bbio_alloc(b->c);
298
	bio->bi_iter.bi_size = KEY_SIZE(&b->key) << 9;
K
Kent Overstreet 已提交
299 300
	bio->bi_end_io	= btree_node_read_endio;
	bio->bi_private	= &cl;
301
	bio->bi_opf = REQ_OP_READ | REQ_META;
K
Kent Overstreet 已提交
302

K
Kent Overstreet 已提交
303
	bch_bio_map(bio, b->keys.set[0].data);
K
Kent Overstreet 已提交
304

K
Kent Overstreet 已提交
305 306
	bch_submit_bbio(bio, b->c, &b->key, 0);
	closure_sync(&cl);
K
Kent Overstreet 已提交
307

308
	if (bio->bi_error)
K
Kent Overstreet 已提交
309 310 311 312 313 314 315 316 317 318 319 320
		set_btree_node_io_error(b);

	bch_bbio_free(bio, b->c);

	if (btree_node_io_error(b))
		goto err;

	bch_btree_node_read_done(b);
	bch_time_stats_update(&b->c->btree_read_time, start_time);

	return;
err:
321
	bch_cache_set_error(b->c, "io error reading bucket %zu",
K
Kent Overstreet 已提交
322
			    PTR_BUCKET_NR(b->c, &b->key, 0));
K
Kent Overstreet 已提交
323 324 325 326 327 328
}

static void btree_complete_write(struct btree *b, struct btree_write *w)
{
	if (w->prio_blocked &&
	    !atomic_sub_return(w->prio_blocked, &b->c->prio_blocked))
329
		wake_up_allocators(b->c);
K
Kent Overstreet 已提交
330 331 332 333 334 335 336 337 338 339

	if (w->journal) {
		atomic_dec_bug(w->journal);
		__closure_wake_up(&b->c->journal.wait);
	}

	w->prio_blocked	= 0;
	w->journal	= NULL;
}

340 341 342 343 344 345 346
static void btree_node_write_unlock(struct closure *cl)
{
	struct btree *b = container_of(cl, struct btree, io);

	up(&b->io_mutex);
}

K
Kent Overstreet 已提交
347
static void __btree_node_write_done(struct closure *cl)
K
Kent Overstreet 已提交
348
{
349
	struct btree *b = container_of(cl, struct btree, io);
K
Kent Overstreet 已提交
350 351 352 353 354 355 356
	struct btree_write *w = btree_prev_write(b);

	bch_bbio_free(b->bio, b->c);
	b->bio = NULL;
	btree_complete_write(b, w);

	if (btree_node_dirty(b))
K
Kent Overstreet 已提交
357
		schedule_delayed_work(&b->work, 30 * HZ);
K
Kent Overstreet 已提交
358

359
	closure_return_with_destructor(cl, btree_node_write_unlock);
K
Kent Overstreet 已提交
360 361
}

K
Kent Overstreet 已提交
362
static void btree_node_write_done(struct closure *cl)
K
Kent Overstreet 已提交
363
{
364
	struct btree *b = container_of(cl, struct btree, io);
K
Kent Overstreet 已提交
365

366
	bio_free_pages(b->bio);
K
Kent Overstreet 已提交
367
	__btree_node_write_done(cl);
K
Kent Overstreet 已提交
368 369
}

370
static void btree_node_write_endio(struct bio *bio)
K
Kent Overstreet 已提交
371 372
{
	struct closure *cl = bio->bi_private;
373
	struct btree *b = container_of(cl, struct btree, io);
K
Kent Overstreet 已提交
374

375
	if (bio->bi_error)
K
Kent Overstreet 已提交
376 377
		set_btree_node_io_error(b);

378
	bch_bbio_count_io_errors(b->c, bio, bio->bi_error, "writing btree");
K
Kent Overstreet 已提交
379 380 381 382
	closure_put(cl);
}

static void do_btree_node_write(struct btree *b)
K
Kent Overstreet 已提交
383
{
384
	struct closure *cl = &b->io;
385
	struct bset *i = btree_bset_last(b);
K
Kent Overstreet 已提交
386 387 388 389 390
	BKEY_PADDED(key) k;

	i->version	= BCACHE_BSET_VERSION;
	i->csum		= btree_csum_set(b, i);

K
Kent Overstreet 已提交
391 392 393 394
	BUG_ON(b->bio);
	b->bio = bch_bbio_alloc(b->c);

	b->bio->bi_end_io	= btree_node_write_endio;
K
Kent Overstreet 已提交
395
	b->bio->bi_private	= cl;
396
	b->bio->bi_iter.bi_size	= roundup(set_bytes(i), block_bytes(b->c));
397
	b->bio->bi_opf		= REQ_OP_WRITE | REQ_META | REQ_FUA;
398
	bch_bio_map(b->bio, i);
K
Kent Overstreet 已提交
399

K
Kent Overstreet 已提交
400 401 402 403 404 405 406 407 408 409 410 411 412 413 414
	/*
	 * If we're appending to a leaf node, we don't technically need FUA -
	 * this write just needs to be persisted before the next journal write,
	 * which will be marked FLUSH|FUA.
	 *
	 * Similarly if we're writing a new btree root - the pointer is going to
	 * be in the next journal entry.
	 *
	 * But if we're writing a new btree node (that isn't a root) or
	 * appending to a non leaf btree node, we need either FUA or a flush
	 * when we write the parent with the new pointer. FUA is cheaper than a
	 * flush, and writes appending to leaf nodes aren't blocking anything so
	 * just make all btree node writes FUA to keep things sane.
	 */

K
Kent Overstreet 已提交
415
	bkey_copy(&k.key, &b->key);
416
	SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) +
K
Kent Overstreet 已提交
417
		       bset_sector_offset(&b->keys, i));
K
Kent Overstreet 已提交
418

419
	if (!bio_alloc_pages(b->bio, __GFP_NOWARN|GFP_NOWAIT)) {
K
Kent Overstreet 已提交
420 421 422 423
		int j;
		struct bio_vec *bv;
		void *base = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1));

424
		bio_for_each_segment_all(bv, b->bio, j)
K
Kent Overstreet 已提交
425 426 427 428 429
			memcpy(page_address(bv->bv_page),
			       base + j * PAGE_SIZE, PAGE_SIZE);

		bch_submit_bbio(b->bio, b->c, &k.key, 0);

K
Kent Overstreet 已提交
430
		continue_at(cl, btree_node_write_done, NULL);
K
Kent Overstreet 已提交
431 432
	} else {
		b->bio->bi_vcnt = 0;
433
		bch_bio_map(b->bio, i);
K
Kent Overstreet 已提交
434 435 436 437

		bch_submit_bbio(b->bio, b->c, &k.key, 0);

		closure_sync(cl);
438
		continue_at_nobarrier(cl, __btree_node_write_done, NULL);
K
Kent Overstreet 已提交
439 440 441
	}
}

K
Kent Overstreet 已提交
442
void __bch_btree_node_write(struct btree *b, struct closure *parent)
K
Kent Overstreet 已提交
443
{
444
	struct bset *i = btree_bset_last(b);
K
Kent Overstreet 已提交
445

K
Kent Overstreet 已提交
446 447
	lockdep_assert_held(&b->write_lock);

K
Kent Overstreet 已提交
448 449
	trace_bcache_btree_write(b);

K
Kent Overstreet 已提交
450
	BUG_ON(current->bio_list);
K
Kent Overstreet 已提交
451 452
	BUG_ON(b->written >= btree_blocks(b));
	BUG_ON(b->written && !i->keys);
453
	BUG_ON(btree_bset_first(b)->seq != i->seq);
454
	bch_check_keys(&b->keys, "writing");
K
Kent Overstreet 已提交
455 456 457

	cancel_delayed_work(&b->work);

K
Kent Overstreet 已提交
458
	/* If caller isn't waiting for write, parent refcount is cache set */
459 460
	down(&b->io_mutex);
	closure_init(&b->io, parent ?: &b->c->cl);
K
Kent Overstreet 已提交
461

K
Kent Overstreet 已提交
462 463 464
	clear_bit(BTREE_NODE_dirty,	 &b->flags);
	change_bit(BTREE_NODE_write_idx, &b->flags);

K
Kent Overstreet 已提交
465
	do_btree_node_write(b);
K
Kent Overstreet 已提交
466

467
	atomic_long_add(set_blocks(i, block_bytes(b->c)) * b->c->sb.block_size,
K
Kent Overstreet 已提交
468 469
			&PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written);

K
Kent Overstreet 已提交
470
	b->written += set_blocks(i, block_bytes(b->c));
K
Kent Overstreet 已提交
471
}
K
Kent Overstreet 已提交
472

K
Kent Overstreet 已提交
473 474 475 476 477 478 479
void bch_btree_node_write(struct btree *b, struct closure *parent)
{
	unsigned nsets = b->keys.nsets;

	lockdep_assert_held(&b->lock);

	__bch_btree_node_write(b, parent);
K
Kent Overstreet 已提交
480

481 482 483 484
	/*
	 * do verify if there was more than one set initially (i.e. we did a
	 * sort) and we sorted down to a single set:
	 */
K
Kent Overstreet 已提交
485
	if (nsets && !b->keys.nsets)
486 487
		bch_btree_verify(b);

K
Kent Overstreet 已提交
488
	bch_btree_init_next(b);
K
Kent Overstreet 已提交
489 490
}

491 492 493 494 495
static void bch_btree_node_write_sync(struct btree *b)
{
	struct closure cl;

	closure_init_stack(&cl);
K
Kent Overstreet 已提交
496 497

	mutex_lock(&b->write_lock);
498
	bch_btree_node_write(b, &cl);
K
Kent Overstreet 已提交
499 500
	mutex_unlock(&b->write_lock);

501 502 503
	closure_sync(&cl);
}

K
Kent Overstreet 已提交
504
static void btree_node_write_work(struct work_struct *w)
K
Kent Overstreet 已提交
505 506 507
{
	struct btree *b = container_of(to_delayed_work(w), struct btree, work);

K
Kent Overstreet 已提交
508
	mutex_lock(&b->write_lock);
K
Kent Overstreet 已提交
509
	if (btree_node_dirty(b))
K
Kent Overstreet 已提交
510 511
		__bch_btree_node_write(b, NULL);
	mutex_unlock(&b->write_lock);
K
Kent Overstreet 已提交
512 513
}

K
Kent Overstreet 已提交
514
static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref)
K
Kent Overstreet 已提交
515
{
516
	struct bset *i = btree_bset_last(b);
K
Kent Overstreet 已提交
517 518
	struct btree_write *w = btree_current_write(b);

K
Kent Overstreet 已提交
519 520
	lockdep_assert_held(&b->write_lock);

K
Kent Overstreet 已提交
521 522
	BUG_ON(!b->written);
	BUG_ON(!i->keys);
K
Kent Overstreet 已提交
523

K
Kent Overstreet 已提交
524
	if (!btree_node_dirty(b))
K
Kent Overstreet 已提交
525
		schedule_delayed_work(&b->work, 30 * HZ);
K
Kent Overstreet 已提交
526

K
Kent Overstreet 已提交
527
	set_btree_node_dirty(b);
K
Kent Overstreet 已提交
528

K
Kent Overstreet 已提交
529
	if (journal_ref) {
K
Kent Overstreet 已提交
530
		if (w->journal &&
K
Kent Overstreet 已提交
531
		    journal_pin_cmp(b->c, w->journal, journal_ref)) {
K
Kent Overstreet 已提交
532 533 534 535 536
			atomic_dec_bug(w->journal);
			w->journal = NULL;
		}

		if (!w->journal) {
K
Kent Overstreet 已提交
537
			w->journal = journal_ref;
K
Kent Overstreet 已提交
538 539 540 541 542
			atomic_inc(w->journal);
		}
	}

	/* Force write if set is too big */
K
Kent Overstreet 已提交
543 544 545
	if (set_bytes(i) > PAGE_SIZE - 48 &&
	    !current->bio_list)
		bch_btree_node_write(b, NULL);
K
Kent Overstreet 已提交
546 547 548 549 550 551 552 553 554 555
}

/*
 * Btree in memory cache - allocation/freeing
 * mca -> memory cache
 */

#define mca_reserve(c)	(((c->root && c->root->level)		\
			  ? c->root->level : 1) * 8 + 16)
#define mca_can_free(c)						\
556
	max_t(int, 0, c->btree_cache_used - mca_reserve(c))
K
Kent Overstreet 已提交
557 558 559

static void mca_data_free(struct btree *b)
{
560
	BUG_ON(b->io_mutex.count != 1);
K
Kent Overstreet 已提交
561

K
Kent Overstreet 已提交
562
	bch_btree_keys_free(&b->keys);
K
Kent Overstreet 已提交
563

564
	b->c->btree_cache_used--;
565
	list_move(&b->list, &b->c->btree_cache_freed);
K
Kent Overstreet 已提交
566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583
}

static void mca_bucket_free(struct btree *b)
{
	BUG_ON(btree_node_dirty(b));

	b->key.ptr[0] = 0;
	hlist_del_init_rcu(&b->hash);
	list_move(&b->list, &b->c->btree_cache_freeable);
}

static unsigned btree_order(struct bkey *k)
{
	return ilog2(KEY_SIZE(k) / PAGE_SECTORS ?: 1);
}

static void mca_data_alloc(struct btree *b, struct bkey *k, gfp_t gfp)
{
K
Kent Overstreet 已提交
584
	if (!bch_btree_keys_alloc(&b->keys,
585 586 587 588
				  max_t(unsigned,
					ilog2(b->c->btree_pages),
					btree_order(k)),
				  gfp)) {
589
		b->c->btree_cache_used++;
590 591 592 593
		list_move(&b->list, &b->c->btree_cache);
	} else {
		list_move(&b->list, &b->c->btree_cache_freed);
	}
K
Kent Overstreet 已提交
594 595 596 597 598 599 600 601 602 603 604
}

static struct btree *mca_bucket_alloc(struct cache_set *c,
				      struct bkey *k, gfp_t gfp)
{
	struct btree *b = kzalloc(sizeof(struct btree), gfp);
	if (!b)
		return NULL;

	init_rwsem(&b->lock);
	lockdep_set_novalidate_class(&b->lock);
K
Kent Overstreet 已提交
605 606
	mutex_init(&b->write_lock);
	lockdep_set_novalidate_class(&b->write_lock);
K
Kent Overstreet 已提交
607
	INIT_LIST_HEAD(&b->list);
K
Kent Overstreet 已提交
608
	INIT_DELAYED_WORK(&b->work, btree_node_write_work);
K
Kent Overstreet 已提交
609
	b->c = c;
610
	sema_init(&b->io_mutex, 1);
K
Kent Overstreet 已提交
611 612 613 614 615

	mca_data_alloc(b, k, gfp);
	return b;
}

616
static int mca_reap(struct btree *b, unsigned min_order, bool flush)
K
Kent Overstreet 已提交
617
{
618 619 620
	struct closure cl;

	closure_init_stack(&cl);
K
Kent Overstreet 已提交
621 622 623 624 625
	lockdep_assert_held(&b->c->bucket_lock);

	if (!down_write_trylock(&b->lock))
		return -ENOMEM;

K
Kent Overstreet 已提交
626
	BUG_ON(btree_node_dirty(b) && !b->keys.set[0].data);
627

K
Kent Overstreet 已提交
628
	if (b->keys.page_order < min_order)
629 630 631 632 633 634 635 636 637
		goto out_unlock;

	if (!flush) {
		if (btree_node_dirty(b))
			goto out_unlock;

		if (down_trylock(&b->io_mutex))
			goto out_unlock;
		up(&b->io_mutex);
K
Kent Overstreet 已提交
638 639
	}

K
Kent Overstreet 已提交
640
	mutex_lock(&b->write_lock);
641
	if (btree_node_dirty(b))
K
Kent Overstreet 已提交
642 643 644 645
		__bch_btree_node_write(b, &cl);
	mutex_unlock(&b->write_lock);

	closure_sync(&cl);
K
Kent Overstreet 已提交
646

647
	/* wait for any in flight btree write */
648 649
	down(&b->io_mutex);
	up(&b->io_mutex);
650

K
Kent Overstreet 已提交
651
	return 0;
652 653 654
out_unlock:
	rw_unlock(true, b);
	return -ENOMEM;
K
Kent Overstreet 已提交
655 656
}

657 658
static unsigned long bch_mca_scan(struct shrinker *shrink,
				  struct shrink_control *sc)
K
Kent Overstreet 已提交
659 660 661 662
{
	struct cache_set *c = container_of(shrink, struct cache_set, shrink);
	struct btree *b, *t;
	unsigned long i, nr = sc->nr_to_scan;
663
	unsigned long freed = 0;
K
Kent Overstreet 已提交
664 665

	if (c->shrinker_disabled)
666
		return SHRINK_STOP;
K
Kent Overstreet 已提交
667

668
	if (c->btree_cache_alloc_lock)
669
		return SHRINK_STOP;
K
Kent Overstreet 已提交
670 671

	/* Return -1 if we can't do anything right now */
672
	if (sc->gfp_mask & __GFP_IO)
K
Kent Overstreet 已提交
673 674 675 676
		mutex_lock(&c->bucket_lock);
	else if (!mutex_trylock(&c->bucket_lock))
		return -1;

677 678 679 680 681 682 683
	/*
	 * It's _really_ critical that we don't free too many btree nodes - we
	 * have to always leave ourselves a reserve. The reserve is how we
	 * guarantee that allocating memory for a new btree node can always
	 * succeed, so that inserting keys into the btree can always succeed and
	 * IO can always make forward progress:
	 */
K
Kent Overstreet 已提交
684 685 686 687 688
	nr /= c->btree_pages;
	nr = min_t(unsigned long, nr, mca_can_free(c));

	i = 0;
	list_for_each_entry_safe(b, t, &c->btree_cache_freeable, list) {
689
		if (freed >= nr)
K
Kent Overstreet 已提交
690 691 692
			break;

		if (++i > 3 &&
693
		    !mca_reap(b, 0, false)) {
K
Kent Overstreet 已提交
694 695
			mca_data_free(b);
			rw_unlock(true, b);
696
			freed++;
K
Kent Overstreet 已提交
697 698 699
		}
	}

700
	for (i = 0; (nr--) && i < c->btree_cache_used; i++) {
K
Kent Overstreet 已提交
701 702 703
		if (list_empty(&c->btree_cache))
			goto out;

K
Kent Overstreet 已提交
704 705 706 707
		b = list_first_entry(&c->btree_cache, struct btree, list);
		list_rotate_left(&c->btree_cache);

		if (!b->accessed &&
708
		    !mca_reap(b, 0, false)) {
K
Kent Overstreet 已提交
709 710 711
			mca_bucket_free(b);
			mca_data_free(b);
			rw_unlock(true, b);
712
			freed++;
K
Kent Overstreet 已提交
713 714 715 716 717
		} else
			b->accessed = 0;
	}
out:
	mutex_unlock(&c->bucket_lock);
718 719 720 721 722 723 724 725 726 727 728
	return freed;
}

static unsigned long bch_mca_count(struct shrinker *shrink,
				   struct shrink_control *sc)
{
	struct cache_set *c = container_of(shrink, struct cache_set, shrink);

	if (c->shrinker_disabled)
		return 0;

729
	if (c->btree_cache_alloc_lock)
730 731 732
		return 0;

	return mca_can_free(c) * c->btree_pages;
K
Kent Overstreet 已提交
733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748
}

void bch_btree_cache_free(struct cache_set *c)
{
	struct btree *b;
	struct closure cl;
	closure_init_stack(&cl);

	if (c->shrink.list.next)
		unregister_shrinker(&c->shrink);

	mutex_lock(&c->bucket_lock);

#ifdef CONFIG_BCACHE_DEBUG
	if (c->verify_data)
		list_move(&c->verify_data->list, &c->btree_cache);
749 750

	free_pages((unsigned long) c->verify_ondisk, ilog2(bucket_pages(c)));
K
Kent Overstreet 已提交
751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781
#endif

	list_splice(&c->btree_cache_freeable,
		    &c->btree_cache);

	while (!list_empty(&c->btree_cache)) {
		b = list_first_entry(&c->btree_cache, struct btree, list);

		if (btree_node_dirty(b))
			btree_complete_write(b, btree_current_write(b));
		clear_bit(BTREE_NODE_dirty, &b->flags);

		mca_data_free(b);
	}

	while (!list_empty(&c->btree_cache_freed)) {
		b = list_first_entry(&c->btree_cache_freed,
				     struct btree, list);
		list_del(&b->list);
		cancel_delayed_work_sync(&b->work);
		kfree(b);
	}

	mutex_unlock(&c->bucket_lock);
}

int bch_btree_cache_alloc(struct cache_set *c)
{
	unsigned i;

	for (i = 0; i < mca_reserve(c); i++)
K
Kent Overstreet 已提交
782 783
		if (!mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL))
			return -ENOMEM;
K
Kent Overstreet 已提交
784 785 786 787 788 789 790

	list_splice_init(&c->btree_cache,
			 &c->btree_cache_freeable);

#ifdef CONFIG_BCACHE_DEBUG
	mutex_init(&c->verify_lock);

791 792 793
	c->verify_ondisk = (void *)
		__get_free_pages(GFP_KERNEL, ilog2(bucket_pages(c)));

K
Kent Overstreet 已提交
794 795 796
	c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL);

	if (c->verify_data &&
K
Kent Overstreet 已提交
797
	    c->verify_data->keys.set->data)
K
Kent Overstreet 已提交
798 799 800 801 802
		list_del_init(&c->verify_data->list);
	else
		c->verify_data = NULL;
#endif

803 804
	c->shrink.count_objects = bch_mca_count;
	c->shrink.scan_objects = bch_mca_scan;
K
Kent Overstreet 已提交
805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832
	c->shrink.seeks = 4;
	c->shrink.batch = c->btree_pages * 2;
	register_shrinker(&c->shrink);

	return 0;
}

/* Btree in memory cache - hash table */

static struct hlist_head *mca_hash(struct cache_set *c, struct bkey *k)
{
	return &c->bucket_hash[hash_32(PTR_HASH(c, k), BUCKET_HASH_BITS)];
}

static struct btree *mca_find(struct cache_set *c, struct bkey *k)
{
	struct btree *b;

	rcu_read_lock();
	hlist_for_each_entry_rcu(b, mca_hash(c, k), hash)
		if (PTR_HASH(c, &b->key) == PTR_HASH(c, k))
			goto out;
	b = NULL;
out:
	rcu_read_unlock();
	return b;
}

833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849
static int mca_cannibalize_lock(struct cache_set *c, struct btree_op *op)
{
	struct task_struct *old;

	old = cmpxchg(&c->btree_cache_alloc_lock, NULL, current);
	if (old && old != current) {
		if (op)
			prepare_to_wait(&c->btree_cache_wait, &op->wait,
					TASK_UNINTERRUPTIBLE);
		return -EINTR;
	}

	return 0;
}

static struct btree *mca_cannibalize(struct cache_set *c, struct btree_op *op,
				     struct bkey *k)
K
Kent Overstreet 已提交
850
{
851
	struct btree *b;
K
Kent Overstreet 已提交
852

K
Kent Overstreet 已提交
853 854
	trace_bcache_btree_cache_cannibalize(c);

855 856
	if (mca_cannibalize_lock(c, op))
		return ERR_PTR(-EINTR);
K
Kent Overstreet 已提交
857

858 859 860
	list_for_each_entry_reverse(b, &c->btree_cache, list)
		if (!mca_reap(b, btree_order(k), false))
			return b;
K
Kent Overstreet 已提交
861

862 863 864
	list_for_each_entry_reverse(b, &c->btree_cache, list)
		if (!mca_reap(b, btree_order(k), true))
			return b;
K
Kent Overstreet 已提交
865

866
	WARN(1, "btree cache cannibalize failed\n");
867
	return ERR_PTR(-ENOMEM);
K
Kent Overstreet 已提交
868 869 870 871 872 873 874 875
}

/*
 * We can only have one thread cannibalizing other cached btree nodes at a time,
 * or we'll deadlock. We use an open coded mutex to ensure that, which a
 * cannibalize_bucket() will take. This means every time we unlock the root of
 * the btree, we need to release this lock if we have it held.
 */
876
static void bch_cannibalize_unlock(struct cache_set *c)
K
Kent Overstreet 已提交
877
{
878 879 880
	if (c->btree_cache_alloc_lock == current) {
		c->btree_cache_alloc_lock = NULL;
		wake_up(&c->btree_cache_wait);
K
Kent Overstreet 已提交
881 882 883
	}
}

884 885
static struct btree *mca_alloc(struct cache_set *c, struct btree_op *op,
			       struct bkey *k, int level)
K
Kent Overstreet 已提交
886 887 888
{
	struct btree *b;

889 890
	BUG_ON(current->bio_list);

K
Kent Overstreet 已提交
891 892 893 894 895 896 897 898 899
	lockdep_assert_held(&c->bucket_lock);

	if (mca_find(c, k))
		return NULL;

	/* btree_free() doesn't free memory; it sticks the node on the end of
	 * the list. Check if there's any freed nodes there:
	 */
	list_for_each_entry(b, &c->btree_cache_freeable, list)
900
		if (!mca_reap(b, btree_order(k), false))
K
Kent Overstreet 已提交
901 902 903 904 905 906
			goto out;

	/* We never free struct btree itself, just the memory that holds the on
	 * disk node. Check the freed list before allocating a new one:
	 */
	list_for_each_entry(b, &c->btree_cache_freed, list)
907
		if (!mca_reap(b, 0, false)) {
K
Kent Overstreet 已提交
908
			mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO);
K
Kent Overstreet 已提交
909
			if (!b->keys.set[0].data)
K
Kent Overstreet 已提交
910 911 912 913 914 915 916 917 918 919
				goto err;
			else
				goto out;
		}

	b = mca_bucket_alloc(c, k, __GFP_NOWARN|GFP_NOIO);
	if (!b)
		goto err;

	BUG_ON(!down_write_trylock(&b->lock));
K
Kent Overstreet 已提交
920
	if (!b->keys.set->data)
K
Kent Overstreet 已提交
921 922
		goto err;
out:
923
	BUG_ON(b->io_mutex.count != 1);
K
Kent Overstreet 已提交
924 925 926 927 928 929 930

	bkey_copy(&b->key, k);
	list_move(&b->list, &c->btree_cache);
	hlist_del_init_rcu(&b->hash);
	hlist_add_head_rcu(&b->hash, mca_hash(c, k));

	lock_set_subclass(&b->lock.dep_map, level + 1, _THIS_IP_);
931
	b->parent	= (void *) ~0UL;
K
Kent Overstreet 已提交
932 933 934
	b->flags	= 0;
	b->written	= 0;
	b->level	= level;
K
Kent Overstreet 已提交
935

936
	if (!b->level)
K
Kent Overstreet 已提交
937 938
		bch_btree_keys_init(&b->keys, &bch_extent_keys_ops,
				    &b->c->expensive_debug_checks);
939
	else
K
Kent Overstreet 已提交
940 941
		bch_btree_keys_init(&b->keys, &bch_btree_keys_ops,
				    &b->c->expensive_debug_checks);
K
Kent Overstreet 已提交
942 943 944 945 946 947

	return b;
err:
	if (b)
		rw_unlock(true, b);

948
	b = mca_cannibalize(c, op, k);
K
Kent Overstreet 已提交
949 950 951 952 953 954 955 956 957 958
	if (!IS_ERR(b))
		goto out;

	return b;
}

/**
 * bch_btree_node_get - find a btree node in the cache and lock it, reading it
 * in from disk if necessary.
 *
K
Kent Overstreet 已提交
959
 * If IO is necessary and running under generic_make_request, returns -EAGAIN.
K
Kent Overstreet 已提交
960 961 962 963
 *
 * The btree node will have either a read or a write lock held, depending on
 * level and op->lock.
 */
964
struct btree *bch_btree_node_get(struct cache_set *c, struct btree_op *op,
965 966
				 struct bkey *k, int level, bool write,
				 struct btree *parent)
K
Kent Overstreet 已提交
967 968 969 970 971 972 973 974 975
{
	int i = 0;
	struct btree *b;

	BUG_ON(level < 0);
retry:
	b = mca_find(c, k);

	if (!b) {
K
Kent Overstreet 已提交
976 977 978
		if (current->bio_list)
			return ERR_PTR(-EAGAIN);

K
Kent Overstreet 已提交
979
		mutex_lock(&c->bucket_lock);
980
		b = mca_alloc(c, op, k, level);
K
Kent Overstreet 已提交
981 982 983 984 985 986 987
		mutex_unlock(&c->bucket_lock);

		if (!b)
			goto retry;
		if (IS_ERR(b))
			return b;

K
Kent Overstreet 已提交
988
		bch_btree_node_read(b);
K
Kent Overstreet 已提交
989 990 991 992 993 994 995 996 997 998 999 1000

		if (!write)
			downgrade_write(&b->lock);
	} else {
		rw_lock(write, b, level);
		if (PTR_HASH(c, &b->key) != PTR_HASH(c, k)) {
			rw_unlock(write, b);
			goto retry;
		}
		BUG_ON(b->level != level);
	}

1001
	b->parent = parent;
K
Kent Overstreet 已提交
1002 1003
	b->accessed = 1;

K
Kent Overstreet 已提交
1004 1005 1006
	for (; i <= b->keys.nsets && b->keys.set[i].size; i++) {
		prefetch(b->keys.set[i].tree);
		prefetch(b->keys.set[i].data);
K
Kent Overstreet 已提交
1007 1008
	}

K
Kent Overstreet 已提交
1009 1010
	for (; i <= b->keys.nsets; i++)
		prefetch(b->keys.set[i].data);
K
Kent Overstreet 已提交
1011

K
Kent Overstreet 已提交
1012
	if (btree_node_io_error(b)) {
K
Kent Overstreet 已提交
1013
		rw_unlock(write, b);
K
Kent Overstreet 已提交
1014 1015 1016 1017
		return ERR_PTR(-EIO);
	}

	BUG_ON(!b->written);
K
Kent Overstreet 已提交
1018 1019 1020 1021

	return b;
}

1022
static void btree_node_prefetch(struct btree *parent, struct bkey *k)
K
Kent Overstreet 已提交
1023 1024 1025
{
	struct btree *b;

1026 1027 1028
	mutex_lock(&parent->c->bucket_lock);
	b = mca_alloc(parent->c, NULL, k, parent->level - 1);
	mutex_unlock(&parent->c->bucket_lock);
K
Kent Overstreet 已提交
1029 1030

	if (!IS_ERR_OR_NULL(b)) {
1031
		b->parent = parent;
K
Kent Overstreet 已提交
1032
		bch_btree_node_read(b);
K
Kent Overstreet 已提交
1033 1034 1035 1036 1037 1038
		rw_unlock(true, b);
	}
}

/* Btree alloc */

1039
static void btree_node_free(struct btree *b)
K
Kent Overstreet 已提交
1040
{
K
Kent Overstreet 已提交
1041 1042
	trace_bcache_btree_node_free(b);

K
Kent Overstreet 已提交
1043 1044
	BUG_ON(b == b->c->root);

K
Kent Overstreet 已提交
1045 1046
	mutex_lock(&b->write_lock);

K
Kent Overstreet 已提交
1047 1048 1049 1050
	if (btree_node_dirty(b))
		btree_complete_write(b, btree_current_write(b));
	clear_bit(BTREE_NODE_dirty, &b->flags);

K
Kent Overstreet 已提交
1051 1052
	mutex_unlock(&b->write_lock);

K
Kent Overstreet 已提交
1053 1054 1055 1056 1057 1058 1059 1060
	cancel_delayed_work(&b->work);

	mutex_lock(&b->c->bucket_lock);
	bch_bucket_free(b->c, &b->key);
	mca_bucket_free(b);
	mutex_unlock(&b->c->bucket_lock);
}

1061
struct btree *__bch_btree_node_alloc(struct cache_set *c, struct btree_op *op,
1062 1063
				     int level, bool wait,
				     struct btree *parent)
K
Kent Overstreet 已提交
1064 1065 1066 1067 1068 1069
{
	BKEY_PADDED(key) k;
	struct btree *b = ERR_PTR(-EAGAIN);

	mutex_lock(&c->bucket_lock);
retry:
1070
	if (__bch_bucket_alloc_set(c, RESERVE_BTREE, &k.key, 1, wait))
K
Kent Overstreet 已提交
1071 1072
		goto err;

1073
	bkey_put(c, &k.key);
K
Kent Overstreet 已提交
1074 1075
	SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS);

1076
	b = mca_alloc(c, op, &k.key, level);
K
Kent Overstreet 已提交
1077 1078 1079 1080
	if (IS_ERR(b))
		goto err_free;

	if (!b) {
K
Kent Overstreet 已提交
1081 1082
		cache_bug(c,
			"Tried to allocate bucket that was in btree cache");
K
Kent Overstreet 已提交
1083 1084 1085 1086
		goto retry;
	}

	b->accessed = 1;
1087
	b->parent = parent;
K
Kent Overstreet 已提交
1088
	bch_bset_init_next(&b->keys, b->keys.set->data, bset_magic(&b->c->sb));
K
Kent Overstreet 已提交
1089 1090

	mutex_unlock(&c->bucket_lock);
K
Kent Overstreet 已提交
1091 1092

	trace_bcache_btree_node_alloc(b);
K
Kent Overstreet 已提交
1093 1094 1095 1096 1097
	return b;
err_free:
	bch_bucket_free(c, &k.key);
err:
	mutex_unlock(&c->bucket_lock);
K
Kent Overstreet 已提交
1098

1099
	trace_bcache_btree_node_alloc_fail(c);
K
Kent Overstreet 已提交
1100 1101 1102
	return b;
}

1103
static struct btree *bch_btree_node_alloc(struct cache_set *c,
1104 1105
					  struct btree_op *op, int level,
					  struct btree *parent)
1106
{
1107
	return __bch_btree_node_alloc(c, op, level, op != NULL, parent);
1108 1109
}

1110 1111
static struct btree *btree_node_alloc_replacement(struct btree *b,
						  struct btree_op *op)
K
Kent Overstreet 已提交
1112
{
1113
	struct btree *n = bch_btree_node_alloc(b->c, op, b->level, b->parent);
1114
	if (!IS_ERR_OR_NULL(n)) {
K
Kent Overstreet 已提交
1115
		mutex_lock(&n->write_lock);
1116
		bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort);
1117
		bkey_copy_key(&n->key, &b->key);
K
Kent Overstreet 已提交
1118
		mutex_unlock(&n->write_lock);
1119
	}
K
Kent Overstreet 已提交
1120 1121 1122 1123

	return n;
}

1124 1125 1126 1127
static void make_btree_freeing_key(struct btree *b, struct bkey *k)
{
	unsigned i;

1128 1129 1130 1131
	mutex_lock(&b->c->bucket_lock);

	atomic_inc(&b->c->prio_blocked);

1132 1133 1134
	bkey_copy(k, &b->key);
	bkey_copy_key(k, &ZERO_KEY);

1135 1136 1137 1138
	for (i = 0; i < KEY_PTRS(k); i++)
		SET_PTR_GEN(k, i,
			    bch_inc_gen(PTR_CACHE(b->c, &b->key, i),
					PTR_BUCKET(b->c, &b->key, i)));
1139

1140
	mutex_unlock(&b->c->bucket_lock);
1141 1142
}

1143 1144 1145 1146
static int btree_check_reserve(struct btree *b, struct btree_op *op)
{
	struct cache_set *c = b->c;
	struct cache *ca;
1147
	unsigned i, reserve = (c->root->level - b->level) * 2 + 1;
1148 1149 1150 1151 1152 1153

	mutex_lock(&c->bucket_lock);

	for_each_cache(ca, c, i)
		if (fifo_used(&ca->free[RESERVE_BTREE]) < reserve) {
			if (op)
1154
				prepare_to_wait(&c->btree_cache_wait, &op->wait,
1155
						TASK_UNINTERRUPTIBLE);
1156 1157
			mutex_unlock(&c->bucket_lock);
			return -EINTR;
1158 1159 1160
		}

	mutex_unlock(&c->bucket_lock);
1161 1162

	return mca_cannibalize_lock(b->c, op);
1163 1164
}

K
Kent Overstreet 已提交
1165 1166
/* Garbage collection */

1167 1168
static uint8_t __bch_btree_mark_key(struct cache_set *c, int level,
				    struct bkey *k)
K
Kent Overstreet 已提交
1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187
{
	uint8_t stale = 0;
	unsigned i;
	struct bucket *g;

	/*
	 * ptr_invalid() can't return true for the keys that mark btree nodes as
	 * freed, but since ptr_bad() returns true we'll never actually use them
	 * for anything and thus we don't want mark their pointers here
	 */
	if (!bkey_cmp(k, &ZERO_KEY))
		return stale;

	for (i = 0; i < KEY_PTRS(k); i++) {
		if (!ptr_available(c, k, i))
			continue;

		g = PTR_BUCKET(c, k, i);

K
Kent Overstreet 已提交
1188 1189
		if (gen_after(g->last_gc, PTR_GEN(k, i)))
			g->last_gc = PTR_GEN(k, i);
K
Kent Overstreet 已提交
1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204

		if (ptr_stale(c, k, i)) {
			stale = max(stale, ptr_stale(c, k, i));
			continue;
		}

		cache_bug_on(GC_MARK(g) &&
			     (GC_MARK(g) == GC_MARK_METADATA) != (level != 0),
			     c, "inconsistent ptrs: mark = %llu, level = %i",
			     GC_MARK(g), level);

		if (level)
			SET_GC_MARK(g, GC_MARK_METADATA);
		else if (KEY_DIRTY(k))
			SET_GC_MARK(g, GC_MARK_DIRTY);
1205 1206
		else if (!GC_MARK(g))
			SET_GC_MARK(g, GC_MARK_RECLAIMABLE);
K
Kent Overstreet 已提交
1207 1208 1209 1210

		/* guard against overflow */
		SET_GC_SECTORS_USED(g, min_t(unsigned,
					     GC_SECTORS_USED(g) + KEY_SIZE(k),
1211
					     MAX_GC_SECTORS_USED));
K
Kent Overstreet 已提交
1212 1213 1214 1215 1216 1217 1218 1219 1220

		BUG_ON(!GC_SECTORS_USED(g));
	}

	return stale;
}

#define btree_mark_key(b, k)	__bch_btree_mark_key(b->c, b->level, k)

1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240
void bch_initial_mark_key(struct cache_set *c, int level, struct bkey *k)
{
	unsigned i;

	for (i = 0; i < KEY_PTRS(k); i++)
		if (ptr_available(c, k, i) &&
		    !ptr_stale(c, k, i)) {
			struct bucket *b = PTR_BUCKET(c, k, i);

			b->gen = PTR_GEN(k, i);

			if (level && bkey_cmp(k, &ZERO_KEY))
				b->prio = BTREE_PRIO;
			else if (!level && b->prio == BTREE_PRIO)
				b->prio = INITIAL_PRIO;
		}

	__bch_btree_mark_key(c, level, k);
}

K
Kent Overstreet 已提交
1241
static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc)
K
Kent Overstreet 已提交
1242 1243
{
	uint8_t stale = 0;
K
Kent Overstreet 已提交
1244
	unsigned keys = 0, good_keys = 0;
K
Kent Overstreet 已提交
1245 1246 1247 1248 1249 1250
	struct bkey *k;
	struct btree_iter iter;
	struct bset_tree *t;

	gc->nodes++;

1251
	for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) {
K
Kent Overstreet 已提交
1252
		stale = max(stale, btree_mark_key(b, k));
K
Kent Overstreet 已提交
1253
		keys++;
K
Kent Overstreet 已提交
1254

K
Kent Overstreet 已提交
1255
		if (bch_ptr_bad(&b->keys, k))
K
Kent Overstreet 已提交
1256 1257 1258 1259
			continue;

		gc->key_bytes += bkey_u64s(k);
		gc->nkeys++;
K
Kent Overstreet 已提交
1260
		good_keys++;
K
Kent Overstreet 已提交
1261 1262 1263 1264

		gc->data += KEY_SIZE(k);
	}

K
Kent Overstreet 已提交
1265
	for (t = b->keys.set; t <= &b->keys.set[b->keys.nsets]; t++)
K
Kent Overstreet 已提交
1266
		btree_bug_on(t->size &&
K
Kent Overstreet 已提交
1267
			     bset_written(&b->keys, t) &&
K
Kent Overstreet 已提交
1268 1269 1270
			     bkey_cmp(&b->key, &t->end) < 0,
			     b, "found short btree key in gc");

K
Kent Overstreet 已提交
1271 1272
	if (b->c->gc_always_rewrite)
		return true;
K
Kent Overstreet 已提交
1273

K
Kent Overstreet 已提交
1274 1275
	if (stale > 10)
		return true;
K
Kent Overstreet 已提交
1276

K
Kent Overstreet 已提交
1277 1278
	if ((keys - good_keys) * 2 > keys)
		return true;
K
Kent Overstreet 已提交
1279

K
Kent Overstreet 已提交
1280
	return false;
K
Kent Overstreet 已提交
1281 1282
}

K
Kent Overstreet 已提交
1283
#define GC_MERGE_NODES	4U
K
Kent Overstreet 已提交
1284 1285 1286 1287 1288 1289

struct gc_merge_info {
	struct btree	*b;
	unsigned	keys;
};

K
Kent Overstreet 已提交
1290 1291 1292 1293
static int bch_btree_insert_node(struct btree *, struct btree_op *,
				 struct keylist *, atomic_t *, struct bkey *);

static int btree_gc_coalesce(struct btree *b, struct btree_op *op,
1294
			     struct gc_stat *gc, struct gc_merge_info *r)
K
Kent Overstreet 已提交
1295
{
K
Kent Overstreet 已提交
1296 1297
	unsigned i, nodes = 0, keys = 0, blocks;
	struct btree *new_nodes[GC_MERGE_NODES];
1298
	struct keylist keylist;
K
Kent Overstreet 已提交
1299
	struct closure cl;
K
Kent Overstreet 已提交
1300
	struct bkey *k;
K
Kent Overstreet 已提交
1301

1302 1303 1304 1305 1306
	bch_keylist_init(&keylist);

	if (btree_check_reserve(b, NULL))
		return 0;

K
Kent Overstreet 已提交
1307
	memset(new_nodes, 0, sizeof(new_nodes));
K
Kent Overstreet 已提交
1308
	closure_init_stack(&cl);
K
Kent Overstreet 已提交
1309

K
Kent Overstreet 已提交
1310
	while (nodes < GC_MERGE_NODES && !IS_ERR_OR_NULL(r[nodes].b))
K
Kent Overstreet 已提交
1311 1312 1313 1314 1315
		keys += r[nodes++].keys;

	blocks = btree_default_blocks(b->c) * 2 / 3;

	if (nodes < 2 ||
K
Kent Overstreet 已提交
1316
	    __set_blocks(b->keys.set[0].data, keys,
1317
			 block_bytes(b->c)) > blocks * (nodes - 1))
K
Kent Overstreet 已提交
1318
		return 0;
K
Kent Overstreet 已提交
1319

K
Kent Overstreet 已提交
1320
	for (i = 0; i < nodes; i++) {
1321
		new_nodes[i] = btree_node_alloc_replacement(r[i].b, NULL);
K
Kent Overstreet 已提交
1322 1323
		if (IS_ERR_OR_NULL(new_nodes[i]))
			goto out_nocoalesce;
K
Kent Overstreet 已提交
1324 1325
	}

1326 1327 1328 1329 1330 1331 1332 1333 1334
	/*
	 * We have to check the reserve here, after we've allocated our new
	 * nodes, to make sure the insert below will succeed - we also check
	 * before as an optimization to potentially avoid a bunch of expensive
	 * allocs/sorts
	 */
	if (btree_check_reserve(b, NULL))
		goto out_nocoalesce;

K
Kent Overstreet 已提交
1335 1336 1337
	for (i = 0; i < nodes; i++)
		mutex_lock(&new_nodes[i]->write_lock);

K
Kent Overstreet 已提交
1338
	for (i = nodes - 1; i > 0; --i) {
1339 1340
		struct bset *n1 = btree_bset_first(new_nodes[i]);
		struct bset *n2 = btree_bset_first(new_nodes[i - 1]);
K
Kent Overstreet 已提交
1341 1342 1343 1344
		struct bkey *k, *last = NULL;

		keys = 0;

K
Kent Overstreet 已提交
1345 1346
		if (i > 1) {
			for (k = n2->start;
K
Kent Overstreet 已提交
1347
			     k < bset_bkey_last(n2);
K
Kent Overstreet 已提交
1348 1349
			     k = bkey_next(k)) {
				if (__set_blocks(n1, n1->keys + keys +
1350 1351
						 bkey_u64s(k),
						 block_bytes(b->c)) > blocks)
K
Kent Overstreet 已提交
1352 1353 1354 1355 1356 1357
					break;

				last = k;
				keys += bkey_u64s(k);
			}
		} else {
K
Kent Overstreet 已提交
1358 1359 1360 1361 1362 1363 1364 1365
			/*
			 * Last node we're not getting rid of - we're getting
			 * rid of the node at r[0]. Have to try and fit all of
			 * the remaining keys into this node; we can't ensure
			 * they will always fit due to rounding and variable
			 * length keys (shouldn't be possible in practice,
			 * though)
			 */
K
Kent Overstreet 已提交
1366
			if (__set_blocks(n1, n1->keys + n2->keys,
1367 1368
					 block_bytes(b->c)) >
			    btree_blocks(new_nodes[i]))
K
Kent Overstreet 已提交
1369
				goto out_nocoalesce;
K
Kent Overstreet 已提交
1370 1371

			keys = n2->keys;
K
Kent Overstreet 已提交
1372
			/* Take the key of the node we're getting rid of */
K
Kent Overstreet 已提交
1373
			last = &r->b->key;
K
Kent Overstreet 已提交
1374
		}
K
Kent Overstreet 已提交
1375

1376 1377
		BUG_ON(__set_blocks(n1, n1->keys + keys, block_bytes(b->c)) >
		       btree_blocks(new_nodes[i]));
K
Kent Overstreet 已提交
1378

K
Kent Overstreet 已提交
1379 1380
		if (last)
			bkey_copy_key(&new_nodes[i]->key, last);
K
Kent Overstreet 已提交
1381

K
Kent Overstreet 已提交
1382
		memcpy(bset_bkey_last(n1),
K
Kent Overstreet 已提交
1383
		       n2->start,
K
Kent Overstreet 已提交
1384
		       (void *) bset_bkey_idx(n2, keys) - (void *) n2->start);
K
Kent Overstreet 已提交
1385 1386

		n1->keys += keys;
K
Kent Overstreet 已提交
1387
		r[i].keys = n1->keys;
K
Kent Overstreet 已提交
1388 1389

		memmove(n2->start,
K
Kent Overstreet 已提交
1390 1391 1392
			bset_bkey_idx(n2, keys),
			(void *) bset_bkey_last(n2) -
			(void *) bset_bkey_idx(n2, keys));
K
Kent Overstreet 已提交
1393 1394 1395

		n2->keys -= keys;

1396
		if (__bch_keylist_realloc(&keylist,
1397
					  bkey_u64s(&new_nodes[i]->key)))
K
Kent Overstreet 已提交
1398 1399 1400
			goto out_nocoalesce;

		bch_btree_node_write(new_nodes[i], &cl);
1401
		bch_keylist_add(&keylist, &new_nodes[i]->key);
K
Kent Overstreet 已提交
1402 1403
	}

K
Kent Overstreet 已提交
1404 1405 1406
	for (i = 0; i < nodes; i++)
		mutex_unlock(&new_nodes[i]->write_lock);

1407 1408 1409 1410 1411 1412
	closure_sync(&cl);

	/* We emptied out this node */
	BUG_ON(btree_bset_first(new_nodes[0])->keys);
	btree_node_free(new_nodes[0]);
	rw_unlock(true, new_nodes[0]);
1413
	new_nodes[0] = NULL;
1414

K
Kent Overstreet 已提交
1415
	for (i = 0; i < nodes; i++) {
1416
		if (__bch_keylist_realloc(&keylist, bkey_u64s(&r[i].b->key)))
K
Kent Overstreet 已提交
1417
			goto out_nocoalesce;
K
Kent Overstreet 已提交
1418

1419 1420
		make_btree_freeing_key(r[i].b, keylist.top);
		bch_keylist_push(&keylist);
K
Kent Overstreet 已提交
1421
	}
K
Kent Overstreet 已提交
1422

1423 1424
	bch_btree_insert_node(b, op, &keylist, NULL, NULL);
	BUG_ON(!bch_keylist_empty(&keylist));
K
Kent Overstreet 已提交
1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436

	for (i = 0; i < nodes; i++) {
		btree_node_free(r[i].b);
		rw_unlock(true, r[i].b);

		r[i].b = new_nodes[i];
	}

	memmove(r, r + 1, sizeof(r[0]) * (nodes - 1));
	r[nodes - 1].b = ERR_PTR(-EINTR);

	trace_bcache_btree_gc_coalesce(nodes);
K
Kent Overstreet 已提交
1437 1438
	gc->nodes--;

1439 1440
	bch_keylist_free(&keylist);

K
Kent Overstreet 已提交
1441 1442 1443 1444 1445
	/* Invalidated our iterator */
	return -EINTR;

out_nocoalesce:
	closure_sync(&cl);
1446
	bch_keylist_free(&keylist);
K
Kent Overstreet 已提交
1447

1448
	while ((k = bch_keylist_pop(&keylist)))
K
Kent Overstreet 已提交
1449 1450 1451 1452 1453 1454 1455 1456 1457
		if (!bkey_cmp(k, &ZERO_KEY))
			atomic_dec(&b->c->prio_blocked);

	for (i = 0; i < nodes; i++)
		if (!IS_ERR_OR_NULL(new_nodes[i])) {
			btree_node_free(new_nodes[i]);
			rw_unlock(true, new_nodes[i]);
		}
	return 0;
K
Kent Overstreet 已提交
1458 1459
}

1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495
static int btree_gc_rewrite_node(struct btree *b, struct btree_op *op,
				 struct btree *replace)
{
	struct keylist keys;
	struct btree *n;

	if (btree_check_reserve(b, NULL))
		return 0;

	n = btree_node_alloc_replacement(replace, NULL);

	/* recheck reserve after allocating replacement node */
	if (btree_check_reserve(b, NULL)) {
		btree_node_free(n);
		rw_unlock(true, n);
		return 0;
	}

	bch_btree_node_write_sync(n);

	bch_keylist_init(&keys);
	bch_keylist_add(&keys, &n->key);

	make_btree_freeing_key(replace, keys.top);
	bch_keylist_push(&keys);

	bch_btree_insert_node(b, op, &keys, NULL, NULL);
	BUG_ON(!bch_keylist_empty(&keys));

	btree_node_free(replace);
	rw_unlock(true, n);

	/* Invalidated our iterator */
	return -EINTR;
}

K
Kent Overstreet 已提交
1496
static unsigned btree_gc_count_keys(struct btree *b)
K
Kent Overstreet 已提交
1497
{
K
Kent Overstreet 已提交
1498 1499 1500
	struct bkey *k;
	struct btree_iter iter;
	unsigned ret = 0;
K
Kent Overstreet 已提交
1501

1502
	for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad)
K
Kent Overstreet 已提交
1503 1504 1505 1506
		ret += bkey_u64s(k);

	return ret;
}
K
Kent Overstreet 已提交
1507

K
Kent Overstreet 已提交
1508 1509 1510 1511 1512 1513 1514
static int btree_gc_recurse(struct btree *b, struct btree_op *op,
			    struct closure *writes, struct gc_stat *gc)
{
	int ret = 0;
	bool should_rewrite;
	struct bkey *k;
	struct btree_iter iter;
K
Kent Overstreet 已提交
1515
	struct gc_merge_info r[GC_MERGE_NODES];
K
Kent Overstreet 已提交
1516
	struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1;
K
Kent Overstreet 已提交
1517

1518
	bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done);
K
Kent Overstreet 已提交
1519

K
Kent Overstreet 已提交
1520 1521
	for (i = r; i < r + ARRAY_SIZE(r); i++)
		i->b = ERR_PTR(-EINTR);
K
Kent Overstreet 已提交
1522

K
Kent Overstreet 已提交
1523
	while (1) {
K
Kent Overstreet 已提交
1524
		k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad);
K
Kent Overstreet 已提交
1525
		if (k) {
1526
			r->b = bch_btree_node_get(b->c, op, k, b->level - 1,
1527
						  true, b);
K
Kent Overstreet 已提交
1528 1529 1530 1531 1532 1533 1534
			if (IS_ERR(r->b)) {
				ret = PTR_ERR(r->b);
				break;
			}

			r->keys = btree_gc_count_keys(r->b);

1535
			ret = btree_gc_coalesce(b, op, gc, r);
K
Kent Overstreet 已提交
1536 1537
			if (ret)
				break;
K
Kent Overstreet 已提交
1538 1539
		}

K
Kent Overstreet 已提交
1540 1541
		if (!last->b)
			break;
K
Kent Overstreet 已提交
1542

K
Kent Overstreet 已提交
1543 1544
		if (!IS_ERR(last->b)) {
			should_rewrite = btree_gc_mark_node(last->b, gc);
1545 1546 1547
			if (should_rewrite) {
				ret = btree_gc_rewrite_node(b, op, last->b);
				if (ret)
K
Kent Overstreet 已提交
1548 1549 1550 1551 1552 1553 1554 1555
					break;
			}

			if (last->b->level) {
				ret = btree_gc_recurse(last->b, op, writes, gc);
				if (ret)
					break;
			}
K
Kent Overstreet 已提交
1556

K
Kent Overstreet 已提交
1557 1558 1559 1560 1561 1562
			bkey_copy_key(&b->c->gc_done, &last->b->key);

			/*
			 * Must flush leaf nodes before gc ends, since replace
			 * operations aren't journalled
			 */
K
Kent Overstreet 已提交
1563
			mutex_lock(&last->b->write_lock);
K
Kent Overstreet 已提交
1564 1565
			if (btree_node_dirty(last->b))
				bch_btree_node_write(last->b, writes);
K
Kent Overstreet 已提交
1566
			mutex_unlock(&last->b->write_lock);
K
Kent Overstreet 已提交
1567 1568 1569 1570 1571
			rw_unlock(true, last->b);
		}

		memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1));
		r->b = NULL;
K
Kent Overstreet 已提交
1572 1573 1574 1575 1576 1577 1578

		if (need_resched()) {
			ret = -EAGAIN;
			break;
		}
	}

K
Kent Overstreet 已提交
1579 1580 1581 1582 1583 1584 1585
	for (i = r; i < r + ARRAY_SIZE(r); i++)
		if (!IS_ERR_OR_NULL(i->b)) {
			mutex_lock(&i->b->write_lock);
			if (btree_node_dirty(i->b))
				bch_btree_node_write(i->b, writes);
			mutex_unlock(&i->b->write_lock);
			rw_unlock(true, i->b);
K
Kent Overstreet 已提交
1586
		}
K
Kent Overstreet 已提交
1587 1588 1589 1590 1591 1592 1593 1594

	return ret;
}

static int bch_btree_gc_root(struct btree *b, struct btree_op *op,
			     struct closure *writes, struct gc_stat *gc)
{
	struct btree *n = NULL;
K
Kent Overstreet 已提交
1595 1596
	int ret = 0;
	bool should_rewrite;
K
Kent Overstreet 已提交
1597

K
Kent Overstreet 已提交
1598 1599
	should_rewrite = btree_gc_mark_node(b, gc);
	if (should_rewrite) {
1600
		n = btree_node_alloc_replacement(b, NULL);
K
Kent Overstreet 已提交
1601

K
Kent Overstreet 已提交
1602 1603
		if (!IS_ERR_OR_NULL(n)) {
			bch_btree_node_write_sync(n);
K
Kent Overstreet 已提交
1604

K
Kent Overstreet 已提交
1605 1606 1607
			bch_btree_set_root(n);
			btree_node_free(b);
			rw_unlock(true, n);
K
Kent Overstreet 已提交
1608

K
Kent Overstreet 已提交
1609 1610 1611
			return -EINTR;
		}
	}
K
Kent Overstreet 已提交
1612

1613 1614
	__bch_btree_mark_key(b->c, b->level + 1, &b->key);

K
Kent Overstreet 已提交
1615 1616 1617 1618
	if (b->level) {
		ret = btree_gc_recurse(b, op, writes, gc);
		if (ret)
			return ret;
K
Kent Overstreet 已提交
1619 1620
	}

K
Kent Overstreet 已提交
1621 1622
	bkey_copy_key(&b->c->gc_done, &b->key);

K
Kent Overstreet 已提交
1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641
	return ret;
}

static void btree_gc_start(struct cache_set *c)
{
	struct cache *ca;
	struct bucket *b;
	unsigned i;

	if (!c->gc_mark_valid)
		return;

	mutex_lock(&c->bucket_lock);

	c->gc_mark_valid = 0;
	c->gc_done = ZERO_KEY;

	for_each_cache(ca, c, i)
		for_each_bucket(b, ca) {
K
Kent Overstreet 已提交
1642
			b->last_gc = b->gen;
1643
			if (!atomic_read(&b->pin)) {
1644
				SET_GC_MARK(b, 0);
1645 1646
				SET_GC_SECTORS_USED(b, 0);
			}
K
Kent Overstreet 已提交
1647 1648 1649 1650 1651
		}

	mutex_unlock(&c->bucket_lock);
}

K
Kent Overstreet 已提交
1652
static size_t bch_btree_gc_finish(struct cache_set *c)
K
Kent Overstreet 已提交
1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668
{
	size_t available = 0;
	struct bucket *b;
	struct cache *ca;
	unsigned i;

	mutex_lock(&c->bucket_lock);

	set_gc_sectors(c);
	c->gc_mark_valid = 1;
	c->need_gc	= 0;

	for (i = 0; i < KEY_PTRS(&c->uuid_bucket); i++)
		SET_GC_MARK(PTR_BUCKET(c, &c->uuid_bucket, i),
			    GC_MARK_METADATA);

1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690
	/* don't reclaim buckets to which writeback keys point */
	rcu_read_lock();
	for (i = 0; i < c->nr_uuids; i++) {
		struct bcache_device *d = c->devices[i];
		struct cached_dev *dc;
		struct keybuf_key *w, *n;
		unsigned j;

		if (!d || UUID_FLASH_ONLY(&c->uuids[i]))
			continue;
		dc = container_of(d, struct cached_dev, disk);

		spin_lock(&dc->writeback_keys.lock);
		rbtree_postorder_for_each_entry_safe(w, n,
					&dc->writeback_keys.keys, node)
			for (j = 0; j < KEY_PTRS(&w->key); j++)
				SET_GC_MARK(PTR_BUCKET(c, &w->key, j),
					    GC_MARK_DIRTY);
		spin_unlock(&dc->writeback_keys.lock);
	}
	rcu_read_unlock();

K
Kent Overstreet 已提交
1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705
	for_each_cache(ca, c, i) {
		uint64_t *i;

		ca->invalidate_needs_gc = 0;

		for (i = ca->sb.d; i < ca->sb.d + ca->sb.keys; i++)
			SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA);

		for (i = ca->prio_buckets;
		     i < ca->prio_buckets + prio_buckets(ca) * 2; i++)
			SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA);

		for_each_bucket(b, ca) {
			c->need_gc	= max(c->need_gc, bucket_gc_gen(b));

1706 1707 1708 1709 1710 1711
			if (atomic_read(&b->pin))
				continue;

			BUG_ON(!GC_MARK(b) && GC_SECTORS_USED(b));

			if (!GC_MARK(b) || GC_MARK(b) == GC_MARK_RECLAIMABLE)
K
Kent Overstreet 已提交
1712 1713 1714 1715 1716 1717 1718 1719
				available++;
		}
	}

	mutex_unlock(&c->bucket_lock);
	return available;
}

K
Kent Overstreet 已提交
1720
static void bch_btree_gc(struct cache_set *c)
K
Kent Overstreet 已提交
1721 1722 1723 1724 1725 1726 1727
{
	int ret;
	unsigned long available;
	struct gc_stat stats;
	struct closure writes;
	struct btree_op op;
	uint64_t start_time = local_clock();
K
Kent Overstreet 已提交
1728

K
Kent Overstreet 已提交
1729
	trace_bcache_gc_start(c);
K
Kent Overstreet 已提交
1730 1731 1732

	memset(&stats, 0, sizeof(struct gc_stat));
	closure_init_stack(&writes);
K
Kent Overstreet 已提交
1733
	bch_btree_op_init(&op, SHRT_MAX);
K
Kent Overstreet 已提交
1734 1735 1736

	btree_gc_start(c);

K
Kent Overstreet 已提交
1737 1738 1739
	do {
		ret = btree_root(gc_root, c, &op, &writes, &stats);
		closure_sync(&writes);
1740
		cond_resched();
K
Kent Overstreet 已提交
1741

K
Kent Overstreet 已提交
1742 1743 1744
		if (ret && ret != -EAGAIN)
			pr_warn("gc failed!");
	} while (ret);
K
Kent Overstreet 已提交
1745 1746

	available = bch_btree_gc_finish(c);
K
Kent Overstreet 已提交
1747 1748
	wake_up_allocators(c);

1749
	bch_time_stats_update(&c->btree_gc_time, start_time);
K
Kent Overstreet 已提交
1750 1751 1752 1753 1754 1755

	stats.key_bytes *= sizeof(uint64_t);
	stats.data	<<= 9;
	stats.in_use	= (c->nbuckets - available) * 100 / c->nbuckets;
	memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat));

K
Kent Overstreet 已提交
1756
	trace_bcache_gc_end(c);
K
Kent Overstreet 已提交
1757

K
Kent Overstreet 已提交
1758 1759 1760
	bch_moving_gc(c);
}

1761
static bool gc_should_run(struct cache_set *c)
K
Kent Overstreet 已提交
1762
{
K
Kent Overstreet 已提交
1763 1764
	struct cache *ca;
	unsigned i;
K
Kent Overstreet 已提交
1765

1766 1767 1768
	for_each_cache(ca, c, i)
		if (ca->invalidate_needs_gc)
			return true;
K
Kent Overstreet 已提交
1769

1770 1771
	if (atomic_read(&c->sectors_to_gc) < 0)
		return true;
K
Kent Overstreet 已提交
1772

1773 1774
	return false;
}
K
Kent Overstreet 已提交
1775

1776 1777 1778
static int bch_gc_thread(void *arg)
{
	struct cache_set *c = arg;
K
Kent Overstreet 已提交
1779

1780 1781 1782
	while (1) {
		wait_event_interruptible(c->gc_wait,
			   kthread_should_stop() || gc_should_run(c));
K
Kent Overstreet 已提交
1783

1784 1785 1786 1787 1788
		if (kthread_should_stop())
			break;

		set_gc_sectors(c);
		bch_btree_gc(c);
K
Kent Overstreet 已提交
1789 1790 1791
	}

	return 0;
K
Kent Overstreet 已提交
1792 1793
}

K
Kent Overstreet 已提交
1794
int bch_gc_thread_start(struct cache_set *c)
K
Kent Overstreet 已提交
1795
{
1796
	c->gc_thread = kthread_run(bch_gc_thread, c, "bcache_gc");
K
Kent Overstreet 已提交
1797 1798 1799 1800
	if (IS_ERR(c->gc_thread))
		return PTR_ERR(c->gc_thread);

	return 0;
K
Kent Overstreet 已提交
1801 1802 1803 1804
}

/* Initial partial gc */

1805
static int bch_btree_check_recurse(struct btree *b, struct btree_op *op)
K
Kent Overstreet 已提交
1806
{
1807 1808
	int ret = 0;
	struct bkey *k, *p = NULL;
K
Kent Overstreet 已提交
1809 1810
	struct btree_iter iter;

1811 1812
	for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid)
		bch_initial_mark_key(b->c, b->level, k);
K
Kent Overstreet 已提交
1813

1814
	bch_initial_mark_key(b->c, b->level + 1, &b->key);
K
Kent Overstreet 已提交
1815 1816

	if (b->level) {
1817
		bch_btree_iter_init(&b->keys, &iter, NULL);
K
Kent Overstreet 已提交
1818

1819
		do {
K
Kent Overstreet 已提交
1820 1821
			k = bch_btree_iter_next_filter(&iter, &b->keys,
						       bch_ptr_bad);
1822
			if (k)
1823
				btree_node_prefetch(b, k);
K
Kent Overstreet 已提交
1824

1825
			if (p)
1826
				ret = btree(check_recurse, p, b, op);
K
Kent Overstreet 已提交
1827

1828 1829
			p = k;
		} while (p && !ret);
K
Kent Overstreet 已提交
1830 1831
	}

1832
	return ret;
K
Kent Overstreet 已提交
1833 1834
}

K
Kent Overstreet 已提交
1835
int bch_btree_check(struct cache_set *c)
K
Kent Overstreet 已提交
1836
{
K
Kent Overstreet 已提交
1837
	struct btree_op op;
K
Kent Overstreet 已提交
1838

K
Kent Overstreet 已提交
1839
	bch_btree_op_init(&op, SHRT_MAX);
K
Kent Overstreet 已提交
1840

1841
	return btree_root(check_recurse, c, &op);
K
Kent Overstreet 已提交
1842 1843
}

K
Kent Overstreet 已提交
1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879
void bch_initial_gc_finish(struct cache_set *c)
{
	struct cache *ca;
	struct bucket *b;
	unsigned i;

	bch_btree_gc_finish(c);

	mutex_lock(&c->bucket_lock);

	/*
	 * We need to put some unused buckets directly on the prio freelist in
	 * order to get the allocator thread started - it needs freed buckets in
	 * order to rewrite the prios and gens, and it needs to rewrite prios
	 * and gens in order to free buckets.
	 *
	 * This is only safe for buckets that have no live data in them, which
	 * there should always be some of.
	 */
	for_each_cache(ca, c, i) {
		for_each_bucket(b, ca) {
			if (fifo_full(&ca->free[RESERVE_PRIO]))
				break;

			if (bch_can_invalidate_bucket(ca, b) &&
			    !GC_MARK(b)) {
				__bch_invalidate_one_bucket(ca, b);
				fifo_push(&ca->free[RESERVE_PRIO],
					  b - ca->buckets);
			}
		}
	}

	mutex_unlock(&c->bucket_lock);
}

K
Kent Overstreet 已提交
1880 1881
/* Btree insertion */

1882 1883
static bool btree_insert_key(struct btree *b, struct bkey *k,
			     struct bkey *replace_key)
K
Kent Overstreet 已提交
1884
{
1885
	unsigned status;
K
Kent Overstreet 已提交
1886 1887

	BUG_ON(bkey_cmp(k, &b->key) > 0);
1888

1889 1890 1891 1892
	status = bch_btree_insert_key(&b->keys, k, replace_key);
	if (status != BTREE_INSERT_STATUS_NO_INSERT) {
		bch_check_keys(&b->keys, "%u for %s", status,
			       replace_key ? "replace" : "insert");
K
Kent Overstreet 已提交
1893

1894 1895 1896 1897 1898
		trace_bcache_btree_insert_key(b, k, replace_key != NULL,
					      status);
		return true;
	} else
		return false;
K
Kent Overstreet 已提交
1899 1900
}

1901 1902
static size_t insert_u64s_remaining(struct btree *b)
{
1903
	long ret = bch_btree_keys_u64s_remaining(&b->keys);
1904 1905 1906 1907 1908 1909 1910 1911 1912 1913

	/*
	 * Might land in the middle of an existing extent and have to split it
	 */
	if (b->keys.ops->is_extents)
		ret -= KEY_MAX_U64S;

	return max(ret, 0L);
}

K
Kent Overstreet 已提交
1914
static bool bch_btree_insert_keys(struct btree *b, struct btree_op *op,
K
Kent Overstreet 已提交
1915 1916
				  struct keylist *insert_keys,
				  struct bkey *replace_key)
K
Kent Overstreet 已提交
1917 1918
{
	bool ret = false;
1919
	int oldsize = bch_count_data(&b->keys);
K
Kent Overstreet 已提交
1920

K
Kent Overstreet 已提交
1921
	while (!bch_keylist_empty(insert_keys)) {
K
Kent Overstreet 已提交
1922
		struct bkey *k = insert_keys->keys;
K
Kent Overstreet 已提交
1923

1924
		if (bkey_u64s(k) > insert_u64s_remaining(b))
1925 1926 1927
			break;

		if (bkey_cmp(k, &b->key) <= 0) {
1928 1929
			if (!b->level)
				bkey_put(b->c, k);
K
Kent Overstreet 已提交
1930

1931
			ret |= btree_insert_key(b, k, replace_key);
K
Kent Overstreet 已提交
1932 1933 1934
			bch_keylist_pop_front(insert_keys);
		} else if (bkey_cmp(&START_KEY(k), &b->key) < 0) {
			BKEY_PADDED(key) temp;
K
Kent Overstreet 已提交
1935
			bkey_copy(&temp.key, insert_keys->keys);
K
Kent Overstreet 已提交
1936 1937

			bch_cut_back(&b->key, &temp.key);
K
Kent Overstreet 已提交
1938
			bch_cut_front(&b->key, insert_keys->keys);
K
Kent Overstreet 已提交
1939

1940
			ret |= btree_insert_key(b, &temp.key, replace_key);
K
Kent Overstreet 已提交
1941 1942 1943 1944
			break;
		} else {
			break;
		}
K
Kent Overstreet 已提交
1945 1946
	}

1947 1948 1949
	if (!ret)
		op->insert_collision = true;

1950 1951
	BUG_ON(!bch_keylist_empty(insert_keys) && b->level);

1952
	BUG_ON(bch_count_data(&b->keys) < oldsize);
K
Kent Overstreet 已提交
1953 1954 1955
	return ret;
}

K
Kent Overstreet 已提交
1956 1957
static int btree_split(struct btree *b, struct btree_op *op,
		       struct keylist *insert_keys,
K
Kent Overstreet 已提交
1958
		       struct bkey *replace_key)
K
Kent Overstreet 已提交
1959
{
1960
	bool split;
K
Kent Overstreet 已提交
1961 1962
	struct btree *n1, *n2 = NULL, *n3 = NULL;
	uint64_t start_time = local_clock();
K
Kent Overstreet 已提交
1963
	struct closure cl;
1964
	struct keylist parent_keys;
K
Kent Overstreet 已提交
1965 1966

	closure_init_stack(&cl);
1967
	bch_keylist_init(&parent_keys);
K
Kent Overstreet 已提交
1968

1969 1970 1971 1972 1973 1974
	if (btree_check_reserve(b, op)) {
		if (!b->level)
			return -EINTR;
		else
			WARN(1, "insufficient reserve for split\n");
	}
1975

1976
	n1 = btree_node_alloc_replacement(b, op);
K
Kent Overstreet 已提交
1977 1978 1979
	if (IS_ERR(n1))
		goto err;

1980 1981
	split = set_blocks(btree_bset_first(n1),
			   block_bytes(n1->c)) > (btree_blocks(b) * 4) / 5;
K
Kent Overstreet 已提交
1982 1983 1984 1985

	if (split) {
		unsigned keys = 0;

1986
		trace_bcache_btree_node_split(b, btree_bset_first(n1)->keys);
K
Kent Overstreet 已提交
1987

1988
		n2 = bch_btree_node_alloc(b->c, op, b->level, b->parent);
K
Kent Overstreet 已提交
1989 1990 1991
		if (IS_ERR(n2))
			goto err_free1;

1992
		if (!b->parent) {
1993
			n3 = bch_btree_node_alloc(b->c, op, b->level + 1, NULL);
K
Kent Overstreet 已提交
1994 1995 1996 1997
			if (IS_ERR(n3))
				goto err_free2;
		}

K
Kent Overstreet 已提交
1998 1999 2000
		mutex_lock(&n1->write_lock);
		mutex_lock(&n2->write_lock);

K
Kent Overstreet 已提交
2001
		bch_btree_insert_keys(n1, op, insert_keys, replace_key);
K
Kent Overstreet 已提交
2002

2003 2004
		/*
		 * Has to be a linear search because we don't have an auxiliary
K
Kent Overstreet 已提交
2005 2006 2007
		 * search tree yet
		 */

2008 2009
		while (keys < (btree_bset_first(n1)->keys * 3) / 5)
			keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1),
K
Kent Overstreet 已提交
2010
							keys));
K
Kent Overstreet 已提交
2011

K
Kent Overstreet 已提交
2012
		bkey_copy_key(&n1->key,
2013 2014
			      bset_bkey_idx(btree_bset_first(n1), keys));
		keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), keys));
K
Kent Overstreet 已提交
2015

2016 2017
		btree_bset_first(n2)->keys = btree_bset_first(n1)->keys - keys;
		btree_bset_first(n1)->keys = keys;
K
Kent Overstreet 已提交
2018

2019 2020 2021
		memcpy(btree_bset_first(n2)->start,
		       bset_bkey_last(btree_bset_first(n1)),
		       btree_bset_first(n2)->keys * sizeof(uint64_t));
K
Kent Overstreet 已提交
2022 2023 2024

		bkey_copy_key(&n2->key, &b->key);

2025
		bch_keylist_add(&parent_keys, &n2->key);
K
Kent Overstreet 已提交
2026
		bch_btree_node_write(n2, &cl);
K
Kent Overstreet 已提交
2027
		mutex_unlock(&n2->write_lock);
K
Kent Overstreet 已提交
2028
		rw_unlock(true, n2);
K
Kent Overstreet 已提交
2029
	} else {
2030
		trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys);
K
Kent Overstreet 已提交
2031

K
Kent Overstreet 已提交
2032
		mutex_lock(&n1->write_lock);
K
Kent Overstreet 已提交
2033
		bch_btree_insert_keys(n1, op, insert_keys, replace_key);
K
Kent Overstreet 已提交
2034
	}
K
Kent Overstreet 已提交
2035

2036
	bch_keylist_add(&parent_keys, &n1->key);
K
Kent Overstreet 已提交
2037
	bch_btree_node_write(n1, &cl);
K
Kent Overstreet 已提交
2038
	mutex_unlock(&n1->write_lock);
K
Kent Overstreet 已提交
2039 2040

	if (n3) {
2041
		/* Depth increases, make a new root */
K
Kent Overstreet 已提交
2042
		mutex_lock(&n3->write_lock);
K
Kent Overstreet 已提交
2043
		bkey_copy_key(&n3->key, &MAX_KEY);
2044
		bch_btree_insert_keys(n3, op, &parent_keys, NULL);
K
Kent Overstreet 已提交
2045
		bch_btree_node_write(n3, &cl);
K
Kent Overstreet 已提交
2046
		mutex_unlock(&n3->write_lock);
K
Kent Overstreet 已提交
2047

K
Kent Overstreet 已提交
2048
		closure_sync(&cl);
K
Kent Overstreet 已提交
2049 2050
		bch_btree_set_root(n3);
		rw_unlock(true, n3);
2051 2052
	} else if (!b->parent) {
		/* Root filled up but didn't need to be split */
K
Kent Overstreet 已提交
2053
		closure_sync(&cl);
K
Kent Overstreet 已提交
2054 2055
		bch_btree_set_root(n1);
	} else {
2056
		/* Split a non root node */
K
Kent Overstreet 已提交
2057
		closure_sync(&cl);
2058 2059 2060 2061 2062
		make_btree_freeing_key(b, parent_keys.top);
		bch_keylist_push(&parent_keys);

		bch_btree_insert_node(b->parent, op, &parent_keys, NULL, NULL);
		BUG_ON(!bch_keylist_empty(&parent_keys));
K
Kent Overstreet 已提交
2063 2064
	}

2065
	btree_node_free(b);
K
Kent Overstreet 已提交
2066 2067
	rw_unlock(true, n1);

2068
	bch_time_stats_update(&b->c->btree_split_time, start_time);
K
Kent Overstreet 已提交
2069 2070 2071

	return 0;
err_free2:
2072
	bkey_put(b->c, &n2->key);
2073
	btree_node_free(n2);
K
Kent Overstreet 已提交
2074 2075
	rw_unlock(true, n2);
err_free1:
2076
	bkey_put(b->c, &n1->key);
2077
	btree_node_free(n1);
K
Kent Overstreet 已提交
2078 2079
	rw_unlock(true, n1);
err:
2080
	WARN(1, "bcache: btree split failed (level %u)", b->level);
2081

K
Kent Overstreet 已提交
2082 2083 2084 2085 2086 2087 2088 2089
	if (n3 == ERR_PTR(-EAGAIN) ||
	    n2 == ERR_PTR(-EAGAIN) ||
	    n1 == ERR_PTR(-EAGAIN))
		return -EAGAIN;

	return -ENOMEM;
}

K
Kent Overstreet 已提交
2090
static int bch_btree_insert_node(struct btree *b, struct btree_op *op,
K
Kent Overstreet 已提交
2091
				 struct keylist *insert_keys,
K
Kent Overstreet 已提交
2092 2093
				 atomic_t *journal_ref,
				 struct bkey *replace_key)
K
Kent Overstreet 已提交
2094
{
K
Kent Overstreet 已提交
2095 2096
	struct closure cl;

2097 2098
	BUG_ON(b->level && replace_key);

K
Kent Overstreet 已提交
2099 2100 2101 2102 2103 2104 2105 2106
	closure_init_stack(&cl);

	mutex_lock(&b->write_lock);

	if (write_block(b) != btree_bset_last(b) &&
	    b->keys.last_set_unwritten)
		bch_btree_init_next(b); /* just wrote a set */

2107
	if (bch_keylist_nkeys(insert_keys) > insert_u64s_remaining(b)) {
K
Kent Overstreet 已提交
2108 2109 2110
		mutex_unlock(&b->write_lock);
		goto split;
	}
2111

K
Kent Overstreet 已提交
2112
	BUG_ON(write_block(b) != btree_bset_last(b));
K
Kent Overstreet 已提交
2113

K
Kent Overstreet 已提交
2114 2115 2116 2117 2118 2119
	if (bch_btree_insert_keys(b, op, insert_keys, replace_key)) {
		if (!b->level)
			bch_btree_leaf_dirty(b, journal_ref);
		else
			bch_btree_node_write(b, &cl);
	}
2120

K
Kent Overstreet 已提交
2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142
	mutex_unlock(&b->write_lock);

	/* wait for btree node write if necessary, after unlock */
	closure_sync(&cl);

	return 0;
split:
	if (current->bio_list) {
		op->lock = b->c->root->level + 1;
		return -EAGAIN;
	} else if (op->lock <= b->c->root->level) {
		op->lock = b->c->root->level + 1;
		return -EINTR;
	} else {
		/* Invalidated all iterators */
		int ret = btree_split(b, op, insert_keys, replace_key);

		if (bch_keylist_empty(insert_keys))
			return 0;
		else if (!ret)
			return -EINTR;
		return ret;
2143
	}
K
Kent Overstreet 已提交
2144
}
K
Kent Overstreet 已提交
2145

2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161
int bch_btree_insert_check_key(struct btree *b, struct btree_op *op,
			       struct bkey *check_key)
{
	int ret = -EINTR;
	uint64_t btree_ptr = b->key.ptr[0];
	unsigned long seq = b->seq;
	struct keylist insert;
	bool upgrade = op->lock == -1;

	bch_keylist_init(&insert);

	if (upgrade) {
		rw_unlock(false, b);
		rw_lock(true, b, b->level);

		if (b->key.ptr[0] != btree_ptr ||
2162 2163
                   b->seq != seq + 1) {
                       op->lock = b->level;
2164
			goto out;
2165
               }
2166 2167 2168 2169 2170 2171 2172 2173 2174
	}

	SET_KEY_PTRS(check_key, 1);
	get_random_bytes(&check_key->ptr[0], sizeof(uint64_t));

	SET_PTR_DEV(check_key, 0, PTR_CHECK_DEV);

	bch_keylist_add(&insert, check_key);

K
Kent Overstreet 已提交
2175
	ret = bch_btree_insert_node(b, op, &insert, NULL, NULL);
2176 2177 2178 2179 2180 2181 2182 2183

	BUG_ON(!ret && !bch_keylist_empty(&insert));
out:
	if (upgrade)
		downgrade_write(&b->lock);
	return ret;
}

2184 2185 2186 2187 2188 2189
struct btree_insert_op {
	struct btree_op	op;
	struct keylist	*keys;
	atomic_t	*journal_ref;
	struct bkey	*replace_key;
};
K
Kent Overstreet 已提交
2190

2191
static int btree_insert_fn(struct btree_op *b_op, struct btree *b)
2192 2193 2194
{
	struct btree_insert_op *op = container_of(b_op,
					struct btree_insert_op, op);
K
Kent Overstreet 已提交
2195

2196 2197 2198 2199 2200 2201
	int ret = bch_btree_insert_node(b, &op->op, op->keys,
					op->journal_ref, op->replace_key);
	if (ret && !bch_keylist_empty(op->keys))
		return ret;
	else
		return MAP_DONE;
K
Kent Overstreet 已提交
2202 2203
}

2204 2205
int bch_btree_insert(struct cache_set *c, struct keylist *keys,
		     atomic_t *journal_ref, struct bkey *replace_key)
K
Kent Overstreet 已提交
2206
{
2207
	struct btree_insert_op op;
K
Kent Overstreet 已提交
2208 2209
	int ret = 0;

2210
	BUG_ON(current->bio_list);
2211
	BUG_ON(bch_keylist_empty(keys));
K
Kent Overstreet 已提交
2212

2213 2214 2215 2216
	bch_btree_op_init(&op.op, 0);
	op.keys		= keys;
	op.journal_ref	= journal_ref;
	op.replace_key	= replace_key;
K
Kent Overstreet 已提交
2217

2218 2219 2220 2221 2222 2223
	while (!ret && !bch_keylist_empty(keys)) {
		op.op.lock = 0;
		ret = bch_btree_map_leaf_nodes(&op.op, c,
					       &START_KEY(keys->keys),
					       btree_insert_fn);
	}
K
Kent Overstreet 已提交
2224

2225 2226
	if (ret) {
		struct bkey *k;
K
Kent Overstreet 已提交
2227

2228
		pr_err("error %i", ret);
K
Kent Overstreet 已提交
2229

2230
		while ((k = bch_keylist_pop(keys)))
2231
			bkey_put(c, k);
2232 2233
	} else if (op.op.insert_collision)
		ret = -ESRCH;
2234

K
Kent Overstreet 已提交
2235 2236 2237 2238 2239 2240
	return ret;
}

void bch_btree_set_root(struct btree *b)
{
	unsigned i;
K
Kent Overstreet 已提交
2241 2242 2243
	struct closure cl;

	closure_init_stack(&cl);
K
Kent Overstreet 已提交
2244

K
Kent Overstreet 已提交
2245 2246
	trace_bcache_btree_set_root(b);

K
Kent Overstreet 已提交
2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257
	BUG_ON(!b->written);

	for (i = 0; i < KEY_PTRS(&b->key); i++)
		BUG_ON(PTR_BUCKET(b->c, &b->key, i)->prio != BTREE_PRIO);

	mutex_lock(&b->c->bucket_lock);
	list_del_init(&b->list);
	mutex_unlock(&b->c->bucket_lock);

	b->c->root = b;

K
Kent Overstreet 已提交
2258 2259
	bch_journal_meta(b->c, &cl);
	closure_sync(&cl);
K
Kent Overstreet 已提交
2260 2261
}

2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273
/* Map across nodes or keys */

static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op,
				       struct bkey *from,
				       btree_map_nodes_fn *fn, int flags)
{
	int ret = MAP_CONTINUE;

	if (b->level) {
		struct bkey *k;
		struct btree_iter iter;

2274
		bch_btree_iter_init(&b->keys, &iter, from);
2275

K
Kent Overstreet 已提交
2276
		while ((k = bch_btree_iter_next_filter(&iter, &b->keys,
2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295
						       bch_ptr_bad))) {
			ret = btree(map_nodes_recurse, k, b,
				    op, from, fn, flags);
			from = NULL;

			if (ret != MAP_CONTINUE)
				return ret;
		}
	}

	if (!b->level || flags == MAP_ALL_NODES)
		ret = fn(op, b);

	return ret;
}

int __bch_btree_map_nodes(struct btree_op *op, struct cache_set *c,
			  struct bkey *from, btree_map_nodes_fn *fn, int flags)
{
K
Kent Overstreet 已提交
2296
	return btree_root(map_nodes_recurse, c, op, from, fn, flags);
2297 2298 2299 2300 2301 2302 2303 2304 2305 2306
}

static int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op,
				      struct bkey *from, btree_map_keys_fn *fn,
				      int flags)
{
	int ret = MAP_CONTINUE;
	struct bkey *k;
	struct btree_iter iter;

2307
	bch_btree_iter_init(&b->keys, &iter, from);
2308

K
Kent Overstreet 已提交
2309
	while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) {
2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328
		ret = !b->level
			? fn(op, b, k)
			: btree(map_keys_recurse, k, b, op, from, fn, flags);
		from = NULL;

		if (ret != MAP_CONTINUE)
			return ret;
	}

	if (!b->level && (flags & MAP_END_KEY))
		ret = fn(op, b, &KEY(KEY_INODE(&b->key),
				     KEY_OFFSET(&b->key), 0));

	return ret;
}

int bch_btree_map_keys(struct btree_op *op, struct cache_set *c,
		       struct bkey *from, btree_map_keys_fn *fn, int flags)
{
K
Kent Overstreet 已提交
2329
	return btree_root(map_keys_recurse, c, op, from, fn, flags);
2330 2331
}

K
Kent Overstreet 已提交
2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349
/* Keybuf code */

static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r)
{
	/* Overlapping keys compare equal */
	if (bkey_cmp(&l->key, &START_KEY(&r->key)) <= 0)
		return -1;
	if (bkey_cmp(&START_KEY(&l->key), &r->key) >= 0)
		return 1;
	return 0;
}

static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l,
					    struct keybuf_key *r)
{
	return clamp_t(int64_t, bkey_cmp(&l->key, &r->key), -1, 1);
}

2350 2351
struct refill {
	struct btree_op	op;
2352
	unsigned	nr_found;
2353 2354 2355 2356
	struct keybuf	*buf;
	struct bkey	*end;
	keybuf_pred_fn	*pred;
};
K
Kent Overstreet 已提交
2357

2358 2359 2360 2361 2362 2363
static int refill_keybuf_fn(struct btree_op *op, struct btree *b,
			    struct bkey *k)
{
	struct refill *refill = container_of(op, struct refill, op);
	struct keybuf *buf = refill->buf;
	int ret = MAP_CONTINUE;
K
Kent Overstreet 已提交
2364

2365 2366 2367 2368
	if (bkey_cmp(k, refill->end) >= 0) {
		ret = MAP_DONE;
		goto out;
	}
K
Kent Overstreet 已提交
2369

2370 2371
	if (!KEY_SIZE(k)) /* end key */
		goto out;
K
Kent Overstreet 已提交
2372

2373 2374
	if (refill->pred(buf, k)) {
		struct keybuf_key *w;
K
Kent Overstreet 已提交
2375

2376
		spin_lock(&buf->lock);
K
Kent Overstreet 已提交
2377

2378 2379 2380 2381 2382
		w = array_alloc(&buf->freelist);
		if (!w) {
			spin_unlock(&buf->lock);
			return MAP_DONE;
		}
K
Kent Overstreet 已提交
2383

2384 2385
		w->private = NULL;
		bkey_copy(&w->key, k);
K
Kent Overstreet 已提交
2386

2387 2388
		if (RB_INSERT(&buf->keys, w, node, keybuf_cmp))
			array_free(&buf->freelist, w);
2389 2390
		else
			refill->nr_found++;
K
Kent Overstreet 已提交
2391

2392 2393
		if (array_freelist_empty(&buf->freelist))
			ret = MAP_DONE;
K
Kent Overstreet 已提交
2394

2395
		spin_unlock(&buf->lock);
K
Kent Overstreet 已提交
2396
	}
2397 2398 2399
out:
	buf->last_scanned = *k;
	return ret;
K
Kent Overstreet 已提交
2400 2401 2402
}

void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf,
K
Kent Overstreet 已提交
2403
		       struct bkey *end, keybuf_pred_fn *pred)
K
Kent Overstreet 已提交
2404 2405
{
	struct bkey start = buf->last_scanned;
2406
	struct refill refill;
K
Kent Overstreet 已提交
2407 2408 2409

	cond_resched();

K
Kent Overstreet 已提交
2410
	bch_btree_op_init(&refill.op, -1);
2411 2412 2413 2414
	refill.nr_found	= 0;
	refill.buf	= buf;
	refill.end	= end;
	refill.pred	= pred;
2415 2416 2417

	bch_btree_map_keys(&refill.op, c, &buf->last_scanned,
			   refill_keybuf_fn, MAP_END_KEY);
K
Kent Overstreet 已提交
2418

2419 2420 2421 2422
	trace_bcache_keyscan(refill.nr_found,
			     KEY_INODE(&start), KEY_OFFSET(&start),
			     KEY_INODE(&buf->last_scanned),
			     KEY_OFFSET(&buf->last_scanned));
K
Kent Overstreet 已提交
2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499

	spin_lock(&buf->lock);

	if (!RB_EMPTY_ROOT(&buf->keys)) {
		struct keybuf_key *w;
		w = RB_FIRST(&buf->keys, struct keybuf_key, node);
		buf->start	= START_KEY(&w->key);

		w = RB_LAST(&buf->keys, struct keybuf_key, node);
		buf->end	= w->key;
	} else {
		buf->start	= MAX_KEY;
		buf->end	= MAX_KEY;
	}

	spin_unlock(&buf->lock);
}

static void __bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w)
{
	rb_erase(&w->node, &buf->keys);
	array_free(&buf->freelist, w);
}

void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w)
{
	spin_lock(&buf->lock);
	__bch_keybuf_del(buf, w);
	spin_unlock(&buf->lock);
}

bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start,
				  struct bkey *end)
{
	bool ret = false;
	struct keybuf_key *p, *w, s;
	s.key = *start;

	if (bkey_cmp(end, &buf->start) <= 0 ||
	    bkey_cmp(start, &buf->end) >= 0)
		return false;

	spin_lock(&buf->lock);
	w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp);

	while (w && bkey_cmp(&START_KEY(&w->key), end) < 0) {
		p = w;
		w = RB_NEXT(w, node);

		if (p->private)
			ret = true;
		else
			__bch_keybuf_del(buf, p);
	}

	spin_unlock(&buf->lock);
	return ret;
}

struct keybuf_key *bch_keybuf_next(struct keybuf *buf)
{
	struct keybuf_key *w;
	spin_lock(&buf->lock);

	w = RB_FIRST(&buf->keys, struct keybuf_key, node);

	while (w && w->private)
		w = RB_NEXT(w, node);

	if (w)
		w->private = ERR_PTR(-EINTR);

	spin_unlock(&buf->lock);
	return w;
}

struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c,
2500 2501 2502
					  struct keybuf *buf,
					  struct bkey *end,
					  keybuf_pred_fn *pred)
K
Kent Overstreet 已提交
2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515
{
	struct keybuf_key *ret;

	while (1) {
		ret = bch_keybuf_next(buf);
		if (ret)
			break;

		if (bkey_cmp(&buf->last_scanned, end) >= 0) {
			pr_debug("scan finished");
			break;
		}

K
Kent Overstreet 已提交
2516
		bch_refill_keybuf(c, buf, end, pred);
K
Kent Overstreet 已提交
2517 2518 2519 2520 2521
	}

	return ret;
}

K
Kent Overstreet 已提交
2522
void bch_keybuf_init(struct keybuf *buf)
K
Kent Overstreet 已提交
2523 2524 2525 2526 2527 2528 2529
{
	buf->last_scanned	= MAX_KEY;
	buf->keys		= RB_ROOT;

	spin_lock_init(&buf->lock);
	array_allocator_init(&buf->freelist);
}