123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473 |
- /*
- * Copyright (C) 2012 Red Hat. All rights reserved.
- *
- * This file is released under the GPL.
- */
- #include "dm-cache-policy.h"
- #include "dm.h"
- #include <linux/hash.h>
- #include <linux/jiffies.h>
- #include <linux/module.h>
- #include <linux/mutex.h>
- #include <linux/slab.h>
- #include <linux/vmalloc.h>
- #define DM_MSG_PREFIX "cache-policy-mq"
- static struct kmem_cache *mq_entry_cache;
- /*----------------------------------------------------------------*/
- static unsigned next_power(unsigned n, unsigned min)
- {
- return roundup_pow_of_two(max(n, min));
- }
- /*----------------------------------------------------------------*/
- /*
- * Large, sequential ios are probably better left on the origin device since
- * spindles tend to have good bandwidth.
- *
- * The io_tracker tries to spot when the io is in one of these sequential
- * modes.
- *
- * Two thresholds to switch between random and sequential io mode are defaulting
- * as follows and can be adjusted via the constructor and message interfaces.
- */
- #define RANDOM_THRESHOLD_DEFAULT 4
- #define SEQUENTIAL_THRESHOLD_DEFAULT 512
- enum io_pattern {
- PATTERN_SEQUENTIAL,
- PATTERN_RANDOM
- };
- struct io_tracker {
- enum io_pattern pattern;
- unsigned nr_seq_samples;
- unsigned nr_rand_samples;
- unsigned thresholds[2];
- dm_oblock_t last_end_oblock;
- };
- static void iot_init(struct io_tracker *t,
- int sequential_threshold, int random_threshold)
- {
- t->pattern = PATTERN_RANDOM;
- t->nr_seq_samples = 0;
- t->nr_rand_samples = 0;
- t->last_end_oblock = 0;
- t->thresholds[PATTERN_RANDOM] = random_threshold;
- t->thresholds[PATTERN_SEQUENTIAL] = sequential_threshold;
- }
- static enum io_pattern iot_pattern(struct io_tracker *t)
- {
- return t->pattern;
- }
- static void iot_update_stats(struct io_tracker *t, struct bio *bio)
- {
- if (bio->bi_iter.bi_sector == from_oblock(t->last_end_oblock) + 1)
- t->nr_seq_samples++;
- else {
- /*
- * Just one non-sequential IO is enough to reset the
- * counters.
- */
- if (t->nr_seq_samples) {
- t->nr_seq_samples = 0;
- t->nr_rand_samples = 0;
- }
- t->nr_rand_samples++;
- }
- t->last_end_oblock = to_oblock(bio_end_sector(bio) - 1);
- }
- static void iot_check_for_pattern_switch(struct io_tracker *t)
- {
- switch (t->pattern) {
- case PATTERN_SEQUENTIAL:
- if (t->nr_rand_samples >= t->thresholds[PATTERN_RANDOM]) {
- t->pattern = PATTERN_RANDOM;
- t->nr_seq_samples = t->nr_rand_samples = 0;
- }
- break;
- case PATTERN_RANDOM:
- if (t->nr_seq_samples >= t->thresholds[PATTERN_SEQUENTIAL]) {
- t->pattern = PATTERN_SEQUENTIAL;
- t->nr_seq_samples = t->nr_rand_samples = 0;
- }
- break;
- }
- }
- static void iot_examine_bio(struct io_tracker *t, struct bio *bio)
- {
- iot_update_stats(t, bio);
- iot_check_for_pattern_switch(t);
- }
- /*----------------------------------------------------------------*/
- /*
- * This queue is divided up into different levels. Allowing us to push
- * entries to the back of any of the levels. Think of it as a partially
- * sorted queue.
- */
- #define NR_QUEUE_LEVELS 16u
- #define NR_SENTINELS NR_QUEUE_LEVELS * 3
- #define WRITEBACK_PERIOD HZ
- struct queue {
- unsigned nr_elts;
- bool current_writeback_sentinels;
- unsigned long next_writeback;
- struct list_head qs[NR_QUEUE_LEVELS];
- struct list_head sentinels[NR_SENTINELS];
- };
- static void queue_init(struct queue *q)
- {
- unsigned i;
- q->nr_elts = 0;
- q->current_writeback_sentinels = false;
- q->next_writeback = 0;
- for (i = 0; i < NR_QUEUE_LEVELS; i++) {
- INIT_LIST_HEAD(q->qs + i);
- INIT_LIST_HEAD(q->sentinels + i);
- INIT_LIST_HEAD(q->sentinels + NR_QUEUE_LEVELS + i);
- INIT_LIST_HEAD(q->sentinels + (2 * NR_QUEUE_LEVELS) + i);
- }
- }
- static unsigned queue_size(struct queue *q)
- {
- return q->nr_elts;
- }
- static bool queue_empty(struct queue *q)
- {
- return q->nr_elts == 0;
- }
- /*
- * Insert an entry to the back of the given level.
- */
- static void queue_push(struct queue *q, unsigned level, struct list_head *elt)
- {
- q->nr_elts++;
- list_add_tail(elt, q->qs + level);
- }
- static void queue_remove(struct queue *q, struct list_head *elt)
- {
- q->nr_elts--;
- list_del(elt);
- }
- static bool is_sentinel(struct queue *q, struct list_head *h)
- {
- return (h >= q->sentinels) && (h < (q->sentinels + NR_SENTINELS));
- }
- /*
- * Gives us the oldest entry of the lowest popoulated level. If the first
- * level is emptied then we shift down one level.
- */
- static struct list_head *queue_peek(struct queue *q)
- {
- unsigned level;
- struct list_head *h;
- for (level = 0; level < NR_QUEUE_LEVELS; level++)
- list_for_each(h, q->qs + level)
- if (!is_sentinel(q, h))
- return h;
- return NULL;
- }
- static struct list_head *queue_pop(struct queue *q)
- {
- struct list_head *r = queue_peek(q);
- if (r) {
- q->nr_elts--;
- list_del(r);
- }
- return r;
- }
- /*
- * Pops an entry from a level that is not past a sentinel.
- */
- static struct list_head *queue_pop_old(struct queue *q)
- {
- unsigned level;
- struct list_head *h;
- for (level = 0; level < NR_QUEUE_LEVELS; level++)
- list_for_each(h, q->qs + level) {
- if (is_sentinel(q, h))
- break;
- q->nr_elts--;
- list_del(h);
- return h;
- }
- return NULL;
- }
- static struct list_head *list_pop(struct list_head *lh)
- {
- struct list_head *r = lh->next;
- BUG_ON(!r);
- list_del_init(r);
- return r;
- }
- static struct list_head *writeback_sentinel(struct queue *q, unsigned level)
- {
- if (q->current_writeback_sentinels)
- return q->sentinels + NR_QUEUE_LEVELS + level;
- else
- return q->sentinels + 2 * NR_QUEUE_LEVELS + level;
- }
- static void queue_update_writeback_sentinels(struct queue *q)
- {
- unsigned i;
- struct list_head *h;
- if (time_after(jiffies, q->next_writeback)) {
- for (i = 0; i < NR_QUEUE_LEVELS; i++) {
- h = writeback_sentinel(q, i);
- list_del(h);
- list_add_tail(h, q->qs + i);
- }
- q->next_writeback = jiffies + WRITEBACK_PERIOD;
- q->current_writeback_sentinels = !q->current_writeback_sentinels;
- }
- }
- /*
- * Sometimes we want to iterate through entries that have been pushed since
- * a certain event. We use sentinel entries on the queues to delimit these
- * 'tick' events.
- */
- static void queue_tick(struct queue *q)
- {
- unsigned i;
- for (i = 0; i < NR_QUEUE_LEVELS; i++) {
- list_del(q->sentinels + i);
- list_add_tail(q->sentinels + i, q->qs + i);
- }
- }
- typedef void (*iter_fn)(struct list_head *, void *);
- static void queue_iterate_tick(struct queue *q, iter_fn fn, void *context)
- {
- unsigned i;
- struct list_head *h;
- for (i = 0; i < NR_QUEUE_LEVELS; i++) {
- list_for_each_prev(h, q->qs + i) {
- if (is_sentinel(q, h))
- break;
- fn(h, context);
- }
- }
- }
- /*----------------------------------------------------------------*/
- /*
- * Describes a cache entry. Used in both the cache and the pre_cache.
- */
- struct entry {
- struct hlist_node hlist;
- struct list_head list;
- dm_oblock_t oblock;
- /*
- * FIXME: pack these better
- */
- bool dirty:1;
- unsigned hit_count;
- };
- /*
- * Rather than storing the cblock in an entry, we allocate all entries in
- * an array, and infer the cblock from the entry position.
- *
- * Free entries are linked together into a list.
- */
- struct entry_pool {
- struct entry *entries, *entries_end;
- struct list_head free;
- unsigned nr_allocated;
- };
- static int epool_init(struct entry_pool *ep, unsigned nr_entries)
- {
- unsigned i;
- ep->entries = vzalloc(sizeof(struct entry) * nr_entries);
- if (!ep->entries)
- return -ENOMEM;
- ep->entries_end = ep->entries + nr_entries;
- INIT_LIST_HEAD(&ep->free);
- for (i = 0; i < nr_entries; i++)
- list_add(&ep->entries[i].list, &ep->free);
- ep->nr_allocated = 0;
- return 0;
- }
- static void epool_exit(struct entry_pool *ep)
- {
- vfree(ep->entries);
- }
- static struct entry *alloc_entry(struct entry_pool *ep)
- {
- struct entry *e;
- if (list_empty(&ep->free))
- return NULL;
- e = list_entry(list_pop(&ep->free), struct entry, list);
- INIT_LIST_HEAD(&e->list);
- INIT_HLIST_NODE(&e->hlist);
- ep->nr_allocated++;
- return e;
- }
- /*
- * This assumes the cblock hasn't already been allocated.
- */
- static struct entry *alloc_particular_entry(struct entry_pool *ep, dm_cblock_t cblock)
- {
- struct entry *e = ep->entries + from_cblock(cblock);
- list_del_init(&e->list);
- INIT_HLIST_NODE(&e->hlist);
- ep->nr_allocated++;
- return e;
- }
- static void free_entry(struct entry_pool *ep, struct entry *e)
- {
- BUG_ON(!ep->nr_allocated);
- ep->nr_allocated--;
- INIT_HLIST_NODE(&e->hlist);
- list_add(&e->list, &ep->free);
- }
- /*
- * Returns NULL if the entry is free.
- */
- static struct entry *epool_find(struct entry_pool *ep, dm_cblock_t cblock)
- {
- struct entry *e = ep->entries + from_cblock(cblock);
- return !hlist_unhashed(&e->hlist) ? e : NULL;
- }
- static bool epool_empty(struct entry_pool *ep)
- {
- return list_empty(&ep->free);
- }
- static bool in_pool(struct entry_pool *ep, struct entry *e)
- {
- return e >= ep->entries && e < ep->entries_end;
- }
- static dm_cblock_t infer_cblock(struct entry_pool *ep, struct entry *e)
- {
- return to_cblock(e - ep->entries);
- }
- /*----------------------------------------------------------------*/
- struct mq_policy {
- struct dm_cache_policy policy;
- /* protects everything */
- struct mutex lock;
- dm_cblock_t cache_size;
- struct io_tracker tracker;
- /*
- * Entries come from two pools, one of pre-cache entries, and one
- * for the cache proper.
- */
- struct entry_pool pre_cache_pool;
- struct entry_pool cache_pool;
- /*
- * We maintain three queues of entries. The cache proper,
- * consisting of a clean and dirty queue, contains the currently
- * active mappings. Whereas the pre_cache tracks blocks that
- * are being hit frequently and potential candidates for promotion
- * to the cache.
- */
- struct queue pre_cache;
- struct queue cache_clean;
- struct queue cache_dirty;
- /*
- * Keeps track of time, incremented by the core. We use this to
- * avoid attributing multiple hits within the same tick.
- *
- * Access to tick_protected should be done with the spin lock held.
- * It's copied to tick at the start of the map function (within the
- * mutex).
- */
- spinlock_t tick_lock;
- unsigned tick_protected;
- unsigned tick;
- /*
- * A count of the number of times the map function has been called
- * and found an entry in the pre_cache or cache. Currently used to
- * calculate the generation.
- */
- unsigned hit_count;
- /*
- * A generation is a longish period that is used to trigger some
- * book keeping effects. eg, decrementing hit counts on entries.
- * This is needed to allow the cache to evolve as io patterns
- * change.
- */
- unsigned generation;
- unsigned generation_period; /* in lookups (will probably change) */
- unsigned discard_promote_adjustment;
- unsigned read_promote_adjustment;
- unsigned write_promote_adjustment;
- /*
- * The hash table allows us to quickly find an entry by origin
- * block. Both pre_cache and cache entries are in here.
- */
- unsigned nr_buckets;
- dm_block_t hash_bits;
- struct hlist_head *table;
- };
- #define DEFAULT_DISCARD_PROMOTE_ADJUSTMENT 1
- #define DEFAULT_READ_PROMOTE_ADJUSTMENT 4
- #define DEFAULT_WRITE_PROMOTE_ADJUSTMENT 8
- #define DISCOURAGE_DEMOTING_DIRTY_THRESHOLD 128
- /*----------------------------------------------------------------*/
- /*
- * Simple hash table implementation. Should replace with the standard hash
- * table that's making its way upstream.
- */
- static void hash_insert(struct mq_policy *mq, struct entry *e)
- {
- unsigned h = hash_64(from_oblock(e->oblock), mq->hash_bits);
- hlist_add_head(&e->hlist, mq->table + h);
- }
- static struct entry *hash_lookup(struct mq_policy *mq, dm_oblock_t oblock)
- {
- unsigned h = hash_64(from_oblock(oblock), mq->hash_bits);
- struct hlist_head *bucket = mq->table + h;
- struct entry *e;
- hlist_for_each_entry(e, bucket, hlist)
- if (e->oblock == oblock) {
- hlist_del(&e->hlist);
- hlist_add_head(&e->hlist, bucket);
- return e;
- }
- return NULL;
- }
- static void hash_remove(struct entry *e)
- {
- hlist_del(&e->hlist);
- }
- /*----------------------------------------------------------------*/
- static bool any_free_cblocks(struct mq_policy *mq)
- {
- return !epool_empty(&mq->cache_pool);
- }
- static bool any_clean_cblocks(struct mq_policy *mq)
- {
- return !queue_empty(&mq->cache_clean);
- }
- /*----------------------------------------------------------------*/
- /*
- * Now we get to the meat of the policy. This section deals with deciding
- * when to to add entries to the pre_cache and cache, and move between
- * them.
- */
- /*
- * The queue level is based on the log2 of the hit count.
- */
- static unsigned queue_level(struct entry *e)
- {
- return min((unsigned) ilog2(e->hit_count), NR_QUEUE_LEVELS - 1u);
- }
- static bool in_cache(struct mq_policy *mq, struct entry *e)
- {
- return in_pool(&mq->cache_pool, e);
- }
- /*
- * Inserts the entry into the pre_cache or the cache. Ensures the cache
- * block is marked as allocated if necc. Inserts into the hash table.
- * Sets the tick which records when the entry was last moved about.
- */
- static void push(struct mq_policy *mq, struct entry *e)
- {
- hash_insert(mq, e);
- if (in_cache(mq, e))
- queue_push(e->dirty ? &mq->cache_dirty : &mq->cache_clean,
- queue_level(e), &e->list);
- else
- queue_push(&mq->pre_cache, queue_level(e), &e->list);
- }
- /*
- * Removes an entry from pre_cache or cache. Removes from the hash table.
- */
- static void del(struct mq_policy *mq, struct entry *e)
- {
- if (in_cache(mq, e))
- queue_remove(e->dirty ? &mq->cache_dirty : &mq->cache_clean, &e->list);
- else
- queue_remove(&mq->pre_cache, &e->list);
- hash_remove(e);
- }
- /*
- * Like del, except it removes the first entry in the queue (ie. the least
- * recently used).
- */
- static struct entry *pop(struct mq_policy *mq, struct queue *q)
- {
- struct entry *e;
- struct list_head *h = queue_pop(q);
- if (!h)
- return NULL;
- e = container_of(h, struct entry, list);
- hash_remove(e);
- return e;
- }
- static struct entry *pop_old(struct mq_policy *mq, struct queue *q)
- {
- struct entry *e;
- struct list_head *h = queue_pop_old(q);
- if (!h)
- return NULL;
- e = container_of(h, struct entry, list);
- hash_remove(e);
- return e;
- }
- static struct entry *peek(struct queue *q)
- {
- struct list_head *h = queue_peek(q);
- return h ? container_of(h, struct entry, list) : NULL;
- }
- /*
- * The promotion threshold is adjusted every generation. As are the counts
- * of the entries.
- *
- * At the moment the threshold is taken by averaging the hit counts of some
- * of the entries in the cache (the first 20 entries across all levels in
- * ascending order, giving preference to the clean entries at each level).
- *
- * We can be much cleverer than this though. For example, each promotion
- * could bump up the threshold helping to prevent churn. Much more to do
- * here.
- */
- #define MAX_TO_AVERAGE 20
- static void check_generation(struct mq_policy *mq)
- {
- unsigned total = 0, nr = 0, count = 0, level;
- struct list_head *head;
- struct entry *e;
- if ((mq->hit_count >= mq->generation_period) && (epool_empty(&mq->cache_pool))) {
- mq->hit_count = 0;
- mq->generation++;
- for (level = 0; level < NR_QUEUE_LEVELS && count < MAX_TO_AVERAGE; level++) {
- head = mq->cache_clean.qs + level;
- list_for_each_entry(e, head, list) {
- nr++;
- total += e->hit_count;
- if (++count >= MAX_TO_AVERAGE)
- break;
- }
- head = mq->cache_dirty.qs + level;
- list_for_each_entry(e, head, list) {
- nr++;
- total += e->hit_count;
- if (++count >= MAX_TO_AVERAGE)
- break;
- }
- }
- }
- }
- /*
- * Whenever we use an entry we bump up it's hit counter, and push it to the
- * back to it's current level.
- */
- static void requeue(struct mq_policy *mq, struct entry *e)
- {
- check_generation(mq);
- del(mq, e);
- push(mq, e);
- }
- /*
- * Demote the least recently used entry from the cache to the pre_cache.
- * Returns the new cache entry to use, and the old origin block it was
- * mapped to.
- *
- * We drop the hit count on the demoted entry back to 1 to stop it bouncing
- * straight back into the cache if it's subsequently hit. There are
- * various options here, and more experimentation would be good:
- *
- * - just forget about the demoted entry completely (ie. don't insert it
- into the pre_cache).
- * - divide the hit count rather that setting to some hard coded value.
- * - set the hit count to a hard coded value other than 1, eg, is it better
- * if it goes in at level 2?
- */
- static int demote_cblock(struct mq_policy *mq,
- struct policy_locker *locker, dm_oblock_t *oblock)
- {
- struct entry *demoted = peek(&mq->cache_clean);
- if (!demoted)
- /*
- * We could get a block from mq->cache_dirty, but that
- * would add extra latency to the triggering bio as it
- * waits for the writeback. Better to not promote this
- * time and hope there's a clean block next time this block
- * is hit.
- */
- return -ENOSPC;
- if (locker->fn(locker, demoted->oblock))
- /*
- * We couldn't lock the demoted block.
- */
- return -EBUSY;
- del(mq, demoted);
- *oblock = demoted->oblock;
- free_entry(&mq->cache_pool, demoted);
- /*
- * We used to put the demoted block into the pre-cache, but I think
- * it's simpler to just let it work it's way up from zero again.
- * Stops blocks flickering in and out of the cache.
- */
- return 0;
- }
- /*
- * Entries in the pre_cache whose hit count passes the promotion
- * threshold move to the cache proper. Working out the correct
- * value for the promotion_threshold is crucial to this policy.
- */
- static unsigned promote_threshold(struct mq_policy *mq)
- {
- struct entry *e;
- if (any_free_cblocks(mq))
- return 0;
- e = peek(&mq->cache_clean);
- if (e)
- return e->hit_count;
- e = peek(&mq->cache_dirty);
- if (e)
- return e->hit_count + DISCOURAGE_DEMOTING_DIRTY_THRESHOLD;
- /* This should never happen */
- return 0;
- }
- /*
- * We modify the basic promotion_threshold depending on the specific io.
- *
- * If the origin block has been discarded then there's no cost to copy it
- * to the cache.
- *
- * We bias towards reads, since they can be demoted at no cost if they
- * haven't been dirtied.
- */
- static unsigned adjusted_promote_threshold(struct mq_policy *mq,
- bool discarded_oblock, int data_dir)
- {
- if (data_dir == READ)
- return promote_threshold(mq) + mq->read_promote_adjustment;
- if (discarded_oblock && (any_free_cblocks(mq) || any_clean_cblocks(mq))) {
- /*
- * We don't need to do any copying at all, so give this a
- * very low threshold.
- */
- return mq->discard_promote_adjustment;
- }
- return promote_threshold(mq) + mq->write_promote_adjustment;
- }
- static bool should_promote(struct mq_policy *mq, struct entry *e,
- bool discarded_oblock, int data_dir)
- {
- return e->hit_count >=
- adjusted_promote_threshold(mq, discarded_oblock, data_dir);
- }
- static int cache_entry_found(struct mq_policy *mq,
- struct entry *e,
- struct policy_result *result)
- {
- requeue(mq, e);
- if (in_cache(mq, e)) {
- result->op = POLICY_HIT;
- result->cblock = infer_cblock(&mq->cache_pool, e);
- }
- return 0;
- }
- /*
- * Moves an entry from the pre_cache to the cache. The main work is
- * finding which cache block to use.
- */
- static int pre_cache_to_cache(struct mq_policy *mq, struct entry *e,
- struct policy_locker *locker,
- struct policy_result *result)
- {
- int r;
- struct entry *new_e;
- /* Ensure there's a free cblock in the cache */
- if (epool_empty(&mq->cache_pool)) {
- result->op = POLICY_REPLACE;
- r = demote_cblock(mq, locker, &result->old_oblock);
- if (r) {
- result->op = POLICY_MISS;
- return 0;
- }
- } else
- result->op = POLICY_NEW;
- new_e = alloc_entry(&mq->cache_pool);
- BUG_ON(!new_e);
- new_e->oblock = e->oblock;
- new_e->dirty = false;
- new_e->hit_count = e->hit_count;
- del(mq, e);
- free_entry(&mq->pre_cache_pool, e);
- push(mq, new_e);
- result->cblock = infer_cblock(&mq->cache_pool, new_e);
- return 0;
- }
- static int pre_cache_entry_found(struct mq_policy *mq, struct entry *e,
- bool can_migrate, bool discarded_oblock,
- int data_dir, struct policy_locker *locker,
- struct policy_result *result)
- {
- int r = 0;
- if (!should_promote(mq, e, discarded_oblock, data_dir)) {
- requeue(mq, e);
- result->op = POLICY_MISS;
- } else if (!can_migrate)
- r = -EWOULDBLOCK;
- else {
- requeue(mq, e);
- r = pre_cache_to_cache(mq, e, locker, result);
- }
- return r;
- }
- static void insert_in_pre_cache(struct mq_policy *mq,
- dm_oblock_t oblock)
- {
- struct entry *e = alloc_entry(&mq->pre_cache_pool);
- if (!e)
- /*
- * There's no spare entry structure, so we grab the least
- * used one from the pre_cache.
- */
- e = pop(mq, &mq->pre_cache);
- if (unlikely(!e)) {
- DMWARN("couldn't pop from pre cache");
- return;
- }
- e->dirty = false;
- e->oblock = oblock;
- e->hit_count = 1;
- push(mq, e);
- }
- static void insert_in_cache(struct mq_policy *mq, dm_oblock_t oblock,
- struct policy_locker *locker,
- struct policy_result *result)
- {
- int r;
- struct entry *e;
- if (epool_empty(&mq->cache_pool)) {
- result->op = POLICY_REPLACE;
- r = demote_cblock(mq, locker, &result->old_oblock);
- if (unlikely(r)) {
- result->op = POLICY_MISS;
- insert_in_pre_cache(mq, oblock);
- return;
- }
- /*
- * This will always succeed, since we've just demoted.
- */
- e = alloc_entry(&mq->cache_pool);
- BUG_ON(!e);
- } else {
- e = alloc_entry(&mq->cache_pool);
- result->op = POLICY_NEW;
- }
- e->oblock = oblock;
- e->dirty = false;
- e->hit_count = 1;
- push(mq, e);
- result->cblock = infer_cblock(&mq->cache_pool, e);
- }
- static int no_entry_found(struct mq_policy *mq, dm_oblock_t oblock,
- bool can_migrate, bool discarded_oblock,
- int data_dir, struct policy_locker *locker,
- struct policy_result *result)
- {
- if (adjusted_promote_threshold(mq, discarded_oblock, data_dir) <= 1) {
- if (can_migrate)
- insert_in_cache(mq, oblock, locker, result);
- else
- return -EWOULDBLOCK;
- } else {
- insert_in_pre_cache(mq, oblock);
- result->op = POLICY_MISS;
- }
- return 0;
- }
- /*
- * Looks the oblock up in the hash table, then decides whether to put in
- * pre_cache, or cache etc.
- */
- static int map(struct mq_policy *mq, dm_oblock_t oblock,
- bool can_migrate, bool discarded_oblock,
- int data_dir, struct policy_locker *locker,
- struct policy_result *result)
- {
- int r = 0;
- struct entry *e = hash_lookup(mq, oblock);
- if (e && in_cache(mq, e))
- r = cache_entry_found(mq, e, result);
- else if (mq->tracker.thresholds[PATTERN_SEQUENTIAL] &&
- iot_pattern(&mq->tracker) == PATTERN_SEQUENTIAL)
- result->op = POLICY_MISS;
- else if (e)
- r = pre_cache_entry_found(mq, e, can_migrate, discarded_oblock,
- data_dir, locker, result);
- else
- r = no_entry_found(mq, oblock, can_migrate, discarded_oblock,
- data_dir, locker, result);
- if (r == -EWOULDBLOCK)
- result->op = POLICY_MISS;
- return r;
- }
- /*----------------------------------------------------------------*/
- /*
- * Public interface, via the policy struct. See dm-cache-policy.h for a
- * description of these.
- */
- static struct mq_policy *to_mq_policy(struct dm_cache_policy *p)
- {
- return container_of(p, struct mq_policy, policy);
- }
- static void mq_destroy(struct dm_cache_policy *p)
- {
- struct mq_policy *mq = to_mq_policy(p);
- vfree(mq->table);
- epool_exit(&mq->cache_pool);
- epool_exit(&mq->pre_cache_pool);
- kfree(mq);
- }
- static void update_pre_cache_hits(struct list_head *h, void *context)
- {
- struct entry *e = container_of(h, struct entry, list);
- e->hit_count++;
- }
- static void update_cache_hits(struct list_head *h, void *context)
- {
- struct mq_policy *mq = context;
- struct entry *e = container_of(h, struct entry, list);
- e->hit_count++;
- mq->hit_count++;
- }
- static void copy_tick(struct mq_policy *mq)
- {
- unsigned long flags, tick;
- spin_lock_irqsave(&mq->tick_lock, flags);
- tick = mq->tick_protected;
- if (tick != mq->tick) {
- queue_iterate_tick(&mq->pre_cache, update_pre_cache_hits, mq);
- queue_iterate_tick(&mq->cache_dirty, update_cache_hits, mq);
- queue_iterate_tick(&mq->cache_clean, update_cache_hits, mq);
- mq->tick = tick;
- }
- queue_tick(&mq->pre_cache);
- queue_tick(&mq->cache_dirty);
- queue_tick(&mq->cache_clean);
- queue_update_writeback_sentinels(&mq->cache_dirty);
- spin_unlock_irqrestore(&mq->tick_lock, flags);
- }
- static int mq_map(struct dm_cache_policy *p, dm_oblock_t oblock,
- bool can_block, bool can_migrate, bool discarded_oblock,
- struct bio *bio, struct policy_locker *locker,
- struct policy_result *result)
- {
- int r;
- struct mq_policy *mq = to_mq_policy(p);
- result->op = POLICY_MISS;
- if (can_block)
- mutex_lock(&mq->lock);
- else if (!mutex_trylock(&mq->lock))
- return -EWOULDBLOCK;
- copy_tick(mq);
- iot_examine_bio(&mq->tracker, bio);
- r = map(mq, oblock, can_migrate, discarded_oblock,
- bio_data_dir(bio), locker, result);
- mutex_unlock(&mq->lock);
- return r;
- }
- static int mq_lookup(struct dm_cache_policy *p, dm_oblock_t oblock, dm_cblock_t *cblock)
- {
- int r;
- struct mq_policy *mq = to_mq_policy(p);
- struct entry *e;
- if (!mutex_trylock(&mq->lock))
- return -EWOULDBLOCK;
- e = hash_lookup(mq, oblock);
- if (e && in_cache(mq, e)) {
- *cblock = infer_cblock(&mq->cache_pool, e);
- r = 0;
- } else
- r = -ENOENT;
- mutex_unlock(&mq->lock);
- return r;
- }
- static void __mq_set_clear_dirty(struct mq_policy *mq, dm_oblock_t oblock, bool set)
- {
- struct entry *e;
- e = hash_lookup(mq, oblock);
- BUG_ON(!e || !in_cache(mq, e));
- del(mq, e);
- e->dirty = set;
- push(mq, e);
- }
- static void mq_set_dirty(struct dm_cache_policy *p, dm_oblock_t oblock)
- {
- struct mq_policy *mq = to_mq_policy(p);
- mutex_lock(&mq->lock);
- __mq_set_clear_dirty(mq, oblock, true);
- mutex_unlock(&mq->lock);
- }
- static void mq_clear_dirty(struct dm_cache_policy *p, dm_oblock_t oblock)
- {
- struct mq_policy *mq = to_mq_policy(p);
- mutex_lock(&mq->lock);
- __mq_set_clear_dirty(mq, oblock, false);
- mutex_unlock(&mq->lock);
- }
- static int mq_load_mapping(struct dm_cache_policy *p,
- dm_oblock_t oblock, dm_cblock_t cblock,
- uint32_t hint, bool hint_valid)
- {
- struct mq_policy *mq = to_mq_policy(p);
- struct entry *e;
- e = alloc_particular_entry(&mq->cache_pool, cblock);
- e->oblock = oblock;
- e->dirty = false; /* this gets corrected in a minute */
- e->hit_count = hint_valid ? hint : 1;
- push(mq, e);
- return 0;
- }
- static int mq_save_hints(struct mq_policy *mq, struct queue *q,
- policy_walk_fn fn, void *context)
- {
- int r;
- unsigned level;
- struct list_head *h;
- struct entry *e;
- for (level = 0; level < NR_QUEUE_LEVELS; level++)
- list_for_each(h, q->qs + level) {
- if (is_sentinel(q, h))
- continue;
- e = container_of(h, struct entry, list);
- r = fn(context, infer_cblock(&mq->cache_pool, e),
- e->oblock, e->hit_count);
- if (r)
- return r;
- }
- return 0;
- }
- static int mq_walk_mappings(struct dm_cache_policy *p, policy_walk_fn fn,
- void *context)
- {
- struct mq_policy *mq = to_mq_policy(p);
- int r = 0;
- mutex_lock(&mq->lock);
- r = mq_save_hints(mq, &mq->cache_clean, fn, context);
- if (!r)
- r = mq_save_hints(mq, &mq->cache_dirty, fn, context);
- mutex_unlock(&mq->lock);
- return r;
- }
- static void __remove_mapping(struct mq_policy *mq, dm_oblock_t oblock)
- {
- struct entry *e;
- e = hash_lookup(mq, oblock);
- BUG_ON(!e || !in_cache(mq, e));
- del(mq, e);
- free_entry(&mq->cache_pool, e);
- }
- static void mq_remove_mapping(struct dm_cache_policy *p, dm_oblock_t oblock)
- {
- struct mq_policy *mq = to_mq_policy(p);
- mutex_lock(&mq->lock);
- __remove_mapping(mq, oblock);
- mutex_unlock(&mq->lock);
- }
- static int __remove_cblock(struct mq_policy *mq, dm_cblock_t cblock)
- {
- struct entry *e = epool_find(&mq->cache_pool, cblock);
- if (!e)
- return -ENODATA;
- del(mq, e);
- free_entry(&mq->cache_pool, e);
- return 0;
- }
- static int mq_remove_cblock(struct dm_cache_policy *p, dm_cblock_t cblock)
- {
- int r;
- struct mq_policy *mq = to_mq_policy(p);
- mutex_lock(&mq->lock);
- r = __remove_cblock(mq, cblock);
- mutex_unlock(&mq->lock);
- return r;
- }
- #define CLEAN_TARGET_PERCENTAGE 25
- static bool clean_target_met(struct mq_policy *mq)
- {
- /*
- * Cache entries may not be populated. So we're cannot rely on the
- * size of the clean queue.
- */
- unsigned nr_clean = from_cblock(mq->cache_size) - queue_size(&mq->cache_dirty);
- unsigned target = from_cblock(mq->cache_size) * CLEAN_TARGET_PERCENTAGE / 100;
- return nr_clean >= target;
- }
- static int __mq_writeback_work(struct mq_policy *mq, dm_oblock_t *oblock,
- dm_cblock_t *cblock)
- {
- struct entry *e = pop_old(mq, &mq->cache_dirty);
- if (!e && !clean_target_met(mq))
- e = pop(mq, &mq->cache_dirty);
- if (!e)
- return -ENODATA;
- *oblock = e->oblock;
- *cblock = infer_cblock(&mq->cache_pool, e);
- e->dirty = false;
- push(mq, e);
- return 0;
- }
- static int mq_writeback_work(struct dm_cache_policy *p, dm_oblock_t *oblock,
- dm_cblock_t *cblock, bool critical_only)
- {
- int r;
- struct mq_policy *mq = to_mq_policy(p);
- mutex_lock(&mq->lock);
- r = __mq_writeback_work(mq, oblock, cblock);
- mutex_unlock(&mq->lock);
- return r;
- }
- static void __force_mapping(struct mq_policy *mq,
- dm_oblock_t current_oblock, dm_oblock_t new_oblock)
- {
- struct entry *e = hash_lookup(mq, current_oblock);
- if (e && in_cache(mq, e)) {
- del(mq, e);
- e->oblock = new_oblock;
- e->dirty = true;
- push(mq, e);
- }
- }
- static void mq_force_mapping(struct dm_cache_policy *p,
- dm_oblock_t current_oblock, dm_oblock_t new_oblock)
- {
- struct mq_policy *mq = to_mq_policy(p);
- mutex_lock(&mq->lock);
- __force_mapping(mq, current_oblock, new_oblock);
- mutex_unlock(&mq->lock);
- }
- static dm_cblock_t mq_residency(struct dm_cache_policy *p)
- {
- dm_cblock_t r;
- struct mq_policy *mq = to_mq_policy(p);
- mutex_lock(&mq->lock);
- r = to_cblock(mq->cache_pool.nr_allocated);
- mutex_unlock(&mq->lock);
- return r;
- }
- static void mq_tick(struct dm_cache_policy *p, bool can_block)
- {
- struct mq_policy *mq = to_mq_policy(p);
- unsigned long flags;
- spin_lock_irqsave(&mq->tick_lock, flags);
- mq->tick_protected++;
- spin_unlock_irqrestore(&mq->tick_lock, flags);
- if (can_block) {
- mutex_lock(&mq->lock);
- copy_tick(mq);
- mutex_unlock(&mq->lock);
- }
- }
- static int mq_set_config_value(struct dm_cache_policy *p,
- const char *key, const char *value)
- {
- struct mq_policy *mq = to_mq_policy(p);
- unsigned long tmp;
- if (kstrtoul(value, 10, &tmp))
- return -EINVAL;
- if (!strcasecmp(key, "random_threshold")) {
- mq->tracker.thresholds[PATTERN_RANDOM] = tmp;
- } else if (!strcasecmp(key, "sequential_threshold")) {
- mq->tracker.thresholds[PATTERN_SEQUENTIAL] = tmp;
- } else if (!strcasecmp(key, "discard_promote_adjustment"))
- mq->discard_promote_adjustment = tmp;
- else if (!strcasecmp(key, "read_promote_adjustment"))
- mq->read_promote_adjustment = tmp;
- else if (!strcasecmp(key, "write_promote_adjustment"))
- mq->write_promote_adjustment = tmp;
- else
- return -EINVAL;
- return 0;
- }
- static int mq_emit_config_values(struct dm_cache_policy *p, char *result,
- unsigned maxlen, ssize_t *sz_ptr)
- {
- ssize_t sz = *sz_ptr;
- struct mq_policy *mq = to_mq_policy(p);
- DMEMIT("10 random_threshold %u "
- "sequential_threshold %u "
- "discard_promote_adjustment %u "
- "read_promote_adjustment %u "
- "write_promote_adjustment %u ",
- mq->tracker.thresholds[PATTERN_RANDOM],
- mq->tracker.thresholds[PATTERN_SEQUENTIAL],
- mq->discard_promote_adjustment,
- mq->read_promote_adjustment,
- mq->write_promote_adjustment);
- *sz_ptr = sz;
- return 0;
- }
- /* Init the policy plugin interface function pointers. */
- static void init_policy_functions(struct mq_policy *mq)
- {
- mq->policy.destroy = mq_destroy;
- mq->policy.map = mq_map;
- mq->policy.lookup = mq_lookup;
- mq->policy.set_dirty = mq_set_dirty;
- mq->policy.clear_dirty = mq_clear_dirty;
- mq->policy.load_mapping = mq_load_mapping;
- mq->policy.walk_mappings = mq_walk_mappings;
- mq->policy.remove_mapping = mq_remove_mapping;
- mq->policy.remove_cblock = mq_remove_cblock;
- mq->policy.writeback_work = mq_writeback_work;
- mq->policy.force_mapping = mq_force_mapping;
- mq->policy.residency = mq_residency;
- mq->policy.tick = mq_tick;
- mq->policy.emit_config_values = mq_emit_config_values;
- mq->policy.set_config_value = mq_set_config_value;
- }
- static struct dm_cache_policy *mq_create(dm_cblock_t cache_size,
- sector_t origin_size,
- sector_t cache_block_size)
- {
- struct mq_policy *mq = kzalloc(sizeof(*mq), GFP_KERNEL);
- if (!mq)
- return NULL;
- init_policy_functions(mq);
- iot_init(&mq->tracker, SEQUENTIAL_THRESHOLD_DEFAULT, RANDOM_THRESHOLD_DEFAULT);
- mq->cache_size = cache_size;
- if (epool_init(&mq->pre_cache_pool, from_cblock(cache_size))) {
- DMERR("couldn't initialize pool of pre-cache entries");
- goto bad_pre_cache_init;
- }
- if (epool_init(&mq->cache_pool, from_cblock(cache_size))) {
- DMERR("couldn't initialize pool of cache entries");
- goto bad_cache_init;
- }
- mq->tick_protected = 0;
- mq->tick = 0;
- mq->hit_count = 0;
- mq->generation = 0;
- mq->discard_promote_adjustment = DEFAULT_DISCARD_PROMOTE_ADJUSTMENT;
- mq->read_promote_adjustment = DEFAULT_READ_PROMOTE_ADJUSTMENT;
- mq->write_promote_adjustment = DEFAULT_WRITE_PROMOTE_ADJUSTMENT;
- mutex_init(&mq->lock);
- spin_lock_init(&mq->tick_lock);
- queue_init(&mq->pre_cache);
- queue_init(&mq->cache_clean);
- queue_init(&mq->cache_dirty);
- mq->generation_period = max((unsigned) from_cblock(cache_size), 1024U);
- mq->nr_buckets = next_power(from_cblock(cache_size) / 2, 16);
- mq->hash_bits = __ffs(mq->nr_buckets);
- mq->table = vzalloc(sizeof(*mq->table) * mq->nr_buckets);
- if (!mq->table)
- goto bad_alloc_table;
- return &mq->policy;
- bad_alloc_table:
- epool_exit(&mq->cache_pool);
- bad_cache_init:
- epool_exit(&mq->pre_cache_pool);
- bad_pre_cache_init:
- kfree(mq);
- return NULL;
- }
- /*----------------------------------------------------------------*/
- static struct dm_cache_policy_type mq_policy_type = {
- .name = "mq",
- .version = {1, 4, 0},
- .hint_size = 4,
- .owner = THIS_MODULE,
- .create = mq_create
- };
- static int __init mq_init(void)
- {
- int r;
- mq_entry_cache = kmem_cache_create("dm_mq_policy_cache_entry",
- sizeof(struct entry),
- __alignof__(struct entry),
- 0, NULL);
- if (!mq_entry_cache)
- return -ENOMEM;
- r = dm_cache_policy_register(&mq_policy_type);
- if (r) {
- DMERR("register failed %d", r);
- kmem_cache_destroy(mq_entry_cache);
- return -ENOMEM;
- }
- return 0;
- }
- static void __exit mq_exit(void)
- {
- dm_cache_policy_unregister(&mq_policy_type);
- kmem_cache_destroy(mq_entry_cache);
- }
- module_init(mq_init);
- module_exit(mq_exit);
- MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
- MODULE_LICENSE("GPL");
- MODULE_DESCRIPTION("mq cache policy");
|