[v8,01/16] hashtable: introduce a small and naive hashtable

Commit Message

Sasha Levin Oct. 30, 2012, 6:45 p.m. UTC

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 <[e-mail]>
---

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

Comments

Mathieu Desnoyers Oct. 30, 2012, 7:19 p.m. UTC | #1

* Sasha Levin ([e-mail]) 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 <[e-mail]>

Reviewed-by: Mathieu Desnoyers <[e-mail]>

> ---
> 
> 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 <[e-mail]>
> + */
> +
> +#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
>

Tejun Heo Oct. 30, 2012, 9:42 p.m. UTC | #2

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 <[e-mail]>

Thanks.

Sasha Levin Oct. 31, 2012, 12:33 a.m. UTC | #3

On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo <[e-mail]> 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 <[e-mail]>
>
> Thanks.
>
> --
> tejun
--
To unsubscribe from this list: send the line "unsubscribe linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Jim Rees Oct. 31, 2012, 12:51 a.m. UTC | #4

Sasha Levin wrote:

  On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo <[e-mail]> 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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Sasha Levin Oct. 31, 2012, 1:15 a.m. UTC | #5

On Tue, Oct 30, 2012 at 8:51 PM, Jim Rees <[e-mail]> wrote:
> Sasha Levin wrote:
>
>   On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo <[e-mail]> 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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Steven Rostedt Oct. 31, 2012, 1:16 a.m. UTC | #6

On Tue, 2012-10-30 at 20:33 -0400, Sasha Levin wrote:
> On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo <[e-mail]> 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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Linus Torvalds Oct. 31, 2012, 1:25 a.m. UTC | #7

On Tue, Oct 30, 2012 at 6:16 PM, Steven Rostedt <[e-mail]> 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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Sasha Levin Oct. 31, 2012, 1:36 a.m. UTC | #8

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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Steven Rostedt Oct. 31, 2012, 1:36 a.m. UTC | #9

On Tue, 2012-10-30 at 18:25 -0700, Linus Torvalds wrote:
> On Tue, Oct 30, 2012 at 6:16 PM, Steven Rostedt <[e-mail]> 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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Linus Torvalds Oct. 31, 2012, 2:23 a.m. UTC | #10

On Tue, Oct 30, 2012 at 6:36 PM, Sasha Levin <[e-mail]> 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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Al Viro Oct. 31, 2012, 2:24 a.m. UTC | #11

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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Linus Torvalds Oct. 31, 2012, 2:48 a.m. UTC | #12

On Tue, Oct 30, 2012 at 7:24 PM, Al Viro <[e-mail]> 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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Al Viro Oct. 31, 2012, 3:24 a.m. UTC | #13

On Tue, Oct 30, 2012 at 07:48:19PM -0700, Linus Torvalds wrote:
> On Tue, Oct 30, 2012 at 7:24 PM, Al Viro <[e-mail]> 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>[e-mail], 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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Linus Torvalds Oct. 31, 2012, 3:48 a.m. UTC | #14

On Tue, Oct 30, 2012 at 8:24 PM, Al Viro <[e-mail]> 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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

David Laight Oct. 31, 2012, 9:46 a.m. UTC | #15

> > > 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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Sasha Levin Nov. 2, 2012, 4:23 a.m. UTC | #16

On Tue, Oct 30, 2012 at 10:23 PM, Linus Torvalds
<[e-mail]> wrote:
> On Tue, Oct 30, 2012 at 6:36 PM, Sasha Levin <[e-mail]> 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 linux-nfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch

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 <[e-mail]>
+ */
+
+#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