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