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

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

[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.

Signed-off-by: Jing Zhang <jingzhangos@google.com>
---
 arch/arm64/kvm/vgic/vgic-its.c | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index 36ab3e4929154..a8e819fe97898 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -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 */
-- 
2.55.0.737.g08866a6d13-goog

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

[sashiko-bot]

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 <jingzhangos@google.com>

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.

[ ... ]

> diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
> index 4477f870c7b36..5e907a34226e3 100644
> --- a/arch/arm64/kvm/vgic/vgic-its.c
> +++ b/arch/arm64/kvm/vgic/vgic-its.c
> @@ -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;
> +	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?

> +	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?

> +
> +	list_for_each_entry_safe(cur, temp, &its->collection_list, coll_list) {
> +		list_del(&cur->coll_list);
> +		kfree(cur);
> +	}
>  }

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260818223422.367803-1-jingzhangos@google.com?part=1

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

[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.

On Tue, 18 Aug 2026 23:34:22 +0100,
Jing Zhang <jingzhangos@google.com> wrote:
> 
> 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.
> 
> Signed-off-by: Jing Zhang <jingzhangos@google.com>
> ---
>  arch/arm64/kvm/vgic/vgic-its.c | 16 ++++++++++++++--
>  1 file changed, 14 insertions(+), 2 deletions(-)
> 
> diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
> index 36ab3e4929154..a8e819fe97898 100644
> --- a/arch/arm64/kvm/vgic/vgic-its.c
> +++ b/arch/arm64/kvm/vgic/vgic-its.c
> @@ -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.
> +	 */

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*.

> +	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/20260819102809.310708-2-fuad.tabba@linux.dev

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

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

[Jing Zhang]

Hi Faud,

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

Thanks,
Jing

On Thu, Aug 20, 2026 at 6:08 AM Marc Zyngier <maz@kernel.org> wrote:
>
> [+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.
>
> On Tue, 18 Aug 2026 23:34:22 +0100,
> Jing Zhang <jingzhangos@google.com> wrote:
> >
> > 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.
> >
> > Signed-off-by: Jing Zhang <jingzhangos@google.com>
> > ---
> >  arch/arm64/kvm/vgic/vgic-its.c | 16 ++++++++++++++--
> >  1 file changed, 14 insertions(+), 2 deletions(-)
> >
> > diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
> > index 36ab3e4929154..a8e819fe97898 100644
> > --- a/arch/arm64/kvm/vgic/vgic-its.c
> > +++ b/arch/arm64/kvm/vgic/vgic-its.c
> > @@ -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.
> > +      */
>
> 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*.
>
> > +     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/20260819102809.310708-2-fuad.tabba@linux.dev
>
> --
> Jazz isn't dead. It just smells funny.