kernel/drivers/md/dm-cache-policy-cleaner.c

   1 /*
   2  * Copyright (C) 2012 Red Hat. All rights reserved.
   3  *
   4  * writeback cache policy supporting flushing out dirty cache blocks.
   5  *
   6  * This file is released under the GPL.
   7  */
   8
   9 #include "dm-cache-policy.h"
  10 #include "dm.h"
  11
  12 #include <linux/hash.h>
  13 #include <linux/module.h>
  14 #include <linux/slab.h>
  15 #include <linux/vmalloc.h>
  16
  17 /*----------------------------------------------------------------*/
  18
  19 #define DM_MSG_PREFIX "cache cleaner"
  20
  21 /* Cache entry struct. */
  22 struct wb_cache_entry {
  23         struct list_head list;
  24         struct hlist_node hlist;
  25
  26         dm_oblock_t oblock;
  27         dm_cblock_t cblock;
  28         bool dirty:1;
  29         bool pending:1;
  30 };
  31
  32 struct hash {
  33         struct hlist_head *table;
  34         dm_block_t hash_bits;
  35         unsigned nr_buckets;
  36 };
  37
  38 struct policy {
  39         struct dm_cache_policy policy;
  40         spinlock_t lock;
  41
  42         struct list_head free;
  43         struct list_head clean;
  44         struct list_head clean_pending;
  45         struct list_head dirty;
  46
  47         /*
  48          * We know exactly how many cblocks will be needed,
  49          * so we can allocate them up front.
  50          */
  51         dm_cblock_t cache_size, nr_cblocks_allocated;
  52         struct wb_cache_entry *cblocks;
  53         struct hash chash;
  54 };
  55
  56 /*----------------------------------------------------------------------------*/
  57
  58 /*
  59  * Low-level functions.
  60  */
  61 static unsigned next_power(unsigned n, unsigned min)
  62 {
  63         return roundup_pow_of_two(max(n, min));
  64 }
  65
  66 static struct policy *to_policy(struct dm_cache_policy *p)
  67 {
  68         return container_of(p, struct policy, policy);
  69 }
  70
  71 static struct list_head *list_pop(struct list_head *q)
  72 {
  73         struct list_head *r = q->next;
  74
  75         list_del(r);
  76
  77         return r;
  78 }
  79
  80 /*----------------------------------------------------------------------------*/
  81
  82 /* Allocate/free various resources. */
  83 static int alloc_hash(struct hash *hash, unsigned elts)
  84 {
  85         hash->nr_buckets = next_power(elts >> 4, 16);
  86         hash->hash_bits = ffs(hash->nr_buckets) - 1;
  87         hash->table = vzalloc(sizeof(*hash->table) * hash->nr_buckets);
  88
  89         return hash->table ? 0 : -ENOMEM;
  90 }
  91
  92 static void free_hash(struct hash *hash)
  93 {
  94         vfree(hash->table);
  95 }
  96
  97 static int alloc_cache_blocks_with_hash(struct policy *p, dm_cblock_t cache_size)
  98 {
  99         int r = -ENOMEM;
 100
 101         p->cblocks = vzalloc(sizeof(*p->cblocks) * from_cblock(cache_size));
 102         if (p->cblocks) {
 103                 unsigned u = from_cblock(cache_size);
 104
 105                 while (u--)
 106                         list_add(&p->cblocks[u].list, &p->free);
 107
 108                 p->nr_cblocks_allocated = 0;
 109
 110                 /* Cache entries hash. */
 111                 r = alloc_hash(&p->chash, from_cblock(cache_size));
 112                 if (r)
 113                         vfree(p->cblocks);
 114         }
 115
 116         return r;
 117 }
 118
 119 static void free_cache_blocks_and_hash(struct policy *p)
 120 {
 121         free_hash(&p->chash);
 122         vfree(p->cblocks);
 123 }
 124
 125 static struct wb_cache_entry *alloc_cache_entry(struct policy *p)
 126 {
 127         struct wb_cache_entry *e;
 128
 129         BUG_ON(from_cblock(p->nr_cblocks_allocated) >= from_cblock(p->cache_size));
 130
 131         e = list_entry(list_pop(&p->free), struct wb_cache_entry, list);
 132         p->nr_cblocks_allocated = to_cblock(from_cblock(p->nr_cblocks_allocated) + 1);
 133
 134         return e;
 135 }
 136
 137 /*----------------------------------------------------------------------------*/
 138
 139 /* Hash functions (lookup, insert, remove). */
 140 static struct wb_cache_entry *lookup_cache_entry(struct policy *p, dm_oblock_t oblock)
 141 {
 142         struct hash *hash = &p->chash;
 143         unsigned h = hash_64(from_oblock(oblock), hash->hash_bits);
 144         struct wb_cache_entry *cur;
 145         struct hlist_head *bucket = &hash->table[h];
 146
 147         hlist_for_each_entry(cur, bucket, hlist) {
 148                 if (cur->oblock == oblock) {
 149                         /* Move upfront bucket for faster access. */
 150                         hlist_del(&cur->hlist);
 151                         hlist_add_head(&cur->hlist, bucket);
 152                         return cur;
 153                 }
 154         }
 155
 156         return NULL;
 157 }
 158
 159 static void insert_cache_hash_entry(struct policy *p, struct wb_cache_entry *e)
 160 {
 161         unsigned h = hash_64(from_oblock(e->oblock), p->chash.hash_bits);
 162
 163         hlist_add_head(&e->hlist, &p->chash.table[h]);
 164 }
 165
 166 static void remove_cache_hash_entry(struct wb_cache_entry *e)
 167 {
 168         hlist_del(&e->hlist);
 169 }
 170
 171 /* Public interface (see dm-cache-policy.h */
 172 static int wb_map(struct dm_cache_policy *pe, dm_oblock_t oblock,
 173                   bool can_block, bool can_migrate, bool discarded_oblock,
 174                   struct bio *bio, struct policy_result *result)
 175 {
 176         struct policy *p = to_policy(pe);
 177         struct wb_cache_entry *e;
 178         unsigned long flags;
 179
 180         result->op = POLICY_MISS;
 181
 182         if (can_block)
 183                 spin_lock_irqsave(&p->lock, flags);
 184
 185         else if (!spin_trylock_irqsave(&p->lock, flags))
 186                 return -EWOULDBLOCK;
 187
 188         e = lookup_cache_entry(p, oblock);
 189         if (e) {
 190                 result->op = POLICY_HIT;
 191                 result->cblock = e->cblock;
 192
 193         }
 194
 195         spin_unlock_irqrestore(&p->lock, flags);
 196
 197         return 0;
 198 }
 199
 200 static int wb_lookup(struct dm_cache_policy *pe, dm_oblock_t oblock, dm_cblock_t *cblock)
 201 {
 202         int r;
 203         struct policy *p = to_policy(pe);
 204         struct wb_cache_entry *e;
 205         unsigned long flags;
 206
 207         if (!spin_trylock_irqsave(&p->lock, flags))
 208                 return -EWOULDBLOCK;
 209
 210         e = lookup_cache_entry(p, oblock);
 211         if (e) {
 212                 *cblock = e->cblock;
 213                 r = 0;
 214
 215         } else
 216                 r = -ENOENT;
 217
 218         spin_unlock_irqrestore(&p->lock, flags);
 219
 220         return r;
 221 }
 222
 223 static void __set_clear_dirty(struct dm_cache_policy *pe, dm_oblock_t oblock, bool set)
 224 {
 225         struct policy *p = to_policy(pe);
 226         struct wb_cache_entry *e;
 227
 228         e = lookup_cache_entry(p, oblock);
 229         BUG_ON(!e);
 230
 231         if (set) {
 232                 if (!e->dirty) {
 233                         e->dirty = true;
 234                         list_move(&e->list, &p->dirty);
 235                 }
 236
 237         } else {
 238                 if (e->dirty) {
 239                         e->pending = false;
 240                         e->dirty = false;
 241                         list_move(&e->list, &p->clean);
 242                 }
 243         }
 244 }
 245
 246 static void wb_set_dirty(struct dm_cache_policy *pe, dm_oblock_t oblock)
 247 {
 248         struct policy *p = to_policy(pe);
 249         unsigned long flags;
 250
 251         spin_lock_irqsave(&p->lock, flags);
 252         __set_clear_dirty(pe, oblock, true);
 253         spin_unlock_irqrestore(&p->lock, flags);
 254 }
 255
 256 static void wb_clear_dirty(struct dm_cache_policy *pe, dm_oblock_t oblock)
 257 {
 258         struct policy *p = to_policy(pe);
 259         unsigned long flags;
 260
 261         spin_lock_irqsave(&p->lock, flags);
 262         __set_clear_dirty(pe, oblock, false);
 263         spin_unlock_irqrestore(&p->lock, flags);
 264 }
 265
 266 static void add_cache_entry(struct policy *p, struct wb_cache_entry *e)
 267 {
 268         insert_cache_hash_entry(p, e);
 269         if (e->dirty)
 270                 list_add(&e->list, &p->dirty);
 271         else
 272                 list_add(&e->list, &p->clean);
 273 }
 274
 275 static int wb_load_mapping(struct dm_cache_policy *pe,
 276                            dm_oblock_t oblock, dm_cblock_t cblock,
 277                            uint32_t hint, bool hint_valid)
 278 {
 279         int r;
 280         struct policy *p = to_policy(pe);
 281         struct wb_cache_entry *e = alloc_cache_entry(p);
 282
 283         if (e) {
 284                 e->cblock = cblock;
 285                 e->oblock = oblock;
 286                 e->dirty = false; /* blocks default to clean */
 287                 add_cache_entry(p, e);
 288                 r = 0;
 289
 290         } else
 291                 r = -ENOMEM;
 292
 293         return r;
 294 }
 295
 296 static void wb_destroy(struct dm_cache_policy *pe)
 297 {
 298         struct policy *p = to_policy(pe);
 299
 300         free_cache_blocks_and_hash(p);
 301         kfree(p);
 302 }
 303
 304 static struct wb_cache_entry *__wb_force_remove_mapping(struct policy *p, dm_oblock_t oblock)
 305 {
 306         struct wb_cache_entry *r = lookup_cache_entry(p, oblock);
 307
 308         BUG_ON(!r);
 309
 310         remove_cache_hash_entry(r);
 311         list_del(&r->list);
 312
 313         return r;
 314 }
 315
 316 static void wb_remove_mapping(struct dm_cache_policy *pe, dm_oblock_t oblock)
 317 {
 318         struct policy *p = to_policy(pe);
 319         struct wb_cache_entry *e;
 320         unsigned long flags;
 321
 322         spin_lock_irqsave(&p->lock, flags);
 323         e = __wb_force_remove_mapping(p, oblock);
 324         list_add_tail(&e->list, &p->free);
 325         BUG_ON(!from_cblock(p->nr_cblocks_allocated));
 326         p->nr_cblocks_allocated = to_cblock(from_cblock(p->nr_cblocks_allocated) - 1);
 327         spin_unlock_irqrestore(&p->lock, flags);
 328 }
 329
 330 static void wb_force_mapping(struct dm_cache_policy *pe,
 331                                 dm_oblock_t current_oblock, dm_oblock_t oblock)
 332 {
 333         struct policy *p = to_policy(pe);
 334         struct wb_cache_entry *e;
 335         unsigned long flags;
 336
 337         spin_lock_irqsave(&p->lock, flags);
 338         e = __wb_force_remove_mapping(p, current_oblock);
 339         e->oblock = oblock;
 340         add_cache_entry(p, e);
 341         spin_unlock_irqrestore(&p->lock, flags);
 342 }
 343
 344 static struct wb_cache_entry *get_next_dirty_entry(struct policy *p)
 345 {
 346         struct list_head *l;
 347         struct wb_cache_entry *r;
 348
 349         if (list_empty(&p->dirty))
 350                 return NULL;
 351
 352         l = list_pop(&p->dirty);
 353         r = container_of(l, struct wb_cache_entry, list);
 354         list_add(l, &p->clean_pending);
 355
 356         return r;
 357 }
 358
 359 static int wb_writeback_work(struct dm_cache_policy *pe,
 360                              dm_oblock_t *oblock,
 361                              dm_cblock_t *cblock)
 362 {
 363         int r = -ENOENT;
 364         struct policy *p = to_policy(pe);
 365         struct wb_cache_entry *e;
 366         unsigned long flags;
 367
 368         spin_lock_irqsave(&p->lock, flags);
 369
 370         e = get_next_dirty_entry(p);
 371         if (e) {
 372                 *oblock = e->oblock;
 373                 *cblock = e->cblock;
 374                 r = 0;
 375         }
 376
 377         spin_unlock_irqrestore(&p->lock, flags);
 378
 379         return r;
 380 }
 381
 382 static dm_cblock_t wb_residency(struct dm_cache_policy *pe)
 383 {
 384         return to_policy(pe)->nr_cblocks_allocated;
 385 }
 386
 387 /* Init the policy plugin interface function pointers. */
 388 static void init_policy_functions(struct policy *p)
 389 {
 390         p->policy.destroy = wb_destroy;
 391         p->policy.map = wb_map;
 392         p->policy.lookup = wb_lookup;
 393         p->policy.set_dirty = wb_set_dirty;
 394         p->policy.clear_dirty = wb_clear_dirty;
 395         p->policy.load_mapping = wb_load_mapping;
 396         p->policy.walk_mappings = NULL;
 397         p->policy.remove_mapping = wb_remove_mapping;
 398         p->policy.writeback_work = wb_writeback_work;
 399         p->policy.force_mapping = wb_force_mapping;
 400         p->policy.residency = wb_residency;
 401         p->policy.tick = NULL;
 402 }
 403
 404 static struct dm_cache_policy *wb_create(dm_cblock_t cache_size,
 405                                          sector_t origin_size,
 406                                          sector_t cache_block_size)
 407 {
 408         int r;
 409         struct policy *p = kzalloc(sizeof(*p), GFP_KERNEL);
 410
 411         if (!p)
 412                 return NULL;
 413
 414         init_policy_functions(p);
 415         INIT_LIST_HEAD(&p->free);
 416         INIT_LIST_HEAD(&p->clean);
 417         INIT_LIST_HEAD(&p->clean_pending);
 418         INIT_LIST_HEAD(&p->dirty);
 419
 420         p->cache_size = cache_size;
 421         spin_lock_init(&p->lock);
 422
 423         /* Allocate cache entry structs and add them to free list. */
 424         r = alloc_cache_blocks_with_hash(p, cache_size);
 425         if (!r)
 426                 return &p->policy;
 427
 428         kfree(p);
 429
 430         return NULL;
 431 }
 432 /*----------------------------------------------------------------------------*/
 433
 434 static struct dm_cache_policy_type wb_policy_type = {
 435         .name = "cleaner",
 436         .version = {1, 0, 0},
 437         .hint_size = 0,
 438         .owner = THIS_MODULE,
 439         .create = wb_create
 440 };
 441
 442 static int __init wb_init(void)
 443 {
 444         int r = dm_cache_policy_register(&wb_policy_type);
 445
 446         if (r < 0)
 447                 DMERR("register failed %d", r);
 448         else
 449                 DMINFO("version %u.%u.%u loaded",
 450                        wb_policy_type.version[0],
 451                        wb_policy_type.version[1],
 452                        wb_policy_type.version[2]);
 453
 454         return r;
 455 }
 456
 457 static void __exit wb_exit(void)
 458 {
 459         dm_cache_policy_unregister(&wb_policy_type);
 460 }
 461
 462 module_init(wb_init);
 463 module_exit(wb_exit);
 464
 465 MODULE_AUTHOR("Heinz Mauelshagen <dm-devel@redhat.com>");
 466 MODULE_LICENSE("GPL");
 467 MODULE_DESCRIPTION("cleaner cache policy");