Skip to contentSkip to conversation

KVM: arm64: vgic-its: Fix O(C*I) loop in vgic_its_free_collection_list

PATCH In review Jing Zhang 3 participants 4 messages Aug 18 – Aug 28

Subsystems (3)
lore
Share & tools
lore

Jing Zhang

author
#0 lore raw

PATCH 1/1 KVM: arm64: vgic-its: Fix O(C*I) loop in vgic_its_free_collection_list

When destroying the vgic-its collection list, vgic_its_free_collection_list() iterates over every collection and for each, calls vgic_its_free_collection(). This function walks every Interrupt Translation Entry (ITE) across all devices via for_each_lpi_its() to nullify the collection pointer.

A guest can allocate up to 65536 collections and hundreds of thousands of ITEs. By clearing GITS_CTLR.Enable and writing Valid=0 to GITS_BASER1, the guest can trigger this teardown path from a single MMIO exit. The resulting O(Collections * ITEs) nested loop executes billions of iterations without a single cond_resched(). This pins a physical CPU and stalls RCU grace periods for seconds or minutes on PREEMPT_NONE kernels.

Fix this by replacing the O(Collections * ITEs) teardown with an O(Collections + ITEs) pass. Since the entire collection list is being freed, we can safely bulk-clear the collection pointers from all ITEs in a single pass, and then free all the collections in a second pass.

---
 arch/arm64/kvm/vgic/vgic-its.c | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)
arch/arm64/kvm/vgic/vgic-its.c +14 -2
index 36ab3e4929154..a8e819fe97898 100644
@@ -1133,9 +1133,21 @@ static void vgic_its_free_device_list(struct kvm *kvm, struct vgic_its *its)
 static void vgic_its_free_collection_list(struct kvm *kvm, struct vgic_its *its)
 {
 	struct its_collection *cur, *temp;
+	struct its_device *device;
+	struct its_ite *ite;
 
-	list_for_each_entry_safe(cur, temp, &its->collection_list, coll_list)
-		vgic_its_free_collection(its, cur->collection_id);
+	/*
+	 * Bulk-clear the collection pointers for all ITEs.
+	 * This transforms the teardown complexity from O(Collections * ITEs)
+	 * to O(Collections + ITEs), avoiding guest-triggered host RCU stalls.
+	 */
+	for_each_lpi_its(device, ite, its)
+		ite->collection = NULL;
+
+	list_for_each_entry_safe(cur, temp, &its->collection_list, coll_list) {
+		list_del(&cur->coll_list);
+		kfree(cur);
+	}
 }
 
 /* Must be called with its_lock mutex held */
Signature · 1 line
2.55.0.737.g08866a6d13-goog
#1 lore raw
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:

Pre-existing issues:
- [Critical] Unconditional dereference of ite->collection during ITS table save leads to host kernel panic.
- [High] Unmitigated O(Total ITEs) loops during ITS command processing lead to guest-triggered soft lockups and RCU stalls. --

--- Patch [1]: [PATCH] KVM: arm64: vgic-its: Fix O(C*I) loop in vgic_its_free_collection_list --- commit 57034db6ba413048ab15ade32e11d1ba6a290388
Author: Jing Zhang <[email protected]>

KVM: arm64: vgic-its: Fix O(C*I) loop in vgic_its_free_collection_list

When destroying the vgic-its collection list, vgic_its_free_collection_list() iterates over every collection and for each, calls vgic_its_free_collection(). This function walks every Interrupt Translation Entry (ITE) across all devices via for_each_lpi_its() to nullify the collection pointer.

[ ... ]

Quoted 8 lines
arch/arm64/kvm/vgic/vgic-its.c +0 -0
index 4477f870c7b36..5e907a34226e3 100644
@@ -1122,9 +1122,21 @@ static void vgic_its_free_device_list(struct kvm *kvm, struct vgic_its *its)
 static void vgic_its_free_collection_list(struct kvm *kvm, struct vgic_its *its)
 {
 	struct its_collection *cur, *temp;

arch/arm64/kvm/vgic/vgic-its.c static void vgic_its_free_device_list(struct kvm *kvm, struct vgic_its *its) · line 1132

Quoted 10 lines
arch/arm64/kvm/vgic/vgic-its.c +7 -2
+	struct its_device *device;
+	struct its_ite *ite;
 
-	list_for_each_entry_safe(cur, temp, &its->collection_list, coll_list)
-		vgic_its_free_collection(its, cur->collection_id);
+	/*
+	 * Bulk-clear the collection pointers for all ITEs.
+	 * This transforms the teardown complexity from O(Collections * ITEs)
+	 * to O(Collections + ITEs), avoiding guest-triggered host RCU stalls.
+	 */

[Severity: High]
This isn't a bug introduced by this patch, but does this fix cover the same RCU stall vulnerability in the ITS command ring processing?

A guest can queue up to 32,768 MAPC commands to remap an existing collection, which vgic_its_process_commands() processes sequentially under cmd_lock without yielding. For each command, update_affinity_collection() loops over all ITEs:

arch/arm64/kvm/vgic/vgic-its.c:update_affinity_collection() {
	for_each_lpi_its(device, ite, its) {
		if (ite->collection != coll)
			continue;

		update_affinity_ite(kvm, ite);
	}
}

With a large number of ITEs, can this unmitigated loop still cause soft lockups and RCU stalls on the host?

arch/arm64/kvm/vgic/vgic-its.c static void vgic_its_free_device_list(struct kvm *kvm, struct vgic_its *its) · line 1145

Quoted 2 lines
arch/arm64/kvm/vgic/vgic-its.c +2 -0
+	for_each_lpi_its(device, ite, its)
+		ite->collection = NULL;

[Severity: Critical]
This is a pre-existing issue, but can setting ite->collection to NULL here cause a kernel panic during state saving?

If a guest clears GITS_BASER1 (triggering this teardown) or unmaps a collection via MAPC with valid=0, the ITEs are left in the device list with a NULL collection pointer.

Later, if host userspace triggers VM state saving, vgic_its_save_ite() blindly dereferences ite->collection:

arch/arm64/kvm/vgic/vgic-its.c:vgic_its_save_ite() {
	val = ((u64)next_offset << KVM_ITS_ITE_NEXT_SHIFT) |
	       ((u64)ite->irq->intid << KVM_ITS_ITE_PINTID_SHIFT) |
		ite->collection->collection_id;
}

Does vgic_its_save_ite() need to verify ite->collection is non-NULL before attempting to access its collection_id?

Quoted 6 lines
arch/arm64/kvm/vgic/vgic-its.c +5 -0
+
+	list_for_each_entry_safe(cur, temp, &its->collection_list, coll_list) {
+		list_del(&cur->coll_list);
+		kfree(cur);
+	}
 }
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
maintainer
#2 lore raw
In reply to Jing Zhang

[+Fuad, Steffen]

Jing,

Please make sure you add all the relevant reviewers in the Cc: list, specially as Fuad is doing a lot of work in that particular area.

Quoted 33 lines · Jing Zhang

When destroying the vgic-its collection list, vgic_its_free_collection_list() iterates over every collection and for each, calls vgic_its_free_collection(). This function walks every Interrupt Translation Entry (ITE) across all devices via for_each_lpi_its() to nullify the collection pointer.

A guest can allocate up to 65536 collections and hundreds of thousands of ITEs. By clearing GITS_CTLR.Enable and writing Valid=0 to GITS_BASER1, the guest can trigger this teardown path from a single MMIO exit. The resulting O(Collections * ITEs) nested loop executes billions of iterations without a single cond_resched(). This pins a physical CPU and stalls RCU grace periods for seconds or minutes on PREEMPT_NONE kernels.

Fix this by replacing the O(Collections * ITEs) teardown with an O(Collections + ITEs) pass. Since the entire collection list is being freed, we can safely bulk-clear the collection pointers from all ITEs in a single pass, and then free all the collections in a second pass.

---
 arch/arm64/kvm/vgic/vgic-its.c | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)
arch/arm64/kvm/vgic/vgic-its.c +0 -0
index 36ab3e4929154..a8e819fe97898 100644
@@ -1133,9 +1133,21 @@ static void vgic_its_free_device_list(struct kvm *kvm, struct vgic_its *its)
 static void vgic_its_free_collection_list(struct kvm *kvm, struct vgic_its *its)
 {
 	struct its_collection *cur, *temp;

arch/arm64/kvm/vgic/vgic-its.c static void vgic_its_free_device_list(struct kvm *kvm, struct vgic_its *its) · line 1143

Quoted 10 lines
arch/arm64/kvm/vgic/vgic-its.c +7 -2
+	struct its_device *device;
+	struct its_ite *ite;
 
-	list_for_each_entry_safe(cur, temp, &its->collection_list, coll_list)
-		vgic_its_free_collection(its, cur->collection_id);
+	/*
+	 * Bulk-clear the collection pointers for all ITEs.
+	 * This transforms the teardown complexity from O(Collections * ITEs)
+	 * to O(Collections + ITEs), avoiding guest-triggered host RCU stalls.
+	 */

I don't think this comment needs to describe this. You already have described it *extremely thoroughly* in the commit message, and that's probably enough. I'd rather see a justification of why this is *safe*.

arch/arm64/kvm/vgic/vgic-its.c static void vgic_its_free_device_list(struct kvm *kvm, struct vgic_its *its) · line 1150

Quoted 7 lines
arch/arm64/kvm/vgic/vgic-its.c +7 -0
+	for_each_lpi_its(device, ite, its)
+		ite->collection = NULL;
+
+	list_for_each_entry_safe(cur, temp, &its->collection_list, coll_list) {
+		list_del(&cur->coll_list);
+		kfree(cur);
+	}

The other thing that is missing is the invalidation of the translation cache. Please see the discussion at [1], and whether this needs to be taken care of here or in Fuad's series.

Thanks,

	M.

[1] https://lore.kernel.org/r/[email protected]

Signature · 1 line
Jazz isn't dead. It just smells funny.
author
#3 lore raw

Hi Faud,

Could you please include this patch in your series? I'll be out of office until the end of September.

Thanks,
Jing

Quoted 78 lines · Marc Zyngier

[+Fuad, Steffen]

Jing,

Please make sure you add all the relevant reviewers in the Cc: list, specially as Fuad is doing a lot of work in that particular area.

Quoted 33 lines · Jing Zhang

When destroying the vgic-its collection list, vgic_its_free_collection_list() iterates over every collection and for each, calls vgic_its_free_collection(). This function walks every Interrupt Translation Entry (ITE) across all devices via for_each_lpi_its() to nullify the collection pointer.

A guest can allocate up to 65536 collections and hundreds of thousands of ITEs. By clearing GITS_CTLR.Enable and writing Valid=0 to GITS_BASER1, the guest can trigger this teardown path from a single MMIO exit. The resulting O(Collections * ITEs) nested loop executes billions of iterations without a single cond_resched(). This pins a physical CPU and stalls RCU grace periods for seconds or minutes on PREEMPT_NONE kernels.

Fix this by replacing the O(Collections * ITEs) teardown with an O(Collections + ITEs) pass. Since the entire collection list is being freed, we can safely bulk-clear the collection pointers from all ITEs in a single pass, and then free all the collections in a second pass.

---
 arch/arm64/kvm/vgic/vgic-its.c | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)
arch/arm64/kvm/vgic/vgic-its.c +0 -0
index 36ab3e4929154..a8e819fe97898 100644
@@ -1133,9 +1133,21 @@ static void vgic_its_free_device_list(struct kvm *kvm, struct vgic_its *its)
 static void vgic_its_free_collection_list(struct kvm *kvm, struct vgic_its *its)
 {
      struct its_collection *cur, *temp;

arch/arm64/kvm/vgic/vgic-its.c static void vgic_its_free_device_list(struct kvm *kvm, struct vgic_its *its) · line 1143

Quoted 10 lines
arch/arm64/kvm/vgic/vgic-its.c +7 -2
+     struct its_device *device;
+     struct its_ite *ite;
 
-     list_for_each_entry_safe(cur, temp, &its->collection_list, coll_list)
-             vgic_its_free_collection(its, cur->collection_id);
+     /*
+      * Bulk-clear the collection pointers for all ITEs.
+      * This transforms the teardown complexity from O(Collections * ITEs)
+      * to O(Collections + ITEs), avoiding guest-triggered host RCU stalls.
+      */

I don't think this comment needs to describe this. You already have described it *extremely thoroughly* in the commit message, and that's probably enough. I'd rather see a justification of why this is *safe*.

arch/arm64/kvm/vgic/vgic-its.c static void vgic_its_free_device_list(struct kvm *kvm, struct vgic_its *its) · line 1150

Quoted 7 lines
arch/arm64/kvm/vgic/vgic-its.c +7 -0
+     for_each_lpi_its(device, ite, its)
+             ite->collection = NULL;
+
+     list_for_each_entry_safe(cur, temp, &its->collection_list, coll_list) {
+             list_del(&cur->coll_list);
+             kfree(cur);
+     }

The other thing that is missing is the invalidation of the translation cache. Please see the discussion at [1], and whether this needs to be taken care of here or in Fuad's series.

Thanks,

        M.

[1] https://lore.kernel.org/r/[email protected]

--
Jazz isn't dead. It just smells funny.