blob: 13f547a4eeb61f2715845090b8e2e5ce311c73d1 [file] [log] [blame]
Joe Thornberf2836352013-03-01 22:45:51 +00001/*
2 * Copyright (C) 2012 Red Hat. All rights reserved.
3 *
4 * This file is released under the GPL.
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"
Joe Thornberf2836352013-03-01 22:45:51 +000017
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
Joe Thornberf2836352013-03-01 22:45:51 +000029/*
30 * Large, sequential ios are probably better left on the origin device since
31 * spindles tend to have good bandwidth.
32 *
33 * The io_tracker tries to spot when the io is in one of these sequential
34 * modes.
35 *
36 * Two thresholds to switch between random and sequential io mode are defaulting
37 * as follows and can be adjusted via the constructor and message interfaces.
38 */
39#define RANDOM_THRESHOLD_DEFAULT 4
40#define SEQUENTIAL_THRESHOLD_DEFAULT 512
41
42enum io_pattern {
43 PATTERN_SEQUENTIAL,
44 PATTERN_RANDOM
45};
46
47struct io_tracker {
48 enum io_pattern pattern;
49
50 unsigned nr_seq_samples;
51 unsigned nr_rand_samples;
52 unsigned thresholds[2];
53
54 dm_oblock_t last_end_oblock;
55};
56
57static void iot_init(struct io_tracker *t,
58 int sequential_threshold, int random_threshold)
59{
60 t->pattern = PATTERN_RANDOM;
61 t->nr_seq_samples = 0;
62 t->nr_rand_samples = 0;
63 t->last_end_oblock = 0;
64 t->thresholds[PATTERN_RANDOM] = random_threshold;
65 t->thresholds[PATTERN_SEQUENTIAL] = sequential_threshold;
66}
67
68static enum io_pattern iot_pattern(struct io_tracker *t)
69{
70 return t->pattern;
71}
72
73static void iot_update_stats(struct io_tracker *t, struct bio *bio)
74{
Kent Overstreet4f024f32013-10-11 15:44:27 -070075 if (bio->bi_iter.bi_sector == from_oblock(t->last_end_oblock) + 1)
Joe Thornberf2836352013-03-01 22:45:51 +000076 t->nr_seq_samples++;
77 else {
78 /*
79 * Just one non-sequential IO is enough to reset the
80 * counters.
81 */
82 if (t->nr_seq_samples) {
83 t->nr_seq_samples = 0;
84 t->nr_rand_samples = 0;
85 }
86
87 t->nr_rand_samples++;
88 }
89
Kent Overstreet4f024f32013-10-11 15:44:27 -070090 t->last_end_oblock = to_oblock(bio_end_sector(bio) - 1);
Joe Thornberf2836352013-03-01 22:45:51 +000091}
92
93static void iot_check_for_pattern_switch(struct io_tracker *t)
94{
95 switch (t->pattern) {
96 case PATTERN_SEQUENTIAL:
97 if (t->nr_rand_samples >= t->thresholds[PATTERN_RANDOM]) {
98 t->pattern = PATTERN_RANDOM;
99 t->nr_seq_samples = t->nr_rand_samples = 0;
100 }
101 break;
102
103 case PATTERN_RANDOM:
104 if (t->nr_seq_samples >= t->thresholds[PATTERN_SEQUENTIAL]) {
105 t->pattern = PATTERN_SEQUENTIAL;
106 t->nr_seq_samples = t->nr_rand_samples = 0;
107 }
108 break;
109 }
110}
111
112static void iot_examine_bio(struct io_tracker *t, struct bio *bio)
113{
114 iot_update_stats(t, bio);
115 iot_check_for_pattern_switch(t);
116}
117
118/*----------------------------------------------------------------*/
119
120
121/*
122 * This queue is divided up into different levels. Allowing us to push
123 * entries to the back of any of the levels. Think of it as a partially
124 * sorted queue.
125 */
126#define NR_QUEUE_LEVELS 16u
127
128struct queue {
129 struct list_head qs[NR_QUEUE_LEVELS];
130};
131
132static void queue_init(struct queue *q)
133{
134 unsigned i;
135
136 for (i = 0; i < NR_QUEUE_LEVELS; i++)
137 INIT_LIST_HEAD(q->qs + i);
138}
139
140/*
Joe Thornberc86c3072013-10-24 14:10:28 -0400141 * Checks to see if the queue is empty.
142 * FIXME: reduce cpu usage.
143 */
144static bool queue_empty(struct queue *q)
145{
146 unsigned i;
147
148 for (i = 0; i < NR_QUEUE_LEVELS; i++)
149 if (!list_empty(q->qs + i))
150 return false;
151
152 return true;
153}
154
155/*
Joe Thornberf2836352013-03-01 22:45:51 +0000156 * Insert an entry to the back of the given level.
157 */
158static void queue_push(struct queue *q, unsigned level, struct list_head *elt)
159{
160 list_add_tail(elt, q->qs + level);
161}
162
163static void queue_remove(struct list_head *elt)
164{
165 list_del(elt);
166}
167
168/*
169 * Shifts all regions down one level. This has no effect on the order of
170 * the queue.
171 */
172static void queue_shift_down(struct queue *q)
173{
174 unsigned level;
175
176 for (level = 1; level < NR_QUEUE_LEVELS; level++)
177 list_splice_init(q->qs + level, q->qs + level - 1);
178}
179
180/*
181 * Gives us the oldest entry of the lowest popoulated level. If the first
182 * level is emptied then we shift down one level.
183 */
Joe Thornberb155aa02014-10-22 14:30:58 +0100184static struct list_head *queue_peek(struct queue *q)
Joe Thornberf2836352013-03-01 22:45:51 +0000185{
186 unsigned level;
Joe Thornberf2836352013-03-01 22:45:51 +0000187
188 for (level = 0; level < NR_QUEUE_LEVELS; level++)
Joe Thornberb155aa02014-10-22 14:30:58 +0100189 if (!list_empty(q->qs + level))
190 return q->qs[level].next;
Joe Thornberf2836352013-03-01 22:45:51 +0000191
192 return NULL;
193}
194
Joe Thornberb155aa02014-10-22 14:30:58 +0100195static struct list_head *queue_pop(struct queue *q)
196{
197 struct list_head *r = queue_peek(q);
198
199 if (r) {
200 list_del(r);
201
202 /* have we just emptied the bottom level? */
203 if (list_empty(q->qs))
204 queue_shift_down(q);
205 }
206
207 return r;
208}
209
Joe Thornberf2836352013-03-01 22:45:51 +0000210static struct list_head *list_pop(struct list_head *lh)
211{
212 struct list_head *r = lh->next;
213
214 BUG_ON(!r);
215 list_del_init(r);
216
217 return r;
218}
219
220/*----------------------------------------------------------------*/
221
222/*
223 * Describes a cache entry. Used in both the cache and the pre_cache.
224 */
225struct entry {
226 struct hlist_node hlist;
227 struct list_head list;
228 dm_oblock_t oblock;
Joe Thornberf2836352013-03-01 22:45:51 +0000229
230 /*
231 * FIXME: pack these better
232 */
Joe Thornber01911c12013-10-24 14:10:28 -0400233 bool dirty:1;
Joe Thornberf2836352013-03-01 22:45:51 +0000234 unsigned hit_count;
235 unsigned generation;
236 unsigned tick;
237};
238
Joe Thornber633618e2013-11-09 11:12:51 +0000239/*
240 * Rather than storing the cblock in an entry, we allocate all entries in
241 * an array, and infer the cblock from the entry position.
242 *
243 * Free entries are linked together into a list.
244 */
245struct entry_pool {
246 struct entry *entries, *entries_end;
247 struct list_head free;
248 unsigned nr_allocated;
249};
250
251static int epool_init(struct entry_pool *ep, unsigned nr_entries)
252{
253 unsigned i;
254
255 ep->entries = vzalloc(sizeof(struct entry) * nr_entries);
256 if (!ep->entries)
257 return -ENOMEM;
258
259 ep->entries_end = ep->entries + nr_entries;
260
261 INIT_LIST_HEAD(&ep->free);
262 for (i = 0; i < nr_entries; i++)
263 list_add(&ep->entries[i].list, &ep->free);
264
265 ep->nr_allocated = 0;
266
267 return 0;
268}
269
270static void epool_exit(struct entry_pool *ep)
271{
272 vfree(ep->entries);
273}
274
275static struct entry *alloc_entry(struct entry_pool *ep)
276{
277 struct entry *e;
278
279 if (list_empty(&ep->free))
280 return NULL;
281
282 e = list_entry(list_pop(&ep->free), struct entry, list);
283 INIT_LIST_HEAD(&e->list);
284 INIT_HLIST_NODE(&e->hlist);
285 ep->nr_allocated++;
286
287 return e;
288}
289
290/*
291 * This assumes the cblock hasn't already been allocated.
292 */
293static struct entry *alloc_particular_entry(struct entry_pool *ep, dm_cblock_t cblock)
294{
295 struct entry *e = ep->entries + from_cblock(cblock);
Joe Thornber633618e2013-11-09 11:12:51 +0000296
Wei Yongjunb8158052013-11-18 13:32:43 -0500297 list_del_init(&e->list);
Joe Thornber633618e2013-11-09 11:12:51 +0000298 INIT_HLIST_NODE(&e->hlist);
299 ep->nr_allocated++;
300
301 return e;
302}
303
304static void free_entry(struct entry_pool *ep, struct entry *e)
305{
306 BUG_ON(!ep->nr_allocated);
307 ep->nr_allocated--;
308 INIT_HLIST_NODE(&e->hlist);
309 list_add(&e->list, &ep->free);
310}
311
Joe Thornber532906a2013-11-08 16:36:17 +0000312/*
313 * Returns NULL if the entry is free.
314 */
315static struct entry *epool_find(struct entry_pool *ep, dm_cblock_t cblock)
316{
317 struct entry *e = ep->entries + from_cblock(cblock);
Mike Snitzer7b6b2bc2013-11-12 12:17:43 -0500318 return !hlist_unhashed(&e->hlist) ? e : NULL;
Joe Thornber532906a2013-11-08 16:36:17 +0000319}
320
Joe Thornber633618e2013-11-09 11:12:51 +0000321static bool epool_empty(struct entry_pool *ep)
322{
323 return list_empty(&ep->free);
324}
325
326static bool in_pool(struct entry_pool *ep, struct entry *e)
327{
328 return e >= ep->entries && e < ep->entries_end;
329}
330
331static dm_cblock_t infer_cblock(struct entry_pool *ep, struct entry *e)
332{
333 return to_cblock(e - ep->entries);
334}
335
336/*----------------------------------------------------------------*/
337
Joe Thornberf2836352013-03-01 22:45:51 +0000338struct mq_policy {
339 struct dm_cache_policy policy;
340
341 /* protects everything */
342 struct mutex lock;
343 dm_cblock_t cache_size;
344 struct io_tracker tracker;
345
346 /*
Joe Thornber633618e2013-11-09 11:12:51 +0000347 * Entries come from two pools, one of pre-cache entries, and one
348 * for the cache proper.
349 */
350 struct entry_pool pre_cache_pool;
351 struct entry_pool cache_pool;
352
353 /*
Joe Thornber01911c12013-10-24 14:10:28 -0400354 * We maintain three queues of entries. The cache proper,
355 * consisting of a clean and dirty queue, contains the currently
356 * active mappings. Whereas the pre_cache tracks blocks that
357 * are being hit frequently and potential candidates for promotion
358 * to the cache.
Joe Thornberf2836352013-03-01 22:45:51 +0000359 */
360 struct queue pre_cache;
Joe Thornber01911c12013-10-24 14:10:28 -0400361 struct queue cache_clean;
362 struct queue cache_dirty;
Joe Thornberf2836352013-03-01 22:45:51 +0000363
364 /*
365 * Keeps track of time, incremented by the core. We use this to
366 * avoid attributing multiple hits within the same tick.
367 *
368 * Access to tick_protected should be done with the spin lock held.
369 * It's copied to tick at the start of the map function (within the
370 * mutex).
371 */
372 spinlock_t tick_lock;
373 unsigned tick_protected;
374 unsigned tick;
375
376 /*
377 * A count of the number of times the map function has been called
378 * and found an entry in the pre_cache or cache. Currently used to
379 * calculate the generation.
380 */
381 unsigned hit_count;
382
383 /*
384 * A generation is a longish period that is used to trigger some
385 * book keeping effects. eg, decrementing hit counts on entries.
386 * This is needed to allow the cache to evolve as io patterns
387 * change.
388 */
389 unsigned generation;
390 unsigned generation_period; /* in lookups (will probably change) */
391
Joe Thornber78e03d62013-12-09 12:53:05 +0000392 unsigned discard_promote_adjustment;
393 unsigned read_promote_adjustment;
394 unsigned write_promote_adjustment;
395
Joe Thornberf2836352013-03-01 22:45:51 +0000396 /*
Joe Thornberf2836352013-03-01 22:45:51 +0000397 * The hash table allows us to quickly find an entry by origin
398 * block. Both pre_cache and cache entries are in here.
399 */
400 unsigned nr_buckets;
401 dm_block_t hash_bits;
402 struct hlist_head *table;
403};
404
Joe Thornber78e03d62013-12-09 12:53:05 +0000405#define DEFAULT_DISCARD_PROMOTE_ADJUSTMENT 1
406#define DEFAULT_READ_PROMOTE_ADJUSTMENT 4
407#define DEFAULT_WRITE_PROMOTE_ADJUSTMENT 8
Joe Thornberb155aa02014-10-22 14:30:58 +0100408#define DISCOURAGE_DEMOTING_DIRTY_THRESHOLD 128
Joe Thornber78e03d62013-12-09 12:53:05 +0000409
Joe Thornberf2836352013-03-01 22:45:51 +0000410/*----------------------------------------------------------------*/
Joe Thornberf2836352013-03-01 22:45:51 +0000411
412/*
413 * Simple hash table implementation. Should replace with the standard hash
414 * table that's making its way upstream.
415 */
416static void hash_insert(struct mq_policy *mq, struct entry *e)
417{
418 unsigned h = hash_64(from_oblock(e->oblock), mq->hash_bits);
419
420 hlist_add_head(&e->hlist, mq->table + h);
421}
422
423static struct entry *hash_lookup(struct mq_policy *mq, dm_oblock_t oblock)
424{
425 unsigned h = hash_64(from_oblock(oblock), mq->hash_bits);
426 struct hlist_head *bucket = mq->table + h;
427 struct entry *e;
428
429 hlist_for_each_entry(e, bucket, hlist)
430 if (e->oblock == oblock) {
431 hlist_del(&e->hlist);
432 hlist_add_head(&e->hlist, bucket);
433 return e;
434 }
435
436 return NULL;
437}
438
439static void hash_remove(struct entry *e)
440{
441 hlist_del(&e->hlist);
442}
443
444/*----------------------------------------------------------------*/
445
Joe Thornberf2836352013-03-01 22:45:51 +0000446static bool any_free_cblocks(struct mq_policy *mq)
447{
Joe Thornber633618e2013-11-09 11:12:51 +0000448 return !epool_empty(&mq->cache_pool);
Joe Thornberf2836352013-03-01 22:45:51 +0000449}
450
Joe Thornberc86c3072013-10-24 14:10:28 -0400451static bool any_clean_cblocks(struct mq_policy *mq)
452{
453 return !queue_empty(&mq->cache_clean);
454}
455
Joe Thornberf2836352013-03-01 22:45:51 +0000456/*----------------------------------------------------------------*/
457
458/*
459 * Now we get to the meat of the policy. This section deals with deciding
460 * when to to add entries to the pre_cache and cache, and move between
461 * them.
462 */
463
464/*
465 * The queue level is based on the log2 of the hit count.
466 */
467static unsigned queue_level(struct entry *e)
468{
469 return min((unsigned) ilog2(e->hit_count), NR_QUEUE_LEVELS - 1u);
470}
471
Joe Thornber633618e2013-11-09 11:12:51 +0000472static bool in_cache(struct mq_policy *mq, struct entry *e)
473{
474 return in_pool(&mq->cache_pool, e);
475}
476
Joe Thornberf2836352013-03-01 22:45:51 +0000477/*
478 * Inserts the entry into the pre_cache or the cache. Ensures the cache
Joe Thornber633618e2013-11-09 11:12:51 +0000479 * block is marked as allocated if necc. Inserts into the hash table.
480 * Sets the tick which records when the entry was last moved about.
Joe Thornberf2836352013-03-01 22:45:51 +0000481 */
482static void push(struct mq_policy *mq, struct entry *e)
483{
484 e->tick = mq->tick;
485 hash_insert(mq, e);
486
Joe Thornber633618e2013-11-09 11:12:51 +0000487 if (in_cache(mq, e))
Joe Thornber01911c12013-10-24 14:10:28 -0400488 queue_push(e->dirty ? &mq->cache_dirty : &mq->cache_clean,
489 queue_level(e), &e->list);
Joe Thornber633618e2013-11-09 11:12:51 +0000490 else
Joe Thornberf2836352013-03-01 22:45:51 +0000491 queue_push(&mq->pre_cache, queue_level(e), &e->list);
492}
493
494/*
495 * Removes an entry from pre_cache or cache. Removes from the hash table.
Joe Thornberf2836352013-03-01 22:45:51 +0000496 */
497static void del(struct mq_policy *mq, struct entry *e)
498{
499 queue_remove(&e->list);
500 hash_remove(e);
Joe Thornberf2836352013-03-01 22:45:51 +0000501}
502
503/*
504 * Like del, except it removes the first entry in the queue (ie. the least
505 * recently used).
506 */
507static struct entry *pop(struct mq_policy *mq, struct queue *q)
508{
Joe Thornber0184b442013-10-24 14:10:28 -0400509 struct entry *e;
510 struct list_head *h = queue_pop(q);
Joe Thornberf2836352013-03-01 22:45:51 +0000511
Joe Thornber0184b442013-10-24 14:10:28 -0400512 if (!h)
513 return NULL;
Joe Thornberf2836352013-03-01 22:45:51 +0000514
Joe Thornber0184b442013-10-24 14:10:28 -0400515 e = container_of(h, struct entry, list);
516 hash_remove(e);
Joe Thornberf2836352013-03-01 22:45:51 +0000517
518 return e;
519}
520
Joe Thornberb155aa02014-10-22 14:30:58 +0100521static struct entry *peek(struct queue *q)
522{
523 struct list_head *h = queue_peek(q);
524 return h ? container_of(h, struct entry, list) : NULL;
525}
526
Joe Thornberf2836352013-03-01 22:45:51 +0000527/*
528 * Has this entry already been updated?
529 */
530static bool updated_this_tick(struct mq_policy *mq, struct entry *e)
531{
532 return mq->tick == e->tick;
533}
534
535/*
536 * The promotion threshold is adjusted every generation. As are the counts
537 * of the entries.
538 *
539 * At the moment the threshold is taken by averaging the hit counts of some
Joe Thornber01911c12013-10-24 14:10:28 -0400540 * of the entries in the cache (the first 20 entries across all levels in
541 * ascending order, giving preference to the clean entries at each level).
Joe Thornberf2836352013-03-01 22:45:51 +0000542 *
543 * We can be much cleverer than this though. For example, each promotion
544 * could bump up the threshold helping to prevent churn. Much more to do
545 * here.
546 */
547
548#define MAX_TO_AVERAGE 20
549
550static void check_generation(struct mq_policy *mq)
551{
552 unsigned total = 0, nr = 0, count = 0, level;
553 struct list_head *head;
554 struct entry *e;
555
Joe Thornber633618e2013-11-09 11:12:51 +0000556 if ((mq->hit_count >= mq->generation_period) && (epool_empty(&mq->cache_pool))) {
Joe Thornberf2836352013-03-01 22:45:51 +0000557 mq->hit_count = 0;
558 mq->generation++;
559
560 for (level = 0; level < NR_QUEUE_LEVELS && count < MAX_TO_AVERAGE; level++) {
Joe Thornber01911c12013-10-24 14:10:28 -0400561 head = mq->cache_clean.qs + level;
562 list_for_each_entry(e, head, list) {
563 nr++;
564 total += e->hit_count;
565
566 if (++count >= MAX_TO_AVERAGE)
567 break;
568 }
569
570 head = mq->cache_dirty.qs + level;
Joe Thornberf2836352013-03-01 22:45:51 +0000571 list_for_each_entry(e, head, list) {
572 nr++;
573 total += e->hit_count;
574
575 if (++count >= MAX_TO_AVERAGE)
576 break;
577 }
578 }
Joe Thornberf2836352013-03-01 22:45:51 +0000579 }
580}
581
582/*
583 * Whenever we use an entry we bump up it's hit counter, and push it to the
584 * back to it's current level.
585 */
586static void requeue_and_update_tick(struct mq_policy *mq, struct entry *e)
587{
588 if (updated_this_tick(mq, e))
589 return;
590
591 e->hit_count++;
592 mq->hit_count++;
593 check_generation(mq);
594
595 /* generation adjustment, to stop the counts increasing forever. */
596 /* FIXME: divide? */
597 /* e->hit_count -= min(e->hit_count - 1, mq->generation - e->generation); */
598 e->generation = mq->generation;
599
600 del(mq, e);
601 push(mq, e);
602}
603
604/*
605 * Demote the least recently used entry from the cache to the pre_cache.
606 * Returns the new cache entry to use, and the old origin block it was
607 * mapped to.
608 *
609 * We drop the hit count on the demoted entry back to 1 to stop it bouncing
610 * straight back into the cache if it's subsequently hit. There are
611 * various options here, and more experimentation would be good:
612 *
613 * - just forget about the demoted entry completely (ie. don't insert it
614 into the pre_cache).
615 * - divide the hit count rather that setting to some hard coded value.
616 * - set the hit count to a hard coded value other than 1, eg, is it better
617 * if it goes in at level 2?
618 */
Joe Thornber633618e2013-11-09 11:12:51 +0000619static int demote_cblock(struct mq_policy *mq, dm_oblock_t *oblock)
Joe Thornberf2836352013-03-01 22:45:51 +0000620{
Joe Thornber01911c12013-10-24 14:10:28 -0400621 struct entry *demoted = pop(mq, &mq->cache_clean);
Joe Thornberf2836352013-03-01 22:45:51 +0000622
Joe Thornber01911c12013-10-24 14:10:28 -0400623 if (!demoted)
624 /*
625 * We could get a block from mq->cache_dirty, but that
626 * would add extra latency to the triggering bio as it
627 * waits for the writeback. Better to not promote this
628 * time and hope there's a clean block next time this block
629 * is hit.
630 */
631 return -ENOSPC;
632
Joe Thornberf2836352013-03-01 22:45:51 +0000633 *oblock = demoted->oblock;
Joe Thornber633618e2013-11-09 11:12:51 +0000634 free_entry(&mq->cache_pool, demoted);
635
636 /*
637 * We used to put the demoted block into the pre-cache, but I think
638 * it's simpler to just let it work it's way up from zero again.
639 * Stops blocks flickering in and out of the cache.
640 */
Joe Thornberf2836352013-03-01 22:45:51 +0000641
Joe Thornber01911c12013-10-24 14:10:28 -0400642 return 0;
Joe Thornberf2836352013-03-01 22:45:51 +0000643}
644
645/*
Joe Thornberb155aa02014-10-22 14:30:58 +0100646 * Entries in the pre_cache whose hit count passes the promotion
647 * threshold move to the cache proper. Working out the correct
648 * value for the promotion_threshold is crucial to this policy.
649 */
650static unsigned promote_threshold(struct mq_policy *mq)
651{
652 struct entry *e;
653
654 if (any_free_cblocks(mq))
655 return 0;
656
657 e = peek(&mq->cache_clean);
658 if (e)
659 return e->hit_count;
660
661 e = peek(&mq->cache_dirty);
662 if (e)
663 return e->hit_count + DISCOURAGE_DEMOTING_DIRTY_THRESHOLD;
664
665 /* This should never happen */
666 return 0;
667}
668
669/*
Joe Thornberf2836352013-03-01 22:45:51 +0000670 * We modify the basic promotion_threshold depending on the specific io.
671 *
672 * If the origin block has been discarded then there's no cost to copy it
673 * to the cache.
674 *
675 * We bias towards reads, since they can be demoted at no cost if they
676 * haven't been dirtied.
677 */
Joe Thornberf2836352013-03-01 22:45:51 +0000678static unsigned adjusted_promote_threshold(struct mq_policy *mq,
679 bool discarded_oblock, int data_dir)
680{
Joe Thornberc86c3072013-10-24 14:10:28 -0400681 if (data_dir == READ)
Joe Thornberb155aa02014-10-22 14:30:58 +0100682 return promote_threshold(mq) + mq->read_promote_adjustment;
Joe Thornberc86c3072013-10-24 14:10:28 -0400683
684 if (discarded_oblock && (any_free_cblocks(mq) || any_clean_cblocks(mq))) {
Joe Thornberf2836352013-03-01 22:45:51 +0000685 /*
686 * We don't need to do any copying at all, so give this a
Joe Thornberc86c3072013-10-24 14:10:28 -0400687 * very low threshold.
Joe Thornberf2836352013-03-01 22:45:51 +0000688 */
Joe Thornber78e03d62013-12-09 12:53:05 +0000689 return mq->discard_promote_adjustment;
Joe Thornberc86c3072013-10-24 14:10:28 -0400690 }
Joe Thornberf2836352013-03-01 22:45:51 +0000691
Joe Thornberb155aa02014-10-22 14:30:58 +0100692 return promote_threshold(mq) + mq->write_promote_adjustment;
Joe Thornberf2836352013-03-01 22:45:51 +0000693}
694
695static bool should_promote(struct mq_policy *mq, struct entry *e,
696 bool discarded_oblock, int data_dir)
697{
698 return e->hit_count >=
699 adjusted_promote_threshold(mq, discarded_oblock, data_dir);
700}
701
702static int cache_entry_found(struct mq_policy *mq,
703 struct entry *e,
704 struct policy_result *result)
705{
706 requeue_and_update_tick(mq, e);
707
Joe Thornber633618e2013-11-09 11:12:51 +0000708 if (in_cache(mq, e)) {
Joe Thornberf2836352013-03-01 22:45:51 +0000709 result->op = POLICY_HIT;
Joe Thornber633618e2013-11-09 11:12:51 +0000710 result->cblock = infer_cblock(&mq->cache_pool, e);
Joe Thornberf2836352013-03-01 22:45:51 +0000711 }
712
713 return 0;
714}
715
716/*
Joe Thornber0184b442013-10-24 14:10:28 -0400717 * Moves an entry from the pre_cache to the cache. The main work is
Joe Thornberf2836352013-03-01 22:45:51 +0000718 * finding which cache block to use.
719 */
720static int pre_cache_to_cache(struct mq_policy *mq, struct entry *e,
721 struct policy_result *result)
722{
Joe Thornber01911c12013-10-24 14:10:28 -0400723 int r;
Joe Thornber633618e2013-11-09 11:12:51 +0000724 struct entry *new_e;
Joe Thornberf2836352013-03-01 22:45:51 +0000725
Joe Thornber633618e2013-11-09 11:12:51 +0000726 /* Ensure there's a free cblock in the cache */
727 if (epool_empty(&mq->cache_pool)) {
Joe Thornberf2836352013-03-01 22:45:51 +0000728 result->op = POLICY_REPLACE;
Joe Thornber633618e2013-11-09 11:12:51 +0000729 r = demote_cblock(mq, &result->old_oblock);
Joe Thornber01911c12013-10-24 14:10:28 -0400730 if (r) {
731 result->op = POLICY_MISS;
732 return 0;
733 }
Joe Thornberf2836352013-03-01 22:45:51 +0000734 } else
735 result->op = POLICY_NEW;
736
Joe Thornber633618e2013-11-09 11:12:51 +0000737 new_e = alloc_entry(&mq->cache_pool);
738 BUG_ON(!new_e);
739
740 new_e->oblock = e->oblock;
741 new_e->dirty = false;
742 new_e->hit_count = e->hit_count;
743 new_e->generation = e->generation;
744 new_e->tick = e->tick;
Joe Thornberf2836352013-03-01 22:45:51 +0000745
746 del(mq, e);
Joe Thornber633618e2013-11-09 11:12:51 +0000747 free_entry(&mq->pre_cache_pool, e);
748 push(mq, new_e);
749
750 result->cblock = infer_cblock(&mq->cache_pool, new_e);
Joe Thornberf2836352013-03-01 22:45:51 +0000751
752 return 0;
753}
754
755static int pre_cache_entry_found(struct mq_policy *mq, struct entry *e,
756 bool can_migrate, bool discarded_oblock,
757 int data_dir, struct policy_result *result)
758{
759 int r = 0;
760 bool updated = updated_this_tick(mq, e);
761
Joe Thornberf2836352013-03-01 22:45:51 +0000762 if ((!discarded_oblock && updated) ||
Joe Thornberaf95e7a2013-11-15 10:51:20 +0000763 !should_promote(mq, e, discarded_oblock, data_dir)) {
764 requeue_and_update_tick(mq, e);
Joe Thornberf2836352013-03-01 22:45:51 +0000765 result->op = POLICY_MISS;
Joe Thornberaf95e7a2013-11-15 10:51:20 +0000766
767 } else if (!can_migrate)
Joe Thornberf2836352013-03-01 22:45:51 +0000768 r = -EWOULDBLOCK;
Joe Thornberaf95e7a2013-11-15 10:51:20 +0000769
770 else {
771 requeue_and_update_tick(mq, e);
Joe Thornberf2836352013-03-01 22:45:51 +0000772 r = pre_cache_to_cache(mq, e, result);
Joe Thornberaf95e7a2013-11-15 10:51:20 +0000773 }
Joe Thornberf2836352013-03-01 22:45:51 +0000774
775 return r;
776}
777
778static void insert_in_pre_cache(struct mq_policy *mq,
779 dm_oblock_t oblock)
780{
Joe Thornber633618e2013-11-09 11:12:51 +0000781 struct entry *e = alloc_entry(&mq->pre_cache_pool);
Joe Thornberf2836352013-03-01 22:45:51 +0000782
783 if (!e)
784 /*
785 * There's no spare entry structure, so we grab the least
786 * used one from the pre_cache.
787 */
788 e = pop(mq, &mq->pre_cache);
789
790 if (unlikely(!e)) {
791 DMWARN("couldn't pop from pre cache");
792 return;
793 }
794
Joe Thornber633618e2013-11-09 11:12:51 +0000795 e->dirty = false;
796 e->oblock = oblock;
797 e->hit_count = 1;
798 e->generation = mq->generation;
799 push(mq, e);
Joe Thornberf2836352013-03-01 22:45:51 +0000800}
801
802static void insert_in_cache(struct mq_policy *mq, dm_oblock_t oblock,
803 struct policy_result *result)
804{
Joe Thornberc86c3072013-10-24 14:10:28 -0400805 int r;
Joe Thornberf2836352013-03-01 22:45:51 +0000806 struct entry *e;
Joe Thornberf2836352013-03-01 22:45:51 +0000807
Joe Thornber633618e2013-11-09 11:12:51 +0000808 if (epool_empty(&mq->cache_pool)) {
809 result->op = POLICY_REPLACE;
810 r = demote_cblock(mq, &result->old_oblock);
Joe Thornberc86c3072013-10-24 14:10:28 -0400811 if (unlikely(r)) {
812 result->op = POLICY_MISS;
813 insert_in_pre_cache(mq, oblock);
814 return;
815 }
Joe Thornberf2836352013-03-01 22:45:51 +0000816
Joe Thornberc86c3072013-10-24 14:10:28 -0400817 /*
818 * This will always succeed, since we've just demoted.
819 */
Joe Thornber633618e2013-11-09 11:12:51 +0000820 e = alloc_entry(&mq->cache_pool);
821 BUG_ON(!e);
Joe Thornberc86c3072013-10-24 14:10:28 -0400822
823 } else {
Joe Thornber633618e2013-11-09 11:12:51 +0000824 e = alloc_entry(&mq->cache_pool);
Joe Thornberc86c3072013-10-24 14:10:28 -0400825 result->op = POLICY_NEW;
Joe Thornberf2836352013-03-01 22:45:51 +0000826 }
827
828 e->oblock = oblock;
Joe Thornber01911c12013-10-24 14:10:28 -0400829 e->dirty = false;
Joe Thornberf2836352013-03-01 22:45:51 +0000830 e->hit_count = 1;
831 e->generation = mq->generation;
832 push(mq, e);
833
Joe Thornber633618e2013-11-09 11:12:51 +0000834 result->cblock = infer_cblock(&mq->cache_pool, e);
Joe Thornberf2836352013-03-01 22:45:51 +0000835}
836
837static int no_entry_found(struct mq_policy *mq, dm_oblock_t oblock,
838 bool can_migrate, bool discarded_oblock,
839 int data_dir, struct policy_result *result)
840{
Joe Thornber78e03d62013-12-09 12:53:05 +0000841 if (adjusted_promote_threshold(mq, discarded_oblock, data_dir) <= 1) {
Joe Thornberf2836352013-03-01 22:45:51 +0000842 if (can_migrate)
843 insert_in_cache(mq, oblock, result);
844 else
845 return -EWOULDBLOCK;
846 } else {
847 insert_in_pre_cache(mq, oblock);
848 result->op = POLICY_MISS;
849 }
850
851 return 0;
852}
853
854/*
855 * Looks the oblock up in the hash table, then decides whether to put in
856 * pre_cache, or cache etc.
857 */
858static int map(struct mq_policy *mq, dm_oblock_t oblock,
859 bool can_migrate, bool discarded_oblock,
860 int data_dir, struct policy_result *result)
861{
862 int r = 0;
863 struct entry *e = hash_lookup(mq, oblock);
864
Joe Thornber633618e2013-11-09 11:12:51 +0000865 if (e && in_cache(mq, e))
Joe Thornberf2836352013-03-01 22:45:51 +0000866 r = cache_entry_found(mq, e, result);
Joe Thornber633618e2013-11-09 11:12:51 +0000867
Mike Snitzerf1afb362014-10-30 10:02:01 -0400868 else if (mq->tracker.thresholds[PATTERN_SEQUENTIAL] &&
869 iot_pattern(&mq->tracker) == PATTERN_SEQUENTIAL)
Joe Thornberf2836352013-03-01 22:45:51 +0000870 result->op = POLICY_MISS;
Joe Thornber633618e2013-11-09 11:12:51 +0000871
Joe Thornberf2836352013-03-01 22:45:51 +0000872 else if (e)
873 r = pre_cache_entry_found(mq, e, can_migrate, discarded_oblock,
874 data_dir, result);
Joe Thornber633618e2013-11-09 11:12:51 +0000875
Joe Thornberf2836352013-03-01 22:45:51 +0000876 else
877 r = no_entry_found(mq, oblock, can_migrate, discarded_oblock,
878 data_dir, result);
879
880 if (r == -EWOULDBLOCK)
881 result->op = POLICY_MISS;
882
883 return r;
884}
885
886/*----------------------------------------------------------------*/
887
888/*
889 * Public interface, via the policy struct. See dm-cache-policy.h for a
890 * description of these.
891 */
892
893static struct mq_policy *to_mq_policy(struct dm_cache_policy *p)
894{
895 return container_of(p, struct mq_policy, policy);
896}
897
898static void mq_destroy(struct dm_cache_policy *p)
899{
900 struct mq_policy *mq = to_mq_policy(p);
901
Heinz Mauelshagen14f398c2014-02-28 12:02:56 -0500902 vfree(mq->table);
Joe Thornber633618e2013-11-09 11:12:51 +0000903 epool_exit(&mq->cache_pool);
904 epool_exit(&mq->pre_cache_pool);
Joe Thornberf2836352013-03-01 22:45:51 +0000905 kfree(mq);
906}
907
908static void copy_tick(struct mq_policy *mq)
909{
910 unsigned long flags;
911
912 spin_lock_irqsave(&mq->tick_lock, flags);
913 mq->tick = mq->tick_protected;
914 spin_unlock_irqrestore(&mq->tick_lock, flags);
915}
916
917static int mq_map(struct dm_cache_policy *p, dm_oblock_t oblock,
918 bool can_block, bool can_migrate, bool discarded_oblock,
919 struct bio *bio, struct policy_result *result)
920{
921 int r;
922 struct mq_policy *mq = to_mq_policy(p);
923
924 result->op = POLICY_MISS;
925
926 if (can_block)
927 mutex_lock(&mq->lock);
928 else if (!mutex_trylock(&mq->lock))
929 return -EWOULDBLOCK;
930
931 copy_tick(mq);
932
933 iot_examine_bio(&mq->tracker, bio);
934 r = map(mq, oblock, can_migrate, discarded_oblock,
935 bio_data_dir(bio), result);
936
937 mutex_unlock(&mq->lock);
938
939 return r;
940}
941
942static int mq_lookup(struct dm_cache_policy *p, dm_oblock_t oblock, dm_cblock_t *cblock)
943{
944 int r;
945 struct mq_policy *mq = to_mq_policy(p);
946 struct entry *e;
947
948 if (!mutex_trylock(&mq->lock))
949 return -EWOULDBLOCK;
950
951 e = hash_lookup(mq, oblock);
Joe Thornber633618e2013-11-09 11:12:51 +0000952 if (e && in_cache(mq, e)) {
953 *cblock = infer_cblock(&mq->cache_pool, e);
Joe Thornberf2836352013-03-01 22:45:51 +0000954 r = 0;
955 } else
956 r = -ENOENT;
957
958 mutex_unlock(&mq->lock);
959
960 return r;
961}
962
Joe Thornber633618e2013-11-09 11:12:51 +0000963static void __mq_set_clear_dirty(struct mq_policy *mq, dm_oblock_t oblock, bool set)
Joe Thornber01911c12013-10-24 14:10:28 -0400964{
Joe Thornber01911c12013-10-24 14:10:28 -0400965 struct entry *e;
966
Joe Thornber01911c12013-10-24 14:10:28 -0400967 e = hash_lookup(mq, oblock);
Joe Thornber633618e2013-11-09 11:12:51 +0000968 BUG_ON(!e || !in_cache(mq, e));
Joe Thornber01911c12013-10-24 14:10:28 -0400969
Joe Thornber633618e2013-11-09 11:12:51 +0000970 del(mq, e);
971 e->dirty = set;
972 push(mq, e);
Joe Thornber01911c12013-10-24 14:10:28 -0400973}
974
975static void mq_set_dirty(struct dm_cache_policy *p, dm_oblock_t oblock)
976{
Joe Thornber633618e2013-11-09 11:12:51 +0000977 struct mq_policy *mq = to_mq_policy(p);
978
979 mutex_lock(&mq->lock);
980 __mq_set_clear_dirty(mq, oblock, true);
981 mutex_unlock(&mq->lock);
Joe Thornber01911c12013-10-24 14:10:28 -0400982}
983
984static void mq_clear_dirty(struct dm_cache_policy *p, dm_oblock_t oblock)
985{
Joe Thornber633618e2013-11-09 11:12:51 +0000986 struct mq_policy *mq = to_mq_policy(p);
987
988 mutex_lock(&mq->lock);
989 __mq_set_clear_dirty(mq, oblock, false);
990 mutex_unlock(&mq->lock);
Joe Thornber01911c12013-10-24 14:10:28 -0400991}
992
Joe Thornberf2836352013-03-01 22:45:51 +0000993static int mq_load_mapping(struct dm_cache_policy *p,
994 dm_oblock_t oblock, dm_cblock_t cblock,
995 uint32_t hint, bool hint_valid)
996{
997 struct mq_policy *mq = to_mq_policy(p);
998 struct entry *e;
999
Joe Thornber633618e2013-11-09 11:12:51 +00001000 e = alloc_particular_entry(&mq->cache_pool, cblock);
Joe Thornberf2836352013-03-01 22:45:51 +00001001 e->oblock = oblock;
Joe Thornber01911c12013-10-24 14:10:28 -04001002 e->dirty = false; /* this gets corrected in a minute */
Joe Thornberf2836352013-03-01 22:45:51 +00001003 e->hit_count = hint_valid ? hint : 1;
1004 e->generation = mq->generation;
1005 push(mq, e);
1006
1007 return 0;
1008}
1009
Joe Thornber633618e2013-11-09 11:12:51 +00001010static int mq_save_hints(struct mq_policy *mq, struct queue *q,
1011 policy_walk_fn fn, void *context)
1012{
1013 int r;
1014 unsigned level;
1015 struct entry *e;
1016
1017 for (level = 0; level < NR_QUEUE_LEVELS; level++)
1018 list_for_each_entry(e, q->qs + level, list) {
1019 r = fn(context, infer_cblock(&mq->cache_pool, e),
1020 e->oblock, e->hit_count);
1021 if (r)
1022 return r;
1023 }
1024
1025 return 0;
1026}
1027
Joe Thornberf2836352013-03-01 22:45:51 +00001028static int mq_walk_mappings(struct dm_cache_policy *p, policy_walk_fn fn,
1029 void *context)
1030{
1031 struct mq_policy *mq = to_mq_policy(p);
1032 int r = 0;
Joe Thornberf2836352013-03-01 22:45:51 +00001033
1034 mutex_lock(&mq->lock);
1035
Joe Thornber633618e2013-11-09 11:12:51 +00001036 r = mq_save_hints(mq, &mq->cache_clean, fn, context);
1037 if (!r)
1038 r = mq_save_hints(mq, &mq->cache_dirty, fn, context);
Joe Thornber01911c12013-10-24 14:10:28 -04001039
Joe Thornberf2836352013-03-01 22:45:51 +00001040 mutex_unlock(&mq->lock);
1041
1042 return r;
1043}
1044
Joe Thornber633618e2013-11-09 11:12:51 +00001045static void __remove_mapping(struct mq_policy *mq, dm_oblock_t oblock)
1046{
1047 struct entry *e;
1048
1049 e = hash_lookup(mq, oblock);
1050 BUG_ON(!e || !in_cache(mq, e));
1051
1052 del(mq, e);
1053 free_entry(&mq->cache_pool, e);
1054}
1055
Geert Uytterhoevenb936bf82013-07-26 09:57:31 +02001056static void mq_remove_mapping(struct dm_cache_policy *p, dm_oblock_t oblock)
Joe Thornberf2836352013-03-01 22:45:51 +00001057{
Geert Uytterhoevenb936bf82013-07-26 09:57:31 +02001058 struct mq_policy *mq = to_mq_policy(p);
Geert Uytterhoevenb936bf82013-07-26 09:57:31 +02001059
1060 mutex_lock(&mq->lock);
Joe Thornber633618e2013-11-09 11:12:51 +00001061 __remove_mapping(mq, oblock);
Joe Thornberf2836352013-03-01 22:45:51 +00001062 mutex_unlock(&mq->lock);
1063}
1064
Joe Thornber532906a2013-11-08 16:36:17 +00001065static int __remove_cblock(struct mq_policy *mq, dm_cblock_t cblock)
1066{
1067 struct entry *e = epool_find(&mq->cache_pool, cblock);
1068
1069 if (!e)
1070 return -ENODATA;
1071
1072 del(mq, e);
1073 free_entry(&mq->cache_pool, e);
1074
1075 return 0;
1076}
1077
1078static int mq_remove_cblock(struct dm_cache_policy *p, dm_cblock_t cblock)
1079{
1080 int r;
1081 struct mq_policy *mq = to_mq_policy(p);
1082
1083 mutex_lock(&mq->lock);
1084 r = __remove_cblock(mq, cblock);
1085 mutex_unlock(&mq->lock);
1086
1087 return r;
1088}
1089
Joe Thornber01911c12013-10-24 14:10:28 -04001090static int __mq_writeback_work(struct mq_policy *mq, dm_oblock_t *oblock,
1091 dm_cblock_t *cblock)
1092{
1093 struct entry *e = pop(mq, &mq->cache_dirty);
1094
1095 if (!e)
1096 return -ENODATA;
1097
1098 *oblock = e->oblock;
Joe Thornber633618e2013-11-09 11:12:51 +00001099 *cblock = infer_cblock(&mq->cache_pool, e);
Joe Thornber01911c12013-10-24 14:10:28 -04001100 e->dirty = false;
1101 push(mq, e);
1102
1103 return 0;
1104}
1105
1106static int mq_writeback_work(struct dm_cache_policy *p, dm_oblock_t *oblock,
1107 dm_cblock_t *cblock)
1108{
1109 int r;
1110 struct mq_policy *mq = to_mq_policy(p);
1111
1112 mutex_lock(&mq->lock);
1113 r = __mq_writeback_work(mq, oblock, cblock);
1114 mutex_unlock(&mq->lock);
1115
1116 return r;
1117}
1118
Joe Thornber633618e2013-11-09 11:12:51 +00001119static void __force_mapping(struct mq_policy *mq,
1120 dm_oblock_t current_oblock, dm_oblock_t new_oblock)
Joe Thornberf2836352013-03-01 22:45:51 +00001121{
1122 struct entry *e = hash_lookup(mq, current_oblock);
1123
Joe Thornber633618e2013-11-09 11:12:51 +00001124 if (e && in_cache(mq, e)) {
1125 del(mq, e);
1126 e->oblock = new_oblock;
1127 e->dirty = true;
1128 push(mq, e);
1129 }
Joe Thornberf2836352013-03-01 22:45:51 +00001130}
1131
1132static void mq_force_mapping(struct dm_cache_policy *p,
1133 dm_oblock_t current_oblock, dm_oblock_t new_oblock)
1134{
1135 struct mq_policy *mq = to_mq_policy(p);
1136
1137 mutex_lock(&mq->lock);
Joe Thornber633618e2013-11-09 11:12:51 +00001138 __force_mapping(mq, current_oblock, new_oblock);
Joe Thornberf2836352013-03-01 22:45:51 +00001139 mutex_unlock(&mq->lock);
1140}
1141
1142static dm_cblock_t mq_residency(struct dm_cache_policy *p)
1143{
Joe Thornber99ba2ae2013-10-21 11:44:57 +01001144 dm_cblock_t r;
Joe Thornberf2836352013-03-01 22:45:51 +00001145 struct mq_policy *mq = to_mq_policy(p);
1146
Joe Thornber99ba2ae2013-10-21 11:44:57 +01001147 mutex_lock(&mq->lock);
Joe Thornber633618e2013-11-09 11:12:51 +00001148 r = to_cblock(mq->cache_pool.nr_allocated);
Joe Thornber99ba2ae2013-10-21 11:44:57 +01001149 mutex_unlock(&mq->lock);
1150
1151 return r;
Joe Thornberf2836352013-03-01 22:45:51 +00001152}
1153
1154static void mq_tick(struct dm_cache_policy *p)
1155{
1156 struct mq_policy *mq = to_mq_policy(p);
1157 unsigned long flags;
1158
1159 spin_lock_irqsave(&mq->tick_lock, flags);
1160 mq->tick_protected++;
1161 spin_unlock_irqrestore(&mq->tick_lock, flags);
1162}
1163
1164static int mq_set_config_value(struct dm_cache_policy *p,
1165 const char *key, const char *value)
1166{
1167 struct mq_policy *mq = to_mq_policy(p);
Joe Thornberf2836352013-03-01 22:45:51 +00001168 unsigned long tmp;
1169
Joe Thornberf2836352013-03-01 22:45:51 +00001170 if (kstrtoul(value, 10, &tmp))
1171 return -EINVAL;
1172
Joe Thornber78e03d62013-12-09 12:53:05 +00001173 if (!strcasecmp(key, "random_threshold")) {
1174 mq->tracker.thresholds[PATTERN_RANDOM] = tmp;
1175
1176 } else if (!strcasecmp(key, "sequential_threshold")) {
1177 mq->tracker.thresholds[PATTERN_SEQUENTIAL] = tmp;
1178
1179 } else if (!strcasecmp(key, "discard_promote_adjustment"))
1180 mq->discard_promote_adjustment = tmp;
1181
1182 else if (!strcasecmp(key, "read_promote_adjustment"))
1183 mq->read_promote_adjustment = tmp;
1184
1185 else if (!strcasecmp(key, "write_promote_adjustment"))
1186 mq->write_promote_adjustment = tmp;
1187
1188 else
1189 return -EINVAL;
Joe Thornberf2836352013-03-01 22:45:51 +00001190
1191 return 0;
1192}
1193
1194static int mq_emit_config_values(struct dm_cache_policy *p, char *result, unsigned maxlen)
1195{
1196 ssize_t sz = 0;
1197 struct mq_policy *mq = to_mq_policy(p);
1198
Joe Thornber78e03d62013-12-09 12:53:05 +00001199 DMEMIT("10 random_threshold %u "
1200 "sequential_threshold %u "
1201 "discard_promote_adjustment %u "
1202 "read_promote_adjustment %u "
1203 "write_promote_adjustment %u",
Joe Thornberf2836352013-03-01 22:45:51 +00001204 mq->tracker.thresholds[PATTERN_RANDOM],
Joe Thornber78e03d62013-12-09 12:53:05 +00001205 mq->tracker.thresholds[PATTERN_SEQUENTIAL],
1206 mq->discard_promote_adjustment,
1207 mq->read_promote_adjustment,
1208 mq->write_promote_adjustment);
Joe Thornberf2836352013-03-01 22:45:51 +00001209
1210 return 0;
1211}
1212
1213/* Init the policy plugin interface function pointers. */
1214static void init_policy_functions(struct mq_policy *mq)
1215{
1216 mq->policy.destroy = mq_destroy;
1217 mq->policy.map = mq_map;
1218 mq->policy.lookup = mq_lookup;
Joe Thornber01911c12013-10-24 14:10:28 -04001219 mq->policy.set_dirty = mq_set_dirty;
1220 mq->policy.clear_dirty = mq_clear_dirty;
Joe Thornberf2836352013-03-01 22:45:51 +00001221 mq->policy.load_mapping = mq_load_mapping;
1222 mq->policy.walk_mappings = mq_walk_mappings;
1223 mq->policy.remove_mapping = mq_remove_mapping;
Joe Thornber532906a2013-11-08 16:36:17 +00001224 mq->policy.remove_cblock = mq_remove_cblock;
Joe Thornber01911c12013-10-24 14:10:28 -04001225 mq->policy.writeback_work = mq_writeback_work;
Joe Thornberf2836352013-03-01 22:45:51 +00001226 mq->policy.force_mapping = mq_force_mapping;
1227 mq->policy.residency = mq_residency;
1228 mq->policy.tick = mq_tick;
1229 mq->policy.emit_config_values = mq_emit_config_values;
1230 mq->policy.set_config_value = mq_set_config_value;
1231}
1232
1233static struct dm_cache_policy *mq_create(dm_cblock_t cache_size,
1234 sector_t origin_size,
1235 sector_t cache_block_size)
1236{
Joe Thornberf2836352013-03-01 22:45:51 +00001237 struct mq_policy *mq = kzalloc(sizeof(*mq), GFP_KERNEL);
1238
1239 if (!mq)
1240 return NULL;
1241
1242 init_policy_functions(mq);
1243 iot_init(&mq->tracker, SEQUENTIAL_THRESHOLD_DEFAULT, RANDOM_THRESHOLD_DEFAULT);
Joe Thornberf2836352013-03-01 22:45:51 +00001244 mq->cache_size = cache_size;
Joe Thornber633618e2013-11-09 11:12:51 +00001245
1246 if (epool_init(&mq->pre_cache_pool, from_cblock(cache_size))) {
1247 DMERR("couldn't initialize pool of pre-cache entries");
1248 goto bad_pre_cache_init;
1249 }
1250
1251 if (epool_init(&mq->cache_pool, from_cblock(cache_size))) {
1252 DMERR("couldn't initialize pool of cache entries");
1253 goto bad_cache_init;
1254 }
1255
Joe Thornberf2836352013-03-01 22:45:51 +00001256 mq->tick_protected = 0;
1257 mq->tick = 0;
1258 mq->hit_count = 0;
1259 mq->generation = 0;
Joe Thornber78e03d62013-12-09 12:53:05 +00001260 mq->discard_promote_adjustment = DEFAULT_DISCARD_PROMOTE_ADJUSTMENT;
1261 mq->read_promote_adjustment = DEFAULT_READ_PROMOTE_ADJUSTMENT;
1262 mq->write_promote_adjustment = DEFAULT_WRITE_PROMOTE_ADJUSTMENT;
Joe Thornberf2836352013-03-01 22:45:51 +00001263 mutex_init(&mq->lock);
1264 spin_lock_init(&mq->tick_lock);
Joe Thornberf2836352013-03-01 22:45:51 +00001265
1266 queue_init(&mq->pre_cache);
Joe Thornber01911c12013-10-24 14:10:28 -04001267 queue_init(&mq->cache_clean);
1268 queue_init(&mq->cache_dirty);
1269
Joe Thornberf2836352013-03-01 22:45:51 +00001270 mq->generation_period = max((unsigned) from_cblock(cache_size), 1024U);
1271
Joe Thornberf2836352013-03-01 22:45:51 +00001272 mq->nr_buckets = next_power(from_cblock(cache_size) / 2, 16);
1273 mq->hash_bits = ffs(mq->nr_buckets) - 1;
Heinz Mauelshagen14f398c2014-02-28 12:02:56 -05001274 mq->table = vzalloc(sizeof(*mq->table) * mq->nr_buckets);
Joe Thornberf2836352013-03-01 22:45:51 +00001275 if (!mq->table)
1276 goto bad_alloc_table;
1277
Joe Thornberf2836352013-03-01 22:45:51 +00001278 return &mq->policy;
1279
Joe Thornberf2836352013-03-01 22:45:51 +00001280bad_alloc_table:
Joe Thornber633618e2013-11-09 11:12:51 +00001281 epool_exit(&mq->cache_pool);
1282bad_cache_init:
1283 epool_exit(&mq->pre_cache_pool);
1284bad_pre_cache_init:
Joe Thornberf2836352013-03-01 22:45:51 +00001285 kfree(mq);
1286
1287 return NULL;
1288}
1289
1290/*----------------------------------------------------------------*/
1291
1292static struct dm_cache_policy_type mq_policy_type = {
1293 .name = "mq",
Mike Snitzerf1afb362014-10-30 10:02:01 -04001294 .version = {1, 3, 0},
Joe Thornberf2836352013-03-01 22:45:51 +00001295 .hint_size = 4,
1296 .owner = THIS_MODULE,
1297 .create = mq_create
1298};
1299
1300static struct dm_cache_policy_type default_policy_type = {
1301 .name = "default",
Mike Snitzerf1afb362014-10-30 10:02:01 -04001302 .version = {1, 3, 0},
Joe Thornberf2836352013-03-01 22:45:51 +00001303 .hint_size = 4,
1304 .owner = THIS_MODULE,
Mike Snitzer2e68c4e2014-01-15 21:06:55 -05001305 .create = mq_create,
1306 .real = &mq_policy_type
Joe Thornberf2836352013-03-01 22:45:51 +00001307};
1308
1309static int __init mq_init(void)
1310{
1311 int r;
1312
1313 mq_entry_cache = kmem_cache_create("dm_mq_policy_cache_entry",
1314 sizeof(struct entry),
1315 __alignof__(struct entry),
1316 0, NULL);
1317 if (!mq_entry_cache)
1318 goto bad;
1319
1320 r = dm_cache_policy_register(&mq_policy_type);
1321 if (r) {
1322 DMERR("register failed %d", r);
1323 goto bad_register_mq;
1324 }
1325
1326 r = dm_cache_policy_register(&default_policy_type);
1327 if (!r) {
Mike Snitzer4e7f5062013-03-20 17:21:27 +00001328 DMINFO("version %u.%u.%u loaded",
1329 mq_policy_type.version[0],
1330 mq_policy_type.version[1],
1331 mq_policy_type.version[2]);
Joe Thornberf2836352013-03-01 22:45:51 +00001332 return 0;
1333 }
1334
1335 DMERR("register failed (as default) %d", r);
1336
1337 dm_cache_policy_unregister(&mq_policy_type);
1338bad_register_mq:
1339 kmem_cache_destroy(mq_entry_cache);
1340bad:
1341 return -ENOMEM;
1342}
1343
1344static void __exit mq_exit(void)
1345{
1346 dm_cache_policy_unregister(&mq_policy_type);
1347 dm_cache_policy_unregister(&default_policy_type);
1348
1349 kmem_cache_destroy(mq_entry_cache);
1350}
1351
1352module_init(mq_init);
1353module_exit(mq_exit);
1354
1355MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
1356MODULE_LICENSE("GPL");
1357MODULE_DESCRIPTION("mq cache policy");
1358
1359MODULE_ALIAS("dm-cache-default");