[v3,01/17] hashtable: introduce a small and naive hashtable

Commit Message

Sasha Levin Aug. 22, 2012, 2:26 a.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]>
---
 include/linux/hashtable.h |  291 +++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 291 insertions(+), 0 deletions(-)
 create mode 100644 include/linux/hashtable.h

Comments

Tejun Heo Aug. 22, 2012, 6:01 p.m. UTC | #1

Hello, Sasha.

On Wed, Aug 22, 2012 at 04:26:56AM +0200, Sasha Levin wrote:
> +#define DEFINE_HASHTABLE(name, bits)					\
> +	struct hlist_head name[HASH_SIZE(bits)];

Shouldn't this be something like the following?

#define DEFINE_HASHTABLE(name, bits)					\
	struct hlist_head name[HASH_SIZE(bits)] =			\
		{ [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT };

Also, given that the declaration isn't non-trivial, you'll probably
want a matching DECLARE_HASHTABLE() macro too.

> +/* 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)))

Why is the branching condition sizeof(val) == 4 instead of <= 4?
Also, no biggie but why isn't this macro in caps?

> +/**
> + * hash_add_size - add an object to a hashtable
> + * @hashtable: hashtable to add to
> + * @bits: bit count used for hashing
> + * @node: the &struct hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add_size(hashtable, bits, node, key)				\
> +	hlist_add_head(node, &hashtable[hash_min(key, bits)]);
> +
> +/**
> + * 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)						\
> +	hash_add_size(hashtable, HASH_BITS(hashtable), node, key)

It would be nice if the comments actually say something which can
differentiate the two.  Ditto for rcu variants.

> +/**
> + * hash_add_rcu_size - add an object to a rcu enabled hashtable
> + * @hashtable: hashtable to add to
> + * @bits: bit count used for hashing
> + * @node: the &struct hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add_rcu_size(hashtable, bits, node, key)				\
> +	hlist_add_head_rcu(node, &hashtable[hash_min(key, bits)]);
> +
> +/**
> + * 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)					\
> +	hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)

Or maybe we're better off with hash_head_size() and hash_head()?  I'll
expand on it later.  Please bear with me.

> +/**
> + * 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))

As the 'h' in hlist* stand for hash anyway and I think this type of
thin wrappers tend to obfuscate more than anything else.

> +/**
> + * 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);
> +}

If we do that, we can remove all these thin wrappers.

> +#define hash_for_each_size(name, bits, bkt, node, obj, member)			\
> +	for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)				\
> +		hlist_for_each_entry(obj, node, &name[bkt], member)
..
> +#define hash_for_each(name, bkt, node, obj, member)				\
> +	hash_for_each_size(name, HASH_BITS(name), bkt, node, obj, member)
...
> +#define hash_for_each_rcu_size(name, bits, bkt, node, obj, member)		\
> +	for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)				\
> +		hlist_for_each_entry_rcu(obj, node, &name[bkt], member)
...
> +#define hash_for_each_rcu(name, bkt, node, obj, member)				\
> +	hash_for_each_rcu_size(name, HASH_BITS(name), bkt, node, obj, member)
...
> +#define hash_for_each_safe_size(name, bits, bkt, node, tmp, obj, member)	\
> +	for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)                     	\
> +		hlist_for_each_entry_safe(obj, node, tmp, &name[bkt], member)
...
> +#define hash_for_each_safe(name, bkt, node, tmp, obj, member)			\
> +	hash_for_each_safe_size(name, HASH_BITS(name), bkt, node,		\
> +				tmp, obj, member)
...
> +#define hash_for_each_possible_size(name, obj, bits, node, member, key)		\
> +	hlist_for_each_entry(obj, node,	&name[hash_min(key, bits)], member)
...
> +#define hash_for_each_possible(name, obj, node, member, key)			\
> +	hash_for_each_possible_size(name, obj, HASH_BITS(name), node, member, key)
...
> +#define hash_for_each_possible_rcu_size(name, obj, bits, node, member, key)	\
> +	hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, bits)], member)
...
> +#define hash_for_each_possible_rcu(name, obj, node, member, key)		\
> +	hash_for_each_possible_rcu_size(name, obj, HASH_BITS(name),		\
...
> +#define hash_for_each_possible_safe_size(name, obj, bits, node, tmp, member, key)\
> +	hlist_for_each_entry_safe(obj, node, tmp,				\
> +		&name[hash_min(key, bits)], member)
...
> +#define hash_for_each_possible_safe(name, obj, node, tmp, member, key)		\
> +	hash_for_each_possible_safe_size(name, obj, HASH_BITS(name),		\

And also all these.  We'd only need hash_for_each_head() and
hash_head().  hash_for_each_possible*() could be nice for convenience,
I suppose.

I think the almost trivial nature of hlist hashtables makes this a bit
tricky and I'm not very sure but having this combinatory explosion is
a bit dazzling when the same functionality can be achieved by simply
combining operations which are already defined and named considering
hashtable.  I'm not feeling too strong about this tho.  What do others
think?

Also, can you please audit the comments on top of each macro?  They
have wrong names and don't differentiate the different variants very
well.

Thanks.

Ryan Mallon Aug. 22, 2012, 11:54 p.m. UTC | #2

On 23/08/12 04:01, Tejun Heo wrote:
> Hello, Sasha.
> 
> On Wed, Aug 22, 2012 at 04:26:56AM +0200, Sasha Levin wrote:
>> +#define DEFINE_HASHTABLE(name, bits)					\
>> +	struct hlist_head name[HASH_SIZE(bits)];
> 
> Shouldn't this be something like the following?
> 
> #define DEFINE_HASHTABLE(name, bits)					\
> 	struct hlist_head name[HASH_SIZE(bits)] =			\
> 		{ [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT };
> 
> Also, given that the declaration isn't non-trivial, you'll probably
> want a matching DECLARE_HASHTABLE() macro too.
> 
>> +/* 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)))
> 
> Why is the branching condition sizeof(val) == 4 instead of <= 4?
> Also, no biggie but why isn't this macro in caps?

It should probably use gcc's statement expression extensions to prevent
side-effect issues with the arguments:

  #define hash_min ({		\
	sizeof(val) <= 4 ?	\
	hash_32(val, bits) :	\
	hash_long(val, bits));	\
  })

~Ryan

--
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 Aug. 23, 2012, 12:24 a.m. UTC | #3

Hi Tejun,

On 08/22/2012 08:01 PM, Tejun Heo wrote:
> Hello, Sasha.
> 
> On Wed, Aug 22, 2012 at 04:26:56AM +0200, Sasha Levin wrote:
>> +#define DEFINE_HASHTABLE(name, bits)					\
>> +	struct hlist_head name[HASH_SIZE(bits)];
> 
> Shouldn't this be something like the following?
> 
> #define DEFINE_HASHTABLE(name, bits)					\
> 	struct hlist_head name[HASH_SIZE(bits)] =			\
> 		{ [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT };
> 
> Also, given that the declaration isn't non-trivial, you'll probably
> want a matching DECLARE_HASHTABLE() macro too.

I figured we might do a DEFINE_HASHTABLE() to prevent the need from using
hash_init() on hashtables defined this way, but I preferred not to since we may
end up wanting a more complex initialization (I'll explain why extensively below).

>> +/* 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)))
> 
> Why is the branching condition sizeof(val) == 4 instead of <= 4?

No reason, will fix.

> Also, no biggie but why isn't this macro in caps?

I had this plan in my mind to move it into linux/hash.h at some stage later, and
the API there uses low caps even for macros (hash_long()).

>> +/**
>> + * hash_add_rcu_size - add an object to a rcu enabled hashtable
>> + * @hashtable: hashtable to add to
>> + * @bits: bit count used for hashing
>> + * @node: the &struct hlist_node of the object to be added
>> + * @key: the key of the object to be added
>> + */
>> +#define hash_add_rcu_size(hashtable, bits, node, key)				\
>> +	hlist_add_head_rcu(node, &hashtable[hash_min(key, bits)]);
>> +
>> +/**
>> + * 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)					\
>> +	hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)
> 
> Or maybe we're better off with hash_head_size() and hash_head()?  I'll
> expand on it later.  Please bear with me.
> 
>> +/**
>> + * 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))
> 
> As the 'h' in hlist* stand for hash anyway and I think this type of
> thin wrappers tend to obfuscate more than anything else.
> 
>> +/**
>> + * 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);
>> +}
> 
> If we do that, we can remove all these thin wrappers.
> 
>> +#define hash_for_each_size(name, bits, bkt, node, obj, member)			\
>> +	for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)				\
>> +		hlist_for_each_entry(obj, node, &name[bkt], member)
> ..
>> +#define hash_for_each(name, bkt, node, obj, member)				\
>> +	hash_for_each_size(name, HASH_BITS(name), bkt, node, obj, member)
> ...
>> +#define hash_for_each_rcu_size(name, bits, bkt, node, obj, member)		\
>> +	for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)				\
>> +		hlist_for_each_entry_rcu(obj, node, &name[bkt], member)
> ...
>> +#define hash_for_each_rcu(name, bkt, node, obj, member)				\
>> +	hash_for_each_rcu_size(name, HASH_BITS(name), bkt, node, obj, member)
> ...
>> +#define hash_for_each_safe_size(name, bits, bkt, node, tmp, obj, member)	\
>> +	for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)                     	\
>> +		hlist_for_each_entry_safe(obj, node, tmp, &name[bkt], member)
> ...
>> +#define hash_for_each_safe(name, bkt, node, tmp, obj, member)			\
>> +	hash_for_each_safe_size(name, HASH_BITS(name), bkt, node,		\
>> +				tmp, obj, member)
> ...
>> +#define hash_for_each_possible_size(name, obj, bits, node, member, key)		\
>> +	hlist_for_each_entry(obj, node,	&name[hash_min(key, bits)], member)
> ...
>> +#define hash_for_each_possible(name, obj, node, member, key)			\
>> +	hash_for_each_possible_size(name, obj, HASH_BITS(name), node, member, key)
> ...
>> +#define hash_for_each_possible_rcu_size(name, obj, bits, node, member, key)	\
>> +	hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, bits)], member)
> ...
>> +#define hash_for_each_possible_rcu(name, obj, node, member, key)		\
>> +	hash_for_each_possible_rcu_size(name, obj, HASH_BITS(name),		\
> ...
>> +#define hash_for_each_possible_safe_size(name, obj, bits, node, tmp, member, key)\
>> +	hlist_for_each_entry_safe(obj, node, tmp,				\
>> +		&name[hash_min(key, bits)], member)
> ...
>> +#define hash_for_each_possible_safe(name, obj, node, tmp, member, key)		\
>> +	hash_for_each_possible_safe_size(name, obj, HASH_BITS(name),		\
> 
> And also all these.  We'd only need hash_for_each_head() and
> hash_head().  hash_for_each_possible*() could be nice for convenience,
> I suppose.
> 
> I think the almost trivial nature of hlist hashtables makes this a bit
> tricky and I'm not very sure but having this combinatory explosion is
> a bit dazzling when the same functionality can be achieved by simply
> combining operations which are already defined and named considering
> hashtable.  I'm not feeling too strong about this tho.  What do others
> think?

I'm thinking that this hashtable API will have 2 purposes: First, it would
prevent the excessive duplication of hashtable implementations all around the code.

Second, it will allow more easily interchangeable hashtable implementations to
find their way into the kernel. There are several maintainers who would be happy
to see dynamically sized RCU hashtable, and I'm guessing that several more
variants could be added based on needs in specific modules.

The second reason is why several things you've mentioned look the way they are:

 - No DEFINE_HASHTABLE(): I wanted to force the use of hash_init() since
initialization for other hashtables may be more complicated than the static
initialization for this implementation, which means that any place that used
DEFINE_HASHTABLE() and didn't do hash_init() will be buggy.

 - hash_hashed(): Different hashtable implementations may not use hlist, so
letting them assume that doing hlist operations on hashtable objects is wrong.

 - Lack of hash_head(): I didn't want to expose the internal structure of the
hashtable to the user. This might make it hard to implement hashtables that
resize themselves if we let the user hold a bucket in his hands.

I'm actually tempted in hiding hlist completely from hashtable users, probably
by simply defining a hash_head/hash_node on top of the hlist_ counterparts.

Now, I know that I mention a lot of these hashtables that might or might not be
added later on in the kernel, this is mostly due to the interest in dynamic
resizable hashtables which was shown during the RFC, and the fact that there is
a solid implementation of a dynamic RCU hashtable in urcu which might be a great
benefit in the kernel as well (I'm also looking at it while working on this
hashtable to verify that both could share an API in the future).

Regarding the amount of new macros, we can address this by splitting off any
dynamic elements into a new hashtable type. This will let us reduce quite a lot
of macros (removing all the _size() ones at least).

> Also, can you please audit the comments on top of each macro?  They
> have wrong names and don't differentiate the different variants very
> well.

Sure, sorry about that.

Thanks,
Sasha

> Thanks.
> 

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

Tejun Heo Aug. 23, 2012, 8:04 p.m. UTC | #4

Hello, Sasha.

On Thu, Aug 23, 2012 at 02:24:32AM +0200, Sasha Levin wrote:
> > I think the almost trivial nature of hlist hashtables makes this a bit
> > tricky and I'm not very sure but having this combinatory explosion is
> > a bit dazzling when the same functionality can be achieved by simply
> > combining operations which are already defined and named considering
> > hashtable.  I'm not feeling too strong about this tho.  What do others
> > think?
> 
> I'm thinking that this hashtable API will have 2 purposes: First, it would
> prevent the excessive duplication of hashtable implementations all around the code.
> 
> Second, it will allow more easily interchangeable hashtable implementations to
> find their way into the kernel. There are several maintainers who would be happy
> to see dynamically sized RCU hashtable, and I'm guessing that several more
> variants could be added based on needs in specific modules.
> 
> The second reason is why several things you've mentioned look the way they are:
> 
>  - No DEFINE_HASHTABLE(): I wanted to force the use of hash_init() since
> initialization for other hashtables may be more complicated than the static
> initialization for this implementation, which means that any place that used
> DEFINE_HASHTABLE() and didn't do hash_init() will be buggy.

I think this is problematic.  It looks exactly like other existing
DEFINE macros yet what its semantics is different.  I don't think
that's a good idea.

> I'm actually tempted in hiding hlist completely from hashtable users, probably
> by simply defining a hash_head/hash_node on top of the hlist_ counterparts.

I think that it would be best to keep this one simple & obvious, which
already has enough in-kernel users to justify its existence.  There
are significant benefits in being trivially understandable and
expectable.  If we want more advanced ones - say resizing, hybrid or
what not, let's make that a separate one.  No need to complicate the
common straight-forward case for that.

So, I think it would be best to keep this one as straight-forward and
trivial as possible.  Helper macros to help its users are fine but
let's please not go for full encapsulation.

Thanks.

Sasha Levin Aug. 24, 2012, 7:47 p.m. UTC | #5

On 08/23/2012 10:04 PM, Tejun Heo wrote:
> Hello, Sasha.
> 
> On Thu, Aug 23, 2012 at 02:24:32AM +0200, Sasha Levin wrote:
>>> I think the almost trivial nature of hlist hashtables makes this a bit
>>> tricky and I'm not very sure but having this combinatory explosion is
>>> a bit dazzling when the same functionality can be achieved by simply
>>> combining operations which are already defined and named considering
>>> hashtable.  I'm not feeling too strong about this tho.  What do others
>>> think?
>>
>> I'm thinking that this hashtable API will have 2 purposes: First, it would
>> prevent the excessive duplication of hashtable implementations all around the code.
>>
>> Second, it will allow more easily interchangeable hashtable implementations to
>> find their way into the kernel. There are several maintainers who would be happy
>> to see dynamically sized RCU hashtable, and I'm guessing that several more
>> variants could be added based on needs in specific modules.
>>
>> The second reason is why several things you've mentioned look the way they are:
>>
>>  - No DEFINE_HASHTABLE(): I wanted to force the use of hash_init() since
>> initialization for other hashtables may be more complicated than the static
>> initialization for this implementation, which means that any place that used
>> DEFINE_HASHTABLE() and didn't do hash_init() will be buggy.
> 
> I think this is problematic.  It looks exactly like other existing
> DEFINE macros yet what its semantics is different.  I don't think
> that's a good idea.

I can switch that to be DECLARE_HASHTABLE() if the issue is semantics.

>> I'm actually tempted in hiding hlist completely from hashtable users, probably
>> by simply defining a hash_head/hash_node on top of the hlist_ counterparts.
> 
> I think that it would be best to keep this one simple & obvious, which
> already has enough in-kernel users to justify its existence.  There
> are significant benefits in being trivially understandable and
> expectable.  If we want more advanced ones - say resizing, hybrid or
> what not, let's make that a separate one.  No need to complicate the
> common straight-forward case for that.
> 
> So, I think it would be best to keep this one as straight-forward and
> trivial as possible.  Helper macros to help its users are fine but
> let's please not go for full encapsulation.

What if we cut off the dynamic allocated (but not resizable) hashtable out for
the moment, and focus on the most common statically allocated hashtable case?

The benefits would be:

 - Getting rid of all the _size() macros, which will make the amount of helpers
here reasonable.
 - Dynamically allocated hashtable can be easily added as a separate
implementation using the same API. We already have some of those in the kernel...
 - When that's ready, I feel it's a shame to lose full encapsulation just due to
hash_hashed().


Thanks,
Sasha

> 
> Thanks.
> 

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

Tejun Heo Aug. 24, 2012, 7:59 p.m. UTC | #6

Hello, Sasha.

On Fri, Aug 24, 2012 at 09:47:19PM +0200, Sasha Levin wrote:
> > I think this is problematic.  It looks exactly like other existing
> > DEFINE macros yet what its semantics is different.  I don't think
> > that's a good idea.
> 
> I can switch that to be DECLARE_HASHTABLE() if the issue is semantics.

If this implementation is about the common trivial case, why not just
have the usual DECLARE/DEFINE_HASHTABLE() combination?

> > So, I think it would be best to keep this one as straight-forward and
> > trivial as possible.  Helper macros to help its users are fine but
> > let's please not go for full encapsulation.
> 
> What if we cut off the dynamic allocated (but not resizable) hashtable out for
> the moment, and focus on the most common statically allocated hashtable case?
> 
> The benefits would be:
> 
>  - Getting rid of all the _size() macros, which will make the amount of helpers
> here reasonable.
>  - Dynamically allocated hashtable can be easily added as a separate
> implementation using the same API. We already have some of those in the kernel...

It seems we have enough of this static usage and solving the static
case first shouldn't hinder the dynamic (!resize) case later, so,
yeah, sounds good to me.

>  - When that's ready, I feel it's a shame to lose full encapsulation just due to
> hash_hashed().

I don't know.  If we stick to the static (or even !resize dymaic)
straight-forward hash - and we need something like that - I don't see
what the full encapsulation buys us other than a lot of trivial
wrappers.

Thanks.

Sasha Levin Aug. 24, 2012, 8:11 p.m. UTC | #7

On 08/24/2012 09:59 PM, Tejun Heo wrote:
> Hello, Sasha.
> 
> On Fri, Aug 24, 2012 at 09:47:19PM +0200, Sasha Levin wrote:
>>> I think this is problematic.  It looks exactly like other existing
>>> DEFINE macros yet what its semantics is different.  I don't think
>>> that's a good idea.
>>
>> I can switch that to be DECLARE_HASHTABLE() if the issue is semantics.
> 
> If this implementation is about the common trivial case, why not just
> have the usual DECLARE/DEFINE_HASHTABLE() combination?

When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() look?

>>> So, I think it would be best to keep this one as straight-forward and
>>> trivial as possible.  Helper macros to help its users are fine but
>>> let's please not go for full encapsulation.
>>
>> What if we cut off the dynamic allocated (but not resizable) hashtable out for
>> the moment, and focus on the most common statically allocated hashtable case?
>>
>> The benefits would be:
>>
>>  - Getting rid of all the _size() macros, which will make the amount of helpers
>> here reasonable.
>>  - Dynamically allocated hashtable can be easily added as a separate
>> implementation using the same API. We already have some of those in the kernel...
> 
> It seems we have enough of this static usage and solving the static
> case first shouldn't hinder the dynamic (!resize) case later, so,
> yeah, sounds good to me.
> 
>>  - When that's ready, I feel it's a shame to lose full encapsulation just due to
>> hash_hashed().
> 
> I don't know.  If we stick to the static (or even !resize dymaic)
> straight-forward hash - and we need something like that - I don't see
> what the full encapsulation buys us other than a lot of trivial
> wrappers.

Which macros do you consider as trivial within the current API?

Basically this entire thing could be reduced to DEFINE/DECLARE_HASHTABLE and
get_bucket(), but it would make the life of anyone who wants a slightly
different hashtable a hell.

I think that right now the only real trivial wrapper is hash_hashed(), and I
think it's a price worth paying to have a single hashtable API instead of
fragmenting it when more implementations come along.

Thanks,
Sasha

> 
> Thanks.
> 

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

Tejun Heo Aug. 24, 2012, 8:33 p.m. UTC | #8

Hello, Sasha.

On Fri, Aug 24, 2012 at 10:11:55PM +0200, Sasha Levin wrote:
> > If this implementation is about the common trivial case, why not just
> > have the usual DECLARE/DEFINE_HASHTABLE() combination?
> 
> When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() look?

Hmmm?  DECLARE/DEFINE are usually for static ones.

> > I don't know.  If we stick to the static (or even !resize dymaic)
> > straight-forward hash - and we need something like that - I don't see
> > what the full encapsulation buys us other than a lot of trivial
> > wrappers.
> 
> Which macros do you consider as trivial within the current API?
> 
> Basically this entire thing could be reduced to DEFINE/DECLARE_HASHTABLE and
> get_bucket(), but it would make the life of anyone who wants a slightly
> different hashtable a hell.

Wouldn't the following be enough to get most of the benefits?

* DECLARE/DEFINE
* hash_head()
* hash_for_each_head()
* hash_add*()
* hash_for_each_possible*()

> I think that right now the only real trivial wrapper is hash_hashed(), and I
> think it's a price worth paying to have a single hashtable API instead of
> fragmenting it when more implementations come along.

I'm not objecting strongly against full encapsulation but having this
many thin wrappers makes me scratch my head.

Thanks.

Sasha Levin Aug. 24, 2012, 8:53 p.m. UTC | #9

On 08/24/2012 10:33 PM, Tejun Heo wrote:
> Hello, Sasha.
> 
> On Fri, Aug 24, 2012 at 10:11:55PM +0200, Sasha Levin wrote:
>>> If this implementation is about the common trivial case, why not just
>>> have the usual DECLARE/DEFINE_HASHTABLE() combination?
>>
>> When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() look?
> 
> Hmmm?  DECLARE/DEFINE are usually for static ones.

Yup, but we could be using the same API for dynamic non-resizable and static if
we go with the DECLARE/hash_init. We could switch between them (and other
implementations) without having to change the code.

>>> I don't know.  If we stick to the static (or even !resize dymaic)
>>> straight-forward hash - and we need something like that - I don't see
>>> what the full encapsulation buys us other than a lot of trivial
>>> wrappers.
>>
>> Which macros do you consider as trivial within the current API?
>>
>> Basically this entire thing could be reduced to DEFINE/DECLARE_HASHTABLE and
>> get_bucket(), but it would make the life of anyone who wants a slightly
>> different hashtable a hell.
> 
> Wouldn't the following be enough to get most of the benefits?
> 
> * DECLARE/DEFINE
> * hash_head()
> * hash_for_each_head()
> * hash_add*()
> * hash_for_each_possible*()
 * hash_for_each*() ?


Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place yet
that needed direct access to the bucket itself.

Consider the following list:

 - DECLARE
 - hash_init
 - hash_add
 - hash_del
 - hash_hashed
 - hash_for_each_[rcu, safe]
 - hash_for_each_possible[rcu, safe]

This basically means 11 macros/functions that would let us have full
encapsulation and will make it very easy for future implementations to work with
this API instead of making up a new one. It's also not significantly (+~2-3)
more than the ones you listed.

>> I think that right now the only real trivial wrapper is hash_hashed(), and I
>> think it's a price worth paying to have a single hashtable API instead of
>> fragmenting it when more implementations come along.
> 
> I'm not objecting strongly against full encapsulation but having this
> many thin wrappers makes me scratch my head.
> 
> Thanks.
> 

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

Tejun Heo Aug. 24, 2012, 9:23 p.m. UTC | #10

Hello,

On Fri, Aug 24, 2012 at 10:53:45PM +0200, Sasha Levin wrote:
> Yup, but we could be using the same API for dynamic non-resizable and static if
> we go with the DECLARE/hash_init. We could switch between them (and other
> implementations) without having to change the code.

I think it's better to stick with the usual conventions.

> > * DECLARE/DEFINE
> > * hash_head()
> > * hash_for_each_head()
> > * hash_add*()
> > * hash_for_each_possible*()
>  * hash_for_each*() ?
> 
> Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place yet
> that needed direct access to the bucket itself.

Because whole hash table walking is much less common and we can avoid
another full set of iterators.

> This basically means 11 macros/functions that would let us have full
> encapsulation and will make it very easy for future implementations to work with
> this API instead of making up a new one. It's also not significantly (+~2-3)
> more than the ones you listed.

I'm not sure whether full encapsulation is a good idea for trivial
hashtable.  For higher level stuff, sure but at this level I think
benefits coming from known obvious implementation can be larger.
e.g. suppose the caller knows certain entries to be way colder than
others and wants to put them at the end of the chain.

So, I think implmenting the minimal set of helpers which reflect the
underlying trivial implementation explicitly could actually be better
even when discounting the reduced number of wrappers.

Thanks.

Sasha Levin Aug. 24, 2012, 10:59 p.m. UTC | #11

>> Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place yet
>> that needed direct access to the bucket itself.
> 
> Because whole hash table walking is much less common and we can avoid
> another full set of iterators.

I don't agree. Out of 32 places which now use a hashtable iterator of some kind,
12 of them (38%) walk the entire table.

The thing is that usually data structures are indexable by more than one key, so
usually hashtables are fully walked in cold paths to look for different keys.

Take kernel/workqueue.c for example: There are 4 places which do a key lookup
(find_worker_executing_work()) and 3 places which fully walk the entire table
(for_each_busy_worker()).

>> This basically means 11 macros/functions that would let us have full
>> encapsulation and will make it very easy for future implementations to work with
>> this API instead of making up a new one. It's also not significantly (+~2-3)
>> more than the ones you listed.
> 
> I'm not sure whether full encapsulation is a good idea for trivial
> hashtable.  For higher level stuff, sure but at this level I think
> benefits coming from known obvious implementation can be larger.
> e.g. suppose the caller knows certain entries to be way colder than
> others and wants to put them at the end of the chain.

Thats the thing, the amount of things of things you can do with a given bucket
is very limited. You can't add entries to any point besides the head (without
walking the entire list).

Basically you can do only two things with a bucket:

 - Add something to it at a very specific place.
 - Walk it

So I don't understand whats the point in exposing the internal structure of the
hashtable if there's nothing significant that can be gained from it by the user.

> 
> So, I think implmenting the minimal set of helpers which reflect the
> underlying trivial implementation explicitly could actually be better
> even when discounting the reduced number of wrappers.
> 
> Thanks.
> 

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

Tejun Heo Aug. 24, 2012, 11:07 p.m. UTC | #12

Hello,

On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> Thats the thing, the amount of things of things you can do with a given bucket
> is very limited. You can't add entries to any point besides the head (without
> walking the entire list).

Kinda my point.  We already have all the hlist*() interface to deal
with such cases.  Having something which is evidently the trivial
hlist hashtable and advertises as such in the interface can be
helpful.  I think we need that more than we need anything fancy.

Heh, this is a debate about which one is less insignificant.  I can
see your point.  I'd really like to hear what others think on this.

Guys, do we want something which is evidently trivial hlist hashtable
which can use hlist_*() API directly or do we want something better
encapsulated?

Thanks.

Mathieu Desnoyers Aug. 25, 2012, 4:24 a.m. UTC | #13

* Tejun Heo ([e-mail]) wrote:
> Hello,
> 
> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> > Thats the thing, the amount of things of things you can do with a given bucket
> > is very limited. You can't add entries to any point besides the head (without
> > walking the entire list).
> 
> Kinda my point.  We already have all the hlist*() interface to deal
> with such cases.  Having something which is evidently the trivial
> hlist hashtable and advertises as such in the interface can be
> helpful.  I think we need that more than we need anything fancy.
> 
> Heh, this is a debate about which one is less insignificant.  I can
> see your point.  I'd really like to hear what others think on this.
> 
> Guys, do we want something which is evidently trivial hlist hashtable
> which can use hlist_*() API directly or do we want something better
> encapsulated?

My 2 cents, FWIW: I think this specific effort should target a trivially
understandable API and implementation, for use-cases where one would be
tempted to reimplement his own trivial hash table anyway. So here
exposing hlist internals, with which kernel developers are already
familiar, seems like a good approach in my opinion, because hiding stuff
behind new abstraction might make the target users go away.

Then, as we see the need, we can eventually merge a more elaborate hash
table with poneys and whatnot, but I would expect that the trivial hash
table implementation would still be useful. There are of course very
compelling reasons to use a more featureful hash table: automatic
resize, RT-aware updates, scalable updates, etc... but I see a purpose
for a trivial implementation. Its primary strong points being:

- it's trivially understandable, so anyone how want to be really sure
  they won't end up debugging the hash table instead of their
  work-in-progress code can have a full understanding of it,
- it has few dependencies, which makes it easier to understand and
  easier to use in some contexts (e.g. early boot).

So I'm in favor of not overdoing the abstraction for this trivial hash
table, and honestly I would rather prefer that this trivial hash table
stays trivial. A more elaborate hash table should probably come as a
separate API.

Thanks,

Mathieu

Sasha Levin Aug. 28, 2012, 9:56 a.m. UTC | #14

On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
> * Tejun Heo ([e-mail]) wrote:
>> Hello,
>>
>> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
>>> Thats the thing, the amount of things of things you can do with a given bucket
>>> is very limited. You can't add entries to any point besides the head (without
>>> walking the entire list).
>>
>> Kinda my point.  We already have all the hlist*() interface to deal
>> with such cases.  Having something which is evidently the trivial
>> hlist hashtable and advertises as such in the interface can be
>> helpful.  I think we need that more than we need anything fancy.
>>
>> Heh, this is a debate about which one is less insignificant.  I can
>> see your point.  I'd really like to hear what others think on this.
>>
>> Guys, do we want something which is evidently trivial hlist hashtable
>> which can use hlist_*() API directly or do we want something better
>> encapsulated?
> 
> My 2 cents, FWIW: I think this specific effort should target a trivially
> understandable API and implementation, for use-cases where one would be
> tempted to reimplement his own trivial hash table anyway. So here
> exposing hlist internals, with which kernel developers are already
> familiar, seems like a good approach in my opinion, because hiding stuff
> behind new abstraction might make the target users go away.
> 
> Then, as we see the need, we can eventually merge a more elaborate hash
> table with poneys and whatnot, but I would expect that the trivial hash
> table implementation would still be useful. There are of course very
> compelling reasons to use a more featureful hash table: automatic
> resize, RT-aware updates, scalable updates, etc... but I see a purpose
> for a trivial implementation. Its primary strong points being:
> 
> - it's trivially understandable, so anyone how want to be really sure
>   they won't end up debugging the hash table instead of their
>   work-in-progress code can have a full understanding of it,
> - it has few dependencies, which makes it easier to understand and
>   easier to use in some contexts (e.g. early boot).
> 
> So I'm in favor of not overdoing the abstraction for this trivial hash
> table, and honestly I would rather prefer that this trivial hash table
> stays trivial. A more elaborate hash table should probably come as a
> separate API.
> 
> Thanks,
> 
> Mathieu
> 

Alright, let's keep it simple then.

I do want to keep the hash_for_each[rcu,safe] family though.

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

Mathieu Desnoyers Aug. 28, 2012, 10:11 a.m. UTC | #15

* Sasha Levin ([e-mail]) wrote:
> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
> > * Tejun Heo ([e-mail]) wrote:
> >> Hello,
> >>
> >> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> >>> Thats the thing, the amount of things of things you can do with a given bucket
> >>> is very limited. You can't add entries to any point besides the head (without
> >>> walking the entire list).
> >>
> >> Kinda my point.  We already have all the hlist*() interface to deal
> >> with such cases.  Having something which is evidently the trivial
> >> hlist hashtable and advertises as such in the interface can be
> >> helpful.  I think we need that more than we need anything fancy.
> >>
> >> Heh, this is a debate about which one is less insignificant.  I can
> >> see your point.  I'd really like to hear what others think on this.
> >>
> >> Guys, do we want something which is evidently trivial hlist hashtable
> >> which can use hlist_*() API directly or do we want something better
> >> encapsulated?
> > 
> > My 2 cents, FWIW: I think this specific effort should target a trivially
> > understandable API and implementation, for use-cases where one would be
> > tempted to reimplement his own trivial hash table anyway. So here
> > exposing hlist internals, with which kernel developers are already
> > familiar, seems like a good approach in my opinion, because hiding stuff
> > behind new abstraction might make the target users go away.
> > 
> > Then, as we see the need, we can eventually merge a more elaborate hash
> > table with poneys and whatnot, but I would expect that the trivial hash
> > table implementation would still be useful. There are of course very
> > compelling reasons to use a more featureful hash table: automatic
> > resize, RT-aware updates, scalable updates, etc... but I see a purpose
> > for a trivial implementation. Its primary strong points being:
> > 
> > - it's trivially understandable, so anyone how want to be really sure
> >   they won't end up debugging the hash table instead of their
> >   work-in-progress code can have a full understanding of it,
> > - it has few dependencies, which makes it easier to understand and
> >   easier to use in some contexts (e.g. early boot).
> > 
> > So I'm in favor of not overdoing the abstraction for this trivial hash
> > table, and honestly I would rather prefer that this trivial hash table
> > stays trivial. A more elaborate hash table should probably come as a
> > separate API.
> > 
> > Thanks,
> > 
> > Mathieu
> > 
> 
> Alright, let's keep it simple then.
> 
> I do want to keep the hash_for_each[rcu,safe] family though.

Just a thought: if the API offered by the simple hash table focus on
providing a mechanism to find the hash bucket to which belongs the hash
chain containing the key looked up, and then expects the user to use the
hlist API to iterate on the chain (with or without the hlist _rcu
variant), then it might seem consistent that a helper providing
iteration over the entire table would actually just provide iteration on
all buckets, and let the user call the hlist for each iterator for each
node within the bucket, e.g.:

struct hlist_head *head;
struct hlist_node *pos;

hash_for_each_bucket(ht, head) {
        hlist_for_each(pos, head) {
                ...
        }
}

That way you only have to provide one single macro
(hash_for_each_bucket), and rely on the already existing:

- hlist_for_each_entry
- hlist_for_each_safe
- hlist_for_each_entry_rcu
- hlist_for_each_safe_rcu
  .....

and various flavors that can appear in the future without duplicating
this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
versions of the hash_for_each_bucket macro.

Thoughts ?

Thanks,

Mathieu

Sasha Levin Aug. 28, 2012, 11:27 a.m. UTC | #16

On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
> * Sasha Levin ([e-mail]) wrote:
>> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
>>> * Tejun Heo ([e-mail]) wrote:
>>>> Hello,
>>>>
>>>> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
>>>>> Thats the thing, the amount of things of things you can do with a given bucket
>>>>> is very limited. You can't add entries to any point besides the head (without
>>>>> walking the entire list).
>>>>
>>>> Kinda my point.  We already have all the hlist*() interface to deal
>>>> with such cases.  Having something which is evidently the trivial
>>>> hlist hashtable and advertises as such in the interface can be
>>>> helpful.  I think we need that more than we need anything fancy.
>>>>
>>>> Heh, this is a debate about which one is less insignificant.  I can
>>>> see your point.  I'd really like to hear what others think on this.
>>>>
>>>> Guys, do we want something which is evidently trivial hlist hashtable
>>>> which can use hlist_*() API directly or do we want something better
>>>> encapsulated?
>>>
>>> My 2 cents, FWIW: I think this specific effort should target a trivially
>>> understandable API and implementation, for use-cases where one would be
>>> tempted to reimplement his own trivial hash table anyway. So here
>>> exposing hlist internals, with which kernel developers are already
>>> familiar, seems like a good approach in my opinion, because hiding stuff
>>> behind new abstraction might make the target users go away.
>>>
>>> Then, as we see the need, we can eventually merge a more elaborate hash
>>> table with poneys and whatnot, but I would expect that the trivial hash
>>> table implementation would still be useful. There are of course very
>>> compelling reasons to use a more featureful hash table: automatic
>>> resize, RT-aware updates, scalable updates, etc... but I see a purpose
>>> for a trivial implementation. Its primary strong points being:
>>>
>>> - it's trivially understandable, so anyone how want to be really sure
>>>   they won't end up debugging the hash table instead of their
>>>   work-in-progress code can have a full understanding of it,
>>> - it has few dependencies, which makes it easier to understand and
>>>   easier to use in some contexts (e.g. early boot).
>>>
>>> So I'm in favor of not overdoing the abstraction for this trivial hash
>>> table, and honestly I would rather prefer that this trivial hash table
>>> stays trivial. A more elaborate hash table should probably come as a
>>> separate API.
>>>
>>> Thanks,
>>>
>>> Mathieu
>>>
>>
>> Alright, let's keep it simple then.
>>
>> I do want to keep the hash_for_each[rcu,safe] family though.
> 
> Just a thought: if the API offered by the simple hash table focus on
> providing a mechanism to find the hash bucket to which belongs the hash
> chain containing the key looked up, and then expects the user to use the
> hlist API to iterate on the chain (with or without the hlist _rcu
> variant), then it might seem consistent that a helper providing
> iteration over the entire table would actually just provide iteration on
> all buckets, and let the user call the hlist for each iterator for each
> node within the bucket, e.g.:
> 
> struct hlist_head *head;
> struct hlist_node *pos;
> 
> hash_for_each_bucket(ht, head) {
>         hlist_for_each(pos, head) {
>                 ...
>         }
> }
> 
> That way you only have to provide one single macro
> (hash_for_each_bucket), and rely on the already existing:
> 
> - hlist_for_each_entry
> - hlist_for_each_safe
> - hlist_for_each_entry_rcu
> - hlist_for_each_safe_rcu
>   .....
> 
> and various flavors that can appear in the future without duplicating
> this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
> versions of the hash_for_each_bucket macro.
> 
> Thoughts ?

In my opinion, the downside here is that it'll require 2 function calls and 2
levels of nesting for a simple hash iteration.

hash_for_each_bucket() will always be followed by an iteration of that bucket,
so splitting a hash_for_each() which does both into 2 different functions which
will almost always must be called in that given order sounds unintuitive to me.

It's also just 3 different possible iterators:

 - hlist_for_each_entry
 - hlist_for_each_entry_safe
 - hlist_for_each_entry_rcu

So I think that it's a good price to pay - 2 extra macro definitions in the
header to save a macro call + nesting level in each place that uses a hashtable.


Thanks,
Sasha

> Thanks,
> 
> Mathieu
> 

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

Mathieu Desnoyers Aug. 28, 2012, 11:56 a.m. UTC | #17

* Sasha Levin ([e-mail]) wrote:
> On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
> > * Sasha Levin ([e-mail]) wrote:
> >> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
> >>> * Tejun Heo ([e-mail]) wrote:
> >>>> Hello,
> >>>>
> >>>> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> >>>>> Thats the thing, the amount of things of things you can do with a given bucket
> >>>>> is very limited. You can't add entries to any point besides the head (without
> >>>>> walking the entire list).
> >>>>
> >>>> Kinda my point.  We already have all the hlist*() interface to deal
> >>>> with such cases.  Having something which is evidently the trivial
> >>>> hlist hashtable and advertises as such in the interface can be
> >>>> helpful.  I think we need that more than we need anything fancy.
> >>>>
> >>>> Heh, this is a debate about which one is less insignificant.  I can
> >>>> see your point.  I'd really like to hear what others think on this.
> >>>>
> >>>> Guys, do we want something which is evidently trivial hlist hashtable
> >>>> which can use hlist_*() API directly or do we want something better
> >>>> encapsulated?
> >>>
> >>> My 2 cents, FWIW: I think this specific effort should target a trivially
> >>> understandable API and implementation, for use-cases where one would be
> >>> tempted to reimplement his own trivial hash table anyway. So here
> >>> exposing hlist internals, with which kernel developers are already
> >>> familiar, seems like a good approach in my opinion, because hiding stuff
> >>> behind new abstraction might make the target users go away.
> >>>
> >>> Then, as we see the need, we can eventually merge a more elaborate hash
> >>> table with poneys and whatnot, but I would expect that the trivial hash
> >>> table implementation would still be useful. There are of course very
> >>> compelling reasons to use a more featureful hash table: automatic
> >>> resize, RT-aware updates, scalable updates, etc... but I see a purpose
> >>> for a trivial implementation. Its primary strong points being:
> >>>
> >>> - it's trivially understandable, so anyone how want to be really sure
> >>>   they won't end up debugging the hash table instead of their
> >>>   work-in-progress code can have a full understanding of it,
> >>> - it has few dependencies, which makes it easier to understand and
> >>>   easier to use in some contexts (e.g. early boot).
> >>>
> >>> So I'm in favor of not overdoing the abstraction for this trivial hash
> >>> table, and honestly I would rather prefer that this trivial hash table
> >>> stays trivial. A more elaborate hash table should probably come as a
> >>> separate API.
> >>>
> >>> Thanks,
> >>>
> >>> Mathieu
> >>>
> >>
> >> Alright, let's keep it simple then.
> >>
> >> I do want to keep the hash_for_each[rcu,safe] family though.
> > 
> > Just a thought: if the API offered by the simple hash table focus on
> > providing a mechanism to find the hash bucket to which belongs the hash
> > chain containing the key looked up, and then expects the user to use the
> > hlist API to iterate on the chain (with or without the hlist _rcu
> > variant), then it might seem consistent that a helper providing
> > iteration over the entire table would actually just provide iteration on
> > all buckets, and let the user call the hlist for each iterator for each
> > node within the bucket, e.g.:
> > 
> > struct hlist_head *head;
> > struct hlist_node *pos;
> > 
> > hash_for_each_bucket(ht, head) {
> >         hlist_for_each(pos, head) {
> >                 ...
> >         }
> > }
> > 
> > That way you only have to provide one single macro
> > (hash_for_each_bucket), and rely on the already existing:
> > 
> > - hlist_for_each_entry
> > - hlist_for_each_safe
> > - hlist_for_each_entry_rcu
> > - hlist_for_each_safe_rcu
> >   .....
> > 
> > and various flavors that can appear in the future without duplicating
> > this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
> > versions of the hash_for_each_bucket macro.
> > 
> > Thoughts ?
> 
> In my opinion, the downside here is that it'll require 2 function calls and 2
> levels of nesting for a simple hash iteration.

Those are macros, not functions. No function call is required. But I see
your point about nesting.

> 
> hash_for_each_bucket() will always be followed by an iteration of that
> bucket, so splitting a hash_for_each() which does both into 2
> different functions which will almost always must be called in that
> given order sounds unintuitive to me.
> 
> It's also just 3 different possible iterators:
> 
>  - hlist_for_each_entry
>  - hlist_for_each_entry_safe
>  - hlist_for_each_entry_rcu
> 
> So I think that it's a good price to pay - 2 extra macro definitions
> in the header to save a macro call + nesting level in each place that
> uses a hashtable.

I must admin I don't care that much one way or another.

Thanks,

Mathieu

> 
> 
> Thanks,
> Sasha
> 
> > Thanks,
> > 
> > Mathieu
> > 
>

Mathieu Desnoyers Aug. 28, 2012, 11 p.m. UTC | #18

* Mathieu Desnoyers ([e-mail]) wrote:
> * Sasha Levin ([e-mail]) wrote:
> > On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
> > > * Sasha Levin ([e-mail]) wrote:
> > >> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
> > >>> * Tejun Heo ([e-mail]) wrote:
> > >>>> Hello,
> > >>>>
> > >>>> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> > >>>>> Thats the thing, the amount of things of things you can do with a given bucket
> > >>>>> is very limited. You can't add entries to any point besides the head (without
> > >>>>> walking the entire list).
> > >>>>
> > >>>> Kinda my point.  We already have all the hlist*() interface to deal
> > >>>> with such cases.  Having something which is evidently the trivial
> > >>>> hlist hashtable and advertises as such in the interface can be
> > >>>> helpful.  I think we need that more than we need anything fancy.
> > >>>>
> > >>>> Heh, this is a debate about which one is less insignificant.  I can
> > >>>> see your point.  I'd really like to hear what others think on this.
> > >>>>
> > >>>> Guys, do we want something which is evidently trivial hlist hashtable
> > >>>> which can use hlist_*() API directly or do we want something better
> > >>>> encapsulated?
> > >>>
> > >>> My 2 cents, FWIW: I think this specific effort should target a trivially
> > >>> understandable API and implementation, for use-cases where one would be
> > >>> tempted to reimplement his own trivial hash table anyway. So here
> > >>> exposing hlist internals, with which kernel developers are already
> > >>> familiar, seems like a good approach in my opinion, because hiding stuff
> > >>> behind new abstraction might make the target users go away.
> > >>>
> > >>> Then, as we see the need, we can eventually merge a more elaborate hash
> > >>> table with poneys and whatnot, but I would expect that the trivial hash
> > >>> table implementation would still be useful. There are of course very
> > >>> compelling reasons to use a more featureful hash table: automatic
> > >>> resize, RT-aware updates, scalable updates, etc... but I see a purpose
> > >>> for a trivial implementation. Its primary strong points being:
> > >>>
> > >>> - it's trivially understandable, so anyone how want to be really sure
> > >>>   they won't end up debugging the hash table instead of their
> > >>>   work-in-progress code can have a full understanding of it,
> > >>> - it has few dependencies, which makes it easier to understand and
> > >>>   easier to use in some contexts (e.g. early boot).
> > >>>
> > >>> So I'm in favor of not overdoing the abstraction for this trivial hash
> > >>> table, and honestly I would rather prefer that this trivial hash table
> > >>> stays trivial. A more elaborate hash table should probably come as a
> > >>> separate API.
> > >>>
> > >>> Thanks,
> > >>>
> > >>> Mathieu
> > >>>
> > >>
> > >> Alright, let's keep it simple then.
> > >>
> > >> I do want to keep the hash_for_each[rcu,safe] family though.
> > > 
> > > Just a thought: if the API offered by the simple hash table focus on
> > > providing a mechanism to find the hash bucket to which belongs the hash
> > > chain containing the key looked up, and then expects the user to use the
> > > hlist API to iterate on the chain (with or without the hlist _rcu
> > > variant), then it might seem consistent that a helper providing
> > > iteration over the entire table would actually just provide iteration on
> > > all buckets, and let the user call the hlist for each iterator for each
> > > node within the bucket, e.g.:
> > > 
> > > struct hlist_head *head;
> > > struct hlist_node *pos;
> > > 
> > > hash_for_each_bucket(ht, head) {
> > >         hlist_for_each(pos, head) {
> > >                 ...
> > >         }
> > > }
> > > 
> > > That way you only have to provide one single macro
> > > (hash_for_each_bucket), and rely on the already existing:
> > > 
> > > - hlist_for_each_entry
> > > - hlist_for_each_safe
> > > - hlist_for_each_entry_rcu
> > > - hlist_for_each_safe_rcu
> > >   .....
> > > 
> > > and various flavors that can appear in the future without duplicating
> > > this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
> > > versions of the hash_for_each_bucket macro.
> > > 
> > > Thoughts ?
> > 
> > In my opinion, the downside here is that it'll require 2 function calls and 2
> > levels of nesting for a simple hash iteration.
> 
> Those are macros, not functions. No function call is required. But I see
> your point about nesting.
> 
> > 
> > hash_for_each_bucket() will always be followed by an iteration of that
> > bucket, so splitting a hash_for_each() which does both into 2
> > different functions which will almost always must be called in that
> > given order sounds unintuitive to me.
> > 
> > It's also just 3 different possible iterators:
> > 
> >  - hlist_for_each_entry
> >  - hlist_for_each_entry_safe
> >  - hlist_for_each_entry_rcu
> > 
> > So I think that it's a good price to pay - 2 extra macro definitions
> > in the header to save a macro call + nesting level in each place that
> > uses a hashtable.
> 
> I must admin I don't care that much one way or another.

Looking again at:

+#define hash_for_each_size(name, bits, bkt, node, obj, member)                 \
+       for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)                             \
+               hlist_for_each_entry(obj, node, &name[bkt], member)

you will notice that a "break" or "continue" in the inner loop will not
affect the outer loop, which is certainly not what the programmer would
expect!

I advise strongly against creating such error-prone construct.

Thanks,

Mathieu



> 
> Thanks,
> 
> Mathieu
> 
> > 
> > 
> > Thanks,
> > Sasha
> > 
> > > Thanks,
> > > 
> > > Mathieu
> > > 
> > 
> 
> -- 
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com

Steven Rostedt Sept. 4, 2012, 3:35 p.m. UTC | #19

On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:

> Looking again at:
> 
> +#define hash_for_each_size(name, bits, bkt, node, obj, member)                 \
> +       for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)                             \
> +               hlist_for_each_entry(obj, node, &name[bkt], member)
> 
> you will notice that a "break" or "continue" in the inner loop will not
> affect the outer loop, which is certainly not what the programmer would
> expect!
> 
> I advise strongly against creating such error-prone construct.
> 

A few existing loop macros do this. But they require a do { } while ()
approach, and all have a comment.

It's used by do_each_thread() in sched.h and ftrace does this as well.
Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().

Yes it breaks 'break' but it does not break 'continue' as it would just
go to the next item that would have been found (like a normal for
would).

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

Pedro Alves Sept. 4, 2012, 4:30 p.m. UTC | #20

On 09/04/2012 04:35 PM, Steven Rostedt wrote:
> On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
> 
>> Looking again at:
>>
>> +#define hash_for_each_size(name, bits, bkt, node, obj, member)                 \
>> +       for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)                             \
>> +               hlist_for_each_entry(obj, node, &name[bkt], member)
>>
>> you will notice that a "break" or "continue" in the inner loop will not
>> affect the outer loop, which is certainly not what the programmer would
>> expect!
>>
>> I advise strongly against creating such error-prone construct.
>>
> 
> A few existing loop macros do this. But they require a do { } while ()
> approach, and all have a comment.
> 
> It's used by do_each_thread() in sched.h and ftrace does this as well.
> Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().
> 
> Yes it breaks 'break' but it does not break 'continue' as it would just
> go to the next item that would have been found (like a normal for
> would).

/*
 * This is a double for. Do not use 'break' to break out of the loop,
 * you must use a goto.
 */
#define do_for_each_ftrace_rec(pg, rec)                                 \
        for (pg = ftrace_pages_start; pg; pg = pg->next) {              \
                int _____i;                                             \
                for (_____i = 0; _____i < pg->index; _____i++) {        \
                        rec = &pg->records[_____i];



You can make 'break' also work as expected if you can embed a little knowledge
of the inner loop's condition in the outer loop's condition.  Sometimes it's
trivial, most often when the inner loop's iterator is a pointer that goes
NULL at the end, but other times not so much.  Something like (completely untested):

#define do_for_each_ftrace_rec(pg, rec)                                 \
        for (pg = ftrace_pages_start, rec = &pg->records[pg->index];    \
             pg && rec == &pg->records[pg->index];                      \
             pg = pg->next) {                                           \
                int _____i;                                             \
                for (_____i = 0; _____i < pg->index; _____i++) {        \
                        rec = &pg->records[_____i];

(other variants possible)

IOW, the outer loop only iterates if the inner loop completes.  If there's
a break in the inner loop, then the outer loop breaks too.  Of course, it
all depends on whether the generated code looks sane or hideous, if
the uses of the macro care for it over bug avoidance.

Mathieu Desnoyers Sept. 4, 2012, 4:32 p.m. UTC | #21

* Steven Rostedt ([e-mail]) wrote:
> On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
> 
> > Looking again at:
> > 
> > +#define hash_for_each_size(name, bits, bkt, node, obj, member)                 \
> > +       for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)                             \
> > +               hlist_for_each_entry(obj, node, &name[bkt], member)
> > 
> > you will notice that a "break" or "continue" in the inner loop will not
> > affect the outer loop, which is certainly not what the programmer would
> > expect!
> > 
> > I advise strongly against creating such error-prone construct.
> > 
> 
> A few existing loop macros do this. But they require a do { } while ()
> approach, and all have a comment.
> 
> It's used by do_each_thread() in sched.h 

Yes. It's worth noting that it is a do_each_thread() /
while_each_thread() pair.


> and ftrace does this as well.
> Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().

Same here.

> 
> Yes it breaks 'break' but it does not break 'continue' as it would just
> go to the next item that would have been found (like a normal for
> would).

Good point.

So would changing hash_for_each_size() to a

do_each_hash_size()/while_each_hash_size() make it clearer that this
contains a double-loop ? (along with an appropriate comment about
break).

Thanks,

Mathieu

> 
> -- Steve
> 
>

Pedro Alves Sept. 4, 2012, 4:40 p.m. UTC | #22

On 09/04/2012 05:30 PM, Pedro Alves wrote:
> On 09/04/2012 04:35 PM, Steven Rostedt wrote:
>> On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
>>
>>> Looking again at:
>>>
>>> +#define hash_for_each_size(name, bits, bkt, node, obj, member)                 \
>>> +       for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)                             \
>>> +               hlist_for_each_entry(obj, node, &name[bkt], member)
>>>
>>> you will notice that a "break" or "continue" in the inner loop will not
>>> affect the outer loop, which is certainly not what the programmer would
>>> expect!
>>>
>>> I advise strongly against creating such error-prone construct.
>>>
>>
>> A few existing loop macros do this. But they require a do { } while ()
>> approach, and all have a comment.
>>
>> It's used by do_each_thread() in sched.h and ftrace does this as well.
>> Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().
>>
>> Yes it breaks 'break' but it does not break 'continue' as it would just
>> go to the next item that would have been found (like a normal for
>> would).
> 
> /*
>  * This is a double for. Do not use 'break' to break out of the loop,
>  * you must use a goto.
>  */
> #define do_for_each_ftrace_rec(pg, rec)                                 \
>         for (pg = ftrace_pages_start; pg; pg = pg->next) {              \
>                 int _____i;                                             \
>                 for (_____i = 0; _____i < pg->index; _____i++) {        \
>                         rec = &pg->records[_____i];
> 
> 
> 
> You can make 'break' also work as expected if you can embed a little knowledge
> of the inner loop's condition in the outer loop's condition.  Sometimes it's
> trivial, most often when the inner loop's iterator is a pointer that goes
> NULL at the end, but other times not so much.  Something like (completely untested):
> 
> #define do_for_each_ftrace_rec(pg, rec)                                 \
>         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];    \
>              pg && rec == &pg->records[pg->index];                      \
>              pg = pg->next) {                                           \
>                 int _____i;                                             \
>                 for (_____i = 0; _____i < pg->index; _____i++) {        \
>                         rec = &pg->records[_____i];
>
> 
> (other variants possible)
> 
> IOW, the outer loop only iterates if the inner loop completes.  If there's
> a break in the inner loop, then the outer loop breaks too.  Of course, it
> all depends on whether the generated code looks sane or hideous, if
> the uses of the macro care for it over bug avoidance.
> 

BTW, you can also go a step further and remove the need to close with double }},
with something like:

#define do_for_each_ftrace_rec(pg, rec)                                          \
        for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
             pg && rec == &pg->records[pg->index];                               \
             pg = pg->next)                                                      \
          for (rec = pg->records; rec < &pg->records[pg->index]; rec++)

Mathieu Desnoyers Sept. 4, 2012, 5:01 p.m. UTC | #23

* Pedro Alves ([e-mail]) wrote:
> On 09/04/2012 05:30 PM, Pedro Alves wrote:
> > On 09/04/2012 04:35 PM, Steven Rostedt wrote:
> >> On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
> >>
> >>> Looking again at:
> >>>
> >>> +#define hash_for_each_size(name, bits, bkt, node, obj, member)                 \
> >>> +       for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)                             \
> >>> +               hlist_for_each_entry(obj, node, &name[bkt], member)
> >>>
> >>> you will notice that a "break" or "continue" in the inner loop will not
> >>> affect the outer loop, which is certainly not what the programmer would
> >>> expect!
> >>>
> >>> I advise strongly against creating such error-prone construct.
> >>>
> >>
> >> A few existing loop macros do this. But they require a do { } while ()
> >> approach, and all have a comment.
> >>
> >> It's used by do_each_thread() in sched.h and ftrace does this as well.
> >> Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().
> >>
> >> Yes it breaks 'break' but it does not break 'continue' as it would just
> >> go to the next item that would have been found (like a normal for
> >> would).
> > 
> > /*
> >  * This is a double for. Do not use 'break' to break out of the loop,
> >  * you must use a goto.
> >  */
> > #define do_for_each_ftrace_rec(pg, rec)                                 \
> >         for (pg = ftrace_pages_start; pg; pg = pg->next) {              \
> >                 int _____i;                                             \
> >                 for (_____i = 0; _____i < pg->index; _____i++) {        \
> >                         rec = &pg->records[_____i];
> > 
> > 
> > 
> > You can make 'break' also work as expected if you can embed a little knowledge
> > of the inner loop's condition in the outer loop's condition.  Sometimes it's
> > trivial, most often when the inner loop's iterator is a pointer that goes
> > NULL at the end, but other times not so much.  Something like (completely untested):
> > 
> > #define do_for_each_ftrace_rec(pg, rec)                                 \
> >         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];    \
> >              pg && rec == &pg->records[pg->index];                      \
> >              pg = pg->next) {                                           \
> >                 int _____i;                                             \
> >                 for (_____i = 0; _____i < pg->index; _____i++) {        \
> >                         rec = &pg->records[_____i];
> >
> > 
> > (other variants possible)
> > 
> > IOW, the outer loop only iterates if the inner loop completes.  If there's
> > a break in the inner loop, then the outer loop breaks too.  Of course, it
> > all depends on whether the generated code looks sane or hideous, if
> > the uses of the macro care for it over bug avoidance.
> > 
> 
> BTW, you can also go a step further and remove the need to close with double }},
> with something like:
> 
> #define do_for_each_ftrace_rec(pg, rec)                                          \
>         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
>              pg && rec == &pg->records[pg->index];                               \
>              pg = pg->next)                                                      \
>           for (rec = pg->records; rec < &pg->records[pg->index]; rec++)

Maybe in some cases there might be ways to combine the two loops into
one ? I'm not seeing exactly how to do it for this one, but it should
not be impossible. If the inner loop condition can be moved to the outer
loop, and if we use (blah ? loop1_conf : loop2_cond) to test for
different conditions depending on the context, and do the same for the
3rd argument of the for() loop. The details elude me for now though, so
maybe it's complete non-sense ;)

It might not be that useful for do_for_each_ftrace_rec, but if we can do
it for the hash table iterator, it might be worth it.

Thanks,

Mathieu

Steven Rostedt Sept. 4, 2012, 5:17 p.m. UTC | #24

On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:

> BTW, you can also go a step further and remove the need to close with double }},
> with something like:
> 
> #define do_for_each_ftrace_rec(pg, rec)                                          \
>         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
>              pg && rec == &pg->records[pg->index];                               \
>              pg = pg->next)                                                      \
>           for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
> 

Yeah, but why bother? It's hidden in a macro, and the extra '{ }' shows
that this is something "special".

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

Pedro Alves Sept. 4, 2012, 5:21 p.m. UTC | #25

On 09/04/2012 06:17 PM, Steven Rostedt wrote:
> On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
> 
>> BTW, you can also go a step further and remove the need to close with double }},
>> with something like:
>>
>> #define do_for_each_ftrace_rec(pg, rec)                                          \
>>         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
>>              pg && rec == &pg->records[pg->index];                               \
>>              pg = pg->next)                                                      \
>>           for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
>>
> 
> Yeah, but why bother? It's hidden in a macro, and the extra '{ }' shows
> that this is something "special".

The point of both changes is that there's nothing special in the end
at all.  It all just works...

Steven Rostedt Sept. 4, 2012, 8:59 p.m. UTC | #26

On Tue, 2012-09-04 at 18:21 +0100, Pedro Alves wrote:
> On 09/04/2012 06:17 PM, Steven Rostedt wrote:
> > On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
> > 
> >> BTW, you can also go a step further and remove the need to close with double }},
> >> with something like:
> >>
> >> #define do_for_each_ftrace_rec(pg, rec)                                          \
> >>         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
> >>              pg && rec == &pg->records[pg->index];                               \
> >>              pg = pg->next)                                                      \
> >>           for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
> >>
> > 
> > Yeah, but why bother? It's hidden in a macro, and the extra '{ }' shows
> > that this is something "special".
> 
> The point of both changes is that there's nothing special in the end
> at all.  It all just works...
> 

It would still fail on a 'break'. The 'while' macro tells us that it is
special, because in the end, it wont work.

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

Pedro Alves Sept. 4, 2012, 9:51 p.m. UTC | #27

On 09/04/2012 09:59 PM, Steven Rostedt wrote:
> On Tue, 2012-09-04 at 18:21 +0100, Pedro Alves wrote:
>> On 09/04/2012 06:17 PM, Steven Rostedt wrote:
>>> On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
>>>
>>>> BTW, you can also go a step further and remove the need to close with double }},
>>>> with something like:
>>>>
>>>> #define do_for_each_ftrace_rec(pg, rec)                                          \
>>>>         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
>>>>              pg && rec == &pg->records[pg->index];                               \
>>>>              pg = pg->next)                                                      \
>>>>           for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
>>>>
>>>
>>> Yeah, but why bother? It's hidden in a macro, and the extra '{ }' shows
>>> that this is something "special".
>>
>> The point of both changes is that there's nothing special in the end
>> at all.  It all just works...
>>
> 
> It would still fail on a 'break'. The 'while' macro tells us that it is
> special, because in the end, it wont work.

Please explain why it would fail on a 'break'.

Steven Rostedt Sept. 4, 2012, 10:41 p.m. UTC | #28

On Tue, 2012-09-04 at 22:51 +0100, Pedro Alves wrote:
> On 09/04/2012 09:59 PM, Steven Rostedt wrote:
> > On Tue, 2012-09-04 at 18:21 +0100, Pedro Alves wrote:
> >> On 09/04/2012 06:17 PM, Steven Rostedt wrote:
> >>> On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
> >>>
> >>>> BTW, you can also go a step further and remove the need to close with double }},
> >>>> with something like:
> >>>>
> >>>> #define do_for_each_ftrace_rec(pg, rec)                                          \
> >>>>         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
> >>>>              pg && rec == &pg->records[pg->index];                               \
> >>>>              pg = pg->next)                                                      \
> >>>>           for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
> >>>>
> >>>
> >>> Yeah, but why bother? It's hidden in a macro, and the extra '{ }' shows
> >>> that this is something "special".
> >>
> >> The point of both changes is that there's nothing special in the end
> >> at all.  It all just works...
> >>
> > 
> > It would still fail on a 'break'. The 'while' macro tells us that it is
> > special, because in the end, it wont work.
> 
> Please explain why it would fail on a 'break'.
> 

Ah, I missed the condition with the rec == &pg->records[pg->index]. But
if ftrace_pages_start is NULL, the rec = &pg->records[pg->index] will
fault.

You could do something like rec = pg ? &pg->records[pg->index] : NULL,
but IIRC, the comma operator does not guarantee order evaluation. That
is, the compiler is allowed to process "a , b" as "b; a;" and not "a;
b;".

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

Pedro Alves Sept. 4, 2012, 10:58 p.m. UTC | #29

On 09/04/2012 11:41 PM, Steven Rostedt wrote:
> Ah, I missed the condition with the rec == &pg->records[pg->index]. But
> if ftrace_pages_start is NULL, the rec = &pg->records[pg->index] will
> fault.

Right.

> 
> You could do something like rec = pg ? &pg->records[pg->index] : NULL,

Right.

> but IIRC, the comma operator does not guarantee order evaluation. That
> is, the compiler is allowed to process "a , b" as "b; a;" and not "a;
> b;".

Not true.  The comma operator introduces a sequence point.  It's the comma
that separates function parameters that doesn't guarantee ordering.

Steven Rostedt Sept. 4, 2012, 11:27 p.m. UTC | #30

On Tue, 2012-09-04 at 23:58 +0100, Pedro Alves wrote:

> Not true.  The comma operator introduces a sequence point.  It's the comma
> that separates function parameters that doesn't guarantee ordering.

Bah! C language is almost as confusing as English.

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

Sasha Levin Sept. 6, 2012, 1:53 p.m. UTC | #31

On 09/04/2012 07:01 PM, Mathieu Desnoyers wrote:
>> #define do_for_each_ftrace_rec(pg, rec)                                          \
>> >         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
>> >              pg && rec == &pg->records[pg->index];                               \
>> >              pg = pg->next)                                                      \
>> >           for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
> Maybe in some cases there might be ways to combine the two loops into
> one ? I'm not seeing exactly how to do it for this one, but it should
> not be impossible. If the inner loop condition can be moved to the outer
> loop, and if we use (blah ? loop1_conf : loop2_cond) to test for
> different conditions depending on the context, and do the same for the
> 3rd argument of the for() loop. The details elude me for now though, so
> maybe it's complete non-sense ;)
> 
> It might not be that useful for do_for_each_ftrace_rec, but if we can do
> it for the hash table iterator, it might be worth it.

So I think that for the hash iterator it might actually be simpler.

My solution to making 'break' work in the iterator is:

	for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
		hlist_for_each_entry(obj, node, &name[bkt], member)

We initialize our node loop cursor with NULL in the external loop, and the
external loop will have a new condition to loop while that cursor is NULL.

My logic is that we can only 'break' when we are iterating over an object in the
internal loop. If we're iterating over an object in that loop then 'node != NULL'.

This way, if we broke from within the internal loop, the external loop will see
node as not NULL, and so it will stop looping itself. On the other hand, if the
internal loop has actually ended, then node will be NULL, and the outer loop
will keep running.

Is there anything I've missed?


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

Pedro Alves Sept. 6, 2012, 2:19 p.m. UTC | #32

On 09/06/2012 02:53 PM, Sasha Levin wrote:

> So I think that for the hash iterator it might actually be simpler.
> 
> My solution to making 'break' work in the iterator is:
> 
> 	for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
> 		hlist_for_each_entry(obj, node, &name[bkt], member)
> 
> We initialize our node loop cursor with NULL in the external loop, and the
> external loop will have a new condition to loop while that cursor is NULL.
> 
> My logic is that we can only 'break' when we are iterating over an object in the
> internal loop. If we're iterating over an object in that loop then 'node != NULL'.
> 
> This way, if we broke from within the internal loop, the external loop will see
> node as not NULL, and so it will stop looping itself. On the other hand, if the
> internal loop has actually ended, then node will be NULL, and the outer loop
> will keep running.
> 
> Is there anything I've missed?

Looks right to me, from a cursory look at hlist_for_each_entry.  That's exactly
what I meant with this most often being trivial when the inner loop's iterator
is a pointer that goes NULL at the end.

Mathieu Desnoyers Sept. 6, 2012, 2:33 p.m. UTC | #33

* Sasha Levin ([e-mail]) wrote:
> On 09/04/2012 07:01 PM, Mathieu Desnoyers wrote:
> >> #define do_for_each_ftrace_rec(pg, rec)                                          \
> >> >         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
> >> >              pg && rec == &pg->records[pg->index];                               \
> >> >              pg = pg->next)                                                      \
> >> >           for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
> > Maybe in some cases there might be ways to combine the two loops into
> > one ? I'm not seeing exactly how to do it for this one, but it should
> > not be impossible. If the inner loop condition can be moved to the outer
> > loop, and if we use (blah ? loop1_conf : loop2_cond) to test for
> > different conditions depending on the context, and do the same for the
> > 3rd argument of the for() loop. The details elude me for now though, so
> > maybe it's complete non-sense ;)
> > 
> > It might not be that useful for do_for_each_ftrace_rec, but if we can do
> > it for the hash table iterator, it might be worth it.
> 
> So I think that for the hash iterator it might actually be simpler.
> 
> My solution to making 'break' work in the iterator is:
> 
> 	for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
> 		hlist_for_each_entry(obj, node, &name[bkt], member)
> 
> We initialize our node loop cursor with NULL in the external loop, and the
> external loop will have a new condition to loop while that cursor is NULL.
> 
> My logic is that we can only 'break' when we are iterating over an object in the
> internal loop. If we're iterating over an object in that loop then 'node != NULL'.
> 
> This way, if we broke from within the internal loop, the external loop will see
> node as not NULL, and so it will stop looping itself. On the other hand, if the
> internal loop has actually ended, then node will be NULL, and the outer loop
> will keep running.
> 
> Is there anything I've missed?

This sounds good. Unless I'm missing something too.

Thanks!

Mathieu

> 
> 
> Thanks,
> Sasha

David Laight Sept. 6, 2012, 2:36 p.m. UTC | #34

> My solution to making 'break' work in the iterator is:
> 
> 	for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node ==
NULL; bkt++)
> 		hlist_for_each_entry(obj, node, &name[bkt], member)

I'd take a look at the generated code.
Might come out a bit better if the condition is changed to:
	node == NULL && bkt < HASH_SIZE(name)
you might find the compiler always optimises out the
node == NULL comparison.
(It might anyway, but switching the order gives it a better
chance.)

	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

Josh Triplett Sept. 6, 2012, 2:55 p.m. UTC | #35

On Thu, Sep 06, 2012 at 03:53:58PM +0200, Sasha Levin wrote:
> On 09/04/2012 07:01 PM, Mathieu Desnoyers wrote:
> >> #define do_for_each_ftrace_rec(pg, rec)                                          \
> >> >         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
> >> >              pg && rec == &pg->records[pg->index];                               \
> >> >              pg = pg->next)                                                      \
> >> >           for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
> > Maybe in some cases there might be ways to combine the two loops into
> > one ? I'm not seeing exactly how to do it for this one, but it should
> > not be impossible. If the inner loop condition can be moved to the outer
> > loop, and if we use (blah ? loop1_conf : loop2_cond) to test for
> > different conditions depending on the context, and do the same for the
> > 3rd argument of the for() loop. The details elude me for now though, so
> > maybe it's complete non-sense ;)
> > 
> > It might not be that useful for do_for_each_ftrace_rec, but if we can do
> > it for the hash table iterator, it might be worth it.
> 
> So I think that for the hash iterator it might actually be simpler.
> 
> My solution to making 'break' work in the iterator is:
> 
> 	for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
> 		hlist_for_each_entry(obj, node, &name[bkt], member)
> 
> We initialize our node loop cursor with NULL in the external loop, and the
> external loop will have a new condition to loop while that cursor is NULL.
> 
> My logic is that we can only 'break' when we are iterating over an object in the
> internal loop. If we're iterating over an object in that loop then 'node != NULL'.
> 
> This way, if we broke from within the internal loop, the external loop will see
> node as not NULL, and so it will stop looping itself. On the other hand, if the
> internal loop has actually ended, then node will be NULL, and the outer loop
> will keep running.
> 
> Is there anything I've missed?

Looks reasonable.  However, it would break (or rather, not break) on
code like this:

	hash_for_each_entry(...) {
		if (...) {
			foo(node);
			node = NULL;
			break;
		}
	}

Hiding the double loop still seems error-prone.

- Josh Triplett
--
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 Sept. 6, 2012, 3:11 p.m. UTC | #36

On Thu, 2012-09-06 at 07:55 -0700, Josh Triplett wrote:

> > My solution to making 'break' work in the iterator is:
> > 
> > 	for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
> > 		hlist_for_each_entry(obj, node, &name[bkt], member)
> > 
> 
> Looks reasonable.  However, it would break (or rather, not break) on
> code like this:
> 
> 	hash_for_each_entry(...) {
> 		if (...) {
> 			foo(node);
> 			node = NULL;
> 			break;
> 		}
> 	}
> 
> Hiding the double loop still seems error-prone.

We've already had this conversation ;-)  A guess a big comment is in
order:

/*
 * NOTE!  Although this is a double loop, 'break' still works because of
 *        the 'node == NULL' condition in the outer loop. On break of
 *        the inner loop, node will be !NULL, and the outer loop will
 *        exit as well.
 */

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

Sasha Levin Sept. 6, 2012, 3:49 p.m. UTC | #37

On 09/06/2012 04:55 PM, Josh Triplett wrote:
> On Thu, Sep 06, 2012 at 03:53:58PM +0200, Sasha Levin wrote:
>> On 09/04/2012 07:01 PM, Mathieu Desnoyers wrote:
>>>> #define do_for_each_ftrace_rec(pg, rec)                                          \
>>>>>         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
>>>>>              pg && rec == &pg->records[pg->index];                               \
>>>>>              pg = pg->next)                                                      \
>>>>>           for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
>>> Maybe in some cases there might be ways to combine the two loops into
>>> one ? I'm not seeing exactly how to do it for this one, but it should
>>> not be impossible. If the inner loop condition can be moved to the outer
>>> loop, and if we use (blah ? loop1_conf : loop2_cond) to test for
>>> different conditions depending on the context, and do the same for the
>>> 3rd argument of the for() loop. The details elude me for now though, so
>>> maybe it's complete non-sense ;)
>>>
>>> It might not be that useful for do_for_each_ftrace_rec, but if we can do
>>> it for the hash table iterator, it might be worth it.
>>
>> So I think that for the hash iterator it might actually be simpler.
>>
>> My solution to making 'break' work in the iterator is:A code like that doesn
>>
>> 	for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
>> 		hlist_for_each_entry(obj, node, &name[bkt], member)
>>
>> We initialize our node loop cursor with NULL in the external loop, and the
>> external loop will have a new condition to loop while that cursor is NULL.
>>
>> My logic is that we can only 'break' when we are iterating over an object in the
>> internal loop. If we're iterating over an object in that loop then 'node != NULL'.
>>
>> This way, if we broke from within the internal loop, the external loop will see
>> node as not NULL, and so it will stop looping itself. On the other hand, if the
>> internal loop has actually ended, then node will be NULL, and the outer loop
>> will keep running.
>>
>> Is there anything I've missed?
> 
> Looks reasonable.  However, it would break (or rather, not break) on
> code like this:
> 
> 	hash_for_each_entry(...) {
> 		if (...) {
> 			foo(node);
> 			node = NULL;
> 			break;
> 		}
> 	}
> 
> Hiding the double loop still seems error-prone.

I think that that code doesn't make sense. The users of hlist_for_each_* aren't
supposed to be changing the loop cursor.

We have three options here:

 1. Stuff everything into a single for(). While not too difficult, it will make
the readability of the code difficult as it will force us to abandon using
hlist_for_each_* macros.

 2. Over-complicate everything, and check for 'node == NULL && obj &&
obj->member.next == NULL' instead. That one will fail only if the user has
specifically set the object as the last object in the list and the node as NULL.

 3. Use 2 loops which might not work properly if the user does something odd,
with a big fat warning above them.


To sum it up, I'd rather go with 3 and let anyone who does things he shouldn't
be doing break.


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 Sept. 6, 2012, 4 p.m. UTC | #38

On Thu, 2012-09-06 at 17:49 +0200, Sasha Levin wrote:
>  
> > Looks reasonable.  However, it would break (or rather, not break) on
> > code like this:
> > 
> > 	hash_for_each_entry(...) {
> > 		if (...) {
> > 			foo(node);
> > 			node = NULL;

ug, I didn't even notice this. Ignore my last email :-p

/me needs to wake-up a bit more.

> > 			break;
> > 		}
> > 	}
> > 
> > Hiding the double loop still seems error-prone.
> 
> I think that that code doesn't make sense. The users of hlist_for_each_* aren't
> supposed to be changing the loop cursor.

I totally agree. Modifying the 'node' pointer is just asking for issues.
Yes that is error prone, but not due to the double loop. It's due to the
modifying of the node pointer that is used internally by the loop
counter. Don't do that :-)


> 
> We have three options here:
> 
>  1. Stuff everything into a single for(). While not too difficult, it will make
> the readability of the code difficult as it will force us to abandon using
> hlist_for_each_* macros.
> 
>  2. Over-complicate everything, and check for 'node == NULL && obj &&
> obj->member.next == NULL' instead. That one will fail only if the user has
> specifically set the object as the last object in the list and the node as NULL.
> 
>  3. Use 2 loops which might not work properly if the user does something odd,
> with a big fat warning above them.
> 
> 
> To sum it up, I'd rather go with 3 and let anyone who does things he shouldn't
> be doing break.

I agree, the double loop itself is not error prone. If you are modifying
'node' you had better know what the hell you are doing.

Actually, it may be something that is legitimate. That is, if you want
to skip to the next bucket, just set node to NULL and do the break (as
Josh had done). This would break if the macro loop changed later on, but
hey, like I said, it's error prone ;-) If you really want to do that,
then hand coding the double loop would be a better bet. IOW, don't use
the macro loop.

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

Sasha Levin Sept. 6, 2012, 4:21 p.m. UTC | #39

On 09/06/2012 06:00 PM, Steven Rostedt wrote:
>> > I think that that code doesn't make sense. The users of hlist_for_each_* aren't
>> > supposed to be changing the loop cursor.
> I totally agree. Modifying the 'node' pointer is just asking for issues.
> Yes that is error prone, but not due to the double loop. It's due to the
> modifying of the node pointer that is used internally by the loop
> counter. Don't do that :-)

While we're on this subject, I haven't actually seen hlist_for_each_entry() code
that even *touches* 'pos'.

Will people yell at me loudly if I change the prototype of those macros to be:

	hlist_for_each_entry(tpos, head, member)

(Dropping the 'pos' parameter), and updating anything that calls those macros to
drop it as well?


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

Mathieu Desnoyers Sept. 6, 2012, 4:50 p.m. UTC | #40

* Sasha Levin ([e-mail]) wrote:
> On 09/06/2012 06:00 PM, Steven Rostedt wrote:
> >> > I think that that code doesn't make sense. The users of hlist_for_each_* aren't
> >> > supposed to be changing the loop cursor.
> > I totally agree. Modifying the 'node' pointer is just asking for issues.
> > Yes that is error prone, but not due to the double loop. It's due to the
> > modifying of the node pointer that is used internally by the loop
> > counter. Don't do that :-)
> 
> While we're on this subject, I haven't actually seen hlist_for_each_entry() code
> that even *touches* 'pos'.
> 
> Will people yell at me loudly if I change the prototype of those macros to be:
> 
> 	hlist_for_each_entry(tpos, head, member)
> 
> (Dropping the 'pos' parameter), and updating anything that calls those macros to
> drop it as well?

I think the intent there is to keep hlist macros and list macros
slightly in sync. Given those are vastly used, I'm not sure you want to
touch them. But hey, that's just my 2 cents.

Thanks,

Mathieu

> 
> 
> Thanks,
> Sasha

Sasha Levin Sept. 6, 2012, 5:01 p.m. UTC | #41

On 09/06/2012 06:50 PM, Mathieu Desnoyers wrote:
> * Sasha Levin ([e-mail]) wrote:
>> On 09/06/2012 06:00 PM, Steven Rostedt wrote:
>>>>> I think that that code doesn't make sense. The users of hlist_for_each_* aren't
>>>>> supposed to be changing the loop cursor.
>>> I totally agree. Modifying the 'node' pointer is just asking for issues.
>>> Yes that is error prone, but not due to the double loop. It's due to the
>>> modifying of the node pointer that is used internally by the loop
>>> counter. Don't do that :-)
>>
>> While we're on this subject, I haven't actually seen hlist_for_each_entry() code
>> that even *touches* 'pos'.
>>
>> Will people yell at me loudly if I change the prototype of those macros to be:
>>
>> 	hlist_for_each_entry(tpos, head, member)
>>
>> (Dropping the 'pos' parameter), and updating anything that calls those macros to
>> drop it as well?
> 
> I think the intent there is to keep hlist macros and list macros
> slightly in sync. Given those are vastly used, I'm not sure you want to
> touch them. But hey, that's just my 2 cents.

Actually, the corresponding list macro looks like this:

	list_for_each_entry(pos, head, member)

With 'pos' being the equivalent of 'tpos' in the hlist macros (the type *).
Changing hlist macro will make them both look as follows:

	hlist_for_each_entry(pos, head, member)
	list_for_each_entry(pos, head, member)

So following this suggesting will actually bring them back to sync...

The only issue I can see is that as you've said, they're used almost everywhere,
so doing something to change that will require some coordination.


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

Mathieu Desnoyers Sept. 6, 2012, 5:02 p.m. UTC | #42

* Sasha Levin ([e-mail]) wrote:
> On 09/06/2012 06:50 PM, Mathieu Desnoyers wrote:
> > * Sasha Levin ([e-mail]) wrote:
> >> On 09/06/2012 06:00 PM, Steven Rostedt wrote:
> >>>>> I think that that code doesn't make sense. The users of hlist_for_each_* aren't
> >>>>> supposed to be changing the loop cursor.
> >>> I totally agree. Modifying the 'node' pointer is just asking for issues.
> >>> Yes that is error prone, but not due to the double loop. It's due to the
> >>> modifying of the node pointer that is used internally by the loop
> >>> counter. Don't do that :-)
> >>
> >> While we're on this subject, I haven't actually seen hlist_for_each_entry() code
> >> that even *touches* 'pos'.
> >>
> >> Will people yell at me loudly if I change the prototype of those macros to be:
> >>
> >> 	hlist_for_each_entry(tpos, head, member)
> >>
> >> (Dropping the 'pos' parameter), and updating anything that calls those macros to
> >> drop it as well?
> > 
> > I think the intent there is to keep hlist macros and list macros
> > slightly in sync. Given those are vastly used, I'm not sure you want to
> > touch them. But hey, that's just my 2 cents.
> 
> Actually, the corresponding list macro looks like this:
> 
> 	list_for_each_entry(pos, head, member)
> 
> With 'pos' being the equivalent of 'tpos' in the hlist macros (the type *).
> Changing hlist macro will make them both look as follows:
> 
> 	hlist_for_each_entry(pos, head, member)
> 	list_for_each_entry(pos, head, member)
> 
> So following this suggesting will actually bring them back to sync...
> 
> The only issue I can see is that as you've said, they're used almost everywhere,
> so doing something to change that will require some coordination.

if this brings hlist and list in sync, then it looks like an
improvement. It might be good to propose this change as a separate
patchset.

Thanks,

Mathieu

> 
> 
> Thanks,
> Sasha

Steven Rostedt Sept. 6, 2012, 5:15 p.m. UTC | #43

On Thu, 2012-09-06 at 18:21 +0200, Sasha Levin wrote:
> On 09/06/2012 06:00 PM, Steven Rostedt wrote:
> >> > I think that that code doesn't make sense. The users of hlist_for_each_* aren't
> >> > supposed to be changing the loop cursor.
> > I totally agree. Modifying the 'node' pointer is just asking for issues.
> > Yes that is error prone, but not due to the double loop. It's due to the
> > modifying of the node pointer that is used internally by the loop
> > counter. Don't do that :-)
> 
> While we're on this subject, I haven't actually seen hlist_for_each_entry() code
> that even *touches* 'pos'.
> 
> Will people yell at me loudly if I change the prototype of those macros to be:
> 
> 	hlist_for_each_entry(tpos, head, member)
> 
> (Dropping the 'pos' parameter), and updating anything that calls those macros to
> drop it as well?

If 'pos' is no longer used in the macro, I don't see any reason for
keeping it around.

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

Patch

diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
new file mode 100644
index 0000000..d2d6ed0
--- /dev/null
+++ b/include/linux/hashtable.h
@@ -0,0 +1,291 @@ 
+/*
+ * 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[HASH_SIZE(bits)];
+
+#define HASH_SIZE(bits) (1 << (bits))
+#define HASH_BITS(name) (ilog2(ARRAY_SIZE(name)))
+#define HASH_REQUIRED_SIZE(bits) (sizeof(struct hlist_head) * HASH_SIZE(bits))
+
+/* 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_size - initialize a hash table
+ * @hashtable: hashtable to be initialized
+ * @bits: bit count of hashing function
+ *
+ * Initializes a hash table with 2**bits buckets.
+ */
+static inline void hash_init_size(struct hlist_head *hashtable, int bits)
+{
+	int i;
+
+	for (i = 0; i < HASH_SIZE(bits); i++)
+		INIT_HLIST_HEAD(hashtable + 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.
+ */
+#define hash_init(name) hash_init_size(name, HASH_BITS(name))
+
+/**
+ * hash_add_size - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the &struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_size(hashtable, bits, node, key)				\
+	hlist_add_head(node, &hashtable[hash_min(key, bits)]);
+
+/**
+ * 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)						\
+	hash_add_size(hashtable, HASH_BITS(hashtable), node, key)
+
+/**
+ * hash_add_rcu_size - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the &struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu_size(hashtable, bits, node, key)				\
+	hlist_add_head_rcu(node, &hashtable[hash_min(key, bits)]);
+
+/**
+ * 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)					\
+	hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)
+
+/**
+ * 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_size - check whether a hashtable is empty
+ * @hashtable: hashtable to check
+ * @bits: bit count used for hashing
+ */
+static inline bool hash_empty_size(struct hlist_head *hashtable, int bits)
+{
+	int i;
+
+	for (i = 0; i < HASH_SIZE(bits); i++)
+		if (!hlist_empty(&hashtable[i]))
+			return false;
+
+	return true;
+}
+
+/**
+ * hash_empty - check whether a hashtable is empty
+ * @hashtable: hashtable to check
+ */
+#define hash_empty(name) hash_empty_size(name, HASH_BITS(name))
+
+/**
+ * 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_size - iterate over a hashtable
+ * @name: hashtable to iterate
+ * @bits: bit count of hashing function of the hashtable
+ * @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_size(name, bits, bkt, node, obj, member)			\
+	for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)				\
+		hlist_for_each_entry(obj, node, &name[bkt], member)
+
+/**
+ * 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)				\
+	hash_for_each_size(name, HASH_BITS(name), bkt, node, obj, member)
+
+/**
+ * hash_for_each_rcu_size - iterate over a rcu enabled hashtable
+ * @name: hashtable to iterate
+ * @bits: bit count of hashing function of the hashtable
+ * @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_size(name, bits, bkt, node, obj, member)		\
+	for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)				\
+		hlist_for_each_entry_rcu(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)				\
+	hash_for_each_rcu_size(name, HASH_BITS(name), bkt, node, obj, member)
+
+/**
+ * hash_for_each_safe_size - 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: another &struct hlist_node to use as 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_size(name, bits, bkt, node, tmp, obj, member)	\
+	for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)                     	\
+		hlist_for_each_entry_safe(obj, node, tmp, &name[bkt], member)
+
+/**
+ * hash_for_each_safe_size - 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
+ * @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)			\
+	hash_for_each_safe_size(name, HASH_BITS(name), bkt, node,		\
+				tmp, obj, member)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hasing to the
+ * same bucket
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @bits: bit count of hashing function of the hashtable
+ * @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_size(name, obj, bits, node, member, key)		\
+	hlist_for_each_entry(obj, node,	&name[hash_min(key, bits)], 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
+ * @bits: bit count of hashing function of the hashtable
+ * @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)			\
+	hash_for_each_possible_size(name, obj, HASH_BITS(name), node, member, key)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hashing to the
+ * same bucket
+ * in a rcu enabled hashtable
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @bits: bit count of hashing function of the hashtable
+ * @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_size(name, obj, bits, node, member, key)	\
+	hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, bits)], member)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hashing to the
+ * same bucket
+ * 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)		\
+	hash_for_each_possible_rcu_size(name, obj, HASH_BITS(name),		\
+					node, member, key)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hashing to the
+ * same bucket
+ * safe against removal of hash entry
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @bits: bit count of hashing function of the hashtable
+ * @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_safe_size(name, obj, bits, node, tmp, member, key)\
+	hlist_for_each_entry_safe(obj, node, tmp,				\
+		&name[hash_min(key, bits)], member)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hashing to the
+ * same bucket
+ * safe against removal of hash entry
+ * @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_safe(name, obj, node, tmp, member, key)		\
+	hash_for_each_possible_safe_size(name, obj, HASH_BITS(name),		\
+						node, tmp, member, key)
+
+#endif