blob: 463d2800a955e65844e9f76d974aefb3f037b671 [file] [log] [blame]
Kent Overstreetcafe5632013-03-23 16:11:31 -07001/*
2 * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>
3 *
4 * Uses a block device as cache for other block devices; optimized for SSDs.
5 * All allocation is done in buckets, which should match the erase block size
6 * of the device.
7 *
8 * Buckets containing cached data are kept on a heap sorted by priority;
9 * bucket priority is increased on cache hit, and periodically all the buckets
10 * on the heap have their priority scaled down. This currently is just used as
11 * an LRU but in the future should allow for more intelligent heuristics.
12 *
13 * Buckets have an 8 bit counter; freeing is accomplished by incrementing the
14 * counter. Garbage collection is used to remove stale pointers.
15 *
16 * Indexing is done via a btree; nodes are not necessarily fully sorted, rather
17 * as keys are inserted we only sort the pages that have not yet been written.
18 * When garbage collection is run, we resort the entire node.
19 *
20 * All configuration is done via sysfs; see Documentation/bcache.txt.
21 */
22
23#include "bcache.h"
24#include "btree.h"
25#include "debug.h"
Kent Overstreet65d45232013-12-20 17:22:05 -080026#include "extents.h"
Kent Overstreetcafe5632013-03-23 16:11:31 -070027
28#include <linux/slab.h>
29#include <linux/bitops.h>
Kent Overstreet72a44512013-10-24 17:19:26 -070030#include <linux/freezer.h>
Kent Overstreetcafe5632013-03-23 16:11:31 -070031#include <linux/hash.h>
Kent Overstreet72a44512013-10-24 17:19:26 -070032#include <linux/kthread.h>
Geert Uytterhoevencd953ed2013-03-27 18:56:28 +010033#include <linux/prefetch.h>
Kent Overstreetcafe5632013-03-23 16:11:31 -070034#include <linux/random.h>
35#include <linux/rcupdate.h>
36#include <trace/events/bcache.h>
37
38/*
39 * Todo:
40 * register_bcache: Return errors out to userspace correctly
41 *
42 * Writeback: don't undirty key until after a cache flush
43 *
44 * Create an iterator for key pointers
45 *
46 * On btree write error, mark bucket such that it won't be freed from the cache
47 *
48 * Journalling:
49 * Check for bad keys in replay
50 * Propagate barriers
51 * Refcount journal entries in journal_replay
52 *
53 * Garbage collection:
54 * Finish incremental gc
55 * Gc should free old UUIDs, data for invalid UUIDs
56 *
57 * Provide a way to list backing device UUIDs we have data cached for, and
58 * probably how long it's been since we've seen them, and a way to invalidate
59 * dirty data for devices that will never be attached again
60 *
61 * Keep 1 min/5 min/15 min statistics of how busy a block device has been, so
62 * that based on that and how much dirty data we have we can keep writeback
63 * from being starved
64 *
65 * Add a tracepoint or somesuch to watch for writeback starvation
66 *
67 * When btree depth > 1 and splitting an interior node, we have to make sure
68 * alloc_bucket() cannot fail. This should be true but is not completely
69 * obvious.
70 *
71 * Make sure all allocations get charged to the root cgroup
72 *
73 * Plugging?
74 *
75 * If data write is less than hard sector size of ssd, round up offset in open
76 * bucket to the next whole sector
77 *
78 * Also lookup by cgroup in get_open_bucket()
79 *
80 * Superblock needs to be fleshed out for multiple cache devices
81 *
82 * Add a sysfs tunable for the number of writeback IOs in flight
83 *
84 * Add a sysfs tunable for the number of open data buckets
85 *
86 * IO tracking: Can we track when one process is doing io on behalf of another?
87 * IO tracking: Don't use just an average, weigh more recent stuff higher
88 *
89 * Test module load/unload
90 */
91
Kent Overstreetcafe5632013-03-23 16:11:31 -070092#define MAX_NEED_GC 64
93#define MAX_SAVE_PRIO 72
94
95#define PTR_DIRTY_BIT (((uint64_t) 1 << 36))
96
97#define PTR_HASH(c, k) \
98 (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0))
99
Kent Overstreetcafe5632013-03-23 16:11:31 -0700100static struct workqueue_struct *btree_io_wq;
101
Kent Overstreetdf8e8972013-07-24 17:37:59 -0700102#define insert_lock(s, b) ((b)->level <= (s)->lock)
103
104/*
105 * These macros are for recursing down the btree - they handle the details of
106 * locking and looking up nodes in the cache for you. They're best treated as
107 * mere syntax when reading code that uses them.
108 *
109 * op->lock determines whether we take a read or a write lock at a given depth.
110 * If you've got a read lock and find that you need a write lock (i.e. you're
111 * going to have to split), set op->lock and return -EINTR; btree_root() will
112 * call you again and you'll have the correct lock.
113 */
114
115/**
116 * btree - recurse down the btree on a specified key
117 * @fn: function to call, which will be passed the child node
118 * @key: key to recurse on
119 * @b: parent btree node
120 * @op: pointer to struct btree_op
121 */
122#define btree(fn, key, b, op, ...) \
123({ \
124 int _r, l = (b)->level - 1; \
125 bool _w = l <= (op)->lock; \
126 struct btree *_child = bch_btree_node_get((b)->c, key, l, _w); \
127 if (!IS_ERR(_child)) { \
128 _child->parent = (b); \
129 _r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__); \
130 rw_unlock(_w, _child); \
131 } else \
132 _r = PTR_ERR(_child); \
133 _r; \
134})
135
136/**
137 * btree_root - call a function on the root of the btree
138 * @fn: function to call, which will be passed the child node
139 * @c: cache set
140 * @op: pointer to struct btree_op
141 */
142#define btree_root(fn, c, op, ...) \
143({ \
144 int _r = -EINTR; \
145 do { \
146 struct btree *_b = (c)->root; \
147 bool _w = insert_lock(op, _b); \
148 rw_lock(_w, _b, _b->level); \
149 if (_b == (c)->root && \
150 _w == insert_lock(op, _b)) { \
151 _b->parent = NULL; \
152 _r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__); \
153 } \
154 rw_unlock(_w, _b); \
Kent Overstreet78365412013-12-17 01:29:34 -0800155 if (_r == -EINTR) \
156 schedule(); \
Kent Overstreetdf8e8972013-07-24 17:37:59 -0700157 bch_cannibalize_unlock(c); \
158 if (_r == -ENOSPC) { \
159 wait_event((c)->try_wait, \
160 !(c)->try_harder); \
161 _r = -EINTR; \
162 } \
163 } while (_r == -EINTR); \
164 \
Kent Overstreet78365412013-12-17 01:29:34 -0800165 finish_wait(&(c)->bucket_wait, &(op)->wait); \
Kent Overstreetdf8e8972013-07-24 17:37:59 -0700166 _r; \
167})
168
Kent Overstreeta85e9682013-12-20 17:28:16 -0800169static inline struct bset *write_block(struct btree *b)
170{
171 return ((void *) btree_bset_first(b)) + b->written * block_bytes(b->c);
172}
173
Kent Overstreetcafe5632013-03-23 16:11:31 -0700174/* Btree key manipulation */
175
Kent Overstreet3a3b6a42013-07-24 16:46:42 -0700176void bkey_put(struct cache_set *c, struct bkey *k)
Kent Overstreete7c590e2013-09-10 18:39:16 -0700177{
178 unsigned i;
179
180 for (i = 0; i < KEY_PTRS(k); i++)
181 if (ptr_available(c, k, i))
182 atomic_dec_bug(&PTR_BUCKET(c, k, i)->pin);
183}
184
Kent Overstreetcafe5632013-03-23 16:11:31 -0700185/* Btree IO */
186
187static uint64_t btree_csum_set(struct btree *b, struct bset *i)
188{
189 uint64_t crc = b->key.ptr[0];
Kent Overstreetfafff812013-12-17 21:56:21 -0800190 void *data = (void *) i + 8, *end = bset_bkey_last(i);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700191
Kent Overstreet169ef1c2013-03-28 12:50:55 -0600192 crc = bch_crc64_update(crc, data, end - data);
Kent Overstreetc19ed232013-03-26 13:49:02 -0700193 return crc ^ 0xffffffffffffffffULL;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700194}
195
Kent Overstreet78b77bf2013-12-17 22:49:08 -0800196void bch_btree_node_read_done(struct btree *b)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700197{
Kent Overstreetcafe5632013-03-23 16:11:31 -0700198 const char *err = "bad btree header";
Kent Overstreetee811282013-12-17 23:49:49 -0800199 struct bset *i = btree_bset_first(b);
Kent Overstreet57943512013-04-25 13:58:35 -0700200 struct btree_iter *iter;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700201
Kent Overstreet57943512013-04-25 13:58:35 -0700202 iter = mempool_alloc(b->c->fill_iter, GFP_NOWAIT);
203 iter->size = b->c->sb.bucket_size / b->c->sb.block_size;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700204 iter->used = 0;
205
Kent Overstreet280481d2013-10-24 16:36:03 -0700206#ifdef CONFIG_BCACHE_DEBUG
Kent Overstreetc052dd92013-11-11 17:35:24 -0800207 iter->b = &b->keys;
Kent Overstreet280481d2013-10-24 16:36:03 -0700208#endif
209
Kent Overstreet57943512013-04-25 13:58:35 -0700210 if (!i->seq)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700211 goto err;
212
213 for (;
Kent Overstreeta85e9682013-12-20 17:28:16 -0800214 b->written < btree_blocks(b) && i->seq == b->keys.set[0].data->seq;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700215 i = write_block(b)) {
216 err = "unsupported bset version";
217 if (i->version > BCACHE_BSET_VERSION)
218 goto err;
219
220 err = "bad btree header";
Kent Overstreetee811282013-12-17 23:49:49 -0800221 if (b->written + set_blocks(i, block_bytes(b->c)) >
222 btree_blocks(b))
Kent Overstreetcafe5632013-03-23 16:11:31 -0700223 goto err;
224
225 err = "bad magic";
Kent Overstreet81ab4192013-10-31 15:46:42 -0700226 if (i->magic != bset_magic(&b->c->sb))
Kent Overstreetcafe5632013-03-23 16:11:31 -0700227 goto err;
228
229 err = "bad checksum";
230 switch (i->version) {
231 case 0:
232 if (i->csum != csum_set(i))
233 goto err;
234 break;
235 case BCACHE_BSET_VERSION:
236 if (i->csum != btree_csum_set(b, i))
237 goto err;
238 break;
239 }
240
241 err = "empty set";
Kent Overstreeta85e9682013-12-20 17:28:16 -0800242 if (i != b->keys.set[0].data && !i->keys)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700243 goto err;
244
Kent Overstreetfafff812013-12-17 21:56:21 -0800245 bch_btree_iter_push(iter, i->start, bset_bkey_last(i));
Kent Overstreetcafe5632013-03-23 16:11:31 -0700246
Kent Overstreetee811282013-12-17 23:49:49 -0800247 b->written += set_blocks(i, block_bytes(b->c));
Kent Overstreetcafe5632013-03-23 16:11:31 -0700248 }
249
250 err = "corrupted btree";
251 for (i = write_block(b);
Kent Overstreeta85e9682013-12-20 17:28:16 -0800252 bset_sector_offset(&b->keys, i) < KEY_SIZE(&b->key);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700253 i = ((void *) i) + block_bytes(b->c))
Kent Overstreeta85e9682013-12-20 17:28:16 -0800254 if (i->seq == b->keys.set[0].data->seq)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700255 goto err;
256
Kent Overstreeta85e9682013-12-20 17:28:16 -0800257 bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700258
Kent Overstreeta85e9682013-12-20 17:28:16 -0800259 i = b->keys.set[0].data;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700260 err = "short btree key";
Kent Overstreeta85e9682013-12-20 17:28:16 -0800261 if (b->keys.set[0].size &&
262 bkey_cmp(&b->key, &b->keys.set[0].end) < 0)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700263 goto err;
264
265 if (b->written < btree_blocks(b))
Kent Overstreeta85e9682013-12-20 17:28:16 -0800266 bch_bset_init_next(&b->keys, write_block(b),
267 bset_magic(&b->c->sb));
Kent Overstreetcafe5632013-03-23 16:11:31 -0700268out:
Kent Overstreet57943512013-04-25 13:58:35 -0700269 mempool_free(iter, b->c->fill_iter);
270 return;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700271err:
272 set_btree_node_io_error(b);
Kent Overstreet88b9f8c2013-12-17 21:46:35 -0800273 bch_cache_set_error(b->c, "%s at bucket %zu, block %u, %u keys",
Kent Overstreetcafe5632013-03-23 16:11:31 -0700274 err, PTR_BUCKET_NR(b->c, &b->key, 0),
Kent Overstreet88b9f8c2013-12-17 21:46:35 -0800275 bset_block_offset(b, i), i->keys);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700276 goto out;
277}
278
Kent Overstreet57943512013-04-25 13:58:35 -0700279static void btree_node_read_endio(struct bio *bio, int error)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700280{
Kent Overstreet57943512013-04-25 13:58:35 -0700281 struct closure *cl = bio->bi_private;
282 closure_put(cl);
283}
Kent Overstreetcafe5632013-03-23 16:11:31 -0700284
Kent Overstreet78b77bf2013-12-17 22:49:08 -0800285static void bch_btree_node_read(struct btree *b)
Kent Overstreet57943512013-04-25 13:58:35 -0700286{
287 uint64_t start_time = local_clock();
288 struct closure cl;
289 struct bio *bio;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700290
Kent Overstreetc37511b2013-04-26 15:39:55 -0700291 trace_bcache_btree_read(b);
292
Kent Overstreet57943512013-04-25 13:58:35 -0700293 closure_init_stack(&cl);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700294
Kent Overstreet57943512013-04-25 13:58:35 -0700295 bio = bch_bbio_alloc(b->c);
296 bio->bi_rw = REQ_META|READ_SYNC;
Kent Overstreet4f024f32013-10-11 15:44:27 -0700297 bio->bi_iter.bi_size = KEY_SIZE(&b->key) << 9;
Kent Overstreet57943512013-04-25 13:58:35 -0700298 bio->bi_end_io = btree_node_read_endio;
299 bio->bi_private = &cl;
300
Kent Overstreeta85e9682013-12-20 17:28:16 -0800301 bch_bio_map(bio, b->keys.set[0].data);
Kent Overstreet57943512013-04-25 13:58:35 -0700302
Kent Overstreet57943512013-04-25 13:58:35 -0700303 bch_submit_bbio(bio, b->c, &b->key, 0);
304 closure_sync(&cl);
305
306 if (!test_bit(BIO_UPTODATE, &bio->bi_flags))
307 set_btree_node_io_error(b);
308
309 bch_bbio_free(bio, b->c);
310
311 if (btree_node_io_error(b))
312 goto err;
313
314 bch_btree_node_read_done(b);
Kent Overstreet57943512013-04-25 13:58:35 -0700315 bch_time_stats_update(&b->c->btree_read_time, start_time);
Kent Overstreet57943512013-04-25 13:58:35 -0700316
317 return;
318err:
Geert Uytterhoeven61cbd252013-09-23 23:17:30 -0700319 bch_cache_set_error(b->c, "io error reading bucket %zu",
Kent Overstreet57943512013-04-25 13:58:35 -0700320 PTR_BUCKET_NR(b->c, &b->key, 0));
Kent Overstreetcafe5632013-03-23 16:11:31 -0700321}
322
323static void btree_complete_write(struct btree *b, struct btree_write *w)
324{
325 if (w->prio_blocked &&
326 !atomic_sub_return(w->prio_blocked, &b->c->prio_blocked))
Kent Overstreet119ba0f2013-04-24 19:01:12 -0700327 wake_up_allocators(b->c);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700328
329 if (w->journal) {
330 atomic_dec_bug(w->journal);
331 __closure_wake_up(&b->c->journal.wait);
332 }
333
Kent Overstreetcafe5632013-03-23 16:11:31 -0700334 w->prio_blocked = 0;
335 w->journal = NULL;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700336}
337
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800338static void btree_node_write_unlock(struct closure *cl)
339{
340 struct btree *b = container_of(cl, struct btree, io);
341
342 up(&b->io_mutex);
343}
344
Kent Overstreet57943512013-04-25 13:58:35 -0700345static void __btree_node_write_done(struct closure *cl)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700346{
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800347 struct btree *b = container_of(cl, struct btree, io);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700348 struct btree_write *w = btree_prev_write(b);
349
350 bch_bbio_free(b->bio, b->c);
351 b->bio = NULL;
352 btree_complete_write(b, w);
353
354 if (btree_node_dirty(b))
355 queue_delayed_work(btree_io_wq, &b->work,
356 msecs_to_jiffies(30000));
357
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800358 closure_return_with_destructor(cl, btree_node_write_unlock);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700359}
360
Kent Overstreet57943512013-04-25 13:58:35 -0700361static void btree_node_write_done(struct closure *cl)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700362{
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800363 struct btree *b = container_of(cl, struct btree, io);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700364 struct bio_vec *bv;
365 int n;
366
Kent Overstreet79886132013-11-23 17:19:00 -0800367 bio_for_each_segment_all(bv, b->bio, n)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700368 __free_page(bv->bv_page);
369
Kent Overstreet57943512013-04-25 13:58:35 -0700370 __btree_node_write_done(cl);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700371}
372
Kent Overstreet57943512013-04-25 13:58:35 -0700373static void btree_node_write_endio(struct bio *bio, int error)
374{
375 struct closure *cl = bio->bi_private;
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800376 struct btree *b = container_of(cl, struct btree, io);
Kent Overstreet57943512013-04-25 13:58:35 -0700377
378 if (error)
379 set_btree_node_io_error(b);
380
381 bch_bbio_count_io_errors(b->c, bio, error, "writing btree");
382 closure_put(cl);
383}
384
385static void do_btree_node_write(struct btree *b)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700386{
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800387 struct closure *cl = &b->io;
Kent Overstreetee811282013-12-17 23:49:49 -0800388 struct bset *i = btree_bset_last(b);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700389 BKEY_PADDED(key) k;
390
391 i->version = BCACHE_BSET_VERSION;
392 i->csum = btree_csum_set(b, i);
393
Kent Overstreet57943512013-04-25 13:58:35 -0700394 BUG_ON(b->bio);
395 b->bio = bch_bbio_alloc(b->c);
396
397 b->bio->bi_end_io = btree_node_write_endio;
Kent Overstreetfaadf0c2013-11-01 18:03:08 -0700398 b->bio->bi_private = cl;
Kent Overstreete49c7c32013-06-26 17:25:38 -0700399 b->bio->bi_rw = REQ_META|WRITE_SYNC|REQ_FUA;
Kent Overstreetee811282013-12-17 23:49:49 -0800400 b->bio->bi_iter.bi_size = roundup(set_bytes(i), block_bytes(b->c));
Kent Overstreet169ef1c2013-03-28 12:50:55 -0600401 bch_bio_map(b->bio, i);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700402
Kent Overstreete49c7c32013-06-26 17:25:38 -0700403 /*
404 * If we're appending to a leaf node, we don't technically need FUA -
405 * this write just needs to be persisted before the next journal write,
406 * which will be marked FLUSH|FUA.
407 *
408 * Similarly if we're writing a new btree root - the pointer is going to
409 * be in the next journal entry.
410 *
411 * But if we're writing a new btree node (that isn't a root) or
412 * appending to a non leaf btree node, we need either FUA or a flush
413 * when we write the parent with the new pointer. FUA is cheaper than a
414 * flush, and writes appending to leaf nodes aren't blocking anything so
415 * just make all btree node writes FUA to keep things sane.
416 */
417
Kent Overstreetcafe5632013-03-23 16:11:31 -0700418 bkey_copy(&k.key, &b->key);
Kent Overstreetee811282013-12-17 23:49:49 -0800419 SET_PTR_OFFSET(&k.key, 0, PTR_OFFSET(&k.key, 0) +
Kent Overstreeta85e9682013-12-20 17:28:16 -0800420 bset_sector_offset(&b->keys, i));
Kent Overstreetcafe5632013-03-23 16:11:31 -0700421
Kent Overstreet8e51e412013-06-06 18:15:57 -0700422 if (!bio_alloc_pages(b->bio, GFP_NOIO)) {
Kent Overstreetcafe5632013-03-23 16:11:31 -0700423 int j;
424 struct bio_vec *bv;
425 void *base = (void *) ((unsigned long) i & ~(PAGE_SIZE - 1));
426
Kent Overstreet79886132013-11-23 17:19:00 -0800427 bio_for_each_segment_all(bv, b->bio, j)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700428 memcpy(page_address(bv->bv_page),
429 base + j * PAGE_SIZE, PAGE_SIZE);
430
Kent Overstreetcafe5632013-03-23 16:11:31 -0700431 bch_submit_bbio(b->bio, b->c, &k.key, 0);
432
Kent Overstreet57943512013-04-25 13:58:35 -0700433 continue_at(cl, btree_node_write_done, NULL);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700434 } else {
435 b->bio->bi_vcnt = 0;
Kent Overstreet169ef1c2013-03-28 12:50:55 -0600436 bch_bio_map(b->bio, i);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700437
Kent Overstreetcafe5632013-03-23 16:11:31 -0700438 bch_submit_bbio(b->bio, b->c, &k.key, 0);
439
440 closure_sync(cl);
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800441 continue_at_nobarrier(cl, __btree_node_write_done, NULL);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700442 }
443}
444
Kent Overstreet57943512013-04-25 13:58:35 -0700445void bch_btree_node_write(struct btree *b, struct closure *parent)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700446{
Kent Overstreetee811282013-12-17 23:49:49 -0800447 struct bset *i = btree_bset_last(b);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700448
Kent Overstreetc37511b2013-04-26 15:39:55 -0700449 trace_bcache_btree_write(b);
450
Kent Overstreetcafe5632013-03-23 16:11:31 -0700451 BUG_ON(current->bio_list);
Kent Overstreet57943512013-04-25 13:58:35 -0700452 BUG_ON(b->written >= btree_blocks(b));
453 BUG_ON(b->written && !i->keys);
Kent Overstreetee811282013-12-17 23:49:49 -0800454 BUG_ON(btree_bset_first(b)->seq != i->seq);
Kent Overstreetdc9d98d2013-12-17 23:47:33 -0800455 bch_check_keys(&b->keys, "writing");
Kent Overstreetcafe5632013-03-23 16:11:31 -0700456
Kent Overstreetcafe5632013-03-23 16:11:31 -0700457 cancel_delayed_work(&b->work);
458
Kent Overstreet57943512013-04-25 13:58:35 -0700459 /* If caller isn't waiting for write, parent refcount is cache set */
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800460 down(&b->io_mutex);
461 closure_init(&b->io, parent ?: &b->c->cl);
Kent Overstreet57943512013-04-25 13:58:35 -0700462
Kent Overstreetcafe5632013-03-23 16:11:31 -0700463 clear_bit(BTREE_NODE_dirty, &b->flags);
464 change_bit(BTREE_NODE_write_idx, &b->flags);
465
Kent Overstreet57943512013-04-25 13:58:35 -0700466 do_btree_node_write(b);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700467
Kent Overstreetee811282013-12-17 23:49:49 -0800468 atomic_long_add(set_blocks(i, block_bytes(b->c)) * b->c->sb.block_size,
Kent Overstreetcafe5632013-03-23 16:11:31 -0700469 &PTR_CACHE(b->c, &b->key, 0)->btree_sectors_written);
470
Kent Overstreeta85e9682013-12-20 17:28:16 -0800471 b->written += set_blocks(i, block_bytes(b->c));
472
Kent Overstreet67539e82013-09-10 22:53:34 -0700473 /* If not a leaf node, always sort */
Kent Overstreeta85e9682013-12-20 17:28:16 -0800474 if (b->level && b->keys.nsets)
Kent Overstreet89ebb4a2013-11-11 18:38:51 -0800475 bch_btree_sort(&b->keys, &b->c->sort);
Kent Overstreet67539e82013-09-10 22:53:34 -0700476 else
Kent Overstreet89ebb4a2013-11-11 18:38:51 -0800477 bch_btree_sort_lazy(&b->keys, &b->c->sort);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700478
Kent Overstreet78b77bf2013-12-17 22:49:08 -0800479 /*
480 * do verify if there was more than one set initially (i.e. we did a
481 * sort) and we sorted down to a single set:
482 */
Kent Overstreeta85e9682013-12-20 17:28:16 -0800483 if (i != b->keys.set->data && !b->keys.nsets)
Kent Overstreet78b77bf2013-12-17 22:49:08 -0800484 bch_btree_verify(b);
485
Kent Overstreetcafe5632013-03-23 16:11:31 -0700486 if (b->written < btree_blocks(b))
Kent Overstreeta85e9682013-12-20 17:28:16 -0800487 bch_bset_init_next(&b->keys, write_block(b),
488 bset_magic(&b->c->sb));
Kent Overstreetcafe5632013-03-23 16:11:31 -0700489}
490
Kent Overstreetf269af52013-07-23 20:48:29 -0700491static void bch_btree_node_write_sync(struct btree *b)
492{
493 struct closure cl;
494
495 closure_init_stack(&cl);
496 bch_btree_node_write(b, &cl);
497 closure_sync(&cl);
498}
499
Kent Overstreet57943512013-04-25 13:58:35 -0700500static void btree_node_write_work(struct work_struct *w)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700501{
502 struct btree *b = container_of(to_delayed_work(w), struct btree, work);
503
Kent Overstreet57943512013-04-25 13:58:35 -0700504 rw_lock(true, b, b->level);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700505
506 if (btree_node_dirty(b))
Kent Overstreet57943512013-04-25 13:58:35 -0700507 bch_btree_node_write(b, NULL);
508 rw_unlock(true, b);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700509}
510
Kent Overstreetc18536a2013-07-24 17:44:17 -0700511static void bch_btree_leaf_dirty(struct btree *b, atomic_t *journal_ref)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700512{
Kent Overstreetee811282013-12-17 23:49:49 -0800513 struct bset *i = btree_bset_last(b);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700514 struct btree_write *w = btree_current_write(b);
515
Kent Overstreet57943512013-04-25 13:58:35 -0700516 BUG_ON(!b->written);
517 BUG_ON(!i->keys);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700518
Kent Overstreet57943512013-04-25 13:58:35 -0700519 if (!btree_node_dirty(b))
520 queue_delayed_work(btree_io_wq, &b->work, 30 * HZ);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700521
Kent Overstreet57943512013-04-25 13:58:35 -0700522 set_btree_node_dirty(b);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700523
Kent Overstreetc18536a2013-07-24 17:44:17 -0700524 if (journal_ref) {
Kent Overstreetcafe5632013-03-23 16:11:31 -0700525 if (w->journal &&
Kent Overstreetc18536a2013-07-24 17:44:17 -0700526 journal_pin_cmp(b->c, w->journal, journal_ref)) {
Kent Overstreetcafe5632013-03-23 16:11:31 -0700527 atomic_dec_bug(w->journal);
528 w->journal = NULL;
529 }
530
531 if (!w->journal) {
Kent Overstreetc18536a2013-07-24 17:44:17 -0700532 w->journal = journal_ref;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700533 atomic_inc(w->journal);
534 }
535 }
536
Kent Overstreetcafe5632013-03-23 16:11:31 -0700537 /* Force write if set is too big */
Kent Overstreet57943512013-04-25 13:58:35 -0700538 if (set_bytes(i) > PAGE_SIZE - 48 &&
539 !current->bio_list)
540 bch_btree_node_write(b, NULL);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700541}
542
543/*
544 * Btree in memory cache - allocation/freeing
545 * mca -> memory cache
546 */
547
Kent Overstreetcafe5632013-03-23 16:11:31 -0700548#define mca_reserve(c) (((c->root && c->root->level) \
549 ? c->root->level : 1) * 8 + 16)
550#define mca_can_free(c) \
551 max_t(int, 0, c->bucket_cache_used - mca_reserve(c))
552
553static void mca_data_free(struct btree *b)
554{
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800555 BUG_ON(b->io_mutex.count != 1);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700556
Kent Overstreeta85e9682013-12-20 17:28:16 -0800557 bch_btree_keys_free(&b->keys);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700558
Kent Overstreetcafe5632013-03-23 16:11:31 -0700559 b->c->bucket_cache_used--;
Kent Overstreetee811282013-12-17 23:49:49 -0800560 list_move(&b->list, &b->c->btree_cache_freed);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700561}
562
563static void mca_bucket_free(struct btree *b)
564{
565 BUG_ON(btree_node_dirty(b));
566
567 b->key.ptr[0] = 0;
568 hlist_del_init_rcu(&b->hash);
569 list_move(&b->list, &b->c->btree_cache_freeable);
570}
571
572static unsigned btree_order(struct bkey *k)
573{
574 return ilog2(KEY_SIZE(k) / PAGE_SECTORS ?: 1);
575}
576
577static void mca_data_alloc(struct btree *b, struct bkey *k, gfp_t gfp)
578{
Kent Overstreeta85e9682013-12-20 17:28:16 -0800579 if (!bch_btree_keys_alloc(&b->keys,
Kent Overstreetee811282013-12-17 23:49:49 -0800580 max_t(unsigned,
581 ilog2(b->c->btree_pages),
582 btree_order(k)),
583 gfp)) {
584 b->c->bucket_cache_used++;
585 list_move(&b->list, &b->c->btree_cache);
586 } else {
587 list_move(&b->list, &b->c->btree_cache_freed);
588 }
Kent Overstreetcafe5632013-03-23 16:11:31 -0700589}
590
591static struct btree *mca_bucket_alloc(struct cache_set *c,
592 struct bkey *k, gfp_t gfp)
593{
594 struct btree *b = kzalloc(sizeof(struct btree), gfp);
595 if (!b)
596 return NULL;
597
598 init_rwsem(&b->lock);
599 lockdep_set_novalidate_class(&b->lock);
600 INIT_LIST_HEAD(&b->list);
Kent Overstreet57943512013-04-25 13:58:35 -0700601 INIT_DELAYED_WORK(&b->work, btree_node_write_work);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700602 b->c = c;
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800603 sema_init(&b->io_mutex, 1);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700604
605 mca_data_alloc(b, k, gfp);
606 return b;
607}
608
Kent Overstreete8e1d462013-07-24 17:27:07 -0700609static int mca_reap(struct btree *b, unsigned min_order, bool flush)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700610{
Kent Overstreete8e1d462013-07-24 17:27:07 -0700611 struct closure cl;
612
613 closure_init_stack(&cl);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700614 lockdep_assert_held(&b->c->bucket_lock);
615
616 if (!down_write_trylock(&b->lock))
617 return -ENOMEM;
618
Kent Overstreeta85e9682013-12-20 17:28:16 -0800619 BUG_ON(btree_node_dirty(b) && !b->keys.set[0].data);
Kent Overstreete8e1d462013-07-24 17:27:07 -0700620
Kent Overstreeta85e9682013-12-20 17:28:16 -0800621 if (b->keys.page_order < min_order)
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800622 goto out_unlock;
623
624 if (!flush) {
625 if (btree_node_dirty(b))
626 goto out_unlock;
627
628 if (down_trylock(&b->io_mutex))
629 goto out_unlock;
630 up(&b->io_mutex);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700631 }
632
Kent Overstreetf269af52013-07-23 20:48:29 -0700633 if (btree_node_dirty(b))
634 bch_btree_node_write_sync(b);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700635
Kent Overstreete8e1d462013-07-24 17:27:07 -0700636 /* wait for any in flight btree write */
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800637 down(&b->io_mutex);
638 up(&b->io_mutex);
Kent Overstreete8e1d462013-07-24 17:27:07 -0700639
Kent Overstreetcafe5632013-03-23 16:11:31 -0700640 return 0;
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800641out_unlock:
642 rw_unlock(true, b);
643 return -ENOMEM;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700644}
645
Dave Chinner7dc19d52013-08-28 10:18:11 +1000646static unsigned long bch_mca_scan(struct shrinker *shrink,
647 struct shrink_control *sc)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700648{
649 struct cache_set *c = container_of(shrink, struct cache_set, shrink);
650 struct btree *b, *t;
651 unsigned long i, nr = sc->nr_to_scan;
Dave Chinner7dc19d52013-08-28 10:18:11 +1000652 unsigned long freed = 0;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700653
654 if (c->shrinker_disabled)
Dave Chinner7dc19d52013-08-28 10:18:11 +1000655 return SHRINK_STOP;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700656
657 if (c->try_harder)
Dave Chinner7dc19d52013-08-28 10:18:11 +1000658 return SHRINK_STOP;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700659
660 /* Return -1 if we can't do anything right now */
Kent Overstreeta698e082013-09-23 23:17:34 -0700661 if (sc->gfp_mask & __GFP_IO)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700662 mutex_lock(&c->bucket_lock);
663 else if (!mutex_trylock(&c->bucket_lock))
664 return -1;
665
Kent Overstreet36c9ea92013-06-03 13:04:56 -0700666 /*
667 * It's _really_ critical that we don't free too many btree nodes - we
668 * have to always leave ourselves a reserve. The reserve is how we
669 * guarantee that allocating memory for a new btree node can always
670 * succeed, so that inserting keys into the btree can always succeed and
671 * IO can always make forward progress:
672 */
Kent Overstreetcafe5632013-03-23 16:11:31 -0700673 nr /= c->btree_pages;
674 nr = min_t(unsigned long, nr, mca_can_free(c));
675
676 i = 0;
677 list_for_each_entry_safe(b, t, &c->btree_cache_freeable, list) {
Dave Chinner7dc19d52013-08-28 10:18:11 +1000678 if (freed >= nr)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700679 break;
680
681 if (++i > 3 &&
Kent Overstreete8e1d462013-07-24 17:27:07 -0700682 !mca_reap(b, 0, false)) {
Kent Overstreetcafe5632013-03-23 16:11:31 -0700683 mca_data_free(b);
684 rw_unlock(true, b);
Dave Chinner7dc19d52013-08-28 10:18:11 +1000685 freed++;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700686 }
687 }
688
Dave Chinner7dc19d52013-08-28 10:18:11 +1000689 for (i = 0; (nr--) && i < c->bucket_cache_used; i++) {
Kent Overstreetb0f32a52013-12-10 13:24:26 -0800690 if (list_empty(&c->btree_cache))
691 goto out;
692
Kent Overstreetcafe5632013-03-23 16:11:31 -0700693 b = list_first_entry(&c->btree_cache, struct btree, list);
694 list_rotate_left(&c->btree_cache);
695
696 if (!b->accessed &&
Kent Overstreete8e1d462013-07-24 17:27:07 -0700697 !mca_reap(b, 0, false)) {
Kent Overstreetcafe5632013-03-23 16:11:31 -0700698 mca_bucket_free(b);
699 mca_data_free(b);
700 rw_unlock(true, b);
Dave Chinner7dc19d52013-08-28 10:18:11 +1000701 freed++;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700702 } else
703 b->accessed = 0;
704 }
705out:
Kent Overstreetcafe5632013-03-23 16:11:31 -0700706 mutex_unlock(&c->bucket_lock);
Dave Chinner7dc19d52013-08-28 10:18:11 +1000707 return freed;
708}
709
710static unsigned long bch_mca_count(struct shrinker *shrink,
711 struct shrink_control *sc)
712{
713 struct cache_set *c = container_of(shrink, struct cache_set, shrink);
714
715 if (c->shrinker_disabled)
716 return 0;
717
718 if (c->try_harder)
719 return 0;
720
721 return mca_can_free(c) * c->btree_pages;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700722}
723
724void bch_btree_cache_free(struct cache_set *c)
725{
726 struct btree *b;
727 struct closure cl;
728 closure_init_stack(&cl);
729
730 if (c->shrink.list.next)
731 unregister_shrinker(&c->shrink);
732
733 mutex_lock(&c->bucket_lock);
734
735#ifdef CONFIG_BCACHE_DEBUG
736 if (c->verify_data)
737 list_move(&c->verify_data->list, &c->btree_cache);
Kent Overstreet78b77bf2013-12-17 22:49:08 -0800738
739 free_pages((unsigned long) c->verify_ondisk, ilog2(bucket_pages(c)));
Kent Overstreetcafe5632013-03-23 16:11:31 -0700740#endif
741
742 list_splice(&c->btree_cache_freeable,
743 &c->btree_cache);
744
745 while (!list_empty(&c->btree_cache)) {
746 b = list_first_entry(&c->btree_cache, struct btree, list);
747
748 if (btree_node_dirty(b))
749 btree_complete_write(b, btree_current_write(b));
750 clear_bit(BTREE_NODE_dirty, &b->flags);
751
752 mca_data_free(b);
753 }
754
755 while (!list_empty(&c->btree_cache_freed)) {
756 b = list_first_entry(&c->btree_cache_freed,
757 struct btree, list);
758 list_del(&b->list);
759 cancel_delayed_work_sync(&b->work);
760 kfree(b);
761 }
762
763 mutex_unlock(&c->bucket_lock);
764}
765
766int bch_btree_cache_alloc(struct cache_set *c)
767{
768 unsigned i;
769
Kent Overstreetcafe5632013-03-23 16:11:31 -0700770 for (i = 0; i < mca_reserve(c); i++)
Kent Overstreet72a44512013-10-24 17:19:26 -0700771 if (!mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL))
772 return -ENOMEM;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700773
774 list_splice_init(&c->btree_cache,
775 &c->btree_cache_freeable);
776
777#ifdef CONFIG_BCACHE_DEBUG
778 mutex_init(&c->verify_lock);
779
Kent Overstreet78b77bf2013-12-17 22:49:08 -0800780 c->verify_ondisk = (void *)
781 __get_free_pages(GFP_KERNEL, ilog2(bucket_pages(c)));
782
Kent Overstreetcafe5632013-03-23 16:11:31 -0700783 c->verify_data = mca_bucket_alloc(c, &ZERO_KEY, GFP_KERNEL);
784
785 if (c->verify_data &&
Kent Overstreeta85e9682013-12-20 17:28:16 -0800786 c->verify_data->keys.set->data)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700787 list_del_init(&c->verify_data->list);
788 else
789 c->verify_data = NULL;
790#endif
791
Dave Chinner7dc19d52013-08-28 10:18:11 +1000792 c->shrink.count_objects = bch_mca_count;
793 c->shrink.scan_objects = bch_mca_scan;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700794 c->shrink.seeks = 4;
795 c->shrink.batch = c->btree_pages * 2;
796 register_shrinker(&c->shrink);
797
798 return 0;
799}
800
801/* Btree in memory cache - hash table */
802
803static struct hlist_head *mca_hash(struct cache_set *c, struct bkey *k)
804{
805 return &c->bucket_hash[hash_32(PTR_HASH(c, k), BUCKET_HASH_BITS)];
806}
807
808static struct btree *mca_find(struct cache_set *c, struct bkey *k)
809{
810 struct btree *b;
811
812 rcu_read_lock();
813 hlist_for_each_entry_rcu(b, mca_hash(c, k), hash)
814 if (PTR_HASH(c, &b->key) == PTR_HASH(c, k))
815 goto out;
816 b = NULL;
817out:
818 rcu_read_unlock();
819 return b;
820}
821
Kent Overstreete8e1d462013-07-24 17:27:07 -0700822static struct btree *mca_cannibalize(struct cache_set *c, struct bkey *k)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700823{
Kent Overstreete8e1d462013-07-24 17:27:07 -0700824 struct btree *b;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700825
Kent Overstreetc37511b2013-04-26 15:39:55 -0700826 trace_bcache_btree_cache_cannibalize(c);
827
Kent Overstreete8e1d462013-07-24 17:27:07 -0700828 if (!c->try_harder) {
829 c->try_harder = current;
830 c->try_harder_start = local_clock();
831 } else if (c->try_harder != current)
832 return ERR_PTR(-ENOSPC);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700833
Kent Overstreete8e1d462013-07-24 17:27:07 -0700834 list_for_each_entry_reverse(b, &c->btree_cache, list)
835 if (!mca_reap(b, btree_order(k), false))
836 return b;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700837
Kent Overstreete8e1d462013-07-24 17:27:07 -0700838 list_for_each_entry_reverse(b, &c->btree_cache, list)
839 if (!mca_reap(b, btree_order(k), true))
840 return b;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700841
Kent Overstreete8e1d462013-07-24 17:27:07 -0700842 return ERR_PTR(-ENOMEM);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700843}
844
845/*
846 * We can only have one thread cannibalizing other cached btree nodes at a time,
847 * or we'll deadlock. We use an open coded mutex to ensure that, which a
848 * cannibalize_bucket() will take. This means every time we unlock the root of
849 * the btree, we need to release this lock if we have it held.
850 */
Kent Overstreetdf8e8972013-07-24 17:37:59 -0700851static void bch_cannibalize_unlock(struct cache_set *c)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700852{
Kent Overstreete8e1d462013-07-24 17:27:07 -0700853 if (c->try_harder == current) {
Kent Overstreet169ef1c2013-03-28 12:50:55 -0600854 bch_time_stats_update(&c->try_harder_time, c->try_harder_start);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700855 c->try_harder = NULL;
Kent Overstreete8e1d462013-07-24 17:27:07 -0700856 wake_up(&c->try_wait);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700857 }
858}
859
Kent Overstreete8e1d462013-07-24 17:27:07 -0700860static struct btree *mca_alloc(struct cache_set *c, struct bkey *k, int level)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700861{
862 struct btree *b;
863
Kent Overstreete8e1d462013-07-24 17:27:07 -0700864 BUG_ON(current->bio_list);
865
Kent Overstreetcafe5632013-03-23 16:11:31 -0700866 lockdep_assert_held(&c->bucket_lock);
867
868 if (mca_find(c, k))
869 return NULL;
870
871 /* btree_free() doesn't free memory; it sticks the node on the end of
872 * the list. Check if there's any freed nodes there:
873 */
874 list_for_each_entry(b, &c->btree_cache_freeable, list)
Kent Overstreete8e1d462013-07-24 17:27:07 -0700875 if (!mca_reap(b, btree_order(k), false))
Kent Overstreetcafe5632013-03-23 16:11:31 -0700876 goto out;
877
878 /* We never free struct btree itself, just the memory that holds the on
879 * disk node. Check the freed list before allocating a new one:
880 */
881 list_for_each_entry(b, &c->btree_cache_freed, list)
Kent Overstreete8e1d462013-07-24 17:27:07 -0700882 if (!mca_reap(b, 0, false)) {
Kent Overstreetcafe5632013-03-23 16:11:31 -0700883 mca_data_alloc(b, k, __GFP_NOWARN|GFP_NOIO);
Kent Overstreeta85e9682013-12-20 17:28:16 -0800884 if (!b->keys.set[0].data)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700885 goto err;
886 else
887 goto out;
888 }
889
890 b = mca_bucket_alloc(c, k, __GFP_NOWARN|GFP_NOIO);
891 if (!b)
892 goto err;
893
894 BUG_ON(!down_write_trylock(&b->lock));
Kent Overstreeta85e9682013-12-20 17:28:16 -0800895 if (!b->keys.set->data)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700896 goto err;
897out:
Kent Overstreetcb7a5832013-12-16 15:27:25 -0800898 BUG_ON(b->io_mutex.count != 1);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700899
900 bkey_copy(&b->key, k);
901 list_move(&b->list, &c->btree_cache);
902 hlist_del_init_rcu(&b->hash);
903 hlist_add_head_rcu(&b->hash, mca_hash(c, k));
904
905 lock_set_subclass(&b->lock.dep_map, level + 1, _THIS_IP_);
Kent Overstreetd6fd3b12013-07-24 17:20:19 -0700906 b->parent = (void *) ~0UL;
Kent Overstreeta85e9682013-12-20 17:28:16 -0800907 b->flags = 0;
908 b->written = 0;
909 b->level = level;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700910
Kent Overstreet65d45232013-12-20 17:22:05 -0800911 if (!b->level)
Kent Overstreeta85e9682013-12-20 17:28:16 -0800912 bch_btree_keys_init(&b->keys, &bch_extent_keys_ops,
913 &b->c->expensive_debug_checks);
Kent Overstreet65d45232013-12-20 17:22:05 -0800914 else
Kent Overstreeta85e9682013-12-20 17:28:16 -0800915 bch_btree_keys_init(&b->keys, &bch_btree_keys_ops,
916 &b->c->expensive_debug_checks);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700917
918 return b;
919err:
920 if (b)
921 rw_unlock(true, b);
922
Kent Overstreete8e1d462013-07-24 17:27:07 -0700923 b = mca_cannibalize(c, k);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700924 if (!IS_ERR(b))
925 goto out;
926
927 return b;
928}
929
930/**
931 * bch_btree_node_get - find a btree node in the cache and lock it, reading it
932 * in from disk if necessary.
933 *
Kent Overstreetb54d6932013-07-24 18:04:18 -0700934 * If IO is necessary and running under generic_make_request, returns -EAGAIN.
Kent Overstreetcafe5632013-03-23 16:11:31 -0700935 *
936 * The btree node will have either a read or a write lock held, depending on
937 * level and op->lock.
938 */
939struct btree *bch_btree_node_get(struct cache_set *c, struct bkey *k,
Kent Overstreete8e1d462013-07-24 17:27:07 -0700940 int level, bool write)
Kent Overstreetcafe5632013-03-23 16:11:31 -0700941{
942 int i = 0;
Kent Overstreetcafe5632013-03-23 16:11:31 -0700943 struct btree *b;
944
945 BUG_ON(level < 0);
946retry:
947 b = mca_find(c, k);
948
949 if (!b) {
Kent Overstreet57943512013-04-25 13:58:35 -0700950 if (current->bio_list)
951 return ERR_PTR(-EAGAIN);
952
Kent Overstreetcafe5632013-03-23 16:11:31 -0700953 mutex_lock(&c->bucket_lock);
Kent Overstreete8e1d462013-07-24 17:27:07 -0700954 b = mca_alloc(c, k, level);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700955 mutex_unlock(&c->bucket_lock);
956
957 if (!b)
958 goto retry;
959 if (IS_ERR(b))
960 return b;
961
Kent Overstreet57943512013-04-25 13:58:35 -0700962 bch_btree_node_read(b);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700963
964 if (!write)
965 downgrade_write(&b->lock);
966 } else {
967 rw_lock(write, b, level);
968 if (PTR_HASH(c, &b->key) != PTR_HASH(c, k)) {
969 rw_unlock(write, b);
970 goto retry;
971 }
972 BUG_ON(b->level != level);
973 }
974
975 b->accessed = 1;
976
Kent Overstreeta85e9682013-12-20 17:28:16 -0800977 for (; i <= b->keys.nsets && b->keys.set[i].size; i++) {
978 prefetch(b->keys.set[i].tree);
979 prefetch(b->keys.set[i].data);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700980 }
981
Kent Overstreeta85e9682013-12-20 17:28:16 -0800982 for (; i <= b->keys.nsets; i++)
983 prefetch(b->keys.set[i].data);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700984
Kent Overstreet57943512013-04-25 13:58:35 -0700985 if (btree_node_io_error(b)) {
Kent Overstreetcafe5632013-03-23 16:11:31 -0700986 rw_unlock(write, b);
Kent Overstreet57943512013-04-25 13:58:35 -0700987 return ERR_PTR(-EIO);
988 }
989
990 BUG_ON(!b->written);
Kent Overstreetcafe5632013-03-23 16:11:31 -0700991
992 return b;
993}
994
995static void btree_node_prefetch(struct cache_set *c, struct bkey *k, int level)
996{
997 struct btree *b;
998
999 mutex_lock(&c->bucket_lock);
Kent Overstreete8e1d462013-07-24 17:27:07 -07001000 b = mca_alloc(c, k, level);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001001 mutex_unlock(&c->bucket_lock);
1002
1003 if (!IS_ERR_OR_NULL(b)) {
Kent Overstreet57943512013-04-25 13:58:35 -07001004 bch_btree_node_read(b);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001005 rw_unlock(true, b);
1006 }
1007}
1008
1009/* Btree alloc */
1010
Kent Overstreete8e1d462013-07-24 17:27:07 -07001011static void btree_node_free(struct btree *b)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001012{
1013 unsigned i;
1014
Kent Overstreetc37511b2013-04-26 15:39:55 -07001015 trace_bcache_btree_node_free(b);
1016
Kent Overstreetcafe5632013-03-23 16:11:31 -07001017 BUG_ON(b == b->c->root);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001018
1019 if (btree_node_dirty(b))
1020 btree_complete_write(b, btree_current_write(b));
1021 clear_bit(BTREE_NODE_dirty, &b->flags);
1022
Kent Overstreetcafe5632013-03-23 16:11:31 -07001023 cancel_delayed_work(&b->work);
1024
1025 mutex_lock(&b->c->bucket_lock);
1026
1027 for (i = 0; i < KEY_PTRS(&b->key); i++) {
1028 BUG_ON(atomic_read(&PTR_BUCKET(b->c, &b->key, i)->pin));
1029
1030 bch_inc_gen(PTR_CACHE(b->c, &b->key, i),
1031 PTR_BUCKET(b->c, &b->key, i));
1032 }
1033
1034 bch_bucket_free(b->c, &b->key);
1035 mca_bucket_free(b);
1036 mutex_unlock(&b->c->bucket_lock);
1037}
1038
Kent Overstreetbc9389e2013-09-10 19:07:35 -07001039struct btree *bch_btree_node_alloc(struct cache_set *c, int level, bool wait)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001040{
1041 BKEY_PADDED(key) k;
1042 struct btree *b = ERR_PTR(-EAGAIN);
1043
1044 mutex_lock(&c->bucket_lock);
1045retry:
Kent Overstreet78365412013-12-17 01:29:34 -08001046 if (__bch_bucket_alloc_set(c, RESERVE_BTREE, &k.key, 1, wait))
Kent Overstreetcafe5632013-03-23 16:11:31 -07001047 goto err;
1048
Kent Overstreet3a3b6a42013-07-24 16:46:42 -07001049 bkey_put(c, &k.key);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001050 SET_KEY_SIZE(&k.key, c->btree_pages * PAGE_SECTORS);
1051
Kent Overstreete8e1d462013-07-24 17:27:07 -07001052 b = mca_alloc(c, &k.key, level);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001053 if (IS_ERR(b))
1054 goto err_free;
1055
1056 if (!b) {
Kent Overstreetb1a67b02013-03-25 11:46:44 -07001057 cache_bug(c,
1058 "Tried to allocate bucket that was in btree cache");
Kent Overstreetcafe5632013-03-23 16:11:31 -07001059 goto retry;
1060 }
1061
Kent Overstreetcafe5632013-03-23 16:11:31 -07001062 b->accessed = 1;
Kent Overstreeta85e9682013-12-20 17:28:16 -08001063 bch_bset_init_next(&b->keys, b->keys.set->data, bset_magic(&b->c->sb));
Kent Overstreetcafe5632013-03-23 16:11:31 -07001064
1065 mutex_unlock(&c->bucket_lock);
Kent Overstreetc37511b2013-04-26 15:39:55 -07001066
1067 trace_bcache_btree_node_alloc(b);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001068 return b;
1069err_free:
1070 bch_bucket_free(c, &k.key);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001071err:
1072 mutex_unlock(&c->bucket_lock);
Kent Overstreetc37511b2013-04-26 15:39:55 -07001073
1074 trace_bcache_btree_node_alloc_fail(b);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001075 return b;
1076}
1077
Kent Overstreetbc9389e2013-09-10 19:07:35 -07001078static struct btree *btree_node_alloc_replacement(struct btree *b, bool wait)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001079{
Kent Overstreetbc9389e2013-09-10 19:07:35 -07001080 struct btree *n = bch_btree_node_alloc(b->c, b->level, wait);
Kent Overstreet67539e82013-09-10 22:53:34 -07001081 if (!IS_ERR_OR_NULL(n)) {
Kent Overstreet89ebb4a2013-11-11 18:38:51 -08001082 bch_btree_sort_into(&b->keys, &n->keys, &b->c->sort);
Kent Overstreet67539e82013-09-10 22:53:34 -07001083 bkey_copy_key(&n->key, &b->key);
1084 }
Kent Overstreetcafe5632013-03-23 16:11:31 -07001085
1086 return n;
1087}
1088
Kent Overstreet8835c122013-07-24 23:18:05 -07001089static void make_btree_freeing_key(struct btree *b, struct bkey *k)
1090{
1091 unsigned i;
1092
1093 bkey_copy(k, &b->key);
1094 bkey_copy_key(k, &ZERO_KEY);
1095
1096 for (i = 0; i < KEY_PTRS(k); i++) {
1097 uint8_t g = PTR_BUCKET(b->c, k, i)->gen + 1;
1098
1099 SET_PTR_GEN(k, i, g);
1100 }
1101
1102 atomic_inc(&b->c->prio_blocked);
1103}
1104
Kent Overstreet78365412013-12-17 01:29:34 -08001105static int btree_check_reserve(struct btree *b, struct btree_op *op)
1106{
1107 struct cache_set *c = b->c;
1108 struct cache *ca;
1109 unsigned i, reserve = c->root->level * 2 + 1;
1110 int ret = 0;
1111
1112 mutex_lock(&c->bucket_lock);
1113
1114 for_each_cache(ca, c, i)
1115 if (fifo_used(&ca->free[RESERVE_BTREE]) < reserve) {
1116 if (op)
1117 prepare_to_wait(&c->bucket_wait, &op->wait,
1118 TASK_UNINTERRUPTIBLE);
1119 ret = -EINTR;
1120 break;
1121 }
1122
1123 mutex_unlock(&c->bucket_lock);
1124 return ret;
1125}
1126
Kent Overstreetcafe5632013-03-23 16:11:31 -07001127/* Garbage collection */
1128
1129uint8_t __bch_btree_mark_key(struct cache_set *c, int level, struct bkey *k)
1130{
1131 uint8_t stale = 0;
1132 unsigned i;
1133 struct bucket *g;
1134
1135 /*
1136 * ptr_invalid() can't return true for the keys that mark btree nodes as
1137 * freed, but since ptr_bad() returns true we'll never actually use them
1138 * for anything and thus we don't want mark their pointers here
1139 */
1140 if (!bkey_cmp(k, &ZERO_KEY))
1141 return stale;
1142
1143 for (i = 0; i < KEY_PTRS(k); i++) {
1144 if (!ptr_available(c, k, i))
1145 continue;
1146
1147 g = PTR_BUCKET(c, k, i);
1148
1149 if (gen_after(g->gc_gen, PTR_GEN(k, i)))
1150 g->gc_gen = PTR_GEN(k, i);
1151
1152 if (ptr_stale(c, k, i)) {
1153 stale = max(stale, ptr_stale(c, k, i));
1154 continue;
1155 }
1156
1157 cache_bug_on(GC_MARK(g) &&
1158 (GC_MARK(g) == GC_MARK_METADATA) != (level != 0),
1159 c, "inconsistent ptrs: mark = %llu, level = %i",
1160 GC_MARK(g), level);
1161
1162 if (level)
1163 SET_GC_MARK(g, GC_MARK_METADATA);
1164 else if (KEY_DIRTY(k))
1165 SET_GC_MARK(g, GC_MARK_DIRTY);
1166
1167 /* guard against overflow */
1168 SET_GC_SECTORS_USED(g, min_t(unsigned,
1169 GC_SECTORS_USED(g) + KEY_SIZE(k),
1170 (1 << 14) - 1));
1171
1172 BUG_ON(!GC_SECTORS_USED(g));
1173 }
1174
1175 return stale;
1176}
1177
1178#define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k)
1179
Kent Overstreeta1f03582013-09-10 19:07:00 -07001180static bool btree_gc_mark_node(struct btree *b, struct gc_stat *gc)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001181{
1182 uint8_t stale = 0;
Kent Overstreeta1f03582013-09-10 19:07:00 -07001183 unsigned keys = 0, good_keys = 0;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001184 struct bkey *k;
1185 struct btree_iter iter;
1186 struct bset_tree *t;
1187
1188 gc->nodes++;
1189
Kent Overstreetc052dd92013-11-11 17:35:24 -08001190 for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) {
Kent Overstreetcafe5632013-03-23 16:11:31 -07001191 stale = max(stale, btree_mark_key(b, k));
Kent Overstreeta1f03582013-09-10 19:07:00 -07001192 keys++;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001193
Kent Overstreeta85e9682013-12-20 17:28:16 -08001194 if (bch_ptr_bad(&b->keys, k))
Kent Overstreetcafe5632013-03-23 16:11:31 -07001195 continue;
1196
Kent Overstreetcafe5632013-03-23 16:11:31 -07001197 gc->key_bytes += bkey_u64s(k);
1198 gc->nkeys++;
Kent Overstreeta1f03582013-09-10 19:07:00 -07001199 good_keys++;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001200
1201 gc->data += KEY_SIZE(k);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001202 }
1203
Kent Overstreeta85e9682013-12-20 17:28:16 -08001204 for (t = b->keys.set; t <= &b->keys.set[b->keys.nsets]; t++)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001205 btree_bug_on(t->size &&
Kent Overstreeta85e9682013-12-20 17:28:16 -08001206 bset_written(&b->keys, t) &&
Kent Overstreetcafe5632013-03-23 16:11:31 -07001207 bkey_cmp(&b->key, &t->end) < 0,
1208 b, "found short btree key in gc");
1209
Kent Overstreeta1f03582013-09-10 19:07:00 -07001210 if (b->c->gc_always_rewrite)
1211 return true;
1212
1213 if (stale > 10)
1214 return true;
1215
1216 if ((keys - good_keys) * 2 > keys)
1217 return true;
1218
1219 return false;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001220}
1221
Kent Overstreeta1f03582013-09-10 19:07:00 -07001222#define GC_MERGE_NODES 4U
Kent Overstreetcafe5632013-03-23 16:11:31 -07001223
1224struct gc_merge_info {
1225 struct btree *b;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001226 unsigned keys;
1227};
1228
Kent Overstreeta1f03582013-09-10 19:07:00 -07001229static int bch_btree_insert_node(struct btree *, struct btree_op *,
1230 struct keylist *, atomic_t *, struct bkey *);
Kent Overstreetb54d6932013-07-24 18:04:18 -07001231
Kent Overstreeta1f03582013-09-10 19:07:00 -07001232static int btree_gc_coalesce(struct btree *b, struct btree_op *op,
1233 struct keylist *keylist, struct gc_stat *gc,
1234 struct gc_merge_info *r)
1235{
1236 unsigned i, nodes = 0, keys = 0, blocks;
1237 struct btree *new_nodes[GC_MERGE_NODES];
1238 struct closure cl;
1239 struct bkey *k;
1240
1241 memset(new_nodes, 0, sizeof(new_nodes));
Kent Overstreetb54d6932013-07-24 18:04:18 -07001242 closure_init_stack(&cl);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001243
Kent Overstreeta1f03582013-09-10 19:07:00 -07001244 while (nodes < GC_MERGE_NODES && !IS_ERR_OR_NULL(r[nodes].b))
Kent Overstreetcafe5632013-03-23 16:11:31 -07001245 keys += r[nodes++].keys;
1246
1247 blocks = btree_default_blocks(b->c) * 2 / 3;
1248
1249 if (nodes < 2 ||
Kent Overstreeta85e9682013-12-20 17:28:16 -08001250 __set_blocks(b->keys.set[0].data, keys,
Kent Overstreetee811282013-12-17 23:49:49 -08001251 block_bytes(b->c)) > blocks * (nodes - 1))
Kent Overstreeta1f03582013-09-10 19:07:00 -07001252 return 0;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001253
Kent Overstreeta1f03582013-09-10 19:07:00 -07001254 for (i = 0; i < nodes; i++) {
Kent Overstreetbc9389e2013-09-10 19:07:35 -07001255 new_nodes[i] = btree_node_alloc_replacement(r[i].b, false);
Kent Overstreeta1f03582013-09-10 19:07:00 -07001256 if (IS_ERR_OR_NULL(new_nodes[i]))
1257 goto out_nocoalesce;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001258 }
1259
1260 for (i = nodes - 1; i > 0; --i) {
Kent Overstreetee811282013-12-17 23:49:49 -08001261 struct bset *n1 = btree_bset_first(new_nodes[i]);
1262 struct bset *n2 = btree_bset_first(new_nodes[i - 1]);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001263 struct bkey *k, *last = NULL;
1264
1265 keys = 0;
1266
Kent Overstreeta1f03582013-09-10 19:07:00 -07001267 if (i > 1) {
Kent Overstreetcafe5632013-03-23 16:11:31 -07001268 for (k = n2->start;
Kent Overstreetfafff812013-12-17 21:56:21 -08001269 k < bset_bkey_last(n2);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001270 k = bkey_next(k)) {
1271 if (__set_blocks(n1, n1->keys + keys +
Kent Overstreetee811282013-12-17 23:49:49 -08001272 bkey_u64s(k),
1273 block_bytes(b->c)) > blocks)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001274 break;
1275
1276 last = k;
1277 keys += bkey_u64s(k);
1278 }
Kent Overstreeta1f03582013-09-10 19:07:00 -07001279 } else {
1280 /*
1281 * Last node we're not getting rid of - we're getting
1282 * rid of the node at r[0]. Have to try and fit all of
1283 * the remaining keys into this node; we can't ensure
1284 * they will always fit due to rounding and variable
1285 * length keys (shouldn't be possible in practice,
1286 * though)
1287 */
1288 if (__set_blocks(n1, n1->keys + n2->keys,
Kent Overstreetee811282013-12-17 23:49:49 -08001289 block_bytes(b->c)) >
1290 btree_blocks(new_nodes[i]))
Kent Overstreeta1f03582013-09-10 19:07:00 -07001291 goto out_nocoalesce;
1292
1293 keys = n2->keys;
1294 /* Take the key of the node we're getting rid of */
1295 last = &r->b->key;
1296 }
Kent Overstreetcafe5632013-03-23 16:11:31 -07001297
Kent Overstreetee811282013-12-17 23:49:49 -08001298 BUG_ON(__set_blocks(n1, n1->keys + keys, block_bytes(b->c)) >
1299 btree_blocks(new_nodes[i]));
Kent Overstreetcafe5632013-03-23 16:11:31 -07001300
Kent Overstreeta1f03582013-09-10 19:07:00 -07001301 if (last)
1302 bkey_copy_key(&new_nodes[i]->key, last);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001303
Kent Overstreetfafff812013-12-17 21:56:21 -08001304 memcpy(bset_bkey_last(n1),
Kent Overstreetcafe5632013-03-23 16:11:31 -07001305 n2->start,
Kent Overstreetfafff812013-12-17 21:56:21 -08001306 (void *) bset_bkey_idx(n2, keys) - (void *) n2->start);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001307
1308 n1->keys += keys;
Kent Overstreeta1f03582013-09-10 19:07:00 -07001309 r[i].keys = n1->keys;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001310
1311 memmove(n2->start,
Kent Overstreetfafff812013-12-17 21:56:21 -08001312 bset_bkey_idx(n2, keys),
1313 (void *) bset_bkey_last(n2) -
1314 (void *) bset_bkey_idx(n2, keys));
Kent Overstreetcafe5632013-03-23 16:11:31 -07001315
1316 n2->keys -= keys;
1317
Kent Overstreet085d2a32013-11-11 18:20:51 -08001318 if (__bch_keylist_realloc(keylist,
1319 bkey_u64s(&new_nodes[i]->key)))
Kent Overstreeta1f03582013-09-10 19:07:00 -07001320 goto out_nocoalesce;
1321
1322 bch_btree_node_write(new_nodes[i], &cl);
1323 bch_keylist_add(keylist, &new_nodes[i]->key);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001324 }
1325
Kent Overstreeta1f03582013-09-10 19:07:00 -07001326 for (i = 0; i < nodes; i++) {
Kent Overstreet085d2a32013-11-11 18:20:51 -08001327 if (__bch_keylist_realloc(keylist, bkey_u64s(&r[i].b->key)))
Kent Overstreeta1f03582013-09-10 19:07:00 -07001328 goto out_nocoalesce;
1329
1330 make_btree_freeing_key(r[i].b, keylist->top);
1331 bch_keylist_push(keylist);
1332 }
1333
1334 /* We emptied out this node */
Kent Overstreetee811282013-12-17 23:49:49 -08001335 BUG_ON(btree_bset_first(new_nodes[0])->keys);
Kent Overstreeta1f03582013-09-10 19:07:00 -07001336 btree_node_free(new_nodes[0]);
1337 rw_unlock(true, new_nodes[0]);
1338
1339 closure_sync(&cl);
1340
1341 for (i = 0; i < nodes; i++) {
1342 btree_node_free(r[i].b);
1343 rw_unlock(true, r[i].b);
1344
1345 r[i].b = new_nodes[i];
1346 }
1347
1348 bch_btree_insert_node(b, op, keylist, NULL, NULL);
1349 BUG_ON(!bch_keylist_empty(keylist));
1350
1351 memmove(r, r + 1, sizeof(r[0]) * (nodes - 1));
1352 r[nodes - 1].b = ERR_PTR(-EINTR);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001353
Kent Overstreetc37511b2013-04-26 15:39:55 -07001354 trace_bcache_btree_gc_coalesce(nodes);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001355 gc->nodes--;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001356
Kent Overstreeta1f03582013-09-10 19:07:00 -07001357 /* Invalidated our iterator */
1358 return -EINTR;
1359
1360out_nocoalesce:
1361 closure_sync(&cl);
1362
1363 while ((k = bch_keylist_pop(keylist)))
1364 if (!bkey_cmp(k, &ZERO_KEY))
1365 atomic_dec(&b->c->prio_blocked);
1366
1367 for (i = 0; i < nodes; i++)
1368 if (!IS_ERR_OR_NULL(new_nodes[i])) {
1369 btree_node_free(new_nodes[i]);
1370 rw_unlock(true, new_nodes[i]);
1371 }
1372 return 0;
1373}
1374
1375static unsigned btree_gc_count_keys(struct btree *b)
1376{
1377 struct bkey *k;
1378 struct btree_iter iter;
1379 unsigned ret = 0;
1380
Kent Overstreetc052dd92013-11-11 17:35:24 -08001381 for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad)
Kent Overstreeta1f03582013-09-10 19:07:00 -07001382 ret += bkey_u64s(k);
1383
1384 return ret;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001385}
1386
1387static int btree_gc_recurse(struct btree *b, struct btree_op *op,
1388 struct closure *writes, struct gc_stat *gc)
1389{
Kent Overstreetcafe5632013-03-23 16:11:31 -07001390 unsigned i;
Kent Overstreeta1f03582013-09-10 19:07:00 -07001391 int ret = 0;
1392 bool should_rewrite;
1393 struct btree *n;
1394 struct bkey *k;
1395 struct keylist keys;
1396 struct btree_iter iter;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001397 struct gc_merge_info r[GC_MERGE_NODES];
Kent Overstreeta1f03582013-09-10 19:07:00 -07001398 struct gc_merge_info *last = r + GC_MERGE_NODES - 1;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001399
Kent Overstreeta1f03582013-09-10 19:07:00 -07001400 bch_keylist_init(&keys);
Kent Overstreetc052dd92013-11-11 17:35:24 -08001401 bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001402
Kent Overstreeta1f03582013-09-10 19:07:00 -07001403 for (i = 0; i < GC_MERGE_NODES; i++)
1404 r[i].b = ERR_PTR(-EINTR);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001405
Kent Overstreeta1f03582013-09-10 19:07:00 -07001406 while (1) {
Kent Overstreeta85e9682013-12-20 17:28:16 -08001407 k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad);
Kent Overstreeta1f03582013-09-10 19:07:00 -07001408 if (k) {
1409 r->b = bch_btree_node_get(b->c, k, b->level - 1, true);
1410 if (IS_ERR(r->b)) {
1411 ret = PTR_ERR(r->b);
1412 break;
1413 }
1414
1415 r->keys = btree_gc_count_keys(r->b);
1416
1417 ret = btree_gc_coalesce(b, op, &keys, gc, r);
1418 if (ret)
1419 break;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001420 }
1421
Kent Overstreeta1f03582013-09-10 19:07:00 -07001422 if (!last->b)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001423 break;
Kent Overstreeta1f03582013-09-10 19:07:00 -07001424
1425 if (!IS_ERR(last->b)) {
1426 should_rewrite = btree_gc_mark_node(last->b, gc);
Kent Overstreet78365412013-12-17 01:29:34 -08001427 if (should_rewrite &&
1428 !btree_check_reserve(b, NULL)) {
Kent Overstreetbc9389e2013-09-10 19:07:35 -07001429 n = btree_node_alloc_replacement(last->b,
1430 false);
Kent Overstreeta1f03582013-09-10 19:07:00 -07001431
1432 if (!IS_ERR_OR_NULL(n)) {
1433 bch_btree_node_write_sync(n);
1434 bch_keylist_add(&keys, &n->key);
1435
1436 make_btree_freeing_key(last->b,
1437 keys.top);
1438 bch_keylist_push(&keys);
1439
1440 btree_node_free(last->b);
1441
1442 bch_btree_insert_node(b, op, &keys,
1443 NULL, NULL);
1444 BUG_ON(!bch_keylist_empty(&keys));
1445
1446 rw_unlock(true, last->b);
1447 last->b = n;
1448
1449 /* Invalidated our iterator */
1450 ret = -EINTR;
1451 break;
1452 }
1453 }
1454
1455 if (last->b->level) {
1456 ret = btree_gc_recurse(last->b, op, writes, gc);
1457 if (ret)
1458 break;
1459 }
1460
1461 bkey_copy_key(&b->c->gc_done, &last->b->key);
1462
1463 /*
1464 * Must flush leaf nodes before gc ends, since replace
1465 * operations aren't journalled
1466 */
1467 if (btree_node_dirty(last->b))
1468 bch_btree_node_write(last->b, writes);
1469 rw_unlock(true, last->b);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001470 }
1471
Kent Overstreeta1f03582013-09-10 19:07:00 -07001472 memmove(r + 1, r, sizeof(r[0]) * (GC_MERGE_NODES - 1));
1473 r->b = NULL;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001474
Kent Overstreetcafe5632013-03-23 16:11:31 -07001475 if (need_resched()) {
1476 ret = -EAGAIN;
1477 break;
1478 }
Kent Overstreetcafe5632013-03-23 16:11:31 -07001479 }
1480
Kent Overstreeta1f03582013-09-10 19:07:00 -07001481 for (i = 0; i < GC_MERGE_NODES; i++)
1482 if (!IS_ERR_OR_NULL(r[i].b)) {
1483 if (btree_node_dirty(r[i].b))
1484 bch_btree_node_write(r[i].b, writes);
1485 rw_unlock(true, r[i].b);
1486 }
Kent Overstreetcafe5632013-03-23 16:11:31 -07001487
Kent Overstreeta1f03582013-09-10 19:07:00 -07001488 bch_keylist_free(&keys);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001489
1490 return ret;
1491}
1492
1493static int bch_btree_gc_root(struct btree *b, struct btree_op *op,
1494 struct closure *writes, struct gc_stat *gc)
1495{
1496 struct btree *n = NULL;
Kent Overstreeta1f03582013-09-10 19:07:00 -07001497 int ret = 0;
1498 bool should_rewrite;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001499
Kent Overstreeta1f03582013-09-10 19:07:00 -07001500 should_rewrite = btree_gc_mark_node(b, gc);
1501 if (should_rewrite) {
Kent Overstreetbc9389e2013-09-10 19:07:35 -07001502 n = btree_node_alloc_replacement(b, false);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001503
Kent Overstreeta1f03582013-09-10 19:07:00 -07001504 if (!IS_ERR_OR_NULL(n)) {
1505 bch_btree_node_write_sync(n);
1506 bch_btree_set_root(n);
1507 btree_node_free(b);
1508 rw_unlock(true, n);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001509
Kent Overstreeta1f03582013-09-10 19:07:00 -07001510 return -EINTR;
1511 }
Kent Overstreetcafe5632013-03-23 16:11:31 -07001512 }
1513
Kent Overstreeta1f03582013-09-10 19:07:00 -07001514 if (b->level) {
1515 ret = btree_gc_recurse(b, op, writes, gc);
1516 if (ret)
1517 return ret;
1518 }
1519
1520 bkey_copy_key(&b->c->gc_done, &b->key);
1521
Kent Overstreetcafe5632013-03-23 16:11:31 -07001522 return ret;
1523}
1524
1525static void btree_gc_start(struct cache_set *c)
1526{
1527 struct cache *ca;
1528 struct bucket *b;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001529 unsigned i;
1530
1531 if (!c->gc_mark_valid)
1532 return;
1533
1534 mutex_lock(&c->bucket_lock);
1535
1536 c->gc_mark_valid = 0;
1537 c->gc_done = ZERO_KEY;
1538
1539 for_each_cache(ca, c, i)
1540 for_each_bucket(b, ca) {
1541 b->gc_gen = b->gen;
Kent Overstreet29ebf462013-07-11 19:43:21 -07001542 if (!atomic_read(&b->pin)) {
Kent Overstreetcafe5632013-03-23 16:11:31 -07001543 SET_GC_MARK(b, GC_MARK_RECLAIMABLE);
Kent Overstreet29ebf462013-07-11 19:43:21 -07001544 SET_GC_SECTORS_USED(b, 0);
1545 }
Kent Overstreetcafe5632013-03-23 16:11:31 -07001546 }
1547
Kent Overstreetcafe5632013-03-23 16:11:31 -07001548 mutex_unlock(&c->bucket_lock);
1549}
1550
1551size_t bch_btree_gc_finish(struct cache_set *c)
1552{
1553 size_t available = 0;
1554 struct bucket *b;
1555 struct cache *ca;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001556 unsigned i;
1557
1558 mutex_lock(&c->bucket_lock);
1559
1560 set_gc_sectors(c);
1561 c->gc_mark_valid = 1;
1562 c->need_gc = 0;
1563
1564 if (c->root)
1565 for (i = 0; i < KEY_PTRS(&c->root->key); i++)
1566 SET_GC_MARK(PTR_BUCKET(c, &c->root->key, i),
1567 GC_MARK_METADATA);
1568
1569 for (i = 0; i < KEY_PTRS(&c->uuid_bucket); i++)
1570 SET_GC_MARK(PTR_BUCKET(c, &c->uuid_bucket, i),
1571 GC_MARK_METADATA);
1572
Nicholas Swensonbf0a6282013-11-26 19:14:23 -08001573 /* don't reclaim buckets to which writeback keys point */
1574 rcu_read_lock();
1575 for (i = 0; i < c->nr_uuids; i++) {
1576 struct bcache_device *d = c->devices[i];
1577 struct cached_dev *dc;
1578 struct keybuf_key *w, *n;
1579 unsigned j;
1580
1581 if (!d || UUID_FLASH_ONLY(&c->uuids[i]))
1582 continue;
1583 dc = container_of(d, struct cached_dev, disk);
1584
1585 spin_lock(&dc->writeback_keys.lock);
1586 rbtree_postorder_for_each_entry_safe(w, n,
1587 &dc->writeback_keys.keys, node)
1588 for (j = 0; j < KEY_PTRS(&w->key); j++)
1589 SET_GC_MARK(PTR_BUCKET(c, &w->key, j),
1590 GC_MARK_DIRTY);
1591 spin_unlock(&dc->writeback_keys.lock);
1592 }
1593 rcu_read_unlock();
1594
Kent Overstreetcafe5632013-03-23 16:11:31 -07001595 for_each_cache(ca, c, i) {
1596 uint64_t *i;
1597
1598 ca->invalidate_needs_gc = 0;
1599
1600 for (i = ca->sb.d; i < ca->sb.d + ca->sb.keys; i++)
1601 SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA);
1602
1603 for (i = ca->prio_buckets;
1604 i < ca->prio_buckets + prio_buckets(ca) * 2; i++)
1605 SET_GC_MARK(ca->buckets + *i, GC_MARK_METADATA);
1606
1607 for_each_bucket(b, ca) {
1608 b->last_gc = b->gc_gen;
1609 c->need_gc = max(c->need_gc, bucket_gc_gen(b));
1610
1611 if (!atomic_read(&b->pin) &&
1612 GC_MARK(b) == GC_MARK_RECLAIMABLE) {
1613 available++;
1614 if (!GC_SECTORS_USED(b))
1615 bch_bucket_add_unused(ca, b);
1616 }
1617 }
1618 }
1619
Kent Overstreetcafe5632013-03-23 16:11:31 -07001620 mutex_unlock(&c->bucket_lock);
1621 return available;
1622}
1623
Kent Overstreet72a44512013-10-24 17:19:26 -07001624static void bch_btree_gc(struct cache_set *c)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001625{
Kent Overstreetcafe5632013-03-23 16:11:31 -07001626 int ret;
1627 unsigned long available;
1628 struct gc_stat stats;
1629 struct closure writes;
1630 struct btree_op op;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001631 uint64_t start_time = local_clock();
Kent Overstreet57943512013-04-25 13:58:35 -07001632
Kent Overstreetc37511b2013-04-26 15:39:55 -07001633 trace_bcache_gc_start(c);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001634
1635 memset(&stats, 0, sizeof(struct gc_stat));
1636 closure_init_stack(&writes);
Kent Overstreetb54d6932013-07-24 18:04:18 -07001637 bch_btree_op_init(&op, SHRT_MAX);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001638
1639 btree_gc_start(c);
1640
Kent Overstreeta1f03582013-09-10 19:07:00 -07001641 do {
1642 ret = btree_root(gc_root, c, &op, &writes, &stats);
1643 closure_sync(&writes);
Kent Overstreet57943512013-04-25 13:58:35 -07001644
Kent Overstreeta1f03582013-09-10 19:07:00 -07001645 if (ret && ret != -EAGAIN)
1646 pr_warn("gc failed!");
1647 } while (ret);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001648
1649 available = bch_btree_gc_finish(c);
Kent Overstreet57943512013-04-25 13:58:35 -07001650 wake_up_allocators(c);
1651
Kent Overstreet169ef1c2013-03-28 12:50:55 -06001652 bch_time_stats_update(&c->btree_gc_time, start_time);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001653
1654 stats.key_bytes *= sizeof(uint64_t);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001655 stats.data <<= 9;
1656 stats.in_use = (c->nbuckets - available) * 100 / c->nbuckets;
1657 memcpy(&c->gc_stats, &stats, sizeof(struct gc_stat));
Kent Overstreetcafe5632013-03-23 16:11:31 -07001658
Kent Overstreetc37511b2013-04-26 15:39:55 -07001659 trace_bcache_gc_end(c);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001660
Kent Overstreet72a44512013-10-24 17:19:26 -07001661 bch_moving_gc(c);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001662}
1663
Kent Overstreet72a44512013-10-24 17:19:26 -07001664static int bch_gc_thread(void *arg)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001665{
Kent Overstreet72a44512013-10-24 17:19:26 -07001666 struct cache_set *c = arg;
Kent Overstreeta1f03582013-09-10 19:07:00 -07001667 struct cache *ca;
1668 unsigned i;
Kent Overstreet72a44512013-10-24 17:19:26 -07001669
1670 while (1) {
Kent Overstreeta1f03582013-09-10 19:07:00 -07001671again:
Kent Overstreet72a44512013-10-24 17:19:26 -07001672 bch_btree_gc(c);
1673
1674 set_current_state(TASK_INTERRUPTIBLE);
1675 if (kthread_should_stop())
1676 break;
1677
Kent Overstreeta1f03582013-09-10 19:07:00 -07001678 mutex_lock(&c->bucket_lock);
1679
1680 for_each_cache(ca, c, i)
1681 if (ca->invalidate_needs_gc) {
1682 mutex_unlock(&c->bucket_lock);
1683 set_current_state(TASK_RUNNING);
1684 goto again;
1685 }
1686
1687 mutex_unlock(&c->bucket_lock);
1688
Kent Overstreet72a44512013-10-24 17:19:26 -07001689 try_to_freeze();
1690 schedule();
1691 }
1692
1693 return 0;
1694}
1695
1696int bch_gc_thread_start(struct cache_set *c)
1697{
1698 c->gc_thread = kthread_create(bch_gc_thread, c, "bcache_gc");
1699 if (IS_ERR(c->gc_thread))
1700 return PTR_ERR(c->gc_thread);
1701
1702 set_task_state(c->gc_thread, TASK_INTERRUPTIBLE);
1703 return 0;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001704}
1705
1706/* Initial partial gc */
1707
1708static int bch_btree_check_recurse(struct btree *b, struct btree_op *op,
1709 unsigned long **seen)
1710{
Kent Overstreet50310162013-09-10 17:18:59 -07001711 int ret = 0;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001712 unsigned i;
Kent Overstreet50310162013-09-10 17:18:59 -07001713 struct bkey *k, *p = NULL;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001714 struct bucket *g;
1715 struct btree_iter iter;
1716
Kent Overstreetc052dd92013-11-11 17:35:24 -08001717 for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) {
Kent Overstreetcafe5632013-03-23 16:11:31 -07001718 for (i = 0; i < KEY_PTRS(k); i++) {
1719 if (!ptr_available(b->c, k, i))
1720 continue;
1721
1722 g = PTR_BUCKET(b->c, k, i);
1723
1724 if (!__test_and_set_bit(PTR_BUCKET_NR(b->c, k, i),
1725 seen[PTR_DEV(k, i)]) ||
1726 !ptr_stale(b->c, k, i)) {
1727 g->gen = PTR_GEN(k, i);
1728
1729 if (b->level)
1730 g->prio = BTREE_PRIO;
1731 else if (g->prio == BTREE_PRIO)
1732 g->prio = INITIAL_PRIO;
1733 }
1734 }
1735
1736 btree_mark_key(b, k);
1737 }
1738
1739 if (b->level) {
Kent Overstreetc052dd92013-11-11 17:35:24 -08001740 bch_btree_iter_init(&b->keys, &iter, NULL);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001741
Kent Overstreet50310162013-09-10 17:18:59 -07001742 do {
Kent Overstreeta85e9682013-12-20 17:28:16 -08001743 k = bch_btree_iter_next_filter(&iter, &b->keys,
1744 bch_ptr_bad);
Kent Overstreet50310162013-09-10 17:18:59 -07001745 if (k)
1746 btree_node_prefetch(b->c, k, b->level - 1);
1747
Kent Overstreetcafe5632013-03-23 16:11:31 -07001748 if (p)
Kent Overstreet50310162013-09-10 17:18:59 -07001749 ret = btree(check_recurse, p, b, op, seen);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001750
Kent Overstreet50310162013-09-10 17:18:59 -07001751 p = k;
1752 } while (p && !ret);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001753 }
1754
1755 return 0;
1756}
1757
Kent Overstreetc18536a2013-07-24 17:44:17 -07001758int bch_btree_check(struct cache_set *c)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001759{
1760 int ret = -ENOMEM;
1761 unsigned i;
1762 unsigned long *seen[MAX_CACHES_PER_SET];
Kent Overstreetc18536a2013-07-24 17:44:17 -07001763 struct btree_op op;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001764
1765 memset(seen, 0, sizeof(seen));
Kent Overstreetb54d6932013-07-24 18:04:18 -07001766 bch_btree_op_init(&op, SHRT_MAX);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001767
1768 for (i = 0; c->cache[i]; i++) {
1769 size_t n = DIV_ROUND_UP(c->cache[i]->sb.nbuckets, 8);
1770 seen[i] = kmalloc(n, GFP_KERNEL);
1771 if (!seen[i])
1772 goto err;
1773
1774 /* Disables the seen array until prio_read() uses it too */
1775 memset(seen[i], 0xFF, n);
1776 }
1777
Kent Overstreetc18536a2013-07-24 17:44:17 -07001778 ret = btree_root(check_recurse, c, &op, seen);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001779err:
1780 for (i = 0; i < MAX_CACHES_PER_SET; i++)
1781 kfree(seen[i]);
1782 return ret;
1783}
1784
1785/* Btree insertion */
1786
Kent Overstreet829a60b2013-11-11 17:02:31 -08001787static bool btree_insert_key(struct btree *b, struct bkey *k,
1788 struct bkey *replace_key)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001789{
Kent Overstreet829a60b2013-11-11 17:02:31 -08001790 unsigned status;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001791
1792 BUG_ON(bkey_cmp(k, &b->key) > 0);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001793
Kent Overstreet829a60b2013-11-11 17:02:31 -08001794 status = bch_btree_insert_key(&b->keys, k, replace_key);
1795 if (status != BTREE_INSERT_STATUS_NO_INSERT) {
1796 bch_check_keys(&b->keys, "%u for %s", status,
1797 replace_key ? "replace" : "insert");
Kent Overstreetcafe5632013-03-23 16:11:31 -07001798
Kent Overstreet829a60b2013-11-11 17:02:31 -08001799 trace_bcache_btree_insert_key(b, k, replace_key != NULL,
1800 status);
1801 return true;
1802 } else
1803 return false;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001804}
1805
Kent Overstreet59158fd2013-11-11 19:03:54 -08001806static size_t insert_u64s_remaining(struct btree *b)
1807{
1808 ssize_t ret = bch_btree_keys_u64s_remaining(&b->keys);
1809
1810 /*
1811 * Might land in the middle of an existing extent and have to split it
1812 */
1813 if (b->keys.ops->is_extents)
1814 ret -= KEY_MAX_U64S;
1815
1816 return max(ret, 0L);
1817}
1818
Kent Overstreet26c949f2013-09-10 18:41:15 -07001819static bool bch_btree_insert_keys(struct btree *b, struct btree_op *op,
Kent Overstreet1b207d82013-09-10 18:52:54 -07001820 struct keylist *insert_keys,
1821 struct bkey *replace_key)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001822{
1823 bool ret = false;
Kent Overstreetdc9d98d2013-12-17 23:47:33 -08001824 int oldsize = bch_count_data(&b->keys);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001825
Kent Overstreet26c949f2013-09-10 18:41:15 -07001826 while (!bch_keylist_empty(insert_keys)) {
Kent Overstreetc2f95ae2013-07-24 17:24:25 -07001827 struct bkey *k = insert_keys->keys;
Kent Overstreet26c949f2013-09-10 18:41:15 -07001828
Kent Overstreet59158fd2013-11-11 19:03:54 -08001829 if (bkey_u64s(k) > insert_u64s_remaining(b))
Kent Overstreet403b6cd2013-07-24 17:22:44 -07001830 break;
1831
1832 if (bkey_cmp(k, &b->key) <= 0) {
Kent Overstreet3a3b6a42013-07-24 16:46:42 -07001833 if (!b->level)
1834 bkey_put(b->c, k);
Kent Overstreet26c949f2013-09-10 18:41:15 -07001835
Kent Overstreet829a60b2013-11-11 17:02:31 -08001836 ret |= btree_insert_key(b, k, replace_key);
Kent Overstreet26c949f2013-09-10 18:41:15 -07001837 bch_keylist_pop_front(insert_keys);
1838 } else if (bkey_cmp(&START_KEY(k), &b->key) < 0) {
Kent Overstreet26c949f2013-09-10 18:41:15 -07001839 BKEY_PADDED(key) temp;
Kent Overstreetc2f95ae2013-07-24 17:24:25 -07001840 bkey_copy(&temp.key, insert_keys->keys);
Kent Overstreet26c949f2013-09-10 18:41:15 -07001841
1842 bch_cut_back(&b->key, &temp.key);
Kent Overstreetc2f95ae2013-07-24 17:24:25 -07001843 bch_cut_front(&b->key, insert_keys->keys);
Kent Overstreet26c949f2013-09-10 18:41:15 -07001844
Kent Overstreet829a60b2013-11-11 17:02:31 -08001845 ret |= btree_insert_key(b, &temp.key, replace_key);
Kent Overstreet26c949f2013-09-10 18:41:15 -07001846 break;
1847 } else {
1848 break;
1849 }
Kent Overstreetcafe5632013-03-23 16:11:31 -07001850 }
1851
Kent Overstreet829a60b2013-11-11 17:02:31 -08001852 if (!ret)
1853 op->insert_collision = true;
1854
Kent Overstreet403b6cd2013-07-24 17:22:44 -07001855 BUG_ON(!bch_keylist_empty(insert_keys) && b->level);
1856
Kent Overstreetdc9d98d2013-12-17 23:47:33 -08001857 BUG_ON(bch_count_data(&b->keys) < oldsize);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001858 return ret;
1859}
1860
Kent Overstreet26c949f2013-09-10 18:41:15 -07001861static int btree_split(struct btree *b, struct btree_op *op,
1862 struct keylist *insert_keys,
Kent Overstreet1b207d82013-09-10 18:52:54 -07001863 struct bkey *replace_key)
Kent Overstreetcafe5632013-03-23 16:11:31 -07001864{
Kent Overstreetd6fd3b12013-07-24 17:20:19 -07001865 bool split;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001866 struct btree *n1, *n2 = NULL, *n3 = NULL;
1867 uint64_t start_time = local_clock();
Kent Overstreetb54d6932013-07-24 18:04:18 -07001868 struct closure cl;
Kent Overstreet17e21a92013-07-26 12:32:38 -07001869 struct keylist parent_keys;
Kent Overstreetb54d6932013-07-24 18:04:18 -07001870
1871 closure_init_stack(&cl);
Kent Overstreet17e21a92013-07-26 12:32:38 -07001872 bch_keylist_init(&parent_keys);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001873
Kent Overstreet78365412013-12-17 01:29:34 -08001874 if (!b->level &&
1875 btree_check_reserve(b, op))
1876 return -EINTR;
1877
Kent Overstreetbc9389e2013-09-10 19:07:35 -07001878 n1 = btree_node_alloc_replacement(b, true);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001879 if (IS_ERR(n1))
1880 goto err;
1881
Kent Overstreetee811282013-12-17 23:49:49 -08001882 split = set_blocks(btree_bset_first(n1),
1883 block_bytes(n1->c)) > (btree_blocks(b) * 4) / 5;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001884
Kent Overstreetcafe5632013-03-23 16:11:31 -07001885 if (split) {
1886 unsigned keys = 0;
1887
Kent Overstreetee811282013-12-17 23:49:49 -08001888 trace_bcache_btree_node_split(b, btree_bset_first(n1)->keys);
Kent Overstreetc37511b2013-04-26 15:39:55 -07001889
Kent Overstreetbc9389e2013-09-10 19:07:35 -07001890 n2 = bch_btree_node_alloc(b->c, b->level, true);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001891 if (IS_ERR(n2))
1892 goto err_free1;
1893
Kent Overstreetd6fd3b12013-07-24 17:20:19 -07001894 if (!b->parent) {
Kent Overstreetbc9389e2013-09-10 19:07:35 -07001895 n3 = bch_btree_node_alloc(b->c, b->level + 1, true);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001896 if (IS_ERR(n3))
1897 goto err_free2;
1898 }
1899
Kent Overstreet1b207d82013-09-10 18:52:54 -07001900 bch_btree_insert_keys(n1, op, insert_keys, replace_key);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001901
Kent Overstreetd6fd3b12013-07-24 17:20:19 -07001902 /*
1903 * Has to be a linear search because we don't have an auxiliary
Kent Overstreetcafe5632013-03-23 16:11:31 -07001904 * search tree yet
1905 */
1906
Kent Overstreetee811282013-12-17 23:49:49 -08001907 while (keys < (btree_bset_first(n1)->keys * 3) / 5)
1908 keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1),
Kent Overstreetfafff812013-12-17 21:56:21 -08001909 keys));
Kent Overstreetcafe5632013-03-23 16:11:31 -07001910
Kent Overstreetfafff812013-12-17 21:56:21 -08001911 bkey_copy_key(&n1->key,
Kent Overstreetee811282013-12-17 23:49:49 -08001912 bset_bkey_idx(btree_bset_first(n1), keys));
1913 keys += bkey_u64s(bset_bkey_idx(btree_bset_first(n1), keys));
Kent Overstreetcafe5632013-03-23 16:11:31 -07001914
Kent Overstreetee811282013-12-17 23:49:49 -08001915 btree_bset_first(n2)->keys = btree_bset_first(n1)->keys - keys;
1916 btree_bset_first(n1)->keys = keys;
Kent Overstreetcafe5632013-03-23 16:11:31 -07001917
Kent Overstreetee811282013-12-17 23:49:49 -08001918 memcpy(btree_bset_first(n2)->start,
1919 bset_bkey_last(btree_bset_first(n1)),
1920 btree_bset_first(n2)->keys * sizeof(uint64_t));
Kent Overstreetcafe5632013-03-23 16:11:31 -07001921
1922 bkey_copy_key(&n2->key, &b->key);
1923
Kent Overstreet17e21a92013-07-26 12:32:38 -07001924 bch_keylist_add(&parent_keys, &n2->key);
Kent Overstreetb54d6932013-07-24 18:04:18 -07001925 bch_btree_node_write(n2, &cl);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001926 rw_unlock(true, n2);
Kent Overstreetc37511b2013-04-26 15:39:55 -07001927 } else {
Kent Overstreetee811282013-12-17 23:49:49 -08001928 trace_bcache_btree_node_compact(b, btree_bset_first(n1)->keys);
Kent Overstreetc37511b2013-04-26 15:39:55 -07001929
Kent Overstreet1b207d82013-09-10 18:52:54 -07001930 bch_btree_insert_keys(n1, op, insert_keys, replace_key);
Kent Overstreetc37511b2013-04-26 15:39:55 -07001931 }
Kent Overstreetcafe5632013-03-23 16:11:31 -07001932
Kent Overstreet17e21a92013-07-26 12:32:38 -07001933 bch_keylist_add(&parent_keys, &n1->key);
Kent Overstreetb54d6932013-07-24 18:04:18 -07001934 bch_btree_node_write(n1, &cl);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001935
1936 if (n3) {
Kent Overstreetd6fd3b12013-07-24 17:20:19 -07001937 /* Depth increases, make a new root */
Kent Overstreetcafe5632013-03-23 16:11:31 -07001938 bkey_copy_key(&n3->key, &MAX_KEY);
Kent Overstreet17e21a92013-07-26 12:32:38 -07001939 bch_btree_insert_keys(n3, op, &parent_keys, NULL);
Kent Overstreetb54d6932013-07-24 18:04:18 -07001940 bch_btree_node_write(n3, &cl);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001941
Kent Overstreetb54d6932013-07-24 18:04:18 -07001942 closure_sync(&cl);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001943 bch_btree_set_root(n3);
1944 rw_unlock(true, n3);
Kent Overstreet17e21a92013-07-26 12:32:38 -07001945
1946 btree_node_free(b);
Kent Overstreetd6fd3b12013-07-24 17:20:19 -07001947 } else if (!b->parent) {
1948 /* Root filled up but didn't need to be split */
Kent Overstreetb54d6932013-07-24 18:04:18 -07001949 closure_sync(&cl);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001950 bch_btree_set_root(n1);
Kent Overstreet17e21a92013-07-26 12:32:38 -07001951
1952 btree_node_free(b);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001953 } else {
Kent Overstreet17e21a92013-07-26 12:32:38 -07001954 /* Split a non root node */
Kent Overstreetb54d6932013-07-24 18:04:18 -07001955 closure_sync(&cl);
Kent Overstreet17e21a92013-07-26 12:32:38 -07001956 make_btree_freeing_key(b, parent_keys.top);
1957 bch_keylist_push(&parent_keys);
1958
1959 btree_node_free(b);
1960
1961 bch_btree_insert_node(b->parent, op, &parent_keys, NULL, NULL);
1962 BUG_ON(!bch_keylist_empty(&parent_keys));
Kent Overstreetcafe5632013-03-23 16:11:31 -07001963 }
1964
1965 rw_unlock(true, n1);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001966
Kent Overstreet169ef1c2013-03-28 12:50:55 -06001967 bch_time_stats_update(&b->c->btree_split_time, start_time);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001968
1969 return 0;
1970err_free2:
Kent Overstreet5f5837d2013-12-16 16:38:49 -08001971 bkey_put(b->c, &n2->key);
Kent Overstreete8e1d462013-07-24 17:27:07 -07001972 btree_node_free(n2);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001973 rw_unlock(true, n2);
1974err_free1:
Kent Overstreet5f5837d2013-12-16 16:38:49 -08001975 bkey_put(b->c, &n1->key);
Kent Overstreete8e1d462013-07-24 17:27:07 -07001976 btree_node_free(n1);
Kent Overstreetcafe5632013-03-23 16:11:31 -07001977 rw_unlock(true, n1);
1978err:
Kent Overstreet5f5837d2013-12-16 16:38:49 -08001979 WARN(1, "bcache: btree split failed");
1980
Kent Overstreetcafe5632013-03-23 16:11:31 -07001981 if (n3 == ERR_PTR(-EAGAIN) ||
1982 n2 == ERR_PTR(-EAGAIN) ||
1983 n1 == ERR_PTR(-EAGAIN))
1984 return -EAGAIN;
1985
Kent Overstreetcafe5632013-03-23 16:11:31 -07001986 return -ENOMEM;
1987}
1988
Kent Overstreet26c949f2013-09-10 18:41:15 -07001989static int bch_btree_insert_node(struct btree *b, struct btree_op *op,
Kent Overstreetc18536a2013-07-24 17:44:17 -07001990 struct keylist *insert_keys,
Kent Overstreet1b207d82013-09-10 18:52:54 -07001991 atomic_t *journal_ref,
1992 struct bkey *replace_key)
Kent Overstreet26c949f2013-09-10 18:41:15 -07001993{
Kent Overstreet17e21a92013-07-26 12:32:38 -07001994 BUG_ON(b->level && replace_key);
Kent Overstreet26c949f2013-09-10 18:41:15 -07001995
Kent Overstreet59158fd2013-11-11 19:03:54 -08001996 if (bch_keylist_nkeys(insert_keys) > insert_u64s_remaining(b)) {
Kent Overstreet17e21a92013-07-26 12:32:38 -07001997 if (current->bio_list) {
1998 op->lock = b->c->root->level + 1;
1999 return -EAGAIN;
2000 } else if (op->lock <= b->c->root->level) {
2001 op->lock = b->c->root->level + 1;
2002 return -EINTR;
Kent Overstreet26c949f2013-09-10 18:41:15 -07002003 } else {
Kent Overstreet17e21a92013-07-26 12:32:38 -07002004 /* Invalidated all iterators */
2005 return btree_split(b, op, insert_keys, replace_key) ?:
2006 -EINTR;
Kent Overstreet26c949f2013-09-10 18:41:15 -07002007 }
Kent Overstreet17e21a92013-07-26 12:32:38 -07002008 } else {
Kent Overstreetee811282013-12-17 23:49:49 -08002009 BUG_ON(write_block(b) != btree_bset_last(b));
Kent Overstreet26c949f2013-09-10 18:41:15 -07002010
Kent Overstreet17e21a92013-07-26 12:32:38 -07002011 if (bch_btree_insert_keys(b, op, insert_keys, replace_key)) {
2012 if (!b->level)
2013 bch_btree_leaf_dirty(b, journal_ref);
2014 else
2015 bch_btree_node_write_sync(b);
2016 }
2017
2018 return 0;
2019 }
Kent Overstreet26c949f2013-09-10 18:41:15 -07002020}
2021
Kent Overstreete7c590e2013-09-10 18:39:16 -07002022int bch_btree_insert_check_key(struct btree *b, struct btree_op *op,
2023 struct bkey *check_key)
2024{
2025 int ret = -EINTR;
2026 uint64_t btree_ptr = b->key.ptr[0];
2027 unsigned long seq = b->seq;
2028 struct keylist insert;
2029 bool upgrade = op->lock == -1;
2030
2031 bch_keylist_init(&insert);
2032
2033 if (upgrade) {
2034 rw_unlock(false, b);
2035 rw_lock(true, b, b->level);
2036
2037 if (b->key.ptr[0] != btree_ptr ||
2038 b->seq != seq + 1)
2039 goto out;
2040 }
2041
2042 SET_KEY_PTRS(check_key, 1);
2043 get_random_bytes(&check_key->ptr[0], sizeof(uint64_t));
2044
2045 SET_PTR_DEV(check_key, 0, PTR_CHECK_DEV);
2046
2047 bch_keylist_add(&insert, check_key);
2048
Kent Overstreet1b207d82013-09-10 18:52:54 -07002049 ret = bch_btree_insert_node(b, op, &insert, NULL, NULL);
Kent Overstreete7c590e2013-09-10 18:39:16 -07002050
2051 BUG_ON(!ret && !bch_keylist_empty(&insert));
2052out:
2053 if (upgrade)
2054 downgrade_write(&b->lock);
2055 return ret;
2056}
2057
Kent Overstreetcc7b8812013-07-24 18:07:22 -07002058struct btree_insert_op {
2059 struct btree_op op;
2060 struct keylist *keys;
2061 atomic_t *journal_ref;
2062 struct bkey *replace_key;
2063};
2064
Wei Yongjun08239ca2013-11-28 10:31:35 +08002065static int btree_insert_fn(struct btree_op *b_op, struct btree *b)
Kent Overstreetcafe5632013-03-23 16:11:31 -07002066{
Kent Overstreetcc7b8812013-07-24 18:07:22 -07002067 struct btree_insert_op *op = container_of(b_op,
2068 struct btree_insert_op, op);
Kent Overstreet403b6cd2013-07-24 17:22:44 -07002069
Kent Overstreetcc7b8812013-07-24 18:07:22 -07002070 int ret = bch_btree_insert_node(b, &op->op, op->keys,
2071 op->journal_ref, op->replace_key);
2072 if (ret && !bch_keylist_empty(op->keys))
2073 return ret;
2074 else
2075 return MAP_DONE;
Kent Overstreetcafe5632013-03-23 16:11:31 -07002076}
2077
Kent Overstreetcc7b8812013-07-24 18:07:22 -07002078int bch_btree_insert(struct cache_set *c, struct keylist *keys,
2079 atomic_t *journal_ref, struct bkey *replace_key)
Kent Overstreetcafe5632013-03-23 16:11:31 -07002080{
Kent Overstreetcc7b8812013-07-24 18:07:22 -07002081 struct btree_insert_op op;
Kent Overstreetcafe5632013-03-23 16:11:31 -07002082 int ret = 0;
Kent Overstreetcafe5632013-03-23 16:11:31 -07002083
Kent Overstreetcc7b8812013-07-24 18:07:22 -07002084 BUG_ON(current->bio_list);
Kent Overstreet4f3d4012013-09-10 18:46:36 -07002085 BUG_ON(bch_keylist_empty(keys));
Kent Overstreetcafe5632013-03-23 16:11:31 -07002086
Kent Overstreetcc7b8812013-07-24 18:07:22 -07002087 bch_btree_op_init(&op.op, 0);
2088 op.keys = keys;
2089 op.journal_ref = journal_ref;
2090 op.replace_key = replace_key;
Kent Overstreetcafe5632013-03-23 16:11:31 -07002091
Kent Overstreetcc7b8812013-07-24 18:07:22 -07002092 while (!ret && !bch_keylist_empty(keys)) {
2093 op.op.lock = 0;
2094 ret = bch_btree_map_leaf_nodes(&op.op, c,
2095 &START_KEY(keys->keys),
2096 btree_insert_fn);
Kent Overstreetcafe5632013-03-23 16:11:31 -07002097 }
2098
Kent Overstreetcc7b8812013-07-24 18:07:22 -07002099 if (ret) {
2100 struct bkey *k;
2101
2102 pr_err("error %i", ret);
2103
2104 while ((k = bch_keylist_pop(keys)))
Kent Overstreet3a3b6a42013-07-24 16:46:42 -07002105 bkey_put(c, k);
Kent Overstreetcc7b8812013-07-24 18:07:22 -07002106 } else if (op.op.insert_collision)
2107 ret = -ESRCH;
Kent Overstreet6054c6d2013-07-24 18:06:22 -07002108
Kent Overstreetcafe5632013-03-23 16:11:31 -07002109 return ret;
2110}
2111
2112void bch_btree_set_root(struct btree *b)
2113{
2114 unsigned i;
Kent Overstreete49c7c32013-06-26 17:25:38 -07002115 struct closure cl;
2116
2117 closure_init_stack(&cl);
Kent Overstreetcafe5632013-03-23 16:11:31 -07002118
Kent Overstreetc37511b2013-04-26 15:39:55 -07002119 trace_bcache_btree_set_root(b);
2120
Kent Overstreetcafe5632013-03-23 16:11:31 -07002121 BUG_ON(!b->written);
2122
2123 for (i = 0; i < KEY_PTRS(&b->key); i++)
2124 BUG_ON(PTR_BUCKET(b->c, &b->key, i)->prio != BTREE_PRIO);
2125
2126 mutex_lock(&b->c->bucket_lock);
2127 list_del_init(&b->list);
2128 mutex_unlock(&b->c->bucket_lock);
2129
2130 b->c->root = b;
Kent Overstreetcafe5632013-03-23 16:11:31 -07002131
Kent Overstreete49c7c32013-06-26 17:25:38 -07002132 bch_journal_meta(b->c, &cl);
2133 closure_sync(&cl);
Kent Overstreetcafe5632013-03-23 16:11:31 -07002134}
2135
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002136/* Map across nodes or keys */
2137
2138static int bch_btree_map_nodes_recurse(struct btree *b, struct btree_op *op,
2139 struct bkey *from,
2140 btree_map_nodes_fn *fn, int flags)
2141{
2142 int ret = MAP_CONTINUE;
2143
2144 if (b->level) {
2145 struct bkey *k;
2146 struct btree_iter iter;
2147
Kent Overstreetc052dd92013-11-11 17:35:24 -08002148 bch_btree_iter_init(&b->keys, &iter, from);
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002149
Kent Overstreeta85e9682013-12-20 17:28:16 -08002150 while ((k = bch_btree_iter_next_filter(&iter, &b->keys,
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002151 bch_ptr_bad))) {
2152 ret = btree(map_nodes_recurse, k, b,
2153 op, from, fn, flags);
2154 from = NULL;
2155
2156 if (ret != MAP_CONTINUE)
2157 return ret;
2158 }
2159 }
2160
2161 if (!b->level || flags == MAP_ALL_NODES)
2162 ret = fn(op, b);
2163
2164 return ret;
2165}
2166
2167int __bch_btree_map_nodes(struct btree_op *op, struct cache_set *c,
2168 struct bkey *from, btree_map_nodes_fn *fn, int flags)
2169{
Kent Overstreetb54d6932013-07-24 18:04:18 -07002170 return btree_root(map_nodes_recurse, c, op, from, fn, flags);
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002171}
2172
2173static int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op,
2174 struct bkey *from, btree_map_keys_fn *fn,
2175 int flags)
2176{
2177 int ret = MAP_CONTINUE;
2178 struct bkey *k;
2179 struct btree_iter iter;
2180
Kent Overstreetc052dd92013-11-11 17:35:24 -08002181 bch_btree_iter_init(&b->keys, &iter, from);
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002182
Kent Overstreeta85e9682013-12-20 17:28:16 -08002183 while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) {
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002184 ret = !b->level
2185 ? fn(op, b, k)
2186 : btree(map_keys_recurse, k, b, op, from, fn, flags);
2187 from = NULL;
2188
2189 if (ret != MAP_CONTINUE)
2190 return ret;
2191 }
2192
2193 if (!b->level && (flags & MAP_END_KEY))
2194 ret = fn(op, b, &KEY(KEY_INODE(&b->key),
2195 KEY_OFFSET(&b->key), 0));
2196
2197 return ret;
2198}
2199
2200int bch_btree_map_keys(struct btree_op *op, struct cache_set *c,
2201 struct bkey *from, btree_map_keys_fn *fn, int flags)
2202{
Kent Overstreetb54d6932013-07-24 18:04:18 -07002203 return btree_root(map_keys_recurse, c, op, from, fn, flags);
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002204}
2205
Kent Overstreetcafe5632013-03-23 16:11:31 -07002206/* Keybuf code */
2207
2208static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r)
2209{
2210 /* Overlapping keys compare equal */
2211 if (bkey_cmp(&l->key, &START_KEY(&r->key)) <= 0)
2212 return -1;
2213 if (bkey_cmp(&START_KEY(&l->key), &r->key) >= 0)
2214 return 1;
2215 return 0;
2216}
2217
2218static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l,
2219 struct keybuf_key *r)
2220{
2221 return clamp_t(int64_t, bkey_cmp(&l->key, &r->key), -1, 1);
2222}
2223
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002224struct refill {
2225 struct btree_op op;
Kent Overstreet48a915a2013-10-31 15:43:22 -07002226 unsigned nr_found;
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002227 struct keybuf *buf;
2228 struct bkey *end;
2229 keybuf_pred_fn *pred;
2230};
2231
2232static int refill_keybuf_fn(struct btree_op *op, struct btree *b,
2233 struct bkey *k)
Kent Overstreetcafe5632013-03-23 16:11:31 -07002234{
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002235 struct refill *refill = container_of(op, struct refill, op);
2236 struct keybuf *buf = refill->buf;
2237 int ret = MAP_CONTINUE;
Kent Overstreetcafe5632013-03-23 16:11:31 -07002238
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002239 if (bkey_cmp(k, refill->end) >= 0) {
2240 ret = MAP_DONE;
2241 goto out;
Kent Overstreetcafe5632013-03-23 16:11:31 -07002242 }
2243
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002244 if (!KEY_SIZE(k)) /* end key */
2245 goto out;
2246
2247 if (refill->pred(buf, k)) {
2248 struct keybuf_key *w;
2249
2250 spin_lock(&buf->lock);
2251
2252 w = array_alloc(&buf->freelist);
2253 if (!w) {
2254 spin_unlock(&buf->lock);
2255 return MAP_DONE;
2256 }
2257
2258 w->private = NULL;
2259 bkey_copy(&w->key, k);
2260
2261 if (RB_INSERT(&buf->keys, w, node, keybuf_cmp))
2262 array_free(&buf->freelist, w);
Kent Overstreet48a915a2013-10-31 15:43:22 -07002263 else
2264 refill->nr_found++;
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002265
2266 if (array_freelist_empty(&buf->freelist))
2267 ret = MAP_DONE;
2268
2269 spin_unlock(&buf->lock);
2270 }
2271out:
2272 buf->last_scanned = *k;
2273 return ret;
Kent Overstreetcafe5632013-03-23 16:11:31 -07002274}
2275
2276void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf,
Kent Overstreet72c27062013-06-05 06:24:39 -07002277 struct bkey *end, keybuf_pred_fn *pred)
Kent Overstreetcafe5632013-03-23 16:11:31 -07002278{
2279 struct bkey start = buf->last_scanned;
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002280 struct refill refill;
Kent Overstreetcafe5632013-03-23 16:11:31 -07002281
2282 cond_resched();
2283
Kent Overstreetb54d6932013-07-24 18:04:18 -07002284 bch_btree_op_init(&refill.op, -1);
Kent Overstreet48a915a2013-10-31 15:43:22 -07002285 refill.nr_found = 0;
2286 refill.buf = buf;
2287 refill.end = end;
2288 refill.pred = pred;
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002289
2290 bch_btree_map_keys(&refill.op, c, &buf->last_scanned,
2291 refill_keybuf_fn, MAP_END_KEY);
Kent Overstreetcafe5632013-03-23 16:11:31 -07002292
Kent Overstreet48a915a2013-10-31 15:43:22 -07002293 trace_bcache_keyscan(refill.nr_found,
2294 KEY_INODE(&start), KEY_OFFSET(&start),
2295 KEY_INODE(&buf->last_scanned),
2296 KEY_OFFSET(&buf->last_scanned));
Kent Overstreetcafe5632013-03-23 16:11:31 -07002297
2298 spin_lock(&buf->lock);
2299
2300 if (!RB_EMPTY_ROOT(&buf->keys)) {
2301 struct keybuf_key *w;
2302 w = RB_FIRST(&buf->keys, struct keybuf_key, node);
2303 buf->start = START_KEY(&w->key);
2304
2305 w = RB_LAST(&buf->keys, struct keybuf_key, node);
2306 buf->end = w->key;
2307 } else {
2308 buf->start = MAX_KEY;
2309 buf->end = MAX_KEY;
2310 }
2311
2312 spin_unlock(&buf->lock);
2313}
2314
2315static void __bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w)
2316{
2317 rb_erase(&w->node, &buf->keys);
2318 array_free(&buf->freelist, w);
2319}
2320
2321void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w)
2322{
2323 spin_lock(&buf->lock);
2324 __bch_keybuf_del(buf, w);
2325 spin_unlock(&buf->lock);
2326}
2327
2328bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bkey *start,
2329 struct bkey *end)
2330{
2331 bool ret = false;
2332 struct keybuf_key *p, *w, s;
2333 s.key = *start;
2334
2335 if (bkey_cmp(end, &buf->start) <= 0 ||
2336 bkey_cmp(start, &buf->end) >= 0)
2337 return false;
2338
2339 spin_lock(&buf->lock);
2340 w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp);
2341
2342 while (w && bkey_cmp(&START_KEY(&w->key), end) < 0) {
2343 p = w;
2344 w = RB_NEXT(w, node);
2345
2346 if (p->private)
2347 ret = true;
2348 else
2349 __bch_keybuf_del(buf, p);
2350 }
2351
2352 spin_unlock(&buf->lock);
2353 return ret;
2354}
2355
2356struct keybuf_key *bch_keybuf_next(struct keybuf *buf)
2357{
2358 struct keybuf_key *w;
2359 spin_lock(&buf->lock);
2360
2361 w = RB_FIRST(&buf->keys, struct keybuf_key, node);
2362
2363 while (w && w->private)
2364 w = RB_NEXT(w, node);
2365
2366 if (w)
2367 w->private = ERR_PTR(-EINTR);
2368
2369 spin_unlock(&buf->lock);
2370 return w;
2371}
2372
2373struct keybuf_key *bch_keybuf_next_rescan(struct cache_set *c,
Kent Overstreet48dad8b2013-09-10 18:48:51 -07002374 struct keybuf *buf,
2375 struct bkey *end,
2376 keybuf_pred_fn *pred)
Kent Overstreetcafe5632013-03-23 16:11:31 -07002377{
2378 struct keybuf_key *ret;
2379
2380 while (1) {
2381 ret = bch_keybuf_next(buf);
2382 if (ret)
2383 break;
2384
2385 if (bkey_cmp(&buf->last_scanned, end) >= 0) {
2386 pr_debug("scan finished");
2387 break;
2388 }
2389
Kent Overstreet72c27062013-06-05 06:24:39 -07002390 bch_refill_keybuf(c, buf, end, pred);
Kent Overstreetcafe5632013-03-23 16:11:31 -07002391 }
2392
2393 return ret;
2394}
2395
Kent Overstreet72c27062013-06-05 06:24:39 -07002396void bch_keybuf_init(struct keybuf *buf)
Kent Overstreetcafe5632013-03-23 16:11:31 -07002397{
Kent Overstreetcafe5632013-03-23 16:11:31 -07002398 buf->last_scanned = MAX_KEY;
2399 buf->keys = RB_ROOT;
2400
2401 spin_lock_init(&buf->lock);
2402 array_allocator_init(&buf->freelist);
2403}
2404
2405void bch_btree_exit(void)
2406{
2407 if (btree_io_wq)
2408 destroy_workqueue(btree_io_wq);
Kent Overstreetcafe5632013-03-23 16:11:31 -07002409}
2410
2411int __init bch_btree_init(void)
2412{
Kent Overstreet72a44512013-10-24 17:19:26 -07002413 btree_io_wq = create_singlethread_workqueue("bch_btree_io");
2414 if (!btree_io_wq)
Kent Overstreetcafe5632013-03-23 16:11:31 -07002415 return -ENOMEM;
2416
2417 return 0;
2418}