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

   1 /*
   2  * Copyright (C) 2015 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-cache-policy-internal.h"
   9 #include "dm.h"
  10
  11 #include <linux/hash.h>
  12 #include <linux/jiffies.h>
  13 #include <linux/module.h>
  14 #include <linux/mutex.h>
  15 #include <linux/vmalloc.h>
  16 #include <linux/math64.h>
  17
  18 #define DM_MSG_PREFIX "cache-policy-smq"
  19
  20 /*----------------------------------------------------------------*/
  21
  22 /*
  23  * Safe division functions that return zero on divide by zero.
  24  */
  25 static unsigned safe_div(unsigned n, unsigned d)
  26 {
  27         return d ? n / d : 0u;
  28 }
  29
  30 static unsigned safe_mod(unsigned n, unsigned d)
  31 {
  32         return d ? n % d : 0u;
  33 }
  34
  35 /*----------------------------------------------------------------*/
  36
  37 struct entry {
  38         unsigned hash_next:28;
  39         unsigned prev:28;
  40         unsigned next:28;
  41         unsigned level:7;
  42         bool dirty:1;
  43         bool allocated:1;
  44         bool sentinel:1;
  45
  46         dm_oblock_t oblock;
  47 };
  48
  49 /*----------------------------------------------------------------*/
  50
  51 #define INDEXER_NULL ((1u << 28u) - 1u)
  52
  53 /*
  54  * An entry_space manages a set of entries that we use for the queues.
  55  * The clean and dirty queues share entries, so this object is separate
  56  * from the queue itself.
  57  */
  58 struct entry_space {
  59         struct entry *begin;
  60         struct entry *end;
  61 };
  62
  63 static int space_init(struct entry_space *es, unsigned nr_entries)
  64 {
  65         if (!nr_entries) {
  66                 es->begin = es->end = NULL;
  67                 return 0;
  68         }
  69
  70         es->begin = vzalloc(sizeof(struct entry) * nr_entries);
  71         if (!es->begin)
  72                 return -ENOMEM;
  73
  74         es->end = es->begin + nr_entries;
  75         return 0;
  76 }
  77
  78 static void space_exit(struct entry_space *es)
  79 {
  80         vfree(es->begin);
  81 }
  82
  83 static struct entry *__get_entry(struct entry_space *es, unsigned block)
  84 {
  85         struct entry *e;
  86
  87         e = es->begin + block;
  88         BUG_ON(e >= es->end);
  89
  90         return e;
  91 }
  92
  93 static unsigned to_index(struct entry_space *es, struct entry *e)
  94 {
  95         BUG_ON(e < es->begin || e >= es->end);
  96         return e - es->begin;
  97 }
  98
  99 static struct entry *to_entry(struct entry_space *es, unsigned block)
 100 {
 101         if (block == INDEXER_NULL)
 102                 return NULL;
 103
 104         return __get_entry(es, block);
 105 }
 106
 107 /*----------------------------------------------------------------*/
 108
 109 struct ilist {
 110         unsigned nr_elts;       /* excluding sentinel entries */
 111         unsigned head, tail;
 112 };
 113
 114 static void l_init(struct ilist *l)
 115 {
 116         l->nr_elts = 0;
 117         l->head = l->tail = INDEXER_NULL;
 118 }
 119
 120 static struct entry *l_head(struct entry_space *es, struct ilist *l)
 121 {
 122         return to_entry(es, l->head);
 123 }
 124
 125 static struct entry *l_tail(struct entry_space *es, struct ilist *l)
 126 {
 127         return to_entry(es, l->tail);
 128 }
 129
 130 static struct entry *l_next(struct entry_space *es, struct entry *e)
 131 {
 132         return to_entry(es, e->next);
 133 }
 134
 135 static struct entry *l_prev(struct entry_space *es, struct entry *e)
 136 {
 137         return to_entry(es, e->prev);
 138 }
 139
 140 static bool l_empty(struct ilist *l)
 141 {
 142         return l->head == INDEXER_NULL;
 143 }
 144
 145 static void l_add_head(struct entry_space *es, struct ilist *l, struct entry *e)
 146 {
 147         struct entry *head = l_head(es, l);
 148
 149         e->next = l->head;
 150         e->prev = INDEXER_NULL;
 151
 152         if (head)
 153                 head->prev = l->head = to_index(es, e);
 154         else
 155                 l->head = l->tail = to_index(es, e);
 156
 157         if (!e->sentinel)
 158                 l->nr_elts++;
 159 }
 160
 161 static void l_add_tail(struct entry_space *es, struct ilist *l, struct entry *e)
 162 {
 163         struct entry *tail = l_tail(es, l);
 164
 165         e->next = INDEXER_NULL;
 166         e->prev = l->tail;
 167
 168         if (tail)
 169                 tail->next = l->tail = to_index(es, e);
 170         else
 171                 l->head = l->tail = to_index(es, e);
 172
 173         if (!e->sentinel)
 174                 l->nr_elts++;
 175 }
 176
 177 static void l_add_before(struct entry_space *es, struct ilist *l,
 178                          struct entry *old, struct entry *e)
 179 {
 180         struct entry *prev = l_prev(es, old);
 181
 182         if (!prev)
 183                 l_add_head(es, l, e);
 184
 185         else {
 186                 e->prev = old->prev;
 187                 e->next = to_index(es, old);
 188                 prev->next = old->prev = to_index(es, e);
 189
 190                 if (!e->sentinel)
 191                         l->nr_elts++;
 192         }
 193 }
 194
 195 static void l_del(struct entry_space *es, struct ilist *l, struct entry *e)
 196 {
 197         struct entry *prev = l_prev(es, e);
 198         struct entry *next = l_next(es, e);
 199
 200         if (prev)
 201                 prev->next = e->next;
 202         else
 203                 l->head = e->next;
 204
 205         if (next)
 206                 next->prev = e->prev;
 207         else
 208                 l->tail = e->prev;
 209
 210         if (!e->sentinel)
 211                 l->nr_elts--;
 212 }
 213
 214 static struct entry *l_pop_tail(struct entry_space *es, struct ilist *l)
 215 {
 216         struct entry *e;
 217
 218         for (e = l_tail(es, l); e; e = l_prev(es, e))
 219                 if (!e->sentinel) {
 220                         l_del(es, l, e);
 221                         return e;
 222                 }
 223
 224         return NULL;
 225 }
 226
 227 /*----------------------------------------------------------------*/
 228
 229 /*
 230  * The stochastic-multi-queue is a set of lru lists stacked into levels.
 231  * Entries are moved up levels when they are used, which loosely orders the
 232  * most accessed entries in the top levels and least in the bottom.  This
 233  * structure is *much* better than a single lru list.
 234  */
 235 #define MAX_LEVELS 64u
 236
 237 struct queue {
 238         struct entry_space *es;
 239
 240         unsigned nr_elts;
 241         unsigned nr_levels;
 242         struct ilist qs[MAX_LEVELS];
 243
 244         /*
 245          * We maintain a count of the number of entries we would like in each
 246          * level.
 247          */
 248         unsigned last_target_nr_elts;
 249         unsigned nr_top_levels;
 250         unsigned nr_in_top_levels;
 251         unsigned target_count[MAX_LEVELS];
 252 };
 253
 254 static void q_init(struct queue *q, struct entry_space *es, unsigned nr_levels)
 255 {
 256         unsigned i;
 257
 258         q->es = es;
 259         q->nr_elts = 0;
 260         q->nr_levels = nr_levels;
 261
 262         for (i = 0; i < q->nr_levels; i++) {
 263                 l_init(q->qs + i);
 264                 q->target_count[i] = 0u;
 265         }
 266
 267         q->last_target_nr_elts = 0u;
 268         q->nr_top_levels = 0u;
 269         q->nr_in_top_levels = 0u;
 270 }
 271
 272 static unsigned q_size(struct queue *q)
 273 {
 274         return q->nr_elts;
 275 }
 276
 277 /*
 278  * Insert an entry to the back of the given level.
 279  */
 280 static void q_push(struct queue *q, struct entry *e)
 281 {
 282         if (!e->sentinel)
 283                 q->nr_elts++;
 284
 285         l_add_tail(q->es, q->qs + e->level, e);
 286 }
 287
 288 static void q_push_before(struct queue *q, struct entry *old, struct entry *e)
 289 {
 290         if (!e->sentinel)
 291                 q->nr_elts++;
 292
 293         l_add_before(q->es, q->qs + e->level, old, e);
 294 }
 295
 296 static void q_del(struct queue *q, struct entry *e)
 297 {
 298         l_del(q->es, q->qs + e->level, e);
 299         if (!e->sentinel)
 300                 q->nr_elts--;
 301 }
 302
 303 /*
 304  * Return the oldest entry of the lowest populated level.
 305  */
 306 static struct entry *q_peek(struct queue *q, unsigned max_level, bool can_cross_sentinel)
 307 {
 308         unsigned level;
 309         struct entry *e;
 310
 311         max_level = min(max_level, q->nr_levels);
 312
 313         for (level = 0; level < max_level; level++)
 314                 for (e = l_head(q->es, q->qs + level); e; e = l_next(q->es, e)) {
 315                         if (e->sentinel) {
 316                                 if (can_cross_sentinel)
 317                                         continue;
 318                                 else
 319                                         break;
 320                         }
 321
 322                         return e;
 323                 }
 324
 325         return NULL;
 326 }
 327
 328 static struct entry *q_pop(struct queue *q)
 329 {
 330         struct entry *e = q_peek(q, q->nr_levels, true);
 331
 332         if (e)
 333                 q_del(q, e);
 334
 335         return e;
 336 }
 337
 338 /*
 339  * Pops an entry from a level that is not past a sentinel.
 340  */
 341 static struct entry *q_pop_old(struct queue *q, unsigned max_level)
 342 {
 343         struct entry *e = q_peek(q, max_level, false);
 344
 345         if (e)
 346                 q_del(q, e);
 347
 348         return e;
 349 }
 350
 351 /*
 352  * This function assumes there is a non-sentinel entry to pop.  It's only
 353  * used by redistribute, so we know this is true.  It also doesn't adjust
 354  * the q->nr_elts count.
 355  */
 356 static struct entry *__redist_pop_from(struct queue *q, unsigned level)
 357 {
 358         struct entry *e;
 359
 360         for (; level < q->nr_levels; level++)
 361                 for (e = l_head(q->es, q->qs + level); e; e = l_next(q->es, e))
 362                         if (!e->sentinel) {
 363                                 l_del(q->es, q->qs + e->level, e);
 364                                 return e;
 365                         }
 366
 367         return NULL;
 368 }
 369
 370 static void q_set_targets_subrange_(struct queue *q, unsigned nr_elts, unsigned lbegin, unsigned lend)
 371 {
 372         unsigned level, nr_levels, entries_per_level, remainder;
 373
 374         BUG_ON(lbegin > lend);
 375         BUG_ON(lend > q->nr_levels);
 376         nr_levels = lend - lbegin;
 377         entries_per_level = safe_div(nr_elts, nr_levels);
 378         remainder = safe_mod(nr_elts, nr_levels);
 379
 380         for (level = lbegin; level < lend; level++)
 381                 q->target_count[level] =
 382                         (level < (lbegin + remainder)) ? entries_per_level + 1u : entries_per_level;
 383 }
 384
 385 /*
 386  * Typically we have fewer elements in the top few levels which allows us
 387  * to adjust the promote threshold nicely.
 388  */
 389 static void q_set_targets(struct queue *q)
 390 {
 391         if (q->last_target_nr_elts == q->nr_elts)
 392                 return;
 393
 394         q->last_target_nr_elts = q->nr_elts;
 395
 396         if (q->nr_top_levels > q->nr_levels)
 397                 q_set_targets_subrange_(q, q->nr_elts, 0, q->nr_levels);
 398
 399         else {
 400                 q_set_targets_subrange_(q, q->nr_in_top_levels,
 401                                         q->nr_levels - q->nr_top_levels, q->nr_levels);
 402
 403                 if (q->nr_in_top_levels < q->nr_elts)
 404                         q_set_targets_subrange_(q, q->nr_elts - q->nr_in_top_levels,
 405                                                 0, q->nr_levels - q->nr_top_levels);
 406                 else
 407                         q_set_targets_subrange_(q, 0, 0, q->nr_levels - q->nr_top_levels);
 408         }
 409 }
 410
 411 static void q_redistribute(struct queue *q)
 412 {
 413         unsigned target, level;
 414         struct ilist *l, *l_above;
 415         struct entry *e;
 416
 417         q_set_targets(q);
 418
 419         for (level = 0u; level < q->nr_levels - 1u; level++) {
 420                 l = q->qs + level;
 421                 target = q->target_count[level];
 422
 423                 /*
 424                  * Pull down some entries from the level above.
 425                  */
 426                 while (l->nr_elts < target) {
 427                         e = __redist_pop_from(q, level + 1u);
 428                         if (!e) {
 429                                 /* bug in nr_elts */
 430                                 break;
 431                         }
 432
 433                         e->level = level;
 434                         l_add_tail(q->es, l, e);
 435                 }
 436
 437                 /*
 438                  * Push some entries up.
 439                  */
 440                 l_above = q->qs + level + 1u;
 441                 while (l->nr_elts > target) {
 442                         e = l_pop_tail(q->es, l);
 443
 444                         if (!e)
 445                                 /* bug in nr_elts */
 446                                 break;
 447
 448                         e->level = level + 1u;
 449                         l_add_head(q->es, l_above, e);
 450                 }
 451         }
 452 }
 453
 454 static void q_requeue_before(struct queue *q, struct entry *dest, struct entry *e, unsigned extra_levels)
 455 {
 456         struct entry *de;
 457         unsigned new_level;
 458
 459         q_del(q, e);
 460
 461         if (extra_levels && (e->level < q->nr_levels - 1u)) {
 462                 new_level = min(q->nr_levels - 1u, e->level + extra_levels);
 463                 for (de = l_head(q->es, q->qs + new_level); de; de = l_next(q->es, de)) {
 464                         if (de->sentinel)
 465                                 continue;
 466
 467                         q_del(q, de);
 468                         de->level = e->level;
 469
 470                         if (dest)
 471                                 q_push_before(q, dest, de);
 472                         else
 473                                 q_push(q, de);
 474                         break;
 475                 }
 476
 477                 e->level = new_level;
 478         }
 479
 480         q_push(q, e);
 481 }
 482
 483 static void q_requeue(struct queue *q, struct entry *e, unsigned extra_levels)
 484 {
 485         q_requeue_before(q, NULL, e, extra_levels);
 486 }
 487
 488 /*----------------------------------------------------------------*/
 489
 490 #define FP_SHIFT 8
 491 #define SIXTEENTH (1u << (FP_SHIFT - 4u))
 492 #define EIGHTH (1u << (FP_SHIFT - 3u))
 493
 494 struct stats {
 495         unsigned hit_threshold;
 496         unsigned hits;
 497         unsigned misses;
 498 };
 499
 500 enum performance {
 501         Q_POOR,
 502         Q_FAIR,
 503         Q_WELL
 504 };
 505
 506 static void stats_init(struct stats *s, unsigned nr_levels)
 507 {
 508         s->hit_threshold = (nr_levels * 3u) / 4u;
 509         s->hits = 0u;
 510         s->misses = 0u;
 511 }
 512
 513 static void stats_reset(struct stats *s)
 514 {
 515         s->hits = s->misses = 0u;
 516 }
 517
 518 static void stats_level_accessed(struct stats *s, unsigned level)
 519 {
 520         if (level >= s->hit_threshold)
 521                 s->hits++;
 522         else
 523                 s->misses++;
 524 }
 525
 526 static void stats_miss(struct stats *s)
 527 {
 528         s->misses++;
 529 }
 530
 531 /*
 532  * There are times when we don't have any confidence in the hotspot queue.
 533  * Such as when a fresh cache is created and the blocks have been spread
 534  * out across the levels, or if an io load changes.  We detect this by
 535  * seeing how often a lookup is in the top levels of the hotspot queue.
 536  */
 537 static enum performance stats_assess(struct stats *s)
 538 {
 539         unsigned confidence = safe_div(s->hits << FP_SHIFT, s->hits + s->misses);
 540
 541         if (confidence < SIXTEENTH)
 542                 return Q_POOR;
 543
 544         else if (confidence < EIGHTH)
 545                 return Q_FAIR;
 546
 547         else
 548                 return Q_WELL;
 549 }
 550
 551 /*----------------------------------------------------------------*/
 552
 553 struct hash_table {
 554         struct entry_space *es;
 555         unsigned long long hash_bits;
 556         unsigned *buckets;
 557 };
 558
 559 /*
 560  * All cache entries are stored in a chained hash table.  To save space we
 561  * use indexing again, and only store indexes to the next entry.
 562  */
 563 static int h_init(struct hash_table *ht, struct entry_space *es, unsigned nr_entries)
 564 {
 565         unsigned i, nr_buckets;
 566
 567         ht->es = es;
 568         nr_buckets = roundup_pow_of_two(max(nr_entries / 4u, 16u));
 569         ht->hash_bits = __ffs(nr_buckets);
 570
 571         ht->buckets = vmalloc(sizeof(*ht->buckets) * nr_buckets);
 572         if (!ht->buckets)
 573                 return -ENOMEM;
 574
 575         for (i = 0; i < nr_buckets; i++)
 576                 ht->buckets[i] = INDEXER_NULL;
 577
 578         return 0;
 579 }
 580
 581 static void h_exit(struct hash_table *ht)
 582 {
 583         vfree(ht->buckets);
 584 }
 585
 586 static struct entry *h_head(struct hash_table *ht, unsigned bucket)
 587 {
 588         return to_entry(ht->es, ht->buckets[bucket]);
 589 }
 590
 591 static struct entry *h_next(struct hash_table *ht, struct entry *e)
 592 {
 593         return to_entry(ht->es, e->hash_next);
 594 }
 595
 596 static void __h_insert(struct hash_table *ht, unsigned bucket, struct entry *e)
 597 {
 598         e->hash_next = ht->buckets[bucket];
 599         ht->buckets[bucket] = to_index(ht->es, e);
 600 }
 601
 602 static void h_insert(struct hash_table *ht, struct entry *e)
 603 {
 604         unsigned h = hash_64(from_oblock(e->oblock), ht->hash_bits);
 605         __h_insert(ht, h, e);
 606 }
 607
 608 static struct entry *__h_lookup(struct hash_table *ht, unsigned h, dm_oblock_t oblock,
 609                                 struct entry **prev)
 610 {
 611         struct entry *e;
 612
 613         *prev = NULL;
 614         for (e = h_head(ht, h); e; e = h_next(ht, e)) {
 615                 if (e->oblock == oblock)
 616                         return e;
 617
 618                 *prev = e;
 619         }
 620
 621         return NULL;
 622 }
 623
 624 static void __h_unlink(struct hash_table *ht, unsigned h,
 625                        struct entry *e, struct entry *prev)
 626 {
 627         if (prev)
 628                 prev->hash_next = e->hash_next;
 629         else
 630                 ht->buckets[h] = e->hash_next;
 631 }
 632
 633 /*
 634  * Also moves each entry to the front of the bucket.
 635  */
 636 static struct entry *h_lookup(struct hash_table *ht, dm_oblock_t oblock)
 637 {
 638         struct entry *e, *prev;
 639         unsigned h = hash_64(from_oblock(oblock), ht->hash_bits);
 640
 641         e = __h_lookup(ht, h, oblock, &prev);
 642         if (e && prev) {
 643                 /*
 644                  * Move to the front because this entry is likely
 645                  * to be hit again.
 646                  */
 647                 __h_unlink(ht, h, e, prev);
 648                 __h_insert(ht, h, e);
 649         }
 650
 651         return e;
 652 }
 653
 654 static void h_remove(struct hash_table *ht, struct entry *e)
 655 {
 656         unsigned h = hash_64(from_oblock(e->oblock), ht->hash_bits);
 657         struct entry *prev;
 658
 659         /*
 660          * The down side of using a singly linked list is we have to
 661          * iterate the bucket to remove an item.
 662          */
 663         e = __h_lookup(ht, h, e->oblock, &prev);
 664         if (e)
 665                 __h_unlink(ht, h, e, prev);
 666 }
 667
 668 /*----------------------------------------------------------------*/
 669
 670 struct entry_alloc {
 671         struct entry_space *es;
 672         unsigned begin;
 673
 674         unsigned nr_allocated;
 675         struct ilist free;
 676 };
 677
 678 static void init_allocator(struct entry_alloc *ea, struct entry_space *es,
 679                            unsigned begin, unsigned end)
 680 {
 681         unsigned i;
 682
 683         ea->es = es;
 684         ea->nr_allocated = 0u;
 685         ea->begin = begin;
 686
 687         l_init(&ea->free);
 688         for (i = begin; i != end; i++)
 689                 l_add_tail(ea->es, &ea->free, __get_entry(ea->es, i));
 690 }
 691
 692 static void init_entry(struct entry *e)
 693 {
 694         /*
 695          * We can't memset because that would clear the hotspot and
 696          * sentinel bits which remain constant.
 697          */
 698         e->hash_next = INDEXER_NULL;
 699         e->next = INDEXER_NULL;
 700         e->prev = INDEXER_NULL;
 701         e->level = 0u;
 702         e->allocated = true;
 703 }
 704
 705 static struct entry *alloc_entry(struct entry_alloc *ea)
 706 {
 707         struct entry *e;
 708
 709         if (l_empty(&ea->free))
 710                 return NULL;
 711
 712         e = l_pop_tail(ea->es, &ea->free);
 713         init_entry(e);
 714         ea->nr_allocated++;
 715
 716         return e;
 717 }
 718
 719 /*
 720  * This assumes the cblock hasn't already been allocated.
 721  */
 722 static struct entry *alloc_particular_entry(struct entry_alloc *ea, unsigned i)
 723 {
 724         struct entry *e = __get_entry(ea->es, ea->begin + i);
 725
 726         BUG_ON(e->allocated);
 727
 728         l_del(ea->es, &ea->free, e);
 729         init_entry(e);
 730         ea->nr_allocated++;
 731
 732         return e;
 733 }
 734
 735 static void free_entry(struct entry_alloc *ea, struct entry *e)
 736 {
 737         BUG_ON(!ea->nr_allocated);
 738         BUG_ON(!e->allocated);
 739
 740         ea->nr_allocated--;
 741         e->allocated = false;
 742         l_add_tail(ea->es, &ea->free, e);
 743 }
 744
 745 static bool allocator_empty(struct entry_alloc *ea)
 746 {
 747         return l_empty(&ea->free);
 748 }
 749
 750 static unsigned get_index(struct entry_alloc *ea, struct entry *e)
 751 {
 752         return to_index(ea->es, e) - ea->begin;
 753 }
 754
 755 static struct entry *get_entry(struct entry_alloc *ea, unsigned index)
 756 {
 757         return __get_entry(ea->es, ea->begin + index);
 758 }
 759
 760 /*----------------------------------------------------------------*/
 761
 762 #define NR_HOTSPOT_LEVELS 64u
 763 #define NR_CACHE_LEVELS 64u
 764
 765 #define WRITEBACK_PERIOD (10 * HZ)
 766 #define DEMOTE_PERIOD (60 * HZ)
 767
 768 #define HOTSPOT_UPDATE_PERIOD (HZ)
 769 #define CACHE_UPDATE_PERIOD (10u * HZ)
 770
 771 struct smq_policy {
 772         struct dm_cache_policy policy;
 773
 774         /* protects everything */
 775         spinlock_t lock;
 776         dm_cblock_t cache_size;
 777         sector_t cache_block_size;
 778
 779         sector_t hotspot_block_size;
 780         unsigned nr_hotspot_blocks;
 781         unsigned cache_blocks_per_hotspot_block;
 782         unsigned hotspot_level_jump;
 783
 784         struct entry_space es;
 785         struct entry_alloc writeback_sentinel_alloc;
 786         struct entry_alloc demote_sentinel_alloc;
 787         struct entry_alloc hotspot_alloc;
 788         struct entry_alloc cache_alloc;
 789
 790         unsigned long *hotspot_hit_bits;
 791         unsigned long *cache_hit_bits;
 792
 793         /*
 794          * We maintain three queues of entries.  The cache proper,
 795          * consisting of a clean and dirty queue, containing the currently
 796          * active mappings.  The hotspot queue uses a larger block size to
 797          * track blocks that are being hit frequently and potential
 798          * candidates for promotion to the cache.
 799          */
 800         struct queue hotspot;
 801         struct queue clean;
 802         struct queue dirty;
 803
 804         struct stats hotspot_stats;
 805         struct stats cache_stats;
 806
 807         /*
 808          * Keeps track of time, incremented by the core.  We use this to
 809          * avoid attributing multiple hits within the same tick.
 810          */
 811         unsigned tick;
 812
 813         /*
 814          * The hash tables allows us to quickly find an entry by origin
 815          * block.
 816          */
 817         struct hash_table table;
 818         struct hash_table hotspot_table;
 819
 820         bool current_writeback_sentinels;
 821         unsigned long next_writeback_period;
 822
 823         bool current_demote_sentinels;
 824         unsigned long next_demote_period;
 825
 826         unsigned write_promote_level;
 827         unsigned read_promote_level;
 828
 829         unsigned long next_hotspot_period;
 830         unsigned long next_cache_period;
 831 };
 832
 833 /*----------------------------------------------------------------*/
 834
 835 static struct entry *get_sentinel(struct entry_alloc *ea, unsigned level, bool which)
 836 {
 837         return get_entry(ea, which ? level : NR_CACHE_LEVELS + level);
 838 }
 839
 840 static struct entry *writeback_sentinel(struct smq_policy *mq, unsigned level)
 841 {
 842         return get_sentinel(&mq->writeback_sentinel_alloc, level, mq->current_writeback_sentinels);
 843 }
 844
 845 static struct entry *demote_sentinel(struct smq_policy *mq, unsigned level)
 846 {
 847         return get_sentinel(&mq->demote_sentinel_alloc, level, mq->current_demote_sentinels);
 848 }
 849
 850 static void __update_writeback_sentinels(struct smq_policy *mq)
 851 {
 852         unsigned level;
 853         struct queue *q = &mq->dirty;
 854         struct entry *sentinel;
 855
 856         for (level = 0; level < q->nr_levels; level++) {
 857                 sentinel = writeback_sentinel(mq, level);
 858                 q_del(q, sentinel);
 859                 q_push(q, sentinel);
 860         }
 861 }
 862
 863 static void __update_demote_sentinels(struct smq_policy *mq)
 864 {
 865         unsigned level;
 866         struct queue *q = &mq->clean;
 867         struct entry *sentinel;
 868
 869         for (level = 0; level < q->nr_levels; level++) {
 870                 sentinel = demote_sentinel(mq, level);
 871                 q_del(q, sentinel);
 872                 q_push(q, sentinel);
 873         }
 874 }
 875
 876 static void update_sentinels(struct smq_policy *mq)
 877 {
 878         if (time_after(jiffies, mq->next_writeback_period)) {
 879                 __update_writeback_sentinels(mq);
 880                 mq->next_writeback_period = jiffies + WRITEBACK_PERIOD;
 881                 mq->current_writeback_sentinels = !mq->current_writeback_sentinels;
 882         }
 883
 884         if (time_after(jiffies, mq->next_demote_period)) {
 885                 __update_demote_sentinels(mq);
 886                 mq->next_demote_period = jiffies + DEMOTE_PERIOD;
 887                 mq->current_demote_sentinels = !mq->current_demote_sentinels;
 888         }
 889 }
 890
 891 static void __sentinels_init(struct smq_policy *mq)
 892 {
 893         unsigned level;
 894         struct entry *sentinel;
 895
 896         for (level = 0; level < NR_CACHE_LEVELS; level++) {
 897                 sentinel = writeback_sentinel(mq, level);
 898                 sentinel->level = level;
 899                 q_push(&mq->dirty, sentinel);
 900
 901                 sentinel = demote_sentinel(mq, level);
 902                 sentinel->level = level;
 903                 q_push(&mq->clean, sentinel);
 904         }
 905 }
 906
 907 static void sentinels_init(struct smq_policy *mq)
 908 {
 909         mq->next_writeback_period = jiffies + WRITEBACK_PERIOD;
 910         mq->next_demote_period = jiffies + DEMOTE_PERIOD;
 911
 912         mq->current_writeback_sentinels = false;
 913         mq->current_demote_sentinels = false;
 914         __sentinels_init(mq);
 915
 916         mq->current_writeback_sentinels = !mq->current_writeback_sentinels;
 917         mq->current_demote_sentinels = !mq->current_demote_sentinels;
 918         __sentinels_init(mq);
 919 }
 920
 921 /*----------------------------------------------------------------*/
 922
 923 /*
 924  * These methods tie together the dirty queue, clean queue and hash table.
 925  */
 926 static void push_new(struct smq_policy *mq, struct entry *e)
 927 {
 928         struct queue *q = e->dirty ? &mq->dirty : &mq->clean;
 929         h_insert(&mq->table, e);
 930         q_push(q, e);
 931 }
 932
 933 static void push(struct smq_policy *mq, struct entry *e)
 934 {
 935         struct entry *sentinel;
 936
 937         h_insert(&mq->table, e);
 938
 939         /*
 940          * Punch this into the queue just in front of the sentinel, to
 941          * ensure it's cleaned straight away.
 942          */
 943         if (e->dirty) {
 944                 sentinel = writeback_sentinel(mq, e->level);
 945                 q_push_before(&mq->dirty, sentinel, e);
 946         } else {
 947                 sentinel = demote_sentinel(mq, e->level);
 948                 q_push_before(&mq->clean, sentinel, e);
 949         }
 950 }
 951
 952 /*
 953  * Removes an entry from cache.  Removes from the hash table.
 954  */
 955 static void __del(struct smq_policy *mq, struct queue *q, struct entry *e)
 956 {
 957         q_del(q, e);
 958         h_remove(&mq->table, e);
 959 }
 960
 961 static void del(struct smq_policy *mq, struct entry *e)
 962 {
 963         __del(mq, e->dirty ? &mq->dirty : &mq->clean, e);
 964 }
 965
 966 static struct entry *pop_old(struct smq_policy *mq, struct queue *q, unsigned max_level)
 967 {
 968         struct entry *e = q_pop_old(q, max_level);
 969         if (e)
 970                 h_remove(&mq->table, e);
 971         return e;
 972 }
 973
 974 static dm_cblock_t infer_cblock(struct smq_policy *mq, struct entry *e)
 975 {
 976         return to_cblock(get_index(&mq->cache_alloc, e));
 977 }
 978
 979 static void requeue(struct smq_policy *mq, struct entry *e)
 980 {
 981         struct entry *sentinel;
 982
 983         if (!test_and_set_bit(from_cblock(infer_cblock(mq, e)), mq->cache_hit_bits)) {
 984                 if (e->dirty) {
 985                         sentinel = writeback_sentinel(mq, e->level);
 986                         q_requeue_before(&mq->dirty, sentinel, e, 1u);
 987                 } else {
 988                         sentinel = demote_sentinel(mq, e->level);
 989                         q_requeue_before(&mq->clean, sentinel, e, 1u);
 990                 }
 991         }
 992 }
 993
 994 static unsigned default_promote_level(struct smq_policy *mq)
 995 {
 996         /*
 997          * The promote level depends on the current performance of the
 998          * cache.
 999          *
1000          * If the cache is performing badly, then we can't afford
1001          * to promote much without causing performance to drop below that
1002          * of the origin device.
1003          *
1004          * If the cache is performing well, then we don't need to promote
1005          * much.  If it isn't broken, don't fix it.
1006          *
1007          * If the cache is middling then we promote more.
1008          *
1009          * This scheme reminds me of a graph of entropy vs probability of a
1010          * binary variable.
1011          */
1012         static unsigned table[] = {1, 1, 1, 2, 4, 6, 7, 8, 7, 6, 4, 4, 3, 3, 2, 2, 1};
1013
1014         unsigned hits = mq->cache_stats.hits;
1015         unsigned misses = mq->cache_stats.misses;
1016         unsigned index = safe_div(hits << 4u, hits + misses);
1017         return table[index];
1018 }
1019
1020 static void update_promote_levels(struct smq_policy *mq)
1021 {
1022         /*
1023          * If there are unused cache entries then we want to be really
1024          * eager to promote.
1025          */
1026         unsigned threshold_level = allocator_empty(&mq->cache_alloc) ?
1027                 default_promote_level(mq) : (NR_HOTSPOT_LEVELS / 2u);
1028
1029         /*
1030          * If the hotspot queue is performing badly then we have little
1031          * confidence that we know which blocks to promote.  So we cut down
1032          * the amount of promotions.
1033          */
1034         switch (stats_assess(&mq->hotspot_stats)) {
1035         case Q_POOR:
1036                 threshold_level /= 4u;
1037                 break;
1038
1039         case Q_FAIR:
1040                 threshold_level /= 2u;
1041                 break;
1042
1043         case Q_WELL:
1044                 break;
1045         }
1046
1047         mq->read_promote_level = NR_HOTSPOT_LEVELS - threshold_level;
1048         mq->write_promote_level = (NR_HOTSPOT_LEVELS - threshold_level) + 2u;
1049 }
1050
1051 /*
1052  * If the hotspot queue is performing badly, then we try and move entries
1053  * around more quickly.
1054  */
1055 static void update_level_jump(struct smq_policy *mq)
1056 {
1057         switch (stats_assess(&mq->hotspot_stats)) {
1058         case Q_POOR:
1059                 mq->hotspot_level_jump = 4u;
1060                 break;
1061
1062         case Q_FAIR:
1063                 mq->hotspot_level_jump = 2u;
1064                 break;
1065
1066         case Q_WELL:
1067                 mq->hotspot_level_jump = 1u;
1068                 break;
1069         }
1070 }
1071
1072 static void end_hotspot_period(struct smq_policy *mq)
1073 {
1074         clear_bitset(mq->hotspot_hit_bits, mq->nr_hotspot_blocks);
1075         update_promote_levels(mq);
1076
1077         if (time_after(jiffies, mq->next_hotspot_period)) {
1078                 update_level_jump(mq);
1079                 q_redistribute(&mq->hotspot);
1080                 stats_reset(&mq->hotspot_stats);
1081                 mq->next_hotspot_period = jiffies + HOTSPOT_UPDATE_PERIOD;
1082         }
1083 }
1084
1085 static void end_cache_period(struct smq_policy *mq)
1086 {
1087         if (time_after(jiffies, mq->next_cache_period)) {
1088                 clear_bitset(mq->cache_hit_bits, from_cblock(mq->cache_size));
1089
1090                 q_redistribute(&mq->dirty);
1091                 q_redistribute(&mq->clean);
1092                 stats_reset(&mq->cache_stats);
1093
1094                 mq->next_cache_period = jiffies + CACHE_UPDATE_PERIOD;
1095         }
1096 }
1097
1098 static int demote_cblock(struct smq_policy *mq,
1099                          struct policy_locker *locker,
1100                          dm_oblock_t *oblock)
1101 {
1102         struct entry *demoted = q_peek(&mq->clean, mq->clean.nr_levels, false);
1103         if (!demoted)
1104                 /*
1105                  * We could get a block from mq->dirty, but that
1106                  * would add extra latency to the triggering bio as it
1107                  * waits for the writeback.  Better to not promote this
1108                  * time and hope there's a clean block next time this block
1109                  * is hit.
1110                  */
1111                 return -ENOSPC;
1112
1113         if (locker->fn(locker, demoted->oblock))
1114                 /*
1115                  * We couldn't lock this block.
1116                  */
1117                 return -EBUSY;
1118
1119         del(mq, demoted);
1120         *oblock = demoted->oblock;
1121         free_entry(&mq->cache_alloc, demoted);
1122
1123         return 0;
1124 }
1125
1126 enum promote_result {
1127         PROMOTE_NOT,
1128         PROMOTE_TEMPORARY,
1129         PROMOTE_PERMANENT
1130 };
1131
1132 /*
1133  * Converts a boolean into a promote result.
1134  */
1135 static enum promote_result maybe_promote(bool promote)
1136 {
1137         return promote ? PROMOTE_PERMANENT : PROMOTE_NOT;
1138 }
1139
1140 static enum promote_result should_promote(struct smq_policy *mq, struct entry *hs_e, struct bio *bio,
1141                                           bool fast_promote)
1142 {
1143         if (bio_data_dir(bio) == WRITE) {
1144                 if (!allocator_empty(&mq->cache_alloc) && fast_promote)
1145                         return PROMOTE_TEMPORARY;
1146
1147                 else
1148                         return maybe_promote(hs_e->level >= mq->write_promote_level);
1149         } else
1150                 return maybe_promote(hs_e->level >= mq->read_promote_level);
1151 }
1152
1153 static void insert_in_cache(struct smq_policy *mq, dm_oblock_t oblock,
1154                             struct policy_locker *locker,
1155                             struct policy_result *result, enum promote_result pr)
1156 {
1157         int r;
1158         struct entry *e;
1159
1160         if (allocator_empty(&mq->cache_alloc)) {
1161                 result->op = POLICY_REPLACE;
1162                 r = demote_cblock(mq, locker, &result->old_oblock);
1163                 if (r) {
1164                         result->op = POLICY_MISS;
1165                         return;
1166                 }
1167
1168         } else
1169                 result->op = POLICY_NEW;
1170
1171         e = alloc_entry(&mq->cache_alloc);
1172         BUG_ON(!e);
1173         e->oblock = oblock;
1174
1175         if (pr == PROMOTE_TEMPORARY)
1176                 push(mq, e);
1177         else
1178                 push_new(mq, e);
1179
1180         result->cblock = infer_cblock(mq, e);
1181 }
1182
1183 static dm_oblock_t to_hblock(struct smq_policy *mq, dm_oblock_t b)
1184 {
1185         sector_t r = from_oblock(b);
1186         (void) sector_div(r, mq->cache_blocks_per_hotspot_block);
1187         return to_oblock(r);
1188 }
1189
1190 static struct entry *update_hotspot_queue(struct smq_policy *mq, dm_oblock_t b, struct bio *bio)
1191 {
1192         unsigned hi;
1193         dm_oblock_t hb = to_hblock(mq, b);
1194         struct entry *e = h_lookup(&mq->hotspot_table, hb);
1195
1196         if (e) {
1197                 stats_level_accessed(&mq->hotspot_stats, e->level);
1198
1199                 hi = get_index(&mq->hotspot_alloc, e);
1200                 q_requeue(&mq->hotspot, e,
1201                           test_and_set_bit(hi, mq->hotspot_hit_bits) ?
1202                           0u : mq->hotspot_level_jump);
1203
1204         } else {
1205                 stats_miss(&mq->hotspot_stats);
1206
1207                 e = alloc_entry(&mq->hotspot_alloc);
1208                 if (!e) {
1209                         e = q_pop(&mq->hotspot);
1210                         if (e) {
1211                                 h_remove(&mq->hotspot_table, e);
1212                                 hi = get_index(&mq->hotspot_alloc, e);
1213                                 clear_bit(hi, mq->hotspot_hit_bits);
1214                         }
1215
1216                 }
1217
1218                 if (e) {
1219                         e->oblock = hb;
1220                         q_push(&mq->hotspot, e);
1221                         h_insert(&mq->hotspot_table, e);
1222                 }
1223         }
1224
1225         return e;
1226 }
1227
1228 /*
1229  * Looks the oblock up in the hash table, then decides whether to put in
1230  * pre_cache, or cache etc.
1231  */
1232 static int map(struct smq_policy *mq, struct bio *bio, dm_oblock_t oblock,
1233                bool can_migrate, bool fast_promote,
1234                struct policy_locker *locker, struct policy_result *result)
1235 {
1236         struct entry *e, *hs_e;
1237         enum promote_result pr;
1238
1239         hs_e = update_hotspot_queue(mq, oblock, bio);
1240
1241         e = h_lookup(&mq->table, oblock);
1242         if (e) {
1243                 stats_level_accessed(&mq->cache_stats, e->level);
1244
1245                 requeue(mq, e);
1246                 result->op = POLICY_HIT;
1247                 result->cblock = infer_cblock(mq, e);
1248
1249         } else {
1250                 stats_miss(&mq->cache_stats);
1251
1252                 pr = should_promote(mq, hs_e, bio, fast_promote);
1253                 if (pr == PROMOTE_NOT)
1254                         result->op = POLICY_MISS;
1255
1256                 else {
1257                         if (!can_migrate) {
1258                                 result->op = POLICY_MISS;
1259                                 return -EWOULDBLOCK;
1260                         }
1261
1262                         insert_in_cache(mq, oblock, locker, result, pr);
1263                 }
1264         }
1265
1266         return 0;
1267 }
1268
1269 /*----------------------------------------------------------------*/
1270
1271 /*
1272  * Public interface, via the policy struct.  See dm-cache-policy.h for a
1273  * description of these.
1274  */
1275
1276 static struct smq_policy *to_smq_policy(struct dm_cache_policy *p)
1277 {
1278         return container_of(p, struct smq_policy, policy);
1279 }
1280
1281 static void smq_destroy(struct dm_cache_policy *p)
1282 {
1283         struct smq_policy *mq = to_smq_policy(p);
1284
1285         h_exit(&mq->hotspot_table);
1286         h_exit(&mq->table);
1287         free_bitset(mq->hotspot_hit_bits);
1288         free_bitset(mq->cache_hit_bits);
1289         space_exit(&mq->es);
1290         kfree(mq);
1291 }
1292
1293 static int smq_map(struct dm_cache_policy *p, dm_oblock_t oblock,
1294                    bool can_block, bool can_migrate, bool fast_promote,
1295                    struct bio *bio, struct policy_locker *locker,
1296                    struct policy_result *result)
1297 {
1298         int r;
1299         unsigned long flags;
1300         struct smq_policy *mq = to_smq_policy(p);
1301
1302         result->op = POLICY_MISS;
1303
1304         spin_lock_irqsave(&mq->lock, flags);
1305         r = map(mq, bio, oblock, can_migrate, fast_promote, locker, result);
1306         spin_unlock_irqrestore(&mq->lock, flags);
1307
1308         return r;
1309 }
1310
1311 static int smq_lookup(struct dm_cache_policy *p, dm_oblock_t oblock, dm_cblock_t *cblock)
1312 {
1313         int r;
1314         unsigned long flags;
1315         struct smq_policy *mq = to_smq_policy(p);
1316         struct entry *e;
1317
1318         spin_lock_irqsave(&mq->lock, flags);
1319         e = h_lookup(&mq->table, oblock);
1320         if (e) {
1321                 *cblock = infer_cblock(mq, e);
1322                 r = 0;
1323         } else
1324                 r = -ENOENT;
1325         spin_unlock_irqrestore(&mq->lock, flags);
1326
1327         return r;
1328 }
1329
1330 static void __smq_set_clear_dirty(struct smq_policy *mq, dm_oblock_t oblock, bool set)
1331 {
1332         struct entry *e;
1333
1334         e = h_lookup(&mq->table, oblock);
1335         BUG_ON(!e);
1336
1337         del(mq, e);
1338         e->dirty = set;
1339         push(mq, e);
1340 }
1341
1342 static void smq_set_dirty(struct dm_cache_policy *p, dm_oblock_t oblock)
1343 {
1344         unsigned long flags;
1345         struct smq_policy *mq = to_smq_policy(p);
1346
1347         spin_lock_irqsave(&mq->lock, flags);
1348         __smq_set_clear_dirty(mq, oblock, true);
1349         spin_unlock_irqrestore(&mq->lock, flags);
1350 }
1351
1352 static void smq_clear_dirty(struct dm_cache_policy *p, dm_oblock_t oblock)
1353 {
1354         struct smq_policy *mq = to_smq_policy(p);
1355         unsigned long flags;
1356
1357         spin_lock_irqsave(&mq->lock, flags);
1358         __smq_set_clear_dirty(mq, oblock, false);
1359         spin_unlock_irqrestore(&mq->lock, flags);
1360 }
1361
1362 static unsigned random_level(dm_cblock_t cblock)
1363 {
1364         return hash_32_generic(from_cblock(cblock), 9) & (NR_CACHE_LEVELS - 1);
1365 }
1366
1367 static int smq_load_mapping(struct dm_cache_policy *p,
1368                             dm_oblock_t oblock, dm_cblock_t cblock,
1369                             uint32_t hint, bool hint_valid)
1370 {
1371         struct smq_policy *mq = to_smq_policy(p);
1372         struct entry *e;
1373
1374         e = alloc_particular_entry(&mq->cache_alloc, from_cblock(cblock));
1375         e->oblock = oblock;
1376         e->dirty = false;       /* this gets corrected in a minute */
1377         e->level = hint_valid ? min(hint, NR_CACHE_LEVELS - 1) : random_level(cblock);
1378         push(mq, e);
1379
1380         return 0;
1381 }
1382
1383 static uint32_t smq_get_hint(struct dm_cache_policy *p, dm_cblock_t cblock)
1384 {
1385         struct smq_policy *mq = to_smq_policy(p);
1386         struct entry *e = get_entry(&mq->cache_alloc, from_cblock(cblock));
1387
1388         if (!e->allocated)
1389                 return 0;
1390
1391         return e->level;
1392 }
1393
1394 static void __remove_mapping(struct smq_policy *mq, dm_oblock_t oblock)
1395 {
1396         struct entry *e;
1397
1398         e = h_lookup(&mq->table, oblock);
1399         BUG_ON(!e);
1400
1401         del(mq, e);
1402         free_entry(&mq->cache_alloc, e);
1403 }
1404
1405 static void smq_remove_mapping(struct dm_cache_policy *p, dm_oblock_t oblock)
1406 {
1407         struct smq_policy *mq = to_smq_policy(p);
1408         unsigned long flags;
1409
1410         spin_lock_irqsave(&mq->lock, flags);
1411         __remove_mapping(mq, oblock);
1412         spin_unlock_irqrestore(&mq->lock, flags);
1413 }
1414
1415 static int __remove_cblock(struct smq_policy *mq, dm_cblock_t cblock)
1416 {
1417         struct entry *e = get_entry(&mq->cache_alloc, from_cblock(cblock));
1418
1419         if (!e || !e->allocated)
1420                 return -ENODATA;
1421
1422         del(mq, e);
1423         free_entry(&mq->cache_alloc, e);
1424
1425         return 0;
1426 }
1427
1428 static int smq_remove_cblock(struct dm_cache_policy *p, dm_cblock_t cblock)
1429 {
1430         int r;
1431         unsigned long flags;
1432         struct smq_policy *mq = to_smq_policy(p);
1433
1434         spin_lock_irqsave(&mq->lock, flags);
1435         r = __remove_cblock(mq, cblock);
1436         spin_unlock_irqrestore(&mq->lock, flags);
1437
1438         return r;
1439 }
1440
1441
1442 #define CLEAN_TARGET_CRITICAL 5u /* percent */
1443
1444 static bool clean_target_met(struct smq_policy *mq, bool critical)
1445 {
1446         if (critical) {
1447                 /*
1448                  * Cache entries may not be populated.  So we're cannot rely on the
1449                  * size of the clean queue.
1450                  */
1451                 unsigned nr_clean = from_cblock(mq->cache_size) - q_size(&mq->dirty);
1452                 unsigned target = from_cblock(mq->cache_size) * CLEAN_TARGET_CRITICAL / 100u;
1453
1454                 return nr_clean >= target;
1455         } else
1456                 return !q_size(&mq->dirty);
1457 }
1458
1459 static int __smq_writeback_work(struct smq_policy *mq, dm_oblock_t *oblock,
1460                                 dm_cblock_t *cblock, bool critical_only)
1461 {
1462         struct entry *e = NULL;
1463         bool target_met = clean_target_met(mq, critical_only);
1464
1465         if (critical_only)
1466                 /*
1467                  * Always try and keep the bottom level clean.
1468                  */
1469                 e = pop_old(mq, &mq->dirty, target_met ? 1u : mq->dirty.nr_levels);
1470
1471         else
1472                 e = pop_old(mq, &mq->dirty, mq->dirty.nr_levels);
1473
1474         if (!e)
1475                 return -ENODATA;
1476
1477         *oblock = e->oblock;
1478         *cblock = infer_cblock(mq, e);
1479         e->dirty = false;
1480         push_new(mq, e);
1481
1482         return 0;
1483 }
1484
1485 static int smq_writeback_work(struct dm_cache_policy *p, dm_oblock_t *oblock,
1486                               dm_cblock_t *cblock, bool critical_only)
1487 {
1488         int r;
1489         unsigned long flags;
1490         struct smq_policy *mq = to_smq_policy(p);
1491
1492         spin_lock_irqsave(&mq->lock, flags);
1493         r = __smq_writeback_work(mq, oblock, cblock, critical_only);
1494         spin_unlock_irqrestore(&mq->lock, flags);
1495
1496         return r;
1497 }
1498
1499 static void __force_mapping(struct smq_policy *mq,
1500                             dm_oblock_t current_oblock, dm_oblock_t new_oblock)
1501 {
1502         struct entry *e = h_lookup(&mq->table, current_oblock);
1503
1504         if (e) {
1505                 del(mq, e);
1506                 e->oblock = new_oblock;
1507                 e->dirty = true;
1508                 push(mq, e);
1509         }
1510 }
1511
1512 static void smq_force_mapping(struct dm_cache_policy *p,
1513                               dm_oblock_t current_oblock, dm_oblock_t new_oblock)
1514 {
1515         unsigned long flags;
1516         struct smq_policy *mq = to_smq_policy(p);
1517
1518         spin_lock_irqsave(&mq->lock, flags);
1519         __force_mapping(mq, current_oblock, new_oblock);
1520         spin_unlock_irqrestore(&mq->lock, flags);
1521 }
1522
1523 static dm_cblock_t smq_residency(struct dm_cache_policy *p)
1524 {
1525         dm_cblock_t r;
1526         unsigned long flags;
1527         struct smq_policy *mq = to_smq_policy(p);
1528
1529         spin_lock_irqsave(&mq->lock, flags);
1530         r = to_cblock(mq->cache_alloc.nr_allocated);
1531         spin_unlock_irqrestore(&mq->lock, flags);
1532
1533         return r;
1534 }
1535
1536 static void smq_tick(struct dm_cache_policy *p, bool can_block)
1537 {
1538         struct smq_policy *mq = to_smq_policy(p);
1539         unsigned long flags;
1540
1541         spin_lock_irqsave(&mq->lock, flags);
1542         mq->tick++;
1543         update_sentinels(mq);
1544         end_hotspot_period(mq);
1545         end_cache_period(mq);
1546         spin_unlock_irqrestore(&mq->lock, flags);
1547 }
1548
1549 /*
1550  * smq has no config values, but the old mq policy did.  To avoid breaking
1551  * software we continue to accept these configurables for the mq policy,
1552  * but they have no effect.
1553  */
1554 static int mq_set_config_value(struct dm_cache_policy *p,
1555                                const char *key, const char *value)
1556 {
1557         unsigned long tmp;
1558
1559         if (kstrtoul(value, 10, &tmp))
1560                 return -EINVAL;
1561
1562         if (!strcasecmp(key, "random_threshold") ||
1563             !strcasecmp(key, "sequential_threshold") ||
1564             !strcasecmp(key, "discard_promote_adjustment") ||
1565             !strcasecmp(key, "read_promote_adjustment") ||
1566             !strcasecmp(key, "write_promote_adjustment")) {
1567                 DMWARN("tunable '%s' no longer has any effect, mq policy is now an alias for smq", key);
1568                 return 0;
1569         }
1570
1571         return -EINVAL;
1572 }
1573
1574 static int mq_emit_config_values(struct dm_cache_policy *p, char *result,
1575                                  unsigned maxlen, ssize_t *sz_ptr)
1576 {
1577         ssize_t sz = *sz_ptr;
1578
1579         DMEMIT("10 random_threshold 0 "
1580                "sequential_threshold 0 "
1581                "discard_promote_adjustment 0 "
1582                "read_promote_adjustment 0 "
1583                "write_promote_adjustment 0 ");
1584
1585         *sz_ptr = sz;
1586         return 0;
1587 }
1588
1589 /* Init the policy plugin interface function pointers. */
1590 static void init_policy_functions(struct smq_policy *mq, bool mimic_mq)
1591 {
1592         mq->policy.destroy = smq_destroy;
1593         mq->policy.map = smq_map;
1594         mq->policy.lookup = smq_lookup;
1595         mq->policy.set_dirty = smq_set_dirty;
1596         mq->policy.clear_dirty = smq_clear_dirty;
1597         mq->policy.load_mapping = smq_load_mapping;
1598         mq->policy.get_hint = smq_get_hint;
1599         mq->policy.remove_mapping = smq_remove_mapping;
1600         mq->policy.remove_cblock = smq_remove_cblock;
1601         mq->policy.writeback_work = smq_writeback_work;
1602         mq->policy.force_mapping = smq_force_mapping;
1603         mq->policy.residency = smq_residency;
1604         mq->policy.tick = smq_tick;
1605
1606         if (mimic_mq) {
1607                 mq->policy.set_config_value = mq_set_config_value;
1608                 mq->policy.emit_config_values = mq_emit_config_values;
1609         }
1610 }
1611
1612 static bool too_many_hotspot_blocks(sector_t origin_size,
1613                                     sector_t hotspot_block_size,
1614                                     unsigned nr_hotspot_blocks)
1615 {
1616         return (hotspot_block_size * nr_hotspot_blocks) > origin_size;
1617 }
1618
1619 static void calc_hotspot_params(sector_t origin_size,
1620                                 sector_t cache_block_size,
1621                                 unsigned nr_cache_blocks,
1622                                 sector_t *hotspot_block_size,
1623                                 unsigned *nr_hotspot_blocks)
1624 {
1625         *hotspot_block_size = cache_block_size * 16u;
1626         *nr_hotspot_blocks = max(nr_cache_blocks / 4u, 1024u);
1627
1628         while ((*hotspot_block_size > cache_block_size) &&
1629                too_many_hotspot_blocks(origin_size, *hotspot_block_size, *nr_hotspot_blocks))
1630                 *hotspot_block_size /= 2u;
1631 }
1632
1633 static struct dm_cache_policy *__smq_create(dm_cblock_t cache_size,
1634                                             sector_t origin_size,
1635                                             sector_t cache_block_size,
1636                                             bool mimic_mq)
1637 {
1638         unsigned i;
1639         unsigned nr_sentinels_per_queue = 2u * NR_CACHE_LEVELS;
1640         unsigned total_sentinels = 2u * nr_sentinels_per_queue;
1641         struct smq_policy *mq = kzalloc(sizeof(*mq), GFP_KERNEL);
1642
1643         if (!mq)
1644                 return NULL;
1645
1646         init_policy_functions(mq, mimic_mq);
1647         mq->cache_size = cache_size;
1648         mq->cache_block_size = cache_block_size;
1649
1650         calc_hotspot_params(origin_size, cache_block_size, from_cblock(cache_size),
1651                             &mq->hotspot_block_size, &mq->nr_hotspot_blocks);
1652
1653         mq->cache_blocks_per_hotspot_block = div64_u64(mq->hotspot_block_size, mq->cache_block_size);
1654         mq->hotspot_level_jump = 1u;
1655         if (space_init(&mq->es, total_sentinels + mq->nr_hotspot_blocks + from_cblock(cache_size))) {
1656                 DMERR("couldn't initialize entry space");
1657                 goto bad_pool_init;
1658         }
1659
1660         init_allocator(&mq->writeback_sentinel_alloc, &mq->es, 0, nr_sentinels_per_queue);
1661         for (i = 0; i < nr_sentinels_per_queue; i++)
1662                 get_entry(&mq->writeback_sentinel_alloc, i)->sentinel = true;
1663
1664         init_allocator(&mq->demote_sentinel_alloc, &mq->es, nr_sentinels_per_queue, total_sentinels);
1665         for (i = 0; i < nr_sentinels_per_queue; i++)
1666                 get_entry(&mq->demote_sentinel_alloc, i)->sentinel = true;
1667
1668         init_allocator(&mq->hotspot_alloc, &mq->es, total_sentinels,
1669                        total_sentinels + mq->nr_hotspot_blocks);
1670
1671         init_allocator(&mq->cache_alloc, &mq->es,
1672                        total_sentinels + mq->nr_hotspot_blocks,
1673                        total_sentinels + mq->nr_hotspot_blocks + from_cblock(cache_size));
1674
1675         mq->hotspot_hit_bits = alloc_bitset(mq->nr_hotspot_blocks);
1676         if (!mq->hotspot_hit_bits) {
1677                 DMERR("couldn't allocate hotspot hit bitset");
1678                 goto bad_hotspot_hit_bits;
1679         }
1680         clear_bitset(mq->hotspot_hit_bits, mq->nr_hotspot_blocks);
1681
1682         if (from_cblock(cache_size)) {
1683                 mq->cache_hit_bits = alloc_bitset(from_cblock(cache_size));
1684                 if (!mq->cache_hit_bits) {
1685                         DMERR("couldn't allocate cache hit bitset");
1686                         goto bad_cache_hit_bits;
1687                 }
1688                 clear_bitset(mq->cache_hit_bits, from_cblock(mq->cache_size));
1689         } else
1690                 mq->cache_hit_bits = NULL;
1691
1692         mq->tick = 0;
1693         spin_lock_init(&mq->lock);
1694
1695         q_init(&mq->hotspot, &mq->es, NR_HOTSPOT_LEVELS);
1696         mq->hotspot.nr_top_levels = 8;
1697         mq->hotspot.nr_in_top_levels = min(mq->nr_hotspot_blocks / NR_HOTSPOT_LEVELS,
1698                                            from_cblock(mq->cache_size) / mq->cache_blocks_per_hotspot_block);
1699
1700         q_init(&mq->clean, &mq->es, NR_CACHE_LEVELS);
1701         q_init(&mq->dirty, &mq->es, NR_CACHE_LEVELS);
1702
1703         stats_init(&mq->hotspot_stats, NR_HOTSPOT_LEVELS);
1704         stats_init(&mq->cache_stats, NR_CACHE_LEVELS);
1705
1706         if (h_init(&mq->table, &mq->es, from_cblock(cache_size)))
1707                 goto bad_alloc_table;
1708
1709         if (h_init(&mq->hotspot_table, &mq->es, mq->nr_hotspot_blocks))
1710                 goto bad_alloc_hotspot_table;
1711
1712         sentinels_init(mq);
1713         mq->write_promote_level = mq->read_promote_level = NR_HOTSPOT_LEVELS;
1714
1715         mq->next_hotspot_period = jiffies;
1716         mq->next_cache_period = jiffies;
1717
1718         return &mq->policy;
1719
1720 bad_alloc_hotspot_table:
1721         h_exit(&mq->table);
1722 bad_alloc_table:
1723         free_bitset(mq->cache_hit_bits);
1724 bad_cache_hit_bits:
1725         free_bitset(mq->hotspot_hit_bits);
1726 bad_hotspot_hit_bits:
1727         space_exit(&mq->es);
1728 bad_pool_init:
1729         kfree(mq);
1730
1731         return NULL;
1732 }
1733
1734 static struct dm_cache_policy *smq_create(dm_cblock_t cache_size,
1735                                           sector_t origin_size,
1736                                           sector_t cache_block_size)
1737 {
1738         return __smq_create(cache_size, origin_size, cache_block_size, false);
1739 }
1740
1741 static struct dm_cache_policy *mq_create(dm_cblock_t cache_size,
1742                                          sector_t origin_size,
1743                                          sector_t cache_block_size)
1744 {
1745         return __smq_create(cache_size, origin_size, cache_block_size, true);
1746 }
1747
1748 /*----------------------------------------------------------------*/
1749
1750 static struct dm_cache_policy_type smq_policy_type = {
1751         .name = "smq",
1752         .version = {1, 5, 0},
1753         .hint_size = 4,
1754         .owner = THIS_MODULE,
1755         .create = smq_create
1756 };
1757
1758 static struct dm_cache_policy_type mq_policy_type = {
1759         .name = "mq",
1760         .version = {1, 5, 0},
1761         .hint_size = 4,
1762         .owner = THIS_MODULE,
1763         .create = mq_create,
1764 };
1765
1766 static struct dm_cache_policy_type default_policy_type = {
1767         .name = "default",
1768         .version = {1, 5, 0},
1769         .hint_size = 4,
1770         .owner = THIS_MODULE,
1771         .create = smq_create,
1772         .real = &smq_policy_type
1773 };
1774
1775 static int __init smq_init(void)
1776 {
1777         int r;
1778
1779         r = dm_cache_policy_register(&smq_policy_type);
1780         if (r) {
1781                 DMERR("register failed %d", r);
1782                 return -ENOMEM;
1783         }
1784
1785         r = dm_cache_policy_register(&mq_policy_type);
1786         if (r) {
1787                 DMERR("register failed (as mq) %d", r);
1788                 dm_cache_policy_unregister(&smq_policy_type);
1789                 return -ENOMEM;
1790         }
1791
1792         r = dm_cache_policy_register(&default_policy_type);
1793         if (r) {
1794                 DMERR("register failed (as default) %d", r);
1795                 dm_cache_policy_unregister(&mq_policy_type);
1796                 dm_cache_policy_unregister(&smq_policy_type);
1797                 return -ENOMEM;
1798         }
1799
1800         return 0;
1801 }
1802
1803 static void __exit smq_exit(void)
1804 {
1805         dm_cache_policy_unregister(&smq_policy_type);
1806         dm_cache_policy_unregister(&mq_policy_type);
1807         dm_cache_policy_unregister(&default_policy_type);
1808 }
1809
1810 module_init(smq_init);
1811 module_exit(smq_exit);
1812
1813 MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
1814 MODULE_LICENSE("GPL");
1815 MODULE_DESCRIPTION("smq cache policy");
1816
1817 MODULE_ALIAS("dm-cache-default");
1818 MODULE_ALIAS("dm-cache-mq");