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

Jason Wang
2023-03-01T05:20:30Z

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

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
>