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/admin-guide/bcache.rst.
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>
38 #include <linux/delay.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
93 #define MAX_GC_TIMES 100
94 #define MIN_GC_NODES 100
95 #define GC_SLEEP_MS 100
97 #define PTR_DIRTY_BIT (((uint64_t) 1 << 36))
99 #define PTR_HASH(c, k) \
100 (((k)->ptr[0] >> c->bucket_bits) | PTR_GEN(k, 0))
102 #define insert_lock(s, b) ((b)->level <= (s)->lock)
105 static inline struct bset
*write_block(struct btree
*b
)
107 return ((void *) btree_bset_first(b
)) + b
->written
* block_bytes(b
->c
);
110 static void bch_btree_init_next(struct btree
*b
)
112 /* If not a leaf node, always sort */
113 if (b
->level
&& b
->keys
.nsets
)
114 bch_btree_sort(&b
->keys
, &b
->c
->sort
);
116 bch_btree_sort_lazy(&b
->keys
, &b
->c
->sort
);
118 if (b
->written
< btree_blocks(b
))
119 bch_bset_init_next(&b
->keys
, write_block(b
),
120 bset_magic(&b
->c
->sb
));
124 /* Btree key manipulation */
126 void bkey_put(struct cache_set
*c
, struct bkey
*k
)
130 for (i
= 0; i
< KEY_PTRS(k
); i
++)
131 if (ptr_available(c
, k
, i
))
132 atomic_dec_bug(&PTR_BUCKET(c
, k
, i
)->pin
);
137 static uint64_t btree_csum_set(struct btree
*b
, struct bset
*i
)
139 uint64_t crc
= b
->key
.ptr
[0];
140 void *data
= (void *) i
+ 8, *end
= bset_bkey_last(i
);
142 crc
= bch_crc64_update(crc
, data
, end
- data
);
143 return crc
^ 0xffffffffffffffffULL
;
146 void bch_btree_node_read_done(struct btree
*b
)
148 const char *err
= "bad btree header";
149 struct bset
*i
= btree_bset_first(b
);
150 struct btree_iter
*iter
;
153 * c->fill_iter can allocate an iterator with more memory space
154 * than static MAX_BSETS.
155 * See the comment arount cache_set->fill_iter.
157 iter
= mempool_alloc(&b
->c
->fill_iter
, GFP_NOIO
);
158 iter
->size
= b
->c
->sb
.bucket_size
/ b
->c
->sb
.block_size
;
161 #ifdef CONFIG_BCACHE_DEBUG
169 b
->written
< btree_blocks(b
) && i
->seq
== b
->keys
.set
[0].data
->seq
;
170 i
= write_block(b
)) {
171 err
= "unsupported bset version";
172 if (i
->version
> BCACHE_BSET_VERSION
)
175 err
= "bad btree header";
176 if (b
->written
+ set_blocks(i
, block_bytes(b
->c
)) >
181 if (i
->magic
!= bset_magic(&b
->c
->sb
))
184 err
= "bad checksum";
185 switch (i
->version
) {
187 if (i
->csum
!= csum_set(i
))
190 case BCACHE_BSET_VERSION
:
191 if (i
->csum
!= btree_csum_set(b
, i
))
197 if (i
!= b
->keys
.set
[0].data
&& !i
->keys
)
200 bch_btree_iter_push(iter
, i
->start
, bset_bkey_last(i
));
202 b
->written
+= set_blocks(i
, block_bytes(b
->c
));
205 err
= "corrupted btree";
206 for (i
= write_block(b
);
207 bset_sector_offset(&b
->keys
, i
) < KEY_SIZE(&b
->key
);
208 i
= ((void *) i
) + block_bytes(b
->c
))
209 if (i
->seq
== b
->keys
.set
[0].data
->seq
)
212 bch_btree_sort_and_fix_extents(&b
->keys
, iter
, &b
->c
->sort
);
214 i
= b
->keys
.set
[0].data
;
215 err
= "short btree key";
216 if (b
->keys
.set
[0].size
&&
217 bkey_cmp(&b
->key
, &b
->keys
.set
[0].end
) < 0)
220 if (b
->written
< btree_blocks(b
))
221 bch_bset_init_next(&b
->keys
, write_block(b
),
222 bset_magic(&b
->c
->sb
));
224 mempool_free(iter
, &b
->c
->fill_iter
);
227 set_btree_node_io_error(b
);
228 bch_cache_set_error(b
->c
, "%s at bucket %zu, block %u, %u keys",
229 err
, PTR_BUCKET_NR(b
->c
, &b
->key
, 0),
230 bset_block_offset(b
, i
), i
->keys
);
234 static void btree_node_read_endio(struct bio
*bio
)
236 struct closure
*cl
= bio
->bi_private
;
241 static void bch_btree_node_read(struct btree
*b
)
243 uint64_t start_time
= local_clock();
247 trace_bcache_btree_read(b
);
249 closure_init_stack(&cl
);
251 bio
= bch_bbio_alloc(b
->c
);
252 bio
->bi_iter
.bi_size
= KEY_SIZE(&b
->key
) << 9;
253 bio
->bi_end_io
= btree_node_read_endio
;
254 bio
->bi_private
= &cl
;
255 bio
->bi_opf
= REQ_OP_READ
| REQ_META
;
257 bch_bio_map(bio
, b
->keys
.set
[0].data
);
259 bch_submit_bbio(bio
, b
->c
, &b
->key
, 0);
263 set_btree_node_io_error(b
);
265 bch_bbio_free(bio
, b
->c
);
267 if (btree_node_io_error(b
))
270 bch_btree_node_read_done(b
);
271 bch_time_stats_update(&b
->c
->btree_read_time
, start_time
);
275 bch_cache_set_error(b
->c
, "io error reading bucket %zu",
276 PTR_BUCKET_NR(b
->c
, &b
->key
, 0));
279 static void btree_complete_write(struct btree
*b
, struct btree_write
*w
)
281 if (w
->prio_blocked
&&
282 !atomic_sub_return(w
->prio_blocked
, &b
->c
->prio_blocked
))
283 wake_up_allocators(b
->c
);
286 atomic_dec_bug(w
->journal
);
287 __closure_wake_up(&b
->c
->journal
.wait
);
294 static void btree_node_write_unlock(struct closure
*cl
)
296 struct btree
*b
= container_of(cl
, struct btree
, io
);
301 static void __btree_node_write_done(struct closure
*cl
)
303 struct btree
*b
= container_of(cl
, struct btree
, io
);
304 struct btree_write
*w
= btree_prev_write(b
);
306 bch_bbio_free(b
->bio
, b
->c
);
308 btree_complete_write(b
, w
);
310 if (btree_node_dirty(b
))
311 schedule_delayed_work(&b
->work
, 30 * HZ
);
313 closure_return_with_destructor(cl
, btree_node_write_unlock
);
316 static void btree_node_write_done(struct closure
*cl
)
318 struct btree
*b
= container_of(cl
, struct btree
, io
);
320 bio_free_pages(b
->bio
);
321 __btree_node_write_done(cl
);
324 static void btree_node_write_endio(struct bio
*bio
)
326 struct closure
*cl
= bio
->bi_private
;
327 struct btree
*b
= container_of(cl
, struct btree
, io
);
330 set_btree_node_io_error(b
);
332 bch_bbio_count_io_errors(b
->c
, bio
, bio
->bi_status
, "writing btree");
336 static void do_btree_node_write(struct btree
*b
)
338 struct closure
*cl
= &b
->io
;
339 struct bset
*i
= btree_bset_last(b
);
342 i
->version
= BCACHE_BSET_VERSION
;
343 i
->csum
= btree_csum_set(b
, i
);
346 b
->bio
= bch_bbio_alloc(b
->c
);
348 b
->bio
->bi_end_io
= btree_node_write_endio
;
349 b
->bio
->bi_private
= cl
;
350 b
->bio
->bi_iter
.bi_size
= roundup(set_bytes(i
), block_bytes(b
->c
));
351 b
->bio
->bi_opf
= REQ_OP_WRITE
| REQ_META
| REQ_FUA
;
352 bch_bio_map(b
->bio
, i
);
355 * If we're appending to a leaf node, we don't technically need FUA -
356 * this write just needs to be persisted before the next journal write,
357 * which will be marked FLUSH|FUA.
359 * Similarly if we're writing a new btree root - the pointer is going to
360 * be in the next journal entry.
362 * But if we're writing a new btree node (that isn't a root) or
363 * appending to a non leaf btree node, we need either FUA or a flush
364 * when we write the parent with the new pointer. FUA is cheaper than a
365 * flush, and writes appending to leaf nodes aren't blocking anything so
366 * just make all btree node writes FUA to keep things sane.
369 bkey_copy(&k
.key
, &b
->key
);
370 SET_PTR_OFFSET(&k
.key
, 0, PTR_OFFSET(&k
.key
, 0) +
371 bset_sector_offset(&b
->keys
, i
));
373 if (!bch_bio_alloc_pages(b
->bio
, __GFP_NOWARN
|GFP_NOWAIT
)) {
375 void *addr
= (void *) ((unsigned long) i
& ~(PAGE_SIZE
- 1));
376 struct bvec_iter_all iter_all
;
378 bio_for_each_segment_all(bv
, b
->bio
, iter_all
) {
379 memcpy(page_address(bv
->bv_page
), addr
, PAGE_SIZE
);
383 bch_submit_bbio(b
->bio
, b
->c
, &k
.key
, 0);
385 continue_at(cl
, btree_node_write_done
, NULL
);
388 * No problem for multipage bvec since the bio is
392 bch_bio_map(b
->bio
, i
);
394 bch_submit_bbio(b
->bio
, b
->c
, &k
.key
, 0);
397 continue_at_nobarrier(cl
, __btree_node_write_done
, NULL
);
401 void __bch_btree_node_write(struct btree
*b
, struct closure
*parent
)
403 struct bset
*i
= btree_bset_last(b
);
405 lockdep_assert_held(&b
->write_lock
);
407 trace_bcache_btree_write(b
);
409 BUG_ON(current
->bio_list
);
410 BUG_ON(b
->written
>= btree_blocks(b
));
411 BUG_ON(b
->written
&& !i
->keys
);
412 BUG_ON(btree_bset_first(b
)->seq
!= i
->seq
);
413 bch_check_keys(&b
->keys
, "writing");
415 cancel_delayed_work(&b
->work
);
417 /* If caller isn't waiting for write, parent refcount is cache set */
419 closure_init(&b
->io
, parent
?: &b
->c
->cl
);
421 clear_bit(BTREE_NODE_dirty
, &b
->flags
);
422 change_bit(BTREE_NODE_write_idx
, &b
->flags
);
424 do_btree_node_write(b
);
426 atomic_long_add(set_blocks(i
, block_bytes(b
->c
)) * b
->c
->sb
.block_size
,
427 &PTR_CACHE(b
->c
, &b
->key
, 0)->btree_sectors_written
);
429 b
->written
+= set_blocks(i
, block_bytes(b
->c
));
432 void bch_btree_node_write(struct btree
*b
, struct closure
*parent
)
434 unsigned int nsets
= b
->keys
.nsets
;
436 lockdep_assert_held(&b
->lock
);
438 __bch_btree_node_write(b
, parent
);
441 * do verify if there was more than one set initially (i.e. we did a
442 * sort) and we sorted down to a single set:
444 if (nsets
&& !b
->keys
.nsets
)
447 bch_btree_init_next(b
);
450 static void bch_btree_node_write_sync(struct btree
*b
)
454 closure_init_stack(&cl
);
456 mutex_lock(&b
->write_lock
);
457 bch_btree_node_write(b
, &cl
);
458 mutex_unlock(&b
->write_lock
);
463 static void btree_node_write_work(struct work_struct
*w
)
465 struct btree
*b
= container_of(to_delayed_work(w
), struct btree
, work
);
467 mutex_lock(&b
->write_lock
);
468 if (btree_node_dirty(b
))
469 __bch_btree_node_write(b
, NULL
);
470 mutex_unlock(&b
->write_lock
);
473 static void bch_btree_leaf_dirty(struct btree
*b
, atomic_t
*journal_ref
)
475 struct bset
*i
= btree_bset_last(b
);
476 struct btree_write
*w
= btree_current_write(b
);
478 lockdep_assert_held(&b
->write_lock
);
483 if (!btree_node_dirty(b
))
484 schedule_delayed_work(&b
->work
, 30 * HZ
);
486 set_btree_node_dirty(b
);
489 * w->journal is always the oldest journal pin of all bkeys
490 * in the leaf node, to make sure the oldest jset seq won't
491 * be increased before this btree node is flushed.
495 journal_pin_cmp(b
->c
, w
->journal
, journal_ref
)) {
496 atomic_dec_bug(w
->journal
);
501 w
->journal
= journal_ref
;
502 atomic_inc(w
->journal
);
506 /* Force write if set is too big */
507 if (set_bytes(i
) > PAGE_SIZE
- 48 &&
509 bch_btree_node_write(b
, NULL
);
513 * Btree in memory cache - allocation/freeing
514 * mca -> memory cache
517 #define mca_reserve(c) (((c->root && c->root->level) \
518 ? c->root->level : 1) * 8 + 16)
519 #define mca_can_free(c) \
520 max_t(int, 0, c->btree_cache_used - mca_reserve(c))
522 static void mca_data_free(struct btree
*b
)
524 BUG_ON(b
->io_mutex
.count
!= 1);
526 bch_btree_keys_free(&b
->keys
);
528 b
->c
->btree_cache_used
--;
529 list_move(&b
->list
, &b
->c
->btree_cache_freed
);
532 static void mca_bucket_free(struct btree
*b
)
534 BUG_ON(btree_node_dirty(b
));
537 hlist_del_init_rcu(&b
->hash
);
538 list_move(&b
->list
, &b
->c
->btree_cache_freeable
);
541 static unsigned int btree_order(struct bkey
*k
)
543 return ilog2(KEY_SIZE(k
) / PAGE_SECTORS
?: 1);
546 static void mca_data_alloc(struct btree
*b
, struct bkey
*k
, gfp_t gfp
)
548 if (!bch_btree_keys_alloc(&b
->keys
,
550 ilog2(b
->c
->btree_pages
),
553 b
->c
->btree_cache_used
++;
554 list_move(&b
->list
, &b
->c
->btree_cache
);
556 list_move(&b
->list
, &b
->c
->btree_cache_freed
);
560 static struct btree
*mca_bucket_alloc(struct cache_set
*c
,
561 struct bkey
*k
, gfp_t gfp
)
564 * kzalloc() is necessary here for initialization,
565 * see code comments in bch_btree_keys_init().
567 struct btree
*b
= kzalloc(sizeof(struct btree
), gfp
);
572 init_rwsem(&b
->lock
);
573 lockdep_set_novalidate_class(&b
->lock
);
574 mutex_init(&b
->write_lock
);
575 lockdep_set_novalidate_class(&b
->write_lock
);
576 INIT_LIST_HEAD(&b
->list
);
577 INIT_DELAYED_WORK(&b
->work
, btree_node_write_work
);
579 sema_init(&b
->io_mutex
, 1);
581 mca_data_alloc(b
, k
, gfp
);
585 static int mca_reap(struct btree
*b
, unsigned int min_order
, bool flush
)
589 closure_init_stack(&cl
);
590 lockdep_assert_held(&b
->c
->bucket_lock
);
592 if (!down_write_trylock(&b
->lock
))
595 BUG_ON(btree_node_dirty(b
) && !b
->keys
.set
[0].data
);
597 if (b
->keys
.page_order
< min_order
)
601 if (btree_node_dirty(b
))
604 if (down_trylock(&b
->io_mutex
))
611 * BTREE_NODE_dirty might be cleared in btree_flush_btree() by
612 * __bch_btree_node_write(). To avoid an extra flush, acquire
613 * b->write_lock before checking BTREE_NODE_dirty bit.
615 mutex_lock(&b
->write_lock
);
617 * If this btree node is selected in btree_flush_write() by journal
618 * code, delay and retry until the node is flushed by journal code
619 * and BTREE_NODE_journal_flush bit cleared by btree_flush_write().
621 if (btree_node_journal_flush(b
)) {
622 pr_debug("bnode %p is flushing by journal, retry", b
);
623 mutex_unlock(&b
->write_lock
);
628 if (btree_node_dirty(b
))
629 __bch_btree_node_write(b
, &cl
);
630 mutex_unlock(&b
->write_lock
);
634 /* wait for any in flight btree write */
644 static unsigned long bch_mca_scan(struct shrinker
*shrink
,
645 struct shrink_control
*sc
)
647 struct cache_set
*c
= container_of(shrink
, struct cache_set
, shrink
);
649 unsigned long i
, nr
= sc
->nr_to_scan
;
650 unsigned long freed
= 0;
651 unsigned int btree_cache_used
;
653 if (c
->shrinker_disabled
)
656 if (c
->btree_cache_alloc_lock
)
659 /* Return -1 if we can't do anything right now */
660 if (sc
->gfp_mask
& __GFP_IO
)
661 mutex_lock(&c
->bucket_lock
);
662 else if (!mutex_trylock(&c
->bucket_lock
))
666 * It's _really_ critical that we don't free too many btree nodes - we
667 * have to always leave ourselves a reserve. The reserve is how we
668 * guarantee that allocating memory for a new btree node can always
669 * succeed, so that inserting keys into the btree can always succeed and
670 * IO can always make forward progress:
672 nr
/= c
->btree_pages
;
675 nr
= min_t(unsigned long, nr
, mca_can_free(c
));
678 btree_cache_used
= c
->btree_cache_used
;
679 list_for_each_entry_safe_reverse(b
, t
, &c
->btree_cache_freeable
, list
) {
683 if (!mca_reap(b
, 0, false)) {
692 list_for_each_entry_safe_reverse(b
, t
, &c
->btree_cache
, list
) {
693 if (nr
<= 0 || i
>= btree_cache_used
)
696 if (!mca_reap(b
, 0, false)) {
707 mutex_unlock(&c
->bucket_lock
);
708 return freed
* c
->btree_pages
;
711 static unsigned long bch_mca_count(struct shrinker
*shrink
,
712 struct shrink_control
*sc
)
714 struct cache_set
*c
= container_of(shrink
, struct cache_set
, shrink
);
716 if (c
->shrinker_disabled
)
719 if (c
->btree_cache_alloc_lock
)
722 return mca_can_free(c
) * c
->btree_pages
;
725 void bch_btree_cache_free(struct cache_set
*c
)
730 closure_init_stack(&cl
);
732 if (c
->shrink
.list
.next
)
733 unregister_shrinker(&c
->shrink
);
735 mutex_lock(&c
->bucket_lock
);
737 #ifdef CONFIG_BCACHE_DEBUG
739 list_move(&c
->verify_data
->list
, &c
->btree_cache
);
741 free_pages((unsigned long) c
->verify_ondisk
, ilog2(bucket_pages(c
)));
744 list_splice(&c
->btree_cache_freeable
,
747 while (!list_empty(&c
->btree_cache
)) {
748 b
= list_first_entry(&c
->btree_cache
, struct btree
, list
);
751 * This function is called by cache_set_free(), no I/O
752 * request on cache now, it is unnecessary to acquire
753 * b->write_lock before clearing BTREE_NODE_dirty anymore.
755 if (btree_node_dirty(b
)) {
756 btree_complete_write(b
, btree_current_write(b
));
757 clear_bit(BTREE_NODE_dirty
, &b
->flags
);
762 while (!list_empty(&c
->btree_cache_freed
)) {
763 b
= list_first_entry(&c
->btree_cache_freed
,
766 cancel_delayed_work_sync(&b
->work
);
770 mutex_unlock(&c
->bucket_lock
);
773 int bch_btree_cache_alloc(struct cache_set
*c
)
777 for (i
= 0; i
< mca_reserve(c
); i
++)
778 if (!mca_bucket_alloc(c
, &ZERO_KEY
, GFP_KERNEL
))
781 list_splice_init(&c
->btree_cache
,
782 &c
->btree_cache_freeable
);
784 #ifdef CONFIG_BCACHE_DEBUG
785 mutex_init(&c
->verify_lock
);
787 c
->verify_ondisk
= (void *)
788 __get_free_pages(GFP_KERNEL
, ilog2(bucket_pages(c
)));
790 c
->verify_data
= mca_bucket_alloc(c
, &ZERO_KEY
, GFP_KERNEL
);
792 if (c
->verify_data
&&
793 c
->verify_data
->keys
.set
->data
)
794 list_del_init(&c
->verify_data
->list
);
796 c
->verify_data
= NULL
;
799 c
->shrink
.count_objects
= bch_mca_count
;
800 c
->shrink
.scan_objects
= bch_mca_scan
;
802 c
->shrink
.batch
= c
->btree_pages
* 2;
804 if (register_shrinker(&c
->shrink
))
805 pr_warn("bcache: %s: could not register shrinker",
811 /* Btree in memory cache - hash table */
813 static struct hlist_head
*mca_hash(struct cache_set
*c
, struct bkey
*k
)
815 return &c
->bucket_hash
[hash_32(PTR_HASH(c
, k
), BUCKET_HASH_BITS
)];
818 static struct btree
*mca_find(struct cache_set
*c
, struct bkey
*k
)
823 hlist_for_each_entry_rcu(b
, mca_hash(c
, k
), hash
)
824 if (PTR_HASH(c
, &b
->key
) == PTR_HASH(c
, k
))
832 static int mca_cannibalize_lock(struct cache_set
*c
, struct btree_op
*op
)
834 spin_lock(&c
->btree_cannibalize_lock
);
835 if (likely(c
->btree_cache_alloc_lock
== NULL
)) {
836 c
->btree_cache_alloc_lock
= current
;
837 } else if (c
->btree_cache_alloc_lock
!= current
) {
839 prepare_to_wait(&c
->btree_cache_wait
, &op
->wait
,
840 TASK_UNINTERRUPTIBLE
);
841 spin_unlock(&c
->btree_cannibalize_lock
);
844 spin_unlock(&c
->btree_cannibalize_lock
);
849 static struct btree
*mca_cannibalize(struct cache_set
*c
, struct btree_op
*op
,
854 trace_bcache_btree_cache_cannibalize(c
);
856 if (mca_cannibalize_lock(c
, op
))
857 return ERR_PTR(-EINTR
);
859 list_for_each_entry_reverse(b
, &c
->btree_cache
, list
)
860 if (!mca_reap(b
, btree_order(k
), false))
863 list_for_each_entry_reverse(b
, &c
->btree_cache
, list
)
864 if (!mca_reap(b
, btree_order(k
), true))
867 WARN(1, "btree cache cannibalize failed\n");
868 return ERR_PTR(-ENOMEM
);
872 * We can only have one thread cannibalizing other cached btree nodes at a time,
873 * or we'll deadlock. We use an open coded mutex to ensure that, which a
874 * cannibalize_bucket() will take. This means every time we unlock the root of
875 * the btree, we need to release this lock if we have it held.
877 static void bch_cannibalize_unlock(struct cache_set
*c
)
879 spin_lock(&c
->btree_cannibalize_lock
);
880 if (c
->btree_cache_alloc_lock
== current
) {
881 c
->btree_cache_alloc_lock
= NULL
;
882 wake_up(&c
->btree_cache_wait
);
884 spin_unlock(&c
->btree_cannibalize_lock
);
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
);
1004 if (btree_node_io_error(b
)) {
1005 rw_unlock(write
, b
);
1006 return ERR_PTR(-EIO
);
1009 BUG_ON(!b
->written
);
1013 for (; i
<= b
->keys
.nsets
&& b
->keys
.set
[i
].size
; i
++) {
1014 prefetch(b
->keys
.set
[i
].tree
);
1015 prefetch(b
->keys
.set
[i
].data
);
1018 for (; i
<= b
->keys
.nsets
; i
++)
1019 prefetch(b
->keys
.set
[i
].data
);
1024 static void btree_node_prefetch(struct btree
*parent
, struct bkey
*k
)
1028 mutex_lock(&parent
->c
->bucket_lock
);
1029 b
= mca_alloc(parent
->c
, NULL
, k
, parent
->level
- 1);
1030 mutex_unlock(&parent
->c
->bucket_lock
);
1032 if (!IS_ERR_OR_NULL(b
)) {
1034 bch_btree_node_read(b
);
1041 static void btree_node_free(struct btree
*b
)
1043 trace_bcache_btree_node_free(b
);
1045 BUG_ON(b
== b
->c
->root
);
1048 mutex_lock(&b
->write_lock
);
1050 * If the btree node is selected and flushing in btree_flush_write(),
1051 * delay and retry until the BTREE_NODE_journal_flush bit cleared,
1052 * then it is safe to free the btree node here. Otherwise this btree
1053 * node will be in race condition.
1055 if (btree_node_journal_flush(b
)) {
1056 mutex_unlock(&b
->write_lock
);
1057 pr_debug("bnode %p journal_flush set, retry", b
);
1062 if (btree_node_dirty(b
)) {
1063 btree_complete_write(b
, btree_current_write(b
));
1064 clear_bit(BTREE_NODE_dirty
, &b
->flags
);
1067 mutex_unlock(&b
->write_lock
);
1069 cancel_delayed_work(&b
->work
);
1071 mutex_lock(&b
->c
->bucket_lock
);
1072 bch_bucket_free(b
->c
, &b
->key
);
1074 mutex_unlock(&b
->c
->bucket_lock
);
1077 struct btree
*__bch_btree_node_alloc(struct cache_set
*c
, struct btree_op
*op
,
1078 int level
, bool wait
,
1079 struct btree
*parent
)
1082 struct btree
*b
= ERR_PTR(-EAGAIN
);
1084 mutex_lock(&c
->bucket_lock
);
1086 if (__bch_bucket_alloc_set(c
, RESERVE_BTREE
, &k
.key
, 1, wait
))
1089 bkey_put(c
, &k
.key
);
1090 SET_KEY_SIZE(&k
.key
, c
->btree_pages
* PAGE_SECTORS
);
1092 b
= mca_alloc(c
, op
, &k
.key
, level
);
1098 "Tried to allocate bucket that was in btree cache");
1103 bch_bset_init_next(&b
->keys
, b
->keys
.set
->data
, bset_magic(&b
->c
->sb
));
1105 mutex_unlock(&c
->bucket_lock
);
1107 trace_bcache_btree_node_alloc(b
);
1110 bch_bucket_free(c
, &k
.key
);
1112 mutex_unlock(&c
->bucket_lock
);
1114 trace_bcache_btree_node_alloc_fail(c
);
1118 static struct btree
*bch_btree_node_alloc(struct cache_set
*c
,
1119 struct btree_op
*op
, int level
,
1120 struct btree
*parent
)
1122 return __bch_btree_node_alloc(c
, op
, level
, op
!= NULL
, parent
);
1125 static struct btree
*btree_node_alloc_replacement(struct btree
*b
,
1126 struct btree_op
*op
)
1128 struct btree
*n
= bch_btree_node_alloc(b
->c
, op
, b
->level
, b
->parent
);
1130 if (!IS_ERR_OR_NULL(n
)) {
1131 mutex_lock(&n
->write_lock
);
1132 bch_btree_sort_into(&b
->keys
, &n
->keys
, &b
->c
->sort
);
1133 bkey_copy_key(&n
->key
, &b
->key
);
1134 mutex_unlock(&n
->write_lock
);
1140 static void make_btree_freeing_key(struct btree
*b
, struct bkey
*k
)
1144 mutex_lock(&b
->c
->bucket_lock
);
1146 atomic_inc(&b
->c
->prio_blocked
);
1148 bkey_copy(k
, &b
->key
);
1149 bkey_copy_key(k
, &ZERO_KEY
);
1151 for (i
= 0; i
< KEY_PTRS(k
); i
++)
1153 bch_inc_gen(PTR_CACHE(b
->c
, &b
->key
, i
),
1154 PTR_BUCKET(b
->c
, &b
->key
, i
)));
1156 mutex_unlock(&b
->c
->bucket_lock
);
1159 static int btree_check_reserve(struct btree
*b
, struct btree_op
*op
)
1161 struct cache_set
*c
= b
->c
;
1163 unsigned int i
, reserve
= (c
->root
->level
- b
->level
) * 2 + 1;
1165 mutex_lock(&c
->bucket_lock
);
1167 for_each_cache(ca
, c
, i
)
1168 if (fifo_used(&ca
->free
[RESERVE_BTREE
]) < reserve
) {
1170 prepare_to_wait(&c
->btree_cache_wait
, &op
->wait
,
1171 TASK_UNINTERRUPTIBLE
);
1172 mutex_unlock(&c
->bucket_lock
);
1176 mutex_unlock(&c
->bucket_lock
);
1178 return mca_cannibalize_lock(b
->c
, op
);
1181 /* Garbage collection */
1183 static uint8_t __bch_btree_mark_key(struct cache_set
*c
, int level
,
1191 * ptr_invalid() can't return true for the keys that mark btree nodes as
1192 * freed, but since ptr_bad() returns true we'll never actually use them
1193 * for anything and thus we don't want mark their pointers here
1195 if (!bkey_cmp(k
, &ZERO_KEY
))
1198 for (i
= 0; i
< KEY_PTRS(k
); i
++) {
1199 if (!ptr_available(c
, k
, i
))
1202 g
= PTR_BUCKET(c
, k
, i
);
1204 if (gen_after(g
->last_gc
, PTR_GEN(k
, i
)))
1205 g
->last_gc
= PTR_GEN(k
, i
);
1207 if (ptr_stale(c
, k
, i
)) {
1208 stale
= max(stale
, ptr_stale(c
, k
, i
));
1212 cache_bug_on(GC_MARK(g
) &&
1213 (GC_MARK(g
) == GC_MARK_METADATA
) != (level
!= 0),
1214 c
, "inconsistent ptrs: mark = %llu, level = %i",
1218 SET_GC_MARK(g
, GC_MARK_METADATA
);
1219 else if (KEY_DIRTY(k
))
1220 SET_GC_MARK(g
, GC_MARK_DIRTY
);
1221 else if (!GC_MARK(g
))
1222 SET_GC_MARK(g
, GC_MARK_RECLAIMABLE
);
1224 /* guard against overflow */
1225 SET_GC_SECTORS_USED(g
, min_t(unsigned int,
1226 GC_SECTORS_USED(g
) + KEY_SIZE(k
),
1227 MAX_GC_SECTORS_USED
));
1229 BUG_ON(!GC_SECTORS_USED(g
));
1235 #define btree_mark_key(b, k) __bch_btree_mark_key(b->c, b->level, k)
1237 void bch_initial_mark_key(struct cache_set
*c
, int level
, struct bkey
*k
)
1241 for (i
= 0; i
< KEY_PTRS(k
); i
++)
1242 if (ptr_available(c
, k
, i
) &&
1243 !ptr_stale(c
, k
, i
)) {
1244 struct bucket
*b
= PTR_BUCKET(c
, k
, i
);
1246 b
->gen
= PTR_GEN(k
, i
);
1248 if (level
&& bkey_cmp(k
, &ZERO_KEY
))
1249 b
->prio
= BTREE_PRIO
;
1250 else if (!level
&& b
->prio
== BTREE_PRIO
)
1251 b
->prio
= INITIAL_PRIO
;
1254 __bch_btree_mark_key(c
, level
, k
);
1257 void bch_update_bucket_in_use(struct cache_set
*c
, struct gc_stat
*stats
)
1259 stats
->in_use
= (c
->nbuckets
- c
->avail_nbuckets
) * 100 / c
->nbuckets
;
1262 static bool btree_gc_mark_node(struct btree
*b
, struct gc_stat
*gc
)
1265 unsigned int keys
= 0, good_keys
= 0;
1267 struct btree_iter iter
;
1268 struct bset_tree
*t
;
1272 for_each_key_filter(&b
->keys
, k
, &iter
, bch_ptr_invalid
) {
1273 stale
= max(stale
, btree_mark_key(b
, k
));
1276 if (bch_ptr_bad(&b
->keys
, k
))
1279 gc
->key_bytes
+= bkey_u64s(k
);
1283 gc
->data
+= KEY_SIZE(k
);
1286 for (t
= b
->keys
.set
; t
<= &b
->keys
.set
[b
->keys
.nsets
]; t
++)
1287 btree_bug_on(t
->size
&&
1288 bset_written(&b
->keys
, t
) &&
1289 bkey_cmp(&b
->key
, &t
->end
) < 0,
1290 b
, "found short btree key in gc");
1292 if (b
->c
->gc_always_rewrite
)
1298 if ((keys
- good_keys
) * 2 > keys
)
1304 #define GC_MERGE_NODES 4U
1306 struct gc_merge_info
{
1311 static int bch_btree_insert_node(struct btree
*b
, struct btree_op
*op
,
1312 struct keylist
*insert_keys
,
1313 atomic_t
*journal_ref
,
1314 struct bkey
*replace_key
);
1316 static int btree_gc_coalesce(struct btree
*b
, struct btree_op
*op
,
1317 struct gc_stat
*gc
, struct gc_merge_info
*r
)
1319 unsigned int i
, nodes
= 0, keys
= 0, blocks
;
1320 struct btree
*new_nodes
[GC_MERGE_NODES
];
1321 struct keylist keylist
;
1325 bch_keylist_init(&keylist
);
1327 if (btree_check_reserve(b
, NULL
))
1330 memset(new_nodes
, 0, sizeof(new_nodes
));
1331 closure_init_stack(&cl
);
1333 while (nodes
< GC_MERGE_NODES
&& !IS_ERR_OR_NULL(r
[nodes
].b
))
1334 keys
+= r
[nodes
++].keys
;
1336 blocks
= btree_default_blocks(b
->c
) * 2 / 3;
1339 __set_blocks(b
->keys
.set
[0].data
, keys
,
1340 block_bytes(b
->c
)) > blocks
* (nodes
- 1))
1343 for (i
= 0; i
< nodes
; i
++) {
1344 new_nodes
[i
] = btree_node_alloc_replacement(r
[i
].b
, NULL
);
1345 if (IS_ERR_OR_NULL(new_nodes
[i
]))
1346 goto out_nocoalesce
;
1350 * We have to check the reserve here, after we've allocated our new
1351 * nodes, to make sure the insert below will succeed - we also check
1352 * before as an optimization to potentially avoid a bunch of expensive
1355 if (btree_check_reserve(b
, NULL
))
1356 goto out_nocoalesce
;
1358 for (i
= 0; i
< nodes
; i
++)
1359 mutex_lock(&new_nodes
[i
]->write_lock
);
1361 for (i
= nodes
- 1; i
> 0; --i
) {
1362 struct bset
*n1
= btree_bset_first(new_nodes
[i
]);
1363 struct bset
*n2
= btree_bset_first(new_nodes
[i
- 1]);
1364 struct bkey
*k
, *last
= NULL
;
1370 k
< bset_bkey_last(n2
);
1372 if (__set_blocks(n1
, n1
->keys
+ keys
+
1374 block_bytes(b
->c
)) > blocks
)
1378 keys
+= bkey_u64s(k
);
1382 * Last node we're not getting rid of - we're getting
1383 * rid of the node at r[0]. Have to try and fit all of
1384 * the remaining keys into this node; we can't ensure
1385 * they will always fit due to rounding and variable
1386 * length keys (shouldn't be possible in practice,
1389 if (__set_blocks(n1
, n1
->keys
+ n2
->keys
,
1390 block_bytes(b
->c
)) >
1391 btree_blocks(new_nodes
[i
]))
1392 goto out_nocoalesce
;
1395 /* Take the key of the node we're getting rid of */
1399 BUG_ON(__set_blocks(n1
, n1
->keys
+ keys
, block_bytes(b
->c
)) >
1400 btree_blocks(new_nodes
[i
]));
1403 bkey_copy_key(&new_nodes
[i
]->key
, last
);
1405 memcpy(bset_bkey_last(n1
),
1407 (void *) bset_bkey_idx(n2
, keys
) - (void *) n2
->start
);
1410 r
[i
].keys
= n1
->keys
;
1413 bset_bkey_idx(n2
, keys
),
1414 (void *) bset_bkey_last(n2
) -
1415 (void *) bset_bkey_idx(n2
, keys
));
1419 if (__bch_keylist_realloc(&keylist
,
1420 bkey_u64s(&new_nodes
[i
]->key
)))
1421 goto out_nocoalesce
;
1423 bch_btree_node_write(new_nodes
[i
], &cl
);
1424 bch_keylist_add(&keylist
, &new_nodes
[i
]->key
);
1427 for (i
= 0; i
< nodes
; i
++)
1428 mutex_unlock(&new_nodes
[i
]->write_lock
);
1432 /* We emptied out this node */
1433 BUG_ON(btree_bset_first(new_nodes
[0])->keys
);
1434 btree_node_free(new_nodes
[0]);
1435 rw_unlock(true, new_nodes
[0]);
1436 new_nodes
[0] = NULL
;
1438 for (i
= 0; i
< nodes
; i
++) {
1439 if (__bch_keylist_realloc(&keylist
, bkey_u64s(&r
[i
].b
->key
)))
1440 goto out_nocoalesce
;
1442 make_btree_freeing_key(r
[i
].b
, keylist
.top
);
1443 bch_keylist_push(&keylist
);
1446 bch_btree_insert_node(b
, op
, &keylist
, NULL
, NULL
);
1447 BUG_ON(!bch_keylist_empty(&keylist
));
1449 for (i
= 0; i
< nodes
; i
++) {
1450 btree_node_free(r
[i
].b
);
1451 rw_unlock(true, r
[i
].b
);
1453 r
[i
].b
= new_nodes
[i
];
1456 memmove(r
, r
+ 1, sizeof(r
[0]) * (nodes
- 1));
1457 r
[nodes
- 1].b
= ERR_PTR(-EINTR
);
1459 trace_bcache_btree_gc_coalesce(nodes
);
1462 bch_keylist_free(&keylist
);
1464 /* Invalidated our iterator */
1470 while ((k
= bch_keylist_pop(&keylist
)))
1471 if (!bkey_cmp(k
, &ZERO_KEY
))
1472 atomic_dec(&b
->c
->prio_blocked
);
1473 bch_keylist_free(&keylist
);
1475 for (i
= 0; i
< nodes
; i
++)
1476 if (!IS_ERR_OR_NULL(new_nodes
[i
])) {
1477 btree_node_free(new_nodes
[i
]);
1478 rw_unlock(true, new_nodes
[i
]);
1483 static int btree_gc_rewrite_node(struct btree
*b
, struct btree_op
*op
,
1484 struct btree
*replace
)
1486 struct keylist keys
;
1489 if (btree_check_reserve(b
, NULL
))
1492 n
= btree_node_alloc_replacement(replace
, NULL
);
1494 /* recheck reserve after allocating replacement node */
1495 if (btree_check_reserve(b
, NULL
)) {
1501 bch_btree_node_write_sync(n
);
1503 bch_keylist_init(&keys
);
1504 bch_keylist_add(&keys
, &n
->key
);
1506 make_btree_freeing_key(replace
, keys
.top
);
1507 bch_keylist_push(&keys
);
1509 bch_btree_insert_node(b
, op
, &keys
, NULL
, NULL
);
1510 BUG_ON(!bch_keylist_empty(&keys
));
1512 btree_node_free(replace
);
1515 /* Invalidated our iterator */
1519 static unsigned int btree_gc_count_keys(struct btree
*b
)
1522 struct btree_iter iter
;
1523 unsigned int ret
= 0;
1525 for_each_key_filter(&b
->keys
, k
, &iter
, bch_ptr_bad
)
1526 ret
+= bkey_u64s(k
);
1531 static size_t btree_gc_min_nodes(struct cache_set
*c
)
1536 * Since incremental GC would stop 100ms when front
1537 * side I/O comes, so when there are many btree nodes,
1538 * if GC only processes constant (100) nodes each time,
1539 * GC would last a long time, and the front side I/Os
1540 * would run out of the buckets (since no new bucket
1541 * can be allocated during GC), and be blocked again.
1542 * So GC should not process constant nodes, but varied
1543 * nodes according to the number of btree nodes, which
1544 * realized by dividing GC into constant(100) times,
1545 * so when there are many btree nodes, GC can process
1546 * more nodes each time, otherwise, GC will process less
1547 * nodes each time (but no less than MIN_GC_NODES)
1549 min_nodes
= c
->gc_stats
.nodes
/ MAX_GC_TIMES
;
1550 if (min_nodes
< MIN_GC_NODES
)
1551 min_nodes
= MIN_GC_NODES
;
1557 static int btree_gc_recurse(struct btree
*b
, struct btree_op
*op
,
1558 struct closure
*writes
, struct gc_stat
*gc
)
1561 bool should_rewrite
;
1563 struct btree_iter iter
;
1564 struct gc_merge_info r
[GC_MERGE_NODES
];
1565 struct gc_merge_info
*i
, *last
= r
+ ARRAY_SIZE(r
) - 1;
1567 bch_btree_iter_init(&b
->keys
, &iter
, &b
->c
->gc_done
);
1569 for (i
= r
; i
< r
+ ARRAY_SIZE(r
); i
++)
1570 i
->b
= ERR_PTR(-EINTR
);
1573 k
= bch_btree_iter_next_filter(&iter
, &b
->keys
, bch_ptr_bad
);
1575 r
->b
= bch_btree_node_get(b
->c
, op
, k
, b
->level
- 1,
1578 ret
= PTR_ERR(r
->b
);
1582 r
->keys
= btree_gc_count_keys(r
->b
);
1584 ret
= btree_gc_coalesce(b
, op
, gc
, r
);
1592 if (!IS_ERR(last
->b
)) {
1593 should_rewrite
= btree_gc_mark_node(last
->b
, gc
);
1594 if (should_rewrite
) {
1595 ret
= btree_gc_rewrite_node(b
, op
, last
->b
);
1600 if (last
->b
->level
) {
1601 ret
= btree_gc_recurse(last
->b
, op
, writes
, gc
);
1606 bkey_copy_key(&b
->c
->gc_done
, &last
->b
->key
);
1609 * Must flush leaf nodes before gc ends, since replace
1610 * operations aren't journalled
1612 mutex_lock(&last
->b
->write_lock
);
1613 if (btree_node_dirty(last
->b
))
1614 bch_btree_node_write(last
->b
, writes
);
1615 mutex_unlock(&last
->b
->write_lock
);
1616 rw_unlock(true, last
->b
);
1619 memmove(r
+ 1, r
, sizeof(r
[0]) * (GC_MERGE_NODES
- 1));
1622 if (atomic_read(&b
->c
->search_inflight
) &&
1623 gc
->nodes
>= gc
->nodes_pre
+ btree_gc_min_nodes(b
->c
)) {
1624 gc
->nodes_pre
= gc
->nodes
;
1629 if (need_resched()) {
1635 for (i
= r
; i
< r
+ ARRAY_SIZE(r
); i
++)
1636 if (!IS_ERR_OR_NULL(i
->b
)) {
1637 mutex_lock(&i
->b
->write_lock
);
1638 if (btree_node_dirty(i
->b
))
1639 bch_btree_node_write(i
->b
, writes
);
1640 mutex_unlock(&i
->b
->write_lock
);
1641 rw_unlock(true, i
->b
);
1647 static int bch_btree_gc_root(struct btree
*b
, struct btree_op
*op
,
1648 struct closure
*writes
, struct gc_stat
*gc
)
1650 struct btree
*n
= NULL
;
1652 bool should_rewrite
;
1654 should_rewrite
= btree_gc_mark_node(b
, gc
);
1655 if (should_rewrite
) {
1656 n
= btree_node_alloc_replacement(b
, NULL
);
1658 if (!IS_ERR_OR_NULL(n
)) {
1659 bch_btree_node_write_sync(n
);
1661 bch_btree_set_root(n
);
1669 __bch_btree_mark_key(b
->c
, b
->level
+ 1, &b
->key
);
1672 ret
= btree_gc_recurse(b
, op
, writes
, gc
);
1677 bkey_copy_key(&b
->c
->gc_done
, &b
->key
);
1682 static void btree_gc_start(struct cache_set
*c
)
1688 if (!c
->gc_mark_valid
)
1691 mutex_lock(&c
->bucket_lock
);
1693 c
->gc_mark_valid
= 0;
1694 c
->gc_done
= ZERO_KEY
;
1696 for_each_cache(ca
, c
, i
)
1697 for_each_bucket(b
, ca
) {
1698 b
->last_gc
= b
->gen
;
1699 if (!atomic_read(&b
->pin
)) {
1701 SET_GC_SECTORS_USED(b
, 0);
1705 mutex_unlock(&c
->bucket_lock
);
1708 static void bch_btree_gc_finish(struct cache_set
*c
)
1714 mutex_lock(&c
->bucket_lock
);
1717 c
->gc_mark_valid
= 1;
1720 for (i
= 0; i
< KEY_PTRS(&c
->uuid_bucket
); i
++)
1721 SET_GC_MARK(PTR_BUCKET(c
, &c
->uuid_bucket
, i
),
1724 /* don't reclaim buckets to which writeback keys point */
1726 for (i
= 0; i
< c
->devices_max_used
; i
++) {
1727 struct bcache_device
*d
= c
->devices
[i
];
1728 struct cached_dev
*dc
;
1729 struct keybuf_key
*w
, *n
;
1732 if (!d
|| UUID_FLASH_ONLY(&c
->uuids
[i
]))
1734 dc
= container_of(d
, struct cached_dev
, disk
);
1736 spin_lock(&dc
->writeback_keys
.lock
);
1737 rbtree_postorder_for_each_entry_safe(w
, n
,
1738 &dc
->writeback_keys
.keys
, node
)
1739 for (j
= 0; j
< KEY_PTRS(&w
->key
); j
++)
1740 SET_GC_MARK(PTR_BUCKET(c
, &w
->key
, j
),
1742 spin_unlock(&dc
->writeback_keys
.lock
);
1746 c
->avail_nbuckets
= 0;
1747 for_each_cache(ca
, c
, i
) {
1750 ca
->invalidate_needs_gc
= 0;
1752 for (i
= ca
->sb
.d
; i
< ca
->sb
.d
+ ca
->sb
.keys
; i
++)
1753 SET_GC_MARK(ca
->buckets
+ *i
, GC_MARK_METADATA
);
1755 for (i
= ca
->prio_buckets
;
1756 i
< ca
->prio_buckets
+ prio_buckets(ca
) * 2; i
++)
1757 SET_GC_MARK(ca
->buckets
+ *i
, GC_MARK_METADATA
);
1759 for_each_bucket(b
, ca
) {
1760 c
->need_gc
= max(c
->need_gc
, bucket_gc_gen(b
));
1762 if (atomic_read(&b
->pin
))
1765 BUG_ON(!GC_MARK(b
) && GC_SECTORS_USED(b
));
1767 if (!GC_MARK(b
) || GC_MARK(b
) == GC_MARK_RECLAIMABLE
)
1768 c
->avail_nbuckets
++;
1772 mutex_unlock(&c
->bucket_lock
);
1775 static void bch_btree_gc(struct cache_set
*c
)
1778 struct gc_stat stats
;
1779 struct closure writes
;
1781 uint64_t start_time
= local_clock();
1783 trace_bcache_gc_start(c
);
1785 memset(&stats
, 0, sizeof(struct gc_stat
));
1786 closure_init_stack(&writes
);
1787 bch_btree_op_init(&op
, SHRT_MAX
);
1791 /* if CACHE_SET_IO_DISABLE set, gc thread should stop too */
1793 ret
= bcache_btree_root(gc_root
, c
, &op
, &writes
, &stats
);
1794 closure_sync(&writes
);
1798 schedule_timeout_interruptible(msecs_to_jiffies
1801 pr_warn("gc failed!");
1802 } while (ret
&& !test_bit(CACHE_SET_IO_DISABLE
, &c
->flags
));
1804 bch_btree_gc_finish(c
);
1805 wake_up_allocators(c
);
1807 bch_time_stats_update(&c
->btree_gc_time
, start_time
);
1809 stats
.key_bytes
*= sizeof(uint64_t);
1811 bch_update_bucket_in_use(c
, &stats
);
1812 memcpy(&c
->gc_stats
, &stats
, sizeof(struct gc_stat
));
1814 trace_bcache_gc_end(c
);
1819 static bool gc_should_run(struct cache_set
*c
)
1824 for_each_cache(ca
, c
, i
)
1825 if (ca
->invalidate_needs_gc
)
1828 if (atomic_read(&c
->sectors_to_gc
) < 0)
1834 static int bch_gc_thread(void *arg
)
1836 struct cache_set
*c
= arg
;
1839 wait_event_interruptible(c
->gc_wait
,
1840 kthread_should_stop() ||
1841 test_bit(CACHE_SET_IO_DISABLE
, &c
->flags
) ||
1844 if (kthread_should_stop() ||
1845 test_bit(CACHE_SET_IO_DISABLE
, &c
->flags
))
1852 wait_for_kthread_stop();
1856 int bch_gc_thread_start(struct cache_set
*c
)
1858 c
->gc_thread
= kthread_run(bch_gc_thread
, c
, "bcache_gc");
1859 return PTR_ERR_OR_ZERO(c
->gc_thread
);
1862 /* Initial partial gc */
1864 static int bch_btree_check_recurse(struct btree
*b
, struct btree_op
*op
)
1867 struct bkey
*k
, *p
= NULL
;
1868 struct btree_iter iter
;
1870 for_each_key_filter(&b
->keys
, k
, &iter
, bch_ptr_invalid
)
1871 bch_initial_mark_key(b
->c
, b
->level
, k
);
1873 bch_initial_mark_key(b
->c
, b
->level
+ 1, &b
->key
);
1876 bch_btree_iter_init(&b
->keys
, &iter
, NULL
);
1879 k
= bch_btree_iter_next_filter(&iter
, &b
->keys
,
1882 btree_node_prefetch(b
, k
);
1884 * initiallize c->gc_stats.nodes
1885 * for incremental GC
1887 b
->c
->gc_stats
.nodes
++;
1891 ret
= bcache_btree(check_recurse
, p
, b
, op
);
1894 } while (p
&& !ret
);
1901 static int bch_btree_check_thread(void *arg
)
1904 struct btree_check_info
*info
= arg
;
1905 struct btree_check_state
*check_state
= info
->state
;
1906 struct cache_set
*c
= check_state
->c
;
1907 struct btree_iter iter
;
1909 int cur_idx
, prev_idx
, skip_nr
;
1914 cur_idx
= prev_idx
= 0;
1917 /* root node keys are checked before thread created */
1918 bch_btree_iter_init(&c
->root
->keys
, &iter
, NULL
);
1919 k
= bch_btree_iter_next_filter(&iter
, &c
->root
->keys
, bch_ptr_bad
);
1925 * Fetch a root node key index, skip the keys which
1926 * should be fetched by other threads, then check the
1927 * sub-tree indexed by the fetched key.
1929 spin_lock(&check_state
->idx_lock
);
1930 cur_idx
= check_state
->key_idx
;
1931 check_state
->key_idx
++;
1932 spin_unlock(&check_state
->idx_lock
);
1934 skip_nr
= cur_idx
- prev_idx
;
1937 k
= bch_btree_iter_next_filter(&iter
,
1944 * No more keys to check in root node,
1945 * current checking threads are enough,
1946 * stop creating more.
1948 atomic_set(&check_state
->enough
, 1);
1949 /* Update check_state->enough earlier */
1950 smp_mb__after_atomic();
1960 btree_node_prefetch(c
->root
, p
);
1961 c
->gc_stats
.nodes
++;
1962 bch_btree_op_init(&op
, 0);
1963 ret
= bcache_btree(check_recurse
, p
, c
->root
, &op
);
1974 /* update check_state->started among all CPUs */
1975 smp_mb__before_atomic();
1976 if (atomic_dec_and_test(&check_state
->started
))
1977 wake_up(&check_state
->wait
);
1984 static int bch_btree_chkthread_nr(void)
1986 int n
= num_online_cpus()/2;
1990 else if (n
> BCH_BTR_CHKTHREAD_MAX
)
1991 n
= BCH_BTR_CHKTHREAD_MAX
;
1996 int bch_btree_check(struct cache_set
*c
)
2000 struct bkey
*k
= NULL
;
2001 struct btree_iter iter
;
2002 struct btree_check_state
*check_state
;
2005 /* check and mark root node keys */
2006 for_each_key_filter(&c
->root
->keys
, k
, &iter
, bch_ptr_invalid
)
2007 bch_initial_mark_key(c
, c
->root
->level
, k
);
2009 bch_initial_mark_key(c
, c
->root
->level
+ 1, &c
->root
->key
);
2011 if (c
->root
->level
== 0)
2014 check_state
= kzalloc(sizeof(struct btree_check_state
), GFP_KERNEL
);
2019 check_state
->total_threads
= bch_btree_chkthread_nr();
2020 check_state
->key_idx
= 0;
2021 spin_lock_init(&check_state
->idx_lock
);
2022 atomic_set(&check_state
->started
, 0);
2023 atomic_set(&check_state
->enough
, 0);
2024 init_waitqueue_head(&check_state
->wait
);
2027 * Run multiple threads to check btree nodes in parallel,
2028 * if check_state->enough is non-zero, it means current
2029 * running check threads are enough, unncessary to create
2032 for (i
= 0; i
< check_state
->total_threads
; i
++) {
2033 /* fetch latest check_state->enough earlier */
2034 smp_mb__before_atomic();
2035 if (atomic_read(&check_state
->enough
))
2038 check_state
->infos
[i
].result
= 0;
2039 check_state
->infos
[i
].state
= check_state
;
2040 snprintf(name
, sizeof(name
), "bch_btrchk[%u]", i
);
2041 atomic_inc(&check_state
->started
);
2043 check_state
->infos
[i
].thread
=
2044 kthread_run(bch_btree_check_thread
,
2045 &check_state
->infos
[i
],
2047 if (IS_ERR(check_state
->infos
[i
].thread
)) {
2048 pr_err("fails to run thread bch_btrchk[%d]", i
);
2049 for (--i
; i
>= 0; i
--)
2050 kthread_stop(check_state
->infos
[i
].thread
);
2056 wait_event_interruptible(check_state
->wait
,
2057 atomic_read(&check_state
->started
) == 0 ||
2058 test_bit(CACHE_SET_IO_DISABLE
, &c
->flags
));
2060 for (i
= 0; i
< check_state
->total_threads
; i
++) {
2061 if (check_state
->infos
[i
].result
) {
2062 ret
= check_state
->infos
[i
].result
;
2072 void bch_initial_gc_finish(struct cache_set
*c
)
2078 bch_btree_gc_finish(c
);
2080 mutex_lock(&c
->bucket_lock
);
2083 * We need to put some unused buckets directly on the prio freelist in
2084 * order to get the allocator thread started - it needs freed buckets in
2085 * order to rewrite the prios and gens, and it needs to rewrite prios
2086 * and gens in order to free buckets.
2088 * This is only safe for buckets that have no live data in them, which
2089 * there should always be some of.
2091 for_each_cache(ca
, c
, i
) {
2092 for_each_bucket(b
, ca
) {
2093 if (fifo_full(&ca
->free
[RESERVE_PRIO
]) &&
2094 fifo_full(&ca
->free
[RESERVE_BTREE
]))
2097 if (bch_can_invalidate_bucket(ca
, b
) &&
2099 __bch_invalidate_one_bucket(ca
, b
);
2100 if (!fifo_push(&ca
->free
[RESERVE_PRIO
],
2102 fifo_push(&ca
->free
[RESERVE_BTREE
],
2108 mutex_unlock(&c
->bucket_lock
);
2111 /* Btree insertion */
2113 static bool btree_insert_key(struct btree
*b
, struct bkey
*k
,
2114 struct bkey
*replace_key
)
2116 unsigned int status
;
2118 BUG_ON(bkey_cmp(k
, &b
->key
) > 0);
2120 status
= bch_btree_insert_key(&b
->keys
, k
, replace_key
);
2121 if (status
!= BTREE_INSERT_STATUS_NO_INSERT
) {
2122 bch_check_keys(&b
->keys
, "%u for %s", status
,
2123 replace_key
? "replace" : "insert");
2125 trace_bcache_btree_insert_key(b
, k
, replace_key
!= NULL
,
2132 static size_t insert_u64s_remaining(struct btree
*b
)
2134 long ret
= bch_btree_keys_u64s_remaining(&b
->keys
);
2137 * Might land in the middle of an existing extent and have to split it
2139 if (b
->keys
.ops
->is_extents
)
2140 ret
-= KEY_MAX_U64S
;
2142 return max(ret
, 0L);
2145 static bool bch_btree_insert_keys(struct btree
*b
, struct btree_op
*op
,
2146 struct keylist
*insert_keys
,
2147 struct bkey
*replace_key
)
2150 int oldsize
= bch_count_data(&b
->keys
);
2152 while (!bch_keylist_empty(insert_keys
)) {
2153 struct bkey
*k
= insert_keys
->keys
;
2155 if (bkey_u64s(k
) > insert_u64s_remaining(b
))
2158 if (bkey_cmp(k
, &b
->key
) <= 0) {
2162 ret
|= btree_insert_key(b
, k
, replace_key
);
2163 bch_keylist_pop_front(insert_keys
);
2164 } else if (bkey_cmp(&START_KEY(k
), &b
->key
) < 0) {
2165 BKEY_PADDED(key
) temp
;
2166 bkey_copy(&temp
.key
, insert_keys
->keys
);
2168 bch_cut_back(&b
->key
, &temp
.key
);
2169 bch_cut_front(&b
->key
, insert_keys
->keys
);
2171 ret
|= btree_insert_key(b
, &temp
.key
, replace_key
);
2179 op
->insert_collision
= true;
2181 BUG_ON(!bch_keylist_empty(insert_keys
) && b
->level
);
2183 BUG_ON(bch_count_data(&b
->keys
) < oldsize
);
2187 static int btree_split(struct btree
*b
, struct btree_op
*op
,
2188 struct keylist
*insert_keys
,
2189 struct bkey
*replace_key
)
2192 struct btree
*n1
, *n2
= NULL
, *n3
= NULL
;
2193 uint64_t start_time
= local_clock();
2195 struct keylist parent_keys
;
2197 closure_init_stack(&cl
);
2198 bch_keylist_init(&parent_keys
);
2200 if (btree_check_reserve(b
, op
)) {
2204 WARN(1, "insufficient reserve for split\n");
2207 n1
= btree_node_alloc_replacement(b
, op
);
2211 split
= set_blocks(btree_bset_first(n1
),
2212 block_bytes(n1
->c
)) > (btree_blocks(b
) * 4) / 5;
2215 unsigned int keys
= 0;
2217 trace_bcache_btree_node_split(b
, btree_bset_first(n1
)->keys
);
2219 n2
= bch_btree_node_alloc(b
->c
, op
, b
->level
, b
->parent
);
2224 n3
= bch_btree_node_alloc(b
->c
, op
, b
->level
+ 1, NULL
);
2229 mutex_lock(&n1
->write_lock
);
2230 mutex_lock(&n2
->write_lock
);
2232 bch_btree_insert_keys(n1
, op
, insert_keys
, replace_key
);
2235 * Has to be a linear search because we don't have an auxiliary
2239 while (keys
< (btree_bset_first(n1
)->keys
* 3) / 5)
2240 keys
+= bkey_u64s(bset_bkey_idx(btree_bset_first(n1
),
2243 bkey_copy_key(&n1
->key
,
2244 bset_bkey_idx(btree_bset_first(n1
), keys
));
2245 keys
+= bkey_u64s(bset_bkey_idx(btree_bset_first(n1
), keys
));
2247 btree_bset_first(n2
)->keys
= btree_bset_first(n1
)->keys
- keys
;
2248 btree_bset_first(n1
)->keys
= keys
;
2250 memcpy(btree_bset_first(n2
)->start
,
2251 bset_bkey_last(btree_bset_first(n1
)),
2252 btree_bset_first(n2
)->keys
* sizeof(uint64_t));
2254 bkey_copy_key(&n2
->key
, &b
->key
);
2256 bch_keylist_add(&parent_keys
, &n2
->key
);
2257 bch_btree_node_write(n2
, &cl
);
2258 mutex_unlock(&n2
->write_lock
);
2259 rw_unlock(true, n2
);
2261 trace_bcache_btree_node_compact(b
, btree_bset_first(n1
)->keys
);
2263 mutex_lock(&n1
->write_lock
);
2264 bch_btree_insert_keys(n1
, op
, insert_keys
, replace_key
);
2267 bch_keylist_add(&parent_keys
, &n1
->key
);
2268 bch_btree_node_write(n1
, &cl
);
2269 mutex_unlock(&n1
->write_lock
);
2272 /* Depth increases, make a new root */
2273 mutex_lock(&n3
->write_lock
);
2274 bkey_copy_key(&n3
->key
, &MAX_KEY
);
2275 bch_btree_insert_keys(n3
, op
, &parent_keys
, NULL
);
2276 bch_btree_node_write(n3
, &cl
);
2277 mutex_unlock(&n3
->write_lock
);
2280 bch_btree_set_root(n3
);
2281 rw_unlock(true, n3
);
2282 } else if (!b
->parent
) {
2283 /* Root filled up but didn't need to be split */
2285 bch_btree_set_root(n1
);
2287 /* Split a non root node */
2289 make_btree_freeing_key(b
, parent_keys
.top
);
2290 bch_keylist_push(&parent_keys
);
2292 bch_btree_insert_node(b
->parent
, op
, &parent_keys
, NULL
, NULL
);
2293 BUG_ON(!bch_keylist_empty(&parent_keys
));
2297 rw_unlock(true, n1
);
2299 bch_time_stats_update(&b
->c
->btree_split_time
, start_time
);
2303 bkey_put(b
->c
, &n2
->key
);
2304 btree_node_free(n2
);
2305 rw_unlock(true, n2
);
2307 bkey_put(b
->c
, &n1
->key
);
2308 btree_node_free(n1
);
2309 rw_unlock(true, n1
);
2311 WARN(1, "bcache: btree split failed (level %u)", b
->level
);
2313 if (n3
== ERR_PTR(-EAGAIN
) ||
2314 n2
== ERR_PTR(-EAGAIN
) ||
2315 n1
== ERR_PTR(-EAGAIN
))
2321 static int bch_btree_insert_node(struct btree
*b
, struct btree_op
*op
,
2322 struct keylist
*insert_keys
,
2323 atomic_t
*journal_ref
,
2324 struct bkey
*replace_key
)
2328 BUG_ON(b
->level
&& replace_key
);
2330 closure_init_stack(&cl
);
2332 mutex_lock(&b
->write_lock
);
2334 if (write_block(b
) != btree_bset_last(b
) &&
2335 b
->keys
.last_set_unwritten
)
2336 bch_btree_init_next(b
); /* just wrote a set */
2338 if (bch_keylist_nkeys(insert_keys
) > insert_u64s_remaining(b
)) {
2339 mutex_unlock(&b
->write_lock
);
2343 BUG_ON(write_block(b
) != btree_bset_last(b
));
2345 if (bch_btree_insert_keys(b
, op
, insert_keys
, replace_key
)) {
2347 bch_btree_leaf_dirty(b
, journal_ref
);
2349 bch_btree_node_write(b
, &cl
);
2352 mutex_unlock(&b
->write_lock
);
2354 /* wait for btree node write if necessary, after unlock */
2359 if (current
->bio_list
) {
2360 op
->lock
= b
->c
->root
->level
+ 1;
2362 } else if (op
->lock
<= b
->c
->root
->level
) {
2363 op
->lock
= b
->c
->root
->level
+ 1;
2366 /* Invalidated all iterators */
2367 int ret
= btree_split(b
, op
, insert_keys
, replace_key
);
2369 if (bch_keylist_empty(insert_keys
))
2377 int bch_btree_insert_check_key(struct btree
*b
, struct btree_op
*op
,
2378 struct bkey
*check_key
)
2381 uint64_t btree_ptr
= b
->key
.ptr
[0];
2382 unsigned long seq
= b
->seq
;
2383 struct keylist insert
;
2384 bool upgrade
= op
->lock
== -1;
2386 bch_keylist_init(&insert
);
2389 rw_unlock(false, b
);
2390 rw_lock(true, b
, b
->level
);
2392 if (b
->key
.ptr
[0] != btree_ptr
||
2393 b
->seq
!= seq
+ 1) {
2394 op
->lock
= b
->level
;
2399 SET_KEY_PTRS(check_key
, 1);
2400 get_random_bytes(&check_key
->ptr
[0], sizeof(uint64_t));
2402 SET_PTR_DEV(check_key
, 0, PTR_CHECK_DEV
);
2404 bch_keylist_add(&insert
, check_key
);
2406 ret
= bch_btree_insert_node(b
, op
, &insert
, NULL
, NULL
);
2408 BUG_ON(!ret
&& !bch_keylist_empty(&insert
));
2411 downgrade_write(&b
->lock
);
2415 struct btree_insert_op
{
2417 struct keylist
*keys
;
2418 atomic_t
*journal_ref
;
2419 struct bkey
*replace_key
;
2422 static int btree_insert_fn(struct btree_op
*b_op
, struct btree
*b
)
2424 struct btree_insert_op
*op
= container_of(b_op
,
2425 struct btree_insert_op
, op
);
2427 int ret
= bch_btree_insert_node(b
, &op
->op
, op
->keys
,
2428 op
->journal_ref
, op
->replace_key
);
2429 if (ret
&& !bch_keylist_empty(op
->keys
))
2435 int bch_btree_insert(struct cache_set
*c
, struct keylist
*keys
,
2436 atomic_t
*journal_ref
, struct bkey
*replace_key
)
2438 struct btree_insert_op op
;
2441 BUG_ON(current
->bio_list
);
2442 BUG_ON(bch_keylist_empty(keys
));
2444 bch_btree_op_init(&op
.op
, 0);
2446 op
.journal_ref
= journal_ref
;
2447 op
.replace_key
= replace_key
;
2449 while (!ret
&& !bch_keylist_empty(keys
)) {
2451 ret
= bch_btree_map_leaf_nodes(&op
.op
, c
,
2452 &START_KEY(keys
->keys
),
2459 pr_err("error %i", ret
);
2461 while ((k
= bch_keylist_pop(keys
)))
2463 } else if (op
.op
.insert_collision
)
2469 void bch_btree_set_root(struct btree
*b
)
2474 closure_init_stack(&cl
);
2476 trace_bcache_btree_set_root(b
);
2478 BUG_ON(!b
->written
);
2480 for (i
= 0; i
< KEY_PTRS(&b
->key
); i
++)
2481 BUG_ON(PTR_BUCKET(b
->c
, &b
->key
, i
)->prio
!= BTREE_PRIO
);
2483 mutex_lock(&b
->c
->bucket_lock
);
2484 list_del_init(&b
->list
);
2485 mutex_unlock(&b
->c
->bucket_lock
);
2489 bch_journal_meta(b
->c
, &cl
);
2493 /* Map across nodes or keys */
2495 static int bch_btree_map_nodes_recurse(struct btree
*b
, struct btree_op
*op
,
2497 btree_map_nodes_fn
*fn
, int flags
)
2499 int ret
= MAP_CONTINUE
;
2503 struct btree_iter iter
;
2505 bch_btree_iter_init(&b
->keys
, &iter
, from
);
2507 while ((k
= bch_btree_iter_next_filter(&iter
, &b
->keys
,
2509 ret
= bcache_btree(map_nodes_recurse
, k
, b
,
2510 op
, from
, fn
, flags
);
2513 if (ret
!= MAP_CONTINUE
)
2518 if (!b
->level
|| flags
== MAP_ALL_NODES
)
2524 int __bch_btree_map_nodes(struct btree_op
*op
, struct cache_set
*c
,
2525 struct bkey
*from
, btree_map_nodes_fn
*fn
, int flags
)
2527 return bcache_btree_root(map_nodes_recurse
, c
, op
, from
, fn
, flags
);
2530 int bch_btree_map_keys_recurse(struct btree
*b
, struct btree_op
*op
,
2531 struct bkey
*from
, btree_map_keys_fn
*fn
,
2534 int ret
= MAP_CONTINUE
;
2536 struct btree_iter iter
;
2538 bch_btree_iter_init(&b
->keys
, &iter
, from
);
2540 while ((k
= bch_btree_iter_next_filter(&iter
, &b
->keys
, bch_ptr_bad
))) {
2543 : bcache_btree(map_keys_recurse
, k
,
2544 b
, op
, from
, fn
, flags
);
2547 if (ret
!= MAP_CONTINUE
)
2551 if (!b
->level
&& (flags
& MAP_END_KEY
))
2552 ret
= fn(op
, b
, &KEY(KEY_INODE(&b
->key
),
2553 KEY_OFFSET(&b
->key
), 0));
2558 int bch_btree_map_keys(struct btree_op
*op
, struct cache_set
*c
,
2559 struct bkey
*from
, btree_map_keys_fn
*fn
, int flags
)
2561 return bcache_btree_root(map_keys_recurse
, c
, op
, from
, fn
, flags
);
2566 static inline int keybuf_cmp(struct keybuf_key
*l
, struct keybuf_key
*r
)
2568 /* Overlapping keys compare equal */
2569 if (bkey_cmp(&l
->key
, &START_KEY(&r
->key
)) <= 0)
2571 if (bkey_cmp(&START_KEY(&l
->key
), &r
->key
) >= 0)
2576 static inline int keybuf_nonoverlapping_cmp(struct keybuf_key
*l
,
2577 struct keybuf_key
*r
)
2579 return clamp_t(int64_t, bkey_cmp(&l
->key
, &r
->key
), -1, 1);
2584 unsigned int nr_found
;
2587 keybuf_pred_fn
*pred
;
2590 static int refill_keybuf_fn(struct btree_op
*op
, struct btree
*b
,
2593 struct refill
*refill
= container_of(op
, struct refill
, op
);
2594 struct keybuf
*buf
= refill
->buf
;
2595 int ret
= MAP_CONTINUE
;
2597 if (bkey_cmp(k
, refill
->end
) > 0) {
2602 if (!KEY_SIZE(k
)) /* end key */
2605 if (refill
->pred(buf
, k
)) {
2606 struct keybuf_key
*w
;
2608 spin_lock(&buf
->lock
);
2610 w
= array_alloc(&buf
->freelist
);
2612 spin_unlock(&buf
->lock
);
2617 bkey_copy(&w
->key
, k
);
2619 if (RB_INSERT(&buf
->keys
, w
, node
, keybuf_cmp
))
2620 array_free(&buf
->freelist
, w
);
2624 if (array_freelist_empty(&buf
->freelist
))
2627 spin_unlock(&buf
->lock
);
2630 buf
->last_scanned
= *k
;
2634 void bch_refill_keybuf(struct cache_set
*c
, struct keybuf
*buf
,
2635 struct bkey
*end
, keybuf_pred_fn
*pred
)
2637 struct bkey start
= buf
->last_scanned
;
2638 struct refill refill
;
2642 bch_btree_op_init(&refill
.op
, -1);
2643 refill
.nr_found
= 0;
2648 bch_btree_map_keys(&refill
.op
, c
, &buf
->last_scanned
,
2649 refill_keybuf_fn
, MAP_END_KEY
);
2651 trace_bcache_keyscan(refill
.nr_found
,
2652 KEY_INODE(&start
), KEY_OFFSET(&start
),
2653 KEY_INODE(&buf
->last_scanned
),
2654 KEY_OFFSET(&buf
->last_scanned
));
2656 spin_lock(&buf
->lock
);
2658 if (!RB_EMPTY_ROOT(&buf
->keys
)) {
2659 struct keybuf_key
*w
;
2661 w
= RB_FIRST(&buf
->keys
, struct keybuf_key
, node
);
2662 buf
->start
= START_KEY(&w
->key
);
2664 w
= RB_LAST(&buf
->keys
, struct keybuf_key
, node
);
2667 buf
->start
= MAX_KEY
;
2671 spin_unlock(&buf
->lock
);
2674 static void __bch_keybuf_del(struct keybuf
*buf
, struct keybuf_key
*w
)
2676 rb_erase(&w
->node
, &buf
->keys
);
2677 array_free(&buf
->freelist
, w
);
2680 void bch_keybuf_del(struct keybuf
*buf
, struct keybuf_key
*w
)
2682 spin_lock(&buf
->lock
);
2683 __bch_keybuf_del(buf
, w
);
2684 spin_unlock(&buf
->lock
);
2687 bool bch_keybuf_check_overlapping(struct keybuf
*buf
, struct bkey
*start
,
2691 struct keybuf_key
*p
, *w
, s
;
2695 if (bkey_cmp(end
, &buf
->start
) <= 0 ||
2696 bkey_cmp(start
, &buf
->end
) >= 0)
2699 spin_lock(&buf
->lock
);
2700 w
= RB_GREATER(&buf
->keys
, s
, node
, keybuf_nonoverlapping_cmp
);
2702 while (w
&& bkey_cmp(&START_KEY(&w
->key
), end
) < 0) {
2704 w
= RB_NEXT(w
, node
);
2709 __bch_keybuf_del(buf
, p
);
2712 spin_unlock(&buf
->lock
);
2716 struct keybuf_key
*bch_keybuf_next(struct keybuf
*buf
)
2718 struct keybuf_key
*w
;
2720 spin_lock(&buf
->lock
);
2722 w
= RB_FIRST(&buf
->keys
, struct keybuf_key
, node
);
2724 while (w
&& w
->private)
2725 w
= RB_NEXT(w
, node
);
2728 w
->private = ERR_PTR(-EINTR
);
2730 spin_unlock(&buf
->lock
);
2734 struct keybuf_key
*bch_keybuf_next_rescan(struct cache_set
*c
,
2737 keybuf_pred_fn
*pred
)
2739 struct keybuf_key
*ret
;
2742 ret
= bch_keybuf_next(buf
);
2746 if (bkey_cmp(&buf
->last_scanned
, end
) >= 0) {
2747 pr_debug("scan finished");
2751 bch_refill_keybuf(c
, buf
, end
, pred
);
2757 void bch_keybuf_init(struct keybuf
*buf
)
2759 buf
->last_scanned
= MAX_KEY
;
2760 buf
->keys
= RB_ROOT
;
2762 spin_lock_init(&buf
->lock
);
2763 array_allocator_init(&buf
->freelist
);