drivers/md/dm-cache-policy-mq.c

   1 /*
   2  * Copyright (C) 2012 Red Hat. All rights reserved.
   3  *
   4  * This file is released under the GPL.
   5  */
   6
   7 #include "dm-cache-policy.h"
   8 #include "dm.h"
   9
  10 #include <linux/hash.h>
  11 #include <linux/module.h>
  12 #include <linux/mutex.h>
  13 #include <linux/slab.h>
  14 #include <linux/vmalloc.h>
  15
  16 #define DM_MSG_PREFIX "cache-policy-mq"
  17 #define MQ_VERSION      "1.0.0"
  18
  19 static struct kmem_cache *mq_entry_cache;
  20
  21 /*----------------------------------------------------------------*/
  22
  23 static unsigned next_power(unsigned n, unsigned min)
  24 {
  25         return roundup_pow_of_two(max(n, min));
  26 }
  27
  28 /*----------------------------------------------------------------*/
  29
  30 static unsigned long *alloc_bitset(unsigned nr_entries)
  31 {
  32         size_t s = sizeof(unsigned long) * dm_div_up(nr_entries, BITS_PER_LONG);
  33         return vzalloc(s);
  34 }
  35
  36 static void free_bitset(unsigned long *bits)
  37 {
  38         vfree(bits);
  39 }
  40
  41 /*----------------------------------------------------------------*/
  42
  43 /*
  44  * Large, sequential ios are probably better left on the origin device since
  45  * spindles tend to have good bandwidth.
  46  *
  47  * The io_tracker tries to spot when the io is in one of these sequential
  48  * modes.
  49  *
  50  * Two thresholds to switch between random and sequential io mode are defaulting
  51  * as follows and can be adjusted via the constructor and message interfaces.
  52  */
  53 #define RANDOM_THRESHOLD_DEFAULT 4
  54 #define SEQUENTIAL_THRESHOLD_DEFAULT 512
  55
  56 enum io_pattern {
  57         PATTERN_SEQUENTIAL,
  58         PATTERN_RANDOM
  59 };
  60
  61 struct io_tracker {
  62         enum io_pattern pattern;
  63
  64         unsigned nr_seq_samples;
  65         unsigned nr_rand_samples;
  66         unsigned thresholds[2];
  67
  68         dm_oblock_t last_end_oblock;
  69 };
  70
  71 static void iot_init(struct io_tracker *t,
  72                      int sequential_threshold, int random_threshold)
  73 {
  74         t->pattern = PATTERN_RANDOM;
  75         t->nr_seq_samples = 0;
  76         t->nr_rand_samples = 0;
  77         t->last_end_oblock = 0;
  78         t->thresholds[PATTERN_RANDOM] = random_threshold;
  79         t->thresholds[PATTERN_SEQUENTIAL] = sequential_threshold;
  80 }
  81
  82 static enum io_pattern iot_pattern(struct io_tracker *t)
  83 {
  84         return t->pattern;
  85 }
  86
  87 static void iot_update_stats(struct io_tracker *t, struct bio *bio)
  88 {
  89         if (bio->bi_sector == from_oblock(t->last_end_oblock) + 1)
  90                 t->nr_seq_samples++;
  91         else {
  92                 /*
  93                  * Just one non-sequential IO is enough to reset the
  94                  * counters.
  95                  */
  96                 if (t->nr_seq_samples) {
  97                         t->nr_seq_samples = 0;
  98                         t->nr_rand_samples = 0;
  99                 }
 100
 101                 t->nr_rand_samples++;
 102         }
 103
 104         t->last_end_oblock = to_oblock(bio->bi_sector + bio_sectors(bio) - 1);
 105 }
 106
 107 static void iot_check_for_pattern_switch(struct io_tracker *t)
 108 {
 109         switch (t->pattern) {
 110         case PATTERN_SEQUENTIAL:
 111                 if (t->nr_rand_samples >= t->thresholds[PATTERN_RANDOM]) {
 112                         t->pattern = PATTERN_RANDOM;
 113                         t->nr_seq_samples = t->nr_rand_samples = 0;
 114                 }
 115                 break;
 116
 117         case PATTERN_RANDOM:
 118                 if (t->nr_seq_samples >= t->thresholds[PATTERN_SEQUENTIAL]) {
 119                         t->pattern = PATTERN_SEQUENTIAL;
 120                         t->nr_seq_samples = t->nr_rand_samples = 0;
 121                 }
 122                 break;
 123         }
 124 }
 125
 126 static void iot_examine_bio(struct io_tracker *t, struct bio *bio)
 127 {
 128         iot_update_stats(t, bio);
 129         iot_check_for_pattern_switch(t);
 130 }
 131
 132 /*----------------------------------------------------------------*/
 133
 134
 135 /*
 136  * This queue is divided up into different levels.  Allowing us to push
 137  * entries to the back of any of the levels.  Think of it as a partially
 138  * sorted queue.
 139  */
 140 #define NR_QUEUE_LEVELS 16u
 141
 142 struct queue {
 143         struct list_head qs[NR_QUEUE_LEVELS];
 144 };
 145
 146 static void queue_init(struct queue *q)
 147 {
 148         unsigned i;
 149
 150         for (i = 0; i < NR_QUEUE_LEVELS; i++)
 151                 INIT_LIST_HEAD(q->qs + i);
 152 }
 153
 154 /*
 155  * Insert an entry to the back of the given level.
 156  */
 157 static void queue_push(struct queue *q, unsigned level, struct list_head *elt)
 158 {
 159         list_add_tail(elt, q->qs + level);
 160 }
 161
 162 static void queue_remove(struct list_head *elt)
 163 {
 164         list_del(elt);
 165 }
 166
 167 /*
 168  * Shifts all regions down one level.  This has no effect on the order of
 169  * the queue.
 170  */
 171 static void queue_shift_down(struct queue *q)
 172 {
 173         unsigned level;
 174
 175         for (level = 1; level < NR_QUEUE_LEVELS; level++)
 176                 list_splice_init(q->qs + level, q->qs + level - 1);
 177 }
 178
 179 /*
 180  * Gives us the oldest entry of the lowest popoulated level.  If the first
 181  * level is emptied then we shift down one level.
 182  */
 183 static struct list_head *queue_pop(struct queue *q)
 184 {
 185         unsigned level;
 186         struct list_head *r;
 187
 188         for (level = 0; level < NR_QUEUE_LEVELS; level++)
 189                 if (!list_empty(q->qs + level)) {
 190                         r = q->qs[level].next;
 191                         list_del(r);
 192
 193                         /* have we just emptied the bottom level? */
 194                         if (level == 0 && list_empty(q->qs))
 195                                 queue_shift_down(q);
 196
 197                         return r;
 198                 }
 199
 200         return NULL;
 201 }
 202
 203 static struct list_head *list_pop(struct list_head *lh)
 204 {
 205         struct list_head *r = lh->next;
 206
 207         BUG_ON(!r);
 208         list_del_init(r);
 209
 210         return r;
 211 }
 212
 213 /*----------------------------------------------------------------*/
 214
 215 /*
 216  * Describes a cache entry.  Used in both the cache and the pre_cache.
 217  */
 218 struct entry {
 219         struct hlist_node hlist;
 220         struct list_head list;
 221         dm_oblock_t oblock;
 222         dm_cblock_t cblock;     /* valid iff in_cache */
 223
 224         /*
 225          * FIXME: pack these better
 226          */
 227         bool in_cache:1;
 228         unsigned hit_count;
 229         unsigned generation;
 230         unsigned tick;
 231 };
 232
 233 struct mq_policy {
 234         struct dm_cache_policy policy;
 235
 236         /* protects everything */
 237         struct mutex lock;
 238         dm_cblock_t cache_size;
 239         struct io_tracker tracker;
 240
 241         /*
 242          * We maintain two queues of entries.  The cache proper contains
 243          * the currently active mappings.  Whereas the pre_cache tracks
 244          * blocks that are being hit frequently and potential candidates
 245          * for promotion to the cache.
 246          */
 247         struct queue pre_cache;
 248         struct queue cache;
 249
 250         /*
 251          * Keeps track of time, incremented by the core.  We use this to
 252          * avoid attributing multiple hits within the same tick.
 253          *
 254          * Access to tick_protected should be done with the spin lock held.
 255          * It's copied to tick at the start of the map function (within the
 256          * mutex).
 257          */
 258         spinlock_t tick_lock;
 259         unsigned tick_protected;
 260         unsigned tick;
 261
 262         /*
 263          * A count of the number of times the map function has been called
 264          * and found an entry in the pre_cache or cache.  Currently used to
 265          * calculate the generation.
 266          */
 267         unsigned hit_count;
 268
 269         /*
 270          * A generation is a longish period that is used to trigger some
 271          * book keeping effects.  eg, decrementing hit counts on entries.
 272          * This is needed to allow the cache to evolve as io patterns
 273          * change.
 274          */
 275         unsigned generation;
 276         unsigned generation_period; /* in lookups (will probably change) */
 277
 278         /*
 279          * Entries in the pre_cache whose hit count passes the promotion
 280          * threshold move to the cache proper.  Working out the correct
 281          * value for the promotion_threshold is crucial to this policy.
 282          */
 283         unsigned promote_threshold;
 284
 285         /*
 286          * We need cache_size entries for the cache, and choose to have
 287          * cache_size entries for the pre_cache too.  One motivation for
 288          * using the same size is to make the hit counts directly
 289          * comparable between pre_cache and cache.
 290          */
 291         unsigned nr_entries;
 292         unsigned nr_entries_allocated;
 293         struct list_head free;
 294
 295         /*
 296          * Cache blocks may be unallocated.  We store this info in a
 297          * bitset.
 298          */
 299         unsigned long *allocation_bitset;
 300         unsigned nr_cblocks_allocated;
 301         unsigned find_free_nr_words;
 302         unsigned find_free_last_word;
 303
 304         /*
 305          * The hash table allows us to quickly find an entry by origin
 306          * block.  Both pre_cache and cache entries are in here.
 307          */
 308         unsigned nr_buckets;
 309         dm_block_t hash_bits;
 310         struct hlist_head *table;
 311 };
 312
 313 /*----------------------------------------------------------------*/
 314 /* Free/alloc mq cache entry structures. */
 315 static void takeout_queue(struct list_head *lh, struct queue *q)
 316 {
 317         unsigned level;
 318
 319         for (level = 0; level < NR_QUEUE_LEVELS; level++)
 320                 list_splice(q->qs + level, lh);
 321 }
 322
 323 static void free_entries(struct mq_policy *mq)
 324 {
 325         struct entry *e, *tmp;
 326
 327         takeout_queue(&mq->free, &mq->pre_cache);
 328         takeout_queue(&mq->free, &mq->cache);
 329
 330         list_for_each_entry_safe(e, tmp, &mq->free, list)
 331                 kmem_cache_free(mq_entry_cache, e);
 332 }
 333
 334 static int alloc_entries(struct mq_policy *mq, unsigned elts)
 335 {
 336         unsigned u = mq->nr_entries;
 337
 338         INIT_LIST_HEAD(&mq->free);
 339         mq->nr_entries_allocated = 0;
 340
 341         while (u--) {
 342                 struct entry *e = kmem_cache_zalloc(mq_entry_cache, GFP_KERNEL);
 343
 344                 if (!e) {
 345                         free_entries(mq);
 346                         return -ENOMEM;
 347                 }
 348
 349
 350                 list_add(&e->list, &mq->free);
 351         }
 352
 353         return 0;
 354 }
 355
 356 /*----------------------------------------------------------------*/
 357
 358 /*
 359  * Simple hash table implementation.  Should replace with the standard hash
 360  * table that's making its way upstream.
 361  */
 362 static void hash_insert(struct mq_policy *mq, struct entry *e)
 363 {
 364         unsigned h = hash_64(from_oblock(e->oblock), mq->hash_bits);
 365
 366         hlist_add_head(&e->hlist, mq->table + h);
 367 }
 368
 369 static struct entry *hash_lookup(struct mq_policy *mq, dm_oblock_t oblock)
 370 {
 371         unsigned h = hash_64(from_oblock(oblock), mq->hash_bits);
 372         struct hlist_head *bucket = mq->table + h;
 373         struct entry *e;
 374
 375         hlist_for_each_entry(e, bucket, hlist)
 376                 if (e->oblock == oblock) {
 377                         hlist_del(&e->hlist);
 378                         hlist_add_head(&e->hlist, bucket);
 379                         return e;
 380                 }
 381
 382         return NULL;
 383 }
 384
 385 static void hash_remove(struct entry *e)
 386 {
 387         hlist_del(&e->hlist);
 388 }
 389
 390 /*----------------------------------------------------------------*/
 391
 392 /*
 393  * Allocates a new entry structure.  The memory is allocated in one lump,
 394  * so we just handing it out here.  Returns NULL if all entries have
 395  * already been allocated.  Cannot fail otherwise.
 396  */
 397 static struct entry *alloc_entry(struct mq_policy *mq)
 398 {
 399         struct entry *e;
 400
 401         if (mq->nr_entries_allocated >= mq->nr_entries) {
 402                 BUG_ON(!list_empty(&mq->free));
 403                 return NULL;
 404         }
 405
 406         e = list_entry(list_pop(&mq->free), struct entry, list);
 407         INIT_LIST_HEAD(&e->list);
 408         INIT_HLIST_NODE(&e->hlist);
 409
 410         mq->nr_entries_allocated++;
 411         return e;
 412 }
 413
 414 /*----------------------------------------------------------------*/
 415
 416 /*
 417  * Mark cache blocks allocated or not in the bitset.
 418  */
 419 static void alloc_cblock(struct mq_policy *mq, dm_cblock_t cblock)
 420 {
 421         BUG_ON(from_cblock(cblock) > from_cblock(mq->cache_size));
 422         BUG_ON(test_bit(from_cblock(cblock), mq->allocation_bitset));
 423
 424         set_bit(from_cblock(cblock), mq->allocation_bitset);
 425         mq->nr_cblocks_allocated++;
 426 }
 427
 428 static void free_cblock(struct mq_policy *mq, dm_cblock_t cblock)
 429 {
 430         BUG_ON(from_cblock(cblock) > from_cblock(mq->cache_size));
 431         BUG_ON(!test_bit(from_cblock(cblock), mq->allocation_bitset));
 432
 433         clear_bit(from_cblock(cblock), mq->allocation_bitset);
 434         mq->nr_cblocks_allocated--;
 435 }
 436
 437 static bool any_free_cblocks(struct mq_policy *mq)
 438 {
 439         return mq->nr_cblocks_allocated < from_cblock(mq->cache_size);
 440 }
 441
 442 /*
 443  * Fills result out with a cache block that isn't in use, or return
 444  * -ENOSPC.  This does _not_ mark the cblock as allocated, the caller is
 445  * reponsible for that.
 446  */
 447 static int __find_free_cblock(struct mq_policy *mq, unsigned begin, unsigned end,
 448                               dm_cblock_t *result, unsigned *last_word)
 449 {
 450         int r = -ENOSPC;
 451         unsigned w;
 452
 453         for (w = begin; w < end; w++) {
 454                 /*
 455                  * ffz is undefined if no zero exists
 456                  */
 457                 if (mq->allocation_bitset[w] != ~0UL) {
 458                         *last_word = w;
 459                         *result = to_cblock((w * BITS_PER_LONG) + ffz(mq->allocation_bitset[w]));
 460                         if (from_cblock(*result) < from_cblock(mq->cache_size))
 461                                 r = 0;
 462
 463                         break;
 464                 }
 465         }
 466
 467         return r;
 468 }
 469
 470 static int find_free_cblock(struct mq_policy *mq, dm_cblock_t *result)
 471 {
 472         int r;
 473
 474         if (!any_free_cblocks(mq))
 475                 return -ENOSPC;
 476
 477         r = __find_free_cblock(mq, mq->find_free_last_word, mq->find_free_nr_words, result, &mq->find_free_last_word);
 478         if (r == -ENOSPC && mq->find_free_last_word)
 479                 r = __find_free_cblock(mq, 0, mq->find_free_last_word, result, &mq->find_free_last_word);
 480
 481         return r;
 482 }
 483
 484 /*----------------------------------------------------------------*/
 485
 486 /*
 487  * Now we get to the meat of the policy.  This section deals with deciding
 488  * when to to add entries to the pre_cache and cache, and move between
 489  * them.
 490  */
 491
 492 /*
 493  * The queue level is based on the log2 of the hit count.
 494  */
 495 static unsigned queue_level(struct entry *e)
 496 {
 497         return min((unsigned) ilog2(e->hit_count), NR_QUEUE_LEVELS - 1u);
 498 }
 499
 500 /*
 501  * Inserts the entry into the pre_cache or the cache.  Ensures the cache
 502  * block is marked as allocated if necc.  Inserts into the hash table.  Sets the
 503  * tick which records when the entry was last moved about.
 504  */
 505 static void push(struct mq_policy *mq, struct entry *e)
 506 {
 507         e->tick = mq->tick;
 508         hash_insert(mq, e);
 509
 510         if (e->in_cache) {
 511                 alloc_cblock(mq, e->cblock);
 512                 queue_push(&mq->cache, queue_level(e), &e->list);
 513         } else
 514                 queue_push(&mq->pre_cache, queue_level(e), &e->list);
 515 }
 516
 517 /*
 518  * Removes an entry from pre_cache or cache.  Removes from the hash table.
 519  * Frees off the cache block if necc.
 520  */
 521 static void del(struct mq_policy *mq, struct entry *e)
 522 {
 523         queue_remove(&e->list);
 524         hash_remove(e);
 525         if (e->in_cache)
 526                 free_cblock(mq, e->cblock);
 527 }
 528
 529 /*
 530  * Like del, except it removes the first entry in the queue (ie. the least
 531  * recently used).
 532  */
 533 static struct entry *pop(struct mq_policy *mq, struct queue *q)
 534 {
 535         struct entry *e = container_of(queue_pop(q), struct entry, list);
 536
 537         if (e) {
 538                 hash_remove(e);
 539
 540                 if (e->in_cache)
 541                         free_cblock(mq, e->cblock);
 542         }
 543
 544         return e;
 545 }
 546
 547 /*
 548  * Has this entry already been updated?
 549  */
 550 static bool updated_this_tick(struct mq_policy *mq, struct entry *e)
 551 {
 552         return mq->tick == e->tick;
 553 }
 554
 555 /*
 556  * The promotion threshold is adjusted every generation.  As are the counts
 557  * of the entries.
 558  *
 559  * At the moment the threshold is taken by averaging the hit counts of some
 560  * of the entries in the cache (the first 20 entries of the first level).
 561  *
 562  * We can be much cleverer than this though.  For example, each promotion
 563  * could bump up the threshold helping to prevent churn.  Much more to do
 564  * here.
 565  */
 566
 567 #define MAX_TO_AVERAGE 20
 568
 569 static void check_generation(struct mq_policy *mq)
 570 {
 571         unsigned total = 0, nr = 0, count = 0, level;
 572         struct list_head *head;
 573         struct entry *e;
 574
 575         if ((mq->hit_count >= mq->generation_period) &&
 576             (mq->nr_cblocks_allocated == from_cblock(mq->cache_size))) {
 577
 578                 mq->hit_count = 0;
 579                 mq->generation++;
 580
 581                 for (level = 0; level < NR_QUEUE_LEVELS && count < MAX_TO_AVERAGE; level++) {
 582                         head = mq->cache.qs + level;
 583                         list_for_each_entry(e, head, list) {
 584                                 nr++;
 585                                 total += e->hit_count;
 586
 587                                 if (++count >= MAX_TO_AVERAGE)
 588                                         break;
 589                         }
 590                 }
 591
 592                 mq->promote_threshold = nr ? total / nr : 1;
 593                 if (mq->promote_threshold * nr < total)
 594                         mq->promote_threshold++;
 595         }
 596 }
 597
 598 /*
 599  * Whenever we use an entry we bump up it's hit counter, and push it to the
 600  * back to it's current level.
 601  */
 602 static void requeue_and_update_tick(struct mq_policy *mq, struct entry *e)
 603 {
 604         if (updated_this_tick(mq, e))
 605                 return;
 606
 607         e->hit_count++;
 608         mq->hit_count++;
 609         check_generation(mq);
 610
 611         /* generation adjustment, to stop the counts increasing forever. */
 612         /* FIXME: divide? */
 613         /* e->hit_count -= min(e->hit_count - 1, mq->generation - e->generation); */
 614         e->generation = mq->generation;
 615
 616         del(mq, e);
 617         push(mq, e);
 618 }
 619
 620 /*
 621  * Demote the least recently used entry from the cache to the pre_cache.
 622  * Returns the new cache entry to use, and the old origin block it was
 623  * mapped to.
 624  *
 625  * We drop the hit count on the demoted entry back to 1 to stop it bouncing
 626  * straight back into the cache if it's subsequently hit.  There are
 627  * various options here, and more experimentation would be good:
 628  *
 629  * - just forget about the demoted entry completely (ie. don't insert it
 630      into the pre_cache).
 631  * - divide the hit count rather that setting to some hard coded value.
 632  * - set the hit count to a hard coded value other than 1, eg, is it better
 633  *   if it goes in at level 2?
 634  */
 635 static dm_cblock_t demote_cblock(struct mq_policy *mq, dm_oblock_t *oblock)
 636 {
 637         dm_cblock_t result;
 638         struct entry *demoted = pop(mq, &mq->cache);
 639
 640         BUG_ON(!demoted);
 641         result = demoted->cblock;
 642         *oblock = demoted->oblock;
 643         demoted->in_cache = false;
 644         demoted->hit_count = 1;
 645         push(mq, demoted);
 646
 647         return result;
 648 }
 649
 650 /*
 651  * We modify the basic promotion_threshold depending on the specific io.
 652  *
 653  * If the origin block has been discarded then there's no cost to copy it
 654  * to the cache.
 655  *
 656  * We bias towards reads, since they can be demoted at no cost if they
 657  * haven't been dirtied.
 658  */
 659 #define DISCARDED_PROMOTE_THRESHOLD 1
 660 #define READ_PROMOTE_THRESHOLD 4
 661 #define WRITE_PROMOTE_THRESHOLD 8
 662
 663 static unsigned adjusted_promote_threshold(struct mq_policy *mq,
 664                                            bool discarded_oblock, int data_dir)
 665 {
 666         if (discarded_oblock && any_free_cblocks(mq) && data_dir == WRITE)
 667                 /*
 668                  * We don't need to do any copying at all, so give this a
 669                  * very low threshold.  In practice this only triggers
 670                  * during initial population after a format.
 671                  */
 672                 return DISCARDED_PROMOTE_THRESHOLD;
 673
 674         return data_dir == READ ?
 675                 (mq->promote_threshold + READ_PROMOTE_THRESHOLD) :
 676                 (mq->promote_threshold + WRITE_PROMOTE_THRESHOLD);
 677 }
 678
 679 static bool should_promote(struct mq_policy *mq, struct entry *e,
 680                            bool discarded_oblock, int data_dir)
 681 {
 682         return e->hit_count >=
 683                 adjusted_promote_threshold(mq, discarded_oblock, data_dir);
 684 }
 685
 686 static int cache_entry_found(struct mq_policy *mq,
 687                              struct entry *e,
 688                              struct policy_result *result)
 689 {
 690         requeue_and_update_tick(mq, e);
 691
 692         if (e->in_cache) {
 693                 result->op = POLICY_HIT;
 694                 result->cblock = e->cblock;
 695         }
 696
 697         return 0;
 698 }
 699
 700 /*
 701  * Moves and entry from the pre_cache to the cache.  The main work is
 702  * finding which cache block to use.
 703  */
 704 static int pre_cache_to_cache(struct mq_policy *mq, struct entry *e,
 705                               struct policy_result *result)
 706 {
 707         dm_cblock_t cblock;
 708
 709         if (find_free_cblock(mq, &cblock) == -ENOSPC) {
 710                 result->op = POLICY_REPLACE;
 711                 cblock = demote_cblock(mq, &result->old_oblock);
 712         } else
 713                 result->op = POLICY_NEW;
 714
 715         result->cblock = e->cblock = cblock;
 716
 717         del(mq, e);
 718         e->in_cache = true;
 719         push(mq, e);
 720
 721         return 0;
 722 }
 723
 724 static int pre_cache_entry_found(struct mq_policy *mq, struct entry *e,
 725                                  bool can_migrate, bool discarded_oblock,
 726                                  int data_dir, struct policy_result *result)
 727 {
 728         int r = 0;
 729         bool updated = updated_this_tick(mq, e);
 730
 731         requeue_and_update_tick(mq, e);
 732
 733         if ((!discarded_oblock && updated) ||
 734             !should_promote(mq, e, discarded_oblock, data_dir))
 735                 result->op = POLICY_MISS;
 736         else if (!can_migrate)
 737                 r = -EWOULDBLOCK;
 738         else
 739                 r = pre_cache_to_cache(mq, e, result);
 740
 741         return r;
 742 }
 743
 744 static void insert_in_pre_cache(struct mq_policy *mq,
 745                                 dm_oblock_t oblock)
 746 {
 747         struct entry *e = alloc_entry(mq);
 748
 749         if (!e)
 750                 /*
 751                  * There's no spare entry structure, so we grab the least
 752                  * used one from the pre_cache.
 753                  */
 754                 e = pop(mq, &mq->pre_cache);
 755
 756         if (unlikely(!e)) {
 757                 DMWARN("couldn't pop from pre cache");
 758                 return;
 759         }
 760
 761         e->in_cache = false;
 762         e->oblock = oblock;
 763         e->hit_count = 1;
 764         e->generation = mq->generation;
 765         push(mq, e);
 766 }
 767
 768 static void insert_in_cache(struct mq_policy *mq, dm_oblock_t oblock,
 769                             struct policy_result *result)
 770 {
 771         struct entry *e;
 772         dm_cblock_t cblock;
 773
 774         if (find_free_cblock(mq, &cblock) == -ENOSPC) {
 775                 result->op = POLICY_MISS;
 776                 insert_in_pre_cache(mq, oblock);
 777                 return;
 778         }
 779
 780         e = alloc_entry(mq);
 781         if (unlikely(!e)) {
 782                 result->op = POLICY_MISS;
 783                 return;
 784         }
 785
 786         e->oblock = oblock;
 787         e->cblock = cblock;
 788         e->in_cache = true;
 789         e->hit_count = 1;
 790         e->generation = mq->generation;
 791         push(mq, e);
 792
 793         result->op = POLICY_NEW;
 794         result->cblock = e->cblock;
 795 }
 796
 797 static int no_entry_found(struct mq_policy *mq, dm_oblock_t oblock,
 798                           bool can_migrate, bool discarded_oblock,
 799                           int data_dir, struct policy_result *result)
 800 {
 801         if (adjusted_promote_threshold(mq, discarded_oblock, data_dir) == 1) {
 802                 if (can_migrate)
 803                         insert_in_cache(mq, oblock, result);
 804                 else
 805                         return -EWOULDBLOCK;
 806         } else {
 807                 insert_in_pre_cache(mq, oblock);
 808                 result->op = POLICY_MISS;
 809         }
 810
 811         return 0;
 812 }
 813
 814 /*
 815  * Looks the oblock up in the hash table, then decides whether to put in
 816  * pre_cache, or cache etc.
 817  */
 818 static int map(struct mq_policy *mq, dm_oblock_t oblock,
 819                bool can_migrate, bool discarded_oblock,
 820                int data_dir, struct policy_result *result)
 821 {
 822         int r = 0;
 823         struct entry *e = hash_lookup(mq, oblock);
 824
 825         if (e && e->in_cache)
 826                 r = cache_entry_found(mq, e, result);
 827         else if (iot_pattern(&mq->tracker) == PATTERN_SEQUENTIAL)
 828                 result->op = POLICY_MISS;
 829         else if (e)
 830                 r = pre_cache_entry_found(mq, e, can_migrate, discarded_oblock,
 831                                           data_dir, result);
 832         else
 833                 r = no_entry_found(mq, oblock, can_migrate, discarded_oblock,
 834                                    data_dir, result);
 835
 836         if (r == -EWOULDBLOCK)
 837                 result->op = POLICY_MISS;
 838
 839         return r;
 840 }
 841
 842 /*----------------------------------------------------------------*/
 843
 844 /*
 845  * Public interface, via the policy struct.  See dm-cache-policy.h for a
 846  * description of these.
 847  */
 848
 849 static struct mq_policy *to_mq_policy(struct dm_cache_policy *p)
 850 {
 851         return container_of(p, struct mq_policy, policy);
 852 }
 853
 854 static void mq_destroy(struct dm_cache_policy *p)
 855 {
 856         struct mq_policy *mq = to_mq_policy(p);
 857
 858         free_bitset(mq->allocation_bitset);
 859         kfree(mq->table);
 860         free_entries(mq);
 861         kfree(mq);
 862 }
 863
 864 static void copy_tick(struct mq_policy *mq)
 865 {
 866         unsigned long flags;
 867
 868         spin_lock_irqsave(&mq->tick_lock, flags);
 869         mq->tick = mq->tick_protected;
 870         spin_unlock_irqrestore(&mq->tick_lock, flags);
 871 }
 872
 873 static int mq_map(struct dm_cache_policy *p, dm_oblock_t oblock,
 874                   bool can_block, bool can_migrate, bool discarded_oblock,
 875                   struct bio *bio, struct policy_result *result)
 876 {
 877         int r;
 878         struct mq_policy *mq = to_mq_policy(p);
 879
 880         result->op = POLICY_MISS;
 881
 882         if (can_block)
 883                 mutex_lock(&mq->lock);
 884         else if (!mutex_trylock(&mq->lock))
 885                 return -EWOULDBLOCK;
 886
 887         copy_tick(mq);
 888
 889         iot_examine_bio(&mq->tracker, bio);
 890         r = map(mq, oblock, can_migrate, discarded_oblock,
 891                 bio_data_dir(bio), result);
 892
 893         mutex_unlock(&mq->lock);
 894
 895         return r;
 896 }
 897
 898 static int mq_lookup(struct dm_cache_policy *p, dm_oblock_t oblock, dm_cblock_t *cblock)
 899 {
 900         int r;
 901         struct mq_policy *mq = to_mq_policy(p);
 902         struct entry *e;
 903
 904         if (!mutex_trylock(&mq->lock))
 905                 return -EWOULDBLOCK;
 906
 907         e = hash_lookup(mq, oblock);
 908         if (e && e->in_cache) {
 909                 *cblock = e->cblock;
 910                 r = 0;
 911         } else
 912                 r = -ENOENT;
 913
 914         mutex_unlock(&mq->lock);
 915
 916         return r;
 917 }
 918
 919 static int mq_load_mapping(struct dm_cache_policy *p,
 920                            dm_oblock_t oblock, dm_cblock_t cblock,
 921                            uint32_t hint, bool hint_valid)
 922 {
 923         struct mq_policy *mq = to_mq_policy(p);
 924         struct entry *e;
 925
 926         e = alloc_entry(mq);
 927         if (!e)
 928                 return -ENOMEM;
 929
 930         e->cblock = cblock;
 931         e->oblock = oblock;
 932         e->in_cache = true;
 933         e->hit_count = hint_valid ? hint : 1;
 934         e->generation = mq->generation;
 935         push(mq, e);
 936
 937         return 0;
 938 }
 939
 940 static int mq_walk_mappings(struct dm_cache_policy *p, policy_walk_fn fn,
 941                             void *context)
 942 {
 943         struct mq_policy *mq = to_mq_policy(p);
 944         int r = 0;
 945         struct entry *e;
 946         unsigned level;
 947
 948         mutex_lock(&mq->lock);
 949
 950         for (level = 0; level < NR_QUEUE_LEVELS; level++)
 951                 list_for_each_entry(e, &mq->cache.qs[level], list) {
 952                         r = fn(context, e->cblock, e->oblock, e->hit_count);
 953                         if (r)
 954                                 goto out;
 955                 }
 956
 957 out:
 958         mutex_unlock(&mq->lock);
 959
 960         return r;
 961 }
 962
 963 static void remove_mapping(struct mq_policy *mq, dm_oblock_t oblock)
 964 {
 965         struct entry *e = hash_lookup(mq, oblock);
 966
 967         BUG_ON(!e || !e->in_cache);
 968
 969         del(mq, e);
 970         e->in_cache = false;
 971         push(mq, e);
 972 }
 973
 974 static void mq_remove_mapping(struct dm_cache_policy *p, dm_oblock_t oblock)
 975 {
 976         struct mq_policy *mq = to_mq_policy(p);
 977
 978         mutex_lock(&mq->lock);
 979         remove_mapping(mq, oblock);
 980         mutex_unlock(&mq->lock);
 981 }
 982
 983 static void force_mapping(struct mq_policy *mq,
 984                           dm_oblock_t current_oblock, dm_oblock_t new_oblock)
 985 {
 986         struct entry *e = hash_lookup(mq, current_oblock);
 987
 988         BUG_ON(!e || !e->in_cache);
 989
 990         del(mq, e);
 991         e->oblock = new_oblock;
 992         push(mq, e);
 993 }
 994
 995 static void mq_force_mapping(struct dm_cache_policy *p,
 996                              dm_oblock_t current_oblock, dm_oblock_t new_oblock)
 997 {
 998         struct mq_policy *mq = to_mq_policy(p);
 999
1000         mutex_lock(&mq->lock);
1001         force_mapping(mq, current_oblock, new_oblock);
1002         mutex_unlock(&mq->lock);
1003 }
1004
1005 static dm_cblock_t mq_residency(struct dm_cache_policy *p)
1006 {
1007         struct mq_policy *mq = to_mq_policy(p);
1008
1009         /* FIXME: lock mutex, not sure we can block here */
1010         return to_cblock(mq->nr_cblocks_allocated);
1011 }
1012
1013 static void mq_tick(struct dm_cache_policy *p)
1014 {
1015         struct mq_policy *mq = to_mq_policy(p);
1016         unsigned long flags;
1017
1018         spin_lock_irqsave(&mq->tick_lock, flags);
1019         mq->tick_protected++;
1020         spin_unlock_irqrestore(&mq->tick_lock, flags);
1021 }
1022
1023 static int mq_set_config_value(struct dm_cache_policy *p,
1024                                const char *key, const char *value)
1025 {
1026         struct mq_policy *mq = to_mq_policy(p);
1027         enum io_pattern pattern;
1028         unsigned long tmp;
1029
1030         if (!strcasecmp(key, "random_threshold"))
1031                 pattern = PATTERN_RANDOM;
1032         else if (!strcasecmp(key, "sequential_threshold"))
1033                 pattern = PATTERN_SEQUENTIAL;
1034         else
1035                 return -EINVAL;
1036
1037         if (kstrtoul(value, 10, &tmp))
1038                 return -EINVAL;
1039
1040         mq->tracker.thresholds[pattern] = tmp;
1041
1042         return 0;
1043 }
1044
1045 static int mq_emit_config_values(struct dm_cache_policy *p, char *result, unsigned maxlen)
1046 {
1047         ssize_t sz = 0;
1048         struct mq_policy *mq = to_mq_policy(p);
1049
1050         DMEMIT("4 random_threshold %u sequential_threshold %u",
1051                mq->tracker.thresholds[PATTERN_RANDOM],
1052                mq->tracker.thresholds[PATTERN_SEQUENTIAL]);
1053
1054         return 0;
1055 }
1056
1057 /* Init the policy plugin interface function pointers. */
1058 static void init_policy_functions(struct mq_policy *mq)
1059 {
1060         mq->policy.destroy = mq_destroy;
1061         mq->policy.map = mq_map;
1062         mq->policy.lookup = mq_lookup;
1063         mq->policy.load_mapping = mq_load_mapping;
1064         mq->policy.walk_mappings = mq_walk_mappings;
1065         mq->policy.remove_mapping = mq_remove_mapping;
1066         mq->policy.writeback_work = NULL;
1067         mq->policy.force_mapping = mq_force_mapping;
1068         mq->policy.residency = mq_residency;
1069         mq->policy.tick = mq_tick;
1070         mq->policy.emit_config_values = mq_emit_config_values;
1071         mq->policy.set_config_value = mq_set_config_value;
1072 }
1073
1074 static struct dm_cache_policy *mq_create(dm_cblock_t cache_size,
1075                                          sector_t origin_size,
1076                                          sector_t cache_block_size)
1077 {
1078         int r;
1079         struct mq_policy *mq = kzalloc(sizeof(*mq), GFP_KERNEL);
1080
1081         if (!mq)
1082                 return NULL;
1083
1084         init_policy_functions(mq);
1085         iot_init(&mq->tracker, SEQUENTIAL_THRESHOLD_DEFAULT, RANDOM_THRESHOLD_DEFAULT);
1086
1087         mq->cache_size = cache_size;
1088         mq->tick_protected = 0;
1089         mq->tick = 0;
1090         mq->hit_count = 0;
1091         mq->generation = 0;
1092         mq->promote_threshold = 0;
1093         mutex_init(&mq->lock);
1094         spin_lock_init(&mq->tick_lock);
1095         mq->find_free_nr_words = dm_div_up(from_cblock(mq->cache_size), BITS_PER_LONG);
1096         mq->find_free_last_word = 0;
1097
1098         queue_init(&mq->pre_cache);
1099         queue_init(&mq->cache);
1100         mq->generation_period = max((unsigned) from_cblock(cache_size), 1024U);
1101
1102         mq->nr_entries = 2 * from_cblock(cache_size);
1103         r = alloc_entries(mq, mq->nr_entries);
1104         if (r)
1105                 goto bad_cache_alloc;
1106
1107         mq->nr_entries_allocated = 0;
1108         mq->nr_cblocks_allocated = 0;
1109
1110         mq->nr_buckets = next_power(from_cblock(cache_size) / 2, 16);
1111         mq->hash_bits = ffs(mq->nr_buckets) - 1;
1112         mq->table = kzalloc(sizeof(*mq->table) * mq->nr_buckets, GFP_KERNEL);
1113         if (!mq->table)
1114                 goto bad_alloc_table;
1115
1116         mq->allocation_bitset = alloc_bitset(from_cblock(cache_size));
1117         if (!mq->allocation_bitset)
1118                 goto bad_alloc_bitset;
1119
1120         return &mq->policy;
1121
1122 bad_alloc_bitset:
1123         kfree(mq->table);
1124 bad_alloc_table:
1125         free_entries(mq);
1126 bad_cache_alloc:
1127         kfree(mq);
1128
1129         return NULL;
1130 }
1131
1132 /*----------------------------------------------------------------*/
1133
1134 static struct dm_cache_policy_type mq_policy_type = {
1135         .name = "mq",
1136         .hint_size = 4,
1137         .owner = THIS_MODULE,
1138         .create = mq_create
1139 };
1140
1141 static struct dm_cache_policy_type default_policy_type = {
1142         .name = "default",
1143         .hint_size = 4,
1144         .owner = THIS_MODULE,
1145         .create = mq_create
1146 };
1147
1148 static int __init mq_init(void)
1149 {
1150         int r;
1151
1152         mq_entry_cache = kmem_cache_create("dm_mq_policy_cache_entry",
1153                                            sizeof(struct entry),
1154                                            __alignof__(struct entry),
1155                                            0, NULL);
1156         if (!mq_entry_cache)
1157                 goto bad;
1158
1159         r = dm_cache_policy_register(&mq_policy_type);
1160         if (r) {
1161                 DMERR("register failed %d", r);
1162                 goto bad_register_mq;
1163         }
1164
1165         r = dm_cache_policy_register(&default_policy_type);
1166         if (!r) {
1167                 DMINFO("version " MQ_VERSION " loaded");
1168                 return 0;
1169         }
1170
1171         DMERR("register failed (as default) %d", r);
1172
1173         dm_cache_policy_unregister(&mq_policy_type);
1174 bad_register_mq:
1175         kmem_cache_destroy(mq_entry_cache);
1176 bad:
1177         return -ENOMEM;
1178 }
1179
1180 static void __exit mq_exit(void)
1181 {
1182         dm_cache_policy_unregister(&mq_policy_type);
1183         dm_cache_policy_unregister(&default_policy_type);
1184
1185         kmem_cache_destroy(mq_entry_cache);
1186 }
1187
1188 module_init(mq_init);
1189 module_exit(mq_exit);
1190
1191 MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
1192 MODULE_LICENSE("GPL");
1193 MODULE_DESCRIPTION("mq cache policy");
1194
1195 MODULE_ALIAS("dm-cache-default");