hashtable: introduce a small and naive hashtable
PATCH v5 1/1 hashtable: introduce a small and naive hashtable
This hashtable implementation is using hlist buckets to provide a simple hashtable to prevent it from getting reimplemented all over the kernel.
---
Changes from v4:
- Addressed comments by Mathieu Desnoyers.
include/linux/hashtable.h | 190 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 190 insertions(+) create mode 100644 include/linux/hashtable.h
include/linux/hashtable.h new file +190 -0
@@ -0,0 +1,190 @@ +/* +* Hash table implementation +* (C) 2012 Sasha Levin <[email protected]> +*/ + +#ifndef _LINUX_HASHTABLE_H +#define _LINUX_HASHTABLE_H + +#include <linux/list.h> +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/hash.h> +#include <linux/rculist.h> + +#define DEFINE_HASHTABLE (name, bits) \ + struct hlist_head name[HASH_SIZE(bits)] = \ + { [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT } + +#define DECLARE_HASHTABLE (name, bits) \ + struct hlist_head name[1 << (bits)] + +#define HASH_SIZE (name) (1 << HASH_BITS(name)) +#define HASH_BITS (name) ilog2(ARRAY_SIZE(name)) + +/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */ +#define hash_min (val, bits) \ +({ \ + sizeof(val) <= 4 ? \ + hash_32(val, bits) : \ + hash_long(val, bits); \ +}) + +/** +* hash_init - initialize a hash table +* @hashtable: hashtable to be initialized +* +* Calculates the size of the hashtable from the given parameter, otherwise +* same as hash_init_size. +* +* This has to be a macro since HASH_BITS() will not work on pointers since +* it calculates the size during preprocessing. +*/ +#define hash_init (hashtable) \ +({ \ + int __i; \ + \ + for (__i = 0; __i < HASH_BITS(hashtable); __i++) \ + INIT_HLIST_HEAD(&hashtable[__i]); \ +}) + +/** +* hash_add - add an object to a hashtable +* @hashtable: hashtable to add to +* @node: the &struct hlist_node of the object to be added +* @key: the key of the object to be added +*/ +#define hash_add (hashtable, node, key) \ + hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]); + +/** +* hash_add_rcu - add an object to a rcu enabled hashtable +* @hashtable: hashtable to add to +* @node: the &struct hlist_node of the object to be added +* @key: the key of the object to be added +*/ +#define hash_add_rcu (hashtable, node, key) \ + hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]); + +/** +* hash_hashed - check whether an object is in any hashtable +* @node: the &struct hlist_node of the object to be checked +*/ +#define hash_hashed (node) (!hlist_unhashed(node)) + +/** +* hash_empty - check whether a hashtable is empty +* @hashtable: hashtable to check +* +* This has to be a macro since HASH_BITS() will not work on pointers since +* it calculates the size during preprocessing. +*/ +#define hash_empty (hashtable) \ +({ \ + int __i; \ + bool __ret = true; \ + \ + for (__i = 0; __i < HASH_SIZE(hashtable); __i++) \ + if (!hlist_empty(&hashtable[__i])) \ + __ret = false; \ + \ + __ret; \ +}) + +/** +* hash_del - remove an object from a hashtable +* @node: &struct hlist_node of the object to remove +*/ +static inline void hash_del (struct hlist_node *node) +{ +hlist_del_init (node); +} + +/** +* hash_del_rcu - remove an object from a rcu enabled hashtable +* @node: &struct hlist_node of the object to remove +*/ +static inline void hash_del_rcu (struct hlist_node *node) +{ +hlist_del_init_rcu (node); +} + +/** +* hash_for_each - iterate over a hashtable +* @name: hashtable to iterate +* @bkt: integer to use as bucket loop cursor +* @node: the &struct list_head to use as a loop cursor for each entry +* @obj: the type * to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +*/ +#define hash_for_each (name, bkt, node, obj, member) \ + for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\ + hlist_for_each_entry(obj, node, &name[bkt], member) + +/** +* hash_for_each_rcu - iterate over a rcu enabled hashtable +* @name: hashtable to iterate +* @bkt: integer to use as bucket loop cursor +* @node: the &struct list_head to use as a loop cursor for each entry +* @obj: the type * to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +*/ +#define hash_for_each_rcu (name, bkt, node, obj, member) \ + for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\ + hlist_for_each_entry_rcu(obj, node, &name[bkt], member) + +/** +* hash_for_each_safe - iterate over a hashtable safe against removal of +* hash entry +* @name: hashtable to iterate +* @bkt: integer to use as bucket loop cursor +* @node: the &struct list_head to use as a loop cursor for each entry +* @tmp: a &struct used for temporary storage +* @obj: the type * to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +*/ +#define hash_for_each_safe (name, bkt, node, tmp, obj, member) \ + for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\ + hlist_for_each_entry_safe(obj, node, tmp, &name[bkt], member) + +/** +* hash_for_each_possible - iterate over all possible objects hashing to the +* same bucket +* @name: hashtable to iterate +* @obj: the type * to use as a loop cursor for each entry +* @node: the &struct list_head to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +* @key: the key of the objects to iterate over +*/ +#define hash_for_each_possible (name, obj, node, member, key) \ + hlist_for_each_entry(obj, node, &name[hash_min(key, HASH_BITS(name))], member) + +/** +* hash_for_each_possible_rcu - iterate over all possible objects hashing to the +* same bucket in an rcu enabled hashtable +* in a rcu enabled hashtable +* @name: hashtable to iterate +* @obj: the type * to use as a loop cursor for each entry +* @node: the &struct list_head to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +* @key: the key of the objects to iterate over +*/ +#define hash_for_each_possible_rcu (name, obj, node, member, key) \ + hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, HASH_BITS(name))], member) + +/** +* hash_for_each_possible_safe - iterate over all possible objects hashing to the +* same bucket safe against removals +* @name: hashtable to iterate +* @obj: the type * to use as a loop cursor for each entry +* @node: the &struct list_head to use as a loop cursor for each entry +* @tmp: a &struct used for temporary storage +* @member: the name of the hlist_node within the struct +* @key: the key of the objects to iterate over +*/ +#define hash_for_each_possible_safe (name, obj, node, tmp, member, key) \ + hlist_for_each_entry_safe(obj, node, tmp, \ + &name[hash_min(key, HASH_BITS(name))], member) + + +#endif
Signature · 1 line
1.7.12
Quoted 57 lines · * Sasha Levin ([email protected]) wrote:
This hashtable implementation is using hlist buckets to provide a simple hashtable to prevent it from getting reimplemented all over the kernel.
Signed-off-by Sasha Levin <[email protected]>---
Changes from v4:
- Addressed comments by Mathieu Desnoyers.
include/linux/hashtable.h | 190 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 190 insertions(+) create mode 100644 include/linux/hashtable.hinclude/linux/hashtable.h new file +37
-0@@ -0,0 +1,190 @@ +/* +* Hash table implementation +* (C) 2012 Sasha Levin <[email protected]> +*/ + +#ifndef _LINUX_HASHTABLE_H +#define _LINUX_HASHTABLE_H + +#include <linux/list.h> +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/hash.h> +#include <linux/rculist.h> + +#define DEFINE_HASHTABLE (name, bits) \ + struct hlist_head name[HASH_SIZE(bits)] = \ + { [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT } + +#define DECLARE_HASHTABLE (name, bits) \ + struct hlist_head name[1 << (bits)] + +#define HASH_SIZE (name) (1 << HASH_BITS(name)) +#define HASH_BITS (name) ilog2(ARRAY_SIZE(name)) + +/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */ +#define hash_min (val, bits) \ +({ \ + sizeof(val) <= 4 ? \ + hash_32(val, bits) : \ + hash_long(val, bits); \ +}) + +/** +* hash_init - initialize a hash table +* @hashtable: hashtable to be initialized +* +* Calculates the size of the hashtable from the given parameter, otherwise
include/linux/hashtable.h line 47
Quoted 10 lines
include/linux/hashtable.h new file +10
-0+* same as hash_init_size. +* +* This has to be a macro since HASH_BITS() will not work on pointers since +* it calculates the size during preprocessing. +*/ +#define hash_init (hashtable) \ +({ \ + int __i; \ + \ + for (__i = 0; __i < HASH_BITS(hashtable); __i++) \
I think this fails to initialize the whole table. You'd need
HASH_BITS -> HASH_SIZE
Which brings the following question: how did you test this code ? It would be nice to have a small test module along with this patchset that stress-tests this simple hash table in various configurations (on stack, in data, etc).
Also, I don't see how hash_init() can be useful, since DEFINE_HASHTABLE already initialize the array entries. If it is for dynamically allocated hash tables, this also won't work, considering the comment "This has to be a macro since HASH_BITS() will not work on pointers since it calculates the size during preprocessing."
Quoted 23 lines
include/linux/hashtable.h new file +23
-0+INIT_HLIST_HEAD (&hashtable[__i]); \ +}) + +/** +* hash_add - add an object to a hashtable +* @hashtable: hashtable to add to +* @node: the &struct hlist_node of the object to be added +* @key: the key of the object to be added +*/ +#define hash_add (hashtable, node, key) \ + hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]); + +/** +* hash_add_rcu - add an object to a rcu enabled hashtable +* @hashtable: hashtable to add to +* @node: the &struct hlist_node of the object to be added +* @key: the key of the object to be added +*/ +#define hash_add_rcu (hashtable, node, key) \ + hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]); + +/** +* hash_hashed - check whether an object is in any hashtable
include/linux/hashtable.h line 80
Quoted 10 lines
include/linux/hashtable.h new file +10
-0+* @node: the &struct hlist_node of the object to be checked +*/ +#define hash_hashed (node) (!hlist_unhashed(node)) + +/** +* hash_empty - check whether a hashtable is empty +* @hashtable: hashtable to check +* +* This has to be a macro since HASH_BITS() will not work on pointers since +* it calculates the size during preprocessing.
So I get that hash_empty is only expected to be used for statically defined hash tables ? Does it support hash tables in dynamically allocated memory ? On the stack ? If these are never expected to be supported, this should be documented.
Thanks,
Mathieu
Quoted 113 lines
include/linux/hashtable.h new file +110
-0+*/ +#define hash_empty (hashtable) \ +({ \ + int __i; \ + bool __ret = true; \ + \ + for (__i = 0; __i < HASH_SIZE(hashtable); __i++) \ + if (!hlist_empty(&hashtable[__i])) \ + __ret = false; \ + \ + __ret; \ +}) + +/** +* hash_del - remove an object from a hashtable +* @node: &struct hlist_node of the object to remove +*/ +static inline void hash_del (struct hlist_node *node) +{ +hlist_del_init (node); +} + +/** +* hash_del_rcu - remove an object from a rcu enabled hashtable +* @node: &struct hlist_node of the object to remove +*/ +static inline void hash_del_rcu (struct hlist_node *node) +{ +hlist_del_init_rcu (node); +} + +/** +* hash_for_each - iterate over a hashtable +* @name: hashtable to iterate +* @bkt: integer to use as bucket loop cursor +* @node: the &struct list_head to use as a loop cursor for each entry +* @obj: the type * to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +*/ +#define hash_for_each (name, bkt, node, obj, member) \ + for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\ + hlist_for_each_entry(obj, node, &name[bkt], member) + +/** +* hash_for_each_rcu - iterate over a rcu enabled hashtable +* @name: hashtable to iterate +* @bkt: integer to use as bucket loop cursor +* @node: the &struct list_head to use as a loop cursor for each entry +* @obj: the type * to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +*/ +#define hash_for_each_rcu (name, bkt, node, obj, member) \ + for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\ + hlist_for_each_entry_rcu(obj, node, &name[bkt], member) + +/** +* hash_for_each_safe - iterate over a hashtable safe against removal of +* hash entry +* @name: hashtable to iterate +* @bkt: integer to use as bucket loop cursor +* @node: the &struct list_head to use as a loop cursor for each entry +* @tmp: a &struct used for temporary storage +* @obj: the type * to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +*/ +#define hash_for_each_safe (name, bkt, node, tmp, obj, member) \ + for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\ + hlist_for_each_entry_safe(obj, node, tmp, &name[bkt], member) + +/** +* hash_for_each_possible - iterate over all possible objects hashing to the +* same bucket +* @name: hashtable to iterate +* @obj: the type * to use as a loop cursor for each entry +* @node: the &struct list_head to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +* @key: the key of the objects to iterate over +*/ +#define hash_for_each_possible (name, obj, node, member, key) \ + hlist_for_each_entry(obj, node, &name[hash_min(key, HASH_BITS(name))], member) + +/** +* hash_for_each_possible_rcu - iterate over all possible objects hashing to the +* same bucket in an rcu enabled hashtable +* in a rcu enabled hashtable +* @name: hashtable to iterate +* @obj: the type * to use as a loop cursor for each entry +* @node: the &struct list_head to use as a loop cursor for each entry +* @member: the name of the hlist_node within the struct +* @key: the key of the objects to iterate over +*/ +#define hash_for_each_possible_rcu (name, obj, node, member, key) \ + hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, HASH_BITS(name))], member) + +/** +* hash_for_each_possible_safe - iterate over all possible objects hashing to the +* same bucket safe against removals +* @name: hashtable to iterate +* @obj: the type * to use as a loop cursor for each entry +* @node: the &struct list_head to use as a loop cursor for each entry +* @tmp: a &struct used for temporary storage +* @member: the name of the hlist_node within the struct +* @key: the key of the objects to iterate over +*/ +#define hash_for_each_possible_safe (name, obj, node, tmp, member, key) \ + hlist_for_each_entry_safe(obj, node, tmp, \ + &name[hash_min(key, HASH_BITS(name))], member) + + +#endif Signature · 1 line
1.7.12
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 71 lines · Mathieu Desnoyers
Quoted 57 lines · * Sasha Levin ([email protected]) wrote:
This hashtable implementation is using hlist buckets to provide a simple hashtable to prevent it from getting reimplemented all over the kernel.
Signed-off-by Sasha Levin <[email protected]>---
Changes from v4:
- Addressed comments by Mathieu Desnoyers.
include/linux/hashtable.h | 190 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 190 insertions(+) create mode 100644 include/linux/hashtable.hinclude/linux/hashtable.h new file +37
-0@@ -0,0 +1,190 @@ +/* +* Hash table implementation +* (C) 2012 Sasha Levin <[email protected]> +*/ + +#ifndef _LINUX_HASHTABLE_H +#define _LINUX_HASHTABLE_H + +#include <linux/list.h> +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/hash.h> +#include <linux/rculist.h> + +#define DEFINE_HASHTABLE (name, bits) \ + struct hlist_head name[HASH_SIZE(bits)] = \ + { [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT } + +#define DECLARE_HASHTABLE (name, bits) \ + struct hlist_head name[1 << (bits)] + +#define HASH_SIZE (name) (1 << HASH_BITS(name)) +#define HASH_BITS (name) ilog2(ARRAY_SIZE(name)) + +/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */ +#define hash_min (val, bits) \ +({ \ + sizeof(val) <= 4 ? \ + hash_32(val, bits) : \ + hash_long(val, bits); \ +}) + +/** +* hash_init - initialize a hash table +* @hashtable: hashtable to be initialized +* +* Calculates the size of the hashtable from the given parameter, otherwise include/linux/hashtable.h line 47
Quoted 10 lines
include/linux/hashtable.h new file +10
-0+* same as hash_init_size. +* +* This has to be a macro since HASH_BITS() will not work on pointers since +* it calculates the size during preprocessing. +*/ +#define hash_init (hashtable) \ +({ \ + int __i; \ + \ + for (__i = 0; __i < HASH_BITS(hashtable); __i++) \I think this fails to initialize the whole table. You'd need
Quoted 1 line
HASH_BITS->HASH_SIZE
Right.
Unfortunately it's pretty hard catching something like this :/
Quoted 4 lines
Which brings the following question: how did you test this code ? It would be nice to have a small test module along with this patchset that stress-tests this simple hash table in various configurations (on stack, in data, etc).
I do two things:
- A small userspace test (since this header works just fine from
userspace as well).
- Build a kernel with all ~20 commits and stresstest it a bit, since
things like workqueue were converted, it finds issues pretty fast.
I agree that there should be something similar to the list sort test we currently have, but I'm not sure if it should be in the scope of this initial patch.
Quoted 5 lines
Also, I don't see how
hash_init()can be useful, sinceDEFINE_HASHTABLEalready initialize the array entries. If it is for dynamically allocated hash tables, this also won't work, considering the comment "This has to be a macro sinceHASH_BITS()will not work on pointers since it calculates the size during preprocessing."
hash_init() is actually used to clear the hashtable in two of the commits I've used to send along with this one. Since as you've said we now have DEFINE_HASHTABLE and DECLARE_HASHTABLE, maybe it should be now called hash_clear() or something similar. I don't have a strong opinion about this.
Quoted 30 lines
Quoted 30 lines
include/linux/hashtable.h new file +30
-0+INIT_HLIST_HEAD (&hashtable[__i]); \ +}) + +/** +* hash_add - add an object to a hashtable +* @hashtable: hashtable to add to +* @node: the &struct hlist_node of the object to be added +* @key: the key of the object to be added +*/ +#define hash_add (hashtable, node, key) \ + hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]); + +/** +* hash_add_rcu - add an object to a rcu enabled hashtable +* @hashtable: hashtable to add to +* @node: the &struct hlist_node of the object to be added +* @key: the key of the object to be added +*/ +#define hash_add_rcu (hashtable, node, key) \ + hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]); + +/** +* hash_hashed - check whether an object is in any hashtable +* @node: the &struct hlist_node of the object to be checked +*/ +#define hash_hashed (node) (!hlist_unhashed(node)) + +/** +* hash_empty - check whether a hashtable is empty +* @hashtable: hashtable to check
Quoted 8 lines
include/linux/hashtable.h line 41
Quoted 3 lines
include/linux/hashtable.h new file +3
-0+* +* This has to be a macro since HASH_BITS() will not work on pointers since +* it calculates the size during preprocessing. So I get that
hash_emptyis only expected to be used for statically defined hash tables ? Does it support hash tables in dynamically allocated memory ? On the stack ? If these are never expected to be supported, this should be documented.
Like the rest of the code, this hashtable implementation only works with non-dynamically allocated hashtables (on the stack/statically defined/etc are supported).
How would you create a dynamic hashtable with this code to begin with?
Thanks,
Sasha
Quoted 86 lines · * Sasha Levin ([email protected]) wrote:
Quoted 71 lines · Mathieu Desnoyers
Quoted 57 lines · * Sasha Levin ([email protected]) wrote:
This hashtable implementation is using hlist buckets to provide a simple hashtable to prevent it from getting reimplemented all over the kernel.
Signed-off-by Sasha Levin <[email protected]>---
Changes from v4:
- Addressed comments by Mathieu Desnoyers.
include/linux/hashtable.h | 190 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 190 insertions(+) create mode 100644 include/linux/hashtable.hinclude/linux/hashtable.h new file +37
-0@@ -0,0 +1,190 @@ +/* +* Hash table implementation +* (C) 2012 Sasha Levin <[email protected]> +*/ + +#ifndef _LINUX_HASHTABLE_H +#define _LINUX_HASHTABLE_H + +#include <linux/list.h> +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/hash.h> +#include <linux/rculist.h> + +#define DEFINE_HASHTABLE (name, bits) \ + struct hlist_head name[HASH_SIZE(bits)] = \ + { [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT } + +#define DECLARE_HASHTABLE (name, bits) \ + struct hlist_head name[1 << (bits)] + +#define HASH_SIZE (name) (1 << HASH_BITS(name)) +#define HASH_BITS (name) ilog2(ARRAY_SIZE(name)) + +/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */ +#define hash_min (val, bits) \ +({ \ + sizeof(val) <= 4 ? \ + hash_32(val, bits) : \ + hash_long(val, bits); \ +}) + +/** +* hash_init - initialize a hash table +* @hashtable: hashtable to be initialized +* +* Calculates the size of the hashtable from the given parameter, otherwise include/linux/hashtable.h line 47
Quoted 10 lines
include/linux/hashtable.h new file +10
-0+* same as hash_init_size. +* +* This has to be a macro since HASH_BITS() will not work on pointers since +* it calculates the size during preprocessing. +*/ +#define hash_init (hashtable) \ +({ \ + int __i; \ + \ + for (__i = 0; __i < HASH_BITS(hashtable); __i++) \I think this fails to initialize the whole table. You'd need
Quoted 1 line
HASH_BITS->HASH_SIZERight.
Unfortunately it's pretty hard catching something like this :/
Quoted 4 lines
Which brings the following question: how did you test this code ? It would be nice to have a small test module along with this patchset that stress-tests this simple hash table in various configurations (on stack, in data, etc).
I do two things:
Quoted 8 lines
- A small userspace test (since this header works just fine from
userspace as well).
- Build a kernel with all ~20 commits and stresstest it a bit, since
things like workqueue were converted, it finds issues pretty fast.I agree that there should be something similar to the list sort test we currently have, but I'm not sure if it should be in the scope of this initial patch.
Fair enough.
Quoted 7 lines
Quoted 6 lines
Also, I don't see how
hash_init()can be useful, sinceDEFINE_HASHTABLEalready initialize the array entries. If it is for dynamically allocated hash tables, this also won't work, considering the comment "This has to be a macro sinceHASH_BITS()will not work on pointers since it calculates the size during preprocessing."
Quoted 5 lines
hash_init()is actually used to clear the hashtable in two of the commits I've used to send along with this one. Since as you've said we now haveDEFINE_HASHTABLEandDECLARE_HASHTABLE, maybe it should be now calledhash_clear()or something similar. I don't have a strong opinion about this.
If it's used somewhere, then it's fine. People are used to "*_init" functions, so I don't think there is a point in renaming this to "clear".
Quoted 40 lines
Quoted 31 lines
Quoted 31 lines
include/linux/hashtable.h new file +30
-0+INIT_HLIST_HEAD (&hashtable[__i]); \ +}) + +/** +* hash_add - add an object to a hashtable +* @hashtable: hashtable to add to +* @node: the &struct hlist_node of the object to be added +* @key: the key of the object to be added +*/ +#define hash_add (hashtable, node, key) \ + hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]); + +/** +* hash_add_rcu - add an object to a rcu enabled hashtable +* @hashtable: hashtable to add to +* @node: the &struct hlist_node of the object to be added +* @key: the key of the object to be added +*/ +#define hash_add_rcu (hashtable, node, key) \ + hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]); + +/** +* hash_hashed - check whether an object is in any hashtable +* @node: the &struct hlist_node of the object to be checked +*/ +#define hash_hashed (node) (!hlist_unhashed(node)) + +/** +* hash_empty - check whether a hashtable is empty +* @hashtable: hashtable to check Quoted 8 lines
include/linux/hashtable.h line 41
Quoted 3 lines
include/linux/hashtable.h new file +3
-0+* +* This has to be a macro since HASH_BITS() will not work on pointers since +* it calculates the size during preprocessing. So I get that
hash_emptyis only expected to be used for statically defined hash tables ? Does it support hash tables in dynamically allocated memory ? On the stack ? If these are never expected to be supported, this should be documented.
Quoted 5 lines
Like the rest of the code, this hashtable implementation only works with non-dynamically allocated hashtables (on the stack/statically defined/etc are supported).
How would you create a dynamic hashtable with this code to begin with?
With a var. sized array in a structure, e.g.:
struct hashtable {
size_t len;
struct hlist_head t[];
};Then create a hash table allocation function, and turn both hash_empty and hash_init into functions that take a struct simplehash pointer as parameter. The downside is to consume extra space (especially because the array always has a power of 2 len), but the nice thing is that we could use this code with a kmalloc'd/vmalloc'd hash table.
I'm not saying we need to do it (due to the space consumption downside), but that we should at least document this limitation.
Thanks,
Mathieu
Quoted 4 lines
Thanks,
Sasha
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 8 lines · Mathieu Desnoyers
Quoted 1 line
How would you create a dynamic hashtable with this code to begin with?
With a var. sized array in a structure, e.g.:
struct hashtable { size_t len; struct hlist_head t[]; };
Quoted 8 lines
Then create a hash table allocation function, and turn both
hash_emptyandhash_initinto functions that take a struct simplehash pointer as parameter. The downside is to consume extra space (especially because the array always has a power of 2 len), but the nice thing is that we could use this code with a kmalloc'd/vmalloc'd hash table.I'm not saying we need to do it (due to the space consumption downside), but that we should at least document this limitation.
We've gone through the process of attempting to support dynamic hashtables in the previous versions of this patch, this turned to complicate the code a lot beyond simply changing the array of hlist_heads into the struct you proposed, so it was decided to not support dynamic hashtables at this point at all.
I thought we've agreed that non-dynamically allocated hashtables are widespread enough to have a dedicated abstraction of their own, and further hashtable implementations may introduce their own API for that.
We can ofcourse open that for discussion again, but I'd rather not go back and forth adding support for dynamic hashtables and removing it again.
Thanks,
Sasha