Skip to contentSkip to conversation

KVM: arm64: Improvements to GICv3 LPI injection

PATCH Superseded Oliver Upton 4 participants 30 messages Jan 24, 2024 – Feb 5, 2024

Subsystems (3)

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

cover KVM: arm64: Improvements to GICv3 LPI injection

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

Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
#1 lore raw

PATCH 1/15 KVM: arm64: vgic: Store LPIs in an xarray

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.

---
 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(+)
arch/arm64/kvm/vgic/vgic-init.c +3 -0
index e949e1d0fd9f..411719053107 100644
@@ -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)
arch/arm64/kvm/vgic/vgic-its.c +13 -0
index e2764d0ffa9f..f152d670113f 100644
@@ -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++;
 
arch/arm64/kvm/vgic/vgic.c +1 -0
index db2a95762b1b..c126014f8395 100644
@@ -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);
include/kvm/arm_vgic.h +2 -0
index 8cc38e836f54..795b35656b54 100644
@@ -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;
 
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
#2 lore raw

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

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/[email protected]/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 <[email protected]>
| Reported-by: Dan Carpenter <[email protected]>
| Closes: https://lore.kernel.org/r/[email protected]/

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  }
Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#3 lore raw

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

In reply to 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.

---
 arch/arm64/kvm/vgic/vgic.c | 19 +++++--------------
 1 file changed, 5 insertions(+), 14 deletions(-)
arch/arm64/kvm/vgic/vgic.c +5 -14
index c126014f8395..d90c42ff051d 100644
@@ -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;
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
#4 lore raw

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

In reply to 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.

---
 arch/arm64/kvm/vgic/vgic-v3.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
arch/arm64/kvm/vgic/vgic-v3.c +2 -1
index 9465d3706ab9..4ea3340786b9 100644
@@ -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;
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
#5 lore raw

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

In reply to Oliver Upton

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

---
 arch/arm64/kvm/vgic/vgic-its.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
arch/arm64/kvm/vgic/vgic-its.c +6 -1
index f152d670113f..a2d95a279798 100644
@@ -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;
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
maintainer
#6 lore raw

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

Quoted 14 lines · Oliver Upton

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

---
 arch/arm64/kvm/vgic/vgic-its.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
arch/arm64/kvm/vgic/vgic-its.c +0 -0
index f152d670113f..a2d95a279798 100644

arch/arm64/kvm/vgic/vgic-its.c static int update_lpi_config(struct kvm *kvm, struct vgic_irq *irq, · line 335

Quoted 4 lines
arch/arm64/kvm/vgic/vgic-its.c +1 -0
@@ -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.

arch/arm64/kvm/vgic/vgic-its.c int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr) · line 356

Quoted 11 lines
arch/arm64/kvm/vgic/vgic-its.c +3 -1
 	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.

arch/arm64/kvm/vgic/vgic-its.c int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr) · line 368

Quoted 12 lines
arch/arm64/kvm/vgic/vgic-its.c +2 -0
 		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.
Signature · 1 line
Without deviation from the norm, progress is not possible.
#7 lore raw

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

Quoted 11 lines · Marc Zyngier
Quoted 9 lines · Oliver Upton

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

---
 arch/arm64/kvm/vgic/vgic-its.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
Quoted 12 lines

arch/arm64/kvm/vgic/vgic-its.c static int update_lpi_config(struct kvm *kvm, struct vgic_irq *irq, · line 335

Quoted 9 lines
arch/arm64/kvm/vgic/vgic-its.c +1 -0
index f152d670113f..a2d95a279798 100644
@@ -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!

Quoted 6 lines
Quoted 6 lines
arch/arm64/kvm/vgic/vgic-its.c +0 -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;
 
Quoted 9 lines

arch/arm64/kvm/vgic/vgic-its.c int vgic_copy_lpi_list(struct kvm *kvm, struct kvm_vcpu *vcpu, u32 **intid_ptr) · line 356

Quoted 5 lines
arch/arm64/kvm/vgic/vgic-its.c +3 -1
 	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.

Signature · 2 lines
Thanks,
Oliver
#8 lore raw

PATCH 5/15 KVM: arm64: vgic: Get rid of the LPI linked-list

In reply to Oliver Upton

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

---
 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(-)
arch/arm64/kvm/vgic/vgic-init.c +0 -1
index 411719053107..e25672d6e846 100644
@@ -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);
arch/arm64/kvm/vgic/vgic-its.c +2 -5
index a2d95a279798..0486d3779d11 100644
@@ -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:
arch/arm64/kvm/vgic/vgic.c +0 -1
index d90c42ff051d..e58ce68e325c 100644
@@ -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--;
 
include/kvm/arm_vgic.h +0 -1
index 795b35656b54..39037db3fa90 100644
@@ -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 */
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
maintainer
#9 lore raw

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

Quoted 66 lines · Oliver Upton

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

---
 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(-)
arch/arm64/kvm/vgic/vgic-init.c +0 -1
index 411719053107..e25672d6e846 100644
@@ -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);
arch/arm64/kvm/vgic/vgic-its.c +2 -5
index a2d95a279798..0486d3779d11 100644
@@ -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:
arch/arm64/kvm/vgic/vgic.c +0 -1
index d90c42ff051d..e58ce68e325c 100644
@@ -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--;
 
include/kvm/arm_vgic.h +0 -0
index 795b35656b54..39037db3fa90 100644

include/kvm/arm_vgic.h struct vgic_dist { · line 282

Quoted 7 lines
include/kvm/arm_vgic.h +0 -1
@@ -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):

arch/arm64/kvm/vgic/vgic-its.c +0 -1
index 46ff21fea785..3de41ee5e6ee 100644
@@ -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);
 
include/kvm/arm_vgic.h +0 -1
index f3fc2cc922ce..4439039ccd45 100644
@@ -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.
Signature · 1 line
Without deviation from the norm, progress is not possible.
#10 lore raw

PATCH 6/15 KVM: arm64: vgic: Use atomics to count LPIs

In reply to Oliver Upton

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

---
 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(-)
arch/arm64/kvm/vgic/vgic-debug.c +1 -1
index 85606a531dc3..389025ce7749 100644
@@ -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");
 
arch/arm64/kvm/vgic/vgic-its.c +2 -2
index 0486d3779d11..1d912a595b71 100644
@@ -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;
arch/arm64/kvm/vgic/vgic.c +1 -1
index e58ce68e325c..5988d162b765 100644
@@ -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);
 }
include/kvm/arm_vgic.h +2 -2
index 39037db3fa90..e944536feee8 100644
@@ -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;
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
#11 lore raw

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

In reply to 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.

---
 arch/arm64/kvm/vgic/vgic.c | 2 +-
 include/kvm/arm_vgic.h     | 1 +
 2 files changed, 2 insertions(+), 1 deletion(-)
arch/arm64/kvm/vgic/vgic.c +1 -1
index 5988d162b765..be3ed4c5e1fa 100644
@@ -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)
include/kvm/arm_vgic.h +1 -0
index e944536feee8..a6f6c1583662 100644
@@ -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;
 
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
#12 lore raw

PATCH 8/15 KVM: arm64: vgic: Rely on RCU protection in vgic_get_lpi()

In reply to 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.

---
 arch/arm64/kvm/vgic/vgic.c |  9 ++++-----
 arch/arm64/kvm/vgic/vgic.h | 11 ++++++++---
 2 files changed, 12 insertions(+), 8 deletions(-)
arch/arm64/kvm/vgic/vgic.c +4 -5
index be3ed4c5e1fa..949af87bb599 100644
@@ -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;
 }
arch/arm64/kvm/vgic/vgic.h +8 -3
index 8d134569d0a1..20886f57416a 100644
@@ -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);
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
#13 lore raw

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

In reply to 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.

---
 arch/arm64/kvm/vgic/vgic-its.c | 18 ++++++++----------
 arch/arm64/kvm/vgic/vgic.c     |  3 ++-
 2 files changed, 10 insertions(+), 11 deletions(-)
arch/arm64/kvm/vgic/vgic-its.c +8 -10
index 1d912a595b71..7219f4a0a93d 100644
@@ -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;
arch/arm64/kvm/vgic/vgic.c +2 -1
index 949af87bb599..7e0d84906a12 100644
@@ -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);
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
maintainer
#14 lore raw

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

Quoted 18 lines · 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.

---
 arch/arm64/kvm/vgic/vgic-its.c | 18 ++++++++----------
 arch/arm64/kvm/vgic/vgic.c     |  3 ++-
 2 files changed, 10 insertions(+), 11 deletions(-)
arch/arm64/kvm/vgic/vgic-its.c +0 -0
index 1d912a595b71..7219f4a0a93d 100644

arch/arm64/kvm/vgic/vgic-its.c static struct vgic_irq *vgic_add_lpi(struct kvm *kvm, u32 intid, · line 78

Quoted 5 lines
arch/arm64/kvm/vgic/vgic-its.c +1 -1
@@ -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.
Signature · 1 line
Without deviation from the norm, progress is not possible.
#15 lore raw

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

In reply to 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().

---
 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(-)
arch/arm64/kvm/vgic/vgic-its.c +2 -2
index 7219f4a0a93d..8c026a530018 100644
@@ -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;
 	}
 
arch/arm64/kvm/vgic/vgic.c +4 -17
index 7e0d84906a12..6b8f440ca0fd 100644
@@ -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;
arch/arm64/kvm/vgic/vgic.h +0 -1
index 20886f57416a..b0a2754eae93 100644
@@ -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);
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
#16 lore raw

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

In reply to 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.

---
 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(-)
arch/arm64/kvm/vgic/vgic-init.c +0 -3
index e25672d6e846..660d5ce3b610 100644
@@ -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
arch/arm64/kvm/vgic/vgic-its.c +37 -49

133 lines not on this page · raw message

include/kvm/arm_vgic.h +1 -0
index a6f6c1583662..70490a2a300d 100644
@@ -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;
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
maintainer
#17 lore raw

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

Quoted 116 lines · 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.

---
 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(-)
arch/arm64/kvm/vgic/vgic-init.c +0 -3
index e25672d6e846..660d5ce3b610 100644
@@ -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
arch/arm64/kvm/vgic/vgic-its.c +27 -20
index 8c026a530018..aec82d9a1b3c 100644
@@ -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);
 

arch/arm64/kvm/vgic/vgic-its.c static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its, · line 681

Quoted 10 lines
arch/arm64/kvm/vgic/vgic-its.c +8 -0
 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.
Signature · 1 line
Without deviation from the norm, progress is not possible.
#18 lore raw

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

Quoted 13 lines · Marc Zyngier

arch/arm64/kvm/vgic/vgic-its.c static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its, · line 681

Quoted 8 lines · Oliver Upton
arch/arm64/kvm/vgic/vgic-its.c +8 -0
+
+	/*
+	 * 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.

Quoted 1 line

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.

Signature · 2 lines
Thanks,
Oliver
#19 lore raw

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

In reply to 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)

---
 arch/arm64/kvm/vgic/vgic-its.c | 42 ++++++++++++++++++++++++++--------
 1 file changed, 32 insertions(+), 10 deletions(-)
arch/arm64/kvm/vgic/vgic-its.c +32 -10
index aec82d9a1b3c..ed0c6c333a6c 100644
@@ -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 {
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
#20 lore raw

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

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

[...]

arch/arm64/kvm/vgic/vgic-its.c static unsigned int vgic_its_max_cache_size(struct kvm *kvm) · line 623

Quoted 10 lines
arch/arm64/kvm/vgic/vgic-its.c +10 -0
+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.

Signature · 2 lines
Thanks,
Oliver
maintainer
#21 lore raw

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

In reply to Oliver Upton
Quoted 58 lines · 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)

---
 arch/arm64/kvm/vgic/vgic-its.c | 42 ++++++++++++++++++++++++++--------
 1 file changed, 32 insertions(+), 10 deletions(-)
arch/arm64/kvm/vgic/vgic-its.c +8 -7
index aec82d9a1b3c..ed0c6c333a6c 100644
@@ -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;
+
+	/*

arch/arm64/kvm/vgic/vgic-its.c static unsigned int vgic_its_max_cache_size(struct kvm *kvm) · line 629

Quoted 10 lines
arch/arm64/kvm/vgic/vgic-its.c +10 -0
+	 * 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?

arch/arm64/kvm/vgic/vgic-its.c static unsigned int vgic_its_max_cache_size(struct kvm *kvm) · line 633

Quoted 4 lines
arch/arm64/kvm/vgic/vgic-its.c +4 -0
+			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).

Quoted 9 lines
arch/arm64/kvm/vgic/vgic-its.c +4 -0
+
+	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;

arch/arm64/kvm/vgic/vgic-its.c static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its, · line 671

Quoted 10 lines
arch/arm64/kvm/vgic/vgic-its.c +5 -3
 
 	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.
Signature · 1 line
Without deviation from the norm, progress is not possible.
#22 lore raw

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

Quoted 1 line · Marc Zyngier

On Wed, 24 Jan 2024 20:49:06 +0000, Oliver Upton <[email protected]> wrote:

[...]

Quoted 11 lines
Quoted 11 lines
arch/arm64/kvm/vgic/vgic-its.c +11 -0
+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) {
Quoted 8 lines

arch/arm64/kvm/vgic/vgic-its.c static unsigned int vgic_its_max_cache_size(struct kvm *kvm) · line 629

Quoted 5 lines
arch/arm64/kvm/vgic/vgic-its.c +5 -0
+		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.

Quoted 10 lines

arch/arm64/kvm/vgic/vgic-its.c static unsigned int vgic_its_max_cache_size(struct kvm *kvm) · line 633

Quoted 4 lines
arch/arm64/kvm/vgic/vgic-its.c +4 -0
+			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.

Quoted 3 lines

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.

Quoted 10 lines
Quoted 10 lines
arch/arm64/kvm/vgic/vgic-its.c +4 -0
+
+	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;
 
Quoted 13 lines

arch/arm64/kvm/vgic/vgic-its.c static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its, · line 671

Quoted 9 lines
arch/arm64/kvm/vgic/vgic-its.c +5 -3
 	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.

Signature · 2 lines
Thanks,
Oliver
maintainer
#23 lore raw

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

Quoted 26 lines · Oliver Upton
Quoted 1 line · Marc Zyngier

On Wed, 24 Jan 2024 20:49:06 +0000, Oliver Upton <[email protected]> wrote:

[...]

Quoted 11 lines
Quoted 11 lines
arch/arm64/kvm/vgic/vgic-its.c +11 -0
+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) {
Quoted 8 lines

arch/arm64/kvm/vgic/vgic-its.c static unsigned int vgic_its_max_cache_size(struct kvm *kvm) · line 629

Quoted 5 lines
arch/arm64/kvm/vgic/vgic-its.c +5 -0
+		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?

Quoted 3 lines

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.

Quoted 47 lines
Quoted 11 lines

arch/arm64/kvm/vgic/vgic-its.c static unsigned int vgic_its_max_cache_size(struct kvm *kvm) · line 633

Quoted 5 lines
arch/arm64/kvm/vgic/vgic-its.c +4 -0
+			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.

Quoted 3 lines

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.

Quoted 10 lines
Quoted 10 lines
arch/arm64/kvm/vgic/vgic-its.c +4 -0
+
+	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;
 
Quoted 13 lines

arch/arm64/kvm/vgic/vgic-its.c static void vgic_its_cache_translation(struct kvm *kvm, struct vgic_its *its, · line 671

Quoted 9 lines
arch/arm64/kvm/vgic/vgic-its.c +5 -3
 	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.

Quoted 4 lines

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.
Signature · 1 line
Without deviation from the norm, progress is not possible.
#24 lore raw

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

In reply to 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.

---
 arch/arm64/kvm/vgic/vgic-its.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
arch/arm64/kvm/vgic/vgic-its.c +11 -7
index ed0c6c333a6c..79b35fdaa1cd 100644
@@ -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);
 }
 
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
#25 lore raw

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

kernel test robot noticed the following build warnings:

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/[email protected]/config)
compiler: clang version 18.0.0git (https://github.com/llvm/llvm-project a31a60074717fc40887cfe132b77eec93bedd307)
reproduce: (https://download.01.org/0day-ci/archive/20240129/[email protected]/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 <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

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  
Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#26 lore raw

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

In reply to Oliver Upton

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

---
 arch/arm64/kvm/vgic/vgic-its.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)
arch/arm64/kvm/vgic/vgic-its.c +5 -3
index 79b35fdaa1cd..1670b452c682 100644
@@ -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);
 }
 
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
#27 lore raw

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

In reply to Oliver Upton

Stop taking the lpi_list_lock when reading the LPI translation cache.

---
 arch/arm64/kvm/vgic/vgic-its.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)
arch/arm64/kvm/vgic/vgic-its.c +2 -3
index 1670b452c682..46ff21fea785 100644
@@ -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;
 }
Signature · 1 line
2.43.0.429.g432eaa2c6b-goog
maintainer
#28 lore raw
In reply to Oliver Upton

Hi Oliver,

Quoted 20 lines · 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.

Quoted 8 lines

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.

Quoted 9 lines

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.
Signature · 1 line
Without deviation from the norm, progress is not possible.
#29 lore raw

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

[...]

Quoted 9 lines
Quoted 5 lines

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.

Signature · 2 lines
Thanks,
Oliver