Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Like Xu <like.xu.linux@gmail.com>
To:     Alex Williamson <alex.williamson@redhat.com>,
        Paolo Bonzini <pbonzini@redhat.com>
Cc:     Zhu Lingshan <lingshan.zhu@intel.com>,
        linux-kernel@vger.kernel.org, kvm@vger.kernel.org
Subject: [PATCH] KVM: irqbypass: Convert producers/consumers single linked list to XArray
Date:   Tue,  1 Aug 2023 19:56:46 +0800
Message-ID: <20230801115646.33990-1-likexu@tencent.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

From: Like Xu <likexu@tencent.com>

Replace producers/consumers linked list with XArray. There are no changes
in functionality, but lookup performance has been improved.

The producers and consumers in current IRQ bypass manager are stored in
simple linked lists, and a single mutex is held while traversing the lists
and connecting a consumer to a producer (and vice versa). With this design
and implementation, if there are a large number of KVM agents concurrently
creating irqfds and all requesting to register their irqfds in the global
consumers list, the global mutex contention will exponentially increase
the avg wait latency, which is no longer tolerable in modern systems with
a large number of CPU cores. For example:

the wait time latency to acquire the mutex in a stress test where 174000
irqfds were created concurrently on an 2.70GHz ICX w/ 144 cores:

- avg = 117.855314 ms
- min = 20 ns
- max = 11428.340858 ms

To reduce latency introduced by the irq_bypass_register_consumer() in
the above usage scenario, the data structure XArray and its normal API
is applied to track the producers and consumers so that lookups don't
require a linear walk since the "tokens" used to match producers and
consumers are just kernel pointers.

Thanks to the nature of XArray (more memory-efficient, parallelisable
and cache friendly), the latecny is significantly reduced (compared to
list and hlist proposal) under the same environment and testing:

- avg = 314 ns
- min = 124 ns
- max = 47637 ns

In this conversion, the non-NULL opaque token to match between producer
and consumer () is used as the XArray index. The list_for_each_entry() is
replaced by xa_load(), and list_add/del() is replaced by xa_store/erase().
The list_head member for linked list is removed, along with comments.

Cc: Alex Williamson <alex.williamson@redhat.com>
Reported-by: Yong He <alexyonghe@tencent.com>
Closes: https://bugzilla.kernel.org/show_bug.cgi?id=217379
Suggested-by: Sean Christopherson <seanjc@google.com>
Suggested-by: Paolo Bonzini <pbonzini@redhat.com>
Signed-off-by: Like Xu <likexu@tencent.com>
---
Prerequisite:
- https://lore.kernel.org/kvm/20230801085408.69597-1-likexu@tencent.com
Test Requests:
- Please rant to me if it causes a negative impact on vdpa/vfio testing.
 include/linux/irqbypass.h |   8 +--
 virt/lib/irqbypass.c      | 123 +++++++++++++++++++-------------------
 2 files changed, 61 insertions(+), 70 deletions(-)

diff --git a/include/linux/irqbypass.h b/include/linux/irqbypass.h
index 9bdb2a781841..dbcc1b4d0ccf 100644
--- a/include/linux/irqbypass.h
+++ b/include/linux/irqbypass.h
@@ -8,14 +8,12 @@
 #ifndef IRQBYPASS_H
 #define IRQBYPASS_H
 
-#include <linux/list.h>
-
 struct irq_bypass_consumer;
 
 /*
  * Theory of operation
  *
- * The IRQ bypass manager is a simple set of lists and callbacks that allows
+ * The IRQ bypass manager is a simple set of xarrays and callbacks that allows
  * IRQ producers (ex. physical interrupt sources) to be matched to IRQ
  * consumers (ex. virtualization hardware that allows IRQ bypass or offload)
  * via a shared token (ex. eventfd_ctx).  Producers and consumers register
@@ -30,7 +28,6 @@ struct irq_bypass_consumer;
 
 /**
  * struct irq_bypass_producer - IRQ bypass producer definition
- * @node: IRQ bypass manager private list management
  * @token: opaque token to match between producer and consumer (non-NULL)
  * @irq: Linux IRQ number for the producer device
  * @add_consumer: Connect the IRQ producer to an IRQ consumer (optional)
@@ -43,7 +40,6 @@ struct irq_bypass_consumer;
  * for a physical device assigned to a VM.
  */
 struct irq_bypass_producer {
-	struct list_head node;
 	void *token;
 	int irq;
 	int (*add_consumer)(struct irq_bypass_producer *,
@@ -56,7 +52,6 @@ struct irq_bypass_producer {
 
 /**
  * struct irq_bypass_consumer - IRQ bypass consumer definition
- * @node: IRQ bypass manager private list management
  * @token: opaque token to match between producer and consumer (non-NULL)
  * @add_producer: Connect the IRQ consumer to an IRQ producer
  * @del_producer: Disconnect the IRQ consumer from an IRQ producer
@@ -69,7 +64,6 @@ struct irq_bypass_producer {
  * portions of the interrupt handling to the VM.
  */
 struct irq_bypass_consumer {
-	struct list_head node;
 	void *token;
 	int (*add_producer)(struct irq_bypass_consumer *,
 			    struct irq_bypass_producer *);
diff --git a/virt/lib/irqbypass.c b/virt/lib/irqbypass.c
index e0aabbbf27ec..78238c0fa83f 100644
--- a/virt/lib/irqbypass.c
+++ b/virt/lib/irqbypass.c
@@ -15,15 +15,15 @@
  */
 
 #include <linux/irqbypass.h>
-#include <linux/list.h>
 #include <linux/module.h>
 #include <linux/mutex.h>
+#include <linux/xarray.h>
 
 MODULE_LICENSE("GPL v2");
 MODULE_DESCRIPTION("IRQ bypass manager utility module");
 
-static LIST_HEAD(producers);
-static LIST_HEAD(consumers);
+static DEFINE_XARRAY(producers);
+static DEFINE_XARRAY(consumers);
 static DEFINE_MUTEX(lock);
 
 /* @lock must be held when calling connect */
@@ -78,11 +78,12 @@ static void __disconnect(struct irq_bypass_producer *prod,
  * irq_bypass_register_producer - register IRQ bypass producer
  * @producer: pointer to producer structure
  *
- * Add the provided IRQ producer to the list of producers and connect
- * with any matching token found on the IRQ consumers list.
+ * Add the provided IRQ producer to the xarray of producers and connect
+ * with any matching token found on the IRQ consumers xarray.
  */
 int irq_bypass_register_producer(struct irq_bypass_producer *producer)
 {
+	unsigned long token = (unsigned long)producer->token;
 	struct irq_bypass_producer *tmp;
 	struct irq_bypass_consumer *consumer;
 	int ret;
@@ -97,23 +98,22 @@ int irq_bypass_register_producer(struct irq_bypass_producer *producer)
 
 	mutex_lock(&lock);
 
-	list_for_each_entry(tmp, &producers, node) {
-		if (tmp->token == producer->token || tmp == producer) {
-			ret = -EBUSY;
+	tmp = xa_load(&producers, token);
+	if (tmp || tmp == producer) {
+		ret = -EBUSY;
+		goto out_err;
+	}
+
+	consumer = xa_load(&consumers, token);
+	if (consumer) {
+		ret = __connect(producer, consumer);
+		if (ret)
 			goto out_err;
-		}
 	}
 
-	list_for_each_entry(consumer, &consumers, node) {
-		if (consumer->token == producer->token) {
-			ret = __connect(producer, consumer);
-			if (ret)
-				goto out_err;
-			break;
-		}
-	}
-
-	list_add(&producer->node, &producers);
+	ret = xa_err(xa_store(&producers, token, producer, GFP_KERNEL));
+	if (ret)
+		goto out_err;
 
 	mutex_unlock(&lock);
 
@@ -129,11 +129,12 @@ EXPORT_SYMBOL_GPL(irq_bypass_register_producer);
  * irq_bypass_unregister_producer - unregister IRQ bypass producer
  * @producer: pointer to producer structure
  *
- * Remove a previously registered IRQ producer from the list of producers
+ * Remove a previously registered IRQ producer from the xarray of producers
  * and disconnect it from any connected IRQ consumer.
  */
 void irq_bypass_unregister_producer(struct irq_bypass_producer *producer)
 {
+	unsigned long token = (unsigned long)producer->token;
 	struct irq_bypass_producer *tmp;
 	struct irq_bypass_consumer *consumer;
 
@@ -143,24 +144,18 @@ void irq_bypass_unregister_producer(struct irq_bypass_producer *producer)
 	might_sleep();
 
 	if (!try_module_get(THIS_MODULE))
-		return; /* nothing in the list anyway */
+		return; /* nothing in the xarray anyway */
 
 	mutex_lock(&lock);
 
-	list_for_each_entry(tmp, &producers, node) {
-		if (tmp != producer)
-			continue;
+	tmp = xa_load(&producers, token);
+	if (tmp == producer) {
+		consumer = xa_load(&consumers, token);
+		if (consumer)
+			__disconnect(producer, consumer);
 
-		list_for_each_entry(consumer, &consumers, node) {
-			if (consumer->token == producer->token) {
-				__disconnect(producer, consumer);
-				break;
-			}
-		}
-
-		list_del(&producer->node);
+		xa_erase(&producers, token);
 		module_put(THIS_MODULE);
-		break;
 	}
 
 	mutex_unlock(&lock);
@@ -173,11 +168,12 @@ EXPORT_SYMBOL_GPL(irq_bypass_unregister_producer);
  * irq_bypass_register_consumer - register IRQ bypass consumer
  * @consumer: pointer to consumer structure
  *
- * Add the provided IRQ consumer to the list of consumers and connect
- * with any matching token found on the IRQ producer list.
+ * Add the provided IRQ consumer to the xarray of consumers and connect
+ * with any matching token found on the IRQ producer xarray.
  */
 int irq_bypass_register_consumer(struct irq_bypass_consumer *consumer)
 {
+	unsigned long token = (unsigned long)consumer->token;
 	struct irq_bypass_consumer *tmp;
 	struct irq_bypass_producer *producer;
 	int ret;
@@ -193,23 +189,22 @@ int irq_bypass_register_consumer(struct irq_bypass_consumer *consumer)
 
 	mutex_lock(&lock);
 
-	list_for_each_entry(tmp, &consumers, node) {
-		if (tmp->token == consumer->token || tmp == consumer) {
-			ret = -EBUSY;
+	tmp = xa_load(&consumers, token);
+	if (tmp || tmp == consumer) {
+		ret = -EBUSY;
+		goto out_err;
+	}
+
+	producer = xa_load(&producers, token);
+	if (producer) {
+		ret = __connect(producer, consumer);
+		if (ret)
 			goto out_err;
-		}
 	}
 
-	list_for_each_entry(producer, &producers, node) {
-		if (producer->token == consumer->token) {
-			ret = __connect(producer, consumer);
-			if (ret)
-				goto out_err;
-			break;
-		}
-	}
-
-	list_add(&consumer->node, &consumers);
+	ret = xa_err(xa_store(&consumers, token, consumer, GFP_KERNEL));
+	if (ret)
+		goto out_err;
 
 	mutex_unlock(&lock);
 
@@ -225,11 +220,12 @@ EXPORT_SYMBOL_GPL(irq_bypass_register_consumer);
  * irq_bypass_unregister_consumer - unregister IRQ bypass consumer
  * @consumer: pointer to consumer structure
  *
- * Remove a previously registered IRQ consumer from the list of consumers
+ * Remove a previously registered IRQ consumer from the xarray of consumers
  * and disconnect it from any connected IRQ producer.
  */
 void irq_bypass_unregister_consumer(struct irq_bypass_consumer *consumer)
 {
+	unsigned long token = (unsigned long)consumer->token;
 	struct irq_bypass_consumer *tmp;
 	struct irq_bypass_producer *producer;
 
@@ -239,24 +235,18 @@ void irq_bypass_unregister_consumer(struct irq_bypass_consumer *consumer)
 	might_sleep();
 
 	if (!try_module_get(THIS_MODULE))
-		return; /* nothing in the list anyway */
+		return; /* nothing in the xarray anyway */
 
 	mutex_lock(&lock);
 
-	list_for_each_entry(tmp, &consumers, node) {
-		if (tmp != consumer)
-			continue;
+	tmp = xa_load(&consumers, token);
+	if (tmp == consumer) {
+		producer = xa_load(&producers, token);
+		if (producer)
+			__disconnect(producer, consumer);
 
-		list_for_each_entry(producer, &producers, node) {
-			if (producer->token == consumer->token) {
-				__disconnect(producer, consumer);
-				break;
-			}
-		}
-
-		list_del(&consumer->node);
+		xa_erase(&consumers, token);
 		module_put(THIS_MODULE);
-		break;
 	}
 
 	mutex_unlock(&lock);
@@ -264,3 +254,10 @@ void irq_bypass_unregister_consumer(struct irq_bypass_consumer *consumer)
 	module_put(THIS_MODULE);
 }
 EXPORT_SYMBOL_GPL(irq_bypass_unregister_consumer);
+
+static void __exit irqbypass_exit(void)
+{
+	xa_destroy(&producers);
+	xa_destroy(&consumers);
+}
+module_exit(irqbypass_exit);

base-commit: b580148824057ef8e3cc3a459082ebcb99716880
-- 
2.41.0