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