| /* |
| * 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/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 |
| |
| struct queue { |
| struct list_head qs[NR_QUEUE_LEVELS]; |
| }; |
| |
| static void queue_init(struct queue *q) |
| { |
| unsigned i; |
| |
| for (i = 0; i < NR_QUEUE_LEVELS; i++) |
| INIT_LIST_HEAD(q->qs + i); |
| } |
| |
| /* |
| * Checks to see if the queue is empty. |
| * FIXME: reduce cpu usage. |
| */ |
| static bool queue_empty(struct queue *q) |
| { |
| unsigned i; |
| |
| for (i = 0; i < NR_QUEUE_LEVELS; i++) |
| if (!list_empty(q->qs + i)) |
| return false; |
| |
| return true; |
| } |
| |
| /* |
| * Insert an entry to the back of the given level. |
| */ |
| static void queue_push(struct queue *q, unsigned level, struct list_head *elt) |
| { |
| list_add_tail(elt, q->qs + level); |
| } |
| |
| static void queue_remove(struct list_head *elt) |
| { |
| list_del(elt); |
| } |
| |
| /* |
| * Shifts all regions down one level. This has no effect on the order of |
| * the queue. |
| */ |
| static void queue_shift_down(struct queue *q) |
| { |
| unsigned level; |
| |
| for (level = 1; level < NR_QUEUE_LEVELS; level++) |
| list_splice_init(q->qs + level, q->qs + level - 1); |
| } |
| |
| /* |
| * 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_pop(struct queue *q) |
| { |
| unsigned level; |
| struct list_head *r; |
| |
| for (level = 0; level < NR_QUEUE_LEVELS; level++) |
| if (!list_empty(q->qs + level)) { |
| r = q->qs[level].next; |
| list_del(r); |
| |
| /* have we just emptied the bottom level? */ |
| if (level == 0 && list_empty(q->qs)) |
| queue_shift_down(q); |
| |
| return r; |
| } |
| |
| 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; |
| } |
| |
| /*----------------------------------------------------------------*/ |
| |
| /* |
| * 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; |
| unsigned generation; |
| unsigned tick; |
| }; |
| |
| /* |
| * 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(&e->list); |
| |
| INIT_LIST_HEAD(&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) */ |
| |
| /* |
| * 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. |
| */ |
| unsigned promote_threshold; |
| |
| /* |
| * 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; |
| }; |
| |
| /*----------------------------------------------------------------*/ |
| |
| /* |
| * 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) |
| { |
| e->tick = mq->tick; |
| 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) |
| { |
| queue_remove(&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; |
| } |
| |
| /* |
| * Has this entry already been updated? |
| */ |
| static bool updated_this_tick(struct mq_policy *mq, struct entry *e) |
| { |
| return mq->tick == e->tick; |
| } |
| |
| /* |
| * 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; |
| } |
| } |
| |
| mq->promote_threshold = nr ? total / nr : 1; |
| if (mq->promote_threshold * nr < total) |
| mq->promote_threshold++; |
| } |
| } |
| |
| /* |
| * 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_and_update_tick(struct mq_policy *mq, struct entry *e) |
| { |
| if (updated_this_tick(mq, e)) |
| return; |
| |
| e->hit_count++; |
| mq->hit_count++; |
| check_generation(mq); |
| |
| /* generation adjustment, to stop the counts increasing forever. */ |
| /* FIXME: divide? */ |
| /* e->hit_count -= min(e->hit_count - 1, mq->generation - e->generation); */ |
| e->generation = mq->generation; |
| |
| 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, dm_oblock_t *oblock) |
| { |
| struct entry *demoted = pop(mq, &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; |
| |
| *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; |
| } |
| |
| /* |
| * 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. |
| */ |
| #define DISCARDED_PROMOTE_THRESHOLD 1 |
| #define READ_PROMOTE_THRESHOLD 4 |
| #define WRITE_PROMOTE_THRESHOLD 8 |
| |
| static unsigned adjusted_promote_threshold(struct mq_policy *mq, |
| bool discarded_oblock, int data_dir) |
| { |
| if (data_dir == READ) |
| return mq->promote_threshold + READ_PROMOTE_THRESHOLD; |
| |
| 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 DISCARDED_PROMOTE_THRESHOLD; |
| } |
| |
| return mq->promote_threshold + WRITE_PROMOTE_THRESHOLD; |
| } |
| |
| 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_and_update_tick(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_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, &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; |
| new_e->generation = e->generation; |
| new_e->tick = e->tick; |
| |
| 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_result *result) |
| { |
| int r = 0; |
| bool updated = updated_this_tick(mq, e); |
| |
| if ((!discarded_oblock && updated) || |
| !should_promote(mq, e, discarded_oblock, data_dir)) { |
| requeue_and_update_tick(mq, e); |
| result->op = POLICY_MISS; |
| |
| } else if (!can_migrate) |
| r = -EWOULDBLOCK; |
| |
| else { |
| requeue_and_update_tick(mq, e); |
| r = pre_cache_to_cache(mq, e, 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; |
| e->generation = mq->generation; |
| push(mq, e); |
| } |
| |
| static void insert_in_cache(struct mq_policy *mq, dm_oblock_t oblock, |
| struct policy_result *result) |
| { |
| int r; |
| struct entry *e; |
| |
| if (epool_empty(&mq->cache_pool)) { |
| result->op = POLICY_REPLACE; |
| r = demote_cblock(mq, &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; |
| e->generation = mq->generation; |
| 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_result *result) |
| { |
| if (adjusted_promote_threshold(mq, discarded_oblock, data_dir) == 1) { |
| if (can_migrate) |
| insert_in_cache(mq, oblock, 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_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 (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, result); |
| |
| else |
| r = no_entry_found(mq, oblock, can_migrate, discarded_oblock, |
| data_dir, 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); |
| |
| kfree(mq->table); |
| epool_exit(&mq->cache_pool); |
| epool_exit(&mq->pre_cache_pool); |
| kfree(mq); |
| } |
| |
| static void copy_tick(struct mq_policy *mq) |
| { |
| unsigned long flags; |
| |
| spin_lock_irqsave(&mq->tick_lock, flags); |
| mq->tick = mq->tick_protected; |
| 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_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), 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; |
| e->generation = mq->generation; |
| 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 entry *e; |
| |
| for (level = 0; level < NR_QUEUE_LEVELS; level++) |
| list_for_each_entry(e, q->qs + level, 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; |
| } |
| |
| static int __mq_writeback_work(struct mq_policy *mq, dm_oblock_t *oblock, |
| dm_cblock_t *cblock) |
| { |
| struct entry *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) |
| { |
| 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) |
| { |
| 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); |
| } |
| |
| 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); |
| enum io_pattern pattern; |
| unsigned long tmp; |
| |
| if (!strcasecmp(key, "random_threshold")) |
| pattern = PATTERN_RANDOM; |
| else if (!strcasecmp(key, "sequential_threshold")) |
| pattern = PATTERN_SEQUENTIAL; |
| else |
| return -EINVAL; |
| |
| if (kstrtoul(value, 10, &tmp)) |
| return -EINVAL; |
| |
| mq->tracker.thresholds[pattern] = tmp; |
| |
| return 0; |
| } |
| |
| static int mq_emit_config_values(struct dm_cache_policy *p, char *result, unsigned maxlen) |
| { |
| ssize_t sz = 0; |
| struct mq_policy *mq = to_mq_policy(p); |
| |
| DMEMIT("4 random_threshold %u sequential_threshold %u", |
| mq->tracker.thresholds[PATTERN_RANDOM], |
| mq->tracker.thresholds[PATTERN_SEQUENTIAL]); |
| |
| 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->promote_threshold = 0; |
| 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) - 1; |
| mq->table = kzalloc(sizeof(*mq->table) * mq->nr_buckets, GFP_KERNEL); |
| 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, 1, 0}, |
| .hint_size = 4, |
| .owner = THIS_MODULE, |
| .create = mq_create |
| }; |
| |
| static struct dm_cache_policy_type default_policy_type = { |
| .name = "default", |
| .version = {1, 1, 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) |
| goto bad; |
| |
| r = dm_cache_policy_register(&mq_policy_type); |
| if (r) { |
| DMERR("register failed %d", r); |
| goto bad_register_mq; |
| } |
| |
| r = dm_cache_policy_register(&default_policy_type); |
| if (!r) { |
| DMINFO("version %u.%u.%u loaded", |
| mq_policy_type.version[0], |
| mq_policy_type.version[1], |
| mq_policy_type.version[2]); |
| return 0; |
| } |
| |
| DMERR("register failed (as default) %d", r); |
| |
| dm_cache_policy_unregister(&mq_policy_type); |
| bad_register_mq: |
| kmem_cache_destroy(mq_entry_cache); |
| bad: |
| return -ENOMEM; |
| } |
| |
| static void __exit mq_exit(void) |
| { |
| dm_cache_policy_unregister(&mq_policy_type); |
| dm_cache_policy_unregister(&default_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"); |
| |
| MODULE_ALIAS("dm-cache-default"); |