85 	struct entry *e;  in __get_entry()  local
87 	e = es->begin + block;  in __get_entry()
88 	BUG_ON(e >= es->end);  in __get_entry()
90 	return e;  in __get_entry()
93 static unsigned to_index(struct entry_space *es, struct entry *e)  in to_index()  argument
95 	BUG_ON(e < es->begin || e >= es->end);  in to_index()
96 	return e - es->begin;  in to_index()
130 static struct entry *l_next(struct entry_space *es, struct entry *e)  in l_next()  argument
132 	return to_entry(es, e->next);  in l_next()
135 static struct entry *l_prev(struct entry_space *es, struct entry *e)  in l_prev()  argument
137 	return to_entry(es, e->prev);  in l_prev()
145 static void l_add_head(struct entry_space *es, struct ilist *l, struct entry *e)  in l_add_head()  argument
149 	e->next = l->head;  in l_add_head()
150 	e->prev = INDEXER_NULL;  in l_add_head()
153 		head->prev = l->head = to_index(es, e);  in l_add_head()
155 		l->head = l->tail = to_index(es, e);  in l_add_head()
157 	if (!e->sentinel)  in l_add_head()
161 static void l_add_tail(struct entry_space *es, struct ilist *l, struct entry *e)  in l_add_tail()  argument
165 	e->next = INDEXER_NULL;  in l_add_tail()
166 	e->prev = l->tail;  in l_add_tail()
169 		tail->next = l->tail = to_index(es, e);  in l_add_tail()
171 		l->head = l->tail = to_index(es, e);  in l_add_tail()
173 	if (!e->sentinel)  in l_add_tail()
178 			 struct entry *old, struct entry *e)  in l_add_before()  argument
183 		l_add_head(es, l, e);  in l_add_before()
186 		e->prev = old->prev;  in l_add_before()
187 		e->next = to_index(es, old);  in l_add_before()
188 		prev->next = old->prev = to_index(es, e);  in l_add_before()
190 		if (!e->sentinel)  in l_add_before()
195 static void l_del(struct entry_space *es, struct ilist *l, struct entry *e)  in l_del()  argument
197 	struct entry *prev = l_prev(es, e);  in l_del()
198 	struct entry *next = l_next(es, e);  in l_del()
201 		prev->next = e->next;  in l_del()
203 		l->head = e->next;  in l_del()
206 		next->prev = e->prev;  in l_del()
208 		l->tail = e->prev;  in l_del()
210 	if (!e->sentinel)  in l_del()
216 	struct entry *e;  in l_pop_tail()  local
218 	for (e = l_tail(es, l); e; e = l_prev(es, e))  in l_pop_tail()
219 		if (!e->sentinel) {  in l_pop_tail()
220 			l_del(es, l, e);  in l_pop_tail()
221 			return e;  in l_pop_tail()
280 static void q_push(struct queue *q, struct entry *e)  in q_push()  argument
282 	if (!e->sentinel)  in q_push()
285 	l_add_tail(q->es, q->qs + e->level, e);  in q_push()
288 static void q_push_before(struct queue *q, struct entry *old, struct entry *e)  in q_push_before()  argument
290 	if (!e->sentinel)  in q_push_before()
293 	l_add_before(q->es, q->qs + e->level, old, e);  in q_push_before()
296 static void q_del(struct queue *q, struct entry *e)  in q_del()  argument
298 	l_del(q->es, q->qs + e->level, e);  in q_del()
299 	if (!e->sentinel)  in q_del()
309 	struct entry *e;  in q_peek()  local
314 		for (e = l_head(q->es, q->qs + level); e; e = l_next(q->es, e)) {  in q_peek()
315 			if (e->sentinel) {  in q_peek()
322 			return e;  in q_peek()
330 	struct entry *e = q_peek(q, q->nr_levels, true);  in q_pop()  local
332 	if (e)  in q_pop()
333 		q_del(q, e);  in q_pop()
335 	return e;  in q_pop()
343 	struct entry *e = q_peek(q, max_level, false);  in q_pop_old()  local
345 	if (e)  in q_pop_old()
346 		q_del(q, e);  in q_pop_old()
348 	return e;  in q_pop_old()
358 	struct entry *e;  in __redist_pop_from()  local
361 		for (e = l_head(q->es, q->qs + level); e; e = l_next(q->es, e))  in __redist_pop_from()
362 			if (!e->sentinel) {  in __redist_pop_from()
363 				l_del(q->es, q->qs + e->level, e);  in __redist_pop_from()
364 				return e;  in __redist_pop_from()
415 	struct entry *e;  in q_redistribute()  local
427 			e = __redist_pop_from(q, level + 1u);  in q_redistribute()
428 			if (!e) {  in q_redistribute()
433 			e->level = level;  in q_redistribute()
434 			l_add_tail(q->es, l, e);  in q_redistribute()
442 			e = l_pop_tail(q->es, l);  in q_redistribute()
444 			if (!e)  in q_redistribute()
448 			e->level = level + 1u;  in q_redistribute()
449 			l_add_head(q->es, l_above, e);  in q_redistribute()
454 static void q_requeue_before(struct queue *q, struct entry *dest, struct entry *e, unsigned extra_l…  in q_requeue_before()  argument
459 	q_del(q, e);  in q_requeue_before()
461 	if (extra_levels && (e->level < q->nr_levels - 1u)) {  in q_requeue_before()
462 		new_level = min(q->nr_levels - 1u, e->level + extra_levels);  in q_requeue_before()
468 			de->level = e->level;  in q_requeue_before()
477 		e->level = new_level;  in q_requeue_before()
480 	q_push(q, e);  in q_requeue_before()
483 static void q_requeue(struct queue *q, struct entry *e, unsigned extra_levels)  in q_requeue()  argument
485 	q_requeue_before(q, NULL, e, extra_levels);  in q_requeue()
591 static struct entry *h_next(struct hash_table *ht, struct entry *e)  in h_next()  argument
593 	return to_entry(ht->es, e->hash_next);  in h_next()
596 static void __h_insert(struct hash_table *ht, unsigned bucket, struct entry *e)  in __h_insert()  argument
598 	e->hash_next = ht->buckets[bucket];  in __h_insert()
599 	ht->buckets[bucket] = to_index(ht->es, e);  in __h_insert()
602 static void h_insert(struct hash_table *ht, struct entry *e)  in h_insert()  argument
604 	unsigned h = hash_64(from_oblock(e->oblock), ht->hash_bits);  in h_insert()
605 	__h_insert(ht, h, e);  in h_insert()
611 	struct entry *e;  in __h_lookup()  local
614 	for (e = h_head(ht, h); e; e = h_next(ht, e)) {  in __h_lookup()
615 		if (e->oblock == oblock)  in __h_lookup()
616 			return e;  in __h_lookup()
618 		*prev = e;  in __h_lookup()
625 		       struct entry *e, struct entry *prev)  in __h_unlink()  argument
628 		prev->hash_next = e->hash_next;  in __h_unlink()
630 		ht->buckets[h] = e->hash_next;  in __h_unlink()
638 	struct entry *e, *prev;  in h_lookup()  local
641 	e = __h_lookup(ht, h, oblock, &prev);  in h_lookup()
642 	if (e && prev) {  in h_lookup()
647 		__h_unlink(ht, h, e, prev);  in h_lookup()
648 		__h_insert(ht, h, e);  in h_lookup()
651 	return e;  in h_lookup()
654 static void h_remove(struct hash_table *ht, struct entry *e)  in h_remove()  argument
656 	unsigned h = hash_64(from_oblock(e->oblock), ht->hash_bits);  in h_remove()
663 	e = __h_lookup(ht, h, e->oblock, &prev);  in h_remove()
664 	if (e)  in h_remove()
665 		__h_unlink(ht, h, e, prev);  in h_remove()
692 static void init_entry(struct entry *e)  in init_entry()  argument
698 	e->hash_next = INDEXER_NULL;  in init_entry()
699 	e->next = INDEXER_NULL;  in init_entry()
700 	e->prev = INDEXER_NULL;  in init_entry()
701 	e->level = 0u;  in init_entry()
702 	e->allocated = true;  in init_entry()
707 	struct entry *e;  in alloc_entry()  local
712 	e = l_pop_tail(ea->es, &ea->free);  in alloc_entry()
713 	init_entry(e);  in alloc_entry()
716 	return e;  in alloc_entry()
724 	struct entry *e = __get_entry(ea->es, ea->begin + i);  in alloc_particular_entry()  local
726 	BUG_ON(e->allocated);  in alloc_particular_entry()
728 	l_del(ea->es, &ea->free, e);  in alloc_particular_entry()
729 	init_entry(e);  in alloc_particular_entry()
732 	return e;  in alloc_particular_entry()
735 static void free_entry(struct entry_alloc *ea, struct entry *e)  in free_entry()  argument
738 	BUG_ON(!e->allocated);  in free_entry()
741 	e->allocated = false;  in free_entry()
742 	l_add_tail(ea->es, &ea->free, e);  in free_entry()
750 static unsigned get_index(struct entry_alloc *ea, struct entry *e)  in get_index()  argument
752 	return to_index(ea->es, e) - ea->begin;  in get_index()
926 static void push_new(struct smq_policy *mq, struct entry *e)  in push_new()  argument
928 	struct queue *q = e->dirty ? &mq->dirty : &mq->clean;  in push_new()
929 	h_insert(&mq->table, e);  in push_new()
930 	q_push(q, e);  in push_new()
933 static void push(struct smq_policy *mq, struct entry *e)  in push()  argument
937 	h_insert(&mq->table, e);  in push()
943 	if (e->dirty) {  in push()
944 		sentinel = writeback_sentinel(mq, e->level);  in push()
945 		q_push_before(&mq->dirty, sentinel, e);  in push()
947 		sentinel = demote_sentinel(mq, e->level);  in push()
948 		q_push_before(&mq->clean, sentinel, e);  in push()
955 static void __del(struct smq_policy *mq, struct queue *q, struct entry *e)  in __del()  argument
957 	q_del(q, e);  in __del()
958 	h_remove(&mq->table, e);  in __del()
961 static void del(struct smq_policy *mq, struct entry *e)  in del()  argument
963 	__del(mq, e->dirty ? &mq->dirty : &mq->clean, e);  in del()
968 	struct entry *e = q_pop_old(q, max_level);  in pop_old()  local
969 	if (e)  in pop_old()
970 		h_remove(&mq->table, e);  in pop_old()
971 	return e;  in pop_old()
974 static dm_cblock_t infer_cblock(struct smq_policy *mq, struct entry *e)  in infer_cblock()  argument
976 	return to_cblock(get_index(&mq->cache_alloc, e));  in infer_cblock()
979 static void requeue(struct smq_policy *mq, struct entry *e)  in requeue()  argument
983 	if (!test_and_set_bit(from_cblock(infer_cblock(mq, e)), mq->cache_hit_bits)) {  in requeue()
984 		if (e->dirty) {  in requeue()
985 			sentinel = writeback_sentinel(mq, e->level);  in requeue()
986 			q_requeue_before(&mq->dirty, sentinel, e, 1u);  in requeue()
988 			sentinel = demote_sentinel(mq, e->level);  in requeue()
989 			q_requeue_before(&mq->clean, sentinel, e, 1u);  in requeue()
1158 	struct entry *e;  in insert_in_cache()  local
1171 	e = alloc_entry(&mq->cache_alloc);  in insert_in_cache()
1172 	BUG_ON(!e);  in insert_in_cache()
1173 	e->oblock = oblock;  in insert_in_cache()
1176 		push(mq, e);  in insert_in_cache()
1178 		push_new(mq, e);  in insert_in_cache()
1180 	result->cblock = infer_cblock(mq, e);  in insert_in_cache()
1194 	struct entry *e = h_lookup(&mq->hotspot_table, hb);  in update_hotspot_queue()  local
1196 	if (e) {  in update_hotspot_queue()
1197 		stats_level_accessed(&mq->hotspot_stats, e->level);  in update_hotspot_queue()
1199 		hi = get_index(&mq->hotspot_alloc, e);  in update_hotspot_queue()
1200 		q_requeue(&mq->hotspot, e,  in update_hotspot_queue()
1207 		e = alloc_entry(&mq->hotspot_alloc);  in update_hotspot_queue()
1208 		if (!e) {  in update_hotspot_queue()
1209 			e = q_pop(&mq->hotspot);  in update_hotspot_queue()
1210 			if (e) {  in update_hotspot_queue()
1211 				h_remove(&mq->hotspot_table, e);  in update_hotspot_queue()
1212 				hi = get_index(&mq->hotspot_alloc, e);  in update_hotspot_queue()
1218 		if (e) {  in update_hotspot_queue()
1219 			e->oblock = hb;  in update_hotspot_queue()
1220 			q_push(&mq->hotspot, e);  in update_hotspot_queue()
1221 			h_insert(&mq->hotspot_table, e);  in update_hotspot_queue()
1225 	return e;  in update_hotspot_queue()
1236 	struct entry *e, *hs_e;  in map()  local
1241 	e = h_lookup(&mq->table, oblock);  in map()
1242 	if (e) {  in map()
1243 		stats_level_accessed(&mq->cache_stats, e->level);  in map()
1245 		requeue(mq, e);  in map()
1247 		result->cblock = infer_cblock(mq, e);  in map()
1316 	struct entry *e;  in smq_lookup()  local
1319 	e = h_lookup(&mq->table, oblock);  in smq_lookup()
1320 	if (e) {  in smq_lookup()
1321 		*cblock = infer_cblock(mq, e);  in smq_lookup()
1332 	struct entry *e;  in __smq_set_clear_dirty()  local
1334 	e = h_lookup(&mq->table, oblock);  in __smq_set_clear_dirty()
1335 	BUG_ON(!e);  in __smq_set_clear_dirty()
1337 	del(mq, e);  in __smq_set_clear_dirty()
1338 	e->dirty = set;  in __smq_set_clear_dirty()
1339 	push(mq, e);  in __smq_set_clear_dirty()
1367 	struct entry *e;  in smq_load_mapping()  local
1369 	e = alloc_particular_entry(&mq->cache_alloc, from_cblock(cblock));  in smq_load_mapping()
1370 	e->oblock = oblock;  in smq_load_mapping()
1371 	e->dirty = false;	/* this gets corrected in a minute */  in smq_load_mapping()
1372 	e->level = hint_valid ? min(hint, NR_CACHE_LEVELS - 1) : 1;  in smq_load_mapping()
1373 	push(mq, e);  in smq_load_mapping()
1383 	struct entry *e;  in smq_save_hints()  local
1386 		for (e = l_head(q->es, q->qs + level); e; e = l_next(q->es, e)) {  in smq_save_hints()
1387 			if (!e->sentinel) {  in smq_save_hints()
1388 				r = fn(context, infer_cblock(mq, e),  in smq_save_hints()
1389 				       e->oblock, e->level);  in smq_save_hints()
1417 	struct entry *e;  in __remove_mapping()  local
1419 	e = h_lookup(&mq->table, oblock);  in __remove_mapping()
1420 	BUG_ON(!e);  in __remove_mapping()
1422 	del(mq, e);  in __remove_mapping()
1423 	free_entry(&mq->cache_alloc, e);  in __remove_mapping()
1438 	struct entry *e = get_entry(&mq->cache_alloc, from_cblock(cblock));  in __remove_cblock()  local
1440 	if (!e || !e->allocated)  in __remove_cblock()
1443 	del(mq, e);  in __remove_cblock()
1444 	free_entry(&mq->cache_alloc, e);  in __remove_cblock()
1483 	struct entry *e = NULL;  in __smq_writeback_work()  local
1490 		e = pop_old(mq, &mq->dirty, target_met ? 1u : mq->dirty.nr_levels);  in __smq_writeback_work()
1493 		e = pop_old(mq, &mq->dirty, mq->dirty.nr_levels);  in __smq_writeback_work()
1495 	if (!e)  in __smq_writeback_work()
1498 	*oblock = e->oblock;  in __smq_writeback_work()
1499 	*cblock = infer_cblock(mq, e);  in __smq_writeback_work()
1500 	e->dirty = false;  in __smq_writeback_work()
1501 	push_new(mq, e);  in __smq_writeback_work()
1523 	struct entry *e = h_lookup(&mq->table, current_oblock);  in __force_mapping()  local
1525 	if (e) {  in __force_mapping()
1526 		del(mq, e);  in __force_mapping()
1527 		e->oblock = new_oblock;  in __force_mapping()
1528 		e->dirty = true;  in __force_mapping()
1529 		push(mq, e);  in __force_mapping()