2 * Primary bucket allocation code
4 * Copyright 2012 Google, Inc.
6 * Allocation in bcache is done in terms of buckets:
8 * Each bucket has associated an 8 bit gen; this gen corresponds to the gen in
9 * btree pointers - they must match for the pointer to be considered valid.
11 * Thus (assuming a bucket has no dirty data or metadata in it) we can reuse a
12 * bucket simply by incrementing its gen.
14 * The gens (along with the priorities; it's really the gens are important but
15 * the code is named as if it's the priorities) are written in an arbitrary list
16 * of buckets on disk, with a pointer to them in the journal header.
18 * When we invalidate a bucket, we have to write its new gen to disk and wait
19 * for that write to complete before we use it - otherwise after a crash we
20 * could have pointers that appeared to be good but pointed to data that had
23 * Since the gens and priorities are all stored contiguously on disk, we can
24 * batch this up: We fill up the free_inc list with freshly invalidated buckets,
25 * call prio_write(), and when prio_write() finishes we pull buckets off the
26 * free_inc list and optionally discard them.
28 * free_inc isn't the only freelist - if it was, we'd often to sleep while
29 * priorities and gens were being written before we could allocate. c->free is a
30 * smaller freelist, and buckets on that list are always ready to be used.
32 * If we've got discards enabled, that happens when a bucket moves from the
33 * free_inc list to the free list.
35 * There is another freelist, because sometimes we have buckets that we know
36 * have nothing pointing into them - these we can reuse without waiting for
37 * priorities to be rewritten. These come from freed btree nodes and buckets
38 * that garbage collection discovered no longer had valid keys pointing into
39 * them (because they were overwritten). That's the unused list - buckets on the
40 * unused list move to the free list, optionally being discarded in the process.
42 * It's also important to ensure that gens don't wrap around - with respect to
43 * either the oldest gen in the btree or the gen on disk. This is quite
44 * difficult to do in practice, but we explicitly guard against it anyways - if
45 * a bucket is in danger of wrapping around we simply skip invalidating it that
46 * time around, and we garbage collect or rewrite the priorities sooner than we
47 * would have otherwise.
49 * bch_bucket_alloc() allocates a single bucket from a specific cache.
51 * bch_bucket_alloc_set() allocates one or more buckets from different caches
54 * free_some_buckets() drives all the processes described above. It's called
55 * from bch_bucket_alloc() and a few other places that need to make sure free
58 * invalidate_buckets_(lru|fifo)() find buckets that are available to be
59 * invalidated, and then invalidate them and stick them on the free_inc list -
60 * in either lru or fifo order.
66 #include <linux/random.h>
68 #define MAX_IN_FLIGHT_DISCARDS 8U
70 /* Bucket heap / gen */
72 uint8_t bch_inc_gen(struct cache
*ca
, struct bucket
*b
)
74 uint8_t ret
= ++b
->gen
;
76 ca
->set
->need_gc
= max(ca
->set
->need_gc
, bucket_gc_gen(b
));
77 WARN_ON_ONCE(ca
->set
->need_gc
> BUCKET_GC_GEN_MAX
);
79 if (CACHE_SYNC(&ca
->set
->sb
)) {
80 ca
->need_save_prio
= max(ca
->need_save_prio
,
82 WARN_ON_ONCE(ca
->need_save_prio
> BUCKET_DISK_GEN_MAX
);
88 void bch_rescale_priorities(struct cache_set
*c
, int sectors
)
92 unsigned next
= c
->nbuckets
* c
->sb
.bucket_size
/ 1024;
96 atomic_sub(sectors
, &c
->rescale
);
99 r
= atomic_read(&c
->rescale
);
103 } while (atomic_cmpxchg(&c
->rescale
, r
, r
+ next
) != r
);
105 mutex_lock(&c
->bucket_lock
);
107 c
->min_prio
= USHRT_MAX
;
109 for_each_cache(ca
, c
, i
)
110 for_each_bucket(b
, ca
)
112 b
->prio
!= BTREE_PRIO
&&
113 !atomic_read(&b
->pin
)) {
115 c
->min_prio
= min(c
->min_prio
, b
->prio
);
118 mutex_unlock(&c
->bucket_lock
);
124 struct list_head list
;
125 struct work_struct work
;
133 static void discard_finish(struct work_struct
*w
)
135 struct discard
*d
= container_of(w
, struct discard
, work
);
136 struct cache
*ca
= d
->ca
;
137 char buf
[BDEVNAME_SIZE
];
139 if (!test_bit(BIO_UPTODATE
, &d
->bio
.bi_flags
)) {
140 pr_notice("discard error on %s, disabling",
141 bdevname(ca
->bdev
, buf
));
145 mutex_lock(&ca
->set
->bucket_lock
);
147 fifo_push(&ca
->free
, d
->bucket
);
148 list_add(&d
->list
, &ca
->discards
);
149 atomic_dec(&ca
->discards_in_flight
);
151 mutex_unlock(&ca
->set
->bucket_lock
);
153 closure_wake_up(&ca
->set
->bucket_wait
);
154 wake_up(&ca
->set
->alloc_wait
);
156 closure_put(&ca
->set
->cl
);
159 static void discard_endio(struct bio
*bio
, int error
)
161 struct discard
*d
= container_of(bio
, struct discard
, bio
);
162 schedule_work(&d
->work
);
165 static void do_discard(struct cache
*ca
, long bucket
)
167 struct discard
*d
= list_first_entry(&ca
->discards
,
168 struct discard
, list
);
173 atomic_inc(&ca
->discards_in_flight
);
174 closure_get(&ca
->set
->cl
);
178 d
->bio
.bi_sector
= bucket_to_sector(ca
->set
, d
->bucket
);
179 d
->bio
.bi_bdev
= ca
->bdev
;
180 d
->bio
.bi_rw
= REQ_WRITE
|REQ_DISCARD
;
181 d
->bio
.bi_max_vecs
= 1;
182 d
->bio
.bi_io_vec
= d
->bio
.bi_inline_vecs
;
183 d
->bio
.bi_size
= bucket_bytes(ca
);
184 d
->bio
.bi_end_io
= discard_endio
;
185 bio_set_prio(&d
->bio
, IOPRIO_PRIO_VALUE(IOPRIO_CLASS_IDLE
, 0));
187 submit_bio(0, &d
->bio
);
192 static inline bool can_inc_bucket_gen(struct bucket
*b
)
194 return bucket_gc_gen(b
) < BUCKET_GC_GEN_MAX
&&
195 bucket_disk_gen(b
) < BUCKET_DISK_GEN_MAX
;
198 bool bch_bucket_add_unused(struct cache
*ca
, struct bucket
*b
)
200 BUG_ON(GC_MARK(b
) || GC_SECTORS_USED(b
));
202 if (fifo_used(&ca
->free
) > ca
->watermark
[WATERMARK_MOVINGGC
] &&
203 CACHE_REPLACEMENT(&ca
->sb
) == CACHE_REPLACEMENT_FIFO
)
208 if (can_inc_bucket_gen(b
) &&
209 fifo_push(&ca
->unused
, b
- ca
->buckets
)) {
217 static bool can_invalidate_bucket(struct cache
*ca
, struct bucket
*b
)
219 return GC_MARK(b
) == GC_MARK_RECLAIMABLE
&&
220 !atomic_read(&b
->pin
) &&
221 can_inc_bucket_gen(b
);
224 static void invalidate_one_bucket(struct cache
*ca
, struct bucket
*b
)
227 b
->prio
= INITIAL_PRIO
;
229 fifo_push(&ca
->free_inc
, b
- ca
->buckets
);
232 #define bucket_prio(b) \
233 (((unsigned) (b->prio - ca->set->min_prio)) * GC_SECTORS_USED(b))
235 #define bucket_max_cmp(l, r) (bucket_prio(l) < bucket_prio(r))
236 #define bucket_min_cmp(l, r) (bucket_prio(l) > bucket_prio(r))
238 static void invalidate_buckets_lru(struct cache
*ca
)
245 for_each_bucket(b
, ca
) {
247 * If we fill up the unused list, if we then return before
248 * adding anything to the free_inc list we'll skip writing
249 * prios/gens and just go back to allocating from the unused
252 if (fifo_full(&ca
->unused
))
255 if (!can_invalidate_bucket(ca
, b
))
258 if (!GC_SECTORS_USED(b
) &&
259 bch_bucket_add_unused(ca
, b
))
262 if (!heap_full(&ca
->heap
))
263 heap_add(&ca
->heap
, b
, bucket_max_cmp
);
264 else if (bucket_max_cmp(b
, heap_peek(&ca
->heap
))) {
265 ca
->heap
.data
[0] = b
;
266 heap_sift(&ca
->heap
, 0, bucket_max_cmp
);
270 for (i
= ca
->heap
.used
/ 2 - 1; i
>= 0; --i
)
271 heap_sift(&ca
->heap
, i
, bucket_min_cmp
);
273 while (!fifo_full(&ca
->free_inc
)) {
274 if (!heap_pop(&ca
->heap
, b
, bucket_min_cmp
)) {
276 * We don't want to be calling invalidate_buckets()
277 * multiple times when it can't do anything
279 ca
->invalidate_needs_gc
= 1;
280 bch_queue_gc(ca
->set
);
284 invalidate_one_bucket(ca
, b
);
288 static void invalidate_buckets_fifo(struct cache
*ca
)
293 while (!fifo_full(&ca
->free_inc
)) {
294 if (ca
->fifo_last_bucket
< ca
->sb
.first_bucket
||
295 ca
->fifo_last_bucket
>= ca
->sb
.nbuckets
)
296 ca
->fifo_last_bucket
= ca
->sb
.first_bucket
;
298 b
= ca
->buckets
+ ca
->fifo_last_bucket
++;
300 if (can_invalidate_bucket(ca
, b
))
301 invalidate_one_bucket(ca
, b
);
303 if (++checked
>= ca
->sb
.nbuckets
) {
304 ca
->invalidate_needs_gc
= 1;
305 bch_queue_gc(ca
->set
);
311 static void invalidate_buckets_random(struct cache
*ca
)
316 while (!fifo_full(&ca
->free_inc
)) {
318 get_random_bytes(&n
, sizeof(n
));
320 n
%= (size_t) (ca
->sb
.nbuckets
- ca
->sb
.first_bucket
);
321 n
+= ca
->sb
.first_bucket
;
325 if (can_invalidate_bucket(ca
, b
))
326 invalidate_one_bucket(ca
, b
);
328 if (++checked
>= ca
->sb
.nbuckets
/ 2) {
329 ca
->invalidate_needs_gc
= 1;
330 bch_queue_gc(ca
->set
);
336 static void invalidate_buckets(struct cache
*ca
)
338 if (ca
->invalidate_needs_gc
)
341 switch (CACHE_REPLACEMENT(&ca
->sb
)) {
342 case CACHE_REPLACEMENT_LRU
:
343 invalidate_buckets_lru(ca
);
345 case CACHE_REPLACEMENT_FIFO
:
346 invalidate_buckets_fifo(ca
);
348 case CACHE_REPLACEMENT_RANDOM
:
349 invalidate_buckets_random(ca
);
353 pr_debug("free %zu/%zu free_inc %zu/%zu unused %zu/%zu",
354 fifo_used(&ca
->free
), ca
->free
.size
,
355 fifo_used(&ca
->free_inc
), ca
->free_inc
.size
,
356 fifo_used(&ca
->unused
), ca
->unused
.size
);
359 #define allocator_wait(ca, cond) \
361 DEFINE_WAIT(__wait); \
364 prepare_to_wait(&ca->set->alloc_wait, \
365 &__wait, TASK_INTERRUPTIBLE); \
369 mutex_unlock(&(ca)->set->bucket_lock); \
370 if (test_bit(CACHE_SET_STOPPING_2, &ca->set->flags)) { \
371 finish_wait(&ca->set->alloc_wait, &__wait); \
372 closure_return(cl); \
376 mutex_lock(&(ca)->set->bucket_lock); \
379 finish_wait(&ca->set->alloc_wait, &__wait); \
382 void bch_allocator_thread(struct closure
*cl
)
384 struct cache
*ca
= container_of(cl
, struct cache
, alloc
);
386 mutex_lock(&ca
->set
->bucket_lock
);
390 * First, we pull buckets off of the unused and free_inc lists,
391 * possibly issue discards to them, then we add the bucket to
397 if ((!atomic_read(&ca
->set
->prio_blocked
) ||
398 !CACHE_SYNC(&ca
->set
->sb
)) &&
399 !fifo_empty(&ca
->unused
))
400 fifo_pop(&ca
->unused
, bucket
);
401 else if (!fifo_empty(&ca
->free_inc
))
402 fifo_pop(&ca
->free_inc
, bucket
);
406 allocator_wait(ca
, (int) fifo_free(&ca
->free
) >
407 atomic_read(&ca
->discards_in_flight
));
410 allocator_wait(ca
, !list_empty(&ca
->discards
));
411 do_discard(ca
, bucket
);
413 fifo_push(&ca
->free
, bucket
);
414 closure_wake_up(&ca
->set
->bucket_wait
);
419 * We've run out of free buckets, we need to find some buckets
420 * we can invalidate. First, invalidate them in memory and add
421 * them to the free_inc list:
424 allocator_wait(ca
, ca
->set
->gc_mark_valid
&&
425 (ca
->need_save_prio
> 64 ||
426 !ca
->invalidate_needs_gc
));
427 invalidate_buckets(ca
);
430 * Now, we write their new gens to disk so we can start writing
433 allocator_wait(ca
, !atomic_read(&ca
->set
->prio_blocked
));
434 if (CACHE_SYNC(&ca
->set
->sb
) &&
435 (!fifo_empty(&ca
->free_inc
) ||
436 ca
->need_save_prio
> 64))
441 long bch_bucket_alloc(struct cache
*ca
, unsigned watermark
, struct closure
*cl
)
445 wake_up(&ca
->set
->alloc_wait
);
447 if (fifo_used(&ca
->free
) > ca
->watermark
[watermark
] &&
448 fifo_pop(&ca
->free
, r
)) {
449 struct bucket
*b
= ca
->buckets
+ r
;
450 #ifdef CONFIG_BCACHE_EDEBUG
454 for (iter
= 0; iter
< prio_buckets(ca
) * 2; iter
++)
455 BUG_ON(ca
->prio_buckets
[iter
] == (uint64_t) r
);
457 fifo_for_each(i
, &ca
->free
, iter
)
459 fifo_for_each(i
, &ca
->free_inc
, iter
)
461 fifo_for_each(i
, &ca
->unused
, iter
)
464 BUG_ON(atomic_read(&b
->pin
) != 1);
466 SET_GC_SECTORS_USED(b
, ca
->sb
.bucket_size
);
468 if (watermark
<= WATERMARK_METADATA
) {
469 SET_GC_MARK(b
, GC_MARK_METADATA
);
470 b
->prio
= BTREE_PRIO
;
472 SET_GC_MARK(b
, GC_MARK_RECLAIMABLE
);
473 b
->prio
= INITIAL_PRIO
;
479 pr_debug("alloc failure: blocked %i free %zu free_inc %zu unused %zu",
480 atomic_read(&ca
->set
->prio_blocked
), fifo_used(&ca
->free
),
481 fifo_used(&ca
->free_inc
), fifo_used(&ca
->unused
));
484 closure_wait(&ca
->set
->bucket_wait
, cl
);
486 if (closure_blocking(cl
)) {
487 mutex_unlock(&ca
->set
->bucket_lock
);
489 mutex_lock(&ca
->set
->bucket_lock
);
497 void bch_bucket_free(struct cache_set
*c
, struct bkey
*k
)
501 for (i
= 0; i
< KEY_PTRS(k
); i
++) {
502 struct bucket
*b
= PTR_BUCKET(c
, k
, i
);
504 SET_GC_MARK(b
, GC_MARK_RECLAIMABLE
);
505 SET_GC_SECTORS_USED(b
, 0);
506 bch_bucket_add_unused(PTR_CACHE(c
, k
, i
), b
);
510 int __bch_bucket_alloc_set(struct cache_set
*c
, unsigned watermark
,
511 struct bkey
*k
, int n
, struct closure
*cl
)
515 lockdep_assert_held(&c
->bucket_lock
);
516 BUG_ON(!n
|| n
> c
->caches_loaded
|| n
> 8);
520 /* sort by free space/prio of oldest data in caches */
522 for (i
= 0; i
< n
; i
++) {
523 struct cache
*ca
= c
->cache_by_alloc
[i
];
524 long b
= bch_bucket_alloc(ca
, watermark
, cl
);
529 k
->ptr
[i
] = PTR(ca
->buckets
[b
].gen
,
530 bucket_to_sector(c
, b
),
533 SET_KEY_PTRS(k
, i
+ 1);
538 bch_bucket_free(c
, k
);
543 int bch_bucket_alloc_set(struct cache_set
*c
, unsigned watermark
,
544 struct bkey
*k
, int n
, struct closure
*cl
)
547 mutex_lock(&c
->bucket_lock
);
548 ret
= __bch_bucket_alloc_set(c
, watermark
, k
, n
, cl
);
549 mutex_unlock(&c
->bucket_lock
);
555 void bch_cache_allocator_exit(struct cache
*ca
)
559 while (!list_empty(&ca
->discards
)) {
560 d
= list_first_entry(&ca
->discards
, struct discard
, list
);
561 cancel_work_sync(&d
->work
);
567 int bch_cache_allocator_init(struct cache
*ca
)
573 * Prio/gen writes first
574 * Then 8 for btree allocations
575 * Then half for the moving garbage collector
578 ca
->watermark
[WATERMARK_PRIO
] = 0;
580 ca
->watermark
[WATERMARK_METADATA
] = prio_buckets(ca
);
582 ca
->watermark
[WATERMARK_MOVINGGC
] = 8 +
583 ca
->watermark
[WATERMARK_METADATA
];
585 ca
->watermark
[WATERMARK_NONE
] = ca
->free
.size
/ 2 +
586 ca
->watermark
[WATERMARK_MOVINGGC
];
588 for (i
= 0; i
< MAX_IN_FLIGHT_DISCARDS
; i
++) {
589 struct discard
*d
= kzalloc(sizeof(*d
), GFP_KERNEL
);
594 INIT_WORK(&d
->work
, discard_finish
);
595 list_add(&d
->list
, &ca
->discards
);
This page took 0.045142 seconds and 5 git commands to generate.