1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * Copyright (C) 2015 Red Hat. All rights reserved.
4  *
5  * This file is released under the GPL.
6  */
7 
8 #include "dm-cache-background-tracker.h"
9 #include "dm-cache-policy-internal.h"
10 #include "dm-cache-policy.h"
11 #include "dm.h"
12 
13 #include <linux/hash.h>
14 #include <linux/jiffies.h>
15 #include <linux/module.h>
16 #include <linux/mutex.h>
17 #include <linux/vmalloc.h>
18 #include <linux/math64.h>
19 
20 #define DM_MSG_PREFIX "cache-policy-smq"
21 
22 /*----------------------------------------------------------------*/
23 
24 /*
25  * Safe division functions that return zero on divide by zero.
26  */
27 static unsigned int safe_div(unsigned int n, unsigned int d)
28 {
29 	return d ? n / d : 0u;
30 }
31 
32 static unsigned int safe_mod(unsigned int n, unsigned int d)
33 {
34 	return d ? n % d : 0u;
35 }
36 
37 /*----------------------------------------------------------------*/
38 
39 struct entry {
40 	unsigned int hash_next:28;
41 	unsigned int prev:28;
42 	unsigned int next:28;
43 	unsigned int level:6;
44 	bool dirty:1;
45 	bool allocated:1;
46 	bool sentinel:1;
47 	bool pending_work:1;
48 
49 	dm_oblock_t oblock;
50 };
51 
52 /*----------------------------------------------------------------*/
53 
54 #define INDEXER_NULL ((1u << 28u) - 1u)
55 
56 /*
57  * An entry_space manages a set of entries that we use for the queues.
58  * The clean and dirty queues share entries, so this object is separate
59  * from the queue itself.
60  */
61 struct entry_space {
62 	struct entry *begin;
63 	struct entry *end;
64 };
65 
66 static 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 
81 static void space_exit(struct entry_space *es)
82 {
83 	vfree(es->begin);
84 }
85 
86 static 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 
96 static 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 
102 static 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 
112 struct ilist {
113 	unsigned int nr_elts;	/* excluding sentinel entries */
114 	unsigned int head, tail;
115 };
116 
117 static void l_init(struct ilist *l)
118 {
119 	l->nr_elts = 0;
120 	l->head = l->tail = INDEXER_NULL;
121 }
122 
123 static struct entry *l_head(struct entry_space *es, struct ilist *l)
124 {
125 	return to_entry(es, l->head);
126 }
127 
128 static struct entry *l_tail(struct entry_space *es, struct ilist *l)
129 {
130 	return to_entry(es, l->tail);
131 }
132 
133 static struct entry *l_next(struct entry_space *es, struct entry *e)
134 {
135 	return to_entry(es, e->next);
136 }
137 
138 static struct entry *l_prev(struct entry_space *es, struct entry *e)
139 {
140 	return to_entry(es, e->prev);
141 }
142 
143 static bool l_empty(struct ilist *l)
144 {
145 	return l->head == INDEXER_NULL;
146 }
147 
148 static void l_add_head(struct entry_space *es, struct ilist *l, struct entry *e)
149 {
150 	struct entry *head = l_head(es, l);
151 
152 	e->next = l->head;
153 	e->prev = INDEXER_NULL;
154 
155 	if (head)
156 		head->prev = l->head = to_index(es, e);
157 	else
158 		l->head = l->tail = to_index(es, e);
159 
160 	if (!e->sentinel)
161 		l->nr_elts++;
162 }
163 
164 static void l_add_tail(struct entry_space *es, struct ilist *l, struct entry *e)
165 {
166 	struct entry *tail = l_tail(es, l);
167 
168 	e->next = INDEXER_NULL;
169 	e->prev = l->tail;
170 
171 	if (tail)
172 		tail->next = l->tail = to_index(es, e);
173 	else
174 		l->head = l->tail = to_index(es, e);
175 
176 	if (!e->sentinel)
177 		l->nr_elts++;
178 }
179 
180 static 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 
198 static void l_del(struct entry_space *es, struct ilist *l, struct entry *e)
199 {
200 	struct entry *prev = l_prev(es, e);
201 	struct entry *next = l_next(es, e);
202 
203 	if (prev)
204 		prev->next = e->next;
205 	else
206 		l->head = e->next;
207 
208 	if (next)
209 		next->prev = e->prev;
210 	else
211 		l->tail = e->prev;
212 
213 	if (!e->sentinel)
214 		l->nr_elts--;
215 }
216 
217 static 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 
230 static struct entry *l_pop_tail(struct entry_space *es, struct ilist *l)
231 {
232 	struct entry *e;
233 
234 	for (e = l_tail(es, l); e; e = l_prev(es, e))
235 		if (!e->sentinel) {
236 			l_del(es, l, e);
237 			return e;
238 		}
239 
240 	return NULL;
241 }
242 
243 /*----------------------------------------------------------------*/
244 
245 /*
246  * The stochastic-multi-queue is a set of lru lists stacked into levels.
247  * Entries are moved up levels when they are used, which loosely orders the
248  * most accessed entries in the top levels and least in the bottom.  This
249  * structure is *much* better than a single lru list.
250  */
251 #define MAX_LEVELS 64u
252 
253 struct queue {
254 	struct entry_space *es;
255 
256 	unsigned int nr_elts;
257 	unsigned int nr_levels;
258 	struct ilist qs[MAX_LEVELS];
259 
260 	/*
261 	 * We maintain a count of the number of entries we would like in each
262 	 * level.
263 	 */
264 	unsigned int last_target_nr_elts;
265 	unsigned int nr_top_levels;
266 	unsigned int nr_in_top_levels;
267 	unsigned int target_count[MAX_LEVELS];
268 };
269 
270 static 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 
288 static 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  */
296 static 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 
306 static 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 
316 static 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 
326 static 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  */
336 static struct entry *q_peek(struct queue *q, unsigned int max_level, bool can_cross_sentinel)
337 {
338 	unsigned int level;
339 	struct entry *e;
340 
341 	max_level = min(max_level, q->nr_levels);
342 
343 	for (level = 0; level < max_level; level++)
344 		for (e = l_head(q->es, q->qs + level); e; e = l_next(q->es, e)) {
345 			if (e->sentinel) {
346 				if (can_cross_sentinel)
347 					continue;
348 				else
349 					break;
350 			}
351 
352 			return e;
353 		}
354 
355 	return NULL;
356 }
357 
358 static struct entry *q_pop(struct queue *q)
359 {
360 	struct entry *e = q_peek(q, q->nr_levels, true);
361 
362 	if (e)
363 		q_del(q, e);
364 
365 	return e;
366 }
367 
368 /*
369  * This function assumes there is a non-sentinel entry to pop.  It's only
370  * used by redistribute, so we know this is true.  It also doesn't adjust
371  * the q->nr_elts count.
372  */
373 static 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 
387 static void q_set_targets_subrange_(struct queue *q, unsigned int nr_elts,
388 				    unsigned int lbegin, unsigned int lend)
389 {
390 	unsigned int level, nr_levels, entries_per_level, remainder;
391 
392 	BUG_ON(lbegin > lend);
393 	BUG_ON(lend > q->nr_levels);
394 	nr_levels = lend - lbegin;
395 	entries_per_level = safe_div(nr_elts, nr_levels);
396 	remainder = safe_mod(nr_elts, nr_levels);
397 
398 	for (level = lbegin; level < lend; level++)
399 		q->target_count[level] =
400 			(level < (lbegin + remainder)) ? entries_per_level + 1u : entries_per_level;
401 }
402 
403 /*
404  * Typically we have fewer elements in the top few levels which allows us
405  * to adjust the promote threshold nicely.
406  */
407 static void q_set_targets(struct queue *q)
408 {
409 	if (q->last_target_nr_elts == q->nr_elts)
410 		return;
411 
412 	q->last_target_nr_elts = q->nr_elts;
413 
414 	if (q->nr_top_levels > q->nr_levels)
415 		q_set_targets_subrange_(q, q->nr_elts, 0, q->nr_levels);
416 
417 	else {
418 		q_set_targets_subrange_(q, q->nr_in_top_levels,
419 					q->nr_levels - q->nr_top_levels, q->nr_levels);
420 
421 		if (q->nr_in_top_levels < q->nr_elts)
422 			q_set_targets_subrange_(q, q->nr_elts - q->nr_in_top_levels,
423 						0, q->nr_levels - q->nr_top_levels);
424 		else
425 			q_set_targets_subrange_(q, 0, 0, q->nr_levels - q->nr_top_levels);
426 	}
427 }
428 
429 static 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 
472 static void q_requeue(struct queue *q, struct entry *e, unsigned int extra_levels,
473 		      struct entry *s1, struct entry *s2)
474 {
475 	struct entry *de;
476 	unsigned int sentinels_passed = 0;
477 	unsigned int new_level = min(q->nr_levels - 1u, e->level + extra_levels);
478 
479 	/* try and find an entry to swap with */
480 	if (extra_levels && (e->level < q->nr_levels - 1u)) {
481 		for (de = l_head(q->es, q->qs + new_level); de && de->sentinel; de = l_next(q->es, de))
482 			sentinels_passed++;
483 
484 		if (de) {
485 			q_del(q, de);
486 			de->level = e->level;
487 			if (s1) {
488 				switch (sentinels_passed) {
489 				case 0:
490 					q_push_before(q, s1, de);
491 					break;
492 
493 				case 1:
494 					q_push_before(q, s2, de);
495 					break;
496 
497 				default:
498 					q_push(q, de);
499 				}
500 			} else
501 				q_push(q, de);
502 		}
503 	}
504 
505 	q_del(q, e);
506 	e->level = new_level;
507 	q_push(q, e);
508 }
509 
510 /*----------------------------------------------------------------*/
511 
512 #define FP_SHIFT 8
513 #define SIXTEENTH (1u << (FP_SHIFT - 4u))
514 #define EIGHTH (1u << (FP_SHIFT - 3u))
515 
516 struct stats {
517 	unsigned int hit_threshold;
518 	unsigned int hits;
519 	unsigned int misses;
520 };
521 
522 enum performance {
523 	Q_POOR,
524 	Q_FAIR,
525 	Q_WELL
526 };
527 
528 static 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 
535 static void stats_reset(struct stats *s)
536 {
537 	s->hits = s->misses = 0u;
538 }
539 
540 static void stats_level_accessed(struct stats *s, unsigned int level)
541 {
542 	if (level >= s->hit_threshold)
543 		s->hits++;
544 	else
545 		s->misses++;
546 }
547 
548 static void stats_miss(struct stats *s)
549 {
550 	s->misses++;
551 }
552 
553 /*
554  * There are times when we don't have any confidence in the hotspot queue.
555  * Such as when a fresh cache is created and the blocks have been spread
556  * out across the levels, or if an io load changes.  We detect this by
557  * seeing how often a lookup is in the top levels of the hotspot queue.
558  */
559 static enum performance stats_assess(struct stats *s)
560 {
561 	unsigned int confidence = safe_div(s->hits << FP_SHIFT, s->hits + s->misses);
562 
563 	if (confidence < SIXTEENTH)
564 		return Q_POOR;
565 
566 	else if (confidence < EIGHTH)
567 		return Q_FAIR;
568 
569 	else
570 		return Q_WELL;
571 }
572 
573 /*----------------------------------------------------------------*/
574 
575 struct smq_hash_table {
576 	struct entry_space *es;
577 	unsigned long long hash_bits;
578 	unsigned int *buckets;
579 };
580 
581 /*
582  * All cache entries are stored in a chained hash table.  To save space we
583  * use indexing again, and only store indexes to the next entry.
584  */
585 static 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 
603 static void h_exit(struct smq_hash_table *ht)
604 {
605 	vfree(ht->buckets);
606 }
607 
608 static struct entry *h_head(struct smq_hash_table *ht, unsigned int bucket)
609 {
610 	return to_entry(ht->es, ht->buckets[bucket]);
611 }
612 
613 static struct entry *h_next(struct smq_hash_table *ht, struct entry *e)
614 {
615 	return to_entry(ht->es, e->hash_next);
616 }
617 
618 static 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 
624 static 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 
631 static 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 
647 static void __h_unlink(struct smq_hash_table *ht, unsigned int h,
648 		       struct entry *e, struct entry *prev)
649 {
650 	if (prev)
651 		prev->hash_next = e->hash_next;
652 	else
653 		ht->buckets[h] = e->hash_next;
654 }
655 
656 /*
657  * Also moves each entry to the front of the bucket.
658  */
659 static struct entry *h_lookup(struct smq_hash_table *ht, dm_oblock_t oblock)
660 {
661 	struct entry *e, *prev;
662 	unsigned int h = hash_64(from_oblock(oblock), ht->hash_bits);
663 
664 	e = __h_lookup(ht, h, oblock, &prev);
665 	if (e && prev) {
666 		/*
667 		 * Move to the front because this entry is likely
668 		 * to be hit again.
669 		 */
670 		__h_unlink(ht, h, e, prev);
671 		__h_insert(ht, h, e);
672 	}
673 
674 	return e;
675 }
676 
677 static void h_remove(struct smq_hash_table *ht, struct entry *e)
678 {
679 	unsigned int h = hash_64(from_oblock(e->oblock), ht->hash_bits);
680 	struct entry *prev;
681 
682 	/*
683 	 * The down side of using a singly linked list is we have to
684 	 * iterate the bucket to remove an item.
685 	 */
686 	e = __h_lookup(ht, h, e->oblock, &prev);
687 	if (e)
688 		__h_unlink(ht, h, e, prev);
689 }
690 
691 /*----------------------------------------------------------------*/
692 
693 struct entry_alloc {
694 	struct entry_space *es;
695 	unsigned int begin;
696 
697 	unsigned int nr_allocated;
698 	struct ilist free;
699 };
700 
701 static 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 
715 static void init_entry(struct entry *e)
716 {
717 	/*
718 	 * We can't memset because that would clear the hotspot and
719 	 * sentinel bits which remain constant.
720 	 */
721 	e->hash_next = INDEXER_NULL;
722 	e->next = INDEXER_NULL;
723 	e->prev = INDEXER_NULL;
724 	e->level = 0u;
725 	e->dirty = true;	/* FIXME: audit */
726 	e->allocated = true;
727 	e->sentinel = false;
728 	e->pending_work = false;
729 }
730 
731 static 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  */
748 static 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 
761 static 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 
771 static bool allocator_empty(struct entry_alloc *ea)
772 {
773 	return l_empty(&ea->free);
774 }
775 
776 static unsigned int get_index(struct entry_alloc *ea, struct entry *e)
777 {
778 	return to_index(ea->es, e) - ea->begin;
779 }
780 
781 static struct entry *get_entry(struct entry_alloc *ea, unsigned int index)
782 {
783 	return __get_entry(ea->es, ea->begin + index);
784 }
785 
786 /*----------------------------------------------------------------*/
787 
788 #define NR_HOTSPOT_LEVELS 64u
789 #define NR_CACHE_LEVELS 64u
790 
791 #define WRITEBACK_PERIOD (10ul * HZ)
792 #define DEMOTE_PERIOD (60ul * HZ)
793 
794 #define HOTSPOT_UPDATE_PERIOD (HZ)
795 #define CACHE_UPDATE_PERIOD (60ul * HZ)
796 
797 struct smq_policy {
798 	struct dm_cache_policy policy;
799 
800 	/* protects everything */
801 	spinlock_t lock;
802 	dm_cblock_t cache_size;
803 	sector_t cache_block_size;
804 
805 	sector_t hotspot_block_size;
806 	unsigned int nr_hotspot_blocks;
807 	unsigned int cache_blocks_per_hotspot_block;
808 	unsigned int hotspot_level_jump;
809 
810 	struct entry_space es;
811 	struct entry_alloc writeback_sentinel_alloc;
812 	struct entry_alloc demote_sentinel_alloc;
813 	struct entry_alloc hotspot_alloc;
814 	struct entry_alloc cache_alloc;
815 
816 	unsigned long *hotspot_hit_bits;
817 	unsigned long *cache_hit_bits;
818 
819 	/*
820 	 * We maintain three queues of entries.  The cache proper,
821 	 * consisting of a clean and dirty queue, containing the currently
822 	 * active mappings.  The hotspot queue uses a larger block size to
823 	 * track blocks that are being hit frequently and potential
824 	 * candidates for promotion to the cache.
825 	 */
826 	struct queue hotspot;
827 	struct queue clean;
828 	struct queue dirty;
829 
830 	struct stats hotspot_stats;
831 	struct stats cache_stats;
832 
833 	/*
834 	 * Keeps track of time, incremented by the core.  We use this to
835 	 * avoid attributing multiple hits within the same tick.
836 	 */
837 	unsigned int tick;
838 
839 	/*
840 	 * The hash tables allows us to quickly find an entry by origin
841 	 * block.
842 	 */
843 	struct smq_hash_table table;
844 	struct smq_hash_table hotspot_table;
845 
846 	bool current_writeback_sentinels;
847 	unsigned long next_writeback_period;
848 
849 	bool current_demote_sentinels;
850 	unsigned long next_demote_period;
851 
852 	unsigned int write_promote_level;
853 	unsigned int read_promote_level;
854 
855 	unsigned long next_hotspot_period;
856 	unsigned long next_cache_period;
857 
858 	struct background_tracker *bg_work;
859 
860 	bool migrations_allowed:1;
861 
862 	/*
863 	 * If this is set the policy will try and clean the whole cache
864 	 * even if the device is not idle.
865 	 */
866 	bool cleaner:1;
867 };
868 
869 /*----------------------------------------------------------------*/
870 
871 static 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 
876 static 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 
881 static 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 
886 static 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 
899 static 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 
912 static 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 
927 static 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 
943 static 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 
959 static void del_queue(struct smq_policy *mq, struct entry *e)
960 {
961 	q_del(e->dirty ? &mq->dirty : &mq->clean, e);
962 }
963 
964 static void push_queue(struct smq_policy *mq, struct entry *e)
965 {
966 	if (e->dirty)
967 		q_push(&mq->dirty, e);
968 	else
969 		q_push(&mq->clean, e);
970 }
971 
972 // !h, !q, a -> h, q, a
973 static 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 
980 static void push_queue_front(struct smq_policy *mq, struct entry *e)
981 {
982 	if (e->dirty)
983 		q_push_front(&mq->dirty, e);
984 	else
985 		q_push_front(&mq->clean, e);
986 }
987 
988 static 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 
995 static 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 
1000 static 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 
1020 static unsigned int default_promote_level(struct smq_policy *mq)
1021 {
1022 	/*
1023 	 * The promote level depends on the current performance of the
1024 	 * cache.
1025 	 *
1026 	 * If the cache is performing badly, then we can't afford
1027 	 * to promote much without causing performance to drop below that
1028 	 * of the origin device.
1029 	 *
1030 	 * If the cache is performing well, then we don't need to promote
1031 	 * much.  If it isn't broken, don't fix it.
1032 	 *
1033 	 * If the cache is middling then we promote more.
1034 	 *
1035 	 * This scheme reminds me of a graph of entropy vs probability of a
1036 	 * binary variable.
1037 	 */
1038 	static const unsigned int table[] = {
1039 		1, 1, 1, 2, 4, 6, 7, 8, 7, 6, 4, 4, 3, 3, 2, 2, 1
1040 	};
1041 
1042 	unsigned int hits = mq->cache_stats.hits;
1043 	unsigned int misses = mq->cache_stats.misses;
1044 	unsigned int index = safe_div(hits << 4u, hits + misses);
1045 	return table[index];
1046 }
1047 
1048 static void update_promote_levels(struct smq_policy *mq)
1049 {
1050 	/*
1051 	 * If there are unused cache entries then we want to be really
1052 	 * eager to promote.
1053 	 */
1054 	unsigned int threshold_level = allocator_empty(&mq->cache_alloc) ?
1055 		default_promote_level(mq) : (NR_HOTSPOT_LEVELS / 2u);
1056 
1057 	threshold_level = max(threshold_level, NR_HOTSPOT_LEVELS);
1058 
1059 	/*
1060 	 * If the hotspot queue is performing badly then we have little
1061 	 * confidence that we know which blocks to promote.  So we cut down
1062 	 * the amount of promotions.
1063 	 */
1064 	switch (stats_assess(&mq->hotspot_stats)) {
1065 	case Q_POOR:
1066 		threshold_level /= 4u;
1067 		break;
1068 
1069 	case Q_FAIR:
1070 		threshold_level /= 2u;
1071 		break;
1072 
1073 	case Q_WELL:
1074 		break;
1075 	}
1076 
1077 	mq->read_promote_level = NR_HOTSPOT_LEVELS - threshold_level;
1078 	mq->write_promote_level = (NR_HOTSPOT_LEVELS - threshold_level);
1079 }
1080 
1081 /*
1082  * If the hotspot queue is performing badly, then we try and move entries
1083  * around more quickly.
1084  */
1085 static 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 
1102 static 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 
1115 static void end_cache_period(struct smq_policy *mq)
1116 {
1117 	if (time_after(jiffies, mq->next_cache_period)) {
1118 		clear_bitset(mq->cache_hit_bits, from_cblock(mq->cache_size));
1119 
1120 		q_redistribute(&mq->dirty);
1121 		q_redistribute(&mq->clean);
1122 		stats_reset(&mq->cache_stats);
1123 
1124 		mq->next_cache_period = jiffies + CACHE_UPDATE_PERIOD;
1125 	}
1126 }
1127 
1128 /*----------------------------------------------------------------*/
1129 
1130 /*
1131  * Targets are given as a percentage.
1132  */
1133 #define CLEAN_TARGET 25u
1134 #define FREE_TARGET 25u
1135 
1136 static unsigned int percent_to_target(struct smq_policy *mq, unsigned int p)
1137 {
1138 	return from_cblock(mq->cache_size) * p / 100u;
1139 }
1140 
1141 static bool clean_target_met(struct smq_policy *mq, bool idle)
1142 {
1143 	/*
1144 	 * Cache entries may not be populated.  So we cannot rely on the
1145 	 * size of the clean queue.
1146 	 */
1147 	if (idle || mq->cleaner) {
1148 		/*
1149 		 * We'd like to clean everything.
1150 		 */
1151 		return q_size(&mq->dirty) == 0u;
1152 	}
1153 
1154 	/*
1155 	 * If we're busy we don't worry about cleaning at all.
1156 	 */
1157 	return true;
1158 }
1159 
1160 static 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 
1171 static 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 
1179 static void clear_pending(struct smq_policy *mq, struct entry *e)
1180 {
1181 	BUG_ON(!e->pending_work);
1182 	e->pending_work = false;
1183 }
1184 
1185 static 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 
1208 static 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 
1237 static void queue_promotion(struct smq_policy *mq, dm_oblock_t oblock,
1238 			    struct policy_work **workp)
1239 {
1240 	int r;
1241 	struct entry *e;
1242 	struct policy_work work;
1243 
1244 	if (!mq->migrations_allowed)
1245 		return;
1246 
1247 	if (allocator_empty(&mq->cache_alloc)) {
1248 		/*
1249 		 * We always claim to be 'idle' to ensure some demotions happen
1250 		 * with continuous loads.
1251 		 */
1252 		if (!free_target_met(mq))
1253 			queue_demotion(mq);
1254 		return;
1255 	}
1256 
1257 	if (btracker_promotion_already_present(mq->bg_work, oblock))
1258 		return;
1259 
1260 	/*
1261 	 * We allocate the entry now to reserve the cblock.  If the
1262 	 * background work is aborted we must remember to free it.
1263 	 */
1264 	e = alloc_entry(&mq->cache_alloc);
1265 	BUG_ON(!e);
1266 	e->pending_work = true;
1267 	work.op = POLICY_PROMOTE;
1268 	work.oblock = oblock;
1269 	work.cblock = infer_cblock(mq, e);
1270 	r = btracker_queue(mq->bg_work, &work, workp);
1271 	if (r)
1272 		free_entry(&mq->cache_alloc, e);
1273 }
1274 
1275 /*----------------------------------------------------------------*/
1276 
1277 enum promote_result {
1278 	PROMOTE_NOT,
1279 	PROMOTE_TEMPORARY,
1280 	PROMOTE_PERMANENT
1281 };
1282 
1283 /*
1284  * Converts a boolean into a promote result.
1285  */
1286 static enum promote_result maybe_promote(bool promote)
1287 {
1288 	return promote ? PROMOTE_PERMANENT : PROMOTE_NOT;
1289 }
1290 
1291 static enum promote_result should_promote(struct smq_policy *mq, struct entry *hs_e,
1292 					  int data_dir, bool fast_promote)
1293 {
1294 	if (data_dir == WRITE) {
1295 		if (!allocator_empty(&mq->cache_alloc) && fast_promote)
1296 			return PROMOTE_TEMPORARY;
1297 
1298 		return maybe_promote(hs_e->level >= mq->write_promote_level);
1299 	} else
1300 		return maybe_promote(hs_e->level >= mq->read_promote_level);
1301 }
1302 
1303 static 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 
1310 static struct entry *update_hotspot_queue(struct smq_policy *mq, dm_oblock_t b)
1311 {
1312 	unsigned int hi;
1313 	dm_oblock_t hb = to_hblock(mq, b);
1314 	struct entry *e = h_lookup(&mq->hotspot_table, hb);
1315 
1316 	if (e) {
1317 		stats_level_accessed(&mq->hotspot_stats, e->level);
1318 
1319 		hi = get_index(&mq->hotspot_alloc, e);
1320 		q_requeue(&mq->hotspot, e,
1321 			  test_and_set_bit(hi, mq->hotspot_hit_bits) ?
1322 			  0u : mq->hotspot_level_jump,
1323 			  NULL, NULL);
1324 
1325 	} else {
1326 		stats_miss(&mq->hotspot_stats);
1327 
1328 		e = alloc_entry(&mq->hotspot_alloc);
1329 		if (!e) {
1330 			e = q_pop(&mq->hotspot);
1331 			if (e) {
1332 				h_remove(&mq->hotspot_table, e);
1333 				hi = get_index(&mq->hotspot_alloc, e);
1334 				clear_bit(hi, mq->hotspot_hit_bits);
1335 			}
1336 
1337 		}
1338 
1339 		if (e) {
1340 			e->oblock = hb;
1341 			q_push(&mq->hotspot, e);
1342 			h_insert(&mq->hotspot_table, e);
1343 		}
1344 	}
1345 
1346 	return e;
1347 }
1348 
1349 /*----------------------------------------------------------------*/
1350 
1351 /*
1352  * Public interface, via the policy struct.  See dm-cache-policy.h for a
1353  * description of these.
1354  */
1355 
1356 static struct smq_policy *to_smq_policy(struct dm_cache_policy *p)
1357 {
1358 	return container_of(p, struct smq_policy, policy);
1359 }
1360 
1361 static 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 
1376 static 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 
1411 static 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 
1428 static 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 
1445 static int smq_get_background_work(struct dm_cache_policy *p, bool idle,
1446 				   struct policy_work **result)
1447 {
1448 	int r;
1449 	unsigned long flags;
1450 	struct smq_policy *mq = to_smq_policy(p);
1451 
1452 	spin_lock_irqsave(&mq->lock, flags);
1453 	r = btracker_issue(mq->bg_work, result);
1454 	if (r == -ENODATA) {
1455 		if (!clean_target_met(mq, idle)) {
1456 			queue_writeback(mq, idle);
1457 			r = btracker_issue(mq->bg_work, result);
1458 		}
1459 	}
1460 	spin_unlock_irqrestore(&mq->lock, flags);
1461 
1462 	return r;
1463 }
1464 
1465 /*
1466  * We need to clear any pending work flags that have been set, and in the
1467  * case of promotion free the entry for the destination cblock.
1468  */
1469 static void __complete_background_work(struct smq_policy *mq,
1470 				       struct policy_work *work,
1471 				       bool success)
1472 {
1473 	struct entry *e = get_entry(&mq->cache_alloc,
1474 				    from_cblock(work->cblock));
1475 
1476 	switch (work->op) {
1477 	case POLICY_PROMOTE:
1478 		// !h, !q, a
1479 		clear_pending(mq, e);
1480 		if (success) {
1481 			e->oblock = work->oblock;
1482 			e->level = NR_CACHE_LEVELS - 1;
1483 			push(mq, e);
1484 			// h, q, a
1485 		} else {
1486 			free_entry(&mq->cache_alloc, e);
1487 			// !h, !q, !a
1488 		}
1489 		break;
1490 
1491 	case POLICY_DEMOTE:
1492 		// h, !q, a
1493 		if (success) {
1494 			h_remove(&mq->table, e);
1495 			free_entry(&mq->cache_alloc, e);
1496 			// !h, !q, !a
1497 		} else {
1498 			clear_pending(mq, e);
1499 			push_queue(mq, e);
1500 			// h, q, a
1501 		}
1502 		break;
1503 
1504 	case POLICY_WRITEBACK:
1505 		// h, !q, a
1506 		clear_pending(mq, e);
1507 		push_queue(mq, e);
1508 		// h, q, a
1509 		break;
1510 	}
1511 
1512 	btracker_complete(mq->bg_work, work);
1513 }
1514 
1515 static 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)
1528 static 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 
1541 static 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 
1551 static 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 
1561 static unsigned int random_level(dm_cblock_t cblock)
1562 {
1563 	return hash_32(from_cblock(cblock), 9) & (NR_CACHE_LEVELS - 1);
1564 }
1565 
1566 static int smq_load_mapping(struct dm_cache_policy *p,
1567 			    dm_oblock_t oblock, dm_cblock_t cblock,
1568 			    bool dirty, uint32_t hint, bool hint_valid)
1569 {
1570 	struct smq_policy *mq = to_smq_policy(p);
1571 	struct entry *e;
1572 
1573 	e = alloc_particular_entry(&mq->cache_alloc, from_cblock(cblock));
1574 	e->oblock = oblock;
1575 	e->dirty = dirty;
1576 	e->level = hint_valid ? min(hint, NR_CACHE_LEVELS - 1) : random_level(cblock);
1577 	e->pending_work = false;
1578 
1579 	/*
1580 	 * When we load mappings we push ahead of both sentinels in order to
1581 	 * allow demotions and cleaning to occur immediately.
1582 	 */
1583 	push_front(mq, e);
1584 
1585 	return 0;
1586 }
1587 
1588 static 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 
1603 static 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 
1614 static 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 
1627 static 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 
1640 static void smq_allow_migrations(struct dm_cache_policy *p, bool allow)
1641 {
1642 	struct smq_policy *mq = to_smq_policy(p);
1643 
1644 	mq->migrations_allowed = allow;
1645 }
1646 
1647 /*
1648  * smq has no config values, but the old mq policy did.  To avoid breaking
1649  * software we continue to accept these configurables for the mq policy,
1650  * but they have no effect.
1651  */
1652 static 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 
1672 static 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. */
1688 static 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 
1710 static 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 
1717 static 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 
1731 static struct dm_cache_policy *
1732 __smq_create(dm_cblock_t cache_size, sector_t origin_size, sector_t cache_block_size,
1733 	     bool mimic_mq, bool migrations_allowed, bool cleaner)
1734 {
1735 	unsigned int i;
1736 	unsigned int nr_sentinels_per_queue = 2u * NR_CACHE_LEVELS;
1737 	unsigned int total_sentinels = 2u * nr_sentinels_per_queue;
1738 	struct smq_policy *mq = kzalloc(sizeof(*mq), GFP_KERNEL);
1739 
1740 	if (!mq)
1741 		return NULL;
1742 
1743 	init_policy_functions(mq, mimic_mq);
1744 	mq->cache_size = cache_size;
1745 	mq->cache_block_size = cache_block_size;
1746 
1747 	calc_hotspot_params(origin_size, cache_block_size, from_cblock(cache_size),
1748 			    &mq->hotspot_block_size, &mq->nr_hotspot_blocks);
1749 
1750 	mq->cache_blocks_per_hotspot_block = div64_u64(mq->hotspot_block_size, mq->cache_block_size);
1751 	mq->hotspot_level_jump = 1u;
1752 	if (space_init(&mq->es, total_sentinels + mq->nr_hotspot_blocks + from_cblock(cache_size))) {
1753 		DMERR("couldn't initialize entry space");
1754 		goto bad_pool_init;
1755 	}
1756 
1757 	init_allocator(&mq->writeback_sentinel_alloc, &mq->es, 0, nr_sentinels_per_queue);
1758 	for (i = 0; i < nr_sentinels_per_queue; i++)
1759 		get_entry(&mq->writeback_sentinel_alloc, i)->sentinel = true;
1760 
1761 	init_allocator(&mq->demote_sentinel_alloc, &mq->es, nr_sentinels_per_queue, total_sentinels);
1762 	for (i = 0; i < nr_sentinels_per_queue; i++)
1763 		get_entry(&mq->demote_sentinel_alloc, i)->sentinel = true;
1764 
1765 	init_allocator(&mq->hotspot_alloc, &mq->es, total_sentinels,
1766 		       total_sentinels + mq->nr_hotspot_blocks);
1767 
1768 	init_allocator(&mq->cache_alloc, &mq->es,
1769 		       total_sentinels + mq->nr_hotspot_blocks,
1770 		       total_sentinels + mq->nr_hotspot_blocks + from_cblock(cache_size));
1771 
1772 	mq->hotspot_hit_bits = alloc_bitset(mq->nr_hotspot_blocks);
1773 	if (!mq->hotspot_hit_bits) {
1774 		DMERR("couldn't allocate hotspot hit bitset");
1775 		goto bad_hotspot_hit_bits;
1776 	}
1777 	clear_bitset(mq->hotspot_hit_bits, mq->nr_hotspot_blocks);
1778 
1779 	if (from_cblock(cache_size)) {
1780 		mq->cache_hit_bits = alloc_bitset(from_cblock(cache_size));
1781 		if (!mq->cache_hit_bits) {
1782 			DMERR("couldn't allocate cache hit bitset");
1783 			goto bad_cache_hit_bits;
1784 		}
1785 		clear_bitset(mq->cache_hit_bits, from_cblock(mq->cache_size));
1786 	} else
1787 		mq->cache_hit_bits = NULL;
1788 
1789 	mq->tick = 0;
1790 	spin_lock_init(&mq->lock);
1791 
1792 	q_init(&mq->hotspot, &mq->es, NR_HOTSPOT_LEVELS);
1793 	mq->hotspot.nr_top_levels = 8;
1794 	mq->hotspot.nr_in_top_levels = min(mq->nr_hotspot_blocks / NR_HOTSPOT_LEVELS,
1795 					   from_cblock(mq->cache_size) / mq->cache_blocks_per_hotspot_block);
1796 
1797 	q_init(&mq->clean, &mq->es, NR_CACHE_LEVELS);
1798 	q_init(&mq->dirty, &mq->es, NR_CACHE_LEVELS);
1799 
1800 	stats_init(&mq->hotspot_stats, NR_HOTSPOT_LEVELS);
1801 	stats_init(&mq->cache_stats, NR_CACHE_LEVELS);
1802 
1803 	if (h_init(&mq->table, &mq->es, from_cblock(cache_size)))
1804 		goto bad_alloc_table;
1805 
1806 	if (h_init(&mq->hotspot_table, &mq->es, mq->nr_hotspot_blocks))
1807 		goto bad_alloc_hotspot_table;
1808 
1809 	sentinels_init(mq);
1810 	mq->write_promote_level = mq->read_promote_level = NR_HOTSPOT_LEVELS;
1811 
1812 	mq->next_hotspot_period = jiffies;
1813 	mq->next_cache_period = jiffies;
1814 
1815 	mq->bg_work = btracker_create(4096); /* FIXME: hard coded value */
1816 	if (!mq->bg_work)
1817 		goto bad_btracker;
1818 
1819 	mq->migrations_allowed = migrations_allowed;
1820 	mq->cleaner = cleaner;
1821 
1822 	return &mq->policy;
1823 
1824 bad_btracker:
1825 	h_exit(&mq->hotspot_table);
1826 bad_alloc_hotspot_table:
1827 	h_exit(&mq->table);
1828 bad_alloc_table:
1829 	free_bitset(mq->cache_hit_bits);
1830 bad_cache_hit_bits:
1831 	free_bitset(mq->hotspot_hit_bits);
1832 bad_hotspot_hit_bits:
1833 	space_exit(&mq->es);
1834 bad_pool_init:
1835 	kfree(mq);
1836 
1837 	return NULL;
1838 }
1839 
1840 static 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 
1848 static 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 
1856 static 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 
1866 static struct dm_cache_policy_type smq_policy_type = {
1867 	.name = "smq",
1868 	.version = {2, 0, 0},
1869 	.hint_size = 4,
1870 	.owner = THIS_MODULE,
1871 	.create = smq_create
1872 };
1873 
1874 static 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 
1882 static 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 
1890 static struct dm_cache_policy_type default_policy_type = {
1891 	.name = "default",
1892 	.version = {2, 0, 0},
1893 	.hint_size = 4,
1894 	.owner = THIS_MODULE,
1895 	.create = smq_create,
1896 	.real = &smq_policy_type
1897 };
1898 
1899 static 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 
1929 out_default:
1930 	dm_cache_policy_unregister(&cleaner_policy_type);
1931 out_cleaner:
1932 	dm_cache_policy_unregister(&mq_policy_type);
1933 out_mq:
1934 	dm_cache_policy_unregister(&smq_policy_type);
1935 
1936 	return -ENOMEM;
1937 }
1938 
1939 static 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 
1947 module_init(smq_init);
1948 module_exit(smq_exit);
1949 
1950 MODULE_AUTHOR("Joe Thornber <dm-devel@redhat.com>");
1951 MODULE_LICENSE("GPL");
1952 MODULE_DESCRIPTION("smq cache policy");
1953 
1954 MODULE_ALIAS("dm-cache-default");
1955 MODULE_ALIAS("dm-cache-mq");
1956 MODULE_ALIAS("dm-cache-cleaner");
1957