]> git.kernelconcepts.de Git - karo-tx-linux.git/blobdiff - drivers/md/dm-cache-policy-mq.c
dm cache policy mq: reduce memory requirements
[karo-tx-linux.git] / drivers / md / dm-cache-policy-mq.c
index 444f0bf10b21292b84a35766f52ea4812fba104e..782bf854666ab361503df8c1e29a60f17132ded3 100644 (file)
@@ -26,19 +26,6 @@ static unsigned next_power(unsigned n, unsigned 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.
@@ -233,18 +220,107 @@ 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;
 };
 
+/*
+ * 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);
+}
+
+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;
 
@@ -253,6 +329,13 @@ struct mq_policy {
        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
@@ -299,25 +382,6 @@ struct mq_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.
@@ -327,50 +391,6 @@ struct mq_policy {
        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;
-}
-
 /*----------------------------------------------------------------*/
 
 /*
@@ -407,54 +427,9 @@ static void hash_remove(struct entry *e)
 
 /*----------------------------------------------------------------*/
 
-/*
- * 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);
+       return !epool_empty(&mq->cache_pool);
 }
 
 static bool any_clean_cblocks(struct mq_policy *mq)
@@ -462,48 +437,6 @@ 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;
-}
-
 /*----------------------------------------------------------------*/
 
 /*
@@ -520,34 +453,35 @@ 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.
+ * 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);
+       if (in_cache(mq, e))
                queue_push(e->dirty ? &mq->cache_dirty : &mq->cache_clean,
                           queue_level(e), &e->list);
-       else
+       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);
 }
 
 /*
@@ -564,8 +498,6 @@ static struct entry *pop(struct mq_policy *mq, struct queue *q)
 
        e = container_of(h, struct entry, list);
        hash_remove(e);
-       if (e->in_cache)
-               free_cblock(mq, e->cblock);
 
        return e;
 }
@@ -599,9 +531,7 @@ static void check_generation(struct mq_policy *mq)
        struct list_head *head;
        struct entry *e;
 
-       if ((mq->hit_count >= mq->generation_period) &&
-           (mq->nr_cblocks_allocated == from_cblock(mq->cache_size))) {
-
+       if ((mq->hit_count >= mq->generation_period) && (epool_empty(&mq->cache_pool))) {
                mq->hit_count = 0;
                mq->generation++;
 
@@ -668,7 +598,7 @@ static void requeue_and_update_tick(struct mq_policy *mq, struct entry *e)
  * - 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)
+static int demote_cblock(struct mq_policy *mq, dm_oblock_t *oblock)
 {
        struct entry *demoted = pop(mq, &mq->cache_clean);
 
@@ -682,12 +612,14 @@ static int demote_cblock(struct mq_policy *mq, dm_oblock_t *oblock, dm_cblock_t
                 */
                return -ENOSPC;
 
-       *cblock = demoted->cblock;
        *oblock = demoted->oblock;
-       demoted->in_cache = false;
-       demoted->dirty = false;
-       demoted->hit_count = 1;
-       push(mq, demoted);
+       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;
 }
@@ -735,9 +667,9 @@ static int cache_entry_found(struct mq_policy *mq,
 {
        requeue_and_update_tick(mq, e);
 
-       if (e->in_cache) {
+       if (in_cache(mq, e)) {
                result->op = POLICY_HIT;
-               result->cblock = e->cblock;
+               result->cblock = infer_cblock(&mq->cache_pool, e);
        }
 
        return 0;
@@ -751,11 +683,12 @@ static int pre_cache_to_cache(struct mq_policy *mq, struct entry *e,
                              struct policy_result *result)
 {
        int r;
-       dm_cblock_t cblock;
+       struct entry *new_e;
 
-       if (find_free_cblock(mq, &cblock) == -ENOSPC) {
+       /* 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, &cblock);
+               r = demote_cblock(mq, &result->old_oblock);
                if (r) {
                        result->op = POLICY_MISS;
                        return 0;
@@ -763,12 +696,20 @@ static int pre_cache_to_cache(struct mq_policy *mq, struct entry *e,
        } else
                result->op = POLICY_NEW;
 
-       result->cblock = e->cblock = cblock;
+       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);
-       e->in_cache = true;
-       e->dirty = false;
-       push(mq, e);
+       free_entry(&mq->pre_cache_pool, e);
+       push(mq, new_e);
+
+       result->cblock = infer_cblock(&mq->cache_pool, new_e);
 
        return 0;
 }
@@ -793,21 +734,10 @@ static int pre_cache_entry_found(struct mq_policy *mq, struct entry *e,
        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);
+       struct entry *e = alloc_entry(&mq->pre_cache_pool);
 
        if (!e)
                /*
@@ -821,7 +751,11 @@ static void insert_in_pre_cache(struct mq_policy *mq,
                return;
        }
 
-       insert_entry_in_pre_cache(mq, e, oblock);
+       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,
@@ -829,10 +763,10 @@ static void insert_in_cache(struct mq_policy *mq, dm_oblock_t oblock,
 {
        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 (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);
@@ -842,31 +776,21 @@ static void insert_in_cache(struct mq_policy *mq, dm_oblock_t oblock,
                /*
                 * This will always succeed, since we've just demoted.
                 */
-               e = pop(mq, &mq->pre_cache);
-               result->op = POLICY_REPLACE;
+               e = alloc_entry(&mq->cache_pool);
+               BUG_ON(!e);
 
        } else {
-               e = alloc_entry(mq);
-               if (unlikely(!e))
-                       e = pop(mq, &mq->pre_cache);
-
-               if (unlikely(!e)) {
-                       result->op = POLICY_MISS;
-                       return;
-               }
-
+               e = alloc_entry(&mq->cache_pool);
                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;
+       result->cblock = infer_cblock(&mq->cache_pool, e);
 }
 
 static int no_entry_found(struct mq_policy *mq, dm_oblock_t oblock,
@@ -897,13 +821,16 @@ static int map(struct mq_policy *mq, dm_oblock_t oblock,
        int r = 0;
        struct entry *e = hash_lookup(mq, oblock);
 
-       if (e && e->in_cache)
+       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);
@@ -930,9 +857,9 @@ 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);
+       epool_exit(&mq->cache_pool);
+       epool_exit(&mq->pre_cache_pool);
        kfree(mq);
 }
 
@@ -980,8 +907,8 @@ static int mq_lookup(struct dm_cache_policy *p, dm_oblock_t oblock, dm_cblock_t
                return -EWOULDBLOCK;
 
        e = hash_lookup(mq, oblock);
-       if (e && e->in_cache) {
-               *cblock = e->cblock;
+       if (e && in_cache(mq, e)) {
+               *cblock = infer_cblock(&mq->cache_pool, e);
                r = 0;
        } else
                r = -ENOENT;
@@ -991,38 +918,34 @@ static int mq_lookup(struct dm_cache_policy *p, dm_oblock_t oblock, dm_cblock_t
        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)
+static void __mq_set_clear_dirty(struct mq_policy *mq, 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);
+       BUG_ON(!e || !in_cache(mq, e));
 
-               del(mq, e);
-               e->dirty = set;
-               push(mq, e);
-       }
-       mutex_unlock(&mq->lock);
+       del(mq, e);
+       e->dirty = set;
+       push(mq, e);
 }
 
 static void mq_set_dirty(struct dm_cache_policy *p, dm_oblock_t oblock)
 {
-       __mq_set_clear_dirty(p, oblock, true);
+       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)
 {
-       __mq_set_clear_dirty(p, oblock, false);
+       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,
@@ -1032,13 +955,8 @@ static int mq_load_mapping(struct dm_cache_policy *p,
        struct mq_policy *mq = to_mq_policy(p);
        struct entry *e;
 
-       e = alloc_entry(mq);
-       if (!e)
-               return -ENOMEM;
-
-       e->cblock = cblock;
+       e = alloc_particular_entry(&mq->cache_pool, 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;
@@ -1047,52 +965,58 @@ static int mq_load_mapping(struct dm_cache_policy *p,
        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;
-       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;
-               }
+       r = mq_save_hints(mq, &mq->cache_clean, fn, context);
+       if (!r)
+               r = mq_save_hints(mq, &mq->cache_dirty, fn, context);
 
-out:
        mutex_unlock(&mq->lock);
 
        return r;
 }
 
-static void mq_remove_mapping(struct dm_cache_policy *p, dm_oblock_t oblock)
+static void __remove_mapping(struct mq_policy *mq, 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);
+       BUG_ON(!e || !in_cache(mq, e));
 
        del(mq, e);
-       e->in_cache = false;
-       e->dirty = false;
-       push(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);
 }
 
@@ -1105,7 +1029,7 @@ static int __mq_writeback_work(struct mq_policy *mq, dm_oblock_t *oblock,
                return -ENODATA;
 
        *oblock = e->oblock;
-       *cblock = e->cblock;
+       *cblock = infer_cblock(&mq->cache_pool, e);
        e->dirty = false;
        push(mq, e);
 
@@ -1125,17 +1049,17 @@ static int mq_writeback_work(struct dm_cache_policy *p, dm_oblock_t *oblock,
        return r;
 }
 
-static void force_mapping(struct mq_policy *mq,
-                         dm_oblock_t current_oblock, dm_oblock_t new_oblock)
+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);
+       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,
@@ -1144,7 +1068,7 @@ static void mq_force_mapping(struct dm_cache_policy *p,
        struct mq_policy *mq = to_mq_policy(p);
 
        mutex_lock(&mq->lock);
-       force_mapping(mq, current_oblock, new_oblock);
+       __force_mapping(mq, current_oblock, new_oblock);
        mutex_unlock(&mq->lock);
 }
 
@@ -1154,7 +1078,7 @@ static dm_cblock_t mq_residency(struct dm_cache_policy *p)
        struct mq_policy *mq = to_mq_policy(p);
 
        mutex_lock(&mq->lock);
-       r = to_cblock(mq->nr_cblocks_allocated);
+       r = to_cblock(mq->cache_pool.nr_allocated);
        mutex_unlock(&mq->lock);
 
        return r;
@@ -1227,7 +1151,6 @@ 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)
@@ -1235,8 +1158,18 @@ static struct dm_cache_policy *mq_create(dm_cblock_t cache_size,
 
        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;
@@ -1244,8 +1177,6 @@ static struct dm_cache_policy *mq_create(dm_cblock_t cache_size,
        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);
@@ -1253,31 +1184,19 @@ static struct dm_cache_policy *mq_create(dm_cblock_t cache_size,
 
        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:
+       epool_exit(&mq->cache_pool);
+bad_cache_init:
+       epool_exit(&mq->pre_cache_pool);
+bad_pre_cache_init:
        kfree(mq);
 
        return NULL;
@@ -1287,7 +1206,7 @@ bad_cache_alloc:
 
 static struct dm_cache_policy_type mq_policy_type = {
        .name = "mq",
-       .version = {1, 0, 0},
+       .version = {1, 1, 0},
        .hint_size = 4,
        .owner = THIS_MODULE,
        .create = mq_create
@@ -1295,7 +1214,7 @@ static struct dm_cache_policy_type mq_policy_type = {
 
 static struct dm_cache_policy_type default_policy_type = {
        .name = "default",
-       .version = {1, 0, 0},
+       .version = {1, 1, 0},
        .hint_size = 4,
        .owner = THIS_MODULE,
        .create = mq_create