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