KVM: arm64: vgic-its: Fix O(C*I) loop in vgic_its_free_collection_list
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
@@ -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
[email protected]
AI reviewThank 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@@ -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
Marc Zyngier
maintainer[+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, callsvgic_its_free_collection(). This function walks every Interrupt Translation Entry (ITE) across all devices viafor_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 resultingO(Collections * ITEs)nested loop executes billions of iterations without a singlecond_resched(). This pins a physical CPU and stalls RCU grace periods for seconds or minutes onPREEMPT_NONEkernels.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.Signed-off-by Jing Zhang <[email protected]>--- arch/arm64/kvm/vgic/vgic-its.c | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-)arch/arm64/kvm/vgic/vgic-its.c +0
-0@@ -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.
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, callsvgic_its_free_collection(). This function walks every Interrupt Translation Entry (ITE) across all devices viafor_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 resultingO(Collections * ITEs)nested loop executes billions of iterations without a singlecond_resched(). This pins a physical CPU and stalls RCU grace periods for seconds or minutes onPREEMPT_NONEkernels.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.Signed-off-by Jing Zhang <[email protected]>--- arch/arm64/kvm/vgic/vgic-its.c | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-)arch/arm64/kvm/vgic/vgic-its.c +0
-0@@ -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.