2 * Copyright (C) 2012 Red Hat. All rights reserved.
4 * writeback cache policy supporting flushing out dirty cache blocks.
6 * This file is released under the GPL.
9 #include "dm-cache-policy.h"
12 #include <linux/hash.h>
13 #include <linux/module.h>
14 #include <linux/slab.h>
15 #include <linux/vmalloc.h>
17 /*----------------------------------------------------------------*/
19 #define DM_MSG_PREFIX "cache cleaner"
20 #define CLEANER_VERSION "1.0.0"
22 /* Cache entry struct. */
23 struct wb_cache_entry {
24 struct list_head list;
25 struct hlist_node hlist;
34 struct hlist_head *table;
40 struct dm_cache_policy policy;
43 struct list_head free;
44 struct list_head clean;
45 struct list_head clean_pending;
46 struct list_head dirty;
49 * We know exactly how many cblocks will be needed,
50 * so we can allocate them up front.
52 dm_cblock_t cache_size, nr_cblocks_allocated;
53 struct wb_cache_entry *cblocks;
57 /*----------------------------------------------------------------------------*/
60 * Low-level functions.
62 static unsigned next_power(unsigned n, unsigned min)
64 return roundup_pow_of_two(max(n, min));
67 static struct policy *to_policy(struct dm_cache_policy *p)
69 return container_of(p, struct policy, policy);
72 static struct list_head *list_pop(struct list_head *q)
74 struct list_head *r = q->next;
81 /*----------------------------------------------------------------------------*/
83 /* Allocate/free various resources. */
84 static int alloc_hash(struct hash *hash, unsigned elts)
86 hash->nr_buckets = next_power(elts >> 4, 16);
87 hash->hash_bits = ffs(hash->nr_buckets) - 1;
88 hash->table = vzalloc(sizeof(*hash->table) * hash->nr_buckets);
90 return hash->table ? 0 : -ENOMEM;
93 static void free_hash(struct hash *hash)
98 static int alloc_cache_blocks_with_hash(struct policy *p, dm_cblock_t cache_size)
102 p->cblocks = vzalloc(sizeof(*p->cblocks) * from_cblock(cache_size));
104 unsigned u = from_cblock(cache_size);
107 list_add(&p->cblocks[u].list, &p->free);
109 p->nr_cblocks_allocated = 0;
111 /* Cache entries hash. */
112 r = alloc_hash(&p->chash, from_cblock(cache_size));
120 static void free_cache_blocks_and_hash(struct policy *p)
122 free_hash(&p->chash);
126 static struct wb_cache_entry *alloc_cache_entry(struct policy *p)
128 struct wb_cache_entry *e;
130 BUG_ON(from_cblock(p->nr_cblocks_allocated) >= from_cblock(p->cache_size));
132 e = list_entry(list_pop(&p->free), struct wb_cache_entry, list);
133 p->nr_cblocks_allocated = to_cblock(from_cblock(p->nr_cblocks_allocated) + 1);
138 /*----------------------------------------------------------------------------*/
140 /* Hash functions (lookup, insert, remove). */
141 static struct wb_cache_entry *lookup_cache_entry(struct policy *p, dm_oblock_t oblock)
143 struct hash *hash = &p->chash;
144 unsigned h = hash_64(from_oblock(oblock), hash->hash_bits);
145 struct wb_cache_entry *cur;
146 struct hlist_head *bucket = &hash->table[h];
148 hlist_for_each_entry(cur, bucket, hlist) {
149 if (cur->oblock == oblock) {
150 /* Move upfront bucket for faster access. */
151 hlist_del(&cur->hlist);
152 hlist_add_head(&cur->hlist, bucket);
160 static void insert_cache_hash_entry(struct policy *p, struct wb_cache_entry *e)
162 unsigned h = hash_64(from_oblock(e->oblock), p->chash.hash_bits);
164 hlist_add_head(&e->hlist, &p->chash.table[h]);
167 static void remove_cache_hash_entry(struct wb_cache_entry *e)
169 hlist_del(&e->hlist);
172 /* Public interface (see dm-cache-policy.h */
173 static int wb_map(struct dm_cache_policy *pe, dm_oblock_t oblock,
174 bool can_block, bool can_migrate, bool discarded_oblock,
175 struct bio *bio, struct policy_result *result)
177 struct policy *p = to_policy(pe);
178 struct wb_cache_entry *e;
181 result->op = POLICY_MISS;
184 spin_lock_irqsave(&p->lock, flags);
186 else if (!spin_trylock_irqsave(&p->lock, flags))
189 e = lookup_cache_entry(p, oblock);
191 result->op = POLICY_HIT;
192 result->cblock = e->cblock;
196 spin_unlock_irqrestore(&p->lock, flags);
201 static int wb_lookup(struct dm_cache_policy *pe, dm_oblock_t oblock, dm_cblock_t *cblock)
204 struct policy *p = to_policy(pe);
205 struct wb_cache_entry *e;
208 if (!spin_trylock_irqsave(&p->lock, flags))
211 e = lookup_cache_entry(p, oblock);
219 spin_unlock_irqrestore(&p->lock, flags);
224 static void __set_clear_dirty(struct dm_cache_policy *pe, dm_oblock_t oblock, bool set)
226 struct policy *p = to_policy(pe);
227 struct wb_cache_entry *e;
229 e = lookup_cache_entry(p, oblock);
235 list_move(&e->list, &p->dirty);
242 list_move(&e->list, &p->clean);
247 static void wb_set_dirty(struct dm_cache_policy *pe, dm_oblock_t oblock)
249 struct policy *p = to_policy(pe);
252 spin_lock_irqsave(&p->lock, flags);
253 __set_clear_dirty(pe, oblock, true);
254 spin_unlock_irqrestore(&p->lock, flags);
257 static void wb_clear_dirty(struct dm_cache_policy *pe, dm_oblock_t oblock)
259 struct policy *p = to_policy(pe);
262 spin_lock_irqsave(&p->lock, flags);
263 __set_clear_dirty(pe, oblock, false);
264 spin_unlock_irqrestore(&p->lock, flags);
267 static void add_cache_entry(struct policy *p, struct wb_cache_entry *e)
269 insert_cache_hash_entry(p, e);
271 list_add(&e->list, &p->dirty);
273 list_add(&e->list, &p->clean);
276 static int wb_load_mapping(struct dm_cache_policy *pe,
277 dm_oblock_t oblock, dm_cblock_t cblock,
278 uint32_t hint, bool hint_valid)
281 struct policy *p = to_policy(pe);
282 struct wb_cache_entry *e = alloc_cache_entry(p);
287 e->dirty = false; /* blocks default to clean */
288 add_cache_entry(p, e);
297 static void wb_destroy(struct dm_cache_policy *pe)
299 struct policy *p = to_policy(pe);
301 free_cache_blocks_and_hash(p);
305 static struct wb_cache_entry *__wb_force_remove_mapping(struct policy *p, dm_oblock_t oblock)
307 struct wb_cache_entry *r = lookup_cache_entry(p, oblock);
311 remove_cache_hash_entry(r);
317 static void wb_remove_mapping(struct dm_cache_policy *pe, dm_oblock_t oblock)
319 struct policy *p = to_policy(pe);
320 struct wb_cache_entry *e;
323 spin_lock_irqsave(&p->lock, flags);
324 e = __wb_force_remove_mapping(p, oblock);
325 list_add_tail(&e->list, &p->free);
326 BUG_ON(!from_cblock(p->nr_cblocks_allocated));
327 p->nr_cblocks_allocated = to_cblock(from_cblock(p->nr_cblocks_allocated) - 1);
328 spin_unlock_irqrestore(&p->lock, flags);
331 static void wb_force_mapping(struct dm_cache_policy *pe,
332 dm_oblock_t current_oblock, dm_oblock_t oblock)
334 struct policy *p = to_policy(pe);
335 struct wb_cache_entry *e;
338 spin_lock_irqsave(&p->lock, flags);
339 e = __wb_force_remove_mapping(p, current_oblock);
341 add_cache_entry(p, e);
342 spin_unlock_irqrestore(&p->lock, flags);
345 static struct wb_cache_entry *get_next_dirty_entry(struct policy *p)
348 struct wb_cache_entry *r;
350 if (list_empty(&p->dirty))
353 l = list_pop(&p->dirty);
354 r = container_of(l, struct wb_cache_entry, list);
355 list_add(l, &p->clean_pending);
360 static int wb_writeback_work(struct dm_cache_policy *pe,
365 struct policy *p = to_policy(pe);
366 struct wb_cache_entry *e;
369 spin_lock_irqsave(&p->lock, flags);
371 e = get_next_dirty_entry(p);
378 spin_unlock_irqrestore(&p->lock, flags);
383 static dm_cblock_t wb_residency(struct dm_cache_policy *pe)
385 return to_policy(pe)->nr_cblocks_allocated;
388 /* Init the policy plugin interface function pointers. */
389 static void init_policy_functions(struct policy *p)
391 p->policy.destroy = wb_destroy;
392 p->policy.map = wb_map;
393 p->policy.lookup = wb_lookup;
394 p->policy.set_dirty = wb_set_dirty;
395 p->policy.clear_dirty = wb_clear_dirty;
396 p->policy.load_mapping = wb_load_mapping;
397 p->policy.walk_mappings = NULL;
398 p->policy.remove_mapping = wb_remove_mapping;
399 p->policy.writeback_work = wb_writeback_work;
400 p->policy.force_mapping = wb_force_mapping;
401 p->policy.residency = wb_residency;
402 p->policy.tick = NULL;
405 static struct dm_cache_policy *wb_create(dm_cblock_t cache_size,
406 sector_t origin_size,
407 sector_t cache_block_size)
410 struct policy *p = kzalloc(sizeof(*p), GFP_KERNEL);
415 init_policy_functions(p);
416 INIT_LIST_HEAD(&p->free);
417 INIT_LIST_HEAD(&p->clean);
418 INIT_LIST_HEAD(&p->clean_pending);
419 INIT_LIST_HEAD(&p->dirty);
421 p->cache_size = cache_size;
422 spin_lock_init(&p->lock);
424 /* Allocate cache entry structs and add them to free list. */
425 r = alloc_cache_blocks_with_hash(p, cache_size);
433 /*----------------------------------------------------------------------------*/
435 static struct dm_cache_policy_type wb_policy_type = {
438 .owner = THIS_MODULE,
442 static int __init wb_init(void)
444 int r = dm_cache_policy_register(&wb_policy_type);
447 DMERR("register failed %d", r);
449 DMINFO("version " CLEANER_VERSION " loaded");
454 static void __exit wb_exit(void)
456 dm_cache_policy_unregister(&wb_policy_type);
459 module_init(wb_init);
460 module_exit(wb_exit);
462 MODULE_AUTHOR("Heinz Mauelshagen <dm-devel@redhat.com>");
463 MODULE_LICENSE("GPL");
464 MODULE_DESCRIPTION("cleaner cache policy");