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