1
2
3
4
5
6
7#include "dm-cache-policy.h"
8#include "dm.h"
9
10#include <linux/hash.h>
11#include <linux/module.h>
12#include <linux/mutex.h>
13#include <linux/slab.h>
14#include <linux/vmalloc.h>
15
16#define DM_MSG_PREFIX "cache-policy-mq"
17
18static struct kmem_cache *mq_entry_cache;
19
20
21
22static unsigned next_power(unsigned n, unsigned min)
23{
24 return roundup_pow_of_two(max(n, min));
25}
26
27
28
29static unsigned long *alloc_bitset(unsigned nr_entries)
30{
31 size_t s = sizeof(unsigned long) * dm_div_up(nr_entries, BITS_PER_LONG);
32 return vzalloc(s);
33}
34
35static void free_bitset(unsigned long *bits)
36{
37 vfree(bits);
38}
39
40
41
42
43
44
45
46
47
48
49
50
51
52#define RANDOM_THRESHOLD_DEFAULT 4
53#define SEQUENTIAL_THRESHOLD_DEFAULT 512
54
55enum io_pattern {
56 PATTERN_SEQUENTIAL,
57 PATTERN_RANDOM
58};
59
60struct io_tracker {
61 enum io_pattern pattern;
62
63 unsigned nr_seq_samples;
64 unsigned nr_rand_samples;
65 unsigned thresholds[2];
66
67 dm_oblock_t last_end_oblock;
68};
69
70static void iot_init(struct io_tracker *t,
71 int sequential_threshold, int random_threshold)
72{
73 t->pattern = PATTERN_RANDOM;
74 t->nr_seq_samples = 0;
75 t->nr_rand_samples = 0;
76 t->last_end_oblock = 0;
77 t->thresholds[PATTERN_RANDOM] = random_threshold;
78 t->thresholds[PATTERN_SEQUENTIAL] = sequential_threshold;
79}
80
81static enum io_pattern iot_pattern(struct io_tracker *t)
82{
83 return t->pattern;
84}
85
86static void iot_update_stats(struct io_tracker *t, struct bio *bio)
87{
88 if (bio->bi_sector == from_oblock(t->last_end_oblock) + 1)
89 t->nr_seq_samples++;
90 else {
91
92
93
94
95 if (t->nr_seq_samples) {
96 t->nr_seq_samples = 0;
97 t->nr_rand_samples = 0;
98 }
99
100 t->nr_rand_samples++;
101 }
102
103 t->last_end_oblock = to_oblock(bio->bi_sector + bio_sectors(bio) - 1);
104}
105
106static void iot_check_for_pattern_switch(struct io_tracker *t)
107{
108 switch (t->pattern) {
109 case PATTERN_SEQUENTIAL:
110 if (t->nr_rand_samples >= t->thresholds[PATTERN_RANDOM]) {
111 t->pattern = PATTERN_RANDOM;
112 t->nr_seq_samples = t->nr_rand_samples = 0;
113 }
114 break;
115
116 case PATTERN_RANDOM:
117 if (t->nr_seq_samples >= t->thresholds[PATTERN_SEQUENTIAL]) {
118 t->pattern = PATTERN_SEQUENTIAL;
119 t->nr_seq_samples = t->nr_rand_samples = 0;
120 }
121 break;
122 }
123}
124
125static void iot_examine_bio(struct io_tracker *t, struct bio *bio)
126{
127 iot_update_stats(t, bio);
128 iot_check_for_pattern_switch(t);
129}
130
131
132
133
134
135
136
137
138
139#define NR_QUEUE_LEVELS 16u
140
141struct queue {
142 struct list_head qs[NR_QUEUE_LEVELS];
143};
144
145static void queue_init(struct queue *q)
146{
147 unsigned i;
148
149 for (i = 0; i < NR_QUEUE_LEVELS; i++)
150 INIT_LIST_HEAD(q->qs + i);
151}
152
153
154
155
156static void queue_push(struct queue *q, unsigned level, struct list_head *elt)
157{
158 list_add_tail(elt, q->qs + level);
159}
160
161static void queue_remove(struct list_head *elt)
162{
163 list_del(elt);
164}
165
166
167
168
169
170static void queue_shift_down(struct queue *q)
171{
172 unsigned level;
173
174 for (level = 1; level < NR_QUEUE_LEVELS; level++)
175 list_splice_init(q->qs + level, q->qs + level - 1);
176}
177
178
179
180
181
182static struct list_head *queue_pop(struct queue *q)
183{
184 unsigned level;
185 struct list_head *r;
186
187 for (level = 0; level < NR_QUEUE_LEVELS; level++)
188 if (!list_empty(q->qs + level)) {
189 r = q->qs[level].next;
190 list_del(r);
191
192
193 if (level == 0 && list_empty(q->qs))
194 queue_shift_down(q);
195
196 return r;
197 }
198
199 return NULL;
200}
201
202static struct list_head *list_pop(struct list_head *lh)
203{
204 struct list_head *r = lh->next;
205
206 BUG_ON(!r);
207 list_del_init(r);
208
209 return r;
210}
211
212
213
214
215
216
217struct entry {
218 struct hlist_node hlist;
219 struct list_head list;
220 dm_oblock_t oblock;
221 dm_cblock_t cblock;
222
223
224
225
226 bool in_cache:1;
227 unsigned hit_count;
228 unsigned generation;
229 unsigned tick;
230};
231
232struct mq_policy {
233 struct dm_cache_policy policy;
234
235
236 struct mutex lock;
237 dm_cblock_t cache_size;
238 struct io_tracker tracker;
239
240
241
242
243
244
245
246 struct queue pre_cache;
247 struct queue cache;
248
249
250
251
252
253
254
255
256
257 spinlock_t tick_lock;
258 unsigned tick_protected;
259 unsigned tick;
260
261
262
263
264
265
266 unsigned hit_count;
267
268
269
270
271
272
273
274 unsigned generation;
275 unsigned generation_period;
276
277
278
279
280
281
282 unsigned promote_threshold;
283
284
285
286
287
288
289
290 unsigned nr_entries;
291 unsigned nr_entries_allocated;
292 struct list_head free;
293
294
295
296
297
298 unsigned long *allocation_bitset;
299 unsigned nr_cblocks_allocated;
300 unsigned find_free_nr_words;
301 unsigned find_free_last_word;
302
303
304
305
306
307 unsigned nr_buckets;
308 dm_block_t hash_bits;
309 struct hlist_head *table;
310};
311
312
313
314static void takeout_queue(struct list_head *lh, struct queue *q)
315{
316 unsigned level;
317
318 for (level = 0; level < NR_QUEUE_LEVELS; level++)
319 list_splice(q->qs + level, lh);
320}
321
322static void free_entries(struct mq_policy *mq)
323{
324 struct entry *e, *tmp;
325
326 takeout_queue(&mq->free, &mq->pre_cache);
327 takeout_queue(&mq->free, &mq->cache);
328
329 list_for_each_entry_safe(e, tmp, &mq->free, list)
330 kmem_cache_free(mq_entry_cache, e);
331}
332
333static int alloc_entries(struct mq_policy *mq, unsigned elts)
334{
335 unsigned u = mq->nr_entries;
336
337 INIT_LIST_HEAD(&mq->free);
338 mq->nr_entries_allocated = 0;
339
340 while (u--) {
341 struct entry *e = kmem_cache_zalloc(mq_entry_cache, GFP_KERNEL);
342
343 if (!e) {
344 free_entries(mq);
345 return -ENOMEM;
346 }
347
348
349 list_add(&e->list, &mq->free);
350 }
351
352 return 0;
353}
354
355
356
357
358
359
360
361static void hash_insert(struct mq_policy *mq, struct entry *e)
362{
363 unsigned h = hash_64(from_oblock(e->oblock), mq->hash_bits);
364
365 hlist_add_head(&e->hlist, mq->table + h);
366}
367
368static struct entry *hash_lookup(struct mq_policy *mq, dm_oblock_t oblock)
369{
370 unsigned h = hash_64(from_oblock(oblock), mq->hash_bits);
371 struct hlist_head *bucket = mq->table + h;
372 struct entry *e;
373
374 hlist_for_each_entry(e, bucket, hlist)
375 if (e->oblock == oblock) {
376 hlist_del(&e->hlist);
377 hlist_add_head(&e->hlist, bucket);
378 return e;
379 }
380
381 return NULL;
382}
383
384static void hash_remove(struct entry *e)
385{
386 hlist_del(&e->hlist);
387}
388
389
390
391
392
393
394
395
396static struct entry *alloc_entry(struct mq_policy *mq)
397{
398 struct entry *e;
399
400 if (mq->nr_entries_allocated >= mq->nr_entries) {
401 BUG_ON(!list_empty(&mq->free));
402 return NULL;
403 }
404
405 e = list_entry(list_pop(&mq->free), struct entry, list);
406 INIT_LIST_HEAD(&e->list);
407 INIT_HLIST_NODE(&e->hlist);
408
409 mq->nr_entries_allocated++;
410 return e;
411}
412
413
414
415
416
417
418static void alloc_cblock(struct mq_policy *mq, dm_cblock_t cblock)
419{
420 BUG_ON(from_cblock(cblock) > from_cblock(mq->cache_size));
421 BUG_ON(test_bit(from_cblock(cblock), mq->allocation_bitset));
422
423 set_bit(from_cblock(cblock), mq->allocation_bitset);
424 mq->nr_cblocks_allocated++;
425}
426
427static void free_cblock(struct mq_policy *mq, dm_cblock_t cblock)
428{
429 BUG_ON(from_cblock(cblock) > from_cblock(mq->cache_size));
430 BUG_ON(!test_bit(from_cblock(cblock), mq->allocation_bitset));
431
432 clear_bit(from_cblock(cblock), mq->allocation_bitset);
433 mq->nr_cblocks_allocated--;
434}
435
436static bool any_free_cblocks(struct mq_policy *mq)
437{
438 return mq->nr_cblocks_allocated < from_cblock(mq->cache_size);
439}
440
441
442
443
444
445
446static int __find_free_cblock(struct mq_policy *mq, unsigned begin, unsigned end,
447 dm_cblock_t *result, unsigned *last_word)
448{
449 int r = -ENOSPC;
450 unsigned w;
451
452 for (w = begin; w < end; w++) {
453
454
455
456 if (mq->allocation_bitset[w] != ~0UL) {
457 *last_word = w;
458 *result = to_cblock((w * BITS_PER_LONG) + ffz(mq->allocation_bitset[w]));
459 if (from_cblock(*result) < from_cblock(mq->cache_size))
460 r = 0;
461
462 break;
463 }
464 }
465
466 return r;
467}
468
469static int find_free_cblock(struct mq_policy *mq, dm_cblock_t *result)
470{
471 int r;
472
473 if (!any_free_cblocks(mq))
474 return -ENOSPC;
475
476 r = __find_free_cblock(mq, mq->find_free_last_word, mq->find_free_nr_words, result, &mq->find_free_last_word);
477 if (r == -ENOSPC && mq->find_free_last_word)
478 r = __find_free_cblock(mq, 0, mq->find_free_last_word, result, &mq->find_free_last_word);
479
480 return r;
481}
482
483
484
485
486
487
488
489
490
491
492
493
494static unsigned queue_level(struct entry *e)
495{
496 return min((unsigned) ilog2(e->hit_count), NR_QUEUE_LEVELS - 1u);
497}
498
499
500
501
502
503
504static void push(struct mq_policy *mq, struct entry *e)
505{
506 e->tick = mq->tick;
507 hash_insert(mq, e);
508
509 if (e->in_cache) {
510 alloc_cblock(mq, e->cblock);
511 queue_push(&mq->cache, queue_level(e), &e->list);
512 } else
513 queue_push(&mq->pre_cache, queue_level(e), &e->list);
514}
515
516
517
518
519
520static void del(struct mq_policy *mq, struct entry *e)
521{
522 queue_remove(&e->list);
523 hash_remove(e);
524 if (e->in_cache)
525 free_cblock(mq, e->cblock);
526}
527
528
529
530
531
532static struct entry *pop(struct mq_policy *mq, struct queue *q)
533{
534 struct entry *e = container_of(queue_pop(q), struct entry, list);
535
536 if (e) {
537 hash_remove(e);
538
539 if (e->in_cache)
540 free_cblock(mq, e->cblock);
541 }
542
543 return e;
544}
545
546
547
548
549static bool updated_this_tick(struct mq_policy *mq, struct entry *e)
550{
551 return mq->tick == e->tick;
552}
553
554
555
556
557
558
559
560
561
562
563
564
565
566#define MAX_TO_AVERAGE 20
567
568static void check_generation(struct mq_policy *mq)
569{
570 unsigned total = 0, nr = 0, count = 0, level;
571 struct list_head *head;
572 struct entry *e;
573
574 if ((mq->hit_count >= mq->generation_period) &&
575 (mq->nr_cblocks_allocated == from_cblock(mq->cache_size))) {
576
577 mq->hit_count = 0;
578 mq->generation++;
579
580 for (level = 0; level < NR_QUEUE_LEVELS && count < MAX_TO_AVERAGE; level++) {
581 head = mq->cache.qs + level;
582 list_for_each_entry(e, head, list) {
583 nr++;
584 total += e->hit_count;
585
586 if (++count >= MAX_TO_AVERAGE)
587 break;
588 }
589 }
590
591 mq->promote_threshold = nr ? total / nr : 1;
592 if (mq->promote_threshold * nr < total)
593 mq->promote_threshold++;
594 }
595}
596
597
598
599
600
601static void requeue_and_update_tick(struct mq_policy *mq, struct entry *e)
602{
603 if (updated_this_tick(mq, e))
604 return;
605
606 e->hit_count++;
607 mq->hit_count++;
608 check_generation(mq);
609
610
611
612
613 e->generation = mq->generation;
614
615 del(mq, e);
616 push(mq, e);
617}
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634static dm_cblock_t demote_cblock(struct mq_policy *mq, dm_oblock_t *oblock)
635{
636 dm_cblock_t result;
637 struct entry *demoted = pop(mq, &mq->cache);
638
639 BUG_ON(!demoted);
640 result = demoted->cblock;
641 *oblock = demoted->oblock;
642 demoted->in_cache = false;
643 demoted->hit_count = 1;
644 push(mq, demoted);
645
646 return result;
647}
648
649
650
651
652
653
654
655
656
657
658#define DISCARDED_PROMOTE_THRESHOLD 1
659#define READ_PROMOTE_THRESHOLD 4
660#define WRITE_PROMOTE_THRESHOLD 8
661
662static unsigned adjusted_promote_threshold(struct mq_policy *mq,
663 bool discarded_oblock, int data_dir)
664{
665 if (discarded_oblock && any_free_cblocks(mq) && data_dir == WRITE)
666
667
668
669
670
671 return DISCARDED_PROMOTE_THRESHOLD;
672
673 return data_dir == READ ?
674 (mq->promote_threshold + READ_PROMOTE_THRESHOLD) :
675 (mq->promote_threshold + WRITE_PROMOTE_THRESHOLD);
676}
677
678static bool should_promote(struct mq_policy *mq, struct entry *e,
679 bool discarded_oblock, int data_dir)
680{
681 return e->hit_count >=
682 adjusted_promote_threshold(mq, discarded_oblock, data_dir);
683}
684
685static int cache_entry_found(struct mq_policy *mq,
686 struct entry *e,
687 struct policy_result *result)
688{
689 requeue_and_update_tick(mq, e);
690
691 if (e->in_cache) {
692 result->op = POLICY_HIT;
693 result->cblock = e->cblock;
694 }
695
696 return 0;
697}
698
699
700
701
702
703static int pre_cache_to_cache(struct mq_policy *mq, struct entry *e,
704 struct policy_result *result)
705{
706 dm_cblock_t cblock;
707
708 if (find_free_cblock(mq, &cblock) == -ENOSPC) {
709 result->op = POLICY_REPLACE;
710 cblock = demote_cblock(mq, &result->old_oblock);
711 } else
712 result->op = POLICY_NEW;
713
714 result->cblock = e->cblock = cblock;
715
716 del(mq, e);
717 e->in_cache = true;
718 push(mq, e);
719
720 return 0;
721}
722
723static int pre_cache_entry_found(struct mq_policy *mq, struct entry *e,
724 bool can_migrate, bool discarded_oblock,
725 int data_dir, struct policy_result *result)
726{
727 int r = 0;
728 bool updated = updated_this_tick(mq, e);
729
730 requeue_and_update_tick(mq, e);
731
732 if ((!discarded_oblock && updated) ||
733 !should_promote(mq, e, discarded_oblock, data_dir))
734 result->op = POLICY_MISS;
735 else if (!can_migrate)
736 r = -EWOULDBLOCK;
737 else
738 r = pre_cache_to_cache(mq, e, result);
739
740 return r;
741}
742
743static void insert_in_pre_cache(struct mq_policy *mq,
744 dm_oblock_t oblock)
745{
746 struct entry *e = alloc_entry(mq);
747
748 if (!e)
749
750
751
752
753 e = pop(mq, &mq->pre_cache);
754
755 if (unlikely(!e)) {
756 DMWARN("couldn't pop from pre cache");
757 return;
758 }
759
760 e->in_cache = false;
761 e->oblock = oblock;
762 e->hit_count = 1;
763 e->generation = mq->generation;
764 push(mq, e);
765}
766
767static void insert_in_cache(struct mq_policy *mq, dm_oblock_t oblock,
768 struct policy_result *result)
769{
770 struct entry *e;
771 dm_cblock_t cblock;
772
773 if (find_free_cblock(mq, &cblock) == -ENOSPC) {
774 result->op = POLICY_MISS;
775 insert_in_pre_cache(mq, oblock);
776 return;
777 }
778
779 e = alloc_entry(mq);
780 if (unlikely(!e)) {
781 result->op = POLICY_MISS;
782 return;
783 }
784
785 e->oblock = oblock;
786 e->cblock = cblock;
787 e->in_cache = true;
788 e->hit_count = 1;
789 e->generation = mq->generation;
790 push(mq, e);
791
792 result->op = POLICY_NEW;
793 result->cblock = e->cblock;
794}
795
796static int no_entry_found(struct mq_policy *mq, dm_oblock_t oblock,
797 bool can_migrate, bool discarded_oblock,
798 int data_dir, struct policy_result *result)
799{
800 if (adjusted_promote_threshold(mq, discarded_oblock, data_dir) == 1) {
801 if (can_migrate)
802 insert_in_cache(mq, oblock, result);
803 else
804 return -EWOULDBLOCK;
805 } else {
806 insert_in_pre_cache(mq, oblock);
807 result->op = POLICY_MISS;
808 }
809
810 return 0;
811}
812
813
814
815
816
817static int map(struct mq_policy *mq, dm_oblock_t oblock,
818 bool can_migrate, bool discarded_oblock,
819 int data_dir, struct policy_result *result)
820{
821 int r = 0;
822 struct entry *e = hash_lookup(mq, oblock);
823
824 if (e && e->in_cache)
825 r = cache_entry_found(mq, e, result);
826 else if (iot_pattern(&mq->tracker) == PATTERN_SEQUENTIAL)
827 result->op = POLICY_MISS;
828 else if (e)
829 r = pre_cache_entry_found(mq, e, can_migrate, discarded_oblock,
830 data_dir, result);
831 else
832 r = no_entry_found(mq, oblock, can_migrate, discarded_oblock,
833 data_dir, result);
834
835 if (r == -EWOULDBLOCK)
836 result->op = POLICY_MISS;
837
838 return r;
839}
840
841
842
843
844
845
846
847
848static struct mq_policy *to_mq_policy(struct dm_cache_policy *p)
849{
850 return container_of(p, struct mq_policy, policy);
851}
852
853static void mq_destroy(struct dm_cache_policy *p)
854{
855 struct mq_policy *mq = to_mq_policy(p);
856
857 free_bitset(mq->allocation_bitset);
858 kfree(mq->table);
859 free_entries(mq);
860 kfree(mq);
861}
862
863static void copy_tick(struct mq_policy *mq)
864{
865 unsigned long flags;
866
867 spin_lock_irqsave(&mq->tick_lock, flags);
868 mq->tick = mq->tick_protected;
869 spin_unlock_irqrestore(&mq->tick_lock, flags);
870}
871
872static int mq_map(struct dm_cache_policy *p, dm_oblock_t oblock,
873 bool can_block, bool can_migrate, bool discarded_oblock,
874 struct bio *bio, struct policy_result *result)
875{
876 int r;
877 struct mq_policy *mq = to_mq_policy(p);
878
879 result->op = POLICY_MISS;
880
881 if (can_block)
882 mutex_lock(&mq->lock);
883 else if (!mutex_trylock(&mq->lock))
884 return -EWOULDBLOCK;
885
886 copy_tick(mq);
887
888 iot_examine_bio(&mq->tracker, bio);
889 r = map(mq, oblock, can_migrate, discarded_oblock,
890 bio_data_dir(bio), result);
891
892 mutex_unlock(&mq->lock);
893
894 return r;
895}
896
897static int mq_lookup(struct dm_cache_policy *p, dm_oblock_t oblock, dm_cblock_t *cblock)
898{
899 int r;
900 struct mq_policy *mq = to_mq_policy(p);
901 struct entry *e;
902
903 if (!mutex_trylock(&mq->lock))
904 return -EWOULDBLOCK;
905
906 e = hash_lookup(mq, oblock);
907 if (e && e->in_cache) {
908 *cblock = e->cblock;
909 r = 0;
910 } else
911 r = -ENOENT;
912
913 mutex_unlock(&mq->lock);
914
915 return r;
916}
917
918static int mq_load_mapping(struct dm_cache_policy *p,
919 dm_oblock_t oblock, dm_cblock_t cblock,
920 uint32_t hint, bool hint_valid)
921{
922 struct mq_policy *mq = to_mq_policy(p);
923 struct entry *e;
924
925 e = alloc_entry(mq);
926 if (!e)
927 return -ENOMEM;
928
929 e->cblock = cblock;
930 e->oblock = oblock;
931 e->in_cache = true;
932 e->hit_count = hint_valid ? hint : 1;
933 e->generation = mq->generation;
934 push(mq, e);
935
936 return 0;
937}
938
939static int mq_walk_mappings(struct dm_cache_policy *p, policy_walk_fn fn,
940 void *context)
941{
942 struct mq_policy *mq = to_mq_policy(p);
943 int r = 0;
944 struct entry *e;
945 unsigned level;
946
947 mutex_lock(&mq->lock);
948
949 for (level = 0; level < NR_QUEUE_LEVELS; level++)
950 list_for_each_entry(e, &mq->cache.qs[level], list) {
951 r = fn(context, e->cblock, e->oblock, e->hit_count);
952 if (r)
953 goto out;
954 }
955
956out:
957 mutex_unlock(&mq->lock);
958
959 return r;
960}
961
962static void mq_remove_mapping(struct dm_cache_policy *p, dm_oblock_t oblock)
963{
964 struct mq_policy *mq = to_mq_policy(p);
965 struct entry *e;
966
967 mutex_lock(&mq->lock);
968
969 e = hash_lookup(mq, oblock);
970
971 BUG_ON(!e || !e->in_cache);
972
973 del(mq, e);
974 e->in_cache = false;
975 push(mq, e);
976
977 mutex_unlock(&mq->lock);
978}
979
980static void force_mapping(struct mq_policy *mq,
981 dm_oblock_t current_oblock, dm_oblock_t new_oblock)
982{
983 struct entry *e = hash_lookup(mq, current_oblock);
984
985 BUG_ON(!e || !e->in_cache);
986
987 del(mq, e);
988 e->oblock = new_oblock;
989 push(mq, e);
990}
991
992static void mq_force_mapping(struct dm_cache_policy *p,
993 dm_oblock_t current_oblock, dm_oblock_t new_oblock)
994{
995 struct mq_policy *mq = to_mq_policy(p);
996
997 mutex_lock(&mq->lock);
998 force_mapping(mq, current_oblock, new_oblock);
999 mutex_unlock(&mq->lock);
1000}
1001
1002static dm_cblock_t mq_residency(struct dm_cache_policy *p)
1003{
1004 struct mq_policy *mq = to_mq_policy(p);
1005
1006
1007 return to_cblock(mq->nr_cblocks_allocated);
1008}
1009
1010static void mq_tick(struct dm_cache_policy *p)
1011{
1012 struct mq_policy *mq = to_mq_policy(p);
1013 unsigned long flags;
1014
1015 spin_lock_irqsave(&mq->tick_lock, flags);
1016 mq->tick_protected++;
1017 spin_unlock_irqrestore(&mq->tick_lock, flags);
1018}
1019
1020static int mq_set_config_value(struct dm_cache_policy *p,
1021 const char *key, const char *value)
1022{
1023 struct mq_policy *mq = to_mq_policy(p);
1024 enum io_pattern pattern;
1025 unsigned long tmp;
1026
1027 if (!strcasecmp(key, "random_threshold"))
1028 pattern = PATTERN_RANDOM;
1029 else if (!strcasecmp(key, "sequential_threshold"))
1030 pattern = PATTERN_SEQUENTIAL;
1031 else
1032 return -EINVAL;
1033
1034 if (kstrtoul(value, 10, &tmp))
1035 return -EINVAL;
1036
1037 mq->tracker.thresholds[pattern] = tmp;
1038
1039 return 0;
1040}
1041
1042static int mq_emit_config_values(struct dm_cache_policy *p, char *result, unsigned maxlen)
1043{
1044 ssize_t sz = 0;
1045 struct mq_policy *mq = to_mq_policy(p);
1046
1047 DMEMIT("4 random_threshold %u sequential_threshold %u",
1048 mq->tracker.thresholds[PATTERN_RANDOM],
1049 mq->tracker.thresholds[PATTERN_SEQUENTIAL]);
1050
1051 return 0;
1052}
1053
1054
1055static void init_policy_functions(struct mq_policy *mq)
1056{
1057 mq->policy.destroy = mq_destroy;
1058 mq->policy.map = mq_map;
1059 mq->policy.lookup = mq_lookup;
1060 mq->policy.load_mapping = mq_load_mapping;
1061 mq->policy.walk_mappings = mq_walk_mappings;
1062 mq->policy.remove_mapping = mq_remove_mapping;
1063 mq->policy.writeback_work = NULL;
1064 mq->policy.force_mapping = mq_force_mapping;
1065 mq->policy.residency = mq_residency;
1066 mq->policy.tick = mq_tick;
1067 mq->policy.emit_config_values = mq_emit_config_values;
1068 mq->policy.set_config_value = mq_set_config_value;
1069}
1070
1071static struct dm_cache_policy *mq_create(dm_cblock_t cache_size,
1072 sector_t origin_size,
1073 sector_t cache_block_size)
1074{
1075 int r;
1076 struct mq_policy *mq = kzalloc(sizeof(*mq), GFP_KERNEL);
1077
1078 if (!mq)
1079 return NULL;
1080
1081 init_policy_functions(mq);
1082 iot_init(&mq->tracker, SEQUENTIAL_THRESHOLD_DEFAULT, RANDOM_THRESHOLD_DEFAULT);
1083
1084 mq->cache_size = cache_size;
1085 mq->tick_protected = 0;
1086 mq->tick = 0;
1087 mq->hit_count = 0;
1088 mq->generation = 0;
1089 mq->promote_threshold = 0;
1090 mutex_init(&mq->lock);
1091 spin_lock_init(&mq->tick_lock);
1092 mq->find_free_nr_words = dm_div_up(from_cblock(mq->cache_size), BITS_PER_LONG);
1093 mq->find_free_last_word = 0;
1094
1095 queue_init(&mq->pre_cache);
1096 queue_init(&mq->cache);
1097 mq->generation_period = max((unsigned) from_cblock(cache_size), 1024U);
1098
1099 mq->nr_entries = 2 * from_cblock(cache_size);
1100 r = alloc_entries(mq, mq->nr_entries);
1101 if (r)
1102 goto bad_cache_alloc;
1103
1104 mq->nr_entries_allocated = 0;
1105 mq->nr_cblocks_allocated = 0;
1106
1107 mq->nr_buckets = next_power(from_cblock(cache_size) / 2, 16);
1108 mq->hash_bits = ffs(mq->nr_buckets) - 1;
1109 mq->table = kzalloc(sizeof(*mq->table) * mq->nr_buckets, GFP_KERNEL);
1110 if (!mq->table)
1111 goto bad_alloc_table;
1112
1113 mq->allocation_bitset = alloc_bitset(from_cblock(cache_size));
1114 if (!mq->allocation_bitset)
1115 goto bad_alloc_bitset;
1116
1117 return &mq->policy;
1118
1119bad_alloc_bitset:
1120 kfree(mq->table);
1121bad_alloc_table:
1122 free_entries(mq);
1123bad_cache_alloc:
1124 kfree(mq);
1125
1126 return NULL;
1127}
1128
1129
1130
1131static struct dm_cache_policy_type mq_policy_type = {
1132 .name = "mq",
1133 .version = {1, 0, 0},
1134 .hint_size = 4,
1135 .owner = THIS_MODULE,
1136 .create = mq_create
1137};
1138
1139static struct dm_cache_policy_type default_policy_type = {
1140 .name = "default",
1141 .version = {1, 0, 0},
1142 .hint_size = 4,
1143 .owner = THIS_MODULE,
1144 .create = mq_create
1145};
1146
1147static int __init mq_init(void)
1148{
1149 int r;
1150
1151 mq_entry_cache = kmem_cache_create("dm_mq_policy_cache_entry",
1152 sizeof(struct entry),
1153 __alignof__(struct entry),
1154 0, NULL);
1155 if (!mq_entry_cache)
1156 goto bad;
1157
1158 r = dm_cache_policy_register(&mq_policy_type);
1159 if (r) {
1160 DMERR("register failed %d", r);
1161 goto bad_register_mq;
1162 }
1163
1164 r = dm_cache_policy_register(&default_policy_type);
1165 if (!r) {
1166 DMINFO("version %u.%u.%u loaded",
1167 mq_policy_type.version[0],
1168 mq_policy_type.version[1],
1169 mq_policy_type.version[2]);
1170 return 0;
1171 }
1172
1173 DMERR("register failed (as default) %d", r);
1174
1175 dm_cache_policy_unregister(&mq_policy_type);
1176bad_register_mq:
1177 kmem_cache_destroy(mq_entry_cache);
1178bad:
1179 return -ENOMEM;
1180}
1181
1182static void __exit mq_exit(void)
1183{
1184 dm_cache_policy_unregister(&mq_policy_type);
1185 dm_cache_policy_unregister(&default_policy_type);
1186
1187 kmem_cache_destroy(mq_entry_cache);
1188}
1189
1190module_init(mq_init);
1191module_exit(mq_exit);
1192
1193MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
1194MODULE_LICENSE("GPL");
1195MODULE_DESCRIPTION("mq cache policy");
1196
1197MODULE_ALIAS("dm-cache-default");
1198