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/hash.h>
31 #include <linux/kthread.h>
32 #include <linux/prefetch.h>
33 #include <linux/random.h>
34 #include <linux/rcupdate.h>
35 #include <trace/events/bcache.h>
39 * register_bcache: Return errors out to userspace correctly
41 * Writeback: don't undirty key until after a cache flush
43 * Create an iterator for key pointers
45 * On btree write error, mark bucket such that it won't be freed from the cache
48 * Check for bad keys in replay
50 * Refcount journal entries in journal_replay
53 * Finish incremental gc
54 * Gc should free old UUIDs, data for invalid UUIDs
56 * Provide a way to list backing device UUIDs we have data cached for, and
57 * probably how long it's been since we've seen them, and a way to invalidate
58 * dirty data for devices that will never be attached again
60 * Keep 1 min/5 min/15 min statistics of how busy a block device has been, so
61 * that based on that and how much dirty data we have we can keep writeback
64 * Add a tracepoint or somesuch to watch for writeback starvation
66 * When btree depth > 1 and splitting an interior node, we have to make sure
67 * alloc_bucket() cannot fail. This should be true but is not completely
72 * If data write is less than hard sector size of ssd, round up offset in open
73 * bucket to the next whole sector
75 * Superblock needs to be fleshed out for multiple cache devices
77 * Add a sysfs tunable for the number of writeback IOs in flight
79 * Add a sysfs tunable for the number of open data buckets
81 * IO tracking: Can we track when one process is doing io on behalf of another?
82 * IO tracking: Don't use just an average, weigh more recent stuff higher
84 * Test module load/unload
87 #define MAX_NEED_GC 64
88 #define MAX_SAVE_PRIO 72
90 #define PTR_DIRTY_BIT (((uint64_t) 1 << 36))
92 #define PTR_HASH(c, k) \
93 (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0))
95 #define insert_lock(s, b) ((b)->level <= (s)->lock)
98 * These macros are for recursing down the btree - they handle the details of
99 * locking and looking up nodes in the cache for you. They're best treated as
100 * mere syntax when reading code that uses them.
102 * op->lock determines whether we take a read or a write lock at a given depth.
103 * If you've got a read lock and find that you need a write lock (i.e. you're
104 * going to have to split), set op->lock and return -EINTR; btree_root() will
105 * call you again and you'll have the correct lock.
109 * btree - recurse down the btree on a specified key
110 * @fn: function to call, which will be passed the child node
111 * @key: key to recurse on
112 * @b: parent btree node
113 * @op: pointer to struct btree_op
115 #define btree(fn, key, b, op, ...) \
117 int _r, l = (b)->level - 1; \
118 bool _w = l <= (op)->lock; \
119 struct btree *_child = bch_btree_node_get((b)->c, op, key, l, \
121 if (!IS_ERR(_child)) { \
122 _r = bch_btree_ ## fn(_child, op, ##__VA_ARGS__); \
123 rw_unlock(_w, _child); \
125 _r = PTR_ERR(_child); \
130 * btree_root - call a function on the root of the btree
131 * @fn: function to call, which will be passed the child node
133 * @op: pointer to struct btree_op
135 #define btree_root(fn, c, op, ...) \
139 struct btree *_b = (c)->root; \
140 bool _w = insert_lock(op, _b); \
141 rw_lock(_w, _b, _b->level); \
142 if (_b == (c)->root && \
143 _w == insert_lock(op, _b)) { \
144 _r = bch_btree_ ## fn(_b, op, ##__VA_ARGS__); \
147 bch_cannibalize_unlock(c); \
150 } while (_r == -EINTR); \
152 finish_wait(&(c)->btree_cache_wait, &(op)->wait); \
156 static inline struct bset
*write_block(struct btree
*b
)
158 return ((void *) btree_bset_first(b
)) + b
->written
* block_bytes(b
->c
);
161 static void bch_btree_init_next(struct btree
*b
)
163 /* If not a leaf node, always sort */
164 if (b
->level
&& b
->keys
.nsets
)
165 bch_btree_sort(&b
->keys
, &b
->c
->sort
);
167 bch_btree_sort_lazy(&b
->keys
, &b
->c
->sort
);
169 if (b
->written
< btree_blocks(b
))
170 bch_bset_init_next(&b
->keys
, write_block(b
),
171 bset_magic(&b
->c
->sb
));
175 /* Btree key manipulation */
177 void bkey_put(struct cache_set
*c
, struct bkey
*k
)
181 for (i
= 0; i
< KEY_PTRS(k
); i
++)
182 if (ptr_available(c
, k
, i
))
183 atomic_dec_bug(&PTR_BUCKET(c
, k
, i
)->pin
);
188 static uint64_t btree_csum_set(struct btree
*b
, struct bset
*i
)
190 uint64_t crc
= b
->key
.ptr
[0];
191 void *data
= (void *) i
+ 8, *end
= bset_bkey_last(i
);
193 crc
= bch_crc64_update(crc
, data
, end
- data
);
194 return crc
^ 0xffffffffffffffffULL
;
197 void bch_btree_node_read_done(struct btree
*b
)
199 const char *err
= "bad btree header";
200 struct bset
*i
= btree_bset_first(b
);
201 struct btree_iter
*iter
;
203 iter
= mempool_alloc(b
->c
->fill_iter
, GFP_NOIO
);
204 iter
->size
= b
->c
->sb
.bucket_size
/ b
->c
->sb
.block_size
;
207 #ifdef CONFIG_BCACHE_DEBUG
215 b
->written
< btree_blocks(b
) && i
->seq
== b
->keys
.set
[0].data
->seq
;
216 i
= write_block(b
)) {
217 err
= "unsupported bset version";
218 if (i
->version
> BCACHE_BSET_VERSION
)
221 err
= "bad btree header";
222 if (b
->written
+ set_blocks(i
, block_bytes(b
->c
)) >
227 if (i
->magic
!= bset_magic(&b
->c
->sb
))
230 err
= "bad checksum";
231 switch (i
->version
) {
233 if (i
->csum
!= csum_set(i
))
236 case BCACHE_BSET_VERSION
:
237 if (i
->csum
!= btree_csum_set(b
, i
))
243 if (i
!= b
->keys
.set
[0].data
&& !i
->keys
)
246 bch_btree_iter_push(iter
, i
->start
, bset_bkey_last(i
));
248 b
->written
+= set_blocks(i
, block_bytes(b
->c
));
251 err
= "corrupted btree";
252 for (i
= write_block(b
);
253 bset_sector_offset(&b
->keys
, i
) < KEY_SIZE(&b
->key
);
254 i
= ((void *) i
) + block_bytes(b
->c
))
255 if (i
->seq
== b
->keys
.set
[0].data
->seq
)
258 bch_btree_sort_and_fix_extents(&b
->keys
, iter
, &b
->c
->sort
);
260 i
= b
->keys
.set
[0].data
;
261 err
= "short btree key";
262 if (b
->keys
.set
[0].size
&&
263 bkey_cmp(&b
->key
, &b
->keys
.set
[0].end
) < 0)
266 if (b
->written
< btree_blocks(b
))
267 bch_bset_init_next(&b
->keys
, write_block(b
),
268 bset_magic(&b
->c
->sb
));
270 mempool_free(iter
, b
->c
->fill_iter
);
273 set_btree_node_io_error(b
);
274 bch_cache_set_error(b
->c
, "%s at bucket %zu, block %u, %u keys",
275 err
, PTR_BUCKET_NR(b
->c
, &b
->key
, 0),
276 bset_block_offset(b
, i
), i
->keys
);
280 static void btree_node_read_endio(struct bio
*bio
)
282 struct closure
*cl
= bio
->bi_private
;
286 static void bch_btree_node_read(struct btree
*b
)
288 uint64_t start_time
= local_clock();
292 trace_bcache_btree_read(b
);
294 closure_init_stack(&cl
);
296 bio
= bch_bbio_alloc(b
->c
);
297 bio
->bi_iter
.bi_size
= KEY_SIZE(&b
->key
) << 9;
298 bio
->bi_end_io
= btree_node_read_endio
;
299 bio
->bi_private
= &cl
;
300 bio_set_op_attrs(bio
, REQ_OP_READ
, REQ_META
|READ_SYNC
);
302 bch_bio_map(bio
, b
->keys
.set
[0].data
);
304 bch_submit_bbio(bio
, b
->c
, &b
->key
, 0);
308 set_btree_node_io_error(b
);
310 bch_bbio_free(bio
, b
->c
);
312 if (btree_node_io_error(b
))
315 bch_btree_node_read_done(b
);
316 bch_time_stats_update(&b
->c
->btree_read_time
, start_time
);
320 bch_cache_set_error(b
->c
, "io error reading bucket %zu",
321 PTR_BUCKET_NR(b
->c
, &b
->key
, 0));
324 static void btree_complete_write(struct btree
*b
, struct btree_write
*w
)
326 if (w
->prio_blocked
&&
327 !atomic_sub_return(w
->prio_blocked
, &b
->c
->prio_blocked
))
328 wake_up_allocators(b
->c
);
331 atomic_dec_bug(w
->journal
);
332 __closure_wake_up(&b
->c
->journal
.wait
);
339 static void btree_node_write_unlock(struct closure
*cl
)
341 struct btree
*b
= container_of(cl
, struct btree
, io
);
346 static void __btree_node_write_done(struct closure
*cl
)
348 struct btree
*b
= container_of(cl
, struct btree
, io
);
349 struct btree_write
*w
= btree_prev_write(b
);
351 bch_bbio_free(b
->bio
, b
->c
);
353 btree_complete_write(b
, w
);
355 if (btree_node_dirty(b
))
356 schedule_delayed_work(&b
->work
, 30 * HZ
);
358 closure_return_with_destructor(cl
, btree_node_write_unlock
);
361 static void btree_node_write_done(struct closure
*cl
)
363 struct btree
*b
= container_of(cl
, struct btree
, io
);
367 bio_for_each_segment_all(bv
, b
->bio
, n
)
368 __free_page(bv
->bv_page
);
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_error
, "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 bio_set_op_attrs(b
->bio
, REQ_OP_WRITE
, REQ_META
|WRITE_SYNC
|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 int bch_gc_thread(void *arg
)
1766 struct cache_set
*c
= arg
;
1774 set_current_state(TASK_INTERRUPTIBLE
);
1775 if (kthread_should_stop())
1778 mutex_lock(&c
->bucket_lock
);
1780 for_each_cache(ca
, c
, i
)
1781 if (ca
->invalidate_needs_gc
) {
1782 mutex_unlock(&c
->bucket_lock
);
1783 set_current_state(TASK_RUNNING
);
1787 mutex_unlock(&c
->bucket_lock
);
1795 int bch_gc_thread_start(struct cache_set
*c
)
1797 c
->gc_thread
= kthread_create(bch_gc_thread
, c
, "bcache_gc");
1798 if (IS_ERR(c
->gc_thread
))
1799 return PTR_ERR(c
->gc_thread
);
1801 set_task_state(c
->gc_thread
, TASK_INTERRUPTIBLE
);
1805 /* Initial partial gc */
1807 static int bch_btree_check_recurse(struct btree
*b
, struct btree_op
*op
)
1810 struct bkey
*k
, *p
= NULL
;
1811 struct btree_iter iter
;
1813 for_each_key_filter(&b
->keys
, k
, &iter
, bch_ptr_invalid
)
1814 bch_initial_mark_key(b
->c
, b
->level
, k
);
1816 bch_initial_mark_key(b
->c
, b
->level
+ 1, &b
->key
);
1819 bch_btree_iter_init(&b
->keys
, &iter
, NULL
);
1822 k
= bch_btree_iter_next_filter(&iter
, &b
->keys
,
1825 btree_node_prefetch(b
, k
);
1828 ret
= btree(check_recurse
, p
, b
, op
);
1831 } while (p
&& !ret
);
1837 int bch_btree_check(struct cache_set
*c
)
1841 bch_btree_op_init(&op
, SHRT_MAX
);
1843 return btree_root(check_recurse
, c
, &op
);
1846 void bch_initial_gc_finish(struct cache_set
*c
)
1852 bch_btree_gc_finish(c
);
1854 mutex_lock(&c
->bucket_lock
);
1857 * We need to put some unused buckets directly on the prio freelist in
1858 * order to get the allocator thread started - it needs freed buckets in
1859 * order to rewrite the prios and gens, and it needs to rewrite prios
1860 * and gens in order to free buckets.
1862 * This is only safe for buckets that have no live data in them, which
1863 * there should always be some of.
1865 for_each_cache(ca
, c
, i
) {
1866 for_each_bucket(b
, ca
) {
1867 if (fifo_full(&ca
->free
[RESERVE_PRIO
]))
1870 if (bch_can_invalidate_bucket(ca
, b
) &&
1872 __bch_invalidate_one_bucket(ca
, b
);
1873 fifo_push(&ca
->free
[RESERVE_PRIO
],
1879 mutex_unlock(&c
->bucket_lock
);
1882 /* Btree insertion */
1884 static bool btree_insert_key(struct btree
*b
, struct bkey
*k
,
1885 struct bkey
*replace_key
)
1889 BUG_ON(bkey_cmp(k
, &b
->key
) > 0);
1891 status
= bch_btree_insert_key(&b
->keys
, k
, replace_key
);
1892 if (status
!= BTREE_INSERT_STATUS_NO_INSERT
) {
1893 bch_check_keys(&b
->keys
, "%u for %s", status
,
1894 replace_key
? "replace" : "insert");
1896 trace_bcache_btree_insert_key(b
, k
, replace_key
!= NULL
,
1903 static size_t insert_u64s_remaining(struct btree
*b
)
1905 long ret
= bch_btree_keys_u64s_remaining(&b
->keys
);
1908 * Might land in the middle of an existing extent and have to split it
1910 if (b
->keys
.ops
->is_extents
)
1911 ret
-= KEY_MAX_U64S
;
1913 return max(ret
, 0L);
1916 static bool bch_btree_insert_keys(struct btree
*b
, struct btree_op
*op
,
1917 struct keylist
*insert_keys
,
1918 struct bkey
*replace_key
)
1921 int oldsize
= bch_count_data(&b
->keys
);
1923 while (!bch_keylist_empty(insert_keys
)) {
1924 struct bkey
*k
= insert_keys
->keys
;
1926 if (bkey_u64s(k
) > insert_u64s_remaining(b
))
1929 if (bkey_cmp(k
, &b
->key
) <= 0) {
1933 ret
|= btree_insert_key(b
, k
, replace_key
);
1934 bch_keylist_pop_front(insert_keys
);
1935 } else if (bkey_cmp(&START_KEY(k
), &b
->key
) < 0) {
1936 BKEY_PADDED(key
) temp
;
1937 bkey_copy(&temp
.key
, insert_keys
->keys
);
1939 bch_cut_back(&b
->key
, &temp
.key
);
1940 bch_cut_front(&b
->key
, insert_keys
->keys
);
1942 ret
|= btree_insert_key(b
, &temp
.key
, replace_key
);
1950 op
->insert_collision
= true;
1952 BUG_ON(!bch_keylist_empty(insert_keys
) && b
->level
);
1954 BUG_ON(bch_count_data(&b
->keys
) < oldsize
);
1958 static int btree_split(struct btree
*b
, struct btree_op
*op
,
1959 struct keylist
*insert_keys
,
1960 struct bkey
*replace_key
)
1963 struct btree
*n1
, *n2
= NULL
, *n3
= NULL
;
1964 uint64_t start_time
= local_clock();
1966 struct keylist parent_keys
;
1968 closure_init_stack(&cl
);
1969 bch_keylist_init(&parent_keys
);
1971 if (btree_check_reserve(b
, op
)) {
1975 WARN(1, "insufficient reserve for split\n");
1978 n1
= btree_node_alloc_replacement(b
, op
);
1982 split
= set_blocks(btree_bset_first(n1
),
1983 block_bytes(n1
->c
)) > (btree_blocks(b
) * 4) / 5;
1988 trace_bcache_btree_node_split(b
, btree_bset_first(n1
)->keys
);
1990 n2
= bch_btree_node_alloc(b
->c
, op
, b
->level
, b
->parent
);
1995 n3
= bch_btree_node_alloc(b
->c
, op
, b
->level
+ 1, NULL
);
2000 mutex_lock(&n1
->write_lock
);
2001 mutex_lock(&n2
->write_lock
);
2003 bch_btree_insert_keys(n1
, op
, insert_keys
, replace_key
);
2006 * Has to be a linear search because we don't have an auxiliary
2010 while (keys
< (btree_bset_first(n1
)->keys
* 3) / 5)
2011 keys
+= bkey_u64s(bset_bkey_idx(btree_bset_first(n1
),
2014 bkey_copy_key(&n1
->key
,
2015 bset_bkey_idx(btree_bset_first(n1
), keys
));
2016 keys
+= bkey_u64s(bset_bkey_idx(btree_bset_first(n1
), keys
));
2018 btree_bset_first(n2
)->keys
= btree_bset_first(n1
)->keys
- keys
;
2019 btree_bset_first(n1
)->keys
= keys
;
2021 memcpy(btree_bset_first(n2
)->start
,
2022 bset_bkey_last(btree_bset_first(n1
)),
2023 btree_bset_first(n2
)->keys
* sizeof(uint64_t));
2025 bkey_copy_key(&n2
->key
, &b
->key
);
2027 bch_keylist_add(&parent_keys
, &n2
->key
);
2028 bch_btree_node_write(n2
, &cl
);
2029 mutex_unlock(&n2
->write_lock
);
2030 rw_unlock(true, n2
);
2032 trace_bcache_btree_node_compact(b
, btree_bset_first(n1
)->keys
);
2034 mutex_lock(&n1
->write_lock
);
2035 bch_btree_insert_keys(n1
, op
, insert_keys
, replace_key
);
2038 bch_keylist_add(&parent_keys
, &n1
->key
);
2039 bch_btree_node_write(n1
, &cl
);
2040 mutex_unlock(&n1
->write_lock
);
2043 /* Depth increases, make a new root */
2044 mutex_lock(&n3
->write_lock
);
2045 bkey_copy_key(&n3
->key
, &MAX_KEY
);
2046 bch_btree_insert_keys(n3
, op
, &parent_keys
, NULL
);
2047 bch_btree_node_write(n3
, &cl
);
2048 mutex_unlock(&n3
->write_lock
);
2051 bch_btree_set_root(n3
);
2052 rw_unlock(true, n3
);
2053 } else if (!b
->parent
) {
2054 /* Root filled up but didn't need to be split */
2056 bch_btree_set_root(n1
);
2058 /* Split a non root node */
2060 make_btree_freeing_key(b
, parent_keys
.top
);
2061 bch_keylist_push(&parent_keys
);
2063 bch_btree_insert_node(b
->parent
, op
, &parent_keys
, NULL
, NULL
);
2064 BUG_ON(!bch_keylist_empty(&parent_keys
));
2068 rw_unlock(true, n1
);
2070 bch_time_stats_update(&b
->c
->btree_split_time
, start_time
);
2074 bkey_put(b
->c
, &n2
->key
);
2075 btree_node_free(n2
);
2076 rw_unlock(true, n2
);
2078 bkey_put(b
->c
, &n1
->key
);
2079 btree_node_free(n1
);
2080 rw_unlock(true, n1
);
2082 WARN(1, "bcache: btree split failed (level %u)", b
->level
);
2084 if (n3
== ERR_PTR(-EAGAIN
) ||
2085 n2
== ERR_PTR(-EAGAIN
) ||
2086 n1
== ERR_PTR(-EAGAIN
))
2092 static int bch_btree_insert_node(struct btree
*b
, struct btree_op
*op
,
2093 struct keylist
*insert_keys
,
2094 atomic_t
*journal_ref
,
2095 struct bkey
*replace_key
)
2099 BUG_ON(b
->level
&& replace_key
);
2101 closure_init_stack(&cl
);
2103 mutex_lock(&b
->write_lock
);
2105 if (write_block(b
) != btree_bset_last(b
) &&
2106 b
->keys
.last_set_unwritten
)
2107 bch_btree_init_next(b
); /* just wrote a set */
2109 if (bch_keylist_nkeys(insert_keys
) > insert_u64s_remaining(b
)) {
2110 mutex_unlock(&b
->write_lock
);
2114 BUG_ON(write_block(b
) != btree_bset_last(b
));
2116 if (bch_btree_insert_keys(b
, op
, insert_keys
, replace_key
)) {
2118 bch_btree_leaf_dirty(b
, journal_ref
);
2120 bch_btree_node_write(b
, &cl
);
2123 mutex_unlock(&b
->write_lock
);
2125 /* wait for btree node write if necessary, after unlock */
2130 if (current
->bio_list
) {
2131 op
->lock
= b
->c
->root
->level
+ 1;
2133 } else if (op
->lock
<= b
->c
->root
->level
) {
2134 op
->lock
= b
->c
->root
->level
+ 1;
2137 /* Invalidated all iterators */
2138 int ret
= btree_split(b
, op
, insert_keys
, replace_key
);
2140 if (bch_keylist_empty(insert_keys
))
2148 int bch_btree_insert_check_key(struct btree
*b
, struct btree_op
*op
,
2149 struct bkey
*check_key
)
2152 uint64_t btree_ptr
= b
->key
.ptr
[0];
2153 unsigned long seq
= b
->seq
;
2154 struct keylist insert
;
2155 bool upgrade
= op
->lock
== -1;
2157 bch_keylist_init(&insert
);
2160 rw_unlock(false, b
);
2161 rw_lock(true, b
, b
->level
);
2163 if (b
->key
.ptr
[0] != btree_ptr
||
2164 b
->seq
!= seq
+ 1) {
2165 op
->lock
= b
->level
;
2170 SET_KEY_PTRS(check_key
, 1);
2171 get_random_bytes(&check_key
->ptr
[0], sizeof(uint64_t));
2173 SET_PTR_DEV(check_key
, 0, PTR_CHECK_DEV
);
2175 bch_keylist_add(&insert
, check_key
);
2177 ret
= bch_btree_insert_node(b
, op
, &insert
, NULL
, NULL
);
2179 BUG_ON(!ret
&& !bch_keylist_empty(&insert
));
2182 downgrade_write(&b
->lock
);
2186 struct btree_insert_op
{
2188 struct keylist
*keys
;
2189 atomic_t
*journal_ref
;
2190 struct bkey
*replace_key
;
2193 static int btree_insert_fn(struct btree_op
*b_op
, struct btree
*b
)
2195 struct btree_insert_op
*op
= container_of(b_op
,
2196 struct btree_insert_op
, op
);
2198 int ret
= bch_btree_insert_node(b
, &op
->op
, op
->keys
,
2199 op
->journal_ref
, op
->replace_key
);
2200 if (ret
&& !bch_keylist_empty(op
->keys
))
2206 int bch_btree_insert(struct cache_set
*c
, struct keylist
*keys
,
2207 atomic_t
*journal_ref
, struct bkey
*replace_key
)
2209 struct btree_insert_op op
;
2212 BUG_ON(current
->bio_list
);
2213 BUG_ON(bch_keylist_empty(keys
));
2215 bch_btree_op_init(&op
.op
, 0);
2217 op
.journal_ref
= journal_ref
;
2218 op
.replace_key
= replace_key
;
2220 while (!ret
&& !bch_keylist_empty(keys
)) {
2222 ret
= bch_btree_map_leaf_nodes(&op
.op
, c
,
2223 &START_KEY(keys
->keys
),
2230 pr_err("error %i", ret
);
2232 while ((k
= bch_keylist_pop(keys
)))
2234 } else if (op
.op
.insert_collision
)
2240 void bch_btree_set_root(struct btree
*b
)
2245 closure_init_stack(&cl
);
2247 trace_bcache_btree_set_root(b
);
2249 BUG_ON(!b
->written
);
2251 for (i
= 0; i
< KEY_PTRS(&b
->key
); i
++)
2252 BUG_ON(PTR_BUCKET(b
->c
, &b
->key
, i
)->prio
!= BTREE_PRIO
);
2254 mutex_lock(&b
->c
->bucket_lock
);
2255 list_del_init(&b
->list
);
2256 mutex_unlock(&b
->c
->bucket_lock
);
2260 bch_journal_meta(b
->c
, &cl
);
2264 /* Map across nodes or keys */
2266 static int bch_btree_map_nodes_recurse(struct btree
*b
, struct btree_op
*op
,
2268 btree_map_nodes_fn
*fn
, int flags
)
2270 int ret
= MAP_CONTINUE
;
2274 struct btree_iter iter
;
2276 bch_btree_iter_init(&b
->keys
, &iter
, from
);
2278 while ((k
= bch_btree_iter_next_filter(&iter
, &b
->keys
,
2280 ret
= btree(map_nodes_recurse
, k
, b
,
2281 op
, from
, fn
, flags
);
2284 if (ret
!= MAP_CONTINUE
)
2289 if (!b
->level
|| flags
== MAP_ALL_NODES
)
2295 int __bch_btree_map_nodes(struct btree_op
*op
, struct cache_set
*c
,
2296 struct bkey
*from
, btree_map_nodes_fn
*fn
, int flags
)
2298 return btree_root(map_nodes_recurse
, c
, op
, from
, fn
, flags
);
2301 static int bch_btree_map_keys_recurse(struct btree
*b
, struct btree_op
*op
,
2302 struct bkey
*from
, btree_map_keys_fn
*fn
,
2305 int ret
= MAP_CONTINUE
;
2307 struct btree_iter iter
;
2309 bch_btree_iter_init(&b
->keys
, &iter
, from
);
2311 while ((k
= bch_btree_iter_next_filter(&iter
, &b
->keys
, bch_ptr_bad
))) {
2314 : btree(map_keys_recurse
, k
, b
, op
, from
, fn
, flags
);
2317 if (ret
!= MAP_CONTINUE
)
2321 if (!b
->level
&& (flags
& MAP_END_KEY
))
2322 ret
= fn(op
, b
, &KEY(KEY_INODE(&b
->key
),
2323 KEY_OFFSET(&b
->key
), 0));
2328 int bch_btree_map_keys(struct btree_op
*op
, struct cache_set
*c
,
2329 struct bkey
*from
, btree_map_keys_fn
*fn
, int flags
)
2331 return btree_root(map_keys_recurse
, c
, op
, from
, fn
, flags
);
2336 static inline int keybuf_cmp(struct keybuf_key
*l
, struct keybuf_key
*r
)
2338 /* Overlapping keys compare equal */
2339 if (bkey_cmp(&l
->key
, &START_KEY(&r
->key
)) <= 0)
2341 if (bkey_cmp(&START_KEY(&l
->key
), &r
->key
) >= 0)
2346 static inline int keybuf_nonoverlapping_cmp(struct keybuf_key
*l
,
2347 struct keybuf_key
*r
)
2349 return clamp_t(int64_t, bkey_cmp(&l
->key
, &r
->key
), -1, 1);
2357 keybuf_pred_fn
*pred
;
2360 static int refill_keybuf_fn(struct btree_op
*op
, struct btree
*b
,
2363 struct refill
*refill
= container_of(op
, struct refill
, op
);
2364 struct keybuf
*buf
= refill
->buf
;
2365 int ret
= MAP_CONTINUE
;
2367 if (bkey_cmp(k
, refill
->end
) >= 0) {
2372 if (!KEY_SIZE(k
)) /* end key */
2375 if (refill
->pred(buf
, k
)) {
2376 struct keybuf_key
*w
;
2378 spin_lock(&buf
->lock
);
2380 w
= array_alloc(&buf
->freelist
);
2382 spin_unlock(&buf
->lock
);
2387 bkey_copy(&w
->key
, k
);
2389 if (RB_INSERT(&buf
->keys
, w
, node
, keybuf_cmp
))
2390 array_free(&buf
->freelist
, w
);
2394 if (array_freelist_empty(&buf
->freelist
))
2397 spin_unlock(&buf
->lock
);
2400 buf
->last_scanned
= *k
;
2404 void bch_refill_keybuf(struct cache_set
*c
, struct keybuf
*buf
,
2405 struct bkey
*end
, keybuf_pred_fn
*pred
)
2407 struct bkey start
= buf
->last_scanned
;
2408 struct refill refill
;
2412 bch_btree_op_init(&refill
.op
, -1);
2413 refill
.nr_found
= 0;
2418 bch_btree_map_keys(&refill
.op
, c
, &buf
->last_scanned
,
2419 refill_keybuf_fn
, MAP_END_KEY
);
2421 trace_bcache_keyscan(refill
.nr_found
,
2422 KEY_INODE(&start
), KEY_OFFSET(&start
),
2423 KEY_INODE(&buf
->last_scanned
),
2424 KEY_OFFSET(&buf
->last_scanned
));
2426 spin_lock(&buf
->lock
);
2428 if (!RB_EMPTY_ROOT(&buf
->keys
)) {
2429 struct keybuf_key
*w
;
2430 w
= RB_FIRST(&buf
->keys
, struct keybuf_key
, node
);
2431 buf
->start
= START_KEY(&w
->key
);
2433 w
= RB_LAST(&buf
->keys
, struct keybuf_key
, node
);
2436 buf
->start
= MAX_KEY
;
2440 spin_unlock(&buf
->lock
);
2443 static void __bch_keybuf_del(struct keybuf
*buf
, struct keybuf_key
*w
)
2445 rb_erase(&w
->node
, &buf
->keys
);
2446 array_free(&buf
->freelist
, w
);
2449 void bch_keybuf_del(struct keybuf
*buf
, struct keybuf_key
*w
)
2451 spin_lock(&buf
->lock
);
2452 __bch_keybuf_del(buf
, w
);
2453 spin_unlock(&buf
->lock
);
2456 bool bch_keybuf_check_overlapping(struct keybuf
*buf
, struct bkey
*start
,
2460 struct keybuf_key
*p
, *w
, s
;
2463 if (bkey_cmp(end
, &buf
->start
) <= 0 ||
2464 bkey_cmp(start
, &buf
->end
) >= 0)
2467 spin_lock(&buf
->lock
);
2468 w
= RB_GREATER(&buf
->keys
, s
, node
, keybuf_nonoverlapping_cmp
);
2470 while (w
&& bkey_cmp(&START_KEY(&w
->key
), end
) < 0) {
2472 w
= RB_NEXT(w
, node
);
2477 __bch_keybuf_del(buf
, p
);
2480 spin_unlock(&buf
->lock
);
2484 struct keybuf_key
*bch_keybuf_next(struct keybuf
*buf
)
2486 struct keybuf_key
*w
;
2487 spin_lock(&buf
->lock
);
2489 w
= RB_FIRST(&buf
->keys
, struct keybuf_key
, node
);
2491 while (w
&& w
->private)
2492 w
= RB_NEXT(w
, node
);
2495 w
->private = ERR_PTR(-EINTR
);
2497 spin_unlock(&buf
->lock
);
2501 struct keybuf_key
*bch_keybuf_next_rescan(struct cache_set
*c
,
2504 keybuf_pred_fn
*pred
)
2506 struct keybuf_key
*ret
;
2509 ret
= bch_keybuf_next(buf
);
2513 if (bkey_cmp(&buf
->last_scanned
, end
) >= 0) {
2514 pr_debug("scan finished");
2518 bch_refill_keybuf(c
, buf
, end
, pred
);
2524 void bch_keybuf_init(struct keybuf
*buf
)
2526 buf
->last_scanned
= MAX_KEY
;
2527 buf
->keys
= RB_ROOT
;
2529 spin_lock_init(&buf
->lock
);
2530 array_allocator_init(&buf
->freelist
);