[PATCH] KVM: irqchip: allocate routing entries in chunks

[PATCH] KVM: irqchip: allocate routing entries in chunks

[lirongqing]

From: Li RongQing <lirongqing@baidu.com>

kvm_set_irq_routing() allocates each routing entry separately, so
a routing table with thousands of GSIs needs thousands of small
allocations and frees, adding significant allocator overhead.

Allocate the entries in chunks instead: each chunk holds up to
PAGE_SIZE / sizeof(struct kvm_kernel_irq_routing_entry) entries, and
the chunk pointers are kept in the routing table so that all entries
are freed together when the table is released.

Each chunk is capped at PAGE_SIZE instead of allocating one array for
the whole table: with nr up to KVM_MAX_IRQ_ROUTES (4096), a single array
would be a multi-page contiguous request, which is what tends to fail
once memory is fragmented. Page-sized chunks stay on the normal kmalloc
path, and a failed allocation only costs one chunk. The chunk pointer
array uses kvzalloc_objs() and can fall back to vmalloc.

The last chunk is sized to the number of entries actually left, so a
table smaller than one chunk - the common case - allocates only what it
needs.

Measured with an eBPF probe on kvm_set_irq_routing() on an Intel EMR CPU:
when a VM has a 2000+ entry routing table, the time spent in the function
drops from about 700us to about 300us.

Signed-off-by: Li RongQing <lirongqing@baidu.com>
---
 include/linux/kvm_host.h |  2 ++
 virt/kvm/irqchip.c       | 62 +++++++++++++++++++++++++++++++++++++++---------
 2 files changed, 53 insertions(+), 11 deletions(-)

diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
index 03bfc92..83848d7 100644
--- a/include/linux/kvm_host.h
+++ b/include/linux/kvm_host.h
@@ -693,6 +693,8 @@ struct kvm_kernel_irq_routing_entry {
 struct kvm_irq_routing_table {
 	int chip[KVM_NR_IRQCHIPS][KVM_IRQCHIP_NUM_PINS];
 	u32 nr_rt_entries;
+	u32 nr_entry_chunks;
+	struct kvm_kernel_irq_routing_entry **entry_chunks;
 	/*
 	 * 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 462c706..044b831 100644
--- a/virt/kvm/irqchip.c
+++ b/virt/kvm/irqchip.c
@@ -18,6 +18,9 @@
 #include <linux/export.h>
 #include <trace/events/kvm.h>
 
+#define KVM_IRQ_ROUTING_ENTRIES_PER_CHUNK	\
+	(PAGE_SIZE / sizeof(struct kvm_kernel_irq_routing_entry))
+
 int kvm_irq_map_gsi(struct kvm *kvm,
 		    struct kvm_kernel_irq_routing_entry *entries, int gsi)
 {
@@ -107,12 +110,14 @@ static void free_irq_routing_table(struct kvm_irq_routing_table *rt)
 		struct kvm_kernel_irq_routing_entry *e;
 		struct hlist_node *n;
 
-		hlist_for_each_entry_safe(e, n, &rt->map[i], link) {
+		hlist_for_each_entry_safe(e, n, &rt->map[i], link)
 			hlist_del(&e->link);
-			kfree(e);
-		}
 	}
 
+	for (i = 0; i < rt->nr_entry_chunks; ++i)
+		kfree(rt->entry_chunks[i]);
+	kvfree(rt->entry_chunks);
+
 	kfree(rt);
 }
 
@@ -170,9 +175,11 @@ int kvm_set_irq_routing(struct kvm *kvm,
 			unsigned nr,
 			unsigned flags)
 {
+	struct kvm_kernel_irq_routing_entry **chunks = NULL;
 	struct kvm_irq_routing_table *new, *old;
 	struct kvm_kernel_irq_routing_entry *e;
 	u32 i, j, nr_rt_entries = 0;
+	u32 nr_chunks;
 	int r;
 
 	for (i = 0; i < nr; ++i) {
@@ -183,6 +190,13 @@ int kvm_set_irq_routing(struct kvm *kvm,
 
 	nr_rt_entries += 1;
 
+	/*
+	 * The chunks hold the routing entries, so they are sized by the number
+	 * of entries passed in by the caller, not by nr_rt_entries, which is
+	 * the size of the GSI map.
+	 */
+	nr_chunks = DIV_ROUND_UP(nr, KVM_IRQ_ROUTING_ENTRIES_PER_CHUNK);
+
 	new = kzalloc_flex(*new, map, nr_rt_entries, GFP_KERNEL_ACCOUNT);
 	if (!new)
 		return -ENOMEM;
@@ -192,26 +206,54 @@ int kvm_set_irq_routing(struct kvm *kvm,
 		for (j = 0; j < KVM_IRQCHIP_NUM_PINS; j++)
 			new->chip[i][j] = -1;
 
+	r = -ENOMEM;
+	if (nr_chunks) {
+		chunks = kvzalloc_objs(*chunks, nr_chunks, GFP_KERNEL_ACCOUNT);
+		if (!chunks)
+			goto out;
+
+		new->entry_chunks = chunks;
+		new->nr_entry_chunks = nr_chunks;
+	}
+
 	for (i = 0; i < nr; ++i) {
+		u32 idx = i / KVM_IRQ_ROUTING_ENTRIES_PER_CHUNK;
+		u32 off = i % KVM_IRQ_ROUTING_ENTRIES_PER_CHUNK;
+
 		r = -ENOMEM;
-		e = kzalloc_obj(*e, GFP_KERNEL_ACCOUNT);
-		if (!e)
-			goto out;
+		if (!chunks[idx]) {
+			struct kvm_kernel_irq_routing_entry *chunk;
+			/*
+			 * A chunk is only entered at its first entry, so nr - i
+			 * is the number of entries left for this chunk; the last
+			 * chunk is short.
+			 */
+			u32 cnt = min_t(u32, nr - i,
+					KVM_IRQ_ROUTING_ENTRIES_PER_CHUNK);
+
+			chunk = kzalloc_objs(*chunk, cnt, GFP_KERNEL_ACCOUNT);
+			if (!chunk)
+				goto out;
+
+			chunks[idx] = chunk;
+		}
+
+		e = chunks[idx] + off;
 
 		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);
 		if (r)
-			goto free_entry;
+			goto out;
 		++ue;
 	}
 
@@ -228,8 +270,6 @@ int kvm_set_irq_routing(struct kvm *kvm,
 	r = 0;
 	goto out;
 
-free_entry:
-	kfree(e);
 out:
 	free_irq_routing_table(new);
 
-- 
2.9.4

Re: [PATCH] KVM: irqchip: allocate routing entries in chunks

[Sean Christopherson]

+Yanfei

On Tue, Sep 08, 2026, lirongqing wrote:
> From: Li RongQing <lirongqing@baidu.com>
> 
> kvm_set_irq_routing() allocates each routing entry separately, so
> a routing table with thousands of GSIs needs thousands of small
> allocations and frees, adding significant allocator overhead.
> 
> Allocate the entries in chunks instead: each chunk holds up to
> PAGE_SIZE / sizeof(struct kvm_kernel_irq_routing_entry) entries, and
> the chunk pointers are kept in the routing table so that all entries
> are freed together when the table is released.
> 
> Each chunk is capped at PAGE_SIZE instead of allocating one array for
> the whole table: with nr up to KVM_MAX_IRQ_ROUTES (4096), a single array
> would be a multi-page contiguous request, which is what tends to fail
> once memory is fragmented. Page-sized chunks stay on the normal kmalloc
> path, and a failed allocation only costs one chunk. The chunk pointer
> array uses kvzalloc_objs() and can fall back to vmalloc.
> 
> The last chunk is sized to the number of entries actually left, so a
> table smaller than one chunk - the common case - allocates only what it
> needs.

Please look at Yanfei's series and help come to an agreement on how best to fix
this.  I am trying to get to Yanfei's series, and normally would take a close
look at both, but I am extremely short on cycles at the moment.

https://lore.kernel.org/all/20260525035242.107264-1-yanfei.xu@bytedance.com

> 
> Measured with an eBPF probe on kvm_set_irq_routing() on an Intel EMR CPU:
> when a VM has a 2000+ entry routing table, the time spent in the function
> drops from about 700us to about 300us.
> 
> Signed-off-by: Li RongQing <lirongqing@baidu.com>
> ---
>  include/linux/kvm_host.h |  2 ++
>  virt/kvm/irqchip.c       | 62 +++++++++++++++++++++++++++++++++++++++---------
>  2 files changed, 53 insertions(+), 11 deletions(-)
> 
> diff --git a/include/linux/kvm_host.h b/include/linux/kvm_host.h
> index 03bfc92..83848d7 100644
> --- a/include/linux/kvm_host.h
> +++ b/include/linux/kvm_host.h
> @@ -693,6 +693,8 @@ struct kvm_kernel_irq_routing_entry {
>  struct kvm_irq_routing_table {
>  	int chip[KVM_NR_IRQCHIPS][KVM_IRQCHIP_NUM_PINS];
>  	u32 nr_rt_entries;
> +	u32 nr_entry_chunks;
> +	struct kvm_kernel_irq_routing_entry **entry_chunks;
>  	/*
>  	 * 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 462c706..044b831 100644
> --- a/virt/kvm/irqchip.c
> +++ b/virt/kvm/irqchip.c
> @@ -18,6 +18,9 @@
>  #include <linux/export.h>
>  #include <trace/events/kvm.h>
>  
> +#define KVM_IRQ_ROUTING_ENTRIES_PER_CHUNK	\
> +	(PAGE_SIZE / sizeof(struct kvm_kernel_irq_routing_entry))
> +
>  int kvm_irq_map_gsi(struct kvm *kvm,
>  		    struct kvm_kernel_irq_routing_entry *entries, int gsi)
>  {
> @@ -107,12 +110,14 @@ static void free_irq_routing_table(struct kvm_irq_routing_table *rt)
>  		struct kvm_kernel_irq_routing_entry *e;
>  		struct hlist_node *n;
>  
> -		hlist_for_each_entry_safe(e, n, &rt->map[i], link) {
> +		hlist_for_each_entry_safe(e, n, &rt->map[i], link)
>  			hlist_del(&e->link);
> -			kfree(e);
> -		}
>  	}
>  
> +	for (i = 0; i < rt->nr_entry_chunks; ++i)
> +		kfree(rt->entry_chunks[i]);
> +	kvfree(rt->entry_chunks);
> +
>  	kfree(rt);
>  }
>  
> @@ -170,9 +175,11 @@ int kvm_set_irq_routing(struct kvm *kvm,
>  			unsigned nr,
>  			unsigned flags)
>  {
> +	struct kvm_kernel_irq_routing_entry **chunks = NULL;
>  	struct kvm_irq_routing_table *new, *old;
>  	struct kvm_kernel_irq_routing_entry *e;
>  	u32 i, j, nr_rt_entries = 0;
> +	u32 nr_chunks;
>  	int r;
>  
>  	for (i = 0; i < nr; ++i) {
> @@ -183,6 +190,13 @@ int kvm_set_irq_routing(struct kvm *kvm,
>  
>  	nr_rt_entries += 1;
>  
> +	/*
> +	 * The chunks hold the routing entries, so they are sized by the number
> +	 * of entries passed in by the caller, not by nr_rt_entries, which is
> +	 * the size of the GSI map.
> +	 */
> +	nr_chunks = DIV_ROUND_UP(nr, KVM_IRQ_ROUTING_ENTRIES_PER_CHUNK);
> +
>  	new = kzalloc_flex(*new, map, nr_rt_entries, GFP_KERNEL_ACCOUNT);
>  	if (!new)
>  		return -ENOMEM;
> @@ -192,26 +206,54 @@ int kvm_set_irq_routing(struct kvm *kvm,
>  		for (j = 0; j < KVM_IRQCHIP_NUM_PINS; j++)
>  			new->chip[i][j] = -1;
>  
> +	r = -ENOMEM;
> +	if (nr_chunks) {
> +		chunks = kvzalloc_objs(*chunks, nr_chunks, GFP_KERNEL_ACCOUNT);
> +		if (!chunks)
> +			goto out;
> +
> +		new->entry_chunks = chunks;
> +		new->nr_entry_chunks = nr_chunks;
> +	}
> +
>  	for (i = 0; i < nr; ++i) {
> +		u32 idx = i / KVM_IRQ_ROUTING_ENTRIES_PER_CHUNK;
> +		u32 off = i % KVM_IRQ_ROUTING_ENTRIES_PER_CHUNK;
> +
>  		r = -ENOMEM;
> -		e = kzalloc_obj(*e, GFP_KERNEL_ACCOUNT);
> -		if (!e)
> -			goto out;
> +		if (!chunks[idx]) {
> +			struct kvm_kernel_irq_routing_entry *chunk;
> +			/*
> +			 * A chunk is only entered at its first entry, so nr - i
> +			 * is the number of entries left for this chunk; the last
> +			 * chunk is short.
> +			 */
> +			u32 cnt = min_t(u32, nr - i,
> +					KVM_IRQ_ROUTING_ENTRIES_PER_CHUNK);
> +
> +			chunk = kzalloc_objs(*chunk, cnt, GFP_KERNEL_ACCOUNT);
> +			if (!chunk)
> +				goto out;
> +
> +			chunks[idx] = chunk;
> +		}
> +
> +		e = chunks[idx] + off;
>  
>  		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);
>  		if (r)
> -			goto free_entry;
> +			goto out;
>  		++ue;
>  	}
>  
> @@ -228,8 +270,6 @@ int kvm_set_irq_routing(struct kvm *kvm,
>  	r = 0;
>  	goto out;
>  
> -free_entry:
> -	kfree(e);
>  out:
>  	free_irq_routing_table(new);
>  
> -- 
> 2.9.4
> 

答复: [????] Re: [PATCH] KVM: irqchip: allocate routing entries in chunks

[Li,Rongqing]

> Please look at Yanfei's series and help come to an agreement on how best to fix
> this.  I am trying to get to Yanfei's series, and normally would take a close look
> at both, but I am extremely short on cycles at the moment.
> 
> https://lore.kernel.org/all/20260525035242.107264-1-yanfei.xu@bytedance.
> com
> 
Hi Sean,

Thanks for pointing me to Yanfei's series. I agree that both approaches
aim to reduce the allocation overhead in KVM_SET_GSI_ROUTING().

One main concern with using kvalloc() for the entire routing entry array is
that, under severe memory fragmentation, it may fall back to vmalloc().
The vmalloc() path can have relatively high and less predictable overhead,
especially when routing tables are updated frequently when guest OS is
running irqbalance.

Thanks
[Li,Rongqing]