btree.c 60.2 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
K
Kent Overstreet 已提交
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
/*
 * 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.
 *
21
 * All configuration is done via sysfs; see Documentation/admin-guide/bcache.rst.
K
Kent Overstreet 已提交
22 23 24 25 26
 */

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

#include <linux/slab.h>
#include <linux/bitops.h>
#include <linux/hash.h>
K
Kent Overstreet 已提交
32
#include <linux/kthread.h>
33
#include <linux/prefetch.h>
K
Kent Overstreet 已提交
34 35
#include <linux/random.h>
#include <linux/rcupdate.h>
36
#include <linux/sched/clock.h>
37
#include <linux/rculist.h>
38
#include <linux/delay.h>
K
Kent Overstreet 已提交
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
#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
93
#define MAX_GC_TIMES		100
T
Tang Junhui 已提交
94 95
#define MIN_GC_NODES		100
#define GC_SLEEP_MS		100
K
Kent Overstreet 已提交
96 97 98 99 100 101

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

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

102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
#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;					\
126 127
	struct btree *_child = bch_btree_node_get((b)->c, op, key, l,	\
						  _w, b);		\
128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
	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);					\
154
		bch_cannibalize_unlock(c);				\
155 156
		if (_r == -EINTR)					\
			schedule();					\
157 158
	} while (_r == -EINTR);						\
									\
159
	finish_wait(&(c)->btree_cache_wait, &(op)->wait);		\
160 161 162
	_r;								\
})

K
Kent Overstreet 已提交
163 164 165 166 167
static inline struct bset *write_block(struct btree *b)
{
	return ((void *) btree_bset_first(b)) + b->written * block_bytes(b->c);
}

K
Kent Overstreet 已提交
168 169 170 171 172 173 174 175 176 177 178 179 180 181
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 已提交
182 183
/* Btree key manipulation */

184
void bkey_put(struct cache_set *c, struct bkey *k)
185
{
186
	unsigned int i;
187 188 189 190 191 192

	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 已提交
193 194 195 196 197
/* Btree IO */

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

200
	crc = bch_crc64_update(crc, data, end - data);
K
Kent Overstreet 已提交
201
	return crc ^ 0xffffffffffffffffULL;
K
Kent Overstreet 已提交
202 203
}

204
void bch_btree_node_read_done(struct btree *b)
K
Kent Overstreet 已提交
205 206
{
	const char *err = "bad btree header";
207
	struct bset *i = btree_bset_first(b);
K
Kent Overstreet 已提交
208
	struct btree_iter *iter;
K
Kent Overstreet 已提交
209

210 211 212 213 214
	/*
	 * c->fill_iter can allocate an iterator with more memory space
	 * than static MAX_BSETS.
	 * See the comment arount cache_set->fill_iter.
	 */
215
	iter = mempool_alloc(&b->c->fill_iter, GFP_NOIO);
K
Kent Overstreet 已提交
216
	iter->size = b->c->sb.bucket_size / b->c->sb.block_size;
K
Kent Overstreet 已提交
217 218
	iter->used = 0;

K
Kent Overstreet 已提交
219
#ifdef CONFIG_BCACHE_DEBUG
220
	iter->b = &b->keys;
K
Kent Overstreet 已提交
221 222
#endif

K
Kent Overstreet 已提交
223
	if (!i->seq)
K
Kent Overstreet 已提交
224 225 226
		goto err;

	for (;
K
Kent Overstreet 已提交
227
	     b->written < btree_blocks(b) && i->seq == b->keys.set[0].data->seq;
K
Kent Overstreet 已提交
228 229 230 231 232 233
	     i = write_block(b)) {
		err = "unsupported bset version";
		if (i->version > BCACHE_BSET_VERSION)
			goto err;

		err = "bad btree header";
234 235
		if (b->written + set_blocks(i, block_bytes(b->c)) >
		    btree_blocks(b))
K
Kent Overstreet 已提交
236 237 238
			goto err;

		err = "bad magic";
239
		if (i->magic != bset_magic(&b->c->sb))
K
Kent Overstreet 已提交
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254
			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 已提交
255
		if (i != b->keys.set[0].data && !i->keys)
K
Kent Overstreet 已提交
256 257
			goto err;

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

260
		b->written += set_blocks(i, block_bytes(b->c));
K
Kent Overstreet 已提交
261 262 263 264
	}

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

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

K
Kent Overstreet 已提交
272
	i = b->keys.set[0].data;
K
Kent Overstreet 已提交
273
	err = "short btree key";
K
Kent Overstreet 已提交
274 275
	if (b->keys.set[0].size &&
	    bkey_cmp(&b->key, &b->keys.set[0].end) < 0)
K
Kent Overstreet 已提交
276 277 278
		goto err;

	if (b->written < btree_blocks(b))
K
Kent Overstreet 已提交
279 280
		bch_bset_init_next(&b->keys, write_block(b),
				   bset_magic(&b->c->sb));
K
Kent Overstreet 已提交
281
out:
282
	mempool_free(iter, &b->c->fill_iter);
K
Kent Overstreet 已提交
283
	return;
K
Kent Overstreet 已提交
284 285
err:
	set_btree_node_io_error(b);
K
Kent Overstreet 已提交
286
	bch_cache_set_error(b->c, "%s at bucket %zu, block %u, %u keys",
K
Kent Overstreet 已提交
287
			    err, PTR_BUCKET_NR(b->c, &b->key, 0),
K
Kent Overstreet 已提交
288
			    bset_block_offset(b, i), i->keys);
K
Kent Overstreet 已提交
289 290 291
	goto out;
}

292
static void btree_node_read_endio(struct bio *bio)
K
Kent Overstreet 已提交
293
{
K
Kent Overstreet 已提交
294
	struct closure *cl = bio->bi_private;
295

K
Kent Overstreet 已提交
296 297
	closure_put(cl);
}
K
Kent Overstreet 已提交
298

299
static void bch_btree_node_read(struct btree *b)
K
Kent Overstreet 已提交
300 301 302 303
{
	uint64_t start_time = local_clock();
	struct closure cl;
	struct bio *bio;
K
Kent Overstreet 已提交
304

K
Kent Overstreet 已提交
305 306
	trace_bcache_btree_read(b);

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

K
Kent Overstreet 已提交
309
	bio = bch_bbio_alloc(b->c);
310
	bio->bi_iter.bi_size = KEY_SIZE(&b->key) << 9;
K
Kent Overstreet 已提交
311 312
	bio->bi_end_io	= btree_node_read_endio;
	bio->bi_private	= &cl;
313
	bio->bi_opf = REQ_OP_READ | REQ_META;
K
Kent Overstreet 已提交
314

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

K
Kent Overstreet 已提交
317 318
	bch_submit_bbio(bio, b->c, &b->key, 0);
	closure_sync(&cl);
K
Kent Overstreet 已提交
319

320
	if (bio->bi_status)
K
Kent Overstreet 已提交
321 322 323 324 325 326 327 328 329 330 331 332
		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:
333
	bch_cache_set_error(b->c, "io error reading bucket %zu",
K
Kent Overstreet 已提交
334
			    PTR_BUCKET_NR(b->c, &b->key, 0));
K
Kent Overstreet 已提交
335 336 337 338 339 340
}

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))
341
		wake_up_allocators(b->c);
K
Kent Overstreet 已提交
342 343 344 345 346 347 348 349 350 351

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

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

352 353 354 355 356 357 358
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 已提交
359
static void __btree_node_write_done(struct closure *cl)
K
Kent Overstreet 已提交
360
{
361
	struct btree *b = container_of(cl, struct btree, io);
K
Kent Overstreet 已提交
362 363 364 365 366 367 368
	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 已提交
369
		schedule_delayed_work(&b->work, 30 * HZ);
K
Kent Overstreet 已提交
370

371
	closure_return_with_destructor(cl, btree_node_write_unlock);
K
Kent Overstreet 已提交
372 373
}

K
Kent Overstreet 已提交
374
static void btree_node_write_done(struct closure *cl)
K
Kent Overstreet 已提交
375
{
376
	struct btree *b = container_of(cl, struct btree, io);
K
Kent Overstreet 已提交
377

378
	bio_free_pages(b->bio);
K
Kent Overstreet 已提交
379
	__btree_node_write_done(cl);
K
Kent Overstreet 已提交
380 381
}

382
static void btree_node_write_endio(struct bio *bio)
K
Kent Overstreet 已提交
383 384
{
	struct closure *cl = bio->bi_private;
385
	struct btree *b = container_of(cl, struct btree, io);
K
Kent Overstreet 已提交
386

387
	if (bio->bi_status)
K
Kent Overstreet 已提交
388 389
		set_btree_node_io_error(b);

390
	bch_bbio_count_io_errors(b->c, bio, bio->bi_status, "writing btree");
K
Kent Overstreet 已提交
391 392 393 394
	closure_put(cl);
}

static void do_btree_node_write(struct btree *b)
K
Kent Overstreet 已提交
395
{
396
	struct closure *cl = &b->io;
397
	struct bset *i = btree_bset_last(b);
K
Kent Overstreet 已提交
398 399 400 401 402
	BKEY_PADDED(key) k;

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

K
Kent Overstreet 已提交
403 404 405 406
	BUG_ON(b->bio);
	b->bio = bch_bbio_alloc(b->c);

	b->bio->bi_end_io	= btree_node_write_endio;
K
Kent Overstreet 已提交
407
	b->bio->bi_private	= cl;
408
	b->bio->bi_iter.bi_size	= roundup(set_bytes(i), block_bytes(b->c));
409
	b->bio->bi_opf		= REQ_OP_WRITE | REQ_META | REQ_FUA;
410
	bch_bio_map(b->bio, i);
K
Kent Overstreet 已提交
411

K
Kent Overstreet 已提交
412 413 414 415 416 417 418 419 420 421 422 423 424 425 426
	/*
	 * 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 已提交
427
	bkey_copy(&k.key, &b->key);
428
	SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) +
K
Kent Overstreet 已提交
429
		       bset_sector_offset(&b->keys, i));
K
Kent Overstreet 已提交
430

431
	if (!bch_bio_alloc_pages(b->bio, __GFP_NOWARN|GFP_NOWAIT)) {
K
Kent Overstreet 已提交
432
		struct bio_vec *bv;
433
		void *addr = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1));
434
		struct bvec_iter_all iter_all;
K
Kent Overstreet 已提交
435

436
		bio_for_each_segment_all(bv, b->bio, iter_all) {
437 438 439
			memcpy(page_address(bv->bv_page), addr, PAGE_SIZE);
			addr += PAGE_SIZE;
		}
K
Kent Overstreet 已提交
440 441 442

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

K
Kent Overstreet 已提交
443
		continue_at(cl, btree_node_write_done, NULL);
K
Kent Overstreet 已提交
444
	} else {
445 446 447 448
		/*
		 * No problem for multipage bvec since the bio is
		 * just allocated
		 */
K
Kent Overstreet 已提交
449
		b->bio->bi_vcnt = 0;
450
		bch_bio_map(b->bio, i);
K
Kent Overstreet 已提交
451 452 453 454

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

		closure_sync(cl);
455
		continue_at_nobarrier(cl, __btree_node_write_done, NULL);
K
Kent Overstreet 已提交
456 457 458
	}
}

K
Kent Overstreet 已提交
459
void __bch_btree_node_write(struct btree *b, struct closure *parent)
K
Kent Overstreet 已提交
460
{
461
	struct bset *i = btree_bset_last(b);
K
Kent Overstreet 已提交
462

K
Kent Overstreet 已提交
463 464
	lockdep_assert_held(&b->write_lock);

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

K
Kent Overstreet 已提交
467
	BUG_ON(current->bio_list);
K
Kent Overstreet 已提交
468 469
	BUG_ON(b->written >= btree_blocks(b));
	BUG_ON(b->written && !i->keys);
470
	BUG_ON(btree_bset_first(b)->seq != i->seq);
471
	bch_check_keys(&b->keys, "writing");
K
Kent Overstreet 已提交
472 473 474

	cancel_delayed_work(&b->work);

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

K
Kent Overstreet 已提交
479 480 481
	clear_bit(BTREE_NODE_dirty,	 &b->flags);
	change_bit(BTREE_NODE_write_idx, &b->flags);

K
Kent Overstreet 已提交
482
	do_btree_node_write(b);
K
Kent Overstreet 已提交
483

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

K
Kent Overstreet 已提交
487
	b->written += set_blocks(i, block_bytes(b->c));
K
Kent Overstreet 已提交
488
}
K
Kent Overstreet 已提交
489

K
Kent Overstreet 已提交
490 491
void bch_btree_node_write(struct btree *b, struct closure *parent)
{
492
	unsigned int nsets = b->keys.nsets;
K
Kent Overstreet 已提交
493 494 495 496

	lockdep_assert_held(&b->lock);

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

498 499 500 501
	/*
	 * 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 已提交
502
	if (nsets && !b->keys.nsets)
503 504
		bch_btree_verify(b);

K
Kent Overstreet 已提交
505
	bch_btree_init_next(b);
K
Kent Overstreet 已提交
506 507
}

508 509 510 511 512
static void bch_btree_node_write_sync(struct btree *b)
{
	struct closure cl;

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

	mutex_lock(&b->write_lock);
515
	bch_btree_node_write(b, &cl);
K
Kent Overstreet 已提交
516 517
	mutex_unlock(&b->write_lock);

518 519 520
	closure_sync(&cl);
}

K
Kent Overstreet 已提交
521
static void btree_node_write_work(struct work_struct *w)
K
Kent Overstreet 已提交
522 523 524
{
	struct btree *b = container_of(to_delayed_work(w), struct btree, work);

K
Kent Overstreet 已提交
525
	mutex_lock(&b->write_lock);
K
Kent Overstreet 已提交
526
	if (btree_node_dirty(b))
K
Kent Overstreet 已提交
527 528
		__bch_btree_node_write(b, NULL);
	mutex_unlock(&b->write_lock);
K
Kent Overstreet 已提交
529 530
}

K
Kent Overstreet 已提交
531
static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref)
K
Kent Overstreet 已提交
532
{
533
	struct bset *i = btree_bset_last(b);
K
Kent Overstreet 已提交
534 535
	struct btree_write *w = btree_current_write(b);

K
Kent Overstreet 已提交
536 537
	lockdep_assert_held(&b->write_lock);

K
Kent Overstreet 已提交
538 539
	BUG_ON(!b->written);
	BUG_ON(!i->keys);
K
Kent Overstreet 已提交
540

K
Kent Overstreet 已提交
541
	if (!btree_node_dirty(b))
K
Kent Overstreet 已提交
542
		schedule_delayed_work(&b->work, 30 * HZ);
K
Kent Overstreet 已提交
543

K
Kent Overstreet 已提交
544
	set_btree_node_dirty(b);
K
Kent Overstreet 已提交
545

K
Kent Overstreet 已提交
546
	if (journal_ref) {
K
Kent Overstreet 已提交
547
		if (w->journal &&
K
Kent Overstreet 已提交
548
		    journal_pin_cmp(b->c, w->journal, journal_ref)) {
K
Kent Overstreet 已提交
549 550 551 552 553
			atomic_dec_bug(w->journal);
			w->journal = NULL;
		}

		if (!w->journal) {
K
Kent Overstreet 已提交
554
			w->journal = journal_ref;
K
Kent Overstreet 已提交
555 556 557 558 559
			atomic_inc(w->journal);
		}
	}

	/* Force write if set is too big */
K
Kent Overstreet 已提交
560 561 562
	if (set_bytes(i) > PAGE_SIZE - 48 &&
	    !current->bio_list)
		bch_btree_node_write(b, NULL);
K
Kent Overstreet 已提交
563 564 565 566 567 568 569 570 571 572
}

/*
 * 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)						\
573
	max_t(int, 0, c->btree_cache_used - mca_reserve(c))
K
Kent Overstreet 已提交
574 575 576

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

K
Kent Overstreet 已提交
579
	bch_btree_keys_free(&b->keys);
K
Kent Overstreet 已提交
580

581
	b->c->btree_cache_used--;
582
	list_move(&b->list, &b->c->btree_cache_freed);
K
Kent Overstreet 已提交
583 584 585 586 587 588 589 590 591 592 593
}

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);
}

594
static unsigned int btree_order(struct bkey *k)
K
Kent Overstreet 已提交
595 596 597 598 599 600
{
	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 已提交
601
	if (!bch_btree_keys_alloc(&b->keys,
602
				  max_t(unsigned int,
603 604 605
					ilog2(b->c->btree_pages),
					btree_order(k)),
				  gfp)) {
606
		b->c->btree_cache_used++;
607 608 609 610
		list_move(&b->list, &b->c->btree_cache);
	} else {
		list_move(&b->list, &b->c->btree_cache_freed);
	}
K
Kent Overstreet 已提交
611 612 613 614 615
}

static struct btree *mca_bucket_alloc(struct cache_set *c,
				      struct bkey *k, gfp_t gfp)
{
616 617 618 619
	/*
	 * kzalloc() is necessary here for initialization,
	 * see code comments in bch_btree_keys_init().
	 */
K
Kent Overstreet 已提交
620
	struct btree *b = kzalloc(sizeof(struct btree), gfp);
621

K
Kent Overstreet 已提交
622 623 624 625 626
	if (!b)
		return NULL;

	init_rwsem(&b->lock);
	lockdep_set_novalidate_class(&b->lock);
K
Kent Overstreet 已提交
627 628
	mutex_init(&b->write_lock);
	lockdep_set_novalidate_class(&b->write_lock);
K
Kent Overstreet 已提交
629
	INIT_LIST_HEAD(&b->list);
K
Kent Overstreet 已提交
630
	INIT_DELAYED_WORK(&b->work, btree_node_write_work);
K
Kent Overstreet 已提交
631
	b->c = c;
632
	sema_init(&b->io_mutex, 1);
K
Kent Overstreet 已提交
633 634 635 636 637

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

638
static int mca_reap(struct btree *b, unsigned int min_order, bool flush)
K
Kent Overstreet 已提交
639
{
640 641 642
	struct closure cl;

	closure_init_stack(&cl);
K
Kent Overstreet 已提交
643 644 645 646 647
	lockdep_assert_held(&b->c->bucket_lock);

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

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

K
Kent Overstreet 已提交
650
	if (b->keys.page_order < min_order)
651 652 653 654 655 656 657 658 659
		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 已提交
660 661
	}

662
retry:
663 664 665 666 667
	/*
	 * BTREE_NODE_dirty might be cleared in btree_flush_btree() by
	 * __bch_btree_node_write(). To avoid an extra flush, acquire
	 * b->write_lock before checking BTREE_NODE_dirty bit.
	 */
K
Kent Overstreet 已提交
668
	mutex_lock(&b->write_lock);
669 670 671 672 673 674 675 676 677 678 679 680
	/*
	 * If this btree node is selected in btree_flush_write() by journal
	 * code, delay and retry until the node is flushed by journal code
	 * and BTREE_NODE_journal_flush bit cleared by btree_flush_write().
	 */
	if (btree_node_journal_flush(b)) {
		pr_debug("bnode %p is flushing by journal, retry", b);
		mutex_unlock(&b->write_lock);
		udelay(1);
		goto retry;
	}

681
	if (btree_node_dirty(b))
K
Kent Overstreet 已提交
682 683 684 685
		__bch_btree_node_write(b, &cl);
	mutex_unlock(&b->write_lock);

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

687
	/* wait for any in flight btree write */
688 689
	down(&b->io_mutex);
	up(&b->io_mutex);
690

K
Kent Overstreet 已提交
691
	return 0;
692 693 694
out_unlock:
	rw_unlock(true, b);
	return -ENOMEM;
K
Kent Overstreet 已提交
695 696
}

697 698
static unsigned long bch_mca_scan(struct shrinker *shrink,
				  struct shrink_control *sc)
K
Kent Overstreet 已提交
699 700 701 702
{
	struct cache_set *c = container_of(shrink, struct cache_set, shrink);
	struct btree *b, *t;
	unsigned long i, nr = sc->nr_to_scan;
703
	unsigned long freed = 0;
704
	unsigned int btree_cache_used;
K
Kent Overstreet 已提交
705 706

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

709
	if (c->btree_cache_alloc_lock)
710
		return SHRINK_STOP;
K
Kent Overstreet 已提交
711 712

	/* Return -1 if we can't do anything right now */
713
	if (sc->gfp_mask & __GFP_IO)
K
Kent Overstreet 已提交
714 715 716 717
		mutex_lock(&c->bucket_lock);
	else if (!mutex_trylock(&c->bucket_lock))
		return -1;

718 719 720 721 722 723 724
	/*
	 * 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 已提交
725 726 727 728
	nr /= c->btree_pages;
	nr = min_t(unsigned long, nr, mca_can_free(c));

	i = 0;
729
	btree_cache_used = c->btree_cache_used;
K
Kent Overstreet 已提交
730
	list_for_each_entry_safe(b, t, &c->btree_cache_freeable, list) {
731 732
		if (nr <= 0)
			goto out;
K
Kent Overstreet 已提交
733 734

		if (++i > 3 &&
735
		    !mca_reap(b, 0, false)) {
K
Kent Overstreet 已提交
736 737
			mca_data_free(b);
			rw_unlock(true, b);
738
			freed++;
K
Kent Overstreet 已提交
739
		}
740
		nr--;
K
Kent Overstreet 已提交
741 742
	}

743
	for (;  (nr--) && i < btree_cache_used; i++) {
K
Kent Overstreet 已提交
744 745 746
		if (list_empty(&c->btree_cache))
			goto out;

K
Kent Overstreet 已提交
747 748 749 750
		b = list_first_entry(&c->btree_cache, struct btree, list);
		list_rotate_left(&c->btree_cache);

		if (!b->accessed &&
751
		    !mca_reap(b, 0, false)) {
K
Kent Overstreet 已提交
752 753 754
			mca_bucket_free(b);
			mca_data_free(b);
			rw_unlock(true, b);
755
			freed++;
K
Kent Overstreet 已提交
756 757 758 759 760
		} else
			b->accessed = 0;
	}
out:
	mutex_unlock(&c->bucket_lock);
761
	return freed * c->btree_pages;
762 763 764 765 766 767 768 769 770 771
}

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;

772
	if (c->btree_cache_alloc_lock)
773 774 775
		return 0;

	return mca_can_free(c) * c->btree_pages;
K
Kent Overstreet 已提交
776 777 778 779 780 781
}

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

K
Kent Overstreet 已提交
783 784 785 786 787 788 789 790 791 792
	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);
793 794

	free_pages((unsigned long) c->verify_ondisk, ilog2(bucket_pages(c)));
K
Kent Overstreet 已提交
795 796 797 798 799 800 801 802
#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);

803 804 805 806 807
		/*
		 * This function is called by cache_set_free(), no I/O
		 * request on cache now, it is unnecessary to acquire
		 * b->write_lock before clearing BTREE_NODE_dirty anymore.
		 */
808
		if (btree_node_dirty(b)) {
K
Kent Overstreet 已提交
809
			btree_complete_write(b, btree_current_write(b));
810 811
			clear_bit(BTREE_NODE_dirty, &b->flags);
		}
K
Kent Overstreet 已提交
812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827
		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)
{
828
	unsigned int i;
K
Kent Overstreet 已提交
829 830

	for (i = 0; i < mca_reserve(c); i++)
K
Kent Overstreet 已提交
831 832
		if (!mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL))
			return -ENOMEM;
K
Kent Overstreet 已提交
833 834 835 836 837 838 839

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

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

840 841 842
	c->verify_ondisk = (void *)
		__get_free_pages(GFP_KERNEL, ilog2(bucket_pages(c)));

K
Kent Overstreet 已提交
843 844 845
	c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL);

	if (c->verify_data &&
K
Kent Overstreet 已提交
846
	    c->verify_data->keys.set->data)
K
Kent Overstreet 已提交
847 848 849 850 851
		list_del_init(&c->verify_data->list);
	else
		c->verify_data = NULL;
#endif

852 853
	c->shrink.count_objects = bch_mca_count;
	c->shrink.scan_objects = bch_mca_scan;
K
Kent Overstreet 已提交
854 855
	c->shrink.seeks = 4;
	c->shrink.batch = c->btree_pages * 2;
856 857 858 859

	if (register_shrinker(&c->shrink))
		pr_warn("bcache: %s: could not register shrinker",
				__func__);
K
Kent Overstreet 已提交
860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884

	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;
}

885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901
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 已提交
902
{
903
	struct btree *b;
K
Kent Overstreet 已提交
904

K
Kent Overstreet 已提交
905 906
	trace_bcache_btree_cache_cannibalize(c);

907 908
	if (mca_cannibalize_lock(c, op))
		return ERR_PTR(-EINTR);
K
Kent Overstreet 已提交
909

910 911 912
	list_for_each_entry_reverse(b, &c->btree_cache, list)
		if (!mca_reap(b, btree_order(k), false))
			return b;
K
Kent Overstreet 已提交
913

914 915 916
	list_for_each_entry_reverse(b, &c->btree_cache, list)
		if (!mca_reap(b, btree_order(k), true))
			return b;
K
Kent Overstreet 已提交
917

918
	WARN(1, "btree cache cannibalize failed\n");
919
	return ERR_PTR(-ENOMEM);
K
Kent Overstreet 已提交
920 921 922 923 924 925 926 927
}

/*
 * 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.
 */
928
static void bch_cannibalize_unlock(struct cache_set *c)
K
Kent Overstreet 已提交
929
{
930 931 932
	if (c->btree_cache_alloc_lock == current) {
		c->btree_cache_alloc_lock = NULL;
		wake_up(&c->btree_cache_wait);
K
Kent Overstreet 已提交
933 934 935
	}
}

936 937
static struct btree *mca_alloc(struct cache_set *c, struct btree_op *op,
			       struct bkey *k, int level)
K
Kent Overstreet 已提交
938 939 940
{
	struct btree *b;

941 942
	BUG_ON(current->bio_list);

K
Kent Overstreet 已提交
943 944 945 946 947 948 949 950 951
	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)
952
		if (!mca_reap(b, btree_order(k), false))
K
Kent Overstreet 已提交
953 954 955 956 957 958
			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)
959
		if (!mca_reap(b, 0, false)) {
K
Kent Overstreet 已提交
960
			mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO);
K
Kent Overstreet 已提交
961
			if (!b->keys.set[0].data)
K
Kent Overstreet 已提交
962 963 964 965 966 967 968 969 970 971
				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 已提交
972
	if (!b->keys.set->data)
K
Kent Overstreet 已提交
973 974
		goto err;
out:
975
	BUG_ON(b->io_mutex.count != 1);
K
Kent Overstreet 已提交
976 977 978 979 980 981 982

	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_);
983
	b->parent	= (void *) ~0UL;
K
Kent Overstreet 已提交
984 985 986
	b->flags	= 0;
	b->written	= 0;
	b->level	= level;
K
Kent Overstreet 已提交
987

988
	if (!b->level)
K
Kent Overstreet 已提交
989 990
		bch_btree_keys_init(&b->keys, &bch_extent_keys_ops,
				    &b->c->expensive_debug_checks);
991
	else
K
Kent Overstreet 已提交
992 993
		bch_btree_keys_init(&b->keys, &bch_btree_keys_ops,
				    &b->c->expensive_debug_checks);
K
Kent Overstreet 已提交
994 995 996 997 998 999

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

1000
	b = mca_cannibalize(c, op, k);
K
Kent Overstreet 已提交
1001 1002 1003 1004 1005 1006
	if (!IS_ERR(b))
		goto out;

	return b;
}

1007
/*
K
Kent Overstreet 已提交
1008 1009 1010
 * bch_btree_node_get - find a btree node in the cache and lock it, reading it
 * in from disk if necessary.
 *
K
Kent Overstreet 已提交
1011
 * If IO is necessary and running under generic_make_request, returns -EAGAIN.
K
Kent Overstreet 已提交
1012 1013 1014 1015
 *
 * The btree node will have either a read or a write lock held, depending on
 * level and op->lock.
 */
1016
struct btree *bch_btree_node_get(struct cache_set *c, struct btree_op *op,
1017 1018
				 struct bkey *k, int level, bool write,
				 struct btree *parent)
K
Kent Overstreet 已提交
1019 1020 1021 1022 1023 1024 1025 1026 1027
{
	int i = 0;
	struct btree *b;

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

	if (!b) {
K
Kent Overstreet 已提交
1028 1029 1030
		if (current->bio_list)
			return ERR_PTR(-EAGAIN);

K
Kent Overstreet 已提交
1031
		mutex_lock(&c->bucket_lock);
1032
		b = mca_alloc(c, op, k, level);
K
Kent Overstreet 已提交
1033 1034 1035 1036 1037 1038 1039
		mutex_unlock(&c->bucket_lock);

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

K
Kent Overstreet 已提交
1040
		bch_btree_node_read(b);
K
Kent Overstreet 已提交
1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052

		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);
	}

1053 1054 1055 1056 1057 1058 1059
	if (btree_node_io_error(b)) {
		rw_unlock(write, b);
		return ERR_PTR(-EIO);
	}

	BUG_ON(!b->written);

1060
	b->parent = parent;
K
Kent Overstreet 已提交
1061 1062
	b->accessed = 1;

K
Kent Overstreet 已提交
1063 1064 1065
	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 已提交
1066 1067
	}

K
Kent Overstreet 已提交
1068 1069
	for (; i <= b->keys.nsets; i++)
		prefetch(b->keys.set[i].data);
K
Kent Overstreet 已提交
1070 1071 1072 1073

	return b;
}

1074
static void btree_node_prefetch(struct btree *parent, struct bkey *k)
K
Kent Overstreet 已提交
1075 1076 1077
{
	struct btree *b;

1078 1079 1080
	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 已提交
1081 1082

	if (!IS_ERR_OR_NULL(b)) {
1083
		b->parent = parent;
K
Kent Overstreet 已提交
1084
		bch_btree_node_read(b);
K
Kent Overstreet 已提交
1085 1086 1087 1088 1089 1090
		rw_unlock(true, b);
	}
}

/* Btree alloc */

1091
static void btree_node_free(struct btree *b)
K
Kent Overstreet 已提交
1092
{
K
Kent Overstreet 已提交
1093 1094
	trace_bcache_btree_node_free(b);

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

1097
retry:
K
Kent Overstreet 已提交
1098
	mutex_lock(&b->write_lock);
1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110
	/*
	 * If the btree node is selected and flushing in btree_flush_write(),
	 * delay and retry until the BTREE_NODE_journal_flush bit cleared,
	 * then it is safe to free the btree node here. Otherwise this btree
	 * node will be in race condition.
	 */
	if (btree_node_journal_flush(b)) {
		mutex_unlock(&b->write_lock);
		pr_debug("bnode %p journal_flush set, retry", b);
		udelay(1);
		goto retry;
	}
K
Kent Overstreet 已提交
1111

1112
	if (btree_node_dirty(b)) {
K
Kent Overstreet 已提交
1113
		btree_complete_write(b, btree_current_write(b));
1114 1115
		clear_bit(BTREE_NODE_dirty, &b->flags);
	}
K
Kent Overstreet 已提交
1116

K
Kent Overstreet 已提交
1117 1118
	mutex_unlock(&b->write_lock);

K
Kent Overstreet 已提交
1119 1120 1121 1122 1123 1124 1125 1126
	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);
}

1127
struct btree *__bch_btree_node_alloc(struct cache_set *c, struct btree_op *op,
1128 1129
				     int level, bool wait,
				     struct btree *parent)
K
Kent Overstreet 已提交
1130 1131 1132 1133 1134 1135
{
	BKEY_PADDED(key) k;
	struct btree *b = ERR_PTR(-EAGAIN);

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

1139
	bkey_put(c, &k.key);
K
Kent Overstreet 已提交
1140 1141
	SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS);

1142
	b = mca_alloc(c, op, &k.key, level);
K
Kent Overstreet 已提交
1143 1144 1145 1146
	if (IS_ERR(b))
		goto err_free;

	if (!b) {
K
Kent Overstreet 已提交
1147 1148
		cache_bug(c,
			"Tried to allocate bucket that was in btree cache");
K
Kent Overstreet 已提交
1149 1150 1151 1152
		goto retry;
	}

	b->accessed = 1;
1153
	b->parent = parent;
K
Kent Overstreet 已提交
1154
	bch_bset_init_next(&b->keys, b->keys.set->data, bset_magic(&b->c->sb));
K
Kent Overstreet 已提交
1155 1156

	mutex_unlock(&c->bucket_lock);
K
Kent Overstreet 已提交
1157 1158

	trace_bcache_btree_node_alloc(b);
K
Kent Overstreet 已提交
1159 1160 1161 1162 1163
	return b;
err_free:
	bch_bucket_free(c, &k.key);
err:
	mutex_unlock(&c->bucket_lock);
K
Kent Overstreet 已提交
1164

1165
	trace_bcache_btree_node_alloc_fail(c);
K
Kent Overstreet 已提交
1166 1167 1168
	return b;
}

1169
static struct btree *bch_btree_node_alloc(struct cache_set *c,
1170 1171
					  struct btree_op *op, int level,
					  struct btree *parent)
1172
{
1173
	return __bch_btree_node_alloc(c, op, level, op != NULL, parent);
1174 1175
}

1176 1177
static struct btree *btree_node_alloc_replacement(struct btree *b,
						  struct btree_op *op)
K
Kent Overstreet 已提交
1178
{
1179
	struct btree *n = bch_btree_node_alloc(b->c, op, b->level, b->parent);
1180

1181
	if (!IS_ERR_OR_NULL(n)) {
K
Kent Overstreet 已提交
1182
		mutex_lock(&n->write_lock);
1183
		bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort);
1184
		bkey_copy_key(&n->key, &b->key);
K
Kent Overstreet 已提交
1185
		mutex_unlock(&n->write_lock);
1186
	}
K
Kent Overstreet 已提交
1187 1188 1189 1190

	return n;
}

1191 1192
static void make_btree_freeing_key(struct btree *b, struct bkey *k)
{
1193
	unsigned int i;
1194

1195 1196 1197 1198
	mutex_lock(&b->c->bucket_lock);

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

1199 1200 1201
	bkey_copy(k, &b->key);
	bkey_copy_key(k, &ZERO_KEY);

1202 1203 1204 1205
	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)));
1206

1207
	mutex_unlock(&b->c->bucket_lock);
1208 1209
}

1210 1211 1212 1213
static int btree_check_reserve(struct btree *b, struct btree_op *op)
{
	struct cache_set *c = b->c;
	struct cache *ca;
1214
	unsigned int i, reserve = (c->root->level - b->level) * 2 + 1;
1215 1216 1217 1218 1219 1220

	mutex_lock(&c->bucket_lock);

	for_each_cache(ca, c, i)
		if (fifo_used(&ca->free[RESERVE_BTREE]) < reserve) {
			if (op)
1221
				prepare_to_wait(&c->btree_cache_wait, &op->wait,
1222
						TASK_UNINTERRUPTIBLE);
1223 1224
			mutex_unlock(&c->bucket_lock);
			return -EINTR;
1225 1226 1227
		}

	mutex_unlock(&c->bucket_lock);
1228 1229

	return mca_cannibalize_lock(b->c, op);
1230 1231
}

K
Kent Overstreet 已提交
1232 1233
/* Garbage collection */

1234 1235
static uint8_t __bch_btree_mark_key(struct cache_set *c, int level,
				    struct bkey *k)
K
Kent Overstreet 已提交
1236 1237
{
	uint8_t stale = 0;
1238
	unsigned int i;
K
Kent Overstreet 已提交
1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254
	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 已提交
1255 1256
		if (gen_after(g->last_gc, PTR_GEN(k, i)))
			g->last_gc = PTR_GEN(k, i);
K
Kent Overstreet 已提交
1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271

		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);
1272 1273
		else if (!GC_MARK(g))
			SET_GC_MARK(g, GC_MARK_RECLAIMABLE);
K
Kent Overstreet 已提交
1274 1275

		/* guard against overflow */
1276
		SET_GC_SECTORS_USED(g, min_t(unsigned int,
K
Kent Overstreet 已提交
1277
					     GC_SECTORS_USED(g) + KEY_SIZE(k),
1278
					     MAX_GC_SECTORS_USED));
K
Kent Overstreet 已提交
1279 1280 1281 1282 1283 1284 1285 1286 1287

		BUG_ON(!GC_SECTORS_USED(g));
	}

	return stale;
}

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

1288 1289
void bch_initial_mark_key(struct cache_set *c, int level, struct bkey *k)
{
1290
	unsigned int i;
1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307

	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);
}

1308 1309 1310 1311 1312
void bch_update_bucket_in_use(struct cache_set *c, struct gc_stat *stats)
{
	stats->in_use = (c->nbuckets - c->avail_nbuckets) * 100 / c->nbuckets;
}

K
Kent Overstreet 已提交
1313
static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc)
K
Kent Overstreet 已提交
1314 1315
{
	uint8_t stale = 0;
1316
	unsigned int keys = 0, good_keys = 0;
K
Kent Overstreet 已提交
1317 1318 1319 1320 1321 1322
	struct bkey *k;
	struct btree_iter iter;
	struct bset_tree *t;

	gc->nodes++;

1323
	for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) {
K
Kent Overstreet 已提交
1324
		stale = max(stale, btree_mark_key(b, k));
K
Kent Overstreet 已提交
1325
		keys++;
K
Kent Overstreet 已提交
1326

K
Kent Overstreet 已提交
1327
		if (bch_ptr_bad(&b->keys, k))
K
Kent Overstreet 已提交
1328 1329 1330 1331
			continue;

		gc->key_bytes += bkey_u64s(k);
		gc->nkeys++;
K
Kent Overstreet 已提交
1332
		good_keys++;
K
Kent Overstreet 已提交
1333 1334 1335 1336

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

K
Kent Overstreet 已提交
1337
	for (t = b->keys.set; t <= &b->keys.set[b->keys.nsets]; t++)
K
Kent Overstreet 已提交
1338
		btree_bug_on(t->size &&
K
Kent Overstreet 已提交
1339
			     bset_written(&b->keys, t) &&
K
Kent Overstreet 已提交
1340 1341 1342
			     bkey_cmp(&b->key, &t->end) < 0,
			     b, "found short btree key in gc");

K
Kent Overstreet 已提交
1343 1344
	if (b->c->gc_always_rewrite)
		return true;
K
Kent Overstreet 已提交
1345

K
Kent Overstreet 已提交
1346 1347
	if (stale > 10)
		return true;
K
Kent Overstreet 已提交
1348

K
Kent Overstreet 已提交
1349 1350
	if ((keys - good_keys) * 2 > keys)
		return true;
K
Kent Overstreet 已提交
1351

K
Kent Overstreet 已提交
1352
	return false;
K
Kent Overstreet 已提交
1353 1354
}

K
Kent Overstreet 已提交
1355
#define GC_MERGE_NODES	4U
K
Kent Overstreet 已提交
1356 1357 1358

struct gc_merge_info {
	struct btree	*b;
1359
	unsigned int	keys;
K
Kent Overstreet 已提交
1360 1361
};

1362 1363 1364 1365
static int bch_btree_insert_node(struct btree *b, struct btree_op *op,
				 struct keylist *insert_keys,
				 atomic_t *journal_ref,
				 struct bkey *replace_key);
K
Kent Overstreet 已提交
1366 1367

static int btree_gc_coalesce(struct btree *b, struct btree_op *op,
1368
			     struct gc_stat *gc, struct gc_merge_info *r)
K
Kent Overstreet 已提交
1369
{
1370
	unsigned int i, nodes = 0, keys = 0, blocks;
K
Kent Overstreet 已提交
1371
	struct btree *new_nodes[GC_MERGE_NODES];
1372
	struct keylist keylist;
K
Kent Overstreet 已提交
1373
	struct closure cl;
K
Kent Overstreet 已提交
1374
	struct bkey *k;
K
Kent Overstreet 已提交
1375

1376 1377 1378 1379 1380
	bch_keylist_init(&keylist);

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

K
Kent Overstreet 已提交
1381
	memset(new_nodes, 0, sizeof(new_nodes));
K
Kent Overstreet 已提交
1382
	closure_init_stack(&cl);
K
Kent Overstreet 已提交
1383

K
Kent Overstreet 已提交
1384
	while (nodes < GC_MERGE_NODES && !IS_ERR_OR_NULL(r[nodes].b))
K
Kent Overstreet 已提交
1385 1386 1387 1388 1389
		keys += r[nodes++].keys;

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

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

K
Kent Overstreet 已提交
1394
	for (i = 0; i < nodes; i++) {
1395
		new_nodes[i] = btree_node_alloc_replacement(r[i].b, NULL);
K
Kent Overstreet 已提交
1396 1397
		if (IS_ERR_OR_NULL(new_nodes[i]))
			goto out_nocoalesce;
K
Kent Overstreet 已提交
1398 1399
	}

1400 1401 1402 1403 1404 1405 1406 1407 1408
	/*
	 * 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 已提交
1409 1410 1411
	for (i = 0; i < nodes; i++)
		mutex_lock(&new_nodes[i]->write_lock);

K
Kent Overstreet 已提交
1412
	for (i = nodes - 1; i > 0; --i) {
1413 1414
		struct bset *n1 = btree_bset_first(new_nodes[i]);
		struct bset *n2 = btree_bset_first(new_nodes[i - 1]);
K
Kent Overstreet 已提交
1415 1416 1417 1418
		struct bkey *k, *last = NULL;

		keys = 0;

K
Kent Overstreet 已提交
1419 1420
		if (i > 1) {
			for (k = n2->start;
K
Kent Overstreet 已提交
1421
			     k < bset_bkey_last(n2);
K
Kent Overstreet 已提交
1422 1423
			     k = bkey_next(k)) {
				if (__set_blocks(n1, n1->keys + keys +
1424 1425
						 bkey_u64s(k),
						 block_bytes(b->c)) > blocks)
K
Kent Overstreet 已提交
1426 1427 1428 1429 1430 1431
					break;

				last = k;
				keys += bkey_u64s(k);
			}
		} else {
K
Kent Overstreet 已提交
1432 1433 1434 1435 1436 1437 1438 1439
			/*
			 * 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 已提交
1440
			if (__set_blocks(n1, n1->keys + n2->keys,
1441 1442
					 block_bytes(b->c)) >
			    btree_blocks(new_nodes[i]))
K
Kent Overstreet 已提交
1443
				goto out_nocoalesce;
K
Kent Overstreet 已提交
1444 1445

			keys = n2->keys;
K
Kent Overstreet 已提交
1446
			/* Take the key of the node we're getting rid of */
K
Kent Overstreet 已提交
1447
			last = &r->b->key;
K
Kent Overstreet 已提交
1448
		}
K
Kent Overstreet 已提交
1449

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

K
Kent Overstreet 已提交
1453 1454
		if (last)
			bkey_copy_key(&new_nodes[i]->key, last);
K
Kent Overstreet 已提交
1455

K
Kent Overstreet 已提交
1456
		memcpy(bset_bkey_last(n1),
K
Kent Overstreet 已提交
1457
		       n2->start,
K
Kent Overstreet 已提交
1458
		       (void *) bset_bkey_idx(n2, keys) - (void *) n2->start);
K
Kent Overstreet 已提交
1459 1460

		n1->keys += keys;
K
Kent Overstreet 已提交
1461
		r[i].keys = n1->keys;
K
Kent Overstreet 已提交
1462 1463

		memmove(n2->start,
K
Kent Overstreet 已提交
1464 1465 1466
			bset_bkey_idx(n2, keys),
			(void *) bset_bkey_last(n2) -
			(void *) bset_bkey_idx(n2, keys));
K
Kent Overstreet 已提交
1467 1468 1469

		n2->keys -= keys;

1470
		if (__bch_keylist_realloc(&keylist,
1471
					  bkey_u64s(&new_nodes[i]->key)))
K
Kent Overstreet 已提交
1472 1473 1474
			goto out_nocoalesce;

		bch_btree_node_write(new_nodes[i], &cl);
1475
		bch_keylist_add(&keylist, &new_nodes[i]->key);
K
Kent Overstreet 已提交
1476 1477
	}

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

1481 1482 1483 1484 1485 1486
	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]);
1487
	new_nodes[0] = NULL;
1488

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

1493 1494
		make_btree_freeing_key(r[i].b, keylist.top);
		bch_keylist_push(&keylist);
K
Kent Overstreet 已提交
1495
	}
K
Kent Overstreet 已提交
1496

1497 1498
	bch_btree_insert_node(b, op, &keylist, NULL, NULL);
	BUG_ON(!bch_keylist_empty(&keylist));
K
Kent Overstreet 已提交
1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510

	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 已提交
1511 1512
	gc->nodes--;

1513 1514
	bch_keylist_free(&keylist);

K
Kent Overstreet 已提交
1515 1516 1517 1518 1519 1520
	/* Invalidated our iterator */
	return -EINTR;

out_nocoalesce:
	closure_sync(&cl);

1521
	while ((k = bch_keylist_pop(&keylist)))
K
Kent Overstreet 已提交
1522 1523
		if (!bkey_cmp(k, &ZERO_KEY))
			atomic_dec(&b->c->prio_blocked);
1524
	bch_keylist_free(&keylist);
K
Kent Overstreet 已提交
1525 1526 1527 1528 1529 1530 1531

	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 已提交
1532 1533
}

1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569
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;
}

1570
static unsigned int btree_gc_count_keys(struct btree *b)
K
Kent Overstreet 已提交
1571
{
K
Kent Overstreet 已提交
1572 1573
	struct bkey *k;
	struct btree_iter iter;
1574
	unsigned int ret = 0;
K
Kent Overstreet 已提交
1575

1576
	for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad)
K
Kent Overstreet 已提交
1577 1578 1579 1580
		ret += bkey_u64s(k);

	return ret;
}
K
Kent Overstreet 已提交
1581

1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607
static size_t btree_gc_min_nodes(struct cache_set *c)
{
	size_t min_nodes;

	/*
	 * Since incremental GC would stop 100ms when front
	 * side I/O comes, so when there are many btree nodes,
	 * if GC only processes constant (100) nodes each time,
	 * GC would last a long time, and the front side I/Os
	 * would run out of the buckets (since no new bucket
	 * can be allocated during GC), and be blocked again.
	 * So GC should not process constant nodes, but varied
	 * nodes according to the number of btree nodes, which
	 * realized by dividing GC into constant(100) times,
	 * so when there are many btree nodes, GC can process
	 * more nodes each time, otherwise, GC will process less
	 * nodes each time (but no less than MIN_GC_NODES)
	 */
	min_nodes = c->gc_stats.nodes / MAX_GC_TIMES;
	if (min_nodes < MIN_GC_NODES)
		min_nodes = MIN_GC_NODES;

	return min_nodes;
}


K
Kent Overstreet 已提交
1608 1609 1610 1611 1612 1613 1614
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 已提交
1615
	struct gc_merge_info r[GC_MERGE_NODES];
K
Kent Overstreet 已提交
1616
	struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1;
K
Kent Overstreet 已提交
1617

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

K
Kent Overstreet 已提交
1620 1621
	for (i = r; i < r + ARRAY_SIZE(r); i++)
		i->b = ERR_PTR(-EINTR);
K
Kent Overstreet 已提交
1622

K
Kent Overstreet 已提交
1623
	while (1) {
K
Kent Overstreet 已提交
1624
		k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad);
K
Kent Overstreet 已提交
1625
		if (k) {
1626
			r->b = bch_btree_node_get(b->c, op, k, b->level - 1,
1627
						  true, b);
K
Kent Overstreet 已提交
1628 1629 1630 1631 1632 1633 1634
			if (IS_ERR(r->b)) {
				ret = PTR_ERR(r->b);
				break;
			}

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

1635
			ret = btree_gc_coalesce(b, op, gc, r);
K
Kent Overstreet 已提交
1636 1637
			if (ret)
				break;
K
Kent Overstreet 已提交
1638 1639
		}

K
Kent Overstreet 已提交
1640 1641
		if (!last->b)
			break;
K
Kent Overstreet 已提交
1642

K
Kent Overstreet 已提交
1643 1644
		if (!IS_ERR(last->b)) {
			should_rewrite = btree_gc_mark_node(last->b, gc);
1645 1646 1647
			if (should_rewrite) {
				ret = btree_gc_rewrite_node(b, op, last->b);
				if (ret)
K
Kent Overstreet 已提交
1648 1649 1650 1651 1652 1653 1654 1655
					break;
			}

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

K
Kent Overstreet 已提交
1657 1658 1659 1660 1661 1662
			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 已提交
1663
			mutex_lock(&last->b->write_lock);
K
Kent Overstreet 已提交
1664 1665
			if (btree_node_dirty(last->b))
				bch_btree_node_write(last->b, writes);
K
Kent Overstreet 已提交
1666
			mutex_unlock(&last->b->write_lock);
K
Kent Overstreet 已提交
1667 1668 1669 1670 1671
			rw_unlock(true, last->b);
		}

		memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1));
		r->b = NULL;
K
Kent Overstreet 已提交
1672

T
Tang Junhui 已提交
1673
		if (atomic_read(&b->c->search_inflight) &&
1674
		    gc->nodes >= gc->nodes_pre + btree_gc_min_nodes(b->c)) {
T
Tang Junhui 已提交
1675 1676 1677 1678 1679
			gc->nodes_pre =  gc->nodes;
			ret = -EAGAIN;
			break;
		}

K
Kent Overstreet 已提交
1680 1681 1682 1683 1684 1685
		if (need_resched()) {
			ret = -EAGAIN;
			break;
		}
	}

K
Kent Overstreet 已提交
1686 1687 1688 1689 1690 1691 1692
	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 已提交
1693
		}
K
Kent Overstreet 已提交
1694 1695 1696 1697 1698 1699 1700 1701

	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 已提交
1702 1703
	int ret = 0;
	bool should_rewrite;
K
Kent Overstreet 已提交
1704

K
Kent Overstreet 已提交
1705 1706
	should_rewrite = btree_gc_mark_node(b, gc);
	if (should_rewrite) {
1707
		n = btree_node_alloc_replacement(b, NULL);
K
Kent Overstreet 已提交
1708

K
Kent Overstreet 已提交
1709 1710
		if (!IS_ERR_OR_NULL(n)) {
			bch_btree_node_write_sync(n);
K
Kent Overstreet 已提交
1711

K
Kent Overstreet 已提交
1712 1713 1714
			bch_btree_set_root(n);
			btree_node_free(b);
			rw_unlock(true, n);
K
Kent Overstreet 已提交
1715

K
Kent Overstreet 已提交
1716 1717 1718
			return -EINTR;
		}
	}
K
Kent Overstreet 已提交
1719

1720 1721
	__bch_btree_mark_key(b->c, b->level + 1, &b->key);

K
Kent Overstreet 已提交
1722 1723 1724 1725
	if (b->level) {
		ret = btree_gc_recurse(b, op, writes, gc);
		if (ret)
			return ret;
K
Kent Overstreet 已提交
1726 1727
	}

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

K
Kent Overstreet 已提交
1730 1731 1732 1733 1734 1735 1736
	return ret;
}

static void btree_gc_start(struct cache_set *c)
{
	struct cache *ca;
	struct bucket *b;
1737
	unsigned int i;
K
Kent Overstreet 已提交
1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748

	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 已提交
1749
			b->last_gc = b->gen;
1750
			if (!atomic_read(&b->pin)) {
1751
				SET_GC_MARK(b, 0);
1752 1753
				SET_GC_SECTORS_USED(b, 0);
			}
K
Kent Overstreet 已提交
1754 1755 1756 1757 1758
		}

	mutex_unlock(&c->bucket_lock);
}

1759
static void bch_btree_gc_finish(struct cache_set *c)
K
Kent Overstreet 已提交
1760 1761 1762
{
	struct bucket *b;
	struct cache *ca;
1763
	unsigned int i;
K
Kent Overstreet 已提交
1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774

	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);

1775 1776
	/* don't reclaim buckets to which writeback keys point */
	rcu_read_lock();
1777
	for (i = 0; i < c->devices_max_used; i++) {
1778 1779 1780
		struct bcache_device *d = c->devices[i];
		struct cached_dev *dc;
		struct keybuf_key *w, *n;
1781
		unsigned int j;
1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796

		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();

1797
	c->avail_nbuckets = 0;
K
Kent Overstreet 已提交
1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812
	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));

1813 1814 1815 1816 1817 1818
			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)
1819
				c->avail_nbuckets++;
K
Kent Overstreet 已提交
1820 1821 1822 1823 1824 1825
		}
	}

	mutex_unlock(&c->bucket_lock);
}

K
Kent Overstreet 已提交
1826
static void bch_btree_gc(struct cache_set *c)
K
Kent Overstreet 已提交
1827 1828 1829 1830 1831 1832
{
	int ret;
	struct gc_stat stats;
	struct closure writes;
	struct btree_op op;
	uint64_t start_time = local_clock();
K
Kent Overstreet 已提交
1833

K
Kent Overstreet 已提交
1834
	trace_bcache_gc_start(c);
K
Kent Overstreet 已提交
1835 1836 1837

	memset(&stats, 0, sizeof(struct gc_stat));
	closure_init_stack(&writes);
K
Kent Overstreet 已提交
1838
	bch_btree_op_init(&op, SHRT_MAX);
K
Kent Overstreet 已提交
1839 1840 1841

	btree_gc_start(c);

1842
	/* if CACHE_SET_IO_DISABLE set, gc thread should stop too */
K
Kent Overstreet 已提交
1843 1844 1845
	do {
		ret = btree_root(gc_root, c, &op, &writes, &stats);
		closure_sync(&writes);
1846
		cond_resched();
K
Kent Overstreet 已提交
1847

T
Tang Junhui 已提交
1848 1849 1850 1851
		if (ret == -EAGAIN)
			schedule_timeout_interruptible(msecs_to_jiffies
						       (GC_SLEEP_MS));
		else if (ret)
K
Kent Overstreet 已提交
1852
			pr_warn("gc failed!");
1853
	} while (ret && !test_bit(CACHE_SET_IO_DISABLE, &c->flags));
K
Kent Overstreet 已提交
1854

1855
	bch_btree_gc_finish(c);
K
Kent Overstreet 已提交
1856 1857
	wake_up_allocators(c);

1858
	bch_time_stats_update(&c->btree_gc_time, start_time);
K
Kent Overstreet 已提交
1859 1860 1861

	stats.key_bytes *= sizeof(uint64_t);
	stats.data	<<= 9;
1862
	bch_update_bucket_in_use(c, &stats);
K
Kent Overstreet 已提交
1863 1864
	memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat));

K
Kent Overstreet 已提交
1865
	trace_bcache_gc_end(c);
K
Kent Overstreet 已提交
1866

K
Kent Overstreet 已提交
1867 1868 1869
	bch_moving_gc(c);
}

1870
static bool gc_should_run(struct cache_set *c)
K
Kent Overstreet 已提交
1871
{
K
Kent Overstreet 已提交
1872
	struct cache *ca;
1873
	unsigned int i;
K
Kent Overstreet 已提交
1874

1875 1876 1877
	for_each_cache(ca, c, i)
		if (ca->invalidate_needs_gc)
			return true;
K
Kent Overstreet 已提交
1878

1879 1880
	if (atomic_read(&c->sectors_to_gc) < 0)
		return true;
K
Kent Overstreet 已提交
1881

1882 1883
	return false;
}
K
Kent Overstreet 已提交
1884

1885 1886 1887
static int bch_gc_thread(void *arg)
{
	struct cache_set *c = arg;
K
Kent Overstreet 已提交
1888

1889 1890
	while (1) {
		wait_event_interruptible(c->gc_wait,
1891 1892 1893
			   kthread_should_stop() ||
			   test_bit(CACHE_SET_IO_DISABLE, &c->flags) ||
			   gc_should_run(c));
K
Kent Overstreet 已提交
1894

1895 1896
		if (kthread_should_stop() ||
		    test_bit(CACHE_SET_IO_DISABLE, &c->flags))
1897 1898 1899 1900
			break;

		set_gc_sectors(c);
		bch_btree_gc(c);
K
Kent Overstreet 已提交
1901 1902
	}

1903
	wait_for_kthread_stop();
K
Kent Overstreet 已提交
1904
	return 0;
K
Kent Overstreet 已提交
1905 1906
}

K
Kent Overstreet 已提交
1907
int bch_gc_thread_start(struct cache_set *c)
K
Kent Overstreet 已提交
1908
{
1909
	c->gc_thread = kthread_run(bch_gc_thread, c, "bcache_gc");
V
Vasyl Gomonovych 已提交
1910
	return PTR_ERR_OR_ZERO(c->gc_thread);
K
Kent Overstreet 已提交
1911 1912 1913 1914
}

/* Initial partial gc */

1915
static int bch_btree_check_recurse(struct btree *b, struct btree_op *op)
K
Kent Overstreet 已提交
1916
{
1917 1918
	int ret = 0;
	struct bkey *k, *p = NULL;
K
Kent Overstreet 已提交
1919 1920
	struct btree_iter iter;

1921 1922
	for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid)
		bch_initial_mark_key(b->c, b->level, k);
K
Kent Overstreet 已提交
1923

1924
	bch_initial_mark_key(b->c, b->level + 1, &b->key);
K
Kent Overstreet 已提交
1925 1926

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

1929
		do {
K
Kent Overstreet 已提交
1930 1931
			k = bch_btree_iter_next_filter(&iter, &b->keys,
						       bch_ptr_bad);
1932
			if (k) {
1933
				btree_node_prefetch(b, k);
1934 1935 1936 1937 1938 1939
				/*
				 * initiallize c->gc_stats.nodes
				 * for incremental GC
				 */
				b->c->gc_stats.nodes++;
			}
K
Kent Overstreet 已提交
1940

1941
			if (p)
1942
				ret = btree(check_recurse, p, b, op);
K
Kent Overstreet 已提交
1943

1944 1945
			p = k;
		} while (p && !ret);
K
Kent Overstreet 已提交
1946 1947
	}

1948
	return ret;
K
Kent Overstreet 已提交
1949 1950
}

K
Kent Overstreet 已提交
1951
int bch_btree_check(struct cache_set *c)
K
Kent Overstreet 已提交
1952
{
K
Kent Overstreet 已提交
1953
	struct btree_op op;
K
Kent Overstreet 已提交
1954

K
Kent Overstreet 已提交
1955
	bch_btree_op_init(&op, SHRT_MAX);
K
Kent Overstreet 已提交
1956

1957
	return btree_root(check_recurse, c, &op);
K
Kent Overstreet 已提交
1958 1959
}

K
Kent Overstreet 已提交
1960 1961 1962 1963
void bch_initial_gc_finish(struct cache_set *c)
{
	struct cache *ca;
	struct bucket *b;
1964
	unsigned int i;
K
Kent Overstreet 已提交
1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980

	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) {
1981 1982
			if (fifo_full(&ca->free[RESERVE_PRIO]) &&
			    fifo_full(&ca->free[RESERVE_BTREE]))
K
Kent Overstreet 已提交
1983 1984 1985 1986 1987
				break;

			if (bch_can_invalidate_bucket(ca, b) &&
			    !GC_MARK(b)) {
				__bch_invalidate_one_bucket(ca, b);
1988 1989 1990 1991
				if (!fifo_push(&ca->free[RESERVE_PRIO],
				   b - ca->buckets))
					fifo_push(&ca->free[RESERVE_BTREE],
						  b - ca->buckets);
K
Kent Overstreet 已提交
1992 1993 1994 1995 1996 1997 1998
			}
		}
	}

	mutex_unlock(&c->bucket_lock);
}

K
Kent Overstreet 已提交
1999 2000
/* Btree insertion */

2001 2002
static bool btree_insert_key(struct btree *b, struct bkey *k,
			     struct bkey *replace_key)
K
Kent Overstreet 已提交
2003
{
2004
	unsigned int status;
K
Kent Overstreet 已提交
2005 2006

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

2008 2009 2010 2011
	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 已提交
2012

2013 2014 2015 2016 2017
		trace_bcache_btree_insert_key(b, k, replace_key != NULL,
					      status);
		return true;
	} else
		return false;
K
Kent Overstreet 已提交
2018 2019
}

2020 2021
static size_t insert_u64s_remaining(struct btree *b)
{
2022
	long ret = bch_btree_keys_u64s_remaining(&b->keys);
2023 2024 2025 2026 2027 2028 2029 2030 2031 2032

	/*
	 * 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 已提交
2033
static bool bch_btree_insert_keys(struct btree *b, struct btree_op *op,
K
Kent Overstreet 已提交
2034 2035
				  struct keylist *insert_keys,
				  struct bkey *replace_key)
K
Kent Overstreet 已提交
2036 2037
{
	bool ret = false;
2038
	int oldsize = bch_count_data(&b->keys);
K
Kent Overstreet 已提交
2039

K
Kent Overstreet 已提交
2040
	while (!bch_keylist_empty(insert_keys)) {
K
Kent Overstreet 已提交
2041
		struct bkey *k = insert_keys->keys;
K
Kent Overstreet 已提交
2042

2043
		if (bkey_u64s(k) > insert_u64s_remaining(b))
2044 2045 2046
			break;

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

2050
			ret |= btree_insert_key(b, k, replace_key);
K
Kent Overstreet 已提交
2051 2052 2053
			bch_keylist_pop_front(insert_keys);
		} else if (bkey_cmp(&START_KEY(k), &b->key) < 0) {
			BKEY_PADDED(key) temp;
K
Kent Overstreet 已提交
2054
			bkey_copy(&temp.key, insert_keys->keys);
K
Kent Overstreet 已提交
2055 2056

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

2059
			ret |= btree_insert_key(b, &temp.key, replace_key);
K
Kent Overstreet 已提交
2060 2061 2062 2063
			break;
		} else {
			break;
		}
K
Kent Overstreet 已提交
2064 2065
	}

2066 2067 2068
	if (!ret)
		op->insert_collision = true;

2069 2070
	BUG_ON(!bch_keylist_empty(insert_keys) && b->level);

2071
	BUG_ON(bch_count_data(&b->keys) < oldsize);
K
Kent Overstreet 已提交
2072 2073 2074
	return ret;
}

K
Kent Overstreet 已提交
2075 2076
static int btree_split(struct btree *b, struct btree_op *op,
		       struct keylist *insert_keys,
K
Kent Overstreet 已提交
2077
		       struct bkey *replace_key)
K
Kent Overstreet 已提交
2078
{
2079
	bool split;
K
Kent Overstreet 已提交
2080 2081
	struct btree *n1, *n2 = NULL, *n3 = NULL;
	uint64_t start_time = local_clock();
K
Kent Overstreet 已提交
2082
	struct closure cl;
2083
	struct keylist parent_keys;
K
Kent Overstreet 已提交
2084 2085

	closure_init_stack(&cl);
2086
	bch_keylist_init(&parent_keys);
K
Kent Overstreet 已提交
2087

2088 2089 2090 2091 2092 2093
	if (btree_check_reserve(b, op)) {
		if (!b->level)
			return -EINTR;
		else
			WARN(1, "insufficient reserve for split\n");
	}
2094

2095
	n1 = btree_node_alloc_replacement(b, op);
K
Kent Overstreet 已提交
2096 2097 2098
	if (IS_ERR(n1))
		goto err;

2099 2100
	split = set_blocks(btree_bset_first(n1),
			   block_bytes(n1->c)) > (btree_blocks(b) * 4) / 5;
K
Kent Overstreet 已提交
2101 2102

	if (split) {
2103
		unsigned int keys = 0;
K
Kent Overstreet 已提交
2104

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

2107
		n2 = bch_btree_node_alloc(b->c, op, b->level, b->parent);
K
Kent Overstreet 已提交
2108 2109 2110
		if (IS_ERR(n2))
			goto err_free1;

2111
		if (!b->parent) {
2112
			n3 = bch_btree_node_alloc(b->c, op, b->level + 1, NULL);
K
Kent Overstreet 已提交
2113 2114 2115 2116
			if (IS_ERR(n3))
				goto err_free2;
		}

K
Kent Overstreet 已提交
2117 2118 2119
		mutex_lock(&n1->write_lock);
		mutex_lock(&n2->write_lock);

K
Kent Overstreet 已提交
2120
		bch_btree_insert_keys(n1, op, insert_keys, replace_key);
K
Kent Overstreet 已提交
2121

2122 2123
		/*
		 * Has to be a linear search because we don't have an auxiliary
K
Kent Overstreet 已提交
2124 2125 2126
		 * search tree yet
		 */

2127 2128
		while (keys < (btree_bset_first(n1)->keys * 3) / 5)
			keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1),
K
Kent Overstreet 已提交
2129
							keys));
K
Kent Overstreet 已提交
2130

K
Kent Overstreet 已提交
2131
		bkey_copy_key(&n1->key,
2132 2133
			      bset_bkey_idx(btree_bset_first(n1), keys));
		keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), keys));
K
Kent Overstreet 已提交
2134

2135 2136
		btree_bset_first(n2)->keys = btree_bset_first(n1)->keys - keys;
		btree_bset_first(n1)->keys = keys;
K
Kent Overstreet 已提交
2137

2138 2139 2140
		memcpy(btree_bset_first(n2)->start,
		       bset_bkey_last(btree_bset_first(n1)),
		       btree_bset_first(n2)->keys * sizeof(uint64_t));
K
Kent Overstreet 已提交
2141 2142 2143

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

2144
		bch_keylist_add(&parent_keys, &n2->key);
K
Kent Overstreet 已提交
2145
		bch_btree_node_write(n2, &cl);
K
Kent Overstreet 已提交
2146
		mutex_unlock(&n2->write_lock);
K
Kent Overstreet 已提交
2147
		rw_unlock(true, n2);
K
Kent Overstreet 已提交
2148
	} else {
2149
		trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys);
K
Kent Overstreet 已提交
2150

K
Kent Overstreet 已提交
2151
		mutex_lock(&n1->write_lock);
K
Kent Overstreet 已提交
2152
		bch_btree_insert_keys(n1, op, insert_keys, replace_key);
K
Kent Overstreet 已提交
2153
	}
K
Kent Overstreet 已提交
2154

2155
	bch_keylist_add(&parent_keys, &n1->key);
K
Kent Overstreet 已提交
2156
	bch_btree_node_write(n1, &cl);
K
Kent Overstreet 已提交
2157
	mutex_unlock(&n1->write_lock);
K
Kent Overstreet 已提交
2158 2159

	if (n3) {
2160
		/* Depth increases, make a new root */
K
Kent Overstreet 已提交
2161
		mutex_lock(&n3->write_lock);
K
Kent Overstreet 已提交
2162
		bkey_copy_key(&n3->key, &MAX_KEY);
2163
		bch_btree_insert_keys(n3, op, &parent_keys, NULL);
K
Kent Overstreet 已提交
2164
		bch_btree_node_write(n3, &cl);
K
Kent Overstreet 已提交
2165
		mutex_unlock(&n3->write_lock);
K
Kent Overstreet 已提交
2166

K
Kent Overstreet 已提交
2167
		closure_sync(&cl);
K
Kent Overstreet 已提交
2168 2169
		bch_btree_set_root(n3);
		rw_unlock(true, n3);
2170 2171
	} else if (!b->parent) {
		/* Root filled up but didn't need to be split */
K
Kent Overstreet 已提交
2172
		closure_sync(&cl);
K
Kent Overstreet 已提交
2173 2174
		bch_btree_set_root(n1);
	} else {
2175
		/* Split a non root node */
K
Kent Overstreet 已提交
2176
		closure_sync(&cl);
2177 2178 2179 2180 2181
		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 已提交
2182 2183
	}

2184
	btree_node_free(b);
K
Kent Overstreet 已提交
2185 2186
	rw_unlock(true, n1);

2187
	bch_time_stats_update(&b->c->btree_split_time, start_time);
K
Kent Overstreet 已提交
2188 2189 2190

	return 0;
err_free2:
2191
	bkey_put(b->c, &n2->key);
2192
	btree_node_free(n2);
K
Kent Overstreet 已提交
2193 2194
	rw_unlock(true, n2);
err_free1:
2195
	bkey_put(b->c, &n1->key);
2196
	btree_node_free(n1);
K
Kent Overstreet 已提交
2197 2198
	rw_unlock(true, n1);
err:
2199
	WARN(1, "bcache: btree split failed (level %u)", b->level);
2200

K
Kent Overstreet 已提交
2201 2202 2203 2204 2205 2206 2207 2208
	if (n3 == ERR_PTR(-EAGAIN) ||
	    n2 == ERR_PTR(-EAGAIN) ||
	    n1 == ERR_PTR(-EAGAIN))
		return -EAGAIN;

	return -ENOMEM;
}

K
Kent Overstreet 已提交
2209
static int bch_btree_insert_node(struct btree *b, struct btree_op *op,
K
Kent Overstreet 已提交
2210
				 struct keylist *insert_keys,
K
Kent Overstreet 已提交
2211 2212
				 atomic_t *journal_ref,
				 struct bkey *replace_key)
K
Kent Overstreet 已提交
2213
{
K
Kent Overstreet 已提交
2214 2215
	struct closure cl;

2216 2217
	BUG_ON(b->level && replace_key);

K
Kent Overstreet 已提交
2218 2219 2220 2221 2222 2223 2224 2225
	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 */

2226
	if (bch_keylist_nkeys(insert_keys) > insert_u64s_remaining(b)) {
K
Kent Overstreet 已提交
2227 2228 2229
		mutex_unlock(&b->write_lock);
		goto split;
	}
2230

K
Kent Overstreet 已提交
2231
	BUG_ON(write_block(b) != btree_bset_last(b));
K
Kent Overstreet 已提交
2232

K
Kent Overstreet 已提交
2233 2234 2235 2236 2237 2238
	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);
	}
2239

K
Kent Overstreet 已提交
2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261
	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;
2262
	}
K
Kent Overstreet 已提交
2263
}
K
Kent Overstreet 已提交
2264

2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280
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 ||
2281
		    b->seq != seq + 1) {
B
Bart Van Assche 已提交
2282
			op->lock = b->level;
2283
			goto out;
2284
		}
2285 2286 2287 2288 2289 2290 2291 2292 2293
	}

	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 已提交
2294
	ret = bch_btree_insert_node(b, op, &insert, NULL, NULL);
2295 2296 2297 2298 2299 2300 2301 2302

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

2303 2304 2305 2306 2307 2308
struct btree_insert_op {
	struct btree_op	op;
	struct keylist	*keys;
	atomic_t	*journal_ref;
	struct bkey	*replace_key;
};
K
Kent Overstreet 已提交
2309

2310
static int btree_insert_fn(struct btree_op *b_op, struct btree *b)
2311 2312 2313
{
	struct btree_insert_op *op = container_of(b_op,
					struct btree_insert_op, op);
K
Kent Overstreet 已提交
2314

2315 2316 2317 2318 2319 2320
	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 已提交
2321 2322
}

2323 2324
int bch_btree_insert(struct cache_set *c, struct keylist *keys,
		     atomic_t *journal_ref, struct bkey *replace_key)
K
Kent Overstreet 已提交
2325
{
2326
	struct btree_insert_op op;
K
Kent Overstreet 已提交
2327 2328
	int ret = 0;

2329
	BUG_ON(current->bio_list);
2330
	BUG_ON(bch_keylist_empty(keys));
K
Kent Overstreet 已提交
2331

2332 2333 2334 2335
	bch_btree_op_init(&op.op, 0);
	op.keys		= keys;
	op.journal_ref	= journal_ref;
	op.replace_key	= replace_key;
K
Kent Overstreet 已提交
2336

2337 2338 2339 2340 2341 2342
	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 已提交
2343

2344 2345
	if (ret) {
		struct bkey *k;
K
Kent Overstreet 已提交
2346

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

2349
		while ((k = bch_keylist_pop(keys)))
2350
			bkey_put(c, k);
2351 2352
	} else if (op.op.insert_collision)
		ret = -ESRCH;
2353

K
Kent Overstreet 已提交
2354 2355 2356 2357 2358
	return ret;
}

void bch_btree_set_root(struct btree *b)
{
2359
	unsigned int i;
K
Kent Overstreet 已提交
2360 2361 2362
	struct closure cl;

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

K
Kent Overstreet 已提交
2364 2365
	trace_bcache_btree_set_root(b);

K
Kent Overstreet 已提交
2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376
	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 已提交
2377 2378
	bch_journal_meta(b->c, &cl);
	closure_sync(&cl);
K
Kent Overstreet 已提交
2379 2380
}

2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392
/* 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;

2393
		bch_btree_iter_init(&b->keys, &iter, from);
2394

K
Kent Overstreet 已提交
2395
		while ((k = bch_btree_iter_next_filter(&iter, &b->keys,
2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414
						       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 已提交
2415
	return btree_root(map_nodes_recurse, c, op, from, fn, flags);
2416 2417 2418 2419 2420 2421 2422 2423 2424 2425
}

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;

2426
	bch_btree_iter_init(&b->keys, &iter, from);
2427

K
Kent Overstreet 已提交
2428
	while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) {
2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447
		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 已提交
2448
	return btree_root(map_keys_recurse, c, op, from, fn, flags);
2449 2450
}

K
Kent Overstreet 已提交
2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468
/* 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);
}

2469 2470
struct refill {
	struct btree_op	op;
2471
	unsigned int	nr_found;
2472 2473 2474 2475
	struct keybuf	*buf;
	struct bkey	*end;
	keybuf_pred_fn	*pred;
};
K
Kent Overstreet 已提交
2476

2477 2478 2479 2480 2481 2482
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 已提交
2483

2484
	if (bkey_cmp(k, refill->end) > 0) {
2485 2486 2487
		ret = MAP_DONE;
		goto out;
	}
K
Kent Overstreet 已提交
2488

2489 2490
	if (!KEY_SIZE(k)) /* end key */
		goto out;
K
Kent Overstreet 已提交
2491

2492 2493
	if (refill->pred(buf, k)) {
		struct keybuf_key *w;
K
Kent Overstreet 已提交
2494

2495
		spin_lock(&buf->lock);
K
Kent Overstreet 已提交
2496

2497 2498 2499 2500 2501
		w = array_alloc(&buf->freelist);
		if (!w) {
			spin_unlock(&buf->lock);
			return MAP_DONE;
		}
K
Kent Overstreet 已提交
2502

2503 2504
		w->private = NULL;
		bkey_copy(&w->key, k);
K
Kent Overstreet 已提交
2505

2506 2507
		if (RB_INSERT(&buf->keys, w, node, keybuf_cmp))
			array_free(&buf->freelist, w);
2508 2509
		else
			refill->nr_found++;
K
Kent Overstreet 已提交
2510

2511 2512
		if (array_freelist_empty(&buf->freelist))
			ret = MAP_DONE;
K
Kent Overstreet 已提交
2513

2514
		spin_unlock(&buf->lock);
K
Kent Overstreet 已提交
2515
	}
2516 2517 2518
out:
	buf->last_scanned = *k;
	return ret;
K
Kent Overstreet 已提交
2519 2520 2521
}

void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf,
K
Kent Overstreet 已提交
2522
		       struct bkey *end, keybuf_pred_fn *pred)
K
Kent Overstreet 已提交
2523 2524
{
	struct bkey start = buf->last_scanned;
2525
	struct refill refill;
K
Kent Overstreet 已提交
2526 2527 2528

	cond_resched();

K
Kent Overstreet 已提交
2529
	bch_btree_op_init(&refill.op, -1);
2530 2531 2532 2533
	refill.nr_found	= 0;
	refill.buf	= buf;
	refill.end	= end;
	refill.pred	= pred;
2534 2535 2536

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

2538 2539 2540 2541
	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 已提交
2542 2543 2544 2545 2546

	spin_lock(&buf->lock);

	if (!RB_EMPTY_ROOT(&buf->keys)) {
		struct keybuf_key *w;
2547

K
Kent Overstreet 已提交
2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578
		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;
2579

K
Kent Overstreet 已提交
2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605
	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;
2606

K
Kent Overstreet 已提交
2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621
	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,
2622 2623 2624
					  struct keybuf *buf,
					  struct bkey *end,
					  keybuf_pred_fn *pred)
K
Kent Overstreet 已提交
2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637
{
	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 已提交
2638
		bch_refill_keybuf(c, buf, end, pred);
K
Kent Overstreet 已提交
2639 2640 2641 2642 2643
	}

	return ret;
}

K
Kent Overstreet 已提交
2644
void bch_keybuf_init(struct keybuf *buf)
K
Kent Overstreet 已提交
2645 2646 2647 2648 2649 2650 2651
{
	buf->last_scanned	= MAX_KEY;
	buf->keys		= RB_ROOT;

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