1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#include "bcache.h"
65#include "btree.h"
66
67#include <linux/blkdev.h>
68#include <linux/kthread.h>
69#include <linux/random.h>
70#include <trace/events/bcache.h>
71
72#define MAX_OPEN_BUCKETS 128
73
74
75
76uint8_t bch_inc_gen(struct cache *ca, struct bucket *b)
77{
78 uint8_t ret = ++b->gen;
79
80 ca->set->need_gc = max(ca->set->need_gc, bucket_gc_gen(b));
81 WARN_ON_ONCE(ca->set->need_gc > BUCKET_GC_GEN_MAX);
82
83 return ret;
84}
85
86void bch_rescale_priorities(struct cache_set *c, int sectors)
87{
88 struct cache *ca;
89 struct bucket *b;
90 unsigned int next = c->nbuckets * c->sb.bucket_size / 1024;
91 unsigned int i;
92 int r;
93
94 atomic_sub(sectors, &c->rescale);
95
96 do {
97 r = atomic_read(&c->rescale);
98
99 if (r >= 0)
100 return;
101 } while (atomic_cmpxchg(&c->rescale, r, r + next) != r);
102
103 mutex_lock(&c->bucket_lock);
104
105 c->min_prio = USHRT_MAX;
106
107 for_each_cache(ca, c, i)
108 for_each_bucket(b, ca)
109 if (b->prio &&
110 b->prio != BTREE_PRIO &&
111 !atomic_read(&b->pin)) {
112 b->prio--;
113 c->min_prio = min(c->min_prio, b->prio);
114 }
115
116 mutex_unlock(&c->bucket_lock);
117}
118
119
120
121
122
123
124
125
126static inline bool can_inc_bucket_gen(struct bucket *b)
127{
128 return bucket_gc_gen(b) < BUCKET_GC_GEN_MAX;
129}
130
131bool bch_can_invalidate_bucket(struct cache *ca, struct bucket *b)
132{
133 BUG_ON(!ca->set->gc_mark_valid);
134
135 return (!GC_MARK(b) ||
136 GC_MARK(b) == GC_MARK_RECLAIMABLE) &&
137 !atomic_read(&b->pin) &&
138 can_inc_bucket_gen(b);
139}
140
141void __bch_invalidate_one_bucket(struct cache *ca, struct bucket *b)
142{
143 lockdep_assert_held(&ca->set->bucket_lock);
144 BUG_ON(GC_MARK(b) && GC_MARK(b) != GC_MARK_RECLAIMABLE);
145
146 if (GC_SECTORS_USED(b))
147 trace_bcache_invalidate(ca, b - ca->buckets);
148
149 bch_inc_gen(ca, b);
150 b->prio = INITIAL_PRIO;
151 atomic_inc(&b->pin);
152}
153
154static void bch_invalidate_one_bucket(struct cache *ca, struct bucket *b)
155{
156 __bch_invalidate_one_bucket(ca, b);
157
158 fifo_push(&ca->free_inc, b - ca->buckets);
159}
160
161
162
163
164
165
166
167
168
169
170#define bucket_prio(b) \
171({ \
172 unsigned int min_prio = (INITIAL_PRIO - ca->set->min_prio) / 8; \
173 \
174 (b->prio - ca->set->min_prio + min_prio) * GC_SECTORS_USED(b); \
175})
176
177#define bucket_max_cmp(l, r) (bucket_prio(l) < bucket_prio(r))
178#define bucket_min_cmp(l, r) (bucket_prio(l) > bucket_prio(r))
179
180static void invalidate_buckets_lru(struct cache *ca)
181{
182 struct bucket *b;
183 ssize_t i;
184
185 ca->heap.used = 0;
186
187 for_each_bucket(b, ca) {
188 if (!bch_can_invalidate_bucket(ca, b))
189 continue;
190
191 if (!heap_full(&ca->heap))
192 heap_add(&ca->heap, b, bucket_max_cmp);
193 else if (bucket_max_cmp(b, heap_peek(&ca->heap))) {
194 ca->heap.data[0] = b;
195 heap_sift(&ca->heap, 0, bucket_max_cmp);
196 }
197 }
198
199 for (i = ca->heap.used / 2 - 1; i >= 0; --i)
200 heap_sift(&ca->heap, i, bucket_min_cmp);
201
202 while (!fifo_full(&ca->free_inc)) {
203 if (!heap_pop(&ca->heap, b, bucket_min_cmp)) {
204
205
206
207
208 ca->invalidate_needs_gc = 1;
209 wake_up_gc(ca->set);
210 return;
211 }
212
213 bch_invalidate_one_bucket(ca, b);
214 }
215}
216
217static void invalidate_buckets_fifo(struct cache *ca)
218{
219 struct bucket *b;
220 size_t checked = 0;
221
222 while (!fifo_full(&ca->free_inc)) {
223 if (ca->fifo_last_bucket < ca->sb.first_bucket ||
224 ca->fifo_last_bucket >= ca->sb.nbuckets)
225 ca->fifo_last_bucket = ca->sb.first_bucket;
226
227 b = ca->buckets + ca->fifo_last_bucket++;
228
229 if (bch_can_invalidate_bucket(ca, b))
230 bch_invalidate_one_bucket(ca, b);
231
232 if (++checked >= ca->sb.nbuckets) {
233 ca->invalidate_needs_gc = 1;
234 wake_up_gc(ca->set);
235 return;
236 }
237 }
238}
239
240static void invalidate_buckets_random(struct cache *ca)
241{
242 struct bucket *b;
243 size_t checked = 0;
244
245 while (!fifo_full(&ca->free_inc)) {
246 size_t n;
247
248 get_random_bytes(&n, sizeof(n));
249
250 n %= (size_t) (ca->sb.nbuckets - ca->sb.first_bucket);
251 n += ca->sb.first_bucket;
252
253 b = ca->buckets + n;
254
255 if (bch_can_invalidate_bucket(ca, b))
256 bch_invalidate_one_bucket(ca, b);
257
258 if (++checked >= ca->sb.nbuckets / 2) {
259 ca->invalidate_needs_gc = 1;
260 wake_up_gc(ca->set);
261 return;
262 }
263 }
264}
265
266static void invalidate_buckets(struct cache *ca)
267{
268 BUG_ON(ca->invalidate_needs_gc);
269
270 switch (CACHE_REPLACEMENT(&ca->sb)) {
271 case CACHE_REPLACEMENT_LRU:
272 invalidate_buckets_lru(ca);
273 break;
274 case CACHE_REPLACEMENT_FIFO:
275 invalidate_buckets_fifo(ca);
276 break;
277 case CACHE_REPLACEMENT_RANDOM:
278 invalidate_buckets_random(ca);
279 break;
280 }
281}
282
283#define allocator_wait(ca, cond) \
284do { \
285 while (1) { \
286 set_current_state(TASK_INTERRUPTIBLE); \
287 if (cond) \
288 break; \
289 \
290 mutex_unlock(&(ca)->set->bucket_lock); \
291 if (kthread_should_stop() || \
292 test_bit(CACHE_SET_IO_DISABLE, &ca->set->flags)) { \
293 set_current_state(TASK_RUNNING); \
294 goto out; \
295 } \
296 \
297 schedule(); \
298 mutex_lock(&(ca)->set->bucket_lock); \
299 } \
300 __set_current_state(TASK_RUNNING); \
301} while (0)
302
303static int bch_allocator_push(struct cache *ca, long bucket)
304{
305 unsigned int i;
306
307
308 if (fifo_push(&ca->free[RESERVE_PRIO], bucket))
309 return true;
310
311 for (i = 0; i < RESERVE_NR; i++)
312 if (fifo_push(&ca->free[i], bucket))
313 return true;
314
315 return false;
316}
317
318static int bch_allocator_thread(void *arg)
319{
320 struct cache *ca = arg;
321
322 mutex_lock(&ca->set->bucket_lock);
323
324 while (1) {
325
326
327
328
329
330 while (!fifo_empty(&ca->free_inc)) {
331 long bucket;
332
333 fifo_pop(&ca->free_inc, bucket);
334
335 if (ca->discard) {
336 mutex_unlock(&ca->set->bucket_lock);
337 blkdev_issue_discard(ca->bdev,
338 bucket_to_sector(ca->set, bucket),
339 ca->sb.bucket_size, GFP_KERNEL, 0);
340 mutex_lock(&ca->set->bucket_lock);
341 }
342
343 allocator_wait(ca, bch_allocator_push(ca, bucket));
344 wake_up(&ca->set->btree_cache_wait);
345 wake_up(&ca->set->bucket_wait);
346 }
347
348
349
350
351
352
353
354retry_invalidate:
355 allocator_wait(ca, ca->set->gc_mark_valid &&
356 !ca->invalidate_needs_gc);
357 invalidate_buckets(ca);
358
359
360
361
362
363 allocator_wait(ca, !atomic_read(&ca->set->prio_blocked));
364 if (CACHE_SYNC(&ca->set->sb)) {
365
366
367
368
369
370
371
372
373
374
375
376 if (!fifo_full(&ca->free_inc))
377 goto retry_invalidate;
378
379 bch_prio_write(ca);
380 }
381 }
382out:
383 wait_for_kthread_stop();
384 return 0;
385}
386
387
388
389long bch_bucket_alloc(struct cache *ca, unsigned int reserve, bool wait)
390{
391 DEFINE_WAIT(w);
392 struct bucket *b;
393 long r;
394
395
396 if (fifo_pop(&ca->free[RESERVE_NONE], r) ||
397 fifo_pop(&ca->free[reserve], r))
398 goto out;
399
400 if (!wait) {
401 trace_bcache_alloc_fail(ca, reserve);
402 return -1;
403 }
404
405 do {
406 prepare_to_wait(&ca->set->bucket_wait, &w,
407 TASK_UNINTERRUPTIBLE);
408
409 mutex_unlock(&ca->set->bucket_lock);
410 schedule();
411 mutex_lock(&ca->set->bucket_lock);
412 } while (!fifo_pop(&ca->free[RESERVE_NONE], r) &&
413 !fifo_pop(&ca->free[reserve], r));
414
415 finish_wait(&ca->set->bucket_wait, &w);
416out:
417 if (ca->alloc_thread)
418 wake_up_process(ca->alloc_thread);
419
420 trace_bcache_alloc(ca, reserve);
421
422 if (expensive_debug_checks(ca->set)) {
423 size_t iter;
424 long i;
425 unsigned int j;
426
427 for (iter = 0; iter < prio_buckets(ca) * 2; iter++)
428 BUG_ON(ca->prio_buckets[iter] == (uint64_t) r);
429
430 for (j = 0; j < RESERVE_NR; j++)
431 fifo_for_each(i, &ca->free[j], iter)
432 BUG_ON(i == r);
433 fifo_for_each(i, &ca->free_inc, iter)
434 BUG_ON(i == r);
435 }
436
437 b = ca->buckets + r;
438
439 BUG_ON(atomic_read(&b->pin) != 1);
440
441 SET_GC_SECTORS_USED(b, ca->sb.bucket_size);
442
443 if (reserve <= RESERVE_PRIO) {
444 SET_GC_MARK(b, GC_MARK_METADATA);
445 SET_GC_MOVE(b, 0);
446 b->prio = BTREE_PRIO;
447 } else {
448 SET_GC_MARK(b, GC_MARK_RECLAIMABLE);
449 SET_GC_MOVE(b, 0);
450 b->prio = INITIAL_PRIO;
451 }
452
453 if (ca->set->avail_nbuckets > 0) {
454 ca->set->avail_nbuckets--;
455 bch_update_bucket_in_use(ca->set, &ca->set->gc_stats);
456 }
457
458 return r;
459}
460
461void __bch_bucket_free(struct cache *ca, struct bucket *b)
462{
463 SET_GC_MARK(b, 0);
464 SET_GC_SECTORS_USED(b, 0);
465
466 if (ca->set->avail_nbuckets < ca->set->nbuckets) {
467 ca->set->avail_nbuckets++;
468 bch_update_bucket_in_use(ca->set, &ca->set->gc_stats);
469 }
470}
471
472void bch_bucket_free(struct cache_set *c, struct bkey *k)
473{
474 unsigned int i;
475
476 for (i = 0; i < KEY_PTRS(k); i++)
477 __bch_bucket_free(PTR_CACHE(c, k, i),
478 PTR_BUCKET(c, k, i));
479}
480
481int __bch_bucket_alloc_set(struct cache_set *c, unsigned int reserve,
482 struct bkey *k, int n, bool wait)
483{
484 int i;
485
486 lockdep_assert_held(&c->bucket_lock);
487 BUG_ON(!n || n > c->caches_loaded || n > MAX_CACHES_PER_SET);
488
489 bkey_init(k);
490
491
492
493 for (i = 0; i < n; i++) {
494 struct cache *ca = c->cache_by_alloc[i];
495 long b = bch_bucket_alloc(ca, reserve, wait);
496
497 if (b == -1)
498 goto err;
499
500 k->ptr[i] = MAKE_PTR(ca->buckets[b].gen,
501 bucket_to_sector(c, b),
502 ca->sb.nr_this_dev);
503
504 SET_KEY_PTRS(k, i + 1);
505 }
506
507 return 0;
508err:
509 bch_bucket_free(c, k);
510 bkey_put(c, k);
511 return -1;
512}
513
514int bch_bucket_alloc_set(struct cache_set *c, unsigned int reserve,
515 struct bkey *k, int n, bool wait)
516{
517 int ret;
518
519 mutex_lock(&c->bucket_lock);
520 ret = __bch_bucket_alloc_set(c, reserve, k, n, wait);
521 mutex_unlock(&c->bucket_lock);
522 return ret;
523}
524
525
526
527struct open_bucket {
528 struct list_head list;
529 unsigned int last_write_point;
530 unsigned int sectors_free;
531 BKEY_PADDED(key);
532};
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559static struct open_bucket *pick_data_bucket(struct cache_set *c,
560 const struct bkey *search,
561 unsigned int write_point,
562 struct bkey *alloc)
563{
564 struct open_bucket *ret, *ret_task = NULL;
565
566 list_for_each_entry_reverse(ret, &c->data_buckets, list)
567 if (UUID_FLASH_ONLY(&c->uuids[KEY_INODE(&ret->key)]) !=
568 UUID_FLASH_ONLY(&c->uuids[KEY_INODE(search)]))
569 continue;
570 else if (!bkey_cmp(&ret->key, search))
571 goto found;
572 else if (ret->last_write_point == write_point)
573 ret_task = ret;
574
575 ret = ret_task ?: list_first_entry(&c->data_buckets,
576 struct open_bucket, list);
577found:
578 if (!ret->sectors_free && KEY_PTRS(alloc)) {
579 ret->sectors_free = c->sb.bucket_size;
580 bkey_copy(&ret->key, alloc);
581 bkey_init(alloc);
582 }
583
584 if (!ret->sectors_free)
585 ret = NULL;
586
587 return ret;
588}
589
590
591
592
593
594
595
596
597
598
599
600bool bch_alloc_sectors(struct cache_set *c,
601 struct bkey *k,
602 unsigned int sectors,
603 unsigned int write_point,
604 unsigned int write_prio,
605 bool wait)
606{
607 struct open_bucket *b;
608 BKEY_PADDED(key) alloc;
609 unsigned int i;
610
611
612
613
614
615
616
617
618 bkey_init(&alloc.key);
619 spin_lock(&c->data_bucket_lock);
620
621 while (!(b = pick_data_bucket(c, k, write_point, &alloc.key))) {
622 unsigned int watermark = write_prio
623 ? RESERVE_MOVINGGC
624 : RESERVE_NONE;
625
626 spin_unlock(&c->data_bucket_lock);
627
628 if (bch_bucket_alloc_set(c, watermark, &alloc.key, 1, wait))
629 return false;
630
631 spin_lock(&c->data_bucket_lock);
632 }
633
634
635
636
637
638
639 if (KEY_PTRS(&alloc.key))
640 bkey_put(c, &alloc.key);
641
642 for (i = 0; i < KEY_PTRS(&b->key); i++)
643 EBUG_ON(ptr_stale(c, &b->key, i));
644
645
646
647 for (i = 0; i < KEY_PTRS(&b->key); i++)
648 k->ptr[i] = b->key.ptr[i];
649
650 sectors = min(sectors, b->sectors_free);
651
652 SET_KEY_OFFSET(k, KEY_OFFSET(k) + sectors);
653 SET_KEY_SIZE(k, sectors);
654 SET_KEY_PTRS(k, KEY_PTRS(&b->key));
655
656
657
658
659
660 list_move_tail(&b->list, &c->data_buckets);
661 bkey_copy_key(&b->key, k);
662 b->last_write_point = write_point;
663
664 b->sectors_free -= sectors;
665
666 for (i = 0; i < KEY_PTRS(&b->key); i++) {
667 SET_PTR_OFFSET(&b->key, i, PTR_OFFSET(&b->key, i) + sectors);
668
669 atomic_long_add(sectors,
670 &PTR_CACHE(c, &b->key, i)->sectors_written);
671 }
672
673 if (b->sectors_free < c->sb.block_size)
674 b->sectors_free = 0;
675
676
677
678
679
680
681 if (b->sectors_free)
682 for (i = 0; i < KEY_PTRS(&b->key); i++)
683 atomic_inc(&PTR_BUCKET(c, &b->key, i)->pin);
684
685 spin_unlock(&c->data_bucket_lock);
686 return true;
687}
688
689
690
691void bch_open_buckets_free(struct cache_set *c)
692{
693 struct open_bucket *b;
694
695 while (!list_empty(&c->data_buckets)) {
696 b = list_first_entry(&c->data_buckets,
697 struct open_bucket, list);
698 list_del(&b->list);
699 kfree(b);
700 }
701}
702
703int bch_open_buckets_alloc(struct cache_set *c)
704{
705 int i;
706
707 spin_lock_init(&c->data_bucket_lock);
708
709 for (i = 0; i < MAX_OPEN_BUCKETS; i++) {
710 struct open_bucket *b = kzalloc(sizeof(*b), GFP_KERNEL);
711
712 if (!b)
713 return -ENOMEM;
714
715 list_add(&b->list, &c->data_buckets);
716 }
717
718 return 0;
719}
720
721int bch_cache_allocator_start(struct cache *ca)
722{
723 struct task_struct *k = kthread_run(bch_allocator_thread,
724 ca, "bcache_allocator");
725 if (IS_ERR(k))
726 return PTR_ERR(k);
727
728 ca->alloc_thread = k;
729 return 0;
730}
731