1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (C) 2010 Kent Overstreet <kent.overstreet@gmail.com>
5 * Uses a block device as cache for other block devices; optimized for SSDs.
6 * All allocation is done in buckets, which should match the erase block size
9 * Buckets containing cached data are kept on a heap sorted by priority;
10 * bucket priority is increased on cache hit, and periodically all the buckets
11 * on the heap have their priority scaled down. This currently is just used as
12 * an LRU but in the future should allow for more intelligent heuristics.
14 * Buckets have an 8 bit counter; freeing is accomplished by incrementing the
15 * counter. Garbage collection is used to remove stale pointers.
17 * Indexing is done via a btree; nodes are not necessarily fully sorted, rather
18 * as keys are inserted we only sort the pages that have not yet been written.
19 * When garbage collection is run, we resort the entire node.
21 * All configuration is done via sysfs; see Documentation/bcache.txt.
29 #include <linux/slab.h>
30 #include <linux/bitops.h>
31 #include <linux/hash.h>
32 #include <linux/kthread.h>
33 #include <linux/prefetch.h>
34 #include <linux/random.h>
35 #include <linux/rcupdate.h>
36 #include <linux/sched/clock.h>
37 #include <linux/rculist.h>
39 #include <trace/events/bcache.h>
43 * register_bcache: Return errors out to userspace correctly
45 * Writeback: don't undirty key until after a cache flush
47 * Create an iterator for key pointers
49 * On btree write error, mark bucket such that it won't be freed from the cache
52 * Check for bad keys in replay
54 * Refcount journal entries in journal_replay
57 * Finish incremental gc
58 * Gc should free old UUIDs, data for invalid UUIDs
60 * Provide a way to list backing device UUIDs we have data cached for, and
61 * probably how long it's been since we've seen them, and a way to invalidate
62 * dirty data for devices that will never be attached again
64 * Keep 1 min/5 min/15 min statistics of how busy a block device has been, so
65 * that based on that and how much dirty data we have we can keep writeback
68 * Add a tracepoint or somesuch to watch for writeback starvation
70 * When btree depth > 1 and splitting an interior node, we have to make sure
71 * alloc_bucket() cannot fail. This should be true but is not completely
76 * If data write is less than hard sector size of ssd, round up offset in open
77 * bucket to the next whole sector
79 * Superblock needs to be fleshed out for multiple cache devices
81 * Add a sysfs tunable for the number of writeback IOs in flight
83 * Add a sysfs tunable for the number of open data buckets
85 * IO tracking: Can we track when one process is doing io on behalf of another?
86 * IO tracking: Don't use just an average, weigh more recent stuff higher
88 * Test module load/unload
91 #define MAX_NEED_GC 64
92 #define MAX_SAVE_PRIO 72
94 #define PTR_DIRTY_BIT (((uint64_t) 1 << 36))
96 #define PTR_HASH(c, k) \
97 (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0))
99 #define insert_lock(s, b) ((b)->level <= (s)->lock)
102 * These macros are for recursing down the btree - they handle the details of
103 * locking and looking up nodes in the cache for you. They're best treated as
104 * mere syntax when reading code that uses them.
106 * op->lock determines whether we take a read or a write lock at a given depth.
107 * If you've got a read lock and find that you need a write lock (i.e. you're
108 * going to have to split), set op->lock and return -EINTR; btree_root() will
109 * call you again and you'll have the correct lock.
113 * btree - recurse down the btree on a specified key
114 * @fn: function to call, which will be passed the child node
115 * @key: key to recurse on
116 * @b: parent btree node
117 * @op: pointer to struct btree_op
119 #define btree(fn, key, b, op, ...) \
121 int _r, l = (b)->level - 1; \
122 bool _w = l <= (op)->lock; \
123 struct btree *_child = bch_btree_node_get((b)->c, op, key, l, \
125 if (!IS_ERR(_child)) { \
126 _r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__); \
127 rw_unlock(_w, _child); \
129 _r = PTR_ERR(_child); \
134 * btree_root - call a function on the root of the btree
135 * @fn: function to call, which will be passed the child node
137 * @op: pointer to struct btree_op
139 #define btree_root(fn, c, op, ...) \
143 struct btree *_b = (c)->root; \
144 bool _w = insert_lock(op, _b); \
145 rw_lock(_w, _b, _b->level); \
146 if (_b == (c)->root && \
147 _w == insert_lock(op, _b)) { \
148 _r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__); \
151 bch_cannibalize_unlock(c); \
154 } while (_r == -EINTR); \
156 finish_wait(&(c)->btree_cache_wait, &(op)->wait); \
160 static inline struct bset
*write_block(struct btree
*b
)
162 return ((void *) btree_bset_first(b
)) + b
->written
* block_bytes(b
->c
);
165 static void bch_btree_init_next(struct btree
*b
)
167 /* If not a leaf node, always sort */
168 if (b
->level
&& b
->keys
.nsets
)
169 bch_btree_sort(&b
->keys
, &b
->c
->sort
);
171 bch_btree_sort_lazy(&b
->keys
, &b
->c
->sort
);
173 if (b
->written
< btree_blocks(b
))
174 bch_bset_init_next(&b
->keys
, write_block(b
),
175 bset_magic(&b
->c
->sb
));
179 /* Btree key manipulation */
181 void bkey_put(struct cache_set
*c
, struct bkey
*k
)
185 for (i
= 0; i
< KEY_PTRS(k
); i
++)
186 if (ptr_available(c
, k
, i
))
187 atomic_dec_bug(&PTR_BUCKET(c
, k
, i
)->pin
);
192 static uint64_t btree_csum_set(struct btree
*b
, struct bset
*i
)
194 uint64_t crc
= b
->key
.ptr
[0];
195 void *data
= (void *) i
+ 8, *end
= bset_bkey_last(i
);
197 crc
= bch_crc64_update(crc
, data
, end
- data
);
198 return crc
^ 0xffffffffffffffffULL
;
201 void bch_btree_node_read_done(struct btree
*b
)
203 const char *err
= "bad btree header";
204 struct bset
*i
= btree_bset_first(b
);
205 struct btree_iter
*iter
;
207 iter
= mempool_alloc(b
->c
->fill_iter
, GFP_NOIO
);
208 iter
->size
= b
->c
->sb
.bucket_size
/ b
->c
->sb
.block_size
;
211 #ifdef CONFIG_BCACHE_DEBUG
219 b
->written
< btree_blocks(b
) && i
->seq
== b
->keys
.set
[0].data
->seq
;
220 i
= write_block(b
)) {
221 err
= "unsupported bset version";
222 if (i
->version
> BCACHE_BSET_VERSION
)
225 err
= "bad btree header";
226 if (b
->written
+ set_blocks(i
, block_bytes(b
->c
)) >
231 if (i
->magic
!= bset_magic(&b
->c
->sb
))
234 err
= "bad checksum";
235 switch (i
->version
) {
237 if (i
->csum
!= csum_set(i
))
240 case BCACHE_BSET_VERSION
:
241 if (i
->csum
!= btree_csum_set(b
, i
))
247 if (i
!= b
->keys
.set
[0].data
&& !i
->keys
)
250 bch_btree_iter_push(iter
, i
->start
, bset_bkey_last(i
));
252 b
->written
+= set_blocks(i
, block_bytes(b
->c
));
255 err
= "corrupted btree";
256 for (i
= write_block(b
);
257 bset_sector_offset(&b
->keys
, i
) < KEY_SIZE(&b
->key
);
258 i
= ((void *) i
) + block_bytes(b
->c
))
259 if (i
->seq
== b
->keys
.set
[0].data
->seq
)
262 bch_btree_sort_and_fix_extents(&b
->keys
, iter
, &b
->c
->sort
);
264 i
= b
->keys
.set
[0].data
;
265 err
= "short btree key";
266 if (b
->keys
.set
[0].size
&&
267 bkey_cmp(&b
->key
, &b
->keys
.set
[0].end
) < 0)
270 if (b
->written
< btree_blocks(b
))
271 bch_bset_init_next(&b
->keys
, write_block(b
),
272 bset_magic(&b
->c
->sb
));
274 mempool_free(iter
, b
->c
->fill_iter
);
277 set_btree_node_io_error(b
);
278 bch_cache_set_error(b
->c
, "%s at bucket %zu, block %u, %u keys",
279 err
, PTR_BUCKET_NR(b
->c
, &b
->key
, 0),
280 bset_block_offset(b
, i
), i
->keys
);
284 static void btree_node_read_endio(struct bio
*bio
)
286 struct closure
*cl
= bio
->bi_private
;
290 static void bch_btree_node_read(struct btree
*b
)
292 uint64_t start_time
= local_clock();
296 trace_bcache_btree_read(b
);
298 closure_init_stack(&cl
);
300 bio
= bch_bbio_alloc(b
->c
);
301 bio
->bi_iter
.bi_size
= KEY_SIZE(&b
->key
) << 9;
302 bio
->bi_end_io
= btree_node_read_endio
;
303 bio
->bi_private
= &cl
;
304 bio
->bi_opf
= REQ_OP_READ
| REQ_META
;
306 bch_bio_map(bio
, b
->keys
.set
[0].data
);
308 bch_submit_bbio(bio
, b
->c
, &b
->key
, 0);
312 set_btree_node_io_error(b
);
314 bch_bbio_free(bio
, b
->c
);
316 if (btree_node_io_error(b
))
319 bch_btree_node_read_done(b
);
320 bch_time_stats_update(&b
->c
->btree_read_time
, start_time
);
324 bch_cache_set_error(b
->c
, "io error reading bucket %zu",
325 PTR_BUCKET_NR(b
->c
, &b
->key
, 0));
328 static void btree_complete_write(struct btree
*b
, struct btree_write
*w
)
330 if (w
->prio_blocked
&&
331 !atomic_sub_return(w
->prio_blocked
, &b
->c
->prio_blocked
))
332 wake_up_allocators(b
->c
);
335 atomic_dec_bug(w
->journal
);
336 __closure_wake_up(&b
->c
->journal
.wait
);
343 static void btree_node_write_unlock(struct closure
*cl
)
345 struct btree
*b
= container_of(cl
, struct btree
, io
);
350 static void __btree_node_write_done(struct closure
*cl
)
352 struct btree
*b
= container_of(cl
, struct btree
, io
);
353 struct btree_write
*w
= btree_prev_write(b
);
355 bch_bbio_free(b
->bio
, b
->c
);
357 btree_complete_write(b
, w
);
359 if (btree_node_dirty(b
))
360 schedule_delayed_work(&b
->work
, 30 * HZ
);
362 closure_return_with_destructor(cl
, btree_node_write_unlock
);
365 static void btree_node_write_done(struct closure
*cl
)
367 struct btree
*b
= container_of(cl
, struct btree
, io
);
369 bio_free_pages(b
->bio
);
370 __btree_node_write_done(cl
);
373 static void btree_node_write_endio(struct bio
*bio
)
375 struct closure
*cl
= bio
->bi_private
;
376 struct btree
*b
= container_of(cl
, struct btree
, io
);
379 set_btree_node_io_error(b
);
381 bch_bbio_count_io_errors(b
->c
, bio
, bio
->bi_status
, "writing btree");
385 static void do_btree_node_write(struct btree
*b
)
387 struct closure
*cl
= &b
->io
;
388 struct bset
*i
= btree_bset_last(b
);
391 i
->version
= BCACHE_BSET_VERSION
;
392 i
->csum
= btree_csum_set(b
, i
);
395 b
->bio
= bch_bbio_alloc(b
->c
);
397 b
->bio
->bi_end_io
= btree_node_write_endio
;
398 b
->bio
->bi_private
= cl
;
399 b
->bio
->bi_iter
.bi_size
= roundup(set_bytes(i
), block_bytes(b
->c
));
400 b
->bio
->bi_opf
= REQ_OP_WRITE
| REQ_META
| REQ_FUA
;
401 bch_bio_map(b
->bio
, i
);
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.
408 * Similarly if we're writing a new btree root - the pointer is going to
409 * be in the next journal entry.
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.
418 bkey_copy(&k
.key
, &b
->key
);
419 SET_PTR_OFFSET(&k
.key
, 0, PTR_OFFSET(&k
.key
, 0) +
420 bset_sector_offset(&b
->keys
, i
));
422 if (!bio_alloc_pages(b
->bio
, __GFP_NOWARN
|GFP_NOWAIT
)) {
425 void *base
= (void *) ((unsigned long) i
& ~(PAGE_SIZE
- 1));
427 bio_for_each_segment_all(bv
, b
->bio
, j
)
428 memcpy(page_address(bv
->bv_page
),
429 base
+ j
* PAGE_SIZE
, PAGE_SIZE
);
431 bch_submit_bbio(b
->bio
, b
->c
, &k
.key
, 0);
433 continue_at(cl
, btree_node_write_done
, NULL
);
436 bch_bio_map(b
->bio
, i
);
438 bch_submit_bbio(b
->bio
, b
->c
, &k
.key
, 0);
441 continue_at_nobarrier(cl
, __btree_node_write_done
, NULL
);
445 void __bch_btree_node_write(struct btree
*b
, struct closure
*parent
)
447 struct bset
*i
= btree_bset_last(b
);
449 lockdep_assert_held(&b
->write_lock
);
451 trace_bcache_btree_write(b
);
453 BUG_ON(current
->bio_list
);
454 BUG_ON(b
->written
>= btree_blocks(b
));
455 BUG_ON(b
->written
&& !i
->keys
);
456 BUG_ON(btree_bset_first(b
)->seq
!= i
->seq
);
457 bch_check_keys(&b
->keys
, "writing");
459 cancel_delayed_work(&b
->work
);
461 /* If caller isn't waiting for write, parent refcount is cache set */
463 closure_init(&b
->io
, parent
?: &b
->c
->cl
);
465 clear_bit(BTREE_NODE_dirty
, &b
->flags
);
466 change_bit(BTREE_NODE_write_idx
, &b
->flags
);
468 do_btree_node_write(b
);
470 atomic_long_add(set_blocks(i
, block_bytes(b
->c
)) * b
->c
->sb
.block_size
,
471 &PTR_CACHE(b
->c
, &b
->key
, 0)->btree_sectors_written
);
473 b
->written
+= set_blocks(i
, block_bytes(b
->c
));
476 void bch_btree_node_write(struct btree
*b
, struct closure
*parent
)
478 unsigned nsets
= b
->keys
.nsets
;
480 lockdep_assert_held(&b
->lock
);
482 __bch_btree_node_write(b
, parent
);
485 * do verify if there was more than one set initially (i.e. we did a
486 * sort) and we sorted down to a single set:
488 if (nsets
&& !b
->keys
.nsets
)
491 bch_btree_init_next(b
);
494 static void bch_btree_node_write_sync(struct btree
*b
)
498 closure_init_stack(&cl
);
500 mutex_lock(&b
->write_lock
);
501 bch_btree_node_write(b
, &cl
);
502 mutex_unlock(&b
->write_lock
);
507 static void btree_node_write_work(struct work_struct
*w
)
509 struct btree
*b
= container_of(to_delayed_work(w
), struct btree
, work
);
511 mutex_lock(&b
->write_lock
);
512 if (btree_node_dirty(b
))
513 __bch_btree_node_write(b
, NULL
);
514 mutex_unlock(&b
->write_lock
);
517 static void bch_btree_leaf_dirty(struct btree
*b
, atomic_t
*journal_ref
)
519 struct bset
*i
= btree_bset_last(b
);
520 struct btree_write
*w
= btree_current_write(b
);
522 lockdep_assert_held(&b
->write_lock
);
527 if (!btree_node_dirty(b
))
528 schedule_delayed_work(&b
->work
, 30 * HZ
);
530 set_btree_node_dirty(b
);
534 journal_pin_cmp(b
->c
, w
->journal
, journal_ref
)) {
535 atomic_dec_bug(w
->journal
);
540 w
->journal
= journal_ref
;
541 atomic_inc(w
->journal
);
545 /* Force write if set is too big */
546 if (set_bytes(i
) > PAGE_SIZE
- 48 &&
548 bch_btree_node_write(b
, NULL
);
552 * Btree in memory cache - allocation/freeing
553 * mca -> memory cache
556 #define mca_reserve(c) (((c->root && c->root->level) \
557 ? c->root->level : 1) * 8 + 16)
558 #define mca_can_free(c) \
559 max_t(int, 0, c->btree_cache_used - mca_reserve(c))
561 static void mca_data_free(struct btree
*b
)
563 BUG_ON(b
->io_mutex
.count
!= 1);
565 bch_btree_keys_free(&b
->keys
);
567 b
->c
->btree_cache_used
--;
568 list_move(&b
->list
, &b
->c
->btree_cache_freed
);
571 static void mca_bucket_free(struct btree
*b
)
573 BUG_ON(btree_node_dirty(b
));
576 hlist_del_init_rcu(&b
->hash
);
577 list_move(&b
->list
, &b
->c
->btree_cache_freeable
);
580 static unsigned btree_order(struct bkey
*k
)
582 return ilog2(KEY_SIZE(k
) / PAGE_SECTORS
?: 1);
585 static void mca_data_alloc(struct btree
*b
, struct bkey
*k
, gfp_t gfp
)
587 if (!bch_btree_keys_alloc(&b
->keys
,
589 ilog2(b
->c
->btree_pages
),
592 b
->c
->btree_cache_used
++;
593 list_move(&b
->list
, &b
->c
->btree_cache
);
595 list_move(&b
->list
, &b
->c
->btree_cache_freed
);
599 static struct btree
*mca_bucket_alloc(struct cache_set
*c
,
600 struct bkey
*k
, gfp_t gfp
)
602 struct btree
*b
= kzalloc(sizeof(struct btree
), gfp
);
606 init_rwsem(&b
->lock
);
607 lockdep_set_novalidate_class(&b
->lock
);
608 mutex_init(&b
->write_lock
);
609 lockdep_set_novalidate_class(&b
->write_lock
);
610 INIT_LIST_HEAD(&b
->list
);
611 INIT_DELAYED_WORK(&b
->work
, btree_node_write_work
);
613 sema_init(&b
->io_mutex
, 1);
615 mca_data_alloc(b
, k
, gfp
);
619 static int mca_reap(struct btree
*b
, unsigned min_order
, bool flush
)
623 closure_init_stack(&cl
);
624 lockdep_assert_held(&b
->c
->bucket_lock
);
626 if (!down_write_trylock(&b
->lock
))
629 BUG_ON(btree_node_dirty(b
) && !b
->keys
.set
[0].data
);
631 if (b
->keys
.page_order
< min_order
)
635 if (btree_node_dirty(b
))
638 if (down_trylock(&b
->io_mutex
))
643 mutex_lock(&b
->write_lock
);
644 if (btree_node_dirty(b
))
645 __bch_btree_node_write(b
, &cl
);
646 mutex_unlock(&b
->write_lock
);
650 /* wait for any in flight btree write */
660 static unsigned long bch_mca_scan(struct shrinker
*shrink
,
661 struct shrink_control
*sc
)
663 struct cache_set
*c
= container_of(shrink
, struct cache_set
, shrink
);
665 unsigned long i
, nr
= sc
->nr_to_scan
;
666 unsigned long freed
= 0;
668 if (c
->shrinker_disabled
)
671 if (c
->btree_cache_alloc_lock
)
674 /* Return -1 if we can't do anything right now */
675 if (sc
->gfp_mask
& __GFP_IO
)
676 mutex_lock(&c
->bucket_lock
);
677 else if (!mutex_trylock(&c
->bucket_lock
))
681 * It's _really_ critical that we don't free too many btree nodes - we
682 * have to always leave ourselves a reserve. The reserve is how we
683 * guarantee that allocating memory for a new btree node can always
684 * succeed, so that inserting keys into the btree can always succeed and
685 * IO can always make forward progress:
687 nr
/= c
->btree_pages
;
688 nr
= min_t(unsigned long, nr
, mca_can_free(c
));
691 list_for_each_entry_safe(b
, t
, &c
->btree_cache_freeable
, list
) {
696 !mca_reap(b
, 0, false)) {
703 for (i
= 0; (nr
--) && i
< c
->btree_cache_used
; i
++) {
704 if (list_empty(&c
->btree_cache
))
707 b
= list_first_entry(&c
->btree_cache
, struct btree
, list
);
708 list_rotate_left(&c
->btree_cache
);
711 !mca_reap(b
, 0, false)) {
720 mutex_unlock(&c
->bucket_lock
);
724 static unsigned long bch_mca_count(struct shrinker
*shrink
,
725 struct shrink_control
*sc
)
727 struct cache_set
*c
= container_of(shrink
, struct cache_set
, shrink
);
729 if (c
->shrinker_disabled
)
732 if (c
->btree_cache_alloc_lock
)
735 return mca_can_free(c
) * c
->btree_pages
;
738 void bch_btree_cache_free(struct cache_set
*c
)
742 closure_init_stack(&cl
);
744 if (c
->shrink
.list
.next
)
745 unregister_shrinker(&c
->shrink
);
747 mutex_lock(&c
->bucket_lock
);
749 #ifdef CONFIG_BCACHE_DEBUG
751 list_move(&c
->verify_data
->list
, &c
->btree_cache
);
753 free_pages((unsigned long) c
->verify_ondisk
, ilog2(bucket_pages(c
)));
756 list_splice(&c
->btree_cache_freeable
,
759 while (!list_empty(&c
->btree_cache
)) {
760 b
= list_first_entry(&c
->btree_cache
, struct btree
, list
);
762 if (btree_node_dirty(b
))
763 btree_complete_write(b
, btree_current_write(b
));
764 clear_bit(BTREE_NODE_dirty
, &b
->flags
);
769 while (!list_empty(&c
->btree_cache_freed
)) {
770 b
= list_first_entry(&c
->btree_cache_freed
,
773 cancel_delayed_work_sync(&b
->work
);
777 mutex_unlock(&c
->bucket_lock
);
780 int bch_btree_cache_alloc(struct cache_set
*c
)
784 for (i
= 0; i
< mca_reserve(c
); i
++)
785 if (!mca_bucket_alloc(c
, &ZERO_KEY
, GFP_KERNEL
))
788 list_splice_init(&c
->btree_cache
,
789 &c
->btree_cache_freeable
);
791 #ifdef CONFIG_BCACHE_DEBUG
792 mutex_init(&c
->verify_lock
);
794 c
->verify_ondisk
= (void *)
795 __get_free_pages(GFP_KERNEL
, ilog2(bucket_pages(c
)));
797 c
->verify_data
= mca_bucket_alloc(c
, &ZERO_KEY
, GFP_KERNEL
);
799 if (c
->verify_data
&&
800 c
->verify_data
->keys
.set
->data
)
801 list_del_init(&c
->verify_data
->list
);
803 c
->verify_data
= NULL
;
806 c
->shrink
.count_objects
= bch_mca_count
;
807 c
->shrink
.scan_objects
= bch_mca_scan
;
809 c
->shrink
.batch
= c
->btree_pages
* 2;
810 register_shrinker(&c
->shrink
);
815 /* Btree in memory cache - hash table */
817 static struct hlist_head
*mca_hash(struct cache_set
*c
, struct bkey
*k
)
819 return &c
->bucket_hash
[hash_32(PTR_HASH(c
, k
), BUCKET_HASH_BITS
)];
822 static struct btree
*mca_find(struct cache_set
*c
, struct bkey
*k
)
827 hlist_for_each_entry_rcu(b
, mca_hash(c
, k
), hash
)
828 if (PTR_HASH(c
, &b
->key
) == PTR_HASH(c
, k
))
836 static int mca_cannibalize_lock(struct cache_set
*c
, struct btree_op
*op
)
838 struct task_struct
*old
;
840 old
= cmpxchg(&c
->btree_cache_alloc_lock
, NULL
, current
);
841 if (old
&& old
!= current
) {
843 prepare_to_wait(&c
->btree_cache_wait
, &op
->wait
,
844 TASK_UNINTERRUPTIBLE
);
851 static struct btree
*mca_cannibalize(struct cache_set
*c
, struct btree_op
*op
,
856 trace_bcache_btree_cache_cannibalize(c
);
858 if (mca_cannibalize_lock(c
, op
))
859 return ERR_PTR(-EINTR
);
861 list_for_each_entry_reverse(b
, &c
->btree_cache
, list
)
862 if (!mca_reap(b
, btree_order(k
), false))
865 list_for_each_entry_reverse(b
, &c
->btree_cache
, list
)
866 if (!mca_reap(b
, btree_order(k
), true))
869 WARN(1, "btree cache cannibalize failed\n");
870 return ERR_PTR(-ENOMEM
);
874 * We can only have one thread cannibalizing other cached btree nodes at a time,
875 * or we'll deadlock. We use an open coded mutex to ensure that, which a
876 * cannibalize_bucket() will take. This means every time we unlock the root of
877 * the btree, we need to release this lock if we have it held.
879 static void bch_cannibalize_unlock(struct cache_set
*c
)
881 if (c
->btree_cache_alloc_lock
== current
) {
882 c
->btree_cache_alloc_lock
= NULL
;
883 wake_up(&c
->btree_cache_wait
);
887 static struct btree
*mca_alloc(struct cache_set
*c
, struct btree_op
*op
,
888 struct bkey
*k
, int level
)
892 BUG_ON(current
->bio_list
);
894 lockdep_assert_held(&c
->bucket_lock
);
899 /* btree_free() doesn't free memory; it sticks the node on the end of
900 * the list. Check if there's any freed nodes there:
902 list_for_each_entry(b
, &c
->btree_cache_freeable
, list
)
903 if (!mca_reap(b
, btree_order(k
), false))
906 /* We never free struct btree itself, just the memory that holds the on
907 * disk node. Check the freed list before allocating a new one:
909 list_for_each_entry(b
, &c
->btree_cache_freed
, list
)
910 if (!mca_reap(b
, 0, false)) {
911 mca_data_alloc(b
, k
, __GFP_NOWARN
|GFP_NOIO
);
912 if (!b
->keys
.set
[0].data
)
918 b
= mca_bucket_alloc(c
, k
, __GFP_NOWARN
|GFP_NOIO
);
922 BUG_ON(!down_write_trylock(&b
->lock
));
923 if (!b
->keys
.set
->data
)
926 BUG_ON(b
->io_mutex
.count
!= 1);
928 bkey_copy(&b
->key
, k
);
929 list_move(&b
->list
, &c
->btree_cache
);
930 hlist_del_init_rcu(&b
->hash
);
931 hlist_add_head_rcu(&b
->hash
, mca_hash(c
, k
));
933 lock_set_subclass(&b
->lock
.dep_map
, level
+ 1, _THIS_IP_
);
934 b
->parent
= (void *) ~0UL;
940 bch_btree_keys_init(&b
->keys
, &bch_extent_keys_ops
,
941 &b
->c
->expensive_debug_checks
);
943 bch_btree_keys_init(&b
->keys
, &bch_btree_keys_ops
,
944 &b
->c
->expensive_debug_checks
);
951 b
= mca_cannibalize(c
, op
, k
);
959 * bch_btree_node_get - find a btree node in the cache and lock it, reading it
960 * in from disk if necessary.
962 * If IO is necessary and running under generic_make_request, returns -EAGAIN.
964 * The btree node will have either a read or a write lock held, depending on
965 * level and op->lock.
967 struct btree
*bch_btree_node_get(struct cache_set
*c
, struct btree_op
*op
,
968 struct bkey
*k
, int level
, bool write
,
969 struct btree
*parent
)
979 if (current
->bio_list
)
980 return ERR_PTR(-EAGAIN
);
982 mutex_lock(&c
->bucket_lock
);
983 b
= mca_alloc(c
, op
, k
, level
);
984 mutex_unlock(&c
->bucket_lock
);
991 bch_btree_node_read(b
);
994 downgrade_write(&b
->lock
);
996 rw_lock(write
, b
, level
);
997 if (PTR_HASH(c
, &b
->key
) != PTR_HASH(c
, k
)) {
1001 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 btree
*parent
, struct bkey
*k
)
1029 mutex_lock(&parent
->c
->bucket_lock
);
1030 b
= mca_alloc(parent
->c
, NULL
, k
, parent
->level
- 1);
1031 mutex_unlock(&parent
->c
->bucket_lock
);
1033 if (!IS_ERR_OR_NULL(b
)) {
1035 bch_btree_node_read(b
);
1042 static void btree_node_free(struct btree
*b
)
1044 trace_bcache_btree_node_free(b
);
1046 BUG_ON(b
== b
->c
->root
);
1048 mutex_lock(&b
->write_lock
);
1050 if (btree_node_dirty(b
))
1051 btree_complete_write(b
, btree_current_write(b
));
1052 clear_bit(BTREE_NODE_dirty
, &b
->flags
);
1054 mutex_unlock(&b
->write_lock
);
1056 cancel_delayed_work(&b
->work
);
1058 mutex_lock(&b
->c
->bucket_lock
);
1059 bch_bucket_free(b
->c
, &b
->key
);
1061 mutex_unlock(&b
->c
->bucket_lock
);
1064 struct btree
*__bch_btree_node_alloc(struct cache_set
*c
, struct btree_op
*op
,
1065 int level
, bool wait
,
1066 struct btree
*parent
)
1069 struct btree
*b
= ERR_PTR(-EAGAIN
);
1071 mutex_lock(&c
->bucket_lock
);
1073 if (__bch_bucket_alloc_set(c
, RESERVE_BTREE
, &k
.key
, 1, wait
))
1076 bkey_put(c
, &k
.key
);
1077 SET_KEY_SIZE(&k
.key
, c
->btree_pages
* PAGE_SECTORS
);
1079 b
= mca_alloc(c
, op
, &k
.key
, level
);
1085 "Tried to allocate bucket that was in btree cache");
1091 bch_bset_init_next(&b
->keys
, b
->keys
.set
->data
, bset_magic(&b
->c
->sb
));
1093 mutex_unlock(&c
->bucket_lock
);
1095 trace_bcache_btree_node_alloc(b
);
1098 bch_bucket_free(c
, &k
.key
);
1100 mutex_unlock(&c
->bucket_lock
);
1102 trace_bcache_btree_node_alloc_fail(c
);
1106 static struct btree
*bch_btree_node_alloc(struct cache_set
*c
,
1107 struct btree_op
*op
, int level
,
1108 struct btree
*parent
)
1110 return __bch_btree_node_alloc(c
, op
, level
, op
!= NULL
, parent
);
1113 static struct btree
*btree_node_alloc_replacement(struct btree
*b
,
1114 struct btree_op
*op
)
1116 struct btree
*n
= bch_btree_node_alloc(b
->c
, op
, b
->level
, b
->parent
);
1117 if (!IS_ERR_OR_NULL(n
)) {
1118 mutex_lock(&n
->write_lock
);
1119 bch_btree_sort_into(&b
->keys
, &n
->keys
, &b
->c
->sort
);
1120 bkey_copy_key(&n
->key
, &b
->key
);
1121 mutex_unlock(&n
->write_lock
);
1127 static void make_btree_freeing_key(struct btree
*b
, struct bkey
*k
)
1131 mutex_lock(&b
->c
->bucket_lock
);
1133 atomic_inc(&b
->c
->prio_blocked
);
1135 bkey_copy(k
, &b
->key
);
1136 bkey_copy_key(k
, &ZERO_KEY
);
1138 for (i
= 0; i
< KEY_PTRS(k
); i
++)
1140 bch_inc_gen(PTR_CACHE(b
->c
, &b
->key
, i
),
1141 PTR_BUCKET(b
->c
, &b
->key
, i
)));
1143 mutex_unlock(&b
->c
->bucket_lock
);
1146 static int btree_check_reserve(struct btree
*b
, struct btree_op
*op
)
1148 struct cache_set
*c
= b
->c
;
1150 unsigned i
, reserve
= (c
->root
->level
- b
->level
) * 2 + 1;
1152 mutex_lock(&c
->bucket_lock
);
1154 for_each_cache(ca
, c
, i
)
1155 if (fifo_used(&ca
->free
[RESERVE_BTREE
]) < reserve
) {
1157 prepare_to_wait(&c
->btree_cache_wait
, &op
->wait
,
1158 TASK_UNINTERRUPTIBLE
);
1159 mutex_unlock(&c
->bucket_lock
);
1163 mutex_unlock(&c
->bucket_lock
);
1165 return mca_cannibalize_lock(b
->c
, op
);
1168 /* Garbage collection */
1170 static uint8_t __bch_btree_mark_key(struct cache_set
*c
, int level
,
1178 * ptr_invalid() can't return true for the keys that mark btree nodes as
1179 * freed, but since ptr_bad() returns true we'll never actually use them
1180 * for anything and thus we don't want mark their pointers here
1182 if (!bkey_cmp(k
, &ZERO_KEY
))
1185 for (i
= 0; i
< KEY_PTRS(k
); i
++) {
1186 if (!ptr_available(c
, k
, i
))
1189 g
= PTR_BUCKET(c
, k
, i
);
1191 if (gen_after(g
->last_gc
, PTR_GEN(k
, i
)))
1192 g
->last_gc
= PTR_GEN(k
, i
);
1194 if (ptr_stale(c
, k
, i
)) {
1195 stale
= max(stale
, ptr_stale(c
, k
, i
));
1199 cache_bug_on(GC_MARK(g
) &&
1200 (GC_MARK(g
) == GC_MARK_METADATA
) != (level
!= 0),
1201 c
, "inconsistent ptrs: mark = %llu, level = %i",
1205 SET_GC_MARK(g
, GC_MARK_METADATA
);
1206 else if (KEY_DIRTY(k
))
1207 SET_GC_MARK(g
, GC_MARK_DIRTY
);
1208 else if (!GC_MARK(g
))
1209 SET_GC_MARK(g
, GC_MARK_RECLAIMABLE
);
1211 /* guard against overflow */
1212 SET_GC_SECTORS_USED(g
, min_t(unsigned,
1213 GC_SECTORS_USED(g
) + KEY_SIZE(k
),
1214 MAX_GC_SECTORS_USED
));
1216 BUG_ON(!GC_SECTORS_USED(g
));
1222 #define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k)
1224 void bch_initial_mark_key(struct cache_set
*c
, int level
, struct bkey
*k
)
1228 for (i
= 0; i
< KEY_PTRS(k
); i
++)
1229 if (ptr_available(c
, k
, i
) &&
1230 !ptr_stale(c
, k
, i
)) {
1231 struct bucket
*b
= PTR_BUCKET(c
, k
, i
);
1233 b
->gen
= PTR_GEN(k
, i
);
1235 if (level
&& bkey_cmp(k
, &ZERO_KEY
))
1236 b
->prio
= BTREE_PRIO
;
1237 else if (!level
&& b
->prio
== BTREE_PRIO
)
1238 b
->prio
= INITIAL_PRIO
;
1241 __bch_btree_mark_key(c
, level
, k
);
1244 static bool btree_gc_mark_node(struct btree
*b
, struct gc_stat
*gc
)
1247 unsigned keys
= 0, good_keys
= 0;
1249 struct btree_iter iter
;
1250 struct bset_tree
*t
;
1254 for_each_key_filter(&b
->keys
, k
, &iter
, bch_ptr_invalid
) {
1255 stale
= max(stale
, btree_mark_key(b
, k
));
1258 if (bch_ptr_bad(&b
->keys
, k
))
1261 gc
->key_bytes
+= bkey_u64s(k
);
1265 gc
->data
+= KEY_SIZE(k
);
1268 for (t
= b
->keys
.set
; t
<= &b
->keys
.set
[b
->keys
.nsets
]; t
++)
1269 btree_bug_on(t
->size
&&
1270 bset_written(&b
->keys
, t
) &&
1271 bkey_cmp(&b
->key
, &t
->end
) < 0,
1272 b
, "found short btree key in gc");
1274 if (b
->c
->gc_always_rewrite
)
1280 if ((keys
- good_keys
) * 2 > keys
)
1286 #define GC_MERGE_NODES 4U
1288 struct gc_merge_info
{
1293 static int bch_btree_insert_node(struct btree
*, struct btree_op
*,
1294 struct keylist
*, atomic_t
*, struct bkey
*);
1296 static int btree_gc_coalesce(struct btree
*b
, struct btree_op
*op
,
1297 struct gc_stat
*gc
, struct gc_merge_info
*r
)
1299 unsigned i
, nodes
= 0, keys
= 0, blocks
;
1300 struct btree
*new_nodes
[GC_MERGE_NODES
];
1301 struct keylist keylist
;
1305 bch_keylist_init(&keylist
);
1307 if (btree_check_reserve(b
, NULL
))
1310 memset(new_nodes
, 0, sizeof(new_nodes
));
1311 closure_init_stack(&cl
);
1313 while (nodes
< GC_MERGE_NODES
&& !IS_ERR_OR_NULL(r
[nodes
].b
))
1314 keys
+= r
[nodes
++].keys
;
1316 blocks
= btree_default_blocks(b
->c
) * 2 / 3;
1319 __set_blocks(b
->keys
.set
[0].data
, keys
,
1320 block_bytes(b
->c
)) > blocks
* (nodes
- 1))
1323 for (i
= 0; i
< nodes
; i
++) {
1324 new_nodes
[i
] = btree_node_alloc_replacement(r
[i
].b
, NULL
);
1325 if (IS_ERR_OR_NULL(new_nodes
[i
]))
1326 goto out_nocoalesce
;
1330 * We have to check the reserve here, after we've allocated our new
1331 * nodes, to make sure the insert below will succeed - we also check
1332 * before as an optimization to potentially avoid a bunch of expensive
1335 if (btree_check_reserve(b
, NULL
))
1336 goto out_nocoalesce
;
1338 for (i
= 0; i
< nodes
; i
++)
1339 mutex_lock(&new_nodes
[i
]->write_lock
);
1341 for (i
= nodes
- 1; i
> 0; --i
) {
1342 struct bset
*n1
= btree_bset_first(new_nodes
[i
]);
1343 struct bset
*n2
= btree_bset_first(new_nodes
[i
- 1]);
1344 struct bkey
*k
, *last
= NULL
;
1350 k
< bset_bkey_last(n2
);
1352 if (__set_blocks(n1
, n1
->keys
+ keys
+
1354 block_bytes(b
->c
)) > blocks
)
1358 keys
+= bkey_u64s(k
);
1362 * Last node we're not getting rid of - we're getting
1363 * rid of the node at r[0]. Have to try and fit all of
1364 * the remaining keys into this node; we can't ensure
1365 * they will always fit due to rounding and variable
1366 * length keys (shouldn't be possible in practice,
1369 if (__set_blocks(n1
, n1
->keys
+ n2
->keys
,
1370 block_bytes(b
->c
)) >
1371 btree_blocks(new_nodes
[i
]))
1372 goto out_nocoalesce
;
1375 /* Take the key of the node we're getting rid of */
1379 BUG_ON(__set_blocks(n1
, n1
->keys
+ keys
, block_bytes(b
->c
)) >
1380 btree_blocks(new_nodes
[i
]));
1383 bkey_copy_key(&new_nodes
[i
]->key
, last
);
1385 memcpy(bset_bkey_last(n1
),
1387 (void *) bset_bkey_idx(n2
, keys
) - (void *) n2
->start
);
1390 r
[i
].keys
= n1
->keys
;
1393 bset_bkey_idx(n2
, keys
),
1394 (void *) bset_bkey_last(n2
) -
1395 (void *) bset_bkey_idx(n2
, keys
));
1399 if (__bch_keylist_realloc(&keylist
,
1400 bkey_u64s(&new_nodes
[i
]->key
)))
1401 goto out_nocoalesce
;
1403 bch_btree_node_write(new_nodes
[i
], &cl
);
1404 bch_keylist_add(&keylist
, &new_nodes
[i
]->key
);
1407 for (i
= 0; i
< nodes
; i
++)
1408 mutex_unlock(&new_nodes
[i
]->write_lock
);
1412 /* We emptied out this node */
1413 BUG_ON(btree_bset_first(new_nodes
[0])->keys
);
1414 btree_node_free(new_nodes
[0]);
1415 rw_unlock(true, new_nodes
[0]);
1416 new_nodes
[0] = NULL
;
1418 for (i
= 0; i
< nodes
; i
++) {
1419 if (__bch_keylist_realloc(&keylist
, bkey_u64s(&r
[i
].b
->key
)))
1420 goto out_nocoalesce
;
1422 make_btree_freeing_key(r
[i
].b
, keylist
.top
);
1423 bch_keylist_push(&keylist
);
1426 bch_btree_insert_node(b
, op
, &keylist
, NULL
, NULL
);
1427 BUG_ON(!bch_keylist_empty(&keylist
));
1429 for (i
= 0; i
< nodes
; i
++) {
1430 btree_node_free(r
[i
].b
);
1431 rw_unlock(true, r
[i
].b
);
1433 r
[i
].b
= new_nodes
[i
];
1436 memmove(r
, r
+ 1, sizeof(r
[0]) * (nodes
- 1));
1437 r
[nodes
- 1].b
= ERR_PTR(-EINTR
);
1439 trace_bcache_btree_gc_coalesce(nodes
);
1442 bch_keylist_free(&keylist
);
1444 /* Invalidated our iterator */
1449 bch_keylist_free(&keylist
);
1451 while ((k
= bch_keylist_pop(&keylist
)))
1452 if (!bkey_cmp(k
, &ZERO_KEY
))
1453 atomic_dec(&b
->c
->prio_blocked
);
1455 for (i
= 0; i
< nodes
; i
++)
1456 if (!IS_ERR_OR_NULL(new_nodes
[i
])) {
1457 btree_node_free(new_nodes
[i
]);
1458 rw_unlock(true, new_nodes
[i
]);
1463 static int btree_gc_rewrite_node(struct btree
*b
, struct btree_op
*op
,
1464 struct btree
*replace
)
1466 struct keylist keys
;
1469 if (btree_check_reserve(b
, NULL
))
1472 n
= btree_node_alloc_replacement(replace
, NULL
);
1474 /* recheck reserve after allocating replacement node */
1475 if (btree_check_reserve(b
, NULL
)) {
1481 bch_btree_node_write_sync(n
);
1483 bch_keylist_init(&keys
);
1484 bch_keylist_add(&keys
, &n
->key
);
1486 make_btree_freeing_key(replace
, keys
.top
);
1487 bch_keylist_push(&keys
);
1489 bch_btree_insert_node(b
, op
, &keys
, NULL
, NULL
);
1490 BUG_ON(!bch_keylist_empty(&keys
));
1492 btree_node_free(replace
);
1495 /* Invalidated our iterator */
1499 static unsigned btree_gc_count_keys(struct btree
*b
)
1502 struct btree_iter iter
;
1505 for_each_key_filter(&b
->keys
, k
, &iter
, bch_ptr_bad
)
1506 ret
+= bkey_u64s(k
);
1511 static int btree_gc_recurse(struct btree
*b
, struct btree_op
*op
,
1512 struct closure
*writes
, struct gc_stat
*gc
)
1515 bool should_rewrite
;
1517 struct btree_iter iter
;
1518 struct gc_merge_info r
[GC_MERGE_NODES
];
1519 struct gc_merge_info
*i
, *last
= r
+ ARRAY_SIZE(r
) - 1;
1521 bch_btree_iter_init(&b
->keys
, &iter
, &b
->c
->gc_done
);
1523 for (i
= r
; i
< r
+ ARRAY_SIZE(r
); i
++)
1524 i
->b
= ERR_PTR(-EINTR
);
1527 k
= bch_btree_iter_next_filter(&iter
, &b
->keys
, bch_ptr_bad
);
1529 r
->b
= bch_btree_node_get(b
->c
, op
, k
, b
->level
- 1,
1532 ret
= PTR_ERR(r
->b
);
1536 r
->keys
= btree_gc_count_keys(r
->b
);
1538 ret
= btree_gc_coalesce(b
, op
, gc
, r
);
1546 if (!IS_ERR(last
->b
)) {
1547 should_rewrite
= btree_gc_mark_node(last
->b
, gc
);
1548 if (should_rewrite
) {
1549 ret
= btree_gc_rewrite_node(b
, op
, last
->b
);
1554 if (last
->b
->level
) {
1555 ret
= btree_gc_recurse(last
->b
, op
, writes
, gc
);
1560 bkey_copy_key(&b
->c
->gc_done
, &last
->b
->key
);
1563 * Must flush leaf nodes before gc ends, since replace
1564 * operations aren't journalled
1566 mutex_lock(&last
->b
->write_lock
);
1567 if (btree_node_dirty(last
->b
))
1568 bch_btree_node_write(last
->b
, writes
);
1569 mutex_unlock(&last
->b
->write_lock
);
1570 rw_unlock(true, last
->b
);
1573 memmove(r
+ 1, r
, sizeof(r
[0]) * (GC_MERGE_NODES
- 1));
1576 if (need_resched()) {
1582 for (i
= r
; i
< r
+ ARRAY_SIZE(r
); i
++)
1583 if (!IS_ERR_OR_NULL(i
->b
)) {
1584 mutex_lock(&i
->b
->write_lock
);
1585 if (btree_node_dirty(i
->b
))
1586 bch_btree_node_write(i
->b
, writes
);
1587 mutex_unlock(&i
->b
->write_lock
);
1588 rw_unlock(true, i
->b
);
1594 static int bch_btree_gc_root(struct btree
*b
, struct btree_op
*op
,
1595 struct closure
*writes
, struct gc_stat
*gc
)
1597 struct btree
*n
= NULL
;
1599 bool should_rewrite
;
1601 should_rewrite
= btree_gc_mark_node(b
, gc
);
1602 if (should_rewrite
) {
1603 n
= btree_node_alloc_replacement(b
, NULL
);
1605 if (!IS_ERR_OR_NULL(n
)) {
1606 bch_btree_node_write_sync(n
);
1608 bch_btree_set_root(n
);
1616 __bch_btree_mark_key(b
->c
, b
->level
+ 1, &b
->key
);
1619 ret
= btree_gc_recurse(b
, op
, writes
, gc
);
1624 bkey_copy_key(&b
->c
->gc_done
, &b
->key
);
1629 static void btree_gc_start(struct cache_set
*c
)
1635 if (!c
->gc_mark_valid
)
1638 mutex_lock(&c
->bucket_lock
);
1640 c
->gc_mark_valid
= 0;
1641 c
->gc_done
= ZERO_KEY
;
1643 for_each_cache(ca
, c
, i
)
1644 for_each_bucket(b
, ca
) {
1645 b
->last_gc
= b
->gen
;
1646 if (!atomic_read(&b
->pin
)) {
1648 SET_GC_SECTORS_USED(b
, 0);
1652 mutex_unlock(&c
->bucket_lock
);
1655 static size_t bch_btree_gc_finish(struct cache_set
*c
)
1657 size_t available
= 0;
1662 mutex_lock(&c
->bucket_lock
);
1665 c
->gc_mark_valid
= 1;
1668 for (i
= 0; i
< KEY_PTRS(&c
->uuid_bucket
); i
++)
1669 SET_GC_MARK(PTR_BUCKET(c
, &c
->uuid_bucket
, i
),
1672 /* don't reclaim buckets to which writeback keys point */
1674 for (i
= 0; i
< c
->nr_uuids
; i
++) {
1675 struct bcache_device
*d
= c
->devices
[i
];
1676 struct cached_dev
*dc
;
1677 struct keybuf_key
*w
, *n
;
1680 if (!d
|| UUID_FLASH_ONLY(&c
->uuids
[i
]))
1682 dc
= container_of(d
, struct cached_dev
, disk
);
1684 spin_lock(&dc
->writeback_keys
.lock
);
1685 rbtree_postorder_for_each_entry_safe(w
, n
,
1686 &dc
->writeback_keys
.keys
, node
)
1687 for (j
= 0; j
< KEY_PTRS(&w
->key
); j
++)
1688 SET_GC_MARK(PTR_BUCKET(c
, &w
->key
, j
),
1690 spin_unlock(&dc
->writeback_keys
.lock
);
1694 for_each_cache(ca
, c
, i
) {
1697 ca
->invalidate_needs_gc
= 0;
1699 for (i
= ca
->sb
.d
; i
< ca
->sb
.d
+ ca
->sb
.keys
; i
++)
1700 SET_GC_MARK(ca
->buckets
+ *i
, GC_MARK_METADATA
);
1702 for (i
= ca
->prio_buckets
;
1703 i
< ca
->prio_buckets
+ prio_buckets(ca
) * 2; i
++)
1704 SET_GC_MARK(ca
->buckets
+ *i
, GC_MARK_METADATA
);
1706 for_each_bucket(b
, ca
) {
1707 c
->need_gc
= max(c
->need_gc
, bucket_gc_gen(b
));
1709 if (atomic_read(&b
->pin
))
1712 BUG_ON(!GC_MARK(b
) && GC_SECTORS_USED(b
));
1714 if (!GC_MARK(b
) || GC_MARK(b
) == GC_MARK_RECLAIMABLE
)
1719 mutex_unlock(&c
->bucket_lock
);
1723 static void bch_btree_gc(struct cache_set
*c
)
1726 unsigned long available
;
1727 struct gc_stat stats
;
1728 struct closure writes
;
1730 uint64_t start_time
= local_clock();
1732 trace_bcache_gc_start(c
);
1734 memset(&stats
, 0, sizeof(struct gc_stat
));
1735 closure_init_stack(&writes
);
1736 bch_btree_op_init(&op
, SHRT_MAX
);
1741 ret
= btree_root(gc_root
, c
, &op
, &writes
, &stats
);
1742 closure_sync(&writes
);
1745 if (ret
&& ret
!= -EAGAIN
)
1746 pr_warn("gc failed!");
1749 available
= bch_btree_gc_finish(c
);
1750 wake_up_allocators(c
);
1752 bch_time_stats_update(&c
->btree_gc_time
, start_time
);
1754 stats
.key_bytes
*= sizeof(uint64_t);
1756 stats
.in_use
= (c
->nbuckets
- available
) * 100 / c
->nbuckets
;
1757 memcpy(&c
->gc_stats
, &stats
, sizeof(struct gc_stat
));
1759 trace_bcache_gc_end(c
);
1764 static bool gc_should_run(struct cache_set
*c
)
1769 for_each_cache(ca
, c
, i
)
1770 if (ca
->invalidate_needs_gc
)
1773 if (atomic_read(&c
->sectors_to_gc
) < 0)
1779 static int bch_gc_thread(void *arg
)
1781 struct cache_set
*c
= arg
;
1784 wait_event_interruptible(c
->gc_wait
,
1785 kthread_should_stop() || gc_should_run(c
));
1787 if (kthread_should_stop())
1797 int bch_gc_thread_start(struct cache_set
*c
)
1799 c
->gc_thread
= kthread_run(bch_gc_thread
, c
, "bcache_gc");
1800 if (IS_ERR(c
->gc_thread
))
1801 return PTR_ERR(c
->gc_thread
);
1806 /* Initial partial gc */
1808 static int bch_btree_check_recurse(struct btree
*b
, struct btree_op
*op
)
1811 struct bkey
*k
, *p
= NULL
;
1812 struct btree_iter iter
;
1814 for_each_key_filter(&b
->keys
, k
, &iter
, bch_ptr_invalid
)
1815 bch_initial_mark_key(b
->c
, b
->level
, k
);
1817 bch_initial_mark_key(b
->c
, b
->level
+ 1, &b
->key
);
1820 bch_btree_iter_init(&b
->keys
, &iter
, NULL
);
1823 k
= bch_btree_iter_next_filter(&iter
, &b
->keys
,
1826 btree_node_prefetch(b
, k
);
1829 ret
= btree(check_recurse
, p
, b
, op
);
1832 } while (p
&& !ret
);
1838 int bch_btree_check(struct cache_set
*c
)
1842 bch_btree_op_init(&op
, SHRT_MAX
);
1844 return btree_root(check_recurse
, c
, &op
);
1847 void bch_initial_gc_finish(struct cache_set
*c
)
1853 bch_btree_gc_finish(c
);
1855 mutex_lock(&c
->bucket_lock
);
1858 * We need to put some unused buckets directly on the prio freelist in
1859 * order to get the allocator thread started - it needs freed buckets in
1860 * order to rewrite the prios and gens, and it needs to rewrite prios
1861 * and gens in order to free buckets.
1863 * This is only safe for buckets that have no live data in them, which
1864 * there should always be some of.
1866 for_each_cache(ca
, c
, i
) {
1867 for_each_bucket(b
, ca
) {
1868 if (fifo_full(&ca
->free
[RESERVE_PRIO
]))
1871 if (bch_can_invalidate_bucket(ca
, b
) &&
1873 __bch_invalidate_one_bucket(ca
, b
);
1874 fifo_push(&ca
->free
[RESERVE_PRIO
],
1880 mutex_unlock(&c
->bucket_lock
);
1883 /* Btree insertion */
1885 static bool btree_insert_key(struct btree
*b
, struct bkey
*k
,
1886 struct bkey
*replace_key
)
1890 BUG_ON(bkey_cmp(k
, &b
->key
) > 0);
1892 status
= bch_btree_insert_key(&b
->keys
, k
, replace_key
);
1893 if (status
!= BTREE_INSERT_STATUS_NO_INSERT
) {
1894 bch_check_keys(&b
->keys
, "%u for %s", status
,
1895 replace_key
? "replace" : "insert");
1897 trace_bcache_btree_insert_key(b
, k
, replace_key
!= NULL
,
1904 static size_t insert_u64s_remaining(struct btree
*b
)
1906 long ret
= bch_btree_keys_u64s_remaining(&b
->keys
);
1909 * Might land in the middle of an existing extent and have to split it
1911 if (b
->keys
.ops
->is_extents
)
1912 ret
-= KEY_MAX_U64S
;
1914 return max(ret
, 0L);
1917 static bool bch_btree_insert_keys(struct btree
*b
, struct btree_op
*op
,
1918 struct keylist
*insert_keys
,
1919 struct bkey
*replace_key
)
1922 int oldsize
= bch_count_data(&b
->keys
);
1924 while (!bch_keylist_empty(insert_keys
)) {
1925 struct bkey
*k
= insert_keys
->keys
;
1927 if (bkey_u64s(k
) > insert_u64s_remaining(b
))
1930 if (bkey_cmp(k
, &b
->key
) <= 0) {
1934 ret
|= btree_insert_key(b
, k
, replace_key
);
1935 bch_keylist_pop_front(insert_keys
);
1936 } else if (bkey_cmp(&START_KEY(k
), &b
->key
) < 0) {
1937 BKEY_PADDED(key
) temp
;
1938 bkey_copy(&temp
.key
, insert_keys
->keys
);
1940 bch_cut_back(&b
->key
, &temp
.key
);
1941 bch_cut_front(&b
->key
, insert_keys
->keys
);
1943 ret
|= btree_insert_key(b
, &temp
.key
, replace_key
);
1951 op
->insert_collision
= true;
1953 BUG_ON(!bch_keylist_empty(insert_keys
) && b
->level
);
1955 BUG_ON(bch_count_data(&b
->keys
) < oldsize
);
1959 static int btree_split(struct btree
*b
, struct btree_op
*op
,
1960 struct keylist
*insert_keys
,
1961 struct bkey
*replace_key
)
1964 struct btree
*n1
, *n2
= NULL
, *n3
= NULL
;
1965 uint64_t start_time
= local_clock();
1967 struct keylist parent_keys
;
1969 closure_init_stack(&cl
);
1970 bch_keylist_init(&parent_keys
);
1972 if (btree_check_reserve(b
, op
)) {
1976 WARN(1, "insufficient reserve for split\n");
1979 n1
= btree_node_alloc_replacement(b
, op
);
1983 split
= set_blocks(btree_bset_first(n1
),
1984 block_bytes(n1
->c
)) > (btree_blocks(b
) * 4) / 5;
1989 trace_bcache_btree_node_split(b
, btree_bset_first(n1
)->keys
);
1991 n2
= bch_btree_node_alloc(b
->c
, op
, b
->level
, b
->parent
);
1996 n3
= bch_btree_node_alloc(b
->c
, op
, b
->level
+ 1, NULL
);
2001 mutex_lock(&n1
->write_lock
);
2002 mutex_lock(&n2
->write_lock
);
2004 bch_btree_insert_keys(n1
, op
, insert_keys
, replace_key
);
2007 * Has to be a linear search because we don't have an auxiliary
2011 while (keys
< (btree_bset_first(n1
)->keys
* 3) / 5)
2012 keys
+= bkey_u64s(bset_bkey_idx(btree_bset_first(n1
),
2015 bkey_copy_key(&n1
->key
,
2016 bset_bkey_idx(btree_bset_first(n1
), keys
));
2017 keys
+= bkey_u64s(bset_bkey_idx(btree_bset_first(n1
), keys
));
2019 btree_bset_first(n2
)->keys
= btree_bset_first(n1
)->keys
- keys
;
2020 btree_bset_first(n1
)->keys
= keys
;
2022 memcpy(btree_bset_first(n2
)->start
,
2023 bset_bkey_last(btree_bset_first(n1
)),
2024 btree_bset_first(n2
)->keys
* sizeof(uint64_t));
2026 bkey_copy_key(&n2
->key
, &b
->key
);
2028 bch_keylist_add(&parent_keys
, &n2
->key
);
2029 bch_btree_node_write(n2
, &cl
);
2030 mutex_unlock(&n2
->write_lock
);
2031 rw_unlock(true, n2
);
2033 trace_bcache_btree_node_compact(b
, btree_bset_first(n1
)->keys
);
2035 mutex_lock(&n1
->write_lock
);
2036 bch_btree_insert_keys(n1
, op
, insert_keys
, replace_key
);
2039 bch_keylist_add(&parent_keys
, &n1
->key
);
2040 bch_btree_node_write(n1
, &cl
);
2041 mutex_unlock(&n1
->write_lock
);
2044 /* Depth increases, make a new root */
2045 mutex_lock(&n3
->write_lock
);
2046 bkey_copy_key(&n3
->key
, &MAX_KEY
);
2047 bch_btree_insert_keys(n3
, op
, &parent_keys
, NULL
);
2048 bch_btree_node_write(n3
, &cl
);
2049 mutex_unlock(&n3
->write_lock
);
2052 bch_btree_set_root(n3
);
2053 rw_unlock(true, n3
);
2054 } else if (!b
->parent
) {
2055 /* Root filled up but didn't need to be split */
2057 bch_btree_set_root(n1
);
2059 /* Split a non root node */
2061 make_btree_freeing_key(b
, parent_keys
.top
);
2062 bch_keylist_push(&parent_keys
);
2064 bch_btree_insert_node(b
->parent
, op
, &parent_keys
, NULL
, NULL
);
2065 BUG_ON(!bch_keylist_empty(&parent_keys
));
2069 rw_unlock(true, n1
);
2071 bch_time_stats_update(&b
->c
->btree_split_time
, start_time
);
2075 bkey_put(b
->c
, &n2
->key
);
2076 btree_node_free(n2
);
2077 rw_unlock(true, n2
);
2079 bkey_put(b
->c
, &n1
->key
);
2080 btree_node_free(n1
);
2081 rw_unlock(true, n1
);
2083 WARN(1, "bcache: btree split failed (level %u)", b
->level
);
2085 if (n3
== ERR_PTR(-EAGAIN
) ||
2086 n2
== ERR_PTR(-EAGAIN
) ||
2087 n1
== ERR_PTR(-EAGAIN
))
2093 static int bch_btree_insert_node(struct btree
*b
, struct btree_op
*op
,
2094 struct keylist
*insert_keys
,
2095 atomic_t
*journal_ref
,
2096 struct bkey
*replace_key
)
2100 BUG_ON(b
->level
&& replace_key
);
2102 closure_init_stack(&cl
);
2104 mutex_lock(&b
->write_lock
);
2106 if (write_block(b
) != btree_bset_last(b
) &&
2107 b
->keys
.last_set_unwritten
)
2108 bch_btree_init_next(b
); /* just wrote a set */
2110 if (bch_keylist_nkeys(insert_keys
) > insert_u64s_remaining(b
)) {
2111 mutex_unlock(&b
->write_lock
);
2115 BUG_ON(write_block(b
) != btree_bset_last(b
));
2117 if (bch_btree_insert_keys(b
, op
, insert_keys
, replace_key
)) {
2119 bch_btree_leaf_dirty(b
, journal_ref
);
2121 bch_btree_node_write(b
, &cl
);
2124 mutex_unlock(&b
->write_lock
);
2126 /* wait for btree node write if necessary, after unlock */
2131 if (current
->bio_list
) {
2132 op
->lock
= b
->c
->root
->level
+ 1;
2134 } else if (op
->lock
<= b
->c
->root
->level
) {
2135 op
->lock
= b
->c
->root
->level
+ 1;
2138 /* Invalidated all iterators */
2139 int ret
= btree_split(b
, op
, insert_keys
, replace_key
);
2141 if (bch_keylist_empty(insert_keys
))
2149 int bch_btree_insert_check_key(struct btree
*b
, struct btree_op
*op
,
2150 struct bkey
*check_key
)
2153 uint64_t btree_ptr
= b
->key
.ptr
[0];
2154 unsigned long seq
= b
->seq
;
2155 struct keylist insert
;
2156 bool upgrade
= op
->lock
== -1;
2158 bch_keylist_init(&insert
);
2161 rw_unlock(false, b
);
2162 rw_lock(true, b
, b
->level
);
2164 if (b
->key
.ptr
[0] != btree_ptr
||
2165 b
->seq
!= seq
+ 1) {
2166 op
->lock
= b
->level
;
2171 SET_KEY_PTRS(check_key
, 1);
2172 get_random_bytes(&check_key
->ptr
[0], sizeof(uint64_t));
2174 SET_PTR_DEV(check_key
, 0, PTR_CHECK_DEV
);
2176 bch_keylist_add(&insert
, check_key
);
2178 ret
= bch_btree_insert_node(b
, op
, &insert
, NULL
, NULL
);
2180 BUG_ON(!ret
&& !bch_keylist_empty(&insert
));
2183 downgrade_write(&b
->lock
);
2187 struct btree_insert_op
{
2189 struct keylist
*keys
;
2190 atomic_t
*journal_ref
;
2191 struct bkey
*replace_key
;
2194 static int btree_insert_fn(struct btree_op
*b_op
, struct btree
*b
)
2196 struct btree_insert_op
*op
= container_of(b_op
,
2197 struct btree_insert_op
, op
);
2199 int ret
= bch_btree_insert_node(b
, &op
->op
, op
->keys
,
2200 op
->journal_ref
, op
->replace_key
);
2201 if (ret
&& !bch_keylist_empty(op
->keys
))
2207 int bch_btree_insert(struct cache_set
*c
, struct keylist
*keys
,
2208 atomic_t
*journal_ref
, struct bkey
*replace_key
)
2210 struct btree_insert_op op
;
2213 BUG_ON(current
->bio_list
);
2214 BUG_ON(bch_keylist_empty(keys
));
2216 bch_btree_op_init(&op
.op
, 0);
2218 op
.journal_ref
= journal_ref
;
2219 op
.replace_key
= replace_key
;
2221 while (!ret
&& !bch_keylist_empty(keys
)) {
2223 ret
= bch_btree_map_leaf_nodes(&op
.op
, c
,
2224 &START_KEY(keys
->keys
),
2231 pr_err("error %i", ret
);
2233 while ((k
= bch_keylist_pop(keys
)))
2235 } else if (op
.op
.insert_collision
)
2241 void bch_btree_set_root(struct btree
*b
)
2246 closure_init_stack(&cl
);
2248 trace_bcache_btree_set_root(b
);
2250 BUG_ON(!b
->written
);
2252 for (i
= 0; i
< KEY_PTRS(&b
->key
); i
++)
2253 BUG_ON(PTR_BUCKET(b
->c
, &b
->key
, i
)->prio
!= BTREE_PRIO
);
2255 mutex_lock(&b
->c
->bucket_lock
);
2256 list_del_init(&b
->list
);
2257 mutex_unlock(&b
->c
->bucket_lock
);
2261 bch_journal_meta(b
->c
, &cl
);
2265 /* Map across nodes or keys */
2267 static int bch_btree_map_nodes_recurse(struct btree
*b
, struct btree_op
*op
,
2269 btree_map_nodes_fn
*fn
, int flags
)
2271 int ret
= MAP_CONTINUE
;
2275 struct btree_iter iter
;
2277 bch_btree_iter_init(&b
->keys
, &iter
, from
);
2279 while ((k
= bch_btree_iter_next_filter(&iter
, &b
->keys
,
2281 ret
= btree(map_nodes_recurse
, k
, b
,
2282 op
, from
, fn
, flags
);
2285 if (ret
!= MAP_CONTINUE
)
2290 if (!b
->level
|| flags
== MAP_ALL_NODES
)
2296 int __bch_btree_map_nodes(struct btree_op
*op
, struct cache_set
*c
,
2297 struct bkey
*from
, btree_map_nodes_fn
*fn
, int flags
)
2299 return btree_root(map_nodes_recurse
, c
, op
, from
, fn
, flags
);
2302 static int bch_btree_map_keys_recurse(struct btree
*b
, struct btree_op
*op
,
2303 struct bkey
*from
, btree_map_keys_fn
*fn
,
2306 int ret
= MAP_CONTINUE
;
2308 struct btree_iter iter
;
2310 bch_btree_iter_init(&b
->keys
, &iter
, from
);
2312 while ((k
= bch_btree_iter_next_filter(&iter
, &b
->keys
, bch_ptr_bad
))) {
2315 : btree(map_keys_recurse
, k
, b
, op
, from
, fn
, flags
);
2318 if (ret
!= MAP_CONTINUE
)
2322 if (!b
->level
&& (flags
& MAP_END_KEY
))
2323 ret
= fn(op
, b
, &KEY(KEY_INODE(&b
->key
),
2324 KEY_OFFSET(&b
->key
), 0));
2329 int bch_btree_map_keys(struct btree_op
*op
, struct cache_set
*c
,
2330 struct bkey
*from
, btree_map_keys_fn
*fn
, int flags
)
2332 return btree_root(map_keys_recurse
, c
, op
, from
, fn
, flags
);
2337 static inline int keybuf_cmp(struct keybuf_key
*l
, struct keybuf_key
*r
)
2339 /* Overlapping keys compare equal */
2340 if (bkey_cmp(&l
->key
, &START_KEY(&r
->key
)) <= 0)
2342 if (bkey_cmp(&START_KEY(&l
->key
), &r
->key
) >= 0)
2347 static inline int keybuf_nonoverlapping_cmp(struct keybuf_key
*l
,
2348 struct keybuf_key
*r
)
2350 return clamp_t(int64_t, bkey_cmp(&l
->key
, &r
->key
), -1, 1);
2358 keybuf_pred_fn
*pred
;
2361 static int refill_keybuf_fn(struct btree_op
*op
, struct btree
*b
,
2364 struct refill
*refill
= container_of(op
, struct refill
, op
);
2365 struct keybuf
*buf
= refill
->buf
;
2366 int ret
= MAP_CONTINUE
;
2368 if (bkey_cmp(k
, refill
->end
) >= 0) {
2373 if (!KEY_SIZE(k
)) /* end key */
2376 if (refill
->pred(buf
, k
)) {
2377 struct keybuf_key
*w
;
2379 spin_lock(&buf
->lock
);
2381 w
= array_alloc(&buf
->freelist
);
2383 spin_unlock(&buf
->lock
);
2388 bkey_copy(&w
->key
, k
);
2390 if (RB_INSERT(&buf
->keys
, w
, node
, keybuf_cmp
))
2391 array_free(&buf
->freelist
, w
);
2395 if (array_freelist_empty(&buf
->freelist
))
2398 spin_unlock(&buf
->lock
);
2401 buf
->last_scanned
= *k
;
2405 void bch_refill_keybuf(struct cache_set
*c
, struct keybuf
*buf
,
2406 struct bkey
*end
, keybuf_pred_fn
*pred
)
2408 struct bkey start
= buf
->last_scanned
;
2409 struct refill refill
;
2413 bch_btree_op_init(&refill
.op
, -1);
2414 refill
.nr_found
= 0;
2419 bch_btree_map_keys(&refill
.op
, c
, &buf
->last_scanned
,
2420 refill_keybuf_fn
, MAP_END_KEY
);
2422 trace_bcache_keyscan(refill
.nr_found
,
2423 KEY_INODE(&start
), KEY_OFFSET(&start
),
2424 KEY_INODE(&buf
->last_scanned
),
2425 KEY_OFFSET(&buf
->last_scanned
));
2427 spin_lock(&buf
->lock
);
2429 if (!RB_EMPTY_ROOT(&buf
->keys
)) {
2430 struct keybuf_key
*w
;
2431 w
= RB_FIRST(&buf
->keys
, struct keybuf_key
, node
);
2432 buf
->start
= START_KEY(&w
->key
);
2434 w
= RB_LAST(&buf
->keys
, struct keybuf_key
, node
);
2437 buf
->start
= MAX_KEY
;
2441 spin_unlock(&buf
->lock
);
2444 static void __bch_keybuf_del(struct keybuf
*buf
, struct keybuf_key
*w
)
2446 rb_erase(&w
->node
, &buf
->keys
);
2447 array_free(&buf
->freelist
, w
);
2450 void bch_keybuf_del(struct keybuf
*buf
, struct keybuf_key
*w
)
2452 spin_lock(&buf
->lock
);
2453 __bch_keybuf_del(buf
, w
);
2454 spin_unlock(&buf
->lock
);
2457 bool bch_keybuf_check_overlapping(struct keybuf
*buf
, struct bkey
*start
,
2461 struct keybuf_key
*p
, *w
, s
;
2464 if (bkey_cmp(end
, &buf
->start
) <= 0 ||
2465 bkey_cmp(start
, &buf
->end
) >= 0)
2468 spin_lock(&buf
->lock
);
2469 w
= RB_GREATER(&buf
->keys
, s
, node
, keybuf_nonoverlapping_cmp
);
2471 while (w
&& bkey_cmp(&START_KEY(&w
->key
), end
) < 0) {
2473 w
= RB_NEXT(w
, node
);
2478 __bch_keybuf_del(buf
, p
);
2481 spin_unlock(&buf
->lock
);
2485 struct keybuf_key
*bch_keybuf_next(struct keybuf
*buf
)
2487 struct keybuf_key
*w
;
2488 spin_lock(&buf
->lock
);
2490 w
= RB_FIRST(&buf
->keys
, struct keybuf_key
, node
);
2492 while (w
&& w
->private)
2493 w
= RB_NEXT(w
, node
);
2496 w
->private = ERR_PTR(-EINTR
);
2498 spin_unlock(&buf
->lock
);
2502 struct keybuf_key
*bch_keybuf_next_rescan(struct cache_set
*c
,
2505 keybuf_pred_fn
*pred
)
2507 struct keybuf_key
*ret
;
2510 ret
= bch_keybuf_next(buf
);
2514 if (bkey_cmp(&buf
->last_scanned
, end
) >= 0) {
2515 pr_debug("scan finished");
2519 bch_refill_keybuf(c
, buf
, end
, pred
);
2525 void bch_keybuf_init(struct keybuf
*buf
)
2527 buf
->last_scanned
= MAX_KEY
;
2528 buf
->keys
= RB_ROOT
;
2530 spin_lock_init(&buf
->lock
);
2531 array_allocator_init(&buf
->freelist
);