[PATCH v2] KVM: irqchip: KVM: Reduce allocation overhead in kvm_set_irq_routing()

[PATCH v2] KVM: irqchip: KVM: Reduce allocation overhead in kvm_set_irq_routing()

[Yanfei Xu]

In guests with many VFIO devices and MSI-X vectors, kvm_set_irq_routing()
becomes a high-overhead operation. Each invocation walks the entire IRQ
routing table and reallocates/frees every routing entry.

As the routing table grows on each call, entry allocation and freeing
dominate the execution time of this function. In scenarios such as VM
live migration or live upgrade, this behavior can introduce unnecessary
downtime.

Allocate memory for all routing entries in one shot using kcalloc(),
allowing them to be freed together with a single kfree() call.

Example: On a VM with 120 vCPUs and 15 VFIO devices (virtio-net), the
total number of calls to kzalloc and kfree is over 20000. With this
change, it is reduced to around 30.

Reported-by: Xiangfeng Cai <caixiangfeng@bytedance.com>
Signed-off-by: Yanfei Xu <yanfei.xu@bytedance.com>
---
v1->v2:
1. fix variable 'r' is used uninitialized when a 'if' condition is true 
2. simplified free_irq_routing_table() by removing the iteration over the
   entries and the hlist cleanup.

 include/linux/kvm_host.h |  1 +
 virt/kvm/irqchip.c       | 34 +++++++++++-----------------------
 2 files changed, 12 insertions(+), 23 deletions(-)

diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index d93f75b05ae2..cc27490bef4b 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -692,6 +692,7 @@ struct kvm_kernel_irq_routing_entry {
 struct kvm_irq_routing_table {
 	int chip[KVM_NR_IRQCHIPS][KVM_IRQCHIP_NUM_PINS];
 	u32 nr_rt_entries;
+	struct kvm_kernel_irq_routing_entry *entries_addr;
 	/*
 	 * Array indexed by gsi. Each entry contains list of irq chips
 	 * the gsi is connected to.
diff --git a/virt/kvm/irqchip.c b/virt/kvm/irqchip.c
index 6ccabfd32287..56779394033d 100644
--- a/virt/kvm/irqchip.c
+++ b/virt/kvm/irqchip.c
@@ -98,21 +98,10 @@ int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level,
 
 static void free_irq_routing_table(struct kvm_irq_routing_table *rt)
 {
-	int i;
-
 	if (!rt)
 		return;
 
-	for (i = 0; i < rt->nr_rt_entries; ++i) {
-		struct kvm_kernel_irq_routing_entry *e;
-		struct hlist_node *n;
-
-		hlist_for_each_entry_safe(e, n, &rt->map[i], link) {
-			hlist_del(&e->link);
-			kfree(e);
-		}
-	}
-
+	kfree(rt->entries_addr);
 	kfree(rt);
 }
 
@@ -186,6 +175,12 @@ int kvm_set_irq_routing(struct kvm *kvm,
 	new = kzalloc(struct_size(new, map, nr_rt_entries), GFP_KERNEL_ACCOUNT);
 	if (!new)
 		return -ENOMEM;
+	e = kcalloc(nr, sizeof(*e), GFP_KERNEL_ACCOUNT);
+	if (!e) {
+		r = -ENOMEM;
+		goto out;
+	}
+	new->entries_addr = e;
 
 	new->nr_rt_entries = nr_rt_entries;
 	for (i = 0; i < KVM_NR_IRQCHIPS; i++)
@@ -193,25 +188,20 @@ int kvm_set_irq_routing(struct kvm *kvm,
 			new->chip[i][j] = -1;
 
 	for (i = 0; i < nr; ++i) {
-		r = -ENOMEM;
-		e = kzalloc(sizeof(*e), GFP_KERNEL_ACCOUNT);
-		if (!e)
-			goto out;
-
 		r = -EINVAL;
 		switch (ue->type) {
 		case KVM_IRQ_ROUTING_MSI:
 			if (ue->flags & ~KVM_MSI_VALID_DEVID)
-				goto free_entry;
+				goto out;
 			break;
 		default:
 			if (ue->flags)
-				goto free_entry;
+				goto out;
 			break;
 		}
-		r = setup_routing_entry(kvm, new, e, ue);
+		r = setup_routing_entry(kvm, new, e + i, ue);
 		if (r)
-			goto free_entry;
+			goto out;
 		++ue;
 	}
 
@@ -228,8 +218,6 @@ int kvm_set_irq_routing(struct kvm *kvm,
 	r = 0;
 	goto out;
 
-free_entry:
-	kfree(e);
 out:
 	free_irq_routing_table(new);
 
-- 
2.20.1

Re: [PATCH v2] KVM: irqchip: KVM: Reduce allocation overhead in kvm_set_irq_routing()

[Yanfei Xu]

gentle ping :)

On 2025/12/26 14:27, Yanfei Xu wrote:
> In guests with many VFIO devices and MSI-X vectors, kvm_set_irq_routing()
> becomes a high-overhead operation. Each invocation walks the entire IRQ
> routing table and reallocates/frees every routing entry.
>
> As the routing table grows on each call, entry allocation and freeing
> dominate the execution time of this function. In scenarios such as VM
> live migration or live upgrade, this behavior can introduce unnecessary
> downtime.
>
> Allocate memory for all routing entries in one shot using kcalloc(),
> allowing them to be freed together with a single kfree() call.
>
> Example: On a VM with 120 vCPUs and 15 VFIO devices (virtio-net), the
> total number of calls to kzalloc and kfree is over 20000. With this
> change, it is reduced to around 30.
>
> Reported-by: Xiangfeng Cai <caixiangfeng@bytedance.com>
> Signed-off-by: Yanfei Xu <yanfei.xu@bytedance.com>
> ---
> v1->v2:
> 1. fix variable 'r' is used uninitialized when a 'if' condition is true
> 2. simplified free_irq_routing_table() by removing the iteration over the
>     entries and the hlist cleanup.
>
>   include/linux/kvm_host.h |  1 +
>   virt/kvm/irqchip.c       | 34 +++++++++++-----------------------
>   2 files changed, 12 insertions(+), 23 deletions(-)
>
> diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
> index d93f75b05ae2..cc27490bef4b 100644
> --- a/include/linux/kvm_host.h
> +++ b/include/linux/kvm_host.h
> @@ -692,6 +692,7 @@ struct kvm_kernel_irq_routing_entry {
>   struct kvm_irq_routing_table {
>   	int chip[KVM_NR_IRQCHIPS][KVM_IRQCHIP_NUM_PINS];
>   	u32 nr_rt_entries;
> +	struct kvm_kernel_irq_routing_entry *entries_addr;
>   	/*
>   	 * Array indexed by gsi. Each entry contains list of irq chips
>   	 * the gsi is connected to.
> diff --git a/virt/kvm/irqchip.c b/virt/kvm/irqchip.c
> index 6ccabfd32287..56779394033d 100644
> --- a/virt/kvm/irqchip.c
> +++ b/virt/kvm/irqchip.c
> @@ -98,21 +98,10 @@ int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level,
>   
>   static void free_irq_routing_table(struct kvm_irq_routing_table *rt)
>   {
> -	int i;
> -
>   	if (!rt)
>   		return;
>   
> -	for (i = 0; i < rt->nr_rt_entries; ++i) {
> -		struct kvm_kernel_irq_routing_entry *e;
> -		struct hlist_node *n;
> -
> -		hlist_for_each_entry_safe(e, n, &rt->map[i], link) {
> -			hlist_del(&e->link);
> -			kfree(e);
> -		}
> -	}
> -
> +	kfree(rt->entries_addr);
>   	kfree(rt);
>   }
>   
> @@ -186,6 +175,12 @@ int kvm_set_irq_routing(struct kvm *kvm,
>   	new = kzalloc(struct_size(new, map, nr_rt_entries), GFP_KERNEL_ACCOUNT);
>   	if (!new)
>   		return -ENOMEM;
> +	e = kcalloc(nr, sizeof(*e), GFP_KERNEL_ACCOUNT);
> +	if (!e) {
> +		r = -ENOMEM;
> +		goto out;
> +	}
> +	new->entries_addr = e;
>   
>   	new->nr_rt_entries = nr_rt_entries;
>   	for (i = 0; i < KVM_NR_IRQCHIPS; i++)
> @@ -193,25 +188,20 @@ int kvm_set_irq_routing(struct kvm *kvm,
>   			new->chip[i][j] = -1;
>   
>   	for (i = 0; i < nr; ++i) {
> -		r = -ENOMEM;
> -		e = kzalloc(sizeof(*e), GFP_KERNEL_ACCOUNT);
> -		if (!e)
> -			goto out;
> -
>   		r = -EINVAL;
>   		switch (ue->type) {
>   		case KVM_IRQ_ROUTING_MSI:
>   			if (ue->flags & ~KVM_MSI_VALID_DEVID)
> -				goto free_entry;
> +				goto out;
>   			break;
>   		default:
>   			if (ue->flags)
> -				goto free_entry;
> +				goto out;
>   			break;
>   		}
> -		r = setup_routing_entry(kvm, new, e, ue);
> +		r = setup_routing_entry(kvm, new, e + i, ue);
>   		if (r)
> -			goto free_entry;
> +			goto out;
>   		++ue;
>   	}
>   
> @@ -228,8 +218,6 @@ int kvm_set_irq_routing(struct kvm *kvm,
>   	r = 0;
>   	goto out;
>   
> -free_entry:
> -	kfree(e);
>   out:
>   	free_irq_routing_table(new);
>   

Re: [PATCH v2] KVM: irqchip: KVM: Reduce allocation overhead in kvm_set_irq_routing()

[Sean Christopherson]

On Fri, Dec 26, 2025, Yanfei Xu wrote:
> In guests with many VFIO devices and MSI-X vectors, kvm_set_irq_routing()
> becomes a high-overhead operation. Each invocation walks the entire IRQ
> routing table and reallocates/frees every routing entry.
> 
> As the routing table grows on each call, entry allocation and freeing
> dominate the execution time of this function. In scenarios such as VM
> live migration or live upgrade, this behavior can introduce unnecessary
> downtime.
> 
> Allocate memory for all routing entries in one shot using kcalloc(),
> allowing them to be freed together with a single kfree() call.
> 
> Example: On a VM with 120 vCPUs and 15 VFIO devices (virtio-net), the
> total number of calls to kzalloc and kfree is over 20000. With this
> change, it is reduced to around 30.

...

> @@ -186,6 +175,12 @@ int kvm_set_irq_routing(struct kvm *kvm,
>  	new = kzalloc(struct_size(new, map, nr_rt_entries), GFP_KERNEL_ACCOUNT);
>  	if (!new)
>  		return -ENOMEM;
> +	e = kcalloc(nr, sizeof(*e), GFP_KERNEL_ACCOUNT);

This needs to be a kv flavor of allocation, or maybe even just a "straight to
vmalloc'd" allocation.  With 20000+ allocations, that means an order-BIG allocations.
So kvzalloc_obj() or kvmalloc_objs()?

And if we're going to allocate one massive array, then we definitely should get
rid of:

	/*
	 * Array indexed by gsi. Each entry contains list of irq chips
	 * the gsi is connected to.
	 */
	struct hlist_head map[];

and kvm_kernel_irq_routing_entry.list.  It'd be easier and faster to have
setup_routing_entry() simply iterate over the array.

Something we should look at (on top of this), is caching the previous routing
table.  I.e. instead of freeing the old table, keep it around, and try to reuse
the old table on the next update.  That would allow eliding the alloc+free
entirely when userspace is changing routing, but not adding or removing entries.

Re: [PATCH v2] KVM: irqchip: KVM: Reduce allocation overhead in kvm_set_irq_routing()

[Yanfei Xu]

Hi Sean,

thanks for your review!

On 2026/5/16 02:52, Sean Christopherson wrote:
> On Fri, Dec 26, 2025, Yanfei Xu wrote:
>> In guests with many VFIO devices and MSI-X vectors, kvm_set_irq_routing()
>> becomes a high-overhead operation. Each invocation walks the entire IRQ
>> routing table and reallocates/frees every routing entry.
>>
>> As the routing table grows on each call, entry allocation and freeing
>> dominate the execution time of this function. In scenarios such as VM
>> live migration or live upgrade, this behavior can introduce unnecessary
>> downtime.
>>
>> Allocate memory for all routing entries in one shot using kcalloc(),
>> allowing them to be freed together with a single kfree() call.
>>
>> Example: On a VM with 120 vCPUs and 15 VFIO devices (virtio-net), the
>> total number of calls to kzalloc and kfree is over 20000. With this
>> change, it is reduced to around 30.
> ...
>
>> @@ -186,6 +175,12 @@ int kvm_set_irq_routing(struct kvm *kvm,
>>   	new = kzalloc(struct_size(new, map, nr_rt_entries), GFP_KERNEL_ACCOUNT);
>>   	if (!new)
>>   		return -ENOMEM;
>> +	e = kcalloc(nr, sizeof(*e), GFP_KERNEL_ACCOUNT);
> This needs to be a kv flavor of allocation, or maybe even just a "straight to
> vmalloc'd" allocation.  With 20000+ allocations, that means an order-BIG allocations.
> So kvzalloc_obj() or kvmalloc_objs()?

Agreed, will switch to kvzalloc_objs in v3

>
> And if we're going to allocate one massive array, then we definitely should get
> rid of:
>
> 	/*
> 	 * Array indexed by gsi. Each entry contains list of irq chips
> 	 * the gsi is connected to.
> 	 */
> 	struct hlist_head map[];
>
> and kvm_kernel_irq_routing_entry.list.  It'd be easier and faster to have
> setup_routing_entry() simply iterate over the array.

if we get rid of these, we need to add a new field to record the offset 
of entries
belonging to the same GSI. Compared to the hlist-based lookup, I am not sure
this would yield a clear gain. Seems hlist feels more straightforward?

>
> Something we should look at (on top of this), is caching the previous routing
> table.  I.e. instead of freeing the old table, keep it around, and try to reuse
> the old table on the next update.  That would allow eliding the alloc+free
> entirely when userspace is changing routing, but not adding or removing entries.

In our live-upgrade scenario, userspace incrementally adds entries via a 
large
number of KVM_SET_GSI_ROUTING ioctls, so the cost is dominated by the
cumulative overhead across tens of thousands of alloc/free pairs.

Per my observation, the per-call alloc/free overhead is fine; it's the 
cumulative
cost that hurts.

Thanks,
Yanfei

>

Re: [PATCH v2] KVM: irqchip: KVM: Reduce allocation overhead in kvm_set_irq_routing()

[Sean Christopherson]

On Mon, May 18, 2026, Yanfei Xu wrote:
> On 2026/5/16 02:52, Sean Christopherson wrote:
> > On Fri, Dec 26, 2025, Yanfei Xu wrote:
> > And if we're going to allocate one massive array, then we definitely should get
> > rid of:
> > 
> > 	/*
> > 	 * Array indexed by gsi. Each entry contains list of irq chips
> > 	 * the gsi is connected to.
> > 	 */
> > 	struct hlist_head map[];
> > 
> > and kvm_kernel_irq_routing_entry.list.  It'd be easier and faster to have
> > setup_routing_entry() simply iterate over the array.
> 
> if we get rid of these, we need to add a new field to record the offset of
> entries belonging to the same GSI. Compared to the hlist-based lookup, I am
> not sure this would yield a clear gain. Seems hlist feels more
> straightforward?

Gah, right, I was thinking the array was indexed by GSI, but it's indexed by the
arbitrary order provided by userspace.  And even ignoring the case where a GSI
has multiple routes, indexing by GSI would massively over-allocate if the routing
table is sparsely populated.

> > Something we should look at (on top of this), is caching the previous routing
> > table.  I.e. instead of freeing the old table, keep it around, and try to reuse
> > the old table on the next update.  That would allow eliding the alloc+free
> > entirely when userspace is changing routing, but not adding or removing entries.
> 
> In our live-upgrade scenario, userspace incrementally adds entries via a
> large number of KVM_SET_GSI_ROUTING ioctls, so the cost is dominated by the
> cumulative overhead across tens of thousands of alloc/free pairs.

Yes, but your live-upgrade scenario isn't the only thing KVM supports :-)

> Per my observation, the per-call alloc/free overhead is fine; it's the
> cumulative cost that hurts.

That might change with vmalloc'd memory, where tearing down the mappings requires
TLB shutdowns.  And as above, even if it's not a problem for _your_ scenario, the
overhead might be meaningful for other setups.  If we can cheaply/easily provide
meaningful performance benefits for such setups, then why not...

Re: [PATCH v2] KVM: irqchip: KVM: Reduce allocation overhead in kvm_set_irq_routing()

[Yanfei Xu]

On 2026/5/18 22:57, Sean Christopherson wrote:
> On Mon, May 18, 2026, Yanfei Xu wrote:
>> On 2026/5/16 02:52, Sean Christopherson wrote:
>>> On Fri, Dec 26, 2025, Yanfei Xu wrote:
>>> And if we're going to allocate one massive array, then we definitely should get
>>> rid of:
>>>
>>> 	/*
>>> 	 * Array indexed by gsi. Each entry contains list of irq chips
>>> 	 * the gsi is connected to.
>>> 	 */
>>> 	struct hlist_head map[];
>>>
>>> and kvm_kernel_irq_routing_entry.list.  It'd be easier and faster to have
>>> setup_routing_entry() simply iterate over the array.
>> if we get rid of these, we need to add a new field to record the offset of
>> entries belonging to the same GSI. Compared to the hlist-based lookup, I am
>> not sure this would yield a clear gain. Seems hlist feels more
>> straightforward?
> Gah, right, I was thinking the array was indexed by GSI, but it's indexed by the
> arbitrary order provided by userspace.  And even ignoring the case where a GSI
> has multiple routes, indexing by GSI would massively over-allocate if the routing
> table is sparsely populated.
>
>>> Something we should look at (on top of this), is caching the previous routing
>>> table.  I.e. instead of freeing the old table, keep it around, and try to reuse
>>> the old table on the next update.  That would allow eliding the alloc+free
>>> entirely when userspace is changing routing, but not adding or removing entries.
>> In our live-upgrade scenario, userspace incrementally adds entries via a
>> large number of KVM_SET_GSI_ROUTING ioctls, so the cost is dominated by the
>> cumulative overhead across tens of thousands of alloc/free pairs.
> Yes, but your live-upgrade scenario isn't the only thing KVM supports :-)
>
>> Per my observation, the per-call alloc/free overhead is fine; it's the
>> cumulative cost that hurts.
> That might change with vmalloc'd memory, where tearing down the mappings requires
> TLB shutdowns.  And as above, even if it's not a problem for _your_ scenario, the
> overhead might be meaningful for other setups.  If we can cheaply/easily provide
> meaningful performance benefits for such setups, then why not...

True... TLB shutdowns or buddy slowpath alloction hurts the 
performation. How about
the implementation like below? I think round up the size of cache to 
kmalloc bucket
size could significantly improve cache hit rate, especially when falling 
back to vmalloc

diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index a8d74b25c5cf..54d9641e2b52 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -694,6 +694,7 @@ struct kvm_irq_routing_table {
         int chip[KVM_NR_IRQCHIPS][KVM_IRQCHIP_NUM_PINS];
         u32 nr_rt_entries;
         struct kvm_kernel_irq_routing_entry *entries;
+       size_t entries_size;
         /*
          * Array indexed by gsi. Each entry contains list of irq chips
          * the gsi is connected to.
@@ -845,6 +846,11 @@ struct kvm {
          * Update side is protected by irq_lock.
          */
         struct kvm_irq_routing_table __rcu *irq_routing;
+       /*
+        * Cache for the entries[] allocation of a freed IRQ routing table.
+        */
+       struct kvm_kernel_irq_routing_entry *irq_routing_entries_cache;
+       size_t irq_routing_entries_cache_size;

         struct hlist_head irq_ack_notifier_list;
  #endif
diff --git a/virt/kvm/irqchip.c b/virt/kvm/irqchip.c
index b78f113af4ea..4b6c2e1a23ff 100644
--- a/virt/kvm/irqchip.c
+++ b/virt/kvm/irqchip.c
@@ -96,12 +96,57 @@ int kvm_set_irq(struct kvm *kvm, int irq_source_id, 
u32 irq, int level,
         return ret;
  }

-static void free_irq_routing_table(struct kvm_irq_routing_table *rt)
+static struct kvm_kernel_irq_routing_entry *
+kvm_get_irq_routing_entries_cache(struct kvm *kvm, size_t alloc_size)
  {
+       struct kvm_kernel_irq_routing_entry *entries = NULL;
+       struct kvm_kernel_irq_routing_entry *cache = NULL;
+
+       /*
+        * Reuse cached entries[] only for an exact allocation-size match.
+        */
+       mutex_lock(&kvm->irq_lock);
+       if (kvm->irq_routing_entries_cache_size == alloc_size &&
+           kvm->irq_routing_entries_cache) {
+               entries = kvm->irq_routing_entries_cache;
+               kvm->irq_routing_entries_cache = NULL;
+               kvm->irq_routing_entries_cache_size = 0;
+       } else if (kvm->irq_routing_entries_cache) {
+               cache = kvm->irq_routing_entries_cache;
+               kvm->irq_routing_entries_cache = NULL;
+               kvm->irq_routing_entries_cache_size = 0;
+       }
+       mutex_unlock(&kvm->irq_lock);
+
+       kvfree(cache);
+       if (entries)
+               memset(entries, 0, alloc_size);
+
+       return entries;
+}
+
+static void free_irq_routing_table(struct kvm *kvm,
+                                  struct kvm_irq_routing_table *rt)
+{
+       struct kvm_kernel_irq_routing_entry *entries;
+
         if (!rt)
                 return;

-       kvfree(rt->entries);
+       entries = rt->entries;
+       if (kvm && !ZERO_OR_NULL_PTR(entries)) {
+               mutex_lock(&kvm->irq_lock);
+               if (!kvm->irq_routing_entries_cache) {
+                       kvm->irq_routing_entries_cache = entries;
+                       kvm->irq_routing_entries_cache_size = 
rt->entries_size;
+                       entries = NULL;
+               }
+               mutex_unlock(&kvm->irq_lock);
+
+               kvfree(entries);
+       } else {
+               kvfree(entries);
+       }
         kfree(rt);
  }

@@ -110,7 +155,10 @@ void kvm_free_irq_routing(struct kvm *kvm)
         /* Called only during vm destruction. Nobody can use the pointer
            at this stage */
         struct kvm_irq_routing_table *rt = 
rcu_access_pointer(kvm->irq_routing);
-       free_irq_routing_table(rt);
+       free_irq_routing_table(NULL, rt);
+       kvfree(kvm->irq_routing_entries_cache);
+       kvm->irq_routing_entries_cache = NULL;
+       kvm->irq_routing_entries_cache_size = 0;
  }

  static int setup_routing_entry(struct kvm *kvm,
@@ -161,6 +209,7 @@ int kvm_set_irq_routing(struct kvm *kvm,
  {
         struct kvm_irq_routing_table *new, *old;
         struct kvm_kernel_irq_routing_entry *e;
+       size_t alloc_size;
         u32 i, j, nr_rt_entries = 0;
         int r;

@@ -176,12 +225,16 @@ int kvm_set_irq_routing(struct kvm *kvm,
         if (!new)
                 return -ENOMEM;

-       e = kvzalloc_objs(*e, nr, GFP_KERNEL_ACCOUNT);
+       alloc_size = kmalloc_size_roundup(size_mul(sizeof(*e), nr));
+       e = kvm_get_irq_routing_entries_cache(kvm, alloc_size);
+       if (!e)
+               e = kvzalloc(alloc_size, GFP_KERNEL_ACCOUNT);
         if (!e) {
                 r = -ENOMEM;
                 goto out;
         }
         new->entries = e;
+       new->entries_size = alloc_size;

         new->nr_rt_entries = nr_rt_entries;
         for (i = 0; i < KVM_NR_IRQCHIPS; i++)
@@ -218,7 +271,7 @@ int kvm_set_irq_routing(struct kvm *kvm,
         new = old;
         r = 0;
  out:
-       free_irq_routing_table(new);
+       free_irq_routing_table(kvm, new);

         return r;
  }