| Message ID | 1351622772-16400-1-git-send-email-levinsasha928@gmail.com |
|---|---|
| State | Not Applicable, archived |
| Delegated to: | David Miller |
| Headers | show |
* Sasha Levin (levinsasha928@gmail.com) 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 <levinsasha928@gmail.com> Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> > --- > > Changes from v8: > > - Addressed comments from Tejun Heo and Mathieu Desnoyers. > > > include/linux/hashtable.h | 196 ++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 196 insertions(+) > create mode 100644 include/linux/hashtable.h > > diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h > new file mode 100644 > index 0000000..3c1a9cb > --- /dev/null > +++ b/include/linux/hashtable.h > @@ -0,0 +1,196 @@ > +/* > + * Statically sized hash table implementation > + * (C) 2012 Sasha Levin <levinsasha928@gmail.com> > + */ > + > +#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[1 << (bits)] = \ > + { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT } > + > +#define DECLARE_HASHTABLE(name, bits) \ > + struct hlist_head name[1 << (bits)] > + > +#define HASH_SIZE(name) (ARRAY_SIZE(name)) > +#define HASH_BITS(name) ilog2(HASH_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); \ > +}) > + > +static inline void __hash_init(struct hlist_head *ht, unsigned int sz) > +{ > + unsigned int i; > + > + for (i = 0; i < sz; i++) > + INIT_HLIST_HEAD(&ht[i]); > +} > + > +/** > + * 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) __hash_init(hashtable, HASH_SIZE(hashtable)) > + > +/** > + * 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 > + */ > +static inline bool hash_hashed(struct hlist_node *node) > +{ > + return !hlist_unhashed(node); > +} > + > +static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz) > +{ > + unsigned int i; > + > + for (i = 0; i < sz; i++) > + if (!hlist_empty(&ht[i])) > + return false; > + > + return true; > +} > + > +/** > + * 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) __hash_empty(hashtable, HASH_SIZE(hashtable)) > + > +/** > + * 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 > -- > 1.7.12.4 >
Hello, Just some nitpicks. On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote: > +/* 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); \ > +}) Doesn't the above fit in 80 column. Why is it broken into multiple lines? Also, you probably want () around at least @val. In general, it's a good idea to add () around any macro argument to avoid nasty surprises. Looks good to me otherwise. Reviewed-by: Tejun Heo <tj@kernel.org> Thanks.
On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo <tj@kernel.org> wrote: > Hello, > > Just some nitpicks. > > On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote: >> +/* 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); \ >> +}) > > Doesn't the above fit in 80 column. Why is it broken into multiple > lines? Also, you probably want () around at least @val. In general, > it's a good idea to add () around any macro argument to avoid nasty > surprises. It was broken to multiple lines because it looks nicer that way (IMO). If we wrap it with () it's going to go over 80, so it's going to stay broken down either way :) Thanks, Sasha > Looks good to me otherwise. > > Reviewed-by: Tejun Heo <tj@kernel.org> > > Thanks. > > -- > tejun -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Sasha Levin wrote: On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo <tj@kernel.org> wrote: > Hello, > > Just some nitpicks. > > On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote: >> +/* 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); \ >> +}) > > Doesn't the above fit in 80 column. Why is it broken into multiple > lines? Also, you probably want () around at least @val. In general, > it's a good idea to add () around any macro argument to avoid nasty > surprises. It was broken to multiple lines because it looks nicer that way (IMO). If we wrap it with () it's going to go over 80, so it's going to stay broken down either way :) I would prefer the body be all on one line too. But shouldn't this be a static inline function? -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Oct 30, 2012 at 8:51 PM, Jim Rees <rees@umich.edu> wrote: > Sasha Levin wrote: > > On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo <tj@kernel.org> wrote: > > Hello, > > > > Just some nitpicks. > > > > On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote: > >> +/* 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); \ > >> +}) > > > > Doesn't the above fit in 80 column. Why is it broken into multiple > > lines? Also, you probably want () around at least @val. In general, > > it's a good idea to add () around any macro argument to avoid nasty > > surprises. > > It was broken to multiple lines because it looks nicer that way (IMO). > > If we wrap it with () it's going to go over 80, so it's going to stay > broken down either way :) > > I would prefer the body be all on one line too. But shouldn't this be a > static inline function? We want sizeof(val), which wouldn't work in a static inline. We can either wrap a static inline __hash_min() with a macro and pass that size to it, but that's quite an overkill here, or we can add a size parameter to hash_min(), but it would look awkward considering how hash_32()/hash_64()/hash_long() look like. Thanks, Sasha -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, 2012-10-30 at 20:33 -0400, Sasha Levin wrote: > On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo <tj@kernel.org> wrote: > > Hello, > > > > Just some nitpicks. > > > > On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote: > >> +/* 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); \ > >> +}) > > > > Doesn't the above fit in 80 column. Why is it broken into multiple > > lines? Also, you probably want () around at least @val. In general, > > it's a good idea to add () around any macro argument to avoid nasty > > surprises. > > It was broken to multiple lines because it looks nicer that way (IMO). > > If we wrap it with () it's going to go over 80, so it's going to stay > broken down either way :) ({ \ sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits); \ }) Is the better way to go. We are C programmers, we like to see the ?: on a single line if possible. The way you have it, looks like three statements run consecutively. -- Steve -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Oct 30, 2012 at 6:16 PM, Steven Rostedt <rostedt@goodmis.org> wrote: > > ({ \ > sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits); \ > }) > > Is the better way to go. We are C programmers, we like to see the ?: on > a single line if possible. The way you have it, looks like three > statements run consecutively. If we're C programmers, why use the non-standard statement-expression at all? And split it onto three lines when it's just a single one? But whatever. This series has gotten way too much bike-shedding anyway. I think it should just be applied, since it does remove lines of code overall. I'd even possibly apply it to mainline, but it seems to be against linux-next. Linus -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hi Linus, > But whatever. This series has gotten way too much bike-shedding > anyway. I think it should just be applied, since it does remove lines > of code overall. I'd even possibly apply it to mainline, but it seems > to be against linux-next. Yup, I switched to using -next because I've been running my trinity/KVM tools tests with it. I can either rebase that on top of mainline, or we can ask maintainers to take it to their own trees if you take only 01/16 into mainline. What would you prefer? Thanks, Sasha -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, 2012-10-30 at 18:25 -0700, Linus Torvalds wrote: > On Tue, Oct 30, 2012 at 6:16 PM, Steven Rostedt <rostedt@goodmis.org> wrote: > > > > ({ \ > > sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits); \ > > }) > > > > Is the better way to go. We are C programmers, we like to see the ?: on > > a single line if possible. The way you have it, looks like three > > statements run consecutively. > > If we're C programmers, why use the non-standard statement-expression > at all? And split it onto three lines when it's just a single one? I like the blue color over the pink. Anyway, I was just expressing an opinion and really didn't care if it was changed or not. > > But whatever. This series has gotten way too much bike-shedding > anyway. I think it should just be applied, since it does remove lines > of code overall. I'd even possibly apply it to mainline, but it seems > to be against linux-next. I would think this change is a bit too big for an -rc4 release, but you're the boss. I've already given my ack for my code that this set touches. Let it go to Stephen's repo then. -- Steve -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Oct 30, 2012 at 6:36 PM, Sasha Levin <levinsasha928@gmail.com> wrote: > > I can either rebase that on top of mainline, or we can ask maintainers > to take it to their own trees if you take only 01/16 into mainline. > What would you prefer? I don't really care deeply. The only reason to merge it now would be to avoid any pain with it during the next merge window. Just taking 01/16 might be the sanest way to do that, then the rest can trickle in independently at their own leisure. Linus -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Oct 30, 2012 at 06:25:46PM -0700, Linus Torvalds wrote: > But whatever. This series has gotten way too much bike-shedding > anyway. I think it should just be applied, since it does remove lines > of code overall. I'd even possibly apply it to mainline, but it seems > to be against linux-next. BTW, how serious have you been back at KS when you were talking about pull requests killing a thousand of lines of code being acceptable at any point in the cycle? Because right now I'm sitting on a pile that removes 2-3 times as much (~-2KLoC for stuff that got considerable testing for most of the architectures, -3KLoC if I include fork/clone/vfork unification series) and seeing how maintainers of a bunch of embedded architectures seem to be MIA... The idea of saying "screw them" and sending a pull request becomes more and more tempting every day ;-) -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Oct 30, 2012 at 7:24 PM, Al Viro <viro@zeniv.linux.org.uk> wrote: > > BTW, how serious have you been back at KS when you were talking about > pull requests killing a thousand of lines of code being acceptable > at any point in the cycle? Well... I'm absolutely a lot more open to pull requests that kill code than not, but I have to admit to being a bit more worried about stuff like your execve/fork patches that touch very low-level code. So I think I'll punt that for 3.8 anyway. Linus -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Oct 30, 2012 at 07:48:19PM -0700, Linus Torvalds wrote: > On Tue, Oct 30, 2012 at 7:24 PM, Al Viro <viro@zeniv.linux.org.uk> wrote: > > > > BTW, how serious have you been back at KS when you were talking about > > pull requests killing a thousand of lines of code being acceptable > > at any point in the cycle? > > Well... I'm absolutely a lot more open to pull requests that kill code > than not, but I have to admit to being a bit more worried about stuff > like your execve/fork patches that touch very low-level code. > > So I think I'll punt that for 3.8 anyway. Oh, well... there go my blackmail plans ;-) Seriously, though, I'm at loss regarding several embedded architectures - arch/score, in particular, seems to be completely orphaned. As far as I can see, it's * abandoned by hw vendor (seems like they were planning to push it game consoles, but that was just before the recession, and...) * abandoned by primary maintainer, who isn't employed by said hw vendor anymore, so his old address had been bouncy for several years. He had bothered to update it in gcc tree, but hadn't been active there either for almost as long. And new address in gcc tree is of form <name>+gcc@gmail.com, so using it for kernel-related mail would seem to be a lousy idea. * the second maintainer seems to be nearly MIA as well - all I can find is Acked-by on one commit. Cc'ed on the kernel_execve() thread, but... no signs of life whatsoever. * a lot of asm glue is in "apparently never worked" state, starting with ptrace hookup (it's clearly started its life as a mips clone, but uses different registers for passing return value, etc. TIF_SYSCALL_TRACE side of that thing still assumes MIPS ABI *and* is suffering obvious bitrot) Sigh... -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Oct 30, 2012 at 8:24 PM, Al Viro <viro@zeniv.linux.org.uk> wrote: > > Oh, well... there go my blackmail plans ;-) Seriously, though, I'm at loss > regarding several embedded architectures - arch/score, in particular, > seems to be completely orphaned. Don't worry about it. Do a best-effort, and if nobody ever reacts about some odd-ball architecture, whatever. We won't start deleting architectures over something like this, but it might be another sign down the road that some arch code can be removed entirely. So it's not arch/score I'd worry about. It's all the *other* architectures.. Linus -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
> > > On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote: > > >> +/* 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); \ > > >> +}) > > > > > > Doesn't the above fit in 80 column. Why is it broken into multiple > > > lines? Also, you probably want () around at least @val. In general, > > > it's a good idea to add () around any macro argument to avoid nasty > > > surprises. > > > > It was broken to multiple lines because it looks nicer that way (IMO). > > > > If we wrap it with () it's going to go over 80, so it's going to stay > > broken down either way :) > > ({ \ > sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits); \ > }) > > Is the better way to go. We are C programmers, we like to see the ?: on > a single line if possible. The way you have it, looks like three > statements run consecutively. To add some more colour (not color): In any case, this is a normal C #define, it doesn't need the {}. So it can just be: # define hash_min(val, bits) \ (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits)) I don't think that s/val/(val)/g and s/bits/(bits)/g are needed because the tokens are already ',' separated. I do actually wonder how many of these hash lists should be replaced with some kind of tree structure in order to get O(log(n)) searches. After all hashing is still O(n). (apologies if I mean o(n) not O(n) - it's a long time since I did my maths degree!) David -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Oct 30, 2012 at 10:23 PM, Linus Torvalds <torvalds@linux-foundation.org> wrote: > On Tue, Oct 30, 2012 at 6:36 PM, Sasha Levin <levinsasha928@gmail.com> wrote: >> >> I can either rebase that on top of mainline, or we can ask maintainers >> to take it to their own trees if you take only 01/16 into mainline. >> What would you prefer? > > I don't really care deeply. The only reason to merge it now would be > to avoid any pain with it during the next merge window. Just taking > 01/16 might be the sanest way to do that, then the rest can trickle in > independently at their own leisure. Okay, I'll keep working on converting everything else as soon as 01/16 makes it in your tree. Thanks, Sasha -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h new file mode 100644 index 0000000..3c1a9cb --- /dev/null +++ b/include/linux/hashtable.h @@ -0,0 +1,196 @@ +/* + * Statically sized hash table implementation + * (C) 2012 Sasha Levin <levinsasha928@gmail.com> + */ + +#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[1 << (bits)] = \ + { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT } + +#define DECLARE_HASHTABLE(name, bits) \ + struct hlist_head name[1 << (bits)] + +#define HASH_SIZE(name) (ARRAY_SIZE(name)) +#define HASH_BITS(name) ilog2(HASH_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); \ +}) + +static inline void __hash_init(struct hlist_head *ht, unsigned int sz) +{ + unsigned int i; + + for (i = 0; i < sz; i++) + INIT_HLIST_HEAD(&ht[i]); +} + +/** + * 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) __hash_init(hashtable, HASH_SIZE(hashtable)) + +/** + * 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 + */ +static inline bool hash_hashed(struct hlist_node *node) +{ + return !hlist_unhashed(node); +} + +static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz) +{ + unsigned int i; + + for (i = 0; i < sz; i++) + if (!hlist_empty(&ht[i])) + return false; + + return true; +} + +/** + * 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) __hash_empty(hashtable, HASH_SIZE(hashtable)) + +/** + * 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
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 <levinsasha928@gmail.com> --- Changes from v8: - Addressed comments from Tejun Heo and Mathieu Desnoyers. include/linux/hashtable.h | 196 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 196 insertions(+) create mode 100644 include/linux/hashtable.h