[PATCH v2 13/23] KVM: arm64: vgic-its: Pick cache victim based on usage count

[Oliver Upton]

To date the translation cache LRU policy relies on the ordering of the
linked-list to pick the victim, as entries are moved to the head of the
list on every cache hit. These sort of transformations are incompatible
with an rculist, necessitating a different strategy for recording usage
in-place.

Count the number of cache hits since the last translation cache miss for
every entry. The preferences for selecting a victim are as follows:

 - Invalid entries over valid entries

 - Valid entry with the lowest usage count

 - In the case of a tie, pick the entry closest to the tail (oldest)

Signed-off-by: Oliver Upton <oliver.upton@xxxxxxxxx>
---
 arch/arm64/kvm/vgic/vgic-its.c | 46 ++++++++++++++++++++++++++--------
 1 file changed, 36 insertions(+), 10 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index a7ba20b57264..35926d5ae561 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -157,6 +157,7 @@ struct vgic_translation_cache_entry {
 	u32			devid;
 	u32			eventid;
 	struct vgic_irq		*irq;
+	atomic64_t		usage_count;
 };
 
 /**
@@ -580,13 +581,7 @@ static struct vgic_irq *__vgic_its_check_cache(struct vgic_dist *dist,
 		    cte->eventid != eventid)
 			continue;
 
-		/*
-		 * Move this entry to the head, as it is the most
-		 * recently used.
-		 */
-		if (!list_is_first(&cte->entry, &dist->lpi_translation_cache))
-			list_move(&cte->entry, &dist->lpi_translation_cache);
-
+		atomic64_inc(&cte->usage_count);
 		return cte->irq;
 	}
 
@@ -619,6 +614,36 @@ static unsigned int vgic_its_max_cache_size(struct kvm *kvm)
 	return atomic_read(&kvm->online_vcpus) * LPI_DEFAULT_PCPU_CACHE_SIZE;
 }
 
+static struct vgic_translation_cache_entry *vgic_its_cache_victim(struct vgic_dist *dist,
+								  s64 *max_usage)
+{
+	struct vgic_translation_cache_entry *cte, *victim = NULL;
+	s64 min, tmp, max = S64_MIN;
+
+	/*
+	 * Find the least used cache entry since the last cache miss, preferring
+	 * older entries in the case of a tie. Return the max usage count seen
+	 * during the scan to initialize the new cache entry.
+	 */
+	list_for_each_entry(cte, &dist->lpi_translation_cache, entry) {
+		tmp = atomic64_read(&cte->usage_count);
+		max = max(max, tmp);
+
+		if (!cte->irq) {
+			victim = cte;
+			break;
+		}
+
+		if (!victim || tmp <= min) {
+			victim = cte;
+			min = tmp;
+		}
+	}
+
+	*max_usage = max;
+	return victim;
+}
+
 static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 				       u32 devid, u32 eventid,
 				       struct vgic_irq *irq)
@@ -627,6 +652,7 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 	struct vgic_dist *dist = &kvm->arch.vgic;
 	unsigned long flags;
 	phys_addr_t db;
+	s64 usage = 0;
 
 	/* Do not cache a directly injected interrupt */
 	if (irq->hw)
@@ -650,9 +676,8 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 	}
 
 	if (dist->lpi_cache_count >= vgic_its_max_cache_size(kvm)) {
-		/* Always reuse the last entry (LRU policy) */
-		victim = list_last_entry(&dist->lpi_translation_cache,
-				      typeof(*cte), entry);
+		victim = vgic_its_cache_victim(dist, &usage);
+
 		list_del(&victim->entry);
 		dist->lpi_cache_count--;
 	}
@@ -664,6 +689,7 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 	lockdep_assert_held(&its->its_lock);
 	vgic_get_irq_kref(irq);
 
+	atomic64_set(&new->usage_count, usage);
 	new->db		= db;
 	new->devid	= devid;
 	new->eventid	= eventid;
-- 
2.43.0.687.g38aa6559b0-goog