From:   "Longpeng(Mike)" <longpeng2@huawei.com>
To:     <pbonzini@redhat.com>, <alex.williamson@redhat.com>,
        <mst@redhat.com>, <jasowang@redhat.com>
CC:     <linux-kernel@vger.kernel.org>, <kvm@vger.kernel.org>,
        <eperezma@redhat.com>, <arei.gonglei@huawei.com>,
        <yechuan@huawei.com>, Longpeng <longpeng2@huawei.com>
Subject: [PATCH] irqbypass: convert producers/consumers single linked list to hlist
Date:   Wed, 1 Mar 2023 10:18:30 +0800
Message-ID: <20230301021830.880-1-longpeng2@huawei.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 7BIT
Content-Type:   text/plain; charset=US-ASCII
Precedence: bulk

From: Longpeng <longpeng2@huawei.com>

There are no functional changes, but this converts the producers/consumers
single linked list to a hash list. This can speed up the lookup if the VM
has many irqfds.

This can save about 15ms when assigning all IRQFS to a QEMU/KVM VM with 1K
irqfds. The overhead would be higher if there were much more irqfds in the
HOST.

Signed-off-by: Longpeng <longpeng2@huawei.com>
---
 include/linux/irqbypass.h |   8 +--
 virt/lib/irqbypass.c      | 131 ++++++++++++++++++++++++--------------
 2 files changed, 86 insertions(+), 53 deletions(-)

diff --git a/include/linux/irqbypass.h b/include/linux/irqbypass.h
index 9bdb2a781841..9039b5f6218d 100644
--- a/include/linux/irqbypass.h
+++ b/include/linux/irqbypass.h
@@ -30,7 +30,7 @@ struct irq_bypass_consumer;
 
 /**
  * struct irq_bypass_producer - IRQ bypass producer definition
- * @node: IRQ bypass manager private list management
+ * @node: IRQ bypass manager private hash 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 +43,7 @@ struct irq_bypass_consumer;
  * for a physical device assigned to a VM.
  */
 struct irq_bypass_producer {
-	struct list_head node;
+	struct hlist_node node;
 	void *token;
 	int irq;
 	int (*add_consumer)(struct irq_bypass_producer *,
@@ -56,7 +56,7 @@ struct irq_bypass_producer {
 
 /**
  * struct irq_bypass_consumer - IRQ bypass consumer definition
- * @node: IRQ bypass manager private list management
+ * @node: IRQ bypass manager private hash 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 +69,7 @@ struct irq_bypass_producer {
  * portions of the interrupt handling to the VM.
  */
 struct irq_bypass_consumer {
-	struct list_head node;
+	struct hlist_node 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 28fda42e471b..8096d2daab01 100644
--- a/virt/lib/irqbypass.c
+++ b/virt/lib/irqbypass.c
@@ -18,14 +18,59 @@
 #include <linux/list.h>
 #include <linux/module.h>
 #include <linux/mutex.h>
+#include <linux/hashtable.h>
 
 MODULE_LICENSE("GPL v2");
 MODULE_DESCRIPTION("IRQ bypass manager utility module");
 
-static LIST_HEAD(producers);
-static LIST_HEAD(consumers);
+/*
+ * hash table for produces/consumers. This improve the performace to find
+ * an existing producer/consumer.
+ */
+#define PRODUCERS_HASH_BITS	9
+#define CONSUMERS_HASH_BITS	9
+static DEFINE_HASHTABLE(producers, PRODUCERS_HASH_BITS);
+static DEFINE_HASHTABLE(consumers, CONSUMERS_HASH_BITS);
 static DEFINE_MUTEX(lock);
 
+
+/* @lock must be held */
+static struct irq_bypass_producer *find_producer_by_token(void *token)
+{
+	struct irq_bypass_producer *producer;
+
+	hash_for_each_possible(producers, producer, node, (uint64_t)token)
+		if (producer->token == token)
+			return producer;
+
+	return NULL;
+}
+
+/* @lock must be held */
+static struct irq_bypass_consumer *find_consumer_by_token(void *token)
+{
+	struct irq_bypass_consumer *consumer;
+
+	hash_for_each_possible(producers, consumer, node, (uint64_t)token)
+		if (consumer->token == token)
+			return consumer;
+
+	return NULL;
+}
+
+/* @lock must be held */
+static bool has_consumer(struct irq_bypass_consumer *consumer)
+{
+	struct irq_bypass_consumer *tmp;
+	int bkt;
+
+	hash_for_each(consumers, bkt, tmp, node)
+		if (tmp == consumer)
+			return true;
+
+	return false;
+}
+
 /* @lock must be held when calling connect */
 static int __connect(struct irq_bypass_producer *prod,
 		     struct irq_bypass_consumer *cons)
@@ -97,23 +142,20 @@ 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) {
-			ret = -EBUSY;
-			goto out_err;
-		}
+	tmp = find_producer_by_token(producer->token);
+	if (tmp) {
+		ret = -EBUSY;
+		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;
-		}
+	consumer = find_consumer_by_token(producer->token);
+	if (consumer) {
+		ret = __connect(producer, consumer);
+		if (ret)
+			goto out_err;
 	}
 
-	list_add(&producer->node, &producers);
+	hash_add(producers, &producer->node, (uint64_t)producer->token);
 
 	mutex_unlock(&lock);
 
@@ -147,22 +189,18 @@ void irq_bypass_unregister_producer(struct irq_bypass_producer *producer)
 
 	mutex_lock(&lock);
 
-	list_for_each_entry(tmp, &producers, node) {
-		if (tmp->token != producer->token)
-			continue;
+	tmp = find_producer_by_token(producer->token);
+	if (!tmp)
+		goto out;
 
-		list_for_each_entry(consumer, &consumers, node) {
-			if (consumer->token == producer->token) {
-				__disconnect(producer, consumer);
-				break;
-			}
-		}
+	consumer = find_consumer_by_token(producer->token);
+	if (consumer)
+		__disconnect(producer, consumer);
 
-		list_del(&producer->node);
-		module_put(THIS_MODULE);
-		break;
-	}
+	hash_del(&producer->node);
+	module_put(THIS_MODULE);
 
+out:
 	mutex_unlock(&lock);
 
 	module_put(THIS_MODULE);
@@ -193,23 +231,20 @@ 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;
-			goto out_err;
-		}
+	tmp = find_consumer_by_token(consumer->token);
+	if (tmp || has_consumer(consumer)) {
+		ret = -EBUSY;
+		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;
-		}
+	producer = find_producer_by_token(consumer->token);
+	if (producer) {
+		ret = __connect(producer, consumer);
+		if (ret)
+			goto out_err;
 	}
 
-	list_add(&consumer->node, &consumers);
+	hash_add(consumers, &consumer->node, (uint64_t)consumer->token);
 
 	mutex_unlock(&lock);
 
@@ -232,6 +267,7 @@ void irq_bypass_unregister_consumer(struct irq_bypass_consumer *consumer)
 {
 	struct irq_bypass_consumer *tmp;
 	struct irq_bypass_producer *producer;
+	int bkt;
 
 	if (!consumer->token)
 		return;
@@ -243,18 +279,15 @@ void irq_bypass_unregister_consumer(struct irq_bypass_consumer *consumer)
 
 	mutex_lock(&lock);
 
-	list_for_each_entry(tmp, &consumers, node) {
+	hash_for_each(consumers, bkt, tmp, node) {
 		if (tmp != consumer)
 			continue;
 
-		list_for_each_entry(producer, &producers, node) {
-			if (producer->token == consumer->token) {
-				__disconnect(producer, consumer);
-				break;
-			}
-		}
+		producer = find_producer_by_token(consumer->token);
+		if (producer)
+			__disconnect(producer, consumer);
 
-		list_del(&consumer->node);
+		hash_del(&consumer->node);
 		module_put(THIS_MODULE);
 		break;
 	}
-- 
2.23.0