356 	struct entry *e;  in alloc_entry()  local
361 	e = list_entry(list_pop(&ep->free), struct entry, list);  in alloc_entry()
362 	INIT_LIST_HEAD(&e->list);  in alloc_entry()
363 	INIT_HLIST_NODE(&e->hlist);  in alloc_entry()
366 	return e;  in alloc_entry()
374 	struct entry *e = ep->entries + from_cblock(cblock);  in alloc_particular_entry()  local
376 	list_del_init(&e->list);  in alloc_particular_entry()
377 	INIT_HLIST_NODE(&e->hlist);  in alloc_particular_entry()
380 	return e;  in alloc_particular_entry()
383 static void free_entry(struct entry_pool *ep, struct entry *e)  in free_entry()  argument
387 	INIT_HLIST_NODE(&e->hlist);  in free_entry()
388 	list_add(&e->list, &ep->free);  in free_entry()
396 	struct entry *e = ep->entries + from_cblock(cblock);  in epool_find()  local
397 	return !hlist_unhashed(&e->hlist) ? e : NULL;  in epool_find()
405 static bool in_pool(struct entry_pool *ep, struct entry *e)  in in_pool()  argument
407 	return e >= ep->entries && e < ep->entries_end;  in in_pool()
410 static dm_cblock_t infer_cblock(struct entry_pool *ep, struct entry *e)  in infer_cblock()  argument
412 	return to_cblock(e - ep->entries);  in infer_cblock()
495 static void hash_insert(struct mq_policy *mq, struct entry *e)  in hash_insert()  argument
497 	unsigned h = hash_64(from_oblock(e->oblock), mq->hash_bits);  in hash_insert()
499 	hlist_add_head(&e->hlist, mq->table + h);  in hash_insert()
506 	struct entry *e;  in hash_lookup()  local
508 	hlist_for_each_entry(e, bucket, hlist)  in hash_lookup()
509 		if (e->oblock == oblock) {  in hash_lookup()
510 			hlist_del(&e->hlist);  in hash_lookup()
511 			hlist_add_head(&e->hlist, bucket);  in hash_lookup()
512 			return e;  in hash_lookup()
518 static void hash_remove(struct entry *e)  in hash_remove()  argument
520 	hlist_del(&e->hlist);  in hash_remove()
546 static unsigned queue_level(struct entry *e)  in queue_level()  argument
548 	return min((unsigned) ilog2(e->hit_count), NR_QUEUE_LEVELS - 1u);  in queue_level()
551 static bool in_cache(struct mq_policy *mq, struct entry *e)  in in_cache()  argument
553 	return in_pool(&mq->cache_pool, e);  in in_cache()
561 static void push(struct mq_policy *mq, struct entry *e)  in push()  argument
563 	hash_insert(mq, e);  in push()
565 	if (in_cache(mq, e))  in push()
566 		queue_push(e->dirty ? &mq->cache_dirty : &mq->cache_clean,  in push()
567 			   queue_level(e), &e->list);  in push()
569 		queue_push(&mq->pre_cache, queue_level(e), &e->list);  in push()
575 static void del(struct mq_policy *mq, struct entry *e)  in del()  argument
577 	if (in_cache(mq, e))  in del()
578 		queue_remove(e->dirty ? &mq->cache_dirty : &mq->cache_clean, &e->list);  in del()
580 		queue_remove(&mq->pre_cache, &e->list);  in del()
582 	hash_remove(e);  in del()
591 	struct entry *e;  in pop()  local
597 	e = container_of(h, struct entry, list);  in pop()
598 	hash_remove(e);  in pop()
600 	return e;  in pop()
605 	struct entry *e;  in pop_old()  local
611 	e = container_of(h, struct entry, list);  in pop_old()
612 	hash_remove(e);  in pop_old()
614 	return e;  in pop_old()
642 	struct entry *e;  in check_generation()  local
650 			list_for_each_entry(e, head, list) {  in check_generation()
652 				total += e->hit_count;  in check_generation()
659 			list_for_each_entry(e, head, list) {  in check_generation()
661 				total += e->hit_count;  in check_generation()
674 static void requeue(struct mq_policy *mq, struct entry *e)  in requeue()  argument
677 	del(mq, e);  in requeue()
678 	push(mq, e);  in requeue()
737 	struct entry *e;  in promote_threshold()  local
742 	e = peek(&mq->cache_clean);  in promote_threshold()
743 	if (e)  in promote_threshold()
744 		return e->hit_count;  in promote_threshold()
746 	e = peek(&mq->cache_dirty);  in promote_threshold()
747 	if (e)  in promote_threshold()
748 		return e->hit_count + DISCOURAGE_DEMOTING_DIRTY_THRESHOLD;  in promote_threshold()
780 static bool should_promote(struct mq_policy *mq, struct entry *e,  in should_promote()  argument
783 	return e->hit_count >=  in should_promote()
788 			     struct entry *e,  in cache_entry_found()  argument
791 	requeue(mq, e);  in cache_entry_found()
793 	if (in_cache(mq, e)) {  in cache_entry_found()
795 		result->cblock = infer_cblock(&mq->cache_pool, e);  in cache_entry_found()
805 static int pre_cache_to_cache(struct mq_policy *mq, struct entry *e,  in pre_cache_to_cache()  argument
827 	new_e->oblock = e->oblock;  in pre_cache_to_cache()
829 	new_e->hit_count = e->hit_count;  in pre_cache_to_cache()
831 	del(mq, e);  in pre_cache_to_cache()
832 	free_entry(&mq->pre_cache_pool, e);  in pre_cache_to_cache()
840 static int pre_cache_entry_found(struct mq_policy *mq, struct entry *e,  in pre_cache_entry_found()  argument
847 	if (!should_promote(mq, e, discarded_oblock, data_dir)) {  in pre_cache_entry_found()
848 		requeue(mq, e);  in pre_cache_entry_found()
855 		requeue(mq, e);  in pre_cache_entry_found()
856 		r = pre_cache_to_cache(mq, e, locker, result);  in pre_cache_entry_found()
865 	struct entry *e = alloc_entry(&mq->pre_cache_pool);  in insert_in_pre_cache()  local
867 	if (!e)  in insert_in_pre_cache()
872 		e = pop(mq, &mq->pre_cache);  in insert_in_pre_cache()
874 	if (unlikely(!e)) {  in insert_in_pre_cache()
879 	e->dirty = false;  in insert_in_pre_cache()
880 	e->oblock = oblock;  in insert_in_pre_cache()
881 	e->hit_count = 1;  in insert_in_pre_cache()
882 	push(mq, e);  in insert_in_pre_cache()
890 	struct entry *e;  in insert_in_cache()  local
904 		e = alloc_entry(&mq->cache_pool);  in insert_in_cache()
905 		BUG_ON(!e);  in insert_in_cache()
908 		e = alloc_entry(&mq->cache_pool);  in insert_in_cache()
912 	e->oblock = oblock;  in insert_in_cache()
913 	e->dirty = false;  in insert_in_cache()
914 	e->hit_count = 1;  in insert_in_cache()
915 	push(mq, e);  in insert_in_cache()
917 	result->cblock = infer_cblock(&mq->cache_pool, e);  in insert_in_cache()
948 	struct entry *e = hash_lookup(mq, oblock);  in map()  local
950 	if (e && in_cache(mq, e))  in map()
951 		r = cache_entry_found(mq, e, result);  in map()
957 	else if (e)  in map()
958 		r = pre_cache_entry_found(mq, e, can_migrate, discarded_oblock,  in map()
995 	struct entry *e = container_of(h, struct entry, list);  in update_pre_cache_hits()  local
996 	e->hit_count++;  in update_pre_cache_hits()
1002 	struct entry *e = container_of(h, struct entry, list);  in update_cache_hits()  local
1003 	e->hit_count++;  in update_cache_hits()
1057 	struct entry *e;  in mq_lookup()  local
1062 	e = hash_lookup(mq, oblock);  in mq_lookup()
1063 	if (e && in_cache(mq, e)) {  in mq_lookup()
1064 		*cblock = infer_cblock(&mq->cache_pool, e);  in mq_lookup()
1076 	struct entry *e;  in __mq_set_clear_dirty()  local
1078 	e = hash_lookup(mq, oblock);  in __mq_set_clear_dirty()
1079 	BUG_ON(!e || !in_cache(mq, e));  in __mq_set_clear_dirty()
1081 	del(mq, e);  in __mq_set_clear_dirty()
1082 	e->dirty = set;  in __mq_set_clear_dirty()
1083 	push(mq, e);  in __mq_set_clear_dirty()
1109 	struct entry *e;  in mq_load_mapping()  local
1111 	e = alloc_particular_entry(&mq->cache_pool, cblock);  in mq_load_mapping()
1112 	e->oblock = oblock;  in mq_load_mapping()
1113 	e->dirty = false;	/* this gets corrected in a minute */  in mq_load_mapping()
1114 	e->hit_count = hint_valid ? hint : 1;  in mq_load_mapping()
1115 	push(mq, e);  in mq_load_mapping()
1126 	struct entry *e;  in mq_save_hints()  local
1133 			e = container_of(h, struct entry, list);  in mq_save_hints()
1134 			r = fn(context, infer_cblock(&mq->cache_pool, e),  in mq_save_hints()
1135 			       e->oblock, e->hit_count);  in mq_save_hints()
1162 	struct entry *e;  in __remove_mapping()  local
1164 	e = hash_lookup(mq, oblock);  in __remove_mapping()
1165 	BUG_ON(!e || !in_cache(mq, e));  in __remove_mapping()
1167 	del(mq, e);  in __remove_mapping()
1168 	free_entry(&mq->cache_pool, e);  in __remove_mapping()
1182 	struct entry *e = epool_find(&mq->cache_pool, cblock);  in __remove_cblock()  local
1184 	if (!e)  in __remove_cblock()
1187 	del(mq, e);  in __remove_cblock()
1188 	free_entry(&mq->cache_pool, e);  in __remove_cblock()
1222 	struct entry *e = pop_old(mq, &mq->cache_dirty);  in __mq_writeback_work()  local
1224 	if (!e && !clean_target_met(mq))  in __mq_writeback_work()
1225 		e = pop(mq, &mq->cache_dirty);  in __mq_writeback_work()
1227 	if (!e)  in __mq_writeback_work()
1230 	*oblock = e->oblock;  in __mq_writeback_work()
1231 	*cblock = infer_cblock(&mq->cache_pool, e);  in __mq_writeback_work()
1232 	e->dirty = false;  in __mq_writeback_work()
1233 	push(mq, e);  in __mq_writeback_work()
1254 	struct entry *e = hash_lookup(mq, current_oblock);  in __force_mapping()  local
1256 	if (e && in_cache(mq, e)) {  in __force_mapping()
1257 		del(mq, e);  in __force_mapping()
1258 		e->oblock = new_oblock;  in __force_mapping()
1259 		e->dirty = true;  in __force_mapping()
1260 		push(mq, e);  in __force_mapping()