[PATCH 00/15] KVM: arm64: Improvements to GICv3 LPI injection

[PATCH 00/15] KVM: arm64: Improvements to GICv3 LPI injection

[Oliver Upton]

The unfortunate reality is there are increasingly large systems that are
shipping today without support for GICv4 vLPI injection. Serialization
in KVM's LPI routing/injection code has been a significant bottleneck
for VMs on these machines when under a high load of LPIs (e.g. a
multi-queue NIC).

Even though the long-term solution is quite clearly **direct
injection**, we really ought to do something about the LPI scaling
issues within KVM.

This series aims to improve the performance of LPI routing/injection in
KVM by moving readers of LPI configuration data away from the
lpi_list_lock in favor or using RCU.

Patches 1-5 change out the representation of LPIs in KVM from a
linked-list to an xarray. While not strictly necessary for making the
locking improvements, this seems to be an opportune time to switch to a
data structure that can actually be indexed.

Patches 6-10 transition vgic_get_lpi() and vgic_put_lpi() away from
taking the lpi_list_lock in favor of using RCU for protection. Note that
this requires some rework to the way references are taken on LPIs and
how reclaim works to be RCU safe.

Lastly, patches 11-15 rework the LRU policy on the LPI translation cache
to not require moving elements in the linked-list and take advantage of
this to make it an rculist readable outside of the lpi_list_lock.

All of this was tested on top of v6.8-rc1. Apologies if any of the
changelogs are a bit too light, I'm happy to rework those further in
subsequent revisions.

I would've liked to have benchmark data showing the improvement on top
of upstream with this series, but I'm currently having issues with our
internal infrastructure and upstream kernels. However, this series has
been found to have a near 2x performance improvement to redis-memtier [*]
benchmarks on our kernel tree.

[*] https://github.com/RedisLabs/memtier_benchmark

Oliver Upton (15):
  KVM: arm64: vgic: Store LPIs in an xarray
  KVM: arm64: vgic: Use xarray to find LPI in vgic_get_lpi()
  KVM: arm64: vgic-v3: Iterate the xarray to find pending LPIs
  KVM: arm64: vgic-its: Walk the LPI xarray in vgic_copy_lpi_list()
  KVM: arm64: vgic: Get rid of the LPI linked-list
  KVM: arm64: vgic: Use atomics to count LPIs
  KVM: arm64: vgic: Free LPI vgic_irq structs in an RCU-safe manner
  KVM: arm64: vgic: Rely on RCU protection in vgic_get_lpi()
  KVM: arm64: vgic: Ensure the irq refcount is nonzero when taking a ref
  KVM: arm64: vgic: Don't acquire the lpi_list_lock in vgic_put_irq()
  KVM: arm64: vgic-its: Lazily allocate LPI translation cache
  KVM: arm64: vgic-its: Pick cache victim based on usage count
  KVM: arm64: vgic-its: Protect cached vgic_irq pointers with RCU
  KVM: arm64: vgic-its: Treat the LPI translation cache as an rculist
  KVM: arm64: vgic-its: Rely on RCU to protect translation cache reads

 arch/arm64/kvm/vgic/vgic-debug.c |   2 +-
 arch/arm64/kvm/vgic/vgic-init.c  |   7 +-
 arch/arm64/kvm/vgic/vgic-its.c   | 190 ++++++++++++++++++-------------
 arch/arm64/kvm/vgic/vgic-v3.c    |   3 +-
 arch/arm64/kvm/vgic/vgic.c       |  56 +++------
 arch/arm64/kvm/vgic/vgic.h       |  12 +-
 include/kvm/arm_vgic.h           |   9 +-
 7 files changed, 146 insertions(+), 133 deletions(-)


base-commit: 6613476e225e090cc9aad49be7fa504e290dd33d
-- 
2.43.0.429.g432eaa2c6b-goog

[PATCH 01/15] KVM: arm64: vgic: Store LPIs in an xarray

[Oliver Upton]

Using a linked-list for LPIs is less than ideal as it of course requires
iterative searches to find a particular entry. An xarray is a better
data structure for this use case, as it provides faster searches and can
still handle a potentially sparse range of INTID allocations.

Start by storing LPIs in an xarray, punting usage of the xarray to a
subsequent change.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-init.c |  3 +++
 arch/arm64/kvm/vgic/vgic-its.c  | 13 +++++++++++++
 arch/arm64/kvm/vgic/vgic.c      |  1 +
 include/kvm/arm_vgic.h          |  2 ++
 4 files changed, 19 insertions(+)

diff --git a/arch/arm64/kvm/vgic/vgic-init.c b/arch/arm64/kvm/vgic/vgic-init.c
index e949e1d0fd9f..411719053107 100644
--- a/arch/arm64/kvm/vgic/vgic-init.c
+++ b/arch/arm64/kvm/vgic/vgic-init.c
@@ -56,6 +56,7 @@ void kvm_vgic_early_init(struct kvm *kvm)
 	INIT_LIST_HEAD(&dist->lpi_list_head);
 	INIT_LIST_HEAD(&dist->lpi_translation_cache);
 	raw_spin_lock_init(&dist->lpi_list_lock);
+	xa_init_flags(&dist->lpi_xa, XA_FLAGS_LOCK_IRQ);
 }
 
 /* CREATION */
@@ -366,6 +367,8 @@ static void kvm_vgic_dist_destroy(struct kvm *kvm)
 
 	if (vgic_supports_direct_msis(kvm))
 		vgic_v4_teardown(kvm);
+
+	xa_destroy(&dist->lpi_xa);
 }
 
 static void __kvm_vgic_vcpu_destroy(struct kvm_vcpu *vcpu)
diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index e2764d0ffa9f..f152d670113f 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -52,6 +52,12 @@ static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid,
 	if (!irq)
 		return ERR_PTR(-ENOMEM);
 
+	ret = xa_reserve_irq(&dist->lpi_xa, intid, GFP_KERNEL_ACCOUNT);
+	if (ret) {
+		kfree(irq);
+		return ERR_PTR(ret);
+	}
+
 	INIT_LIST_HEAD(&irq->lpi_list);
 	INIT_LIST_HEAD(&irq->ap_list);
 	raw_spin_lock_init(&irq->irq_lock);
@@ -86,6 +92,13 @@ static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid,
 		goto out_unlock;
 	}
 
+	ret = xa_err(xa_store(&dist->lpi_xa, intid, irq, 0));
+	if (ret) {
+		xa_release(&dist->lpi_xa, intid);
+		kfree(irq);
+		return ERR_PTR(ret);
+	}
+
 	list_add_tail(&irq->lpi_list, &dist->lpi_list_head);
 	dist->lpi_list_count++;
 
diff --git a/arch/arm64/kvm/vgic/vgic.c b/arch/arm64/kvm/vgic/vgic.c
index db2a95762b1b..c126014f8395 100644
--- a/arch/arm64/kvm/vgic/vgic.c
+++ b/arch/arm64/kvm/vgic/vgic.c
@@ -131,6 +131,7 @@ void __vgic_put_lpi_locked(struct kvm *kvm, struct vgic_irq *irq)
 		return;
 
 	list_del(&irq->lpi_list);
+	xa_erase(&dist->lpi_xa, irq->intid);
 	dist->lpi_list_count--;
 
 	kfree(irq);
diff --git a/include/kvm/arm_vgic.h b/include/kvm/arm_vgic.h
index 8cc38e836f54..795b35656b54 100644
--- a/include/kvm/arm_vgic.h
+++ b/include/kvm/arm_vgic.h
@@ -13,6 +13,7 @@
 #include <linux/spinlock.h>
 #include <linux/static_key.h>
 #include <linux/types.h>
+#include <linux/xarray.h>
 #include <kvm/iodev.h>
 #include <linux/list.h>
 #include <linux/jump_label.h>
@@ -275,6 +276,7 @@ struct vgic_dist {
 
 	/* Protects the lpi_list and the count value below. */
 	raw_spinlock_t		lpi_list_lock;
+	struct xarray		lpi_xa;
 	struct list_head	lpi_list_head;
 	int			lpi_list_count;
 
-- 
2.43.0.429.g432eaa2c6b-goog

Re: [PATCH 01/15] KVM: arm64: vgic: Store LPIs in an xarray

[Dan Carpenter]

Hi Oliver,

kernel test robot noticed the following build warnings:

url:    https://github.com/intel-lab-lkp/linux/commits/Oliver-Upton/KVM-arm64-vgic-Store-LPIs-in-an-xarray/20240125-045255
base:   6613476e225e090cc9aad49be7fa504e290dd33d
patch link:    https://lore.kernel.org/r/20240124204909.105952-2-oliver.upton%40linux.dev
patch subject: [PATCH 01/15] KVM: arm64: vgic: Store LPIs in an xarray
config: arm64-randconfig-r081-20240129 (https://download.01.org/0day-ci/archive/20240204/202402041412.mZlOxFFw-lkp@intel.com/config)
compiler: clang version 19.0.0git (https://github.com/llvm/llvm-project 4a39d08908942b2d415db405844cbe4af73e75d4)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Reported-by: Dan Carpenter <dan.carpenter@linaro.org>
| Closes: https://lore.kernel.org/r/202402041412.mZlOxFFw-lkp@intel.com/

New smatch warnings:
arch/arm64/kvm/vgic/vgic-its.c:128 vgic_add_lpi() warn: inconsistent returns '&dist->lpi_list_lock'.
arch/arm64/kvm/vgic/vgic-its.c:128 vgic_add_lpi() warn: inconsistent returns 'flags'.

Old smatch warnings:
arch/arm64/kvm/vgic/vgic-its.c:324 update_lpi_config() warn: inconsistent returns '&irq->irq_lock'.
arch/arm64/kvm/vgic/vgic-its.c:324 update_lpi_config() warn: inconsistent returns 'flags'.

vim +128 arch/arm64/kvm/vgic/vgic-its.c

06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04   39  static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid,
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04   40  				     struct kvm_vcpu *vcpu)
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   41  {
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   42  	struct vgic_dist *dist = &kvm->arch.vgic;
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   43  	struct vgic_irq *irq = vgic_get_irq(kvm, NULL, intid), *oldirq;
388d4359680b56 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2018-05-11   44  	unsigned long flags;
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04   45  	int ret;
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   46  
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   47  	/* In this case there is no put, since we keep the reference. */
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   48  	if (irq)
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   49  		return irq;
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   50  
3ef231670b9e90 arch/arm64/kvm/vgic/vgic-its.c Jia He           2021-09-07   51  	irq = kzalloc(sizeof(struct vgic_irq), GFP_KERNEL_ACCOUNT);
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   52  	if (!irq)
99e5e886a0a59d virt/kvm/arm/vgic/vgic-its.c   Christoffer Dall 2016-08-01   53  		return ERR_PTR(-ENOMEM);
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   54  
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24   55  	ret = xa_reserve_irq(&dist->lpi_xa, intid, GFP_KERNEL_ACCOUNT);
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24   56  	if (ret) {
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24   57  		kfree(irq);
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24   58  		return ERR_PTR(ret);
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24   59  	}
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24   60  
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   61  	INIT_LIST_HEAD(&irq->lpi_list);
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   62  	INIT_LIST_HEAD(&irq->ap_list);
8fa3adb8c6beee virt/kvm/arm/vgic/vgic-its.c   Julien Thierry   2019-01-07   63  	raw_spin_lock_init(&irq->irq_lock);
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   64  
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   65  	irq->config = VGIC_CONFIG_EDGE;
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   66  	kref_init(&irq->refcount);
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   67  	irq->intid = intid;
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04   68  	irq->target_vcpu = vcpu;
8df3c8f33f46ad virt/kvm/arm/vgic/vgic-its.c   Christoffer Dall 2018-07-16   69  	irq->group = 1;
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   70  
fc3bc475231e12 virt/kvm/arm/vgic/vgic-its.c   Julien Thierry   2019-01-07   71  	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   72  
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   73  	/*
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   74  	 * There could be a race with another vgic_add_lpi(), so we need to
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   75  	 * check that we don't add a second list entry with the same LPI.
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   76  	 */
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   77  	list_for_each_entry(oldirq, &dist->lpi_list_head, lpi_list) {
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   78  		if (oldirq->intid != intid)
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   79  			continue;
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   80  
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   81  		/* Someone was faster with adding this LPI, lets use that. */
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   82  		kfree(irq);
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   83  		irq = oldirq;
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   84  
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   85  		/*
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   86  		 * This increases the refcount, the caller is expected to
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   87  		 * call vgic_put_irq() on the returned pointer once it's
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   88  		 * finished with the IRQ.
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   89  		 */
d97594e6bc1b4a virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier     2016-07-17   90  		vgic_get_irq_kref(irq);
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   91  
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   92  		goto out_unlock;
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   93  	}
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15   94  
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24   95  	ret = xa_err(xa_store(&dist->lpi_xa, intid, irq, 0));
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24   96  	if (ret) {
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24   97  		xa_release(&dist->lpi_xa, intid);
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24   98  		kfree(irq);
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24   99  		return ERR_PTR(ret);

should be goto out_unlock or something

3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24  100  	}
3e55a25b7db23f arch/arm64/kvm/vgic/vgic-its.c Oliver Upton     2024-01-24  101  
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15  102  	list_add_tail(&irq->lpi_list, &dist->lpi_list_head);
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15  103  	dist->lpi_list_count++;
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15  104  
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15  105  out_unlock:
fc3bc475231e12 virt/kvm/arm/vgic/vgic-its.c   Julien Thierry   2019-01-07  106  	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15  107  
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04  108  	/*
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04  109  	 * We "cache" the configuration table entries in our struct vgic_irq's.
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04  110  	 * However we only have those structs for mapped IRQs, so we read in
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04  111  	 * the respective config data from memory here upon mapping the LPI.
57bdb436ce869a virt/kvm/arm/vgic/vgic-its.c   Zenghui Yu       2020-04-14  112  	 *
57bdb436ce869a virt/kvm/arm/vgic/vgic-its.c   Zenghui Yu       2020-04-14  113  	 * Should any of these fail, behave as if we couldn't create the LPI
57bdb436ce869a virt/kvm/arm/vgic/vgic-its.c   Zenghui Yu       2020-04-14  114  	 * by dropping the refcount and returning the error.
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04  115  	 */
6ce18e3a5f3308 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier     2017-10-27  116  	ret = update_lpi_config(kvm, irq, NULL, false);
57bdb436ce869a virt/kvm/arm/vgic/vgic-its.c   Zenghui Yu       2020-04-14  117  	if (ret) {
57bdb436ce869a virt/kvm/arm/vgic/vgic-its.c   Zenghui Yu       2020-04-14  118  		vgic_put_irq(kvm, irq);
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04  119  		return ERR_PTR(ret);
57bdb436ce869a virt/kvm/arm/vgic/vgic-its.c   Zenghui Yu       2020-04-14  120  	}
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04  121  
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04  122  	ret = vgic_v3_lpi_sync_pending_status(kvm, irq);
57bdb436ce869a virt/kvm/arm/vgic/vgic-its.c   Zenghui Yu       2020-04-14  123  	if (ret) {
57bdb436ce869a virt/kvm/arm/vgic/vgic-its.c   Zenghui Yu       2020-04-14  124  		vgic_put_irq(kvm, irq);
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04  125  		return ERR_PTR(ret);
57bdb436ce869a virt/kvm/arm/vgic/vgic-its.c   Zenghui Yu       2020-04-14  126  	}
06bd5359549d7a virt/kvm/arm/vgic/vgic-its.c   Eric Auger       2017-05-04  127  
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15 @128  	return irq;
df9f58fbea9bc6 virt/kvm/arm/vgic/vgic-its.c   Andre Przywara   2016-07-15  129  }

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

[PATCH 02/15] KVM: arm64: vgic: Use xarray to find LPI in vgic_get_lpi()

[Oliver Upton]

Iterating over the LPI linked-list is less than ideal when the desired
index is already known. Use the INTID to index the LPI xarray instead.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic.c | 19 +++++--------------
 1 file changed, 5 insertions(+), 14 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic.c b/arch/arm64/kvm/vgic/vgic.c
index c126014f8395..d90c42ff051d 100644
--- a/arch/arm64/kvm/vgic/vgic.c
+++ b/arch/arm64/kvm/vgic/vgic.c
@@ -54,8 +54,9 @@ struct vgic_global kvm_vgic_global_state __ro_after_init = {
  */
 
 /*
- * Iterate over the VM's list of mapped LPIs to find the one with a
- * matching interrupt ID and return a reference to the IRQ structure.
+ * Index the VM's xarray of mapped LPIs and return a reference to the IRQ
+ * structure. The caller is expected to call vgic_put_irq() later once it's
+ * finished with the IRQ.
  */
 static struct vgic_irq *vgic_get_lpi(struct kvm *kvm, u32 intid)
 {
@@ -65,20 +66,10 @@ static struct vgic_irq *vgic_get_lpi(struct kvm *kvm, u32 intid)
 
 	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
 
-	list_for_each_entry(irq, &dist->lpi_list_head, lpi_list) {
-		if (irq->intid != intid)
-			continue;
-
-		/*
-		 * This increases the refcount, the caller is expected to
-		 * call vgic_put_irq() later once it's finished with the IRQ.
-		 */
+	irq = xa_load(&dist->lpi_xa, intid);
+	if (irq)
 		vgic_get_irq_kref(irq);
-		goto out_unlock;
-	}
-	irq = NULL;
 
-out_unlock:
 	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
 
 	return irq;
-- 
2.43.0.429.g432eaa2c6b-goog

[PATCH 03/15] KVM: arm64: vgic-v3: Iterate the xarray to find pending LPIs

[Oliver Upton]

Start walking the LPI xarray to find pending LPIs in preparation for
the removal of the LPI linked-list. Note that the 'basic' iterator
is chosen here as each iteration needs to drop the xarray read lock
(RCU) as reads/writes to guest memory can potentially block.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-v3.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/arch/arm64/kvm/vgic/vgic-v3.c b/arch/arm64/kvm/vgic/vgic-v3.c
index 9465d3706ab9..4ea3340786b9 100644
--- a/arch/arm64/kvm/vgic/vgic-v3.c
+++ b/arch/arm64/kvm/vgic/vgic-v3.c
@@ -380,6 +380,7 @@ int vgic_v3_save_pending_tables(struct kvm *kvm)
 	struct vgic_irq *irq;
 	gpa_t last_ptr = ~(gpa_t)0;
 	bool vlpi_avail = false;
+	unsigned long index;
 	int ret = 0;
 	u8 val;
 
@@ -396,7 +397,7 @@ int vgic_v3_save_pending_tables(struct kvm *kvm)
 		vlpi_avail = true;
 	}
 
-	list_for_each_entry(irq, &dist->lpi_list_head, lpi_list) {
+	xa_for_each(&dist->lpi_xa, index, irq) {
 		int byte_offset, bit_nr;
 		struct kvm_vcpu *vcpu;
 		gpa_t pendbase, ptr;
-- 
2.43.0.429.g432eaa2c6b-goog

[PATCH 04/15] KVM: arm64: vgic-its: Walk the LPI xarray in vgic_copy_lpi_list()

[Oliver Upton]

Start iterating the LPI xarray in anticipation of removing the LPI
linked-list.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-its.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index f152d670113f..a2d95a279798 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -332,6 +332,7 @@ static int update_lpi_config(struct kvm *kvm, struct vgic_irq *irq,
 int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr)
 {
 	struct vgic_dist *dist = &kvm->arch.vgic;
+	XA_STATE(xas, &dist->lpi_xa, 0);
 	struct vgic_irq *irq;
 	unsigned long flags;
 	u32 *intids;
@@ -350,7 +351,9 @@ int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr)
 		return -ENOMEM;
 
 	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
-	list_for_each_entry(irq, &dist->lpi_list_head, lpi_list) {
+	rcu_read_lock();
+
+	xas_for_each(&xas, irq, U32_MAX) {
 		if (i == irq_count)
 			break;
 		/* We don't need to "get" the IRQ, as we hold the list lock. */
@@ -358,6 +361,8 @@ int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr)
 			continue;
 		intids[i++] = irq->intid;
 	}
+
+	rcu_read_unlock();
 	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
 
 	*intid_ptr = intids;
-- 
2.43.0.429.g432eaa2c6b-goog

Re: [PATCH 04/15] KVM: arm64: vgic-its: Walk the LPI xarray in vgic_copy_lpi_list()

[Marc Zyngier]

On Wed, 24 Jan 2024 20:48:58 +0000,
Oliver Upton <oliver.upton@linux.dev> wrote:
> 
> Start iterating the LPI xarray in anticipation of removing the LPI
> linked-list.
> 
> Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
> ---
>  arch/arm64/kvm/vgic/vgic-its.c | 7 ++++++-
>  1 file changed, 6 insertions(+), 1 deletion(-)
> 
> diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
> index f152d670113f..a2d95a279798 100644
> --- a/arch/arm64/kvm/vgic/vgic-its.c
> +++ b/arch/arm64/kvm/vgic/vgic-its.c
> @@ -332,6 +332,7 @@ static int update_lpi_config(struct kvm *kvm, struct vgic_irq *irq,
>  int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr)
>  {
>  	struct vgic_dist *dist = &kvm->arch.vgic;
> +	XA_STATE(xas, &dist->lpi_xa, 0);

Why 0? LPIs start at 8192 (aka GIC_LPI_OFFSET), so it'd probably make
sense to use that.

>  	struct vgic_irq *irq;
>  	unsigned long flags;
>  	u32 *intids;
> @@ -350,7 +351,9 @@ int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr)
>  		return -ENOMEM;
>  
>  	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
> -	list_for_each_entry(irq, &dist->lpi_list_head, lpi_list) {
> +	rcu_read_lock();
> +
> +	xas_for_each(&xas, irq, U32_MAX) {

Similar thing: we advertise 16 bits of ID space (described as
INTERRUPT_ID_BITS_ITS), so capping at that level would make it more
understandable.

>  		if (i == irq_count)
>  			break;
>  		/* We don't need to "get" the IRQ, as we hold the list lock. */
> @@ -358,6 +361,8 @@ int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr)
>  			continue;
>  		intids[i++] = irq->intid;
>  	}
> +
> +	rcu_read_unlock();
>  	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
>  
>  	*intid_ptr = intids;

Thanks,

	M.

-- 
Without deviation from the norm, progress is not possible.

Re: [PATCH 04/15] KVM: arm64: vgic-its: Walk the LPI xarray in vgic_copy_lpi_list()

[Oliver Upton]

On Thu, Jan 25, 2024 at 09:15:30AM +0000, Marc Zyngier wrote:
> On Wed, 24 Jan 2024 20:48:58 +0000,
> Oliver Upton <oliver.upton@linux.dev> wrote:
> > 
> > Start iterating the LPI xarray in anticipation of removing the LPI
> > linked-list.
> > 
> > Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
> > ---
> >  arch/arm64/kvm/vgic/vgic-its.c | 7 ++++++-
> >  1 file changed, 6 insertions(+), 1 deletion(-)
> > 
> > diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
> > index f152d670113f..a2d95a279798 100644
> > --- a/arch/arm64/kvm/vgic/vgic-its.c
> > +++ b/arch/arm64/kvm/vgic/vgic-its.c
> > @@ -332,6 +332,7 @@ static int update_lpi_config(struct kvm *kvm, struct vgic_irq *irq,
> >  int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr)
> >  {
> >  	struct vgic_dist *dist = &kvm->arch.vgic;
> > +	XA_STATE(xas, &dist->lpi_xa, 0);
> 
> Why 0? LPIs start at 8192 (aka GIC_LPI_OFFSET), so it'd probably make
> sense to use that.

Just being lazy!

> >  	struct vgic_irq *irq;
> >  	unsigned long flags;
> >  	u32 *intids;
> > @@ -350,7 +351,9 @@ int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr)
> >  		return -ENOMEM;
> >  
> >  	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
> > -	list_for_each_entry(irq, &dist->lpi_list_head, lpi_list) {
> > +	rcu_read_lock();
> > +
> > +	xas_for_each(&xas, irq, U32_MAX) {
> 
> Similar thing: we advertise 16 bits of ID space (described as
> INTERRUPT_ID_BITS_ITS), so capping at that level would make it more
> understandable.

See above. But completely agree, this is much more readable when it
matches the the actual ID space.

-- 
Thanks,
Oliver

[PATCH 05/15] KVM: arm64: vgic: Get rid of the LPI linked-list

[Oliver Upton]

All readers of LPI configuration have been transitioned to use the LPI
xarray. Get rid of the linked-list altogether.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-init.c | 1 -
 arch/arm64/kvm/vgic/vgic-its.c  | 7 ++-----
 arch/arm64/kvm/vgic/vgic.c      | 1 -
 include/kvm/arm_vgic.h          | 1 -
 4 files changed, 2 insertions(+), 8 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-init.c b/arch/arm64/kvm/vgic/vgic-init.c
index 411719053107..e25672d6e846 100644
--- a/arch/arm64/kvm/vgic/vgic-init.c
+++ b/arch/arm64/kvm/vgic/vgic-init.c
@@ -53,7 +53,6 @@ void kvm_vgic_early_init(struct kvm *kvm)
 {
 	struct vgic_dist *dist = &kvm->arch.vgic;
 
-	INIT_LIST_HEAD(&dist->lpi_list_head);
 	INIT_LIST_HEAD(&dist->lpi_translation_cache);
 	raw_spin_lock_init(&dist->lpi_list_lock);
 	xa_init_flags(&dist->lpi_xa, XA_FLAGS_LOCK_IRQ);
diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index a2d95a279798..0486d3779d11 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -74,10 +74,8 @@ static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid,
 	 * There could be a race with another vgic_add_lpi(), so we need to
 	 * check that we don't add a second list entry with the same LPI.
 	 */
-	list_for_each_entry(oldirq, &dist->lpi_list_head, lpi_list) {
-		if (oldirq->intid != intid)
-			continue;
-
+	oldirq = xa_load(&dist->lpi_xa, intid);
+	if (oldirq) {
 		/* Someone was faster with adding this LPI, lets use that. */
 		kfree(irq);
 		irq = oldirq;
@@ -99,7 +97,6 @@ static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid,
 		return ERR_PTR(ret);
 	}
 
-	list_add_tail(&irq->lpi_list, &dist->lpi_list_head);
 	dist->lpi_list_count++;
 
 out_unlock:
diff --git a/arch/arm64/kvm/vgic/vgic.c b/arch/arm64/kvm/vgic/vgic.c
index d90c42ff051d..e58ce68e325c 100644
--- a/arch/arm64/kvm/vgic/vgic.c
+++ b/arch/arm64/kvm/vgic/vgic.c
@@ -121,7 +121,6 @@ void __vgic_put_lpi_locked(struct kvm *kvm, struct vgic_irq *irq)
 	if (!kref_put(&irq->refcount, vgic_irq_release))
 		return;
 
-	list_del(&irq->lpi_list);
 	xa_erase(&dist->lpi_xa, irq->intid);
 	dist->lpi_list_count--;
 
diff --git a/include/kvm/arm_vgic.h b/include/kvm/arm_vgic.h
index 795b35656b54..39037db3fa90 100644
--- a/include/kvm/arm_vgic.h
+++ b/include/kvm/arm_vgic.h
@@ -277,7 +277,6 @@ struct vgic_dist {
 	/* Protects the lpi_list and the count value below. */
 	raw_spinlock_t		lpi_list_lock;
 	struct xarray		lpi_xa;
-	struct list_head	lpi_list_head;
 	int			lpi_list_count;
 
 	/* LPI translation cache */
-- 
2.43.0.429.g432eaa2c6b-goog

Re: [PATCH 05/15] KVM: arm64: vgic: Get rid of the LPI linked-list

[Marc Zyngier]

On Wed, 24 Jan 2024 20:48:59 +0000,
Oliver Upton <oliver.upton@linux.dev> wrote:
> 
> All readers of LPI configuration have been transitioned to use the LPI
> xarray. Get rid of the linked-list altogether.
> 
> Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
> ---
>  arch/arm64/kvm/vgic/vgic-init.c | 1 -
>  arch/arm64/kvm/vgic/vgic-its.c  | 7 ++-----
>  arch/arm64/kvm/vgic/vgic.c      | 1 -
>  include/kvm/arm_vgic.h          | 1 -
>  4 files changed, 2 insertions(+), 8 deletions(-)
> 
> diff --git a/arch/arm64/kvm/vgic/vgic-init.c b/arch/arm64/kvm/vgic/vgic-init.c
> index 411719053107..e25672d6e846 100644
> --- a/arch/arm64/kvm/vgic/vgic-init.c
> +++ b/arch/arm64/kvm/vgic/vgic-init.c
> @@ -53,7 +53,6 @@ void kvm_vgic_early_init(struct kvm *kvm)
>  {
>  	struct vgic_dist *dist = &kvm->arch.vgic;
>  
> -	INIT_LIST_HEAD(&dist->lpi_list_head);
>  	INIT_LIST_HEAD(&dist->lpi_translation_cache);
>  	raw_spin_lock_init(&dist->lpi_list_lock);
>  	xa_init_flags(&dist->lpi_xa, XA_FLAGS_LOCK_IRQ);
> diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
> index a2d95a279798..0486d3779d11 100644
> --- a/arch/arm64/kvm/vgic/vgic-its.c
> +++ b/arch/arm64/kvm/vgic/vgic-its.c
> @@ -74,10 +74,8 @@ static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid,
>  	 * There could be a race with another vgic_add_lpi(), so we need to
>  	 * check that we don't add a second list entry with the same LPI.
>  	 */
> -	list_for_each_entry(oldirq, &dist->lpi_list_head, lpi_list) {
> -		if (oldirq->intid != intid)
> -			continue;
> -
> +	oldirq = xa_load(&dist->lpi_xa, intid);
> +	if (oldirq) {
>  		/* Someone was faster with adding this LPI, lets use that. */
>  		kfree(irq);
>  		irq = oldirq;
> @@ -99,7 +97,6 @@ static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid,
>  		return ERR_PTR(ret);
>  	}
>  
> -	list_add_tail(&irq->lpi_list, &dist->lpi_list_head);
>  	dist->lpi_list_count++;
>  
>  out_unlock:
> diff --git a/arch/arm64/kvm/vgic/vgic.c b/arch/arm64/kvm/vgic/vgic.c
> index d90c42ff051d..e58ce68e325c 100644
> --- a/arch/arm64/kvm/vgic/vgic.c
> +++ b/arch/arm64/kvm/vgic/vgic.c
> @@ -121,7 +121,6 @@ void __vgic_put_lpi_locked(struct kvm *kvm, struct vgic_irq *irq)
>  	if (!kref_put(&irq->refcount, vgic_irq_release))
>  		return;
>  
> -	list_del(&irq->lpi_list);
>  	xa_erase(&dist->lpi_xa, irq->intid);
>  	dist->lpi_list_count--;
>  
> diff --git a/include/kvm/arm_vgic.h b/include/kvm/arm_vgic.h
> index 795b35656b54..39037db3fa90 100644
> --- a/include/kvm/arm_vgic.h
> +++ b/include/kvm/arm_vgic.h
> @@ -277,7 +277,6 @@ struct vgic_dist {
>  	/* Protects the lpi_list and the count value below. */
>  	raw_spinlock_t		lpi_list_lock;
>  	struct xarray		lpi_xa;
> -	struct list_head	lpi_list_head;
>  	int			lpi_list_count;
>  
>  	/* LPI translation cache */

You seem to be missing some of it (patch against the full series, so
context will be wrong):

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index 46ff21fea785..3de41ee5e6ee 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -58,7 +58,6 @@ static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid,
 		return ERR_PTR(ret);
 	}
 
-	INIT_LIST_HEAD(&irq->lpi_list);
 	INIT_LIST_HEAD(&irq->ap_list);
 	raw_spin_lock_init(&irq->irq_lock);
 
diff --git a/include/kvm/arm_vgic.h b/include/kvm/arm_vgic.h
index f3fc2cc922ce..4439039ccd45 100644
--- a/include/kvm/arm_vgic.h
+++ b/include/kvm/arm_vgic.h
@@ -118,7 +118,6 @@ struct irq_ops {
 struct vgic_irq {
 	raw_spinlock_t irq_lock;	/* Protects the content of the struct */
 	struct rcu_head rcu;
-	struct list_head lpi_list;	/* Used to link all LPIs together */
 	struct list_head ap_list;
 
 	struct kvm_vcpu *vcpu;		/* SGIs and PPIs: The VCPU


	M.

-- 
Without deviation from the norm, progress is not possible.

[PATCH 06/15] KVM: arm64: vgic: Use atomics to count LPIs

[Oliver Upton]

Switch to using atomics for LPI accounting, allowing vgic_irq references
to be dropped in parallel.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-debug.c | 2 +-
 arch/arm64/kvm/vgic/vgic-its.c   | 4 ++--
 arch/arm64/kvm/vgic/vgic.c       | 2 +-
 include/kvm/arm_vgic.h           | 4 ++--
 4 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-debug.c b/arch/arm64/kvm/vgic/vgic-debug.c
index 85606a531dc3..389025ce7749 100644
--- a/arch/arm64/kvm/vgic/vgic-debug.c
+++ b/arch/arm64/kvm/vgic/vgic-debug.c
@@ -149,7 +149,7 @@ static void print_dist_state(struct seq_file *s, struct vgic_dist *dist)
 	seq_printf(s, "vgic_model:\t%s\n", v3 ? "GICv3" : "GICv2");
 	seq_printf(s, "nr_spis:\t%d\n", dist->nr_spis);
 	if (v3)
-		seq_printf(s, "nr_lpis:\t%d\n", dist->lpi_list_count);
+		seq_printf(s, "nr_lpis:\t%d\n", atomic_read(&dist->lpi_count));
 	seq_printf(s, "enabled:\t%d\n", dist->enabled);
 	seq_printf(s, "\n");
 
diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index 0486d3779d11..1d912a595b71 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -97,7 +97,7 @@ static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid,
 		return ERR_PTR(ret);
 	}
 
-	dist->lpi_list_count++;
+	atomic_inc(&dist->lpi_count);
 
 out_unlock:
 	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
@@ -342,7 +342,7 @@ int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr)
 	 * command). If coming from another path (such as enabling LPIs),
 	 * we must be careful not to overrun the array.
 	 */
-	irq_count = READ_ONCE(dist->lpi_list_count);
+	irq_count = atomic_read(&dist->lpi_count);
 	intids = kmalloc_array(irq_count, sizeof(intids[0]), GFP_KERNEL_ACCOUNT);
 	if (!intids)
 		return -ENOMEM;
diff --git a/arch/arm64/kvm/vgic/vgic.c b/arch/arm64/kvm/vgic/vgic.c
index e58ce68e325c..5988d162b765 100644
--- a/arch/arm64/kvm/vgic/vgic.c
+++ b/arch/arm64/kvm/vgic/vgic.c
@@ -122,7 +122,7 @@ void __vgic_put_lpi_locked(struct kvm *kvm, struct vgic_irq *irq)
 		return;
 
 	xa_erase(&dist->lpi_xa, irq->intid);
-	dist->lpi_list_count--;
+	atomic_dec(&dist->lpi_count);
 
 	kfree(irq);
 }
diff --git a/include/kvm/arm_vgic.h b/include/kvm/arm_vgic.h
index 39037db3fa90..e944536feee8 100644
--- a/include/kvm/arm_vgic.h
+++ b/include/kvm/arm_vgic.h
@@ -274,10 +274,10 @@ struct vgic_dist {
 	 */
 	u64			propbaser;
 
-	/* Protects the lpi_list and the count value below. */
+	/* Protects the lpi_list. */
 	raw_spinlock_t		lpi_list_lock;
 	struct xarray		lpi_xa;
-	int			lpi_list_count;
+	atomic_t		lpi_count;
 
 	/* LPI translation cache */
 	struct list_head	lpi_translation_cache;
-- 
2.43.0.429.g432eaa2c6b-goog

[PATCH 07/15] KVM: arm64: vgic: Free LPI vgic_irq structs in an RCU-safe manner

[Oliver Upton]

Free the vgic_irq structs in an RCU-safe manner to allow reads of the
LPI configuration data to happen in parallel with the release of LPIs.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic.c | 2 +-
 include/kvm/arm_vgic.h     | 1 +
 2 files changed, 2 insertions(+), 1 deletion(-)

diff --git a/arch/arm64/kvm/vgic/vgic.c b/arch/arm64/kvm/vgic/vgic.c
index 5988d162b765..be3ed4c5e1fa 100644
--- a/arch/arm64/kvm/vgic/vgic.c
+++ b/arch/arm64/kvm/vgic/vgic.c
@@ -124,7 +124,7 @@ void __vgic_put_lpi_locked(struct kvm *kvm, struct vgic_irq *irq)
 	xa_erase(&dist->lpi_xa, irq->intid);
 	atomic_dec(&dist->lpi_count);
 
-	kfree(irq);
+	kfree_rcu(irq, rcu);
 }
 
 void vgic_put_irq(struct kvm *kvm, struct vgic_irq *irq)
diff --git a/include/kvm/arm_vgic.h b/include/kvm/arm_vgic.h
index e944536feee8..a6f6c1583662 100644
--- a/include/kvm/arm_vgic.h
+++ b/include/kvm/arm_vgic.h
@@ -117,6 +117,7 @@ struct irq_ops {
 
 struct vgic_irq {
 	raw_spinlock_t irq_lock;	/* Protects the content of the struct */
+	struct rcu_head rcu;
 	struct list_head lpi_list;	/* Used to link all LPIs together */
 	struct list_head ap_list;
 
-- 
2.43.0.429.g432eaa2c6b-goog

[PATCH 08/15] KVM: arm64: vgic: Rely on RCU protection in vgic_get_lpi()

[Oliver Upton]

Stop acquiring the lpi_list_lock in favor of RCU for protecting
the read-side critical section in vgic_get_lpi(). In order for this to
be safe, we also need to be careful not to take a reference on an irq
with a refcount of 0, as it is about to be freed.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic.c |  9 ++++-----
 arch/arm64/kvm/vgic/vgic.h | 11 ++++++++---
 2 files changed, 12 insertions(+), 8 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic.c b/arch/arm64/kvm/vgic/vgic.c
index be3ed4c5e1fa..949af87bb599 100644
--- a/arch/arm64/kvm/vgic/vgic.c
+++ b/arch/arm64/kvm/vgic/vgic.c
@@ -62,15 +62,14 @@ static struct vgic_irq *vgic_get_lpi(struct kvm *kvm, u32 intid)
 {
 	struct vgic_dist *dist = &kvm->arch.vgic;
 	struct vgic_irq *irq = NULL;
-	unsigned long flags;
 
-	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
+	rcu_read_lock();
 
 	irq = xa_load(&dist->lpi_xa, intid);
-	if (irq)
-		vgic_get_irq_kref(irq);
+	if (irq && !vgic_try_get_irq_kref(irq))
+		irq = NULL;
 
-	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
+	rcu_read_unlock();
 
 	return irq;
 }
diff --git a/arch/arm64/kvm/vgic/vgic.h b/arch/arm64/kvm/vgic/vgic.h
index 8d134569d0a1..20886f57416a 100644
--- a/arch/arm64/kvm/vgic/vgic.h
+++ b/arch/arm64/kvm/vgic/vgic.h
@@ -220,12 +220,17 @@ void vgic_v2_vmcr_sync(struct kvm_vcpu *vcpu);
 void vgic_v2_save_state(struct kvm_vcpu *vcpu);
 void vgic_v2_restore_state(struct kvm_vcpu *vcpu);
 
-static inline void vgic_get_irq_kref(struct vgic_irq *irq)
+static inline bool vgic_try_get_irq_kref(struct vgic_irq *irq)
 {
 	if (irq->intid < VGIC_MIN_LPI)
-		return;
+		return true;
+
+	return kref_get_unless_zero(&irq->refcount);
+}
 
-	kref_get(&irq->refcount);
+static inline void vgic_get_irq_kref(struct vgic_irq *irq)
+{
+	WARN_ON_ONCE(!vgic_try_get_irq_kref(irq));
 }
 
 void vgic_v3_fold_lr_state(struct kvm_vcpu *vcpu);
-- 
2.43.0.429.g432eaa2c6b-goog

[PATCH 09/15] KVM: arm64: vgic: Ensure the irq refcount is nonzero when taking a ref

[Oliver Upton]

It will soon be possible for get() and put() calls to happen in
parallel, which means in most cases we must ensure the refcount is
nonzero when taking a new reference. Switch to using
vgic_try_get_irq_kref() where necessary, and document the few conditions
where an IRQ's refcount is guaranteed to be nonzero.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-its.c | 18 ++++++++----------
 arch/arm64/kvm/vgic/vgic.c     |  3 ++-
 2 files changed, 10 insertions(+), 11 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index 1d912a595b71..7219f4a0a93d 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -75,18 +75,11 @@ static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid,
 	 * check that we don't add a second list entry with the same LPI.
 	 */
 	oldirq = xa_load(&dist->lpi_xa, intid);
-	if (oldirq) {
+	if (oldirq && vgic_try_get_irq_kref(oldirq)) {
 		/* Someone was faster with adding this LPI, lets use that. */
 		kfree(irq);
 		irq = oldirq;
 
-		/*
-		 * This increases the refcount, the caller is expected to
-		 * call vgic_put_irq() on the returned pointer once it's
-		 * finished with the IRQ.
-		 */
-		vgic_get_irq_kref(irq);
-
 		goto out_unlock;
 	}
 
@@ -607,8 +600,8 @@ static struct vgic_irq *vgic_its_check_cache(struct kvm *kvm, phys_addr_t db,
 	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
 
 	irq = __vgic_its_check_cache(dist, db, devid, eventid);
-	if (irq)
-		vgic_get_irq_kref(irq);
+	if (irq && !vgic_try_get_irq_kref(irq))
+		irq = NULL;
 
 	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
 
@@ -654,6 +647,11 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 	if (cte->irq)
 		__vgic_put_lpi_locked(kvm, cte->irq);
 
+	/*
+	 * The irq refcount is guaranteed to be nonzero while holding the
+	 * its_lock, as the ITE (and the reference it holds) cannot be freed.
+	 */
+	lockdep_assert_held(&its->its_lock);
 	vgic_get_irq_kref(irq);
 
 	cte->db		= db;
diff --git a/arch/arm64/kvm/vgic/vgic.c b/arch/arm64/kvm/vgic/vgic.c
index 949af87bb599..7e0d84906a12 100644
--- a/arch/arm64/kvm/vgic/vgic.c
+++ b/arch/arm64/kvm/vgic/vgic.c
@@ -394,7 +394,8 @@ bool vgic_queue_irq_unlock(struct kvm *kvm, struct vgic_irq *irq,
 
 	/*
 	 * Grab a reference to the irq to reflect the fact that it is
-	 * now in the ap_list.
+	 * now in the ap_list. This is safe as the caller must already hold a
+	 * reference on the irq.
 	 */
 	vgic_get_irq_kref(irq);
 	list_add_tail(&irq->ap_list, &vcpu->arch.vgic_cpu.ap_list_head);
-- 
2.43.0.429.g432eaa2c6b-goog

Re: [PATCH 09/15] KVM: arm64: vgic: Ensure the irq refcount is nonzero when taking a ref

[Marc Zyngier]

On Wed, 24 Jan 2024 20:49:03 +0000,
Oliver Upton <oliver.upton@linux.dev> wrote:
> 
> It will soon be possible for get() and put() calls to happen in
> parallel, which means in most cases we must ensure the refcount is
> nonzero when taking a new reference. Switch to using
> vgic_try_get_irq_kref() where necessary, and document the few conditions
> where an IRQ's refcount is guaranteed to be nonzero.
> 
> Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
> ---
>  arch/arm64/kvm/vgic/vgic-its.c | 18 ++++++++----------
>  arch/arm64/kvm/vgic/vgic.c     |  3 ++-
>  2 files changed, 10 insertions(+), 11 deletions(-)
> 
> diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
> index 1d912a595b71..7219f4a0a93d 100644
> --- a/arch/arm64/kvm/vgic/vgic-its.c
> +++ b/arch/arm64/kvm/vgic/vgic-its.c
> @@ -75,18 +75,11 @@ static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid,
>  	 * check that we don't add a second list entry with the same LPI.
>  	 */
>  	oldirq = xa_load(&dist->lpi_xa, intid);
> -	if (oldirq) {
> +	if (oldirq && vgic_try_get_irq_kref(oldirq)) {

nit: move the NULL-check inside the helper, since you always have to
do it.

Thanks,

	M.

-- 
Without deviation from the norm, progress is not possible.

[PATCH 10/15] KVM: arm64: vgic: Don't acquire the lpi_list_lock in vgic_put_irq()

[Oliver Upton]

The LPI xarray's xa_lock is sufficient for synchronizing writers when
freeing a given LPI. Furthermore, readers can only take a new reference
on an IRQ if it was already nonzero.

Stop taking the lpi_list_lock unnecessarily and get rid of
__vgic_put_lpi_locked().

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-its.c |  4 ++--
 arch/arm64/kvm/vgic/vgic.c     | 21 ++++-----------------
 arch/arm64/kvm/vgic/vgic.h     |  1 -
 3 files changed, 6 insertions(+), 20 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index 7219f4a0a93d..8c026a530018 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -645,7 +645,7 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 	 * was in the cache, and increment it on the new interrupt.
 	 */
 	if (cte->irq)
-		__vgic_put_lpi_locked(kvm, cte->irq);
+		vgic_put_irq(kvm, cte->irq);
 
 	/*
 	 * The irq refcount is guaranteed to be nonzero while holding the
@@ -682,7 +682,7 @@ void vgic_its_invalidate_cache(struct kvm *kvm)
 		if (!cte->irq)
 			break;
 
-		__vgic_put_lpi_locked(kvm, cte->irq);
+		vgic_put_irq(kvm, cte->irq);
 		cte->irq = NULL;
 	}
 
diff --git a/arch/arm64/kvm/vgic/vgic.c b/arch/arm64/kvm/vgic/vgic.c
index 7e0d84906a12..6b8f440ca0fd 100644
--- a/arch/arm64/kvm/vgic/vgic.c
+++ b/arch/arm64/kvm/vgic/vgic.c
@@ -110,13 +110,13 @@ static void vgic_irq_release(struct kref *ref)
 {
 }
 
-/*
- * Drop the refcount on the LPI. Must be called with lpi_list_lock held.
- */
-void __vgic_put_lpi_locked(struct kvm *kvm, struct vgic_irq *irq)
+void vgic_put_irq(struct kvm *kvm, struct vgic_irq *irq)
 {
 	struct vgic_dist *dist = &kvm->arch.vgic;
 
+	if (irq->intid < VGIC_MIN_LPI)
+		return;
+
 	if (!kref_put(&irq->refcount, vgic_irq_release))
 		return;
 
@@ -126,19 +126,6 @@ void __vgic_put_lpi_locked(struct kvm *kvm, struct vgic_irq *irq)
 	kfree_rcu(irq, rcu);
 }
 
-void vgic_put_irq(struct kvm *kvm, struct vgic_irq *irq)
-{
-	struct vgic_dist *dist = &kvm->arch.vgic;
-	unsigned long flags;
-
-	if (irq->intid < VGIC_MIN_LPI)
-		return;
-
-	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
-	__vgic_put_lpi_locked(kvm, irq);
-	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
-}
-
 void vgic_flush_pending_lpis(struct kvm_vcpu *vcpu)
 {
 	struct vgic_cpu *vgic_cpu = &vcpu->arch.vgic_cpu;
diff --git a/arch/arm64/kvm/vgic/vgic.h b/arch/arm64/kvm/vgic/vgic.h
index 20886f57416a..b0a2754eae93 100644
--- a/arch/arm64/kvm/vgic/vgic.h
+++ b/arch/arm64/kvm/vgic/vgic.h
@@ -180,7 +180,6 @@ vgic_get_mmio_region(struct kvm_vcpu *vcpu, struct vgic_io_device *iodev,
 		     gpa_t addr, int len);
 struct vgic_irq *vgic_get_irq(struct kvm *kvm, struct kvm_vcpu *vcpu,
 			      u32 intid);
-void __vgic_put_lpi_locked(struct kvm *kvm, struct vgic_irq *irq);
 void vgic_put_irq(struct kvm *kvm, struct vgic_irq *irq);
 bool vgic_get_phys_line_level(struct vgic_irq *irq);
 void vgic_irq_set_phys_pending(struct vgic_irq *irq, bool pending);
-- 
2.43.0.429.g432eaa2c6b-goog

[PATCH 11/15] KVM: arm64: vgic-its: Lazily allocate LPI translation cache

[Oliver Upton]

Reusing translation cache entries within a read-side critical section is
fundamentally incompatible with an rculist. As such, we need to allocate
a new entry to replace an eviction and free the removed entry
afterwards.

Take this as an opportunity to remove the eager allocation of
translation cache entries altogether in favor of a lazy allocation model
on cache miss.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-init.c |  3 --
 arch/arm64/kvm/vgic/vgic-its.c  | 86 ++++++++++++++-------------------
 include/kvm/arm_vgic.h          |  1 +
 3 files changed, 38 insertions(+), 52 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-init.c b/arch/arm64/kvm/vgic/vgic-init.c
index e25672d6e846..660d5ce3b610 100644
--- a/arch/arm64/kvm/vgic/vgic-init.c
+++ b/arch/arm64/kvm/vgic/vgic-init.c
@@ -305,9 +305,6 @@ int vgic_init(struct kvm *kvm)
 		}
 	}
 
-	if (vgic_has_its(kvm))
-		vgic_lpi_translation_cache_init(kvm);
-
 	/*
 	 * If we have GICv4.1 enabled, unconditionnaly request enable the
 	 * v4 support so that we get HW-accelerated vSGIs. Otherwise, only
diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index 8c026a530018..aec82d9a1b3c 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -608,12 +608,20 @@ static struct vgic_irq *vgic_its_check_cache(struct kvm *kvm, phys_addr_t db,
 	return irq;
 }
 
+/* Default is 16 cached LPIs per vcpu */
+#define LPI_DEFAULT_PCPU_CACHE_SIZE	16
+
+static unsigned int vgic_its_max_cache_size(struct kvm *kvm)
+{
+	return atomic_read(&kvm->online_vcpus) * LPI_DEFAULT_PCPU_CACHE_SIZE;
+}
+
 static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 				       u32 devid, u32 eventid,
 				       struct vgic_irq *irq)
 {
+	struct vgic_translation_cache_entry *new, *victim;
 	struct vgic_dist *dist = &kvm->arch.vgic;
-	struct vgic_translation_cache_entry *cte;
 	unsigned long flags;
 	phys_addr_t db;
 
@@ -621,10 +629,11 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 	if (irq->hw)
 		return;
 
-	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
+	new = victim = kzalloc(sizeof(*new), GFP_KERNEL_ACCOUNT);
+	if (!new)
+		return;
 
-	if (unlikely(list_empty(&dist->lpi_translation_cache)))
-		goto out;
+	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
 
 	/*
 	 * We could have raced with another CPU caching the same
@@ -635,17 +644,15 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 	if (__vgic_its_check_cache(dist, db, devid, eventid))
 		goto out;
 
-	/* Always reuse the last entry (LRU policy) */
-	cte = list_last_entry(&dist->lpi_translation_cache,
-			      typeof(*cte), entry);
-
-	/*
-	 * Caching the translation implies having an extra reference
-	 * to the interrupt, so drop the potential reference on what
-	 * was in the cache, and increment it on the new interrupt.
-	 */
-	if (cte->irq)
-		vgic_put_irq(kvm, cte->irq);
+	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);
+		list_del(&victim->entry);
+		dist->lpi_cache_count--;
+	} else {
+		victim = NULL;
+	}
 
 	/*
 	 * The irq refcount is guaranteed to be nonzero while holding the
@@ -654,16 +661,26 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 	lockdep_assert_held(&its->its_lock);
 	vgic_get_irq_kref(irq);
 
-	cte->db		= db;
-	cte->devid	= devid;
-	cte->eventid	= eventid;
-	cte->irq	= irq;
+	new->db		= db;
+	new->devid	= devid;
+	new->eventid	= eventid;
+	new->irq	= irq;
 
 	/* Move the new translation to the head of the list */
-	list_move(&cte->entry, &dist->lpi_translation_cache);
+	list_add(&new->entry, &dist->lpi_translation_cache);
 
 out:
 	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
+
+	/*
+	 * Caching the translation implies having an extra reference
+	 * to the interrupt, so drop the potential reference on what
+	 * was in the cache, and increment it on the new interrupt.
+	 */
+	if (victim && victim->irq)
+		vgic_put_irq(kvm, victim->irq);
+
+	kfree(victim);
 }
 
 void vgic_its_invalidate_cache(struct kvm *kvm)
@@ -1905,33 +1922,6 @@ static int vgic_register_its_iodev(struct kvm *kvm, struct vgic_its *its,
 	return ret;
 }
 
-/* Default is 16 cached LPIs per vcpu */
-#define LPI_DEFAULT_PCPU_CACHE_SIZE	16
-
-void vgic_lpi_translation_cache_init(struct kvm *kvm)
-{
-	struct vgic_dist *dist = &kvm->arch.vgic;
-	unsigned int sz;
-	int i;
-
-	if (!list_empty(&dist->lpi_translation_cache))
-		return;
-
-	sz = atomic_read(&kvm->online_vcpus) * LPI_DEFAULT_PCPU_CACHE_SIZE;
-
-	for (i = 0; i < sz; i++) {
-		struct vgic_translation_cache_entry *cte;
-
-		/* An allocation failure is not fatal */
-		cte = kzalloc(sizeof(*cte), GFP_KERNEL_ACCOUNT);
-		if (WARN_ON(!cte))
-			break;
-
-		INIT_LIST_HEAD(&cte->entry);
-		list_add(&cte->entry, &dist->lpi_translation_cache);
-	}
-}
-
 void vgic_lpi_translation_cache_destroy(struct kvm *kvm)
 {
 	struct vgic_dist *dist = &kvm->arch.vgic;
@@ -1978,8 +1968,6 @@ static int vgic_its_create(struct kvm_device *dev, u32 type)
 			kfree(its);
 			return ret;
 		}
-
-		vgic_lpi_translation_cache_init(dev->kvm);
 	}
 
 	mutex_init(&its->its_lock);
diff --git a/include/kvm/arm_vgic.h b/include/kvm/arm_vgic.h
index a6f6c1583662..70490a2a300d 100644
--- a/include/kvm/arm_vgic.h
+++ b/include/kvm/arm_vgic.h
@@ -282,6 +282,7 @@ struct vgic_dist {
 
 	/* LPI translation cache */
 	struct list_head	lpi_translation_cache;
+	unsigned int		lpi_cache_count;
 
 	/* used by vgic-debug */
 	struct vgic_state_iter *iter;
-- 
2.43.0.429.g432eaa2c6b-goog

Re: [PATCH 11/15] KVM: arm64: vgic-its: Lazily allocate LPI translation cache

[Marc Zyngier]

On Wed, 24 Jan 2024 20:49:05 +0000,
Oliver Upton <oliver.upton@linux.dev> wrote:
> 
> Reusing translation cache entries within a read-side critical section is
> fundamentally incompatible with an rculist. As such, we need to allocate
> a new entry to replace an eviction and free the removed entry
> afterwards.
> 
> Take this as an opportunity to remove the eager allocation of
> translation cache entries altogether in favor of a lazy allocation model
> on cache miss.
> 
> Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
> ---
>  arch/arm64/kvm/vgic/vgic-init.c |  3 --
>  arch/arm64/kvm/vgic/vgic-its.c  | 86 ++++++++++++++-------------------
>  include/kvm/arm_vgic.h          |  1 +
>  3 files changed, 38 insertions(+), 52 deletions(-)
> 
> diff --git a/arch/arm64/kvm/vgic/vgic-init.c b/arch/arm64/kvm/vgic/vgic-init.c
> index e25672d6e846..660d5ce3b610 100644
> --- a/arch/arm64/kvm/vgic/vgic-init.c
> +++ b/arch/arm64/kvm/vgic/vgic-init.c
> @@ -305,9 +305,6 @@ int vgic_init(struct kvm *kvm)
>  		}
>  	}
>  
> -	if (vgic_has_its(kvm))
> -		vgic_lpi_translation_cache_init(kvm);
> -
>  	/*
>  	 * If we have GICv4.1 enabled, unconditionnaly request enable the
>  	 * v4 support so that we get HW-accelerated vSGIs. Otherwise, only
> diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
> index 8c026a530018..aec82d9a1b3c 100644
> --- a/arch/arm64/kvm/vgic/vgic-its.c
> +++ b/arch/arm64/kvm/vgic/vgic-its.c
> @@ -608,12 +608,20 @@ static struct vgic_irq *vgic_its_check_cache(struct kvm *kvm, phys_addr_t db,
>  	return irq;
>  }
>  
> +/* Default is 16 cached LPIs per vcpu */
> +#define LPI_DEFAULT_PCPU_CACHE_SIZE	16
> +
> +static unsigned int vgic_its_max_cache_size(struct kvm *kvm)
> +{
> +	return atomic_read(&kvm->online_vcpus) * LPI_DEFAULT_PCPU_CACHE_SIZE;
> +}
> +
>  static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
>  				       u32 devid, u32 eventid,
>  				       struct vgic_irq *irq)
>  {
> +	struct vgic_translation_cache_entry *new, *victim;
>  	struct vgic_dist *dist = &kvm->arch.vgic;
> -	struct vgic_translation_cache_entry *cte;
>  	unsigned long flags;
>  	phys_addr_t db;
>  
> @@ -621,10 +629,11 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
>  	if (irq->hw)
>  		return;
>  
> -	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
> +	new = victim = kzalloc(sizeof(*new), GFP_KERNEL_ACCOUNT);
> +	if (!new)
> +		return;
>  
> -	if (unlikely(list_empty(&dist->lpi_translation_cache)))
> -		goto out;
> +	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
>  
>  	/*
>  	 * We could have raced with another CPU caching the same
> @@ -635,17 +644,15 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
>  	if (__vgic_its_check_cache(dist, db, devid, eventid))
>  		goto out;
>  
> -	/* Always reuse the last entry (LRU policy) */
> -	cte = list_last_entry(&dist->lpi_translation_cache,
> -			      typeof(*cte), entry);
> -
> -	/*
> -	 * Caching the translation implies having an extra reference
> -	 * to the interrupt, so drop the potential reference on what
> -	 * was in the cache, and increment it on the new interrupt.
> -	 */
> -	if (cte->irq)
> -		vgic_put_irq(kvm, cte->irq);
> +	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);
> +		list_del(&victim->entry);
> +		dist->lpi_cache_count--;
> +	} else {
> +		victim = NULL;
> +	}
>
>  	/*
>  	 * The irq refcount is guaranteed to be nonzero while holding the
> @@ -654,16 +661,26 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
>  	lockdep_assert_held(&its->its_lock);
>  	vgic_get_irq_kref(irq);
>  
> -	cte->db		= db;
> -	cte->devid	= devid;
> -	cte->eventid	= eventid;
> -	cte->irq	= irq;
> +	new->db		= db;
> +	new->devid	= devid;
> +	new->eventid	= eventid;
> +	new->irq	= irq;
>  
>  	/* Move the new translation to the head of the list */
> -	list_move(&cte->entry, &dist->lpi_translation_cache);
> +	list_add(&new->entry, &dist->lpi_translation_cache);
>  
>  out:
>  	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
> +
> +	/*
> +	 * Caching the translation implies having an extra reference
> +	 * to the interrupt, so drop the potential reference on what
> +	 * was in the cache, and increment it on the new interrupt.
> +	 */
> +	if (victim && victim->irq)
> +		vgic_put_irq(kvm, victim->irq);

The games you play with 'victim' are a bit odd. I'd rather have it
initialised to NULL, and be trusted to have a valid irq if non-NULL.

Is there something special I'm missing?

Thanks,

	M.

-- 
Without deviation from the norm, progress is not possible.

Re: [PATCH 11/15] KVM: arm64: vgic-its: Lazily allocate LPI translation cache

[Oliver Upton]

On Thu, Jan 25, 2024 at 10:19:46AM +0000, Marc Zyngier wrote:
> On Wed, 24 Jan 2024 20:49:05 +0000, Oliver Upton <oliver.upton@linux.dev> wrote:
> > +
> > +	/*
> > +	 * Caching the translation implies having an extra reference
> > +	 * to the interrupt, so drop the potential reference on what
> > +	 * was in the cache, and increment it on the new interrupt.
> > +	 */
> > +	if (victim && victim->irq)
> > +		vgic_put_irq(kvm, victim->irq);
> 
> The games you play with 'victim' are a bit odd. I'd rather have it
> initialised to NULL, and be trusted to have a valid irq if non-NULL.
> 
> Is there something special I'm missing?

I pulled some shenanigans use the same cleanup path to free the new
cache entry in the case of a race. At that point the new cache entry
is initialized to 0 and doesn't have a valid pointer to an irq.

I thought this was a fun trick, but in retrospect it just makes it hard
to follow. I'll just explicitly free the new entry in the case of a
detected race and do away with the weirdness.

-- 
Thanks,
Oliver

[PATCH 12/15] 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@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-its.c | 42 ++++++++++++++++++++++++++--------
 1 file changed, 32 insertions(+), 10 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index aec82d9a1b3c..ed0c6c333a6c 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -154,6 +154,7 @@ struct vgic_translation_cache_entry {
 	u32			devid;
 	u32			eventid;
 	struct vgic_irq		*irq;
+	atomic64_t		usage_count;
 };
 
 /**
@@ -577,13 +578,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;
 	}
 
@@ -616,6 +611,30 @@ 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)
+{
+	struct vgic_translation_cache_entry *cte, *victim = NULL;
+	u64 min, tmp;
+
+	/*
+	 * Find the least used cache entry since the last cache miss, preferring
+	 * older entries in the case of a tie. Note that usage accounting is
+	 * deliberately non-atomic, so this is all best-effort.
+	 */
+	list_for_each_entry(cte, &dist->lpi_translation_cache, entry) {
+		if (!cte->irq)
+			return cte;
+
+		tmp = atomic64_xchg_relaxed(&cte->usage_count, 0);
+		if (!victim || tmp <= min) {
+			victim = cte;
+			min = tmp;
+		}
+	}
+
+	return victim;
+}
+
 static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 				       u32 devid, u32 eventid,
 				       struct vgic_irq *irq)
@@ -645,9 +664,12 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 		goto out;
 
 	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);
+		if (WARN_ON_ONCE(!victim)) {
+			victim = new;
+			goto out;
+		}
+
 		list_del(&victim->entry);
 		dist->lpi_cache_count--;
 	} else {
-- 
2.43.0.429.g432eaa2c6b-goog

Re: [PATCH 12/15] KVM: arm64: vgic-its: Pick cache victim based on usage count

[Oliver Upton]

On Wed, Jan 24, 2024 at 08:49:06PM +0000, Oliver Upton wrote:

[...]

> +static struct vgic_translation_cache_entry *vgic_its_cache_victim(struct vgic_dist *dist)
> +{
> +	struct vgic_translation_cache_entry *cte, *victim = NULL;
> +	u64 min, tmp;
> +
> +	/*
> +	 * Find the least used cache entry since the last cache miss, preferring
> +	 * older entries in the case of a tie. Note that usage accounting is
> +	 * deliberately non-atomic, so this is all best-effort.
> +	 */

This comment is stale, and does not reflect the fact that I'm very
obviously using atomics below.

-- 
Thanks,
Oliver

Re: [PATCH 12/15] KVM: arm64: vgic-its: Pick cache victim based on usage count

[Marc Zyngier]

On Wed, 24 Jan 2024 20:49:06 +0000,
Oliver Upton <oliver.upton@linux.dev> wrote:
> 
> 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 | 42 ++++++++++++++++++++++++++--------
>  1 file changed, 32 insertions(+), 10 deletions(-)
> 
> diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
> index aec82d9a1b3c..ed0c6c333a6c 100644
> --- a/arch/arm64/kvm/vgic/vgic-its.c
> +++ b/arch/arm64/kvm/vgic/vgic-its.c
> @@ -154,6 +154,7 @@ struct vgic_translation_cache_entry {
>  	u32			devid;
>  	u32			eventid;
>  	struct vgic_irq		*irq;
> +	atomic64_t		usage_count;
>  };
>  
>  /**
> @@ -577,13 +578,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;
>  	}
>  
> @@ -616,6 +611,30 @@ 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)
> +{
> +	struct vgic_translation_cache_entry *cte, *victim = NULL;
> +	u64 min, tmp;
> +
> +	/*
> +	 * Find the least used cache entry since the last cache miss, preferring
> +	 * older entries in the case of a tie. Note that usage accounting is
> +	 * deliberately non-atomic, so this is all best-effort.
> +	 */
> +	list_for_each_entry(cte, &dist->lpi_translation_cache, entry) {
> +		if (!cte->irq)
> +			return cte;
> +
> +		tmp = atomic64_xchg_relaxed(&cte->usage_count, 0);
> +		if (!victim || tmp <= min) {

min is not initialised until after the first round. Not great. How
comes the compiler doesn't spot this?

> +			victim = cte;
> +			min = tmp;
> +		}
> +	}

So this resets all the counters on each search for a new insertion?
Seems expensive, specially on large VMs (512 * 16 = up to 8K SWP
instructions in a tight loop, and I'm not even mentioning the fun
without LSE). I can at least think of a box that will throw its
interconnect out of the pram it tickled that way.

I'd rather the new cache entry inherits the max of the current set,
making it a lot cheaper. We can always detect the overflow and do a
full invalidation in that case (worse case -- better options exist).

> +
> +	return victim;
> +}
> +
>  static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
>  				       u32 devid, u32 eventid,
>  				       struct vgic_irq *irq)
> @@ -645,9 +664,12 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
>  		goto out;
>  
>  	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);
> +		if (WARN_ON_ONCE(!victim)) {
> +			victim = new;
> +			goto out;
> +		}

I don't understand how this could happen. It sort of explains the
oddity I was mentioning earlier, but I don't think we need this
complexity.

Thanks,

	M.

-- 
Without deviation from the norm, progress is not possible.

Re: [PATCH 12/15] KVM: arm64: vgic-its: Pick cache victim based on usage count

[Oliver Upton]

On Thu, Jan 25, 2024 at 10:55:19AM +0000, Marc Zyngier wrote:
> On Wed, 24 Jan 2024 20:49:06 +0000, Oliver Upton <oliver.upton@linux.dev> wrote:

[...]

> > +static struct vgic_translation_cache_entry *vgic_its_cache_victim(struct vgic_dist *dist)
> > +{
> > +	struct vgic_translation_cache_entry *cte, *victim = NULL;
> > +	u64 min, tmp;
> > +
> > +	/*
> > +	 * Find the least used cache entry since the last cache miss, preferring
> > +	 * older entries in the case of a tie. Note that usage accounting is
> > +	 * deliberately non-atomic, so this is all best-effort.
> > +	 */
> > +	list_for_each_entry(cte, &dist->lpi_translation_cache, entry) {
> > +		if (!cte->irq)
> > +			return cte;
> > +
> > +		tmp = atomic64_xchg_relaxed(&cte->usage_count, 0);
> > +		if (!victim || tmp <= min) {
> 
> min is not initialised until after the first round. Not great. How
> comes the compiler doesn't spot this?

min never gets read on the first iteration, since victim is known to be
NULL. Happy to initialize it though to keep this more ovbviously sane.

> > +			victim = cte;
> > +			min = tmp;
> > +		}
> > +	}
> 
> So this resets all the counters on each search for a new insertion?
> Seems expensive, specially on large VMs (512 * 16 = up to 8K SWP
> instructions in a tight loop, and I'm not even mentioning the fun
> without LSE). I can at least think of a box that will throw its
> interconnect out of the pram it tickled that way.

Well, each cache eviction after we hit the cache limit. I wrote this up
to have _something_ that allowed the rculist conversion to later come
back to rework futher, but that obviously didn't happen.

> I'd rather the new cache entry inherits the max of the current set,
> making it a lot cheaper. We can always detect the overflow and do a
> full invalidation in that case (worse case -- better options exist).

Yeah, I like your suggested approach. I'll probably build a bit on top
of that.

> > +
> > +	return victim;
> > +}
> > +
> >  static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
> >  				       u32 devid, u32 eventid,
> >  				       struct vgic_irq *irq)
> > @@ -645,9 +664,12 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
> >  		goto out;
> >  
> >  	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);
> > +		if (WARN_ON_ONCE(!victim)) {
> > +			victim = new;
> > +			goto out;
> > +		}
>
> I don't understand how this could happen. It sort of explains the
> oddity I was mentioning earlier, but I don't think we need this
> complexity.

The only way it could actually happen is if a bug were introduced where
lpi_cache_count is somehow nonzero but the list is empty. But yeah, we
can dump this and assume we find a victim, which ought to always be
true.

-- 
Thanks,
Oliver

Re: [PATCH 12/15] KVM: arm64: vgic-its: Pick cache victim based on usage count

[Marc Zyngier]

On Thu, 25 Jan 2024 15:34:31 +0000,
Oliver Upton <oliver.upton@linux.dev> wrote:
> 
> On Thu, Jan 25, 2024 at 10:55:19AM +0000, Marc Zyngier wrote:
> > On Wed, 24 Jan 2024 20:49:06 +0000, Oliver Upton <oliver.upton@linux.dev> wrote:
> 
> [...]
> 
> > > +static struct vgic_translation_cache_entry *vgic_its_cache_victim(struct vgic_dist *dist)
> > > +{
> > > +	struct vgic_translation_cache_entry *cte, *victim = NULL;
> > > +	u64 min, tmp;
> > > +
> > > +	/*
> > > +	 * Find the least used cache entry since the last cache miss, preferring
> > > +	 * older entries in the case of a tie. Note that usage accounting is
> > > +	 * deliberately non-atomic, so this is all best-effort.
> > > +	 */
> > > +	list_for_each_entry(cte, &dist->lpi_translation_cache, entry) {
> > > +		if (!cte->irq)
> > > +			return cte;
> > > +
> > > +		tmp = atomic64_xchg_relaxed(&cte->usage_count, 0);
> > > +		if (!victim || tmp <= min) {
> > 
> > min is not initialised until after the first round. Not great. How
> > comes the compiler doesn't spot this?
> 
> min never gets read on the first iteration, since victim is known to be
> NULL. Happy to initialize it though to keep this more ovbviously
> sane.

Ah, gotcha! Completely missed that. Sorry about the noise.

> 
> > > +			victim = cte;
> > > +			min = tmp;
> > > +		}
> > > +	}
> > 
> > So this resets all the counters on each search for a new insertion?
> > Seems expensive, specially on large VMs (512 * 16 = up to 8K SWP
> > instructions in a tight loop, and I'm not even mentioning the fun
> > without LSE). I can at least think of a box that will throw its
> > interconnect out of the pram it tickled that way.
> 
> Well, each cache eviction after we hit the cache limit. I wrote this up
> to have _something_ that allowed the rculist conversion to later come
> back to rework futher, but that obviously didn't happen.
> 
> > I'd rather the new cache entry inherits the max of the current set,
> > making it a lot cheaper. We can always detect the overflow and do a
> > full invalidation in that case (worse case -- better options exist).
> 
> Yeah, I like your suggested approach. I'll probably build a bit on top
> of that.
> 
> > > +
> > > +	return victim;
> > > +}
> > > +
> > >  static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
> > >  				       u32 devid, u32 eventid,
> > >  				       struct vgic_irq *irq)
> > > @@ -645,9 +664,12 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
> > >  		goto out;
> > >  
> > >  	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);
> > > +		if (WARN_ON_ONCE(!victim)) {
> > > +			victim = new;
> > > +			goto out;
> > > +		}
> >
> > I don't understand how this could happen. It sort of explains the
> > oddity I was mentioning earlier, but I don't think we need this
> > complexity.
> 
> The only way it could actually happen is if a bug were introduced where
> lpi_cache_count is somehow nonzero but the list is empty. But yeah, we
> can dump this and assume we find a victim, which ought to always be
> true.

Right, that was my impression as well, and I couldn't find a way to
fail it.

Thanks,

	M.

-- 
Without deviation from the norm, progress is not possible.

[PATCH 13/15] KVM: arm64: vgic-its: Protect cached vgic_irq pointers with RCU

[Oliver Upton]

RCU readers of the LPI translation cache will be able to run in parallel
with a cache invalidation, which clears the RCU pointer. Start using RCU
protection on the cached irq pointer in light of this.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-its.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index ed0c6c333a6c..79b35fdaa1cd 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -153,7 +153,7 @@ struct vgic_translation_cache_entry {
 	phys_addr_t		db;
 	u32			devid;
 	u32			eventid;
-	struct vgic_irq		*irq;
+	struct vgic_irq __rcu	*irq;
 	atomic64_t		usage_count;
 };
 
@@ -571,7 +571,7 @@ static struct vgic_irq *__vgic_its_check_cache(struct vgic_dist *dist,
 		 * If we hit a NULL entry, there is nothing after this
 		 * point.
 		 */
-		if (!cte->irq)
+		if (!rcu_access_pointer(cte->irq))
 			break;
 
 		if (cte->db != db || cte->devid != devid ||
@@ -579,7 +579,7 @@ static struct vgic_irq *__vgic_its_check_cache(struct vgic_dist *dist,
 			continue;
 
 		atomic64_inc(&cte->usage_count);
-		return cte->irq;
+		return rcu_dereference(cte->irq);
 	}
 
 	return NULL;
@@ -622,7 +622,7 @@ static struct vgic_translation_cache_entry *vgic_its_cache_victim(struct vgic_di
 	 * deliberately non-atomic, so this is all best-effort.
 	 */
 	list_for_each_entry(cte, &dist->lpi_translation_cache, entry) {
-		if (!cte->irq)
+		if (!rcu_access_pointer(cte->irq))
 			return cte;
 
 		tmp = atomic64_xchg_relaxed(&cte->usage_count, 0);
@@ -653,6 +653,7 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 		return;
 
 	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
+	rcu_read_lock();
 
 	/*
 	 * We could have raced with another CPU caching the same
@@ -686,12 +687,13 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 	new->db		= db;
 	new->devid	= devid;
 	new->eventid	= eventid;
-	new->irq	= irq;
+	rcu_assign_pointer(new->irq, irq);
 
 	/* Move the new translation to the head of the list */
 	list_add(&new->entry, &dist->lpi_translation_cache);
 
 out:
+	rcu_read_unlock();
 	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
 
 	/*
@@ -712,19 +714,21 @@ void vgic_its_invalidate_cache(struct kvm *kvm)
 	unsigned long flags;
 
 	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
+	rcu_read_lock();
 
 	list_for_each_entry(cte, &dist->lpi_translation_cache, entry) {
 		/*
 		 * If we hit a NULL entry, there is nothing after this
 		 * point.
 		 */
-		if (!cte->irq)
+		if (!rcu_access_pointer(cte->irq))
 			break;
 
 		vgic_put_irq(kvm, cte->irq);
-		cte->irq = NULL;
+		rcu_assign_pointer(cte->irq, NULL);
 	}
 
+	rcu_read_unlock();
 	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
 }
 
-- 
2.43.0.429.g432eaa2c6b-goog

Re: [PATCH 13/15] KVM: arm64: vgic-its: Protect cached vgic_irq pointers with RCU

[kernel test robot]

Hi Oliver,

kernel test robot noticed the following build warnings:

[auto build test WARNING on 6613476e225e090cc9aad49be7fa504e290dd33d]

url:    https://github.com/intel-lab-lkp/linux/commits/Oliver-Upton/KVM-arm64-vgic-Store-LPIs-in-an-xarray/20240125-045255
base:   6613476e225e090cc9aad49be7fa504e290dd33d
patch link:    https://lore.kernel.org/r/20240124204909.105952-14-oliver.upton%40linux.dev
patch subject: [PATCH 13/15] KVM: arm64: vgic-its: Protect cached vgic_irq pointers with RCU
config: arm64-randconfig-r112-20240128 (https://download.01.org/0day-ci/archive/20240129/202401290835.TjDnhUFI-lkp@intel.com/config)
compiler: clang version 18.0.0git (https://github.com/llvm/llvm-project a31a60074717fc40887cfe132b77eec93bedd307)
reproduce: (https://download.01.org/0day-ci/archive/20240129/202401290835.TjDnhUFI-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202401290835.TjDnhUFI-lkp@intel.com/

sparse warnings: (new ones prefixed by >>)
>> arch/arm64/kvm/vgic/vgic-its.c:705:41: sparse: sparse: incorrect type in argument 2 (different address spaces) @@     expected struct vgic_irq *irq @@     got struct vgic_irq [noderef] __rcu *irq @@
   arch/arm64/kvm/vgic/vgic-its.c:705:41: sparse:     expected struct vgic_irq *irq
   arch/arm64/kvm/vgic/vgic-its.c:705:41: sparse:     got struct vgic_irq [noderef] __rcu *irq
   arch/arm64/kvm/vgic/vgic-its.c:727:38: sparse: sparse: incorrect type in argument 2 (different address spaces) @@     expected struct vgic_irq *irq @@     got struct vgic_irq [noderef] __rcu *irq @@
   arch/arm64/kvm/vgic/vgic-its.c:727:38: sparse:     expected struct vgic_irq *irq
   arch/arm64/kvm/vgic/vgic-its.c:727:38: sparse:     got struct vgic_irq [noderef] __rcu *irq
   arch/arm64/kvm/vgic/vgic-its.c:891:17: sparse: sparse: cast to restricted __le64
   arch/arm64/kvm/vgic/vgic-its.c:1031:24: sparse: sparse: cast to restricted __le64
   arch/arm64/kvm/vgic/vgic-its.c:2245:13: sparse: sparse: incorrect type in assignment (different base types) @@     expected unsigned long long [assigned] [usertype] val @@     got restricted __le64 [usertype] @@
   arch/arm64/kvm/vgic/vgic-its.c:2245:13: sparse:     expected unsigned long long [assigned] [usertype] val
   arch/arm64/kvm/vgic/vgic-its.c:2245:13: sparse:     got restricted __le64 [usertype]
   arch/arm64/kvm/vgic/vgic-its.c:2271:15: sparse: sparse: cast to restricted __le64
   arch/arm64/kvm/vgic/vgic-its.c:2397:13: sparse: sparse: incorrect type in assignment (different base types) @@     expected unsigned long long [assigned] [usertype] val @@     got restricted __le64 [usertype] @@
   arch/arm64/kvm/vgic/vgic-its.c:2397:13: sparse:     expected unsigned long long [assigned] [usertype] val
   arch/arm64/kvm/vgic/vgic-its.c:2397:13: sparse:     got restricted __le64 [usertype]
   arch/arm64/kvm/vgic/vgic-its.c:2424:17: sparse: sparse: cast to restricted __le64
   arch/arm64/kvm/vgic/vgic-its.c:2525:17: sparse: sparse: cast to restricted __le64
   arch/arm64/kvm/vgic/vgic-its.c:2584:13: sparse: sparse: incorrect type in assignment (different base types) @@     expected unsigned long long [assigned] [usertype] val @@     got restricted __le64 [usertype] @@
   arch/arm64/kvm/vgic/vgic-its.c:2584:13: sparse:     expected unsigned long long [assigned] [usertype] val
   arch/arm64/kvm/vgic/vgic-its.c:2584:13: sparse:     got restricted __le64 [usertype]
   arch/arm64/kvm/vgic/vgic-its.c:2605:15: sparse: sparse: cast to restricted __le64
   arch/arm64/kvm/vgic/vgic-its.c:39:24: sparse: sparse: context imbalance in 'vgic_add_lpi' - different lock contexts for basic block
   arch/arm64/kvm/vgic/vgic-its.c:284:12: sparse: sparse: context imbalance in 'update_lpi_config' - different lock contexts for basic block
   arch/arm64/kvm/vgic/vgic-its.c:458:9: sparse: sparse: context imbalance in 'its_sync_lpi_pending_table' - different lock contexts for basic block
   arch/arm64/kvm/vgic/vgic-its.c: note: in included file (through include/linux/random.h, arch/arm64/include/asm/pointer_auth.h, arch/arm64/include/asm/processor.h, ...):
   include/linux/list.h:83:21: sparse: sparse: self-comparison always evaluates to true
   arch/arm64/kvm/vgic/vgic-its.c:796:12: sparse: sparse: context imbalance in 'vgic_its_trigger_msi' - different lock contexts for basic block
   arch/arm64/kvm/vgic/vgic-its.c:818:5: sparse: sparse: context imbalance in 'vgic_its_inject_cached_translation' - wrong count at exit
   include/linux/list.h:83:21: sparse: sparse: self-comparison always evaluates to true
   include/linux/list.h:83:21: sparse: sparse: self-comparison always evaluates to true
   include/linux/list.h:83:21: sparse: sparse: self-comparison always evaluates to true

vim +705 arch/arm64/kvm/vgic/vgic-its.c

73dcc3dd6274b9 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  637  
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  638  static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  639  				       u32 devid, u32 eventid,
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  640  				       struct vgic_irq *irq)
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  641  {
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  642  	struct vgic_translation_cache_entry *new, *victim;
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  643  	struct vgic_dist *dist = &kvm->arch.vgic;
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  644  	unsigned long flags;
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  645  	phys_addr_t db;
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  646  
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  647  	/* Do not cache a directly injected interrupt */
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  648  	if (irq->hw)
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  649  		return;
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  650  
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  651  	new = victim = kzalloc(sizeof(*new), GFP_KERNEL_ACCOUNT);
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  652  	if (!new)
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  653  		return;
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  654  
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  655  	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
131b61b5cd90e9 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  656  	rcu_read_lock();
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  657  
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  658  	/*
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  659  	 * We could have raced with another CPU caching the same
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  660  	 * translation behind our back, so let's check it is not in
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  661  	 * already
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  662  	 */
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  663  	db = its->vgic_its_base + GITS_TRANSLATER;
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  664  	if (__vgic_its_check_cache(dist, db, devid, eventid))
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  665  		goto out;
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  666  
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  667  	if (dist->lpi_cache_count >= vgic_its_max_cache_size(kvm)) {
73dcc3dd6274b9 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  668  		victim = vgic_its_cache_victim(dist);
73dcc3dd6274b9 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  669  		if (WARN_ON_ONCE(!victim)) {
73dcc3dd6274b9 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  670  			victim = new;
73dcc3dd6274b9 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  671  			goto out;
73dcc3dd6274b9 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  672  		}
73dcc3dd6274b9 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  673  
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  674  		list_del(&victim->entry);
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  675  		dist->lpi_cache_count--;
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  676  	} else {
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  677  		victim = NULL;
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  678  	}
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  679  
7f253bdb6144f3 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  680  	/*
7f253bdb6144f3 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  681  	 * The irq refcount is guaranteed to be nonzero while holding the
7f253bdb6144f3 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  682  	 * its_lock, as the ITE (and the reference it holds) cannot be freed.
7f253bdb6144f3 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  683  	 */
7f253bdb6144f3 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  684  	lockdep_assert_held(&its->its_lock);
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  685  	vgic_get_irq_kref(irq);
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  686  
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  687  	new->db		= db;
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  688  	new->devid	= devid;
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  689  	new->eventid	= eventid;
131b61b5cd90e9 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  690  	rcu_assign_pointer(new->irq, irq);
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  691  
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  692  	/* Move the new translation to the head of the list */
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  693  	list_add(&new->entry, &dist->lpi_translation_cache);
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  694  
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  695  out:
131b61b5cd90e9 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  696  	rcu_read_unlock();
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  697  	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  698  
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  699  	/*
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  700  	 * Caching the translation implies having an extra reference
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  701  	 * to the interrupt, so drop the potential reference on what
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  702  	 * was in the cache, and increment it on the new interrupt.
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  703  	 */
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  704  	if (victim && victim->irq)
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24 @705  		vgic_put_irq(kvm, victim->irq);
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  706  
8fb2f0e370c963 arch/arm64/kvm/vgic/vgic-its.c Oliver Upton 2024-01-24  707  	kfree(victim);
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  708  }
89489ee9ced892 virt/kvm/arm/vgic/vgic-its.c   Marc Zyngier 2019-03-18  709  

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

[PATCH 14/15] KVM: arm64: vgic-its: Treat the LPI translation cache as an rculist

[Oliver Upton]

Convert the LPI translation cache to an rculist such that readers can
walk it while only holding the RCU read lock.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-its.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index 79b35fdaa1cd..1670b452c682 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -566,7 +566,7 @@ static struct vgic_irq *__vgic_its_check_cache(struct vgic_dist *dist,
 {
 	struct vgic_translation_cache_entry *cte;
 
-	list_for_each_entry(cte, &dist->lpi_translation_cache, entry) {
+	list_for_each_entry_rcu(cte, &dist->lpi_translation_cache, entry) {
 		/*
 		 * If we hit a NULL entry, there is nothing after this
 		 * point.
@@ -671,7 +671,7 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 			goto out;
 		}
 
-		list_del(&victim->entry);
+		list_del_rcu(&victim->entry);
 		dist->lpi_cache_count--;
 	} else {
 		victim = NULL;
@@ -690,7 +690,8 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 	rcu_assign_pointer(new->irq, irq);
 
 	/* Move the new translation to the head of the list */
-	list_add(&new->entry, &dist->lpi_translation_cache);
+	list_add_rcu(&new->entry, &dist->lpi_translation_cache);
+	dist->lpi_cache_count++;
 
 out:
 	rcu_read_unlock();
@@ -704,6 +705,7 @@ static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its,
 	if (victim && victim->irq)
 		vgic_put_irq(kvm, victim->irq);
 
+	synchronize_rcu();
 	kfree(victim);
 }
 
-- 
2.43.0.429.g432eaa2c6b-goog

[PATCH 15/15] KVM: arm64: vgic-its: Rely on RCU to protect translation cache reads

[Oliver Upton]

Stop taking the lpi_list_lock when reading the LPI translation cache.

Signed-off-by: Oliver Upton <oliver.upton@linux.dev>
---
 arch/arm64/kvm/vgic/vgic-its.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index 1670b452c682..46ff21fea785 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -590,15 +590,14 @@ static struct vgic_irq *vgic_its_check_cache(struct kvm *kvm, phys_addr_t db,
 {
 	struct vgic_dist *dist = &kvm->arch.vgic;
 	struct vgic_irq *irq;
-	unsigned long flags;
 
-	raw_spin_lock_irqsave(&dist->lpi_list_lock, flags);
+	rcu_read_lock();
 
 	irq = __vgic_its_check_cache(dist, db, devid, eventid);
 	if (irq && !vgic_try_get_irq_kref(irq))
 		irq = NULL;
 
-	raw_spin_unlock_irqrestore(&dist->lpi_list_lock, flags);
+	rcu_read_unlock();
 
 	return irq;
 }
-- 
2.43.0.429.g432eaa2c6b-goog

Re: [PATCH 00/15] KVM: arm64: Improvements to GICv3 LPI injection

[Marc Zyngier]

Hi Oliver,

On Wed, 24 Jan 2024 20:48:54 +0000,
Oliver Upton <oliver.upton@linux.dev> wrote:
> 
> The unfortunate reality is there are increasingly large systems that are
> shipping today without support for GICv4 vLPI injection. Serialization
> in KVM's LPI routing/injection code has been a significant bottleneck
> for VMs on these machines when under a high load of LPIs (e.g. a
> multi-queue NIC).
> 
> Even though the long-term solution is quite clearly **direct
> injection**, we really ought to do something about the LPI scaling
> issues within KVM.
> 
> This series aims to improve the performance of LPI routing/injection in
> KVM by moving readers of LPI configuration data away from the
> lpi_list_lock in favor or using RCU.
> 
> Patches 1-5 change out the representation of LPIs in KVM from a
> linked-list to an xarray. While not strictly necessary for making the
> locking improvements, this seems to be an opportune time to switch to a
> data structure that can actually be indexed.
> 
> Patches 6-10 transition vgic_get_lpi() and vgic_put_lpi() away from
> taking the lpi_list_lock in favor of using RCU for protection. Note that
> this requires some rework to the way references are taken on LPIs and
> how reclaim works to be RCU safe.
> 
> Lastly, patches 11-15 rework the LRU policy on the LPI translation cache
> to not require moving elements in the linked-list and take advantage of
> this to make it an rculist readable outside of the lpi_list_lock.

I quite like the overall direction. I've left a few comments here and
there, and will probably get back to it after I try to run some tests
on a big-ish box.

> All of this was tested on top of v6.8-rc1. Apologies if any of the
> changelogs are a bit too light, I'm happy to rework those further in
> subsequent revisions.
> 
> I would've liked to have benchmark data showing the improvement on top
> of upstream with this series, but I'm currently having issues with our
> internal infrastructure and upstream kernels. However, this series has
> been found to have a near 2x performance improvement to redis-memtier [*]
> benchmarks on our kernel tree.

It'd be really good to have upstream-based numbers, with details of
the actual setup (device assignment? virtio?) so that we can compare
things and even track regressions in the future.

Thanks,

	M.

-- 
Without deviation from the norm, progress is not possible.

Re: [PATCH 00/15] KVM: arm64: Improvements to GICv3 LPI injection

[Oliver Upton]

On Thu, Jan 25, 2024 at 11:02:01AM +0000, Marc Zyngier wrote:

[...]

> > I would've liked to have benchmark data showing the improvement on top
> > of upstream with this series, but I'm currently having issues with our
> > internal infrastructure and upstream kernels. However, this series has
> > been found to have a near 2x performance improvement to redis-memtier [*]
> > benchmarks on our kernel tree.
> 
> It'd be really good to have upstream-based numbers, with details of
> the actual setup (device assignment? virtio?) so that we can compare
> things and even track regressions in the future.

Yeah, that sort of thing isn't optional IMO, I just figured that getting
reviews on this would be a bit more productive while I try and recreate
the test correctly on top of upstream.

The test setup I based my "2x" statement on is 4 16 vCPU client VMs
talking to 1 16 vCPU server VM over NIC VFs assigned to the
respective VMs. 16 TX + 16 RX queues for each NIC. As I'm sure you're
aware, I know damn near nothing about the Redis setup itself, and I'll
need to do a bit of work to translate the thing I was using into a
script.

-- 
Thanks,
Oliver