2 * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>
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
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.
13 * Buckets have an 8 bit counter; freeing is accomplished by incrementing the
14 * counter. Garbage collection is used to remove stale pointers.
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.
20 * All configuration is done via sysfs; see Documentation/bcache.txt.
28 #include <linux/slab.h>
29 #include <linux/bitops.h>
30 #include <linux/freezer.h>
31 #include <linux/hash.h>
32 #include <linux/kthread.h>
33 #include <linux/prefetch.h>
34 #include <linux/random.h>
35 #include <linux/rcupdate.h>
36 #include <trace/events/bcache.h>
40 * register_bcache: Return errors out to userspace correctly
42 * Writeback: don't undirty key until after a cache flush
44 * Create an iterator for key pointers
46 * On btree write error, mark bucket such that it won't be freed from the cache
49 * Check for bad keys in replay
51 * Refcount journal entries in journal_replay
54 * Finish incremental gc
55 * Gc should free old UUIDs, data for invalid UUIDs
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
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
65 * Add a tracepoint or somesuch to watch for writeback starvation
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
73 * If data write is less than hard sector size of ssd, round up offset in open
74 * bucket to the next whole sector
76 * Superblock needs to be fleshed out for multiple cache devices
78 * Add a sysfs tunable for the number of writeback IOs in flight
80 * Add a sysfs tunable for the number of open data buckets
82 * IO tracking: Can we track when one process is doing io on behalf of another?
83 * IO tracking: Don't use just an average, weigh more recent stuff higher
85 * Test module load/unload
88 #define MAX_NEED_GC 64
89 #define MAX_SAVE_PRIO 72
91 #define PTR_DIRTY_BIT (((uint64_t) 1 << 36))
93 #define PTR_HASH(c, k) \
94 (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0))
96 #define insert_lock(s, b) ((b)->level <= (s)->lock)
99 * These macros are for recursing down the btree - they handle the details of
100 * locking and looking up nodes in the cache for you. They're best treated as
101 * mere syntax when reading code that uses them.
103 * op->lock determines whether we take a read or a write lock at a given depth.
104 * If you've got a read lock and find that you need a write lock (i.e. you're
105 * going to have to split), set op->lock and return -EINTR; btree_root() will
106 * call you again and you'll have the correct lock.
110 * btree - recurse down the btree on a specified key
111 * @fn: function to call, which will be passed the child node
112 * @key: key to recurse on
113 * @b: parent btree node
114 * @op: pointer to struct btree_op
116 #define btree(fn, key, b, op, ...) \
118 int _r, l = (b)->level - 1; \
119 bool _w = l <= (op)->lock; \
120 struct btree *_child = bch_btree_node_get((b)->c, op, key, l, _w);\
121 if (!IS_ERR(_child)) { \
122 _child->parent = (b); \
123 _r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__); \
124 rw_unlock(_w, _child); \
126 _r = PTR_ERR(_child); \
131 * btree_root - call a function on the root of the btree
132 * @fn: function to call, which will be passed the child node
134 * @op: pointer to struct btree_op
136 #define btree_root(fn, c, op, ...) \
140 struct btree *_b = (c)->root; \
141 bool _w = insert_lock(op, _b); \
142 rw_lock(_w, _b, _b->level); \
143 if (_b == (c)->root && \
144 _w == insert_lock(op, _b)) { \
146 _r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__); \
149 bch_cannibalize_unlock(c); \
152 } while (_r == -EINTR); \
154 finish_wait(&(c)->btree_cache_wait, &(op)->wait); \
158 static inline struct bset
*write_block(struct btree
*b
)
160 return ((void *) btree_bset_first(b
)) + b
->written
* block_bytes(b
->c
);
163 static void bch_btree_init_next(struct btree
*b
)
165 /* If not a leaf node, always sort */
166 if (b
->level
&& b
->keys
.nsets
)
167 bch_btree_sort(&b
->keys
, &b
->c
->sort
);
169 bch_btree_sort_lazy(&b
->keys
, &b
->c
->sort
);
171 if (b
->written
< btree_blocks(b
))
172 bch_bset_init_next(&b
->keys
, write_block(b
),
173 bset_magic(&b
->c
->sb
));
177 /* Btree key manipulation */
179 void bkey_put(struct cache_set
*c
, struct bkey
*k
)
183 for (i
= 0; i
< KEY_PTRS(k
); i
++)
184 if (ptr_available(c
, k
, i
))
185 atomic_dec_bug(&PTR_BUCKET(c
, k
, i
)->pin
);
190 static uint64_t btree_csum_set(struct btree
*b
, struct bset
*i
)
192 uint64_t crc
= b
->key
.ptr
[0];
193 void *data
= (void *) i
+ 8, *end
= bset_bkey_last(i
);
195 crc
= bch_crc64_update(crc
, data
, end
- data
);
196 return crc
^ 0xffffffffffffffffULL
;
199 void bch_btree_node_read_done(struct btree
*b
)
201 const char *err
= "bad btree header";
202 struct bset
*i
= btree_bset_first(b
);
203 struct btree_iter
*iter
;
205 iter
= mempool_alloc(b
->c
->fill_iter
, GFP_NOIO
);
206 iter
->size
= b
->c
->sb
.bucket_size
/ b
->c
->sb
.block_size
;
209 #ifdef CONFIG_BCACHE_DEBUG
217 b
->written
< btree_blocks(b
) && i
->seq
== b
->keys
.set
[0].data
->seq
;
218 i
= write_block(b
)) {
219 err
= "unsupported bset version";
220 if (i
->version
> BCACHE_BSET_VERSION
)
223 err
= "bad btree header";
224 if (b
->written
+ set_blocks(i
, block_bytes(b
->c
)) >
229 if (i
->magic
!= bset_magic(&b
->c
->sb
))
232 err
= "bad checksum";
233 switch (i
->version
) {
235 if (i
->csum
!= csum_set(i
))
238 case BCACHE_BSET_VERSION
:
239 if (i
->csum
!= btree_csum_set(b
, i
))
245 if (i
!= b
->keys
.set
[0].data
&& !i
->keys
)
248 bch_btree_iter_push(iter
, i
->start
, bset_bkey_last(i
));
250 b
->written
+= set_blocks(i
, block_bytes(b
->c
));
253 err
= "corrupted btree";
254 for (i
= write_block(b
);
255 bset_sector_offset(&b
->keys
, i
) < KEY_SIZE(&b
->key
);
256 i
= ((void *) i
) + block_bytes(b
->c
))
257 if (i
->seq
== b
->keys
.set
[0].data
->seq
)
260 bch_btree_sort_and_fix_extents(&b
->keys
, iter
, &b
->c
->sort
);
262 i
= b
->keys
.set
[0].data
;
263 err
= "short btree key";
264 if (b
->keys
.set
[0].size
&&
265 bkey_cmp(&b
->key
, &b
->keys
.set
[0].end
) < 0)
268 if (b
->written
< btree_blocks(b
))
269 bch_bset_init_next(&b
->keys
, write_block(b
),
270 bset_magic(&b
->c
->sb
));
272 mempool_free(iter
, b
->c
->fill_iter
);
275 set_btree_node_io_error(b
);
276 bch_cache_set_error(b
->c
, "%s at bucket %zu, block %u, %u keys",
277 err
, PTR_BUCKET_NR(b
->c
, &b
->key
, 0),
278 bset_block_offset(b
, i
), i
->keys
);
282 static void btree_node_read_endio(struct bio
*bio
, int error
)
284 struct closure
*cl
= bio
->bi_private
;
288 static void bch_btree_node_read(struct btree
*b
)
290 uint64_t start_time
= local_clock();
294 trace_bcache_btree_read(b
);
296 closure_init_stack(&cl
);
298 bio
= bch_bbio_alloc(b
->c
);
299 bio
->bi_rw
= REQ_META
|READ_SYNC
;
300 bio
->bi_iter
.bi_size
= KEY_SIZE(&b
->key
) << 9;
301 bio
->bi_end_io
= btree_node_read_endio
;
302 bio
->bi_private
= &cl
;
304 bch_bio_map(bio
, b
->keys
.set
[0].data
);
306 bch_submit_bbio(bio
, b
->c
, &b
->key
, 0);
309 if (!test_bit(BIO_UPTODATE
, &bio
->bi_flags
))
310 set_btree_node_io_error(b
);
312 bch_bbio_free(bio
, b
->c
);
314 if (btree_node_io_error(b
))
317 bch_btree_node_read_done(b
);
318 bch_time_stats_update(&b
->c
->btree_read_time
, start_time
);
322 bch_cache_set_error(b
->c
, "io error reading bucket %zu",
323 PTR_BUCKET_NR(b
->c
, &b
->key
, 0));
326 static void btree_complete_write(struct btree
*b
, struct btree_write
*w
)
328 if (w
->prio_blocked
&&
329 !atomic_sub_return(w
->prio_blocked
, &b
->c
->prio_blocked
))
330 wake_up_allocators(b
->c
);
333 atomic_dec_bug(w
->journal
);
334 __closure_wake_up(&b
->c
->journal
.wait
);
341 static void btree_node_write_unlock(struct closure
*cl
)
343 struct btree
*b
= container_of(cl
, struct btree
, io
);
348 static void __btree_node_write_done(struct closure
*cl
)
350 struct btree
*b
= container_of(cl
, struct btree
, io
);
351 struct btree_write
*w
= btree_prev_write(b
);
353 bch_bbio_free(b
->bio
, b
->c
);
355 btree_complete_write(b
, w
);
357 if (btree_node_dirty(b
))
358 schedule_delayed_work(&b
->work
, 30 * HZ
);
360 closure_return_with_destructor(cl
, btree_node_write_unlock
);
363 static void btree_node_write_done(struct closure
*cl
)
365 struct btree
*b
= container_of(cl
, struct btree
, io
);
369 bio_for_each_segment_all(bv
, b
->bio
, n
)
370 __free_page(bv
->bv_page
);
372 __btree_node_write_done(cl
);
375 static void btree_node_write_endio(struct bio
*bio
, int error
)
377 struct closure
*cl
= bio
->bi_private
;
378 struct btree
*b
= container_of(cl
, struct btree
, io
);
381 set_btree_node_io_error(b
);
383 bch_bbio_count_io_errors(b
->c
, bio
, error
, "writing btree");
387 static void do_btree_node_write(struct btree
*b
)
389 struct closure
*cl
= &b
->io
;
390 struct bset
*i
= btree_bset_last(b
);
393 i
->version
= BCACHE_BSET_VERSION
;
394 i
->csum
= btree_csum_set(b
, i
);
397 b
->bio
= bch_bbio_alloc(b
->c
);
399 b
->bio
->bi_end_io
= btree_node_write_endio
;
400 b
->bio
->bi_private
= cl
;
401 b
->bio
->bi_rw
= REQ_META
|WRITE_SYNC
|REQ_FUA
;
402 b
->bio
->bi_iter
.bi_size
= roundup(set_bytes(i
), block_bytes(b
->c
));
403 bch_bio_map(b
->bio
, i
);
406 * If we're appending to a leaf node, we don't technically need FUA -
407 * this write just needs to be persisted before the next journal write,
408 * which will be marked FLUSH|FUA.
410 * Similarly if we're writing a new btree root - the pointer is going to
411 * be in the next journal entry.
413 * But if we're writing a new btree node (that isn't a root) or
414 * appending to a non leaf btree node, we need either FUA or a flush
415 * when we write the parent with the new pointer. FUA is cheaper than a
416 * flush, and writes appending to leaf nodes aren't blocking anything so
417 * just make all btree node writes FUA to keep things sane.
420 bkey_copy(&k
.key
, &b
->key
);
421 SET_PTR_OFFSET(&k
.key
, 0, PTR_OFFSET(&k
.key
, 0) +
422 bset_sector_offset(&b
->keys
, i
));
424 if (!bio_alloc_pages(b
->bio
, GFP_NOIO
)) {
427 void *base
= (void *) ((unsigned long) i
& ~(PAGE_SIZE
- 1));
429 bio_for_each_segment_all(bv
, b
->bio
, j
)
430 memcpy(page_address(bv
->bv_page
),
431 base
+ j
* PAGE_SIZE
, PAGE_SIZE
);
433 bch_submit_bbio(b
->bio
, b
->c
, &k
.key
, 0);
435 continue_at(cl
, btree_node_write_done
, NULL
);
438 bch_bio_map(b
->bio
, i
);
440 bch_submit_bbio(b
->bio
, b
->c
, &k
.key
, 0);
443 continue_at_nobarrier(cl
, __btree_node_write_done
, NULL
);
447 void __bch_btree_node_write(struct btree
*b
, struct closure
*parent
)
449 struct bset
*i
= btree_bset_last(b
);
451 lockdep_assert_held(&b
->write_lock
);
453 trace_bcache_btree_write(b
);
455 BUG_ON(current
->bio_list
);
456 BUG_ON(b
->written
>= btree_blocks(b
));
457 BUG_ON(b
->written
&& !i
->keys
);
458 BUG_ON(btree_bset_first(b
)->seq
!= i
->seq
);
459 bch_check_keys(&b
->keys
, "writing");
461 cancel_delayed_work(&b
->work
);
463 /* If caller isn't waiting for write, parent refcount is cache set */
465 closure_init(&b
->io
, parent
?: &b
->c
->cl
);
467 clear_bit(BTREE_NODE_dirty
, &b
->flags
);
468 change_bit(BTREE_NODE_write_idx
, &b
->flags
);
470 do_btree_node_write(b
);
472 atomic_long_add(set_blocks(i
, block_bytes(b
->c
)) * b
->c
->sb
.block_size
,
473 &PTR_CACHE(b
->c
, &b
->key
, 0)->btree_sectors_written
);
475 b
->written
+= set_blocks(i
, block_bytes(b
->c
));
478 void bch_btree_node_write(struct btree
*b
, struct closure
*parent
)
480 unsigned nsets
= b
->keys
.nsets
;
482 lockdep_assert_held(&b
->lock
);
484 __bch_btree_node_write(b
, parent
);
487 * do verify if there was more than one set initially (i.e. we did a
488 * sort) and we sorted down to a single set:
490 if (nsets
&& !b
->keys
.nsets
)
493 bch_btree_init_next(b
);
496 static void bch_btree_node_write_sync(struct btree
*b
)
500 closure_init_stack(&cl
);
502 mutex_lock(&b
->write_lock
);
503 bch_btree_node_write(b
, &cl
);
504 mutex_unlock(&b
->write_lock
);
509 static void btree_node_write_work(struct work_struct
*w
)
511 struct btree
*b
= container_of(to_delayed_work(w
), struct btree
, work
);
513 mutex_lock(&b
->write_lock
);
514 if (btree_node_dirty(b
))
515 __bch_btree_node_write(b
, NULL
);
516 mutex_unlock(&b
->write_lock
);
519 static void bch_btree_leaf_dirty(struct btree
*b
, atomic_t
*journal_ref
)
521 struct bset
*i
= btree_bset_last(b
);
522 struct btree_write
*w
= btree_current_write(b
);
524 lockdep_assert_held(&b
->write_lock
);
529 if (!btree_node_dirty(b
))
530 schedule_delayed_work(&b
->work
, 30 * HZ
);
532 set_btree_node_dirty(b
);
536 journal_pin_cmp(b
->c
, w
->journal
, journal_ref
)) {
537 atomic_dec_bug(w
->journal
);
542 w
->journal
= journal_ref
;
543 atomic_inc(w
->journal
);
547 /* Force write if set is too big */
548 if (set_bytes(i
) > PAGE_SIZE
- 48 &&
550 bch_btree_node_write(b
, NULL
);
554 * Btree in memory cache - allocation/freeing
555 * mca -> memory cache
558 #define mca_reserve(c) (((c->root && c->root->level) \
559 ? c->root->level : 1) * 8 + 16)
560 #define mca_can_free(c) \
561 max_t(int, 0, c->btree_cache_used - mca_reserve(c))
563 static void mca_data_free(struct btree
*b
)
565 BUG_ON(b
->io_mutex
.count
!= 1);
567 bch_btree_keys_free(&b
->keys
);
569 b
->c
->btree_cache_used
--;
570 list_move(&b
->list
, &b
->c
->btree_cache_freed
);
573 static void mca_bucket_free(struct btree
*b
)
575 BUG_ON(btree_node_dirty(b
));
578 hlist_del_init_rcu(&b
->hash
);
579 list_move(&b
->list
, &b
->c
->btree_cache_freeable
);
582 static unsigned btree_order(struct bkey
*k
)
584 return ilog2(KEY_SIZE(k
) / PAGE_SECTORS
?: 1);
587 static void mca_data_alloc(struct btree
*b
, struct bkey
*k
, gfp_t gfp
)
589 if (!bch_btree_keys_alloc(&b
->keys
,
591 ilog2(b
->c
->btree_pages
),
594 b
->c
->btree_cache_used
++;
595 list_move(&b
->list
, &b
->c
->btree_cache
);
597 list_move(&b
->list
, &b
->c
->btree_cache_freed
);
601 static struct btree
*mca_bucket_alloc(struct cache_set
*c
,
602 struct bkey
*k
, gfp_t gfp
)
604 struct btree
*b
= kzalloc(sizeof(struct btree
), gfp
);
608 init_rwsem(&b
->lock
);
609 lockdep_set_novalidate_class(&b
->lock
);
610 mutex_init(&b
->write_lock
);
611 lockdep_set_novalidate_class(&b
->write_lock
);
612 INIT_LIST_HEAD(&b
->list
);
613 INIT_DELAYED_WORK(&b
->work
, btree_node_write_work
);
615 sema_init(&b
->io_mutex
, 1);
617 mca_data_alloc(b
, k
, gfp
);
621 static int mca_reap(struct btree
*b
, unsigned min_order
, bool flush
)
625 closure_init_stack(&cl
);
626 lockdep_assert_held(&b
->c
->bucket_lock
);
628 if (!down_write_trylock(&b
->lock
))
631 BUG_ON(btree_node_dirty(b
) && !b
->keys
.set
[0].data
);
633 if (b
->keys
.page_order
< min_order
)
637 if (btree_node_dirty(b
))
640 if (down_trylock(&b
->io_mutex
))
645 mutex_lock(&b
->write_lock
);
646 if (btree_node_dirty(b
))
647 __bch_btree_node_write(b
, &cl
);
648 mutex_unlock(&b
->write_lock
);
652 /* wait for any in flight btree write */
662 static unsigned long bch_mca_scan(struct shrinker
*shrink
,
663 struct shrink_control
*sc
)
665 struct cache_set
*c
= container_of(shrink
, struct cache_set
, shrink
);
667 unsigned long i
, nr
= sc
->nr_to_scan
;
668 unsigned long freed
= 0;
670 if (c
->shrinker_disabled
)
673 if (c
->btree_cache_alloc_lock
)
676 /* Return -1 if we can't do anything right now */
677 if (sc
->gfp_mask
& __GFP_IO
)
678 mutex_lock(&c
->bucket_lock
);
679 else if (!mutex_trylock(&c
->bucket_lock
))
683 * It's _really_ critical that we don't free too many btree nodes - we
684 * have to always leave ourselves a reserve. The reserve is how we
685 * guarantee that allocating memory for a new btree node can always
686 * succeed, so that inserting keys into the btree can always succeed and
687 * IO can always make forward progress:
689 nr
/= c
->btree_pages
;
690 nr
= min_t(unsigned long, nr
, mca_can_free(c
));
693 list_for_each_entry_safe(b
, t
, &c
->btree_cache_freeable
, list
) {
698 !mca_reap(b
, 0, false)) {
705 for (i
= 0; (nr
--) && i
< c
->btree_cache_used
; i
++) {
706 if (list_empty(&c
->btree_cache
))
709 b
= list_first_entry(&c
->btree_cache
, struct btree
, list
);
710 list_rotate_left(&c
->btree_cache
);
713 !mca_reap(b
, 0, false)) {
722 mutex_unlock(&c
->bucket_lock
);
726 static unsigned long bch_mca_count(struct shrinker
*shrink
,
727 struct shrink_control
*sc
)
729 struct cache_set
*c
= container_of(shrink
, struct cache_set
, shrink
);
731 if (c
->shrinker_disabled
)
734 if (c
->btree_cache_alloc_lock
)
737 return mca_can_free(c
) * c
->btree_pages
;
740 void bch_btree_cache_free(struct cache_set
*c
)
744 closure_init_stack(&cl
);
746 if (c
->shrink
.list
.next
)
747 unregister_shrinker(&c
->shrink
);
749 mutex_lock(&c
->bucket_lock
);
751 #ifdef CONFIG_BCACHE_DEBUG
753 list_move(&c
->verify_data
->list
, &c
->btree_cache
);
755 free_pages((unsigned long) c
->verify_ondisk
, ilog2(bucket_pages(c
)));
758 list_splice(&c
->btree_cache_freeable
,
761 while (!list_empty(&c
->btree_cache
)) {
762 b
= list_first_entry(&c
->btree_cache
, struct btree
, list
);
764 if (btree_node_dirty(b
))
765 btree_complete_write(b
, btree_current_write(b
));
766 clear_bit(BTREE_NODE_dirty
, &b
->flags
);
771 while (!list_empty(&c
->btree_cache_freed
)) {
772 b
= list_first_entry(&c
->btree_cache_freed
,
775 cancel_delayed_work_sync(&b
->work
);
779 mutex_unlock(&c
->bucket_lock
);
782 int bch_btree_cache_alloc(struct cache_set
*c
)
786 for (i
= 0; i
< mca_reserve(c
); i
++)
787 if (!mca_bucket_alloc(c
, &ZERO_KEY
, GFP_KERNEL
))
790 list_splice_init(&c
->btree_cache
,
791 &c
->btree_cache_freeable
);
793 #ifdef CONFIG_BCACHE_DEBUG
794 mutex_init(&c
->verify_lock
);
796 c
->verify_ondisk
= (void *)
797 __get_free_pages(GFP_KERNEL
, ilog2(bucket_pages(c
)));
799 c
->verify_data
= mca_bucket_alloc(c
, &ZERO_KEY
, GFP_KERNEL
);
801 if (c
->verify_data
&&
802 c
->verify_data
->keys
.set
->data
)
803 list_del_init(&c
->verify_data
->list
);
805 c
->verify_data
= NULL
;
808 c
->shrink
.count_objects
= bch_mca_count
;
809 c
->shrink
.scan_objects
= bch_mca_scan
;
811 c
->shrink
.batch
= c
->btree_pages
* 2;
812 register_shrinker(&c
->shrink
);
817 /* Btree in memory cache - hash table */
819 static struct hlist_head
*mca_hash(struct cache_set
*c
, struct bkey
*k
)
821 return &c
->bucket_hash
[hash_32(PTR_HASH(c
, k
), BUCKET_HASH_BITS
)];
824 static struct btree
*mca_find(struct cache_set
*c
, struct bkey
*k
)
829 hlist_for_each_entry_rcu(b
, mca_hash(c
, k
), hash
)
830 if (PTR_HASH(c
, &b
->key
) == PTR_HASH(c
, k
))
838 static int mca_cannibalize_lock(struct cache_set
*c
, struct btree_op
*op
)
840 struct task_struct
*old
;
842 old
= cmpxchg(&c
->btree_cache_alloc_lock
, NULL
, current
);
843 if (old
&& old
!= current
) {
845 prepare_to_wait(&c
->btree_cache_wait
, &op
->wait
,
846 TASK_UNINTERRUPTIBLE
);
853 static struct btree
*mca_cannibalize(struct cache_set
*c
, struct btree_op
*op
,
858 trace_bcache_btree_cache_cannibalize(c
);
860 if (mca_cannibalize_lock(c
, op
))
861 return ERR_PTR(-EINTR
);
863 list_for_each_entry_reverse(b
, &c
->btree_cache
, list
)
864 if (!mca_reap(b
, btree_order(k
), false))
867 list_for_each_entry_reverse(b
, &c
->btree_cache
, list
)
868 if (!mca_reap(b
, btree_order(k
), true))
871 WARN(1, "btree cache cannibalize failed\n");
872 return ERR_PTR(-ENOMEM
);
876 * We can only have one thread cannibalizing other cached btree nodes at a time,
877 * or we'll deadlock. We use an open coded mutex to ensure that, which a
878 * cannibalize_bucket() will take. This means every time we unlock the root of
879 * the btree, we need to release this lock if we have it held.
881 static void bch_cannibalize_unlock(struct cache_set
*c
)
883 if (c
->btree_cache_alloc_lock
== current
) {
884 c
->btree_cache_alloc_lock
= NULL
;
885 wake_up(&c
->btree_cache_wait
);
889 static struct btree
*mca_alloc(struct cache_set
*c
, struct btree_op
*op
,
890 struct bkey
*k
, int level
)
894 BUG_ON(current
->bio_list
);
896 lockdep_assert_held(&c
->bucket_lock
);
901 /* btree_free() doesn't free memory; it sticks the node on the end of
902 * the list. Check if there's any freed nodes there:
904 list_for_each_entry(b
, &c
->btree_cache_freeable
, list
)
905 if (!mca_reap(b
, btree_order(k
), false))
908 /* We never free struct btree itself, just the memory that holds the on
909 * disk node. Check the freed list before allocating a new one:
911 list_for_each_entry(b
, &c
->btree_cache_freed
, list
)
912 if (!mca_reap(b
, 0, false)) {
913 mca_data_alloc(b
, k
, __GFP_NOWARN
|GFP_NOIO
);
914 if (!b
->keys
.set
[0].data
)
920 b
= mca_bucket_alloc(c
, k
, __GFP_NOWARN
|GFP_NOIO
);
924 BUG_ON(!down_write_trylock(&b
->lock
));
925 if (!b
->keys
.set
->data
)
928 BUG_ON(b
->io_mutex
.count
!= 1);
930 bkey_copy(&b
->key
, k
);
931 list_move(&b
->list
, &c
->btree_cache
);
932 hlist_del_init_rcu(&b
->hash
);
933 hlist_add_head_rcu(&b
->hash
, mca_hash(c
, k
));
935 lock_set_subclass(&b
->lock
.dep_map
, level
+ 1, _THIS_IP_
);
936 b
->parent
= (void *) ~0UL;
942 bch_btree_keys_init(&b
->keys
, &bch_extent_keys_ops
,
943 &b
->c
->expensive_debug_checks
);
945 bch_btree_keys_init(&b
->keys
, &bch_btree_keys_ops
,
946 &b
->c
->expensive_debug_checks
);
953 b
= mca_cannibalize(c
, op
, k
);
961 * bch_btree_node_get - find a btree node in the cache and lock it, reading it
962 * in from disk if necessary.
964 * If IO is necessary and running under generic_make_request, returns -EAGAIN.
966 * The btree node will have either a read or a write lock held, depending on
967 * level and op->lock.
969 struct btree
*bch_btree_node_get(struct cache_set
*c
, struct btree_op
*op
,
970 struct bkey
*k
, int level
, bool write
)
980 if (current
->bio_list
)
981 return ERR_PTR(-EAGAIN
);
983 mutex_lock(&c
->bucket_lock
);
984 b
= mca_alloc(c
, op
, k
, level
);
985 mutex_unlock(&c
->bucket_lock
);
992 bch_btree_node_read(b
);
995 downgrade_write(&b
->lock
);
997 rw_lock(write
, b
, level
);
998 if (PTR_HASH(c
, &b
->key
) != PTR_HASH(c
, k
)) {
1002 BUG_ON(b
->level
!= level
);
1007 for (; i
<= b
->keys
.nsets
&& b
->keys
.set
[i
].size
; i
++) {
1008 prefetch(b
->keys
.set
[i
].tree
);
1009 prefetch(b
->keys
.set
[i
].data
);
1012 for (; i
<= b
->keys
.nsets
; i
++)
1013 prefetch(b
->keys
.set
[i
].data
);
1015 if (btree_node_io_error(b
)) {
1016 rw_unlock(write
, b
);
1017 return ERR_PTR(-EIO
);
1020 BUG_ON(!b
->written
);
1025 static void btree_node_prefetch(struct cache_set
*c
, struct bkey
*k
, int level
)
1029 mutex_lock(&c
->bucket_lock
);
1030 b
= mca_alloc(c
, NULL
, k
, level
);
1031 mutex_unlock(&c
->bucket_lock
);
1033 if (!IS_ERR_OR_NULL(b
)) {
1034 bch_btree_node_read(b
);
1041 static void btree_node_free(struct btree
*b
)
1043 trace_bcache_btree_node_free(b
);
1045 BUG_ON(b
== b
->c
->root
);
1047 mutex_lock(&b
->write_lock
);
1049 if (btree_node_dirty(b
))
1050 btree_complete_write(b
, btree_current_write(b
));
1051 clear_bit(BTREE_NODE_dirty
, &b
->flags
);
1053 mutex_unlock(&b
->write_lock
);
1055 cancel_delayed_work(&b
->work
);
1057 mutex_lock(&b
->c
->bucket_lock
);
1058 bch_bucket_free(b
->c
, &b
->key
);
1060 mutex_unlock(&b
->c
->bucket_lock
);
1063 struct btree
*__bch_btree_node_alloc(struct cache_set
*c
, struct btree_op
*op
,
1064 int level
, bool wait
)
1067 struct btree
*b
= ERR_PTR(-EAGAIN
);
1069 mutex_lock(&c
->bucket_lock
);
1071 if (__bch_bucket_alloc_set(c
, RESERVE_BTREE
, &k
.key
, 1, wait
))
1074 bkey_put(c
, &k
.key
);
1075 SET_KEY_SIZE(&k
.key
, c
->btree_pages
* PAGE_SECTORS
);
1077 b
= mca_alloc(c
, op
, &k
.key
, level
);
1083 "Tried to allocate bucket that was in btree cache");
1088 bch_bset_init_next(&b
->keys
, b
->keys
.set
->data
, bset_magic(&b
->c
->sb
));
1090 mutex_unlock(&c
->bucket_lock
);
1092 trace_bcache_btree_node_alloc(b
);
1095 bch_bucket_free(c
, &k
.key
);
1097 mutex_unlock(&c
->bucket_lock
);
1099 trace_bcache_btree_node_alloc_fail(b
);
1103 static struct btree
*bch_btree_node_alloc(struct cache_set
*c
,
1104 struct btree_op
*op
, int level
)
1106 return __bch_btree_node_alloc(c
, op
, level
, op
!= NULL
);
1109 static struct btree
*btree_node_alloc_replacement(struct btree
*b
,
1110 struct btree_op
*op
)
1112 struct btree
*n
= bch_btree_node_alloc(b
->c
, op
, b
->level
);
1113 if (!IS_ERR_OR_NULL(n
)) {
1114 mutex_lock(&n
->write_lock
);
1115 bch_btree_sort_into(&b
->keys
, &n
->keys
, &b
->c
->sort
);
1116 bkey_copy_key(&n
->key
, &b
->key
);
1117 mutex_unlock(&n
->write_lock
);
1123 static void make_btree_freeing_key(struct btree
*b
, struct bkey
*k
)
1127 mutex_lock(&b
->c
->bucket_lock
);
1129 atomic_inc(&b
->c
->prio_blocked
);
1131 bkey_copy(k
, &b
->key
);
1132 bkey_copy_key(k
, &ZERO_KEY
);
1134 for (i
= 0; i
< KEY_PTRS(k
); i
++)
1136 bch_inc_gen(PTR_CACHE(b
->c
, &b
->key
, i
),
1137 PTR_BUCKET(b
->c
, &b
->key
, i
)));
1139 mutex_unlock(&b
->c
->bucket_lock
);
1142 static int btree_check_reserve(struct btree
*b
, struct btree_op
*op
)
1144 struct cache_set
*c
= b
->c
;
1146 unsigned i
, reserve
= (c
->root
->level
- b
->level
) * 2 + 1;
1148 mutex_lock(&c
->bucket_lock
);
1150 for_each_cache(ca
, c
, i
)
1151 if (fifo_used(&ca
->free
[RESERVE_BTREE
]) < reserve
) {
1153 prepare_to_wait(&c
->btree_cache_wait
, &op
->wait
,
1154 TASK_UNINTERRUPTIBLE
);
1155 mutex_unlock(&c
->bucket_lock
);
1159 mutex_unlock(&c
->bucket_lock
);
1161 return mca_cannibalize_lock(b
->c
, op
);
1164 /* Garbage collection */
1166 static uint8_t __bch_btree_mark_key(struct cache_set
*c
, int level
,
1174 * ptr_invalid() can't return true for the keys that mark btree nodes as
1175 * freed, but since ptr_bad() returns true we'll never actually use them
1176 * for anything and thus we don't want mark their pointers here
1178 if (!bkey_cmp(k
, &ZERO_KEY
))
1181 for (i
= 0; i
< KEY_PTRS(k
); i
++) {
1182 if (!ptr_available(c
, k
, i
))
1185 g
= PTR_BUCKET(c
, k
, i
);
1187 if (gen_after(g
->last_gc
, PTR_GEN(k
, i
)))
1188 g
->last_gc
= PTR_GEN(k
, i
);
1190 if (ptr_stale(c
, k
, i
)) {
1191 stale
= max(stale
, ptr_stale(c
, k
, i
));
1195 cache_bug_on(GC_MARK(g
) &&
1196 (GC_MARK(g
) == GC_MARK_METADATA
) != (level
!= 0),
1197 c
, "inconsistent ptrs: mark = %llu, level = %i",
1201 SET_GC_MARK(g
, GC_MARK_METADATA
);
1202 else if (KEY_DIRTY(k
))
1203 SET_GC_MARK(g
, GC_MARK_DIRTY
);
1204 else if (!GC_MARK(g
))
1205 SET_GC_MARK(g
, GC_MARK_RECLAIMABLE
);
1207 /* guard against overflow */
1208 SET_GC_SECTORS_USED(g
, min_t(unsigned,
1209 GC_SECTORS_USED(g
) + KEY_SIZE(k
),
1210 MAX_GC_SECTORS_USED
));
1212 BUG_ON(!GC_SECTORS_USED(g
));
1218 #define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k)
1220 void bch_initial_mark_key(struct cache_set
*c
, int level
, struct bkey
*k
)
1224 for (i
= 0; i
< KEY_PTRS(k
); i
++)
1225 if (ptr_available(c
, k
, i
) &&
1226 !ptr_stale(c
, k
, i
)) {
1227 struct bucket
*b
= PTR_BUCKET(c
, k
, i
);
1229 b
->gen
= PTR_GEN(k
, i
);
1231 if (level
&& bkey_cmp(k
, &ZERO_KEY
))
1232 b
->prio
= BTREE_PRIO
;
1233 else if (!level
&& b
->prio
== BTREE_PRIO
)
1234 b
->prio
= INITIAL_PRIO
;
1237 __bch_btree_mark_key(c
, level
, k
);
1240 static bool btree_gc_mark_node(struct btree
*b
, struct gc_stat
*gc
)
1243 unsigned keys
= 0, good_keys
= 0;
1245 struct btree_iter iter
;
1246 struct bset_tree
*t
;
1250 for_each_key_filter(&b
->keys
, k
, &iter
, bch_ptr_invalid
) {
1251 stale
= max(stale
, btree_mark_key(b
, k
));
1254 if (bch_ptr_bad(&b
->keys
, k
))
1257 gc
->key_bytes
+= bkey_u64s(k
);
1261 gc
->data
+= KEY_SIZE(k
);
1264 for (t
= b
->keys
.set
; t
<= &b
->keys
.set
[b
->keys
.nsets
]; t
++)
1265 btree_bug_on(t
->size
&&
1266 bset_written(&b
->keys
, t
) &&
1267 bkey_cmp(&b
->key
, &t
->end
) < 0,
1268 b
, "found short btree key in gc");
1270 if (b
->c
->gc_always_rewrite
)
1276 if ((keys
- good_keys
) * 2 > keys
)
1282 #define GC_MERGE_NODES 4U
1284 struct gc_merge_info
{
1289 static int bch_btree_insert_node(struct btree
*, struct btree_op
*,
1290 struct keylist
*, atomic_t
*, struct bkey
*);
1292 static int btree_gc_coalesce(struct btree
*b
, struct btree_op
*op
,
1293 struct gc_stat
*gc
, struct gc_merge_info
*r
)
1295 unsigned i
, nodes
= 0, keys
= 0, blocks
;
1296 struct btree
*new_nodes
[GC_MERGE_NODES
];
1297 struct keylist keylist
;
1301 bch_keylist_init(&keylist
);
1303 if (btree_check_reserve(b
, NULL
))
1306 memset(new_nodes
, 0, sizeof(new_nodes
));
1307 closure_init_stack(&cl
);
1309 while (nodes
< GC_MERGE_NODES
&& !IS_ERR_OR_NULL(r
[nodes
].b
))
1310 keys
+= r
[nodes
++].keys
;
1312 blocks
= btree_default_blocks(b
->c
) * 2 / 3;
1315 __set_blocks(b
->keys
.set
[0].data
, keys
,
1316 block_bytes(b
->c
)) > blocks
* (nodes
- 1))
1319 for (i
= 0; i
< nodes
; i
++) {
1320 new_nodes
[i
] = btree_node_alloc_replacement(r
[i
].b
, NULL
);
1321 if (IS_ERR_OR_NULL(new_nodes
[i
]))
1322 goto out_nocoalesce
;
1326 * We have to check the reserve here, after we've allocated our new
1327 * nodes, to make sure the insert below will succeed - we also check
1328 * before as an optimization to potentially avoid a bunch of expensive
1331 if (btree_check_reserve(b
, NULL
))
1332 goto out_nocoalesce
;
1334 for (i
= 0; i
< nodes
; i
++)
1335 mutex_lock(&new_nodes
[i
]->write_lock
);
1337 for (i
= nodes
- 1; i
> 0; --i
) {
1338 struct bset
*n1
= btree_bset_first(new_nodes
[i
]);
1339 struct bset
*n2
= btree_bset_first(new_nodes
[i
- 1]);
1340 struct bkey
*k
, *last
= NULL
;
1346 k
< bset_bkey_last(n2
);
1348 if (__set_blocks(n1
, n1
->keys
+ keys
+
1350 block_bytes(b
->c
)) > blocks
)
1354 keys
+= bkey_u64s(k
);
1358 * Last node we're not getting rid of - we're getting
1359 * rid of the node at r[0]. Have to try and fit all of
1360 * the remaining keys into this node; we can't ensure
1361 * they will always fit due to rounding and variable
1362 * length keys (shouldn't be possible in practice,
1365 if (__set_blocks(n1
, n1
->keys
+ n2
->keys
,
1366 block_bytes(b
->c
)) >
1367 btree_blocks(new_nodes
[i
]))
1368 goto out_nocoalesce
;
1371 /* Take the key of the node we're getting rid of */
1375 BUG_ON(__set_blocks(n1
, n1
->keys
+ keys
, block_bytes(b
->c
)) >
1376 btree_blocks(new_nodes
[i
]));
1379 bkey_copy_key(&new_nodes
[i
]->key
, last
);
1381 memcpy(bset_bkey_last(n1
),
1383 (void *) bset_bkey_idx(n2
, keys
) - (void *) n2
->start
);
1386 r
[i
].keys
= n1
->keys
;
1389 bset_bkey_idx(n2
, keys
),
1390 (void *) bset_bkey_last(n2
) -
1391 (void *) bset_bkey_idx(n2
, keys
));
1395 if (__bch_keylist_realloc(&keylist
,
1396 bkey_u64s(&new_nodes
[i
]->key
)))
1397 goto out_nocoalesce
;
1399 bch_btree_node_write(new_nodes
[i
], &cl
);
1400 bch_keylist_add(&keylist
, &new_nodes
[i
]->key
);
1403 for (i
= 0; i
< nodes
; i
++)
1404 mutex_unlock(&new_nodes
[i
]->write_lock
);
1408 /* We emptied out this node */
1409 BUG_ON(btree_bset_first(new_nodes
[0])->keys
);
1410 btree_node_free(new_nodes
[0]);
1411 rw_unlock(true, new_nodes
[0]);
1413 for (i
= 0; i
< nodes
; i
++) {
1414 if (__bch_keylist_realloc(&keylist
, bkey_u64s(&r
[i
].b
->key
)))
1415 goto out_nocoalesce
;
1417 make_btree_freeing_key(r
[i
].b
, keylist
.top
);
1418 bch_keylist_push(&keylist
);
1421 bch_btree_insert_node(b
, op
, &keylist
, NULL
, NULL
);
1422 BUG_ON(!bch_keylist_empty(&keylist
));
1424 for (i
= 0; i
< nodes
; i
++) {
1425 btree_node_free(r
[i
].b
);
1426 rw_unlock(true, r
[i
].b
);
1428 r
[i
].b
= new_nodes
[i
];
1431 memmove(r
, r
+ 1, sizeof(r
[0]) * (nodes
- 1));
1432 r
[nodes
- 1].b
= ERR_PTR(-EINTR
);
1434 trace_bcache_btree_gc_coalesce(nodes
);
1437 bch_keylist_free(&keylist
);
1439 /* Invalidated our iterator */
1444 bch_keylist_free(&keylist
);
1446 while ((k
= bch_keylist_pop(&keylist
)))
1447 if (!bkey_cmp(k
, &ZERO_KEY
))
1448 atomic_dec(&b
->c
->prio_blocked
);
1450 for (i
= 0; i
< nodes
; i
++)
1451 if (!IS_ERR_OR_NULL(new_nodes
[i
])) {
1452 btree_node_free(new_nodes
[i
]);
1453 rw_unlock(true, new_nodes
[i
]);
1458 static int btree_gc_rewrite_node(struct btree
*b
, struct btree_op
*op
,
1459 struct btree
*replace
)
1461 struct keylist keys
;
1464 if (btree_check_reserve(b
, NULL
))
1467 n
= btree_node_alloc_replacement(replace
, NULL
);
1469 /* recheck reserve after allocating replacement node */
1470 if (btree_check_reserve(b
, NULL
)) {
1476 bch_btree_node_write_sync(n
);
1478 bch_keylist_init(&keys
);
1479 bch_keylist_add(&keys
, &n
->key
);
1481 make_btree_freeing_key(replace
, keys
.top
);
1482 bch_keylist_push(&keys
);
1484 bch_btree_insert_node(b
, op
, &keys
, NULL
, NULL
);
1485 BUG_ON(!bch_keylist_empty(&keys
));
1487 btree_node_free(replace
);
1490 /* Invalidated our iterator */
1494 static unsigned btree_gc_count_keys(struct btree
*b
)
1497 struct btree_iter iter
;
1500 for_each_key_filter(&b
->keys
, k
, &iter
, bch_ptr_bad
)
1501 ret
+= bkey_u64s(k
);
1506 static int btree_gc_recurse(struct btree
*b
, struct btree_op
*op
,
1507 struct closure
*writes
, struct gc_stat
*gc
)
1510 bool should_rewrite
;
1512 struct btree_iter iter
;
1513 struct gc_merge_info r
[GC_MERGE_NODES
];
1514 struct gc_merge_info
*i
, *last
= r
+ ARRAY_SIZE(r
) - 1;
1516 bch_btree_iter_init(&b
->keys
, &iter
, &b
->c
->gc_done
);
1518 for (i
= r
; i
< r
+ ARRAY_SIZE(r
); i
++)
1519 i
->b
= ERR_PTR(-EINTR
);
1522 k
= bch_btree_iter_next_filter(&iter
, &b
->keys
, bch_ptr_bad
);
1524 r
->b
= bch_btree_node_get(b
->c
, op
, k
, b
->level
- 1,
1527 ret
= PTR_ERR(r
->b
);
1531 r
->keys
= btree_gc_count_keys(r
->b
);
1533 ret
= btree_gc_coalesce(b
, op
, gc
, r
);
1541 if (!IS_ERR(last
->b
)) {
1542 should_rewrite
= btree_gc_mark_node(last
->b
, gc
);
1543 if (should_rewrite
) {
1544 ret
= btree_gc_rewrite_node(b
, op
, last
->b
);
1549 if (last
->b
->level
) {
1550 ret
= btree_gc_recurse(last
->b
, op
, writes
, gc
);
1555 bkey_copy_key(&b
->c
->gc_done
, &last
->b
->key
);
1558 * Must flush leaf nodes before gc ends, since replace
1559 * operations aren't journalled
1561 mutex_lock(&last
->b
->write_lock
);
1562 if (btree_node_dirty(last
->b
))
1563 bch_btree_node_write(last
->b
, writes
);
1564 mutex_unlock(&last
->b
->write_lock
);
1565 rw_unlock(true, last
->b
);
1568 memmove(r
+ 1, r
, sizeof(r
[0]) * (GC_MERGE_NODES
- 1));
1571 if (need_resched()) {
1577 for (i
= r
; i
< r
+ ARRAY_SIZE(r
); i
++)
1578 if (!IS_ERR_OR_NULL(i
->b
)) {
1579 mutex_lock(&i
->b
->write_lock
);
1580 if (btree_node_dirty(i
->b
))
1581 bch_btree_node_write(i
->b
, writes
);
1582 mutex_unlock(&i
->b
->write_lock
);
1583 rw_unlock(true, i
->b
);
1589 static int bch_btree_gc_root(struct btree
*b
, struct btree_op
*op
,
1590 struct closure
*writes
, struct gc_stat
*gc
)
1592 struct btree
*n
= NULL
;
1594 bool should_rewrite
;
1596 should_rewrite
= btree_gc_mark_node(b
, gc
);
1597 if (should_rewrite
) {
1598 n
= btree_node_alloc_replacement(b
, NULL
);
1600 if (!IS_ERR_OR_NULL(n
)) {
1601 bch_btree_node_write_sync(n
);
1603 bch_btree_set_root(n
);
1611 __bch_btree_mark_key(b
->c
, b
->level
+ 1, &b
->key
);
1614 ret
= btree_gc_recurse(b
, op
, writes
, gc
);
1619 bkey_copy_key(&b
->c
->gc_done
, &b
->key
);
1624 static void btree_gc_start(struct cache_set
*c
)
1630 if (!c
->gc_mark_valid
)
1633 mutex_lock(&c
->bucket_lock
);
1635 c
->gc_mark_valid
= 0;
1636 c
->gc_done
= ZERO_KEY
;
1638 for_each_cache(ca
, c
, i
)
1639 for_each_bucket(b
, ca
) {
1640 b
->last_gc
= b
->gen
;
1641 if (!atomic_read(&b
->pin
)) {
1643 SET_GC_SECTORS_USED(b
, 0);
1647 mutex_unlock(&c
->bucket_lock
);
1650 static size_t bch_btree_gc_finish(struct cache_set
*c
)
1652 size_t available
= 0;
1657 mutex_lock(&c
->bucket_lock
);
1660 c
->gc_mark_valid
= 1;
1663 for (i
= 0; i
< KEY_PTRS(&c
->uuid_bucket
); i
++)
1664 SET_GC_MARK(PTR_BUCKET(c
, &c
->uuid_bucket
, i
),
1667 /* don't reclaim buckets to which writeback keys point */
1669 for (i
= 0; i
< c
->nr_uuids
; i
++) {
1670 struct bcache_device
*d
= c
->devices
[i
];
1671 struct cached_dev
*dc
;
1672 struct keybuf_key
*w
, *n
;
1675 if (!d
|| UUID_FLASH_ONLY(&c
->uuids
[i
]))
1677 dc
= container_of(d
, struct cached_dev
, disk
);
1679 spin_lock(&dc
->writeback_keys
.lock
);
1680 rbtree_postorder_for_each_entry_safe(w
, n
,
1681 &dc
->writeback_keys
.keys
, node
)
1682 for (j
= 0; j
< KEY_PTRS(&w
->key
); j
++)
1683 SET_GC_MARK(PTR_BUCKET(c
, &w
->key
, j
),
1685 spin_unlock(&dc
->writeback_keys
.lock
);
1689 for_each_cache(ca
, c
, i
) {
1692 ca
->invalidate_needs_gc
= 0;
1694 for (i
= ca
->sb
.d
; i
< ca
->sb
.d
+ ca
->sb
.keys
; i
++)
1695 SET_GC_MARK(ca
->buckets
+ *i
, GC_MARK_METADATA
);
1697 for (i
= ca
->prio_buckets
;
1698 i
< ca
->prio_buckets
+ prio_buckets(ca
) * 2; i
++)
1699 SET_GC_MARK(ca
->buckets
+ *i
, GC_MARK_METADATA
);
1701 for_each_bucket(b
, ca
) {
1702 c
->need_gc
= max(c
->need_gc
, bucket_gc_gen(b
));
1704 if (atomic_read(&b
->pin
))
1707 BUG_ON(!GC_MARK(b
) && GC_SECTORS_USED(b
));
1709 if (!GC_MARK(b
) || GC_MARK(b
) == GC_MARK_RECLAIMABLE
)
1714 mutex_unlock(&c
->bucket_lock
);
1718 static void bch_btree_gc(struct cache_set
*c
)
1721 unsigned long available
;
1722 struct gc_stat stats
;
1723 struct closure writes
;
1725 uint64_t start_time
= local_clock();
1727 trace_bcache_gc_start(c
);
1729 memset(&stats
, 0, sizeof(struct gc_stat
));
1730 closure_init_stack(&writes
);
1731 bch_btree_op_init(&op
, SHRT_MAX
);
1736 ret
= btree_root(gc_root
, c
, &op
, &writes
, &stats
);
1737 closure_sync(&writes
);
1739 if (ret
&& ret
!= -EAGAIN
)
1740 pr_warn("gc failed!");
1743 available
= bch_btree_gc_finish(c
);
1744 wake_up_allocators(c
);
1746 bch_time_stats_update(&c
->btree_gc_time
, start_time
);
1748 stats
.key_bytes
*= sizeof(uint64_t);
1750 stats
.in_use
= (c
->nbuckets
- available
) * 100 / c
->nbuckets
;
1751 memcpy(&c
->gc_stats
, &stats
, sizeof(struct gc_stat
));
1753 trace_bcache_gc_end(c
);
1758 static int bch_gc_thread(void *arg
)
1760 struct cache_set
*c
= arg
;
1768 set_current_state(TASK_INTERRUPTIBLE
);
1769 if (kthread_should_stop())
1772 mutex_lock(&c
->bucket_lock
);
1774 for_each_cache(ca
, c
, i
)
1775 if (ca
->invalidate_needs_gc
) {
1776 mutex_unlock(&c
->bucket_lock
);
1777 set_current_state(TASK_RUNNING
);
1781 mutex_unlock(&c
->bucket_lock
);
1790 int bch_gc_thread_start(struct cache_set
*c
)
1792 c
->gc_thread
= kthread_create(bch_gc_thread
, c
, "bcache_gc");
1793 if (IS_ERR(c
->gc_thread
))
1794 return PTR_ERR(c
->gc_thread
);
1796 set_task_state(c
->gc_thread
, TASK_INTERRUPTIBLE
);
1800 /* Initial partial gc */
1802 static int bch_btree_check_recurse(struct btree
*b
, struct btree_op
*op
)
1805 struct bkey
*k
, *p
= NULL
;
1806 struct btree_iter iter
;
1808 for_each_key_filter(&b
->keys
, k
, &iter
, bch_ptr_invalid
)
1809 bch_initial_mark_key(b
->c
, b
->level
, k
);
1811 bch_initial_mark_key(b
->c
, b
->level
+ 1, &b
->key
);
1814 bch_btree_iter_init(&b
->keys
, &iter
, NULL
);
1817 k
= bch_btree_iter_next_filter(&iter
, &b
->keys
,
1820 btree_node_prefetch(b
->c
, k
, b
->level
- 1);
1823 ret
= btree(check_recurse
, p
, b
, op
);
1826 } while (p
&& !ret
);
1832 int bch_btree_check(struct cache_set
*c
)
1836 bch_btree_op_init(&op
, SHRT_MAX
);
1838 return btree_root(check_recurse
, c
, &op
);
1841 void bch_initial_gc_finish(struct cache_set
*c
)
1847 bch_btree_gc_finish(c
);
1849 mutex_lock(&c
->bucket_lock
);
1852 * We need to put some unused buckets directly on the prio freelist in
1853 * order to get the allocator thread started - it needs freed buckets in
1854 * order to rewrite the prios and gens, and it needs to rewrite prios
1855 * and gens in order to free buckets.
1857 * This is only safe for buckets that have no live data in them, which
1858 * there should always be some of.
1860 for_each_cache(ca
, c
, i
) {
1861 for_each_bucket(b
, ca
) {
1862 if (fifo_full(&ca
->free
[RESERVE_PRIO
]))
1865 if (bch_can_invalidate_bucket(ca
, b
) &&
1867 __bch_invalidate_one_bucket(ca
, b
);
1868 fifo_push(&ca
->free
[RESERVE_PRIO
],
1874 mutex_unlock(&c
->bucket_lock
);
1877 /* Btree insertion */
1879 static bool btree_insert_key(struct btree
*b
, struct bkey
*k
,
1880 struct bkey
*replace_key
)
1884 BUG_ON(bkey_cmp(k
, &b
->key
) > 0);
1886 status
= bch_btree_insert_key(&b
->keys
, k
, replace_key
);
1887 if (status
!= BTREE_INSERT_STATUS_NO_INSERT
) {
1888 bch_check_keys(&b
->keys
, "%u for %s", status
,
1889 replace_key
? "replace" : "insert");
1891 trace_bcache_btree_insert_key(b
, k
, replace_key
!= NULL
,
1898 static size_t insert_u64s_remaining(struct btree
*b
)
1900 long ret
= bch_btree_keys_u64s_remaining(&b
->keys
);
1903 * Might land in the middle of an existing extent and have to split it
1905 if (b
->keys
.ops
->is_extents
)
1906 ret
-= KEY_MAX_U64S
;
1908 return max(ret
, 0L);
1911 static bool bch_btree_insert_keys(struct btree
*b
, struct btree_op
*op
,
1912 struct keylist
*insert_keys
,
1913 struct bkey
*replace_key
)
1916 int oldsize
= bch_count_data(&b
->keys
);
1918 while (!bch_keylist_empty(insert_keys
)) {
1919 struct bkey
*k
= insert_keys
->keys
;
1921 if (bkey_u64s(k
) > insert_u64s_remaining(b
))
1924 if (bkey_cmp(k
, &b
->key
) <= 0) {
1928 ret
|= btree_insert_key(b
, k
, replace_key
);
1929 bch_keylist_pop_front(insert_keys
);
1930 } else if (bkey_cmp(&START_KEY(k
), &b
->key
) < 0) {
1931 BKEY_PADDED(key
) temp
;
1932 bkey_copy(&temp
.key
, insert_keys
->keys
);
1934 bch_cut_back(&b
->key
, &temp
.key
);
1935 bch_cut_front(&b
->key
, insert_keys
->keys
);
1937 ret
|= btree_insert_key(b
, &temp
.key
, replace_key
);
1945 op
->insert_collision
= true;
1947 BUG_ON(!bch_keylist_empty(insert_keys
) && b
->level
);
1949 BUG_ON(bch_count_data(&b
->keys
) < oldsize
);
1953 static int btree_split(struct btree
*b
, struct btree_op
*op
,
1954 struct keylist
*insert_keys
,
1955 struct bkey
*replace_key
)
1958 struct btree
*n1
, *n2
= NULL
, *n3
= NULL
;
1959 uint64_t start_time
= local_clock();
1961 struct keylist parent_keys
;
1963 closure_init_stack(&cl
);
1964 bch_keylist_init(&parent_keys
);
1966 if (btree_check_reserve(b
, op
)) {
1970 WARN(1, "insufficient reserve for split\n");
1973 n1
= btree_node_alloc_replacement(b
, op
);
1977 split
= set_blocks(btree_bset_first(n1
),
1978 block_bytes(n1
->c
)) > (btree_blocks(b
) * 4) / 5;
1983 trace_bcache_btree_node_split(b
, btree_bset_first(n1
)->keys
);
1985 n2
= bch_btree_node_alloc(b
->c
, op
, b
->level
);
1990 n3
= bch_btree_node_alloc(b
->c
, op
, b
->level
+ 1);
1995 mutex_lock(&n1
->write_lock
);
1996 mutex_lock(&n2
->write_lock
);
1998 bch_btree_insert_keys(n1
, op
, insert_keys
, replace_key
);
2001 * Has to be a linear search because we don't have an auxiliary
2005 while (keys
< (btree_bset_first(n1
)->keys
* 3) / 5)
2006 keys
+= bkey_u64s(bset_bkey_idx(btree_bset_first(n1
),
2009 bkey_copy_key(&n1
->key
,
2010 bset_bkey_idx(btree_bset_first(n1
), keys
));
2011 keys
+= bkey_u64s(bset_bkey_idx(btree_bset_first(n1
), keys
));
2013 btree_bset_first(n2
)->keys
= btree_bset_first(n1
)->keys
- keys
;
2014 btree_bset_first(n1
)->keys
= keys
;
2016 memcpy(btree_bset_first(n2
)->start
,
2017 bset_bkey_last(btree_bset_first(n1
)),
2018 btree_bset_first(n2
)->keys
* sizeof(uint64_t));
2020 bkey_copy_key(&n2
->key
, &b
->key
);
2022 bch_keylist_add(&parent_keys
, &n2
->key
);
2023 bch_btree_node_write(n2
, &cl
);
2024 mutex_unlock(&n2
->write_lock
);
2025 rw_unlock(true, n2
);
2027 trace_bcache_btree_node_compact(b
, btree_bset_first(n1
)->keys
);
2029 mutex_lock(&n1
->write_lock
);
2030 bch_btree_insert_keys(n1
, op
, insert_keys
, replace_key
);
2033 bch_keylist_add(&parent_keys
, &n1
->key
);
2034 bch_btree_node_write(n1
, &cl
);
2035 mutex_unlock(&n1
->write_lock
);
2038 /* Depth increases, make a new root */
2039 mutex_lock(&n3
->write_lock
);
2040 bkey_copy_key(&n3
->key
, &MAX_KEY
);
2041 bch_btree_insert_keys(n3
, op
, &parent_keys
, NULL
);
2042 bch_btree_node_write(n3
, &cl
);
2043 mutex_unlock(&n3
->write_lock
);
2046 bch_btree_set_root(n3
);
2047 rw_unlock(true, n3
);
2048 } else if (!b
->parent
) {
2049 /* Root filled up but didn't need to be split */
2051 bch_btree_set_root(n1
);
2053 /* Split a non root node */
2055 make_btree_freeing_key(b
, parent_keys
.top
);
2056 bch_keylist_push(&parent_keys
);
2058 bch_btree_insert_node(b
->parent
, op
, &parent_keys
, NULL
, NULL
);
2059 BUG_ON(!bch_keylist_empty(&parent_keys
));
2063 rw_unlock(true, n1
);
2065 bch_time_stats_update(&b
->c
->btree_split_time
, start_time
);
2069 bkey_put(b
->c
, &n2
->key
);
2070 btree_node_free(n2
);
2071 rw_unlock(true, n2
);
2073 bkey_put(b
->c
, &n1
->key
);
2074 btree_node_free(n1
);
2075 rw_unlock(true, n1
);
2077 WARN(1, "bcache: btree split failed (level %u)", b
->level
);
2079 if (n3
== ERR_PTR(-EAGAIN
) ||
2080 n2
== ERR_PTR(-EAGAIN
) ||
2081 n1
== ERR_PTR(-EAGAIN
))
2087 static int bch_btree_insert_node(struct btree
*b
, struct btree_op
*op
,
2088 struct keylist
*insert_keys
,
2089 atomic_t
*journal_ref
,
2090 struct bkey
*replace_key
)
2094 BUG_ON(b
->level
&& replace_key
);
2096 closure_init_stack(&cl
);
2098 mutex_lock(&b
->write_lock
);
2100 if (write_block(b
) != btree_bset_last(b
) &&
2101 b
->keys
.last_set_unwritten
)
2102 bch_btree_init_next(b
); /* just wrote a set */
2104 if (bch_keylist_nkeys(insert_keys
) > insert_u64s_remaining(b
)) {
2105 mutex_unlock(&b
->write_lock
);
2109 BUG_ON(write_block(b
) != btree_bset_last(b
));
2111 if (bch_btree_insert_keys(b
, op
, insert_keys
, replace_key
)) {
2113 bch_btree_leaf_dirty(b
, journal_ref
);
2115 bch_btree_node_write(b
, &cl
);
2118 mutex_unlock(&b
->write_lock
);
2120 /* wait for btree node write if necessary, after unlock */
2125 if (current
->bio_list
) {
2126 op
->lock
= b
->c
->root
->level
+ 1;
2128 } else if (op
->lock
<= b
->c
->root
->level
) {
2129 op
->lock
= b
->c
->root
->level
+ 1;
2132 /* Invalidated all iterators */
2133 int ret
= btree_split(b
, op
, insert_keys
, replace_key
);
2135 if (bch_keylist_empty(insert_keys
))
2143 int bch_btree_insert_check_key(struct btree
*b
, struct btree_op
*op
,
2144 struct bkey
*check_key
)
2147 uint64_t btree_ptr
= b
->key
.ptr
[0];
2148 unsigned long seq
= b
->seq
;
2149 struct keylist insert
;
2150 bool upgrade
= op
->lock
== -1;
2152 bch_keylist_init(&insert
);
2155 rw_unlock(false, b
);
2156 rw_lock(true, b
, b
->level
);
2158 if (b
->key
.ptr
[0] != btree_ptr
||
2163 SET_KEY_PTRS(check_key
, 1);
2164 get_random_bytes(&check_key
->ptr
[0], sizeof(uint64_t));
2166 SET_PTR_DEV(check_key
, 0, PTR_CHECK_DEV
);
2168 bch_keylist_add(&insert
, check_key
);
2170 ret
= bch_btree_insert_node(b
, op
, &insert
, NULL
, NULL
);
2172 BUG_ON(!ret
&& !bch_keylist_empty(&insert
));
2175 downgrade_write(&b
->lock
);
2179 struct btree_insert_op
{
2181 struct keylist
*keys
;
2182 atomic_t
*journal_ref
;
2183 struct bkey
*replace_key
;
2186 static int btree_insert_fn(struct btree_op
*b_op
, struct btree
*b
)
2188 struct btree_insert_op
*op
= container_of(b_op
,
2189 struct btree_insert_op
, op
);
2191 int ret
= bch_btree_insert_node(b
, &op
->op
, op
->keys
,
2192 op
->journal_ref
, op
->replace_key
);
2193 if (ret
&& !bch_keylist_empty(op
->keys
))
2199 int bch_btree_insert(struct cache_set
*c
, struct keylist
*keys
,
2200 atomic_t
*journal_ref
, struct bkey
*replace_key
)
2202 struct btree_insert_op op
;
2205 BUG_ON(current
->bio_list
);
2206 BUG_ON(bch_keylist_empty(keys
));
2208 bch_btree_op_init(&op
.op
, 0);
2210 op
.journal_ref
= journal_ref
;
2211 op
.replace_key
= replace_key
;
2213 while (!ret
&& !bch_keylist_empty(keys
)) {
2215 ret
= bch_btree_map_leaf_nodes(&op
.op
, c
,
2216 &START_KEY(keys
->keys
),
2223 pr_err("error %i", ret
);
2225 while ((k
= bch_keylist_pop(keys
)))
2227 } else if (op
.op
.insert_collision
)
2233 void bch_btree_set_root(struct btree
*b
)
2238 closure_init_stack(&cl
);
2240 trace_bcache_btree_set_root(b
);
2242 BUG_ON(!b
->written
);
2244 for (i
= 0; i
< KEY_PTRS(&b
->key
); i
++)
2245 BUG_ON(PTR_BUCKET(b
->c
, &b
->key
, i
)->prio
!= BTREE_PRIO
);
2247 mutex_lock(&b
->c
->bucket_lock
);
2248 list_del_init(&b
->list
);
2249 mutex_unlock(&b
->c
->bucket_lock
);
2253 bch_journal_meta(b
->c
, &cl
);
2257 /* Map across nodes or keys */
2259 static int bch_btree_map_nodes_recurse(struct btree
*b
, struct btree_op
*op
,
2261 btree_map_nodes_fn
*fn
, int flags
)
2263 int ret
= MAP_CONTINUE
;
2267 struct btree_iter iter
;
2269 bch_btree_iter_init(&b
->keys
, &iter
, from
);
2271 while ((k
= bch_btree_iter_next_filter(&iter
, &b
->keys
,
2273 ret
= btree(map_nodes_recurse
, k
, b
,
2274 op
, from
, fn
, flags
);
2277 if (ret
!= MAP_CONTINUE
)
2282 if (!b
->level
|| flags
== MAP_ALL_NODES
)
2288 int __bch_btree_map_nodes(struct btree_op
*op
, struct cache_set
*c
,
2289 struct bkey
*from
, btree_map_nodes_fn
*fn
, int flags
)
2291 return btree_root(map_nodes_recurse
, c
, op
, from
, fn
, flags
);
2294 static int bch_btree_map_keys_recurse(struct btree
*b
, struct btree_op
*op
,
2295 struct bkey
*from
, btree_map_keys_fn
*fn
,
2298 int ret
= MAP_CONTINUE
;
2300 struct btree_iter iter
;
2302 bch_btree_iter_init(&b
->keys
, &iter
, from
);
2304 while ((k
= bch_btree_iter_next_filter(&iter
, &b
->keys
, bch_ptr_bad
))) {
2307 : btree(map_keys_recurse
, k
, b
, op
, from
, fn
, flags
);
2310 if (ret
!= MAP_CONTINUE
)
2314 if (!b
->level
&& (flags
& MAP_END_KEY
))
2315 ret
= fn(op
, b
, &KEY(KEY_INODE(&b
->key
),
2316 KEY_OFFSET(&b
->key
), 0));
2321 int bch_btree_map_keys(struct btree_op
*op
, struct cache_set
*c
,
2322 struct bkey
*from
, btree_map_keys_fn
*fn
, int flags
)
2324 return btree_root(map_keys_recurse
, c
, op
, from
, fn
, flags
);
2329 static inline int keybuf_cmp(struct keybuf_key
*l
, struct keybuf_key
*r
)
2331 /* Overlapping keys compare equal */
2332 if (bkey_cmp(&l
->key
, &START_KEY(&r
->key
)) <= 0)
2334 if (bkey_cmp(&START_KEY(&l
->key
), &r
->key
) >= 0)
2339 static inline int keybuf_nonoverlapping_cmp(struct keybuf_key
*l
,
2340 struct keybuf_key
*r
)
2342 return clamp_t(int64_t, bkey_cmp(&l
->key
, &r
->key
), -1, 1);
2350 keybuf_pred_fn
*pred
;
2353 static int refill_keybuf_fn(struct btree_op
*op
, struct btree
*b
,
2356 struct refill
*refill
= container_of(op
, struct refill
, op
);
2357 struct keybuf
*buf
= refill
->buf
;
2358 int ret
= MAP_CONTINUE
;
2360 if (bkey_cmp(k
, refill
->end
) >= 0) {
2365 if (!KEY_SIZE(k
)) /* end key */
2368 if (refill
->pred(buf
, k
)) {
2369 struct keybuf_key
*w
;
2371 spin_lock(&buf
->lock
);
2373 w
= array_alloc(&buf
->freelist
);
2375 spin_unlock(&buf
->lock
);
2380 bkey_copy(&w
->key
, k
);
2382 if (RB_INSERT(&buf
->keys
, w
, node
, keybuf_cmp
))
2383 array_free(&buf
->freelist
, w
);
2387 if (array_freelist_empty(&buf
->freelist
))
2390 spin_unlock(&buf
->lock
);
2393 buf
->last_scanned
= *k
;
2397 void bch_refill_keybuf(struct cache_set
*c
, struct keybuf
*buf
,
2398 struct bkey
*end
, keybuf_pred_fn
*pred
)
2400 struct bkey start
= buf
->last_scanned
;
2401 struct refill refill
;
2405 bch_btree_op_init(&refill
.op
, -1);
2406 refill
.nr_found
= 0;
2411 bch_btree_map_keys(&refill
.op
, c
, &buf
->last_scanned
,
2412 refill_keybuf_fn
, MAP_END_KEY
);
2414 trace_bcache_keyscan(refill
.nr_found
,
2415 KEY_INODE(&start
), KEY_OFFSET(&start
),
2416 KEY_INODE(&buf
->last_scanned
),
2417 KEY_OFFSET(&buf
->last_scanned
));
2419 spin_lock(&buf
->lock
);
2421 if (!RB_EMPTY_ROOT(&buf
->keys
)) {
2422 struct keybuf_key
*w
;
2423 w
= RB_FIRST(&buf
->keys
, struct keybuf_key
, node
);
2424 buf
->start
= START_KEY(&w
->key
);
2426 w
= RB_LAST(&buf
->keys
, struct keybuf_key
, node
);
2429 buf
->start
= MAX_KEY
;
2433 spin_unlock(&buf
->lock
);
2436 static void __bch_keybuf_del(struct keybuf
*buf
, struct keybuf_key
*w
)
2438 rb_erase(&w
->node
, &buf
->keys
);
2439 array_free(&buf
->freelist
, w
);
2442 void bch_keybuf_del(struct keybuf
*buf
, struct keybuf_key
*w
)
2444 spin_lock(&buf
->lock
);
2445 __bch_keybuf_del(buf
, w
);
2446 spin_unlock(&buf
->lock
);
2449 bool bch_keybuf_check_overlapping(struct keybuf
*buf
, struct bkey
*start
,
2453 struct keybuf_key
*p
, *w
, s
;
2456 if (bkey_cmp(end
, &buf
->start
) <= 0 ||
2457 bkey_cmp(start
, &buf
->end
) >= 0)
2460 spin_lock(&buf
->lock
);
2461 w
= RB_GREATER(&buf
->keys
, s
, node
, keybuf_nonoverlapping_cmp
);
2463 while (w
&& bkey_cmp(&START_KEY(&w
->key
), end
) < 0) {
2465 w
= RB_NEXT(w
, node
);
2470 __bch_keybuf_del(buf
, p
);
2473 spin_unlock(&buf
->lock
);
2477 struct keybuf_key
*bch_keybuf_next(struct keybuf
*buf
)
2479 struct keybuf_key
*w
;
2480 spin_lock(&buf
->lock
);
2482 w
= RB_FIRST(&buf
->keys
, struct keybuf_key
, node
);
2484 while (w
&& w
->private)
2485 w
= RB_NEXT(w
, node
);
2488 w
->private = ERR_PTR(-EINTR
);
2490 spin_unlock(&buf
->lock
);
2494 struct keybuf_key
*bch_keybuf_next_rescan(struct cache_set
*c
,
2497 keybuf_pred_fn
*pred
)
2499 struct keybuf_key
*ret
;
2502 ret
= bch_keybuf_next(buf
);
2506 if (bkey_cmp(&buf
->last_scanned
, end
) >= 0) {
2507 pr_debug("scan finished");
2511 bch_refill_keybuf(c
, buf
, end
, pred
);
2517 void bch_keybuf_init(struct keybuf
*buf
)
2519 buf
->last_scanned
= MAX_KEY
;
2520 buf
->keys
= RB_ROOT
;
2522 spin_lock_init(&buf
->lock
);
2523 array_allocator_init(&buf
->freelist
);