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@linux.dev>
---
arch/arm64/kvm/vgic/vgic-its.c | 46 ++++++++++++++++++++++++++--------
1 file changed, 36 insertions(+), 10 deletions(-)
@@ -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;