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

[Marc Zyngier <maz@kernel.org>]

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