Re: [PATCH v2 2/2] KVM: irqbypass: Convert producers/consumers single linked list to XArray

From: Like Xu
Date: Wed Oct 11 2023 - 07:24:56 EST


Hi all, do we have any negative comments on this issue ?
This register path could be a performance bottleneck in serverless scenarios.
Your comments are much appreciated, thanks!

On 26/9/2023 5:18 pm, Like Xu wrote:
On 25/9/2023 11:24 pm, Like Xu wrote:
@@ -97,24 +98,23 @@ 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;
+    }
+
+    ret = xa_err(xa_store(&producers, token, producer, GFP_KERNEL));
+    if (ret)
+        goto out_err;
+
+    consumer = xa_load(&consumers, token);
+    if (consumer) {
+        ret = __connect(producer, consumer);
+        if (ret)
              goto out_err;

This doesn't match previous behavior, the producer is registered to the
xarray regardless of the result of the connect operation and the caller
cannot distinguish between failures.  The module reference is released
regardless of xarray item.  Nak.

Hi Alex,

Thanks for your comments and indeed, the additional error throwing logic
breaks the caller's expectations as you said.

What if we use LIST as a fallback option for XARRAY? Specifically, when
xa_err(xa_store()) is true, then fallback to use LIST to check for
producers/consumers, and in most cases it still takes the XARRAY path:

     static DEFINE_XARRAY(xproducers);
     ...
     if (xa_err(xa_store(&xproducers, (unsigned long)producer->token,
                 producer, GFP_KERNEL)))
         list_add(&producer->node, &producers);
     ...

There will also be a LIST option on the lookup path.

The rough code already works, could we move in this direction (combining
XARRAY with LIST to hidden the memory allocation error from xa_store) ?

For better discussion and further improvement, here's the draft code combining
xarray and list, using both xarray and list to store producers and consumers,
but with xarray preferred for queries:

diff --git a/virt/lib/irqbypass.c b/virt/lib/irqbypass.c
index e0aabbbf27ec..7cc30d699ece 100644
--- a/virt/lib/irqbypass.c
+++ b/virt/lib/irqbypass.c
@@ -18,12 +18,15 @@
 #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(xproducers);
+static DEFINE_XARRAY(xconsumers);
 static DEFINE_MUTEX(lock);

 /* @lock must be held when calling connect */
@@ -74,6 +77,117 @@ static void __disconnect(struct irq_bypass_producer *prod,
         prod->start(prod);
 }

+#define CHECK_TOKEN    BIT_ULL(0)
+#define CHECK_POINTER    BIT_ULL(1)
+
+static inline bool
+producer_already_exist(struct irq_bypass_producer *producer, u64 flags)
+{
+    struct irq_bypass_producer *tmp;
+
+    if (((flags & CHECK_POINTER) && xa_load(&xproducers,
+                        (unsigned long)producer)) ||
+        ((flags & CHECK_TOKEN) && xa_load(&xproducers,
+                          (unsigned long)producer->token)))
+        return true;
+
+    list_for_each_entry(tmp, &producers, node) {
+        if (((flags & CHECK_POINTER) && tmp == producer) ||
+            ((flags & CHECK_TOKEN) && tmp->token == producer->token))
+            return true;
+    }
+
+    return false;
+}
+
+static inline bool
+consumer_already_exist(struct irq_bypass_consumer *consumer, u64 flags)
+{
+    struct irq_bypass_consumer *tmp;
+
+    if (((flags & CHECK_POINTER) && xa_load(&xconsumers,
+                        (unsigned long)consumer)) ||
+        ((flags & CHECK_TOKEN) && xa_load(&xconsumers,
+                          (unsigned long)consumer->token)))
+        return true;
+
+    list_for_each_entry(tmp, &consumers, node) {
+        if (((flags & CHECK_POINTER) && tmp == consumer) ||
+            ((flags & CHECK_TOKEN) && tmp->token == consumer->token))
+            return true;
+    }
+
+    return false;
+}
+
+static inline struct irq_bypass_producer *get_producer_by_token(void *token)
+{
+    struct irq_bypass_producer *tmp;
+
+    tmp = xa_load(&xproducers, (unsigned long)token);
+    if (tmp)
+        return tmp;
+
+    list_for_each_entry(tmp, &producers, node) {
+        if (tmp->token == token)
+            return tmp;
+    }
+
+    return NULL;
+}
+
+static inline struct irq_bypass_consumer *get_consumer_by_token(void *token)
+{
+    struct irq_bypass_consumer *tmp;
+
+    tmp = xa_load(&xconsumers, (unsigned long)token);
+    if (tmp)
+        return tmp;
+
+    list_for_each_entry(tmp, &consumers, node) {
+        if (tmp->token == token)
+            return tmp;
+    }
+
+    return NULL;
+}
+
+static inline void add_irq_bypass_producer(struct irq_bypass_producer *producer)
+{
+    xa_store(&xproducers, (unsigned long)producer->token,
+         producer, GFP_KERNEL);
+    xa_store(&xproducers, (unsigned long)producer,
+         producer, GFP_KERNEL);
+
+    list_add(&producer->node, &producers);
+}
+
+static inline void del_irq_bypass_producer(struct irq_bypass_producer *producer)
+{
+    xa_erase(&xproducers, (unsigned long)producer->token);
+    xa_erase(&xproducers, (unsigned long)producer);
+
+    list_del(&producer->node);
+}
+
+static inline void add_irq_bypass_consumer(struct irq_bypass_consumer *consumer)
+{
+    xa_store(&xconsumers, (unsigned long)consumer->token,
+         consumer, GFP_KERNEL);
+    xa_store(&xconsumers, (unsigned long)consumer,
+         consumer, GFP_KERNEL);
+
+    list_add(&consumer->node, &consumers);
+}
+
+static inline void del_irq_bypass_consumer(struct irq_bypass_consumer *consumer)
+{
+    xa_erase(&xconsumers, (unsigned long)consumer->token);
+    xa_erase(&xconsumers, (unsigned long)consumer);
+
+    list_del(&consumer->node);
+}
+
 /**
  * irq_bypass_register_producer - register IRQ bypass producer
  * @producer: pointer to producer structure
@@ -83,7 +197,6 @@ static void __disconnect(struct irq_bypass_producer *prod,
  */
 int irq_bypass_register_producer(struct irq_bypass_producer *producer)
 {
-    struct irq_bypass_producer *tmp;
     struct irq_bypass_consumer *consumer;
     int ret;

@@ -97,23 +210,19 @@ 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;
+    if (producer_already_exist(producer, CHECK_TOKEN | CHECK_POINTER)) {
+        ret = -EBUSY;
+        goto out_err;
+    }
+
+    consumer = get_consumer_by_token(producer->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);
+    add_irq_bypass_producer(producer);

     mutex_unlock(&lock);

@@ -134,7 +243,6 @@ EXPORT_SYMBOL_GPL(irq_bypass_register_producer);
  */
 void irq_bypass_unregister_producer(struct irq_bypass_producer *producer)
 {
-    struct irq_bypass_producer *tmp;
     struct irq_bypass_consumer *consumer;

     if (!producer->token)
@@ -147,20 +255,13 @@ void irq_bypass_unregister_producer(struct irq_bypass_producer *producer)

     mutex_lock(&lock);

-    list_for_each_entry(tmp, &producers, node) {
-        if (tmp != producer)
-            continue;
+    if (producer_already_exist(producer, CHECK_POINTER)) {
+        consumer = get_consumer_by_token(producer->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);
+        del_irq_bypass_producer(producer);
         module_put(THIS_MODULE);
-        break;
     }

     mutex_unlock(&lock);
@@ -178,7 +279,6 @@ EXPORT_SYMBOL_GPL(irq_bypass_unregister_producer);
  */
 int irq_bypass_register_consumer(struct irq_bypass_consumer *consumer)
 {
-    struct irq_bypass_consumer *tmp;
     struct irq_bypass_producer *producer;
     int ret;

@@ -193,23 +293,19 @@ 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;
+    if (consumer_already_exist(consumer, CHECK_TOKEN | CHECK_POINTER)) {
+        ret = -EBUSY;
+        goto out_err;
+    }
+
+    producer = get_producer_by_token(consumer->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);
+    add_irq_bypass_consumer(consumer);

     mutex_unlock(&lock);

@@ -230,7 +326,6 @@ EXPORT_SYMBOL_GPL(irq_bypass_register_consumer);
  */
 void irq_bypass_unregister_consumer(struct irq_bypass_consumer *consumer)
 {
-    struct irq_bypass_consumer *tmp;
     struct irq_bypass_producer *producer;

     if (!consumer->token)
@@ -243,20 +338,13 @@ void irq_bypass_unregister_consumer(struct irq_bypass_consumer *consumer)

     mutex_lock(&lock);

-    list_for_each_entry(tmp, &consumers, node) {
-        if (tmp != consumer)
-            continue;
+    if (consumer_already_exist(consumer, CHECK_POINTER)) {
+        producer = get_producer_by_token(consumer->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);
+        del_irq_bypass_consumer(consumer);
         module_put(THIS_MODULE);
-        break;
     }

     mutex_unlock(&lock);
@@ -264,3 +352,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(&xproducers);
+    xa_destroy(&xconsumers);
+}
+module_exit(irqbypass_exit);