Re: [PATCH] irqbypass: convert producers/consumers single linked list to hlist

[Jason Wang]

On Wed, Mar 1, 2023 at 10:18 AM Longpeng(Mike) <longpeng2@xxxxxxxxxx> wrote:
>
> From: Longpeng <longpeng2@xxxxxxxxxx>
>
> 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@xxxxxxxxxx>
> ---
>  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;
>         }

Nit: I wonder if it would be more straightforward to simply open code
the find_producer_by_token() by simply replacing

list_for_each_entry()

with

hash_for_each_possible().

This seems more flexible than adding stuffs like hash_consumer(). Or
factor out the find_producer_by_token first and replace list with
hlist.

Thanks

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