/* * Copyright (C) 2012 Red Hat. All rights reserved. * * This file is released under the GPL. */ #include "dm-cache-policy.h" #include "dm.h" #include #include #include #include #include #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)); } /*----------------------------------------------------------------*/ static unsigned long *alloc_bitset(unsigned nr_entries) { size_t s = sizeof(unsigned long) * dm_div_up(nr_entries, BITS_PER_LONG); return vzalloc(s); } static void free_bitset(unsigned long *bits) { vfree(bits); } /*----------------------------------------------------------------*/ /* * 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_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->bi_sector + bio_sectors(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; dm_cblock_t cblock; /* valid iff in_cache */ /* * FIXME: pack these better */ bool in_cache:1; bool dirty:1; unsigned hit_count; unsigned generation; unsigned tick; }; struct mq_policy { struct dm_cache_policy policy; /* protects everything */ struct mutex lock; dm_cblock_t cache_size; struct io_tracker tracker; /* * 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; /* * We need cache_size entries for the cache, and choose to have * cache_size entries for the pre_cache too. One motivation for * using the same size is to make the hit counts directly * comparable between pre_cache and cache. */ unsigned nr_entries; unsigned nr_entries_allocated; struct list_head free; /* * Cache blocks may be unallocated. We store this info in a * bitset. */ unsigned long *allocation_bitset; unsigned nr_cblocks_allocated; unsigned find_free_nr_words; unsigned find_free_last_word; /* * 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; }; /*----------------------------------------------------------------*/ /* Free/alloc mq cache entry structures. */ static void concat_queue(struct list_head *lh, struct queue *q) { unsigned level; for (level = 0; level < NR_QUEUE_LEVELS; level++) list_splice(q->qs + level, lh); } static void free_entries(struct mq_policy *mq) { struct entry *e, *tmp; concat_queue(&mq->free, &mq->pre_cache); concat_queue(&mq->free, &mq->cache_clean); concat_queue(&mq->free, &mq->cache_dirty); list_for_each_entry_safe(e, tmp, &mq->free, list) kmem_cache_free(mq_entry_cache, e); } static int alloc_entries(struct mq_policy *mq, unsigned elts) { unsigned u = mq->nr_entries; INIT_LIST_HEAD(&mq->free); mq->nr_entries_allocated = 0; while (u--) { struct entry *e = kmem_cache_zalloc(mq_entry_cache, GFP_KERNEL); if (!e) { free_entries(mq); return -ENOMEM; } list_add(&e->list, &mq->free); } return 0; } /*----------------------------------------------------------------*/ /* * 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); } /*----------------------------------------------------------------*/ /* * Allocates a new entry structure. The memory is allocated in one lump, * so we just handing it out here. Returns NULL if all entries have * already been allocated. Cannot fail otherwise. */ static struct entry *alloc_entry(struct mq_policy *mq) { struct entry *e; if (mq->nr_entries_allocated >= mq->nr_entries) { BUG_ON(!list_empty(&mq->free)); return NULL; } e = list_entry(list_pop(&mq->free), struct entry, list); INIT_LIST_HEAD(&e->list); INIT_HLIST_NODE(&e->hlist); mq->nr_entries_allocated++; return e; } /*----------------------------------------------------------------*/ /* * Mark cache blocks allocated or not in the bitset. */ static void alloc_cblock(struct mq_policy *mq, dm_cblock_t cblock) { BUG_ON(from_cblock(cblock) > from_cblock(mq->cache_size)); BUG_ON(test_bit(from_cblock(cblock), mq->allocation_bitset)); set_bit(from_cblock(cblock), mq->allocation_bitset); mq->nr_cblocks_allocated++; } static void free_cblock(struct mq_policy *mq, dm_cblock_t cblock) { BUG_ON(from_cblock(cblock) > from_cblock(mq->cache_size)); BUG_ON(!test_bit(from_cblock(cblock), mq->allocation_bitset)); clear_bit(from_cblock(cblock), mq->allocation_bitset); mq->nr_cblocks_allocated--; } static bool any_free_cblocks(struct mq_policy *mq) { return mq->nr_cblocks_allocated < from_cblock(mq->cache_size); } static bool any_clean_cblocks(struct mq_policy *mq) { return !queue_empty(&mq->cache_clean); } /* * Fills result out with a cache block that isn't in use, or return * -ENOSPC. This does _not_ mark the cblock as allocated, the caller is * reponsible for that. */ static int __find_free_cblock(struct mq_policy *mq, unsigned begin, unsigned end, dm_cblock_t *result, unsigned *last_word) { int r = -ENOSPC; unsigned w; for (w = begin; w < end; w++) { /* * ffz is undefined if no zero exists */ if (mq->allocation_bitset[w] != ~0UL) { *last_word = w; *result = to_cblock((w * BITS_PER_LONG) + ffz(mq->allocation_bitset[w])); if (from_cblock(*result) < from_cblock(mq->cache_size)) r = 0; break; } } return r; } static int find_free_cblock(struct mq_policy *mq, dm_cblock_t *result) { int r; if (!any_free_cblocks(mq)) return -ENOSPC; r = __find_free_cblock(mq, mq->find_free_last_word, mq->find_free_nr_words, result, &mq->find_free_last_word); if (r == -ENOSPC && mq->find_free_last_word) r = __find_free_cblock(mq, 0, mq->find_free_last_word, result, &mq->find_free_last_word); return r; } /*----------------------------------------------------------------*/ /* * 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); } /* * 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 (e->in_cache) { alloc_cblock(mq, e->cblock); 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. * Frees off the cache block if necc. */ static void del(struct mq_policy *mq, struct entry *e) { queue_remove(&e->list); hash_remove(e); if (e->in_cache) free_cblock(mq, e->cblock); } /* * 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); if (e->in_cache) free_cblock(mq, e->cblock); 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) && (mq->nr_cblocks_allocated == from_cblock(mq->cache_size))) { 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, dm_cblock_t *cblock) { 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; *cblock = demoted->cblock; *oblock = demoted->oblock; demoted->in_cache = false; demoted->dirty = false; demoted->hit_count = 1; push(mq, demoted); 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 (e->in_cache) { result->op = POLICY_HIT; result->cblock = e->cblock; } 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; dm_cblock_t cblock; if (find_free_cblock(mq, &cblock) == -ENOSPC) { result->op = POLICY_REPLACE; r = demote_cblock(mq, &result->old_oblock, &cblock); if (r) { result->op = POLICY_MISS; return 0; } } else result->op = POLICY_NEW; result->cblock = e->cblock = cblock; del(mq, e); e->in_cache = true; e->dirty = false; push(mq, 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); requeue_and_update_tick(mq, e); if ((!discarded_oblock && updated) || !should_promote(mq, e, discarded_oblock, data_dir)) result->op = POLICY_MISS; else if (!can_migrate) r = -EWOULDBLOCK; else r = pre_cache_to_cache(mq, e, result); return r; } static void insert_entry_in_pre_cache(struct mq_policy *mq, struct entry *e, dm_oblock_t oblock) { e->in_cache = false; e->dirty = false; e->oblock = oblock; e->hit_count = 1; e->generation = mq->generation; push(mq, e); } static void insert_in_pre_cache(struct mq_policy *mq, dm_oblock_t oblock) { struct entry *e = alloc_entry(mq); 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; } insert_entry_in_pre_cache(mq, e, oblock); } static void insert_in_cache(struct mq_policy *mq, dm_oblock_t oblock, struct policy_result *result) { int r; struct entry *e; dm_cblock_t cblock; if (find_free_cblock(mq, &cblock) == -ENOSPC) { r = demote_cblock(mq, &result->old_oblock, &cblock); if (unlikely(r)) { result->op = POLICY_MISS; insert_in_pre_cache(mq, oblock); return; } /* * This will always succeed, since we've just demoted. */ e = pop(mq, &mq->pre_cache); result->op = POLICY_REPLACE; } else { e = alloc_entry(mq); if (unlikely(!e)) e = pop(mq, &mq->pre_cache); if (unlikely(!e)) { result->op = POLICY_MISS; return; } result->op = POLICY_NEW; } e->oblock = oblock; e->cblock = cblock; e->in_cache = true; e->dirty = false; e->hit_count = 1; e->generation = mq->generation; push(mq, e); result->cblock = e->cblock; } 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 && e->in_cache) 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); free_bitset(mq->allocation_bitset); kfree(mq->table); free_entries(mq); 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 && e->in_cache) { *cblock = e->cblock; r = 0; } else r = -ENOENT; mutex_unlock(&mq->lock); return r; } /* * FIXME: __mq_set_clear_dirty can block due to mutex. * Ideally a policy should not block in functions called * from the map() function. Explore using RCU. */ static void __mq_set_clear_dirty(struct dm_cache_policy *p, dm_oblock_t oblock, bool set) { struct mq_policy *mq = to_mq_policy(p); struct entry *e; mutex_lock(&mq->lock); e = hash_lookup(mq, oblock); if (!e) DMWARN("__mq_set_clear_dirty called for a block that isn't in the cache"); else { BUG_ON(!e->in_cache); del(mq, e); e->dirty = set; push(mq, e); } mutex_unlock(&mq->lock); } static void mq_set_dirty(struct dm_cache_policy *p, dm_oblock_t oblock) { __mq_set_clear_dirty(p, oblock, true); } static void mq_clear_dirty(struct dm_cache_policy *p, dm_oblock_t oblock) { __mq_set_clear_dirty(p, oblock, false); } 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_entry(mq); if (!e) return -ENOMEM; e->cblock = cblock; e->oblock = oblock; e->in_cache = true; 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_walk_mappings(struct dm_cache_policy *p, policy_walk_fn fn, void *context) { struct mq_policy *mq = to_mq_policy(p); int r = 0; struct entry *e; unsigned level; mutex_lock(&mq->lock); for (level = 0; level < NR_QUEUE_LEVELS; level++) list_for_each_entry(e, &mq->cache_clean.qs[level], list) { r = fn(context, e->cblock, e->oblock, e->hit_count); if (r) goto out; } for (level = 0; level < NR_QUEUE_LEVELS; level++) list_for_each_entry(e, &mq->cache_dirty.qs[level], list) { r = fn(context, e->cblock, e->oblock, e->hit_count); if (r) goto out; } out: mutex_unlock(&mq->lock); return r; } static void mq_remove_mapping(struct dm_cache_policy *p, dm_oblock_t oblock) { struct mq_policy *mq = to_mq_policy(p); struct entry *e; mutex_lock(&mq->lock); e = hash_lookup(mq, oblock); BUG_ON(!e || !e->in_cache); del(mq, e); e->in_cache = false; e->dirty = false; push(mq, e); mutex_unlock(&mq->lock); } 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 = e->cblock; 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); BUG_ON(!e || !e->in_cache); 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->nr_cblocks_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.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) { int r; 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; 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); mq->find_free_nr_words = dm_div_up(from_cblock(mq->cache_size), BITS_PER_LONG); mq->find_free_last_word = 0; 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_entries = 2 * from_cblock(cache_size); r = alloc_entries(mq, mq->nr_entries); if (r) goto bad_cache_alloc; mq->nr_entries_allocated = 0; mq->nr_cblocks_allocated = 0; 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; mq->allocation_bitset = alloc_bitset(from_cblock(cache_size)); if (!mq->allocation_bitset) goto bad_alloc_bitset; return &mq->policy; bad_alloc_bitset: kfree(mq->table); bad_alloc_table: free_entries(mq); bad_cache_alloc: kfree(mq); return NULL; } /*----------------------------------------------------------------*/ static struct dm_cache_policy_type mq_policy_type = { .name = "mq", .version = {1, 0, 0}, .hint_size = 4, .owner = THIS_MODULE, .create = mq_create }; static struct dm_cache_policy_type default_policy_type = { .name = "default", .version = {1, 0, 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 "); MODULE_LICENSE("GPL"); MODULE_DESCRIPTION("mq cache policy"); MODULE_ALIAS("dm-cache-default");