diff mbox series

irqbypass: convert producers/consumers single linked list to hlist

Message ID 20230301021830.880-1-longpeng2@huawei.com (mailing list archive)
State New, archived
Headers show
Series irqbypass: convert producers/consumers single linked list to hlist | expand

Commit Message

Longpeng(Mike) March 1, 2023, 2:18 a.m. UTC 
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(-)

Comments

kernel test robot March 1, 2023, 4:11 a.m. UTC | #1 
Hi Longpeng(Mike),

Thank you for the patch! Perhaps something to improve:

[auto build test WARNING on linus/master]
[also build test WARNING on v6.2 next-20230301]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Longpeng-Mike/irqbypass-convert-producers-consumers-single-linked-list-to-hlist/20230301-101936
patch link:    https://lore.kernel.org/r/20230301021830.880-1-longpeng2%40huawei.com
patch subject: [PATCH] irqbypass: convert producers/consumers single linked list to hlist
config: m68k-allyesconfig (https://download.01.org/0day-ci/archive/20230301/202303011218.cfYZyYAh-lkp@intel.com/config)
compiler: m68k-linux-gcc (GCC) 12.1.0
reproduce (this is a W=1 build):
        wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # https://github.com/intel-lab-lkp/linux/commit/4dcec57dc5acaecbf3bb03634ab1ef6a696927be
        git remote add linux-review https://github.com/intel-lab-lkp/linux
        git fetch --no-tags linux-review Longpeng-Mike/irqbypass-convert-producers-consumers-single-linked-list-to-hlist/20230301-101936
        git checkout 4dcec57dc5acaecbf3bb03634ab1ef6a696927be
        # save the config file
        mkdir build_dir && cp config build_dir/.config
        COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-12.1.0 make.cross W=1 O=build_dir ARCH=m68k olddefconfig
        COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-12.1.0 make.cross W=1 O=build_dir ARCH=m68k SHELL=/bin/bash virt/

If you fix the issue, kindly add following tag where applicable
| Reported-by: kernel test robot <lkp@intel.com>
| Link: https://lore.kernel.org/oe-kbuild-all/202303011218.cfYZyYAh-lkp@intel.com/

All warnings (new ones prefixed by >>):

   In file included from include/linux/irqbypass.h:11,
                    from virt/lib/irqbypass.c:17:
   virt/lib/irqbypass.c: In function 'find_producer_by_token':
>> virt/lib/irqbypass.c:42:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:19: note: in definition of macro 'hlist_entry_safe'
    1043 |         ({ typeof(ptr) ____ptr = (ptr); \
         |                   ^~~
   include/linux/hashtable.h:166:9: note: in expansion of macro 'hlist_for_each_entry'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |         ^~~~~~~~~~~~~~~~~~~~
   include/linux/hashtable.h:166:41: note: in expansion of macro 'hash_min'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |                                         ^~~~~~~~
   virt/lib/irqbypass.c:42:9: note: in expansion of macro 'hash_for_each_possible'
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |         ^~~~~~~~~~~~~~~~~~~~~~
>> virt/lib/irqbypass.c:42:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:19: note: in definition of macro 'hlist_entry_safe'
    1043 |         ({ typeof(ptr) ____ptr = (ptr); \
         |                   ^~~
   include/linux/hashtable.h:166:9: note: in expansion of macro 'hlist_for_each_entry'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |         ^~~~~~~~~~~~~~~~~~~~
   include/linux/hashtable.h:166:41: note: in expansion of macro 'hash_min'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |                                         ^~~~~~~~
   virt/lib/irqbypass.c:42:9: note: in expansion of macro 'hash_for_each_possible'
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |         ^~~~~~~~~~~~~~~~~~~~~~
>> virt/lib/irqbypass.c:42:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:19: note: in definition of macro 'hlist_entry_safe'
    1043 |         ({ typeof(ptr) ____ptr = (ptr); \
         |                   ^~~
   include/linux/hashtable.h:166:9: note: in expansion of macro 'hlist_for_each_entry'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |         ^~~~~~~~~~~~~~~~~~~~
   include/linux/hashtable.h:32:50: note: in expansion of macro 'hash_long'
      32 |         (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
         |                                                  ^~~~~~~~~
   include/linux/hashtable.h:166:41: note: in expansion of macro 'hash_min'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |                                         ^~~~~~~~
   virt/lib/irqbypass.c:42:9: note: in expansion of macro 'hash_for_each_possible'
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |         ^~~~~~~~~~~~~~~~~~~~~~
>> virt/lib/irqbypass.c:42:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:35: note: in definition of macro 'hlist_entry_safe'
    1043 |         ({ typeof(ptr) ____ptr = (ptr); \
         |                                   ^~~
   include/linux/hashtable.h:166:9: note: in expansion of macro 'hlist_for_each_entry'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |         ^~~~~~~~~~~~~~~~~~~~
   include/linux/hashtable.h:166:41: note: in expansion of macro 'hash_min'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |                                         ^~~~~~~~
   virt/lib/irqbypass.c:42:9: note: in expansion of macro 'hash_for_each_possible'
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |         ^~~~~~~~~~~~~~~~~~~~~~
>> virt/lib/irqbypass.c:42:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:35: note: in definition of macro 'hlist_entry_safe'
    1043 |         ({ typeof(ptr) ____ptr = (ptr); \
         |                                   ^~~
   include/linux/hashtable.h:166:9: note: in expansion of macro 'hlist_for_each_entry'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |         ^~~~~~~~~~~~~~~~~~~~
   include/linux/hashtable.h:166:41: note: in expansion of macro 'hash_min'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |                                         ^~~~~~~~
   virt/lib/irqbypass.c:42:9: note: in expansion of macro 'hash_for_each_possible'
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |         ^~~~~~~~~~~~~~~~~~~~~~
>> virt/lib/irqbypass.c:42:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:35: note: in definition of macro 'hlist_entry_safe'
    1043 |         ({ typeof(ptr) ____ptr = (ptr); \
         |                                   ^~~
   include/linux/hashtable.h:166:9: note: in expansion of macro 'hlist_for_each_entry'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |         ^~~~~~~~~~~~~~~~~~~~
   include/linux/hashtable.h:32:50: note: in expansion of macro 'hash_long'
      32 |         (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
         |                                                  ^~~~~~~~~
   include/linux/hashtable.h:166:41: note: in expansion of macro 'hash_min'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |                                         ^~~~~~~~
   virt/lib/irqbypass.c:42:9: note: in expansion of macro 'hash_for_each_possible'
      42 |         hash_for_each_possible(producers, producer, node, (uint64_t)token)
         |         ^~~~~~~~~~~~~~~~~~~~~~
   virt/lib/irqbypass.c: In function 'find_consumer_by_token':
   virt/lib/irqbypass.c:54:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      54 |         hash_for_each_possible(producers, consumer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:19: note: in definition of macro 'hlist_entry_safe'
    1043 |         ({ typeof(ptr) ____ptr = (ptr); \
         |                   ^~~
   include/linux/hashtable.h:166:9: note: in expansion of macro 'hlist_for_each_entry'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |         ^~~~~~~~~~~~~~~~~~~~
   include/linux/hashtable.h:166:41: note: in expansion of macro 'hash_min'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |                                         ^~~~~~~~
   virt/lib/irqbypass.c:54:9: note: in expansion of macro 'hash_for_each_possible'
      54 |         hash_for_each_possible(producers, consumer, node, (uint64_t)token)
         |         ^~~~~~~~~~~~~~~~~~~~~~
   virt/lib/irqbypass.c:54:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      54 |         hash_for_each_possible(producers, consumer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:19: note: in definition of macro 'hlist_entry_safe'
    1043 |         ({ typeof(ptr) ____ptr = (ptr); \
         |                   ^~~
   include/linux/hashtable.h:166:9: note: in expansion of macro 'hlist_for_each_entry'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |         ^~~~~~~~~~~~~~~~~~~~
   include/linux/hashtable.h:166:41: note: in expansion of macro 'hash_min'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |                                         ^~~~~~~~
   virt/lib/irqbypass.c:54:9: note: in expansion of macro 'hash_for_each_possible'
      54 |         hash_for_each_possible(producers, consumer, node, (uint64_t)token)
         |         ^~~~~~~~~~~~~~~~~~~~~~
   virt/lib/irqbypass.c:54:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      54 |         hash_for_each_possible(producers, consumer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:19: note: in definition of macro 'hlist_entry_safe'
    1043 |         ({ typeof(ptr) ____ptr = (ptr); \
         |                   ^~~
   include/linux/hashtable.h:166:9: note: in expansion of macro 'hlist_for_each_entry'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |         ^~~~~~~~~~~~~~~~~~~~
   include/linux/hashtable.h:32:50: note: in expansion of macro 'hash_long'
      32 |         (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
         |                                                  ^~~~~~~~~
   include/linux/hashtable.h:166:41: note: in expansion of macro 'hash_min'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |                                         ^~~~~~~~
   virt/lib/irqbypass.c:54:9: note: in expansion of macro 'hash_for_each_possible'
      54 |         hash_for_each_possible(producers, consumer, node, (uint64_t)token)
         |         ^~~~~~~~~~~~~~~~~~~~~~
   virt/lib/irqbypass.c:54:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      54 |         hash_for_each_possible(producers, consumer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:35: note: in definition of macro 'hlist_entry_safe'
    1043 |         ({ typeof(ptr) ____ptr = (ptr); \
         |                                   ^~~
   include/linux/hashtable.h:166:9: note: in expansion of macro 'hlist_for_each_entry'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |         ^~~~~~~~~~~~~~~~~~~~
   include/linux/hashtable.h:166:41: note: in expansion of macro 'hash_min'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |                                         ^~~~~~~~
   virt/lib/irqbypass.c:54:9: note: in expansion of macro 'hash_for_each_possible'
      54 |         hash_for_each_possible(producers, consumer, node, (uint64_t)token)
         |         ^~~~~~~~~~~~~~~~~~~~~~
   virt/lib/irqbypass.c:54:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      54 |         hash_for_each_possible(producers, consumer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:35: note: in definition of macro 'hlist_entry_safe'
    1043 |         ({ typeof(ptr) ____ptr = (ptr); \
         |                                   ^~~
   include/linux/hashtable.h:166:9: note: in expansion of macro 'hlist_for_each_entry'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |         ^~~~~~~~~~~~~~~~~~~~
   include/linux/hashtable.h:166:41: note: in expansion of macro 'hash_min'
     166 |         hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
         |                                         ^~~~~~~~
   virt/lib/irqbypass.c:54:9: note: in expansion of macro 'hash_for_each_possible'
      54 |         hash_for_each_possible(producers, consumer, node, (uint64_t)token)
         |         ^~~~~~~~~~~~~~~~~~~~~~
   virt/lib/irqbypass.c:54:59: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
      54 |         hash_for_each_possible(producers, consumer, node, (uint64_t)token)
         |                                                           ^
   include/linux/list.h:1043:35: note: in definition of macro 'hlist_entry_safe'


vim +42 virt/lib/irqbypass.c

  > 17	#include <linux/irqbypass.h>
    18	#include <linux/list.h>
    19	#include <linux/module.h>
    20	#include <linux/mutex.h>
    21	#include <linux/hashtable.h>
    22	
    23	MODULE_LICENSE("GPL v2");
    24	MODULE_DESCRIPTION("IRQ bypass manager utility module");
    25	
    26	/*
    27	 * hash table for produces/consumers. This improve the performace to find
    28	 * an existing producer/consumer.
    29	 */
    30	#define PRODUCERS_HASH_BITS	9
    31	#define CONSUMERS_HASH_BITS	9
    32	static DEFINE_HASHTABLE(producers, PRODUCERS_HASH_BITS);
    33	static DEFINE_HASHTABLE(consumers, CONSUMERS_HASH_BITS);
    34	static DEFINE_MUTEX(lock);
    35	
    36	
    37	/* @lock must be held */
    38	static struct irq_bypass_producer *find_producer_by_token(void *token)
    39	{
    40		struct irq_bypass_producer *producer;
    41	
  > 42		hash_for_each_possible(producers, producer, node, (uint64_t)token)
    43			if (producer->token == token)
    44				return producer;
    45	
    46		return NULL;
    47	}
    48
Jason Wang March 1, 2023, 5:19 a.m. UTC | #2 
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
>
diff mbox series

Patch

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