irqbypass: convert producers/consumers single linked list to hlist
Commit Message
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
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
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
>
@@ -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 *);
@@ -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;
}