1957 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*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 separate59 * 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 else158 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 else174 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 else206 l->head = e->next;207 208 if (next)209 next->prev = e->prev;210 else211 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 the248 * most accessed entries in the top levels and least in the bottom. This249 * structure is *much* better than a single lru list.250 */251#define MAX_LEVELS 64u252 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 each262 * 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 else349 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 only370 * used by redistribute, so we know this is true. It also doesn't adjust371 * 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 us405 * 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 else425 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 } else501 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 8513#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_WELL526};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 else545 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 spread556 * out across the levels, or if an io load changes. We detect this by557 * 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 else570 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 we583 * 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 else653 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 likely668 * 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 to684 * 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 and719 * 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 64u789#define NR_CACHE_LEVELS 64u790 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 currently822 * active mappings. The hotspot queue uses a larger block size to823 * track blocks that are being hit frequently and potential824 * 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 to835 * 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 origin841 * 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 cache864 * 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 else969 q_push(&mq->clean, e);970}971 972// !h, !q, a -> h, q, a973static 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 else985 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 the1024 * cache.1025 *1026 * If the cache is performing badly, then we can't afford1027 * to promote much without causing performance to drop below that1028 * of the origin device.1029 *1030 * If the cache is performing well, then we don't need to promote1031 * 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 a1036 * 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, 11040 };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 really1052 * 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 little1061 * confidence that we know which blocks to promote. So we cut down1062 * 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 entries1083 * 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 25u1134#define FREE_TARGET 25u1135 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 the1145 * 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 happen1250 * 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 the1262 * 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_PERMANENT1281};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 } else1300 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 a1353 * 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 the1467 * 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, a1479 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, a1485 } else {1486 free_entry(&mq->cache_alloc, e);1487 // !h, !q, !a1488 }1489 break;1490 1491 case POLICY_DEMOTE:1492 // h, !q, a1493 if (success) {1494 h_remove(&mq->table, e);1495 free_entry(&mq->cache_alloc, e);1496 // !h, !q, !a1497 } else {1498 clear_pending(mq, e);1499 push_queue(mq, e);1500 // h, q, a1501 }1502 break;1503 1504 case POLICY_WRITEBACK:1505 // h, !q, a1506 clear_pending(mq, e);1507 push_queue(mq, e);1508 // h, q, a1509 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 to1581 * 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 breaking1649 * 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 } else1787 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_create1872};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_type1897};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