[PATCH v6] hashtable: introduce a small and naive hashtable

[PATCH v6] hashtable: introduce a small and naive hashtable

[Sasha Levin]

This hashtable implementation is using hlist buckets to provide a simple
hashtable to prevent it from getting reimplemented all over the kernel.

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---

Changes since v5:

 - Fix hash_init.
 - Clarify this implementation deals with statically allocated hashtables only.

 include/linux/hashtable.h | 190 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 190 insertions(+)
 create mode 100644 include/linux/hashtable.h

diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
new file mode 100644
index 0000000..195173e
--- /dev/null
+++ b/include/linux/hashtable.h
@@ -0,0 +1,190 @@
+/*
+ * Statically sized hash table implementation
+ * (C) 2012  Sasha Levin <levinsasha928@gmail.com>
+ */
+
+#ifndef _LINUX_HASHTABLE_H
+#define _LINUX_HASHTABLE_H
+
+#include <linux/list.h>
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/hash.h>
+#include <linux/rculist.h>
+
+#define DEFINE_HASHTABLE(name, bits)						\
+	struct hlist_head name[HASH_SIZE(bits)] =				\
+			{ [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT }
+
+#define DECLARE_HASHTABLE(name, bits)                                   	\
+	struct hlist_head name[1 << (bits)]
+
+#define HASH_SIZE(name) (1 << HASH_BITS(name))
+#define HASH_BITS(name) ilog2(ARRAY_SIZE(name))
+
+/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
+#define hash_min(val, bits)							\
+({										\
+	sizeof(val) <= 4 ?							\
+	hash_32(val, bits) :							\
+	hash_long(val, bits);							\
+})
+
+/**
+ * hash_init - initialize a hash table
+ * @hashtable: hashtable to be initialized
+ *
+ * Calculates the size of the hashtable from the given parameter, otherwise
+ * same as hash_init_size.
+ *
+ * This has to be a macro since HASH_BITS() will not work on pointers since
+ * it calculates the size during preprocessing.
+ */
+#define hash_init(hashtable)							\
+({										\
+	int __i;								\
+										\
+	for (__i = 0; __i < HASH_SIZE(hashtable); __i++)			\
+		INIT_HLIST_HEAD(&hashtable[__i]);				\
+})
+
+/**
+ * hash_add - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @node: the &struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add(hashtable, node, key)						\
+	hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]);
+
+/**
+ * hash_add_rcu - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @node: the &struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu(hashtable, node, key)					\
+	hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))]);
+
+/**
+ * hash_hashed - check whether an object is in any hashtable
+ * @node: the &struct hlist_node of the object to be checked
+ */
+#define hash_hashed(node) (!hlist_unhashed(node))
+
+/**
+ * hash_empty - check whether a hashtable is empty
+ * @hashtable: hashtable to check
+ *
+ * This has to be a macro since HASH_BITS() will not work on pointers since
+ * it calculates the size during preprocessing.
+ */
+#define hash_empty(hashtable)							\
+({										\
+	int __i;								\
+	bool __ret = true;							\
+										\
+	for (__i = 0; __i < HASH_SIZE(hashtable); __i++)			\
+		if (!hlist_empty(&hashtable[__i]))				\
+			__ret = false;						\
+										\
+	__ret;									\
+})
+
+/**
+ * hash_del - remove an object from a hashtable
+ * @node: &struct hlist_node of the object to remove
+ */
+static inline void hash_del(struct hlist_node *node)
+{
+	hlist_del_init(node);
+}
+
+/**
+ * hash_del_rcu - remove an object from a rcu enabled hashtable
+ * @node: &struct hlist_node of the object to remove
+ */
+static inline void hash_del_rcu(struct hlist_node *node)
+{
+	hlist_del_init_rcu(node);
+}
+
+/**
+ * hash_for_each - iterate over a hashtable
+ * @name: hashtable to iterate
+ * @bkt: integer to use as bucket loop cursor
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @obj: the type * to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ */
+#define hash_for_each(name, bkt, node, obj, member)				\
+	for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\
+		hlist_for_each_entry(obj, node, &name[bkt], member)
+
+/**
+ * hash_for_each_rcu - iterate over a rcu enabled hashtable
+ * @name: hashtable to iterate
+ * @bkt: integer to use as bucket loop cursor
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @obj: the type * to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ */
+#define hash_for_each_rcu(name, bkt, node, obj, member)				\
+	for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\
+		hlist_for_each_entry_rcu(obj, node, &name[bkt], member)
+
+/**
+ * hash_for_each_safe - iterate over a hashtable safe against removal of
+ * hash entry
+ * @name: hashtable to iterate
+ * @bkt: integer to use as bucket loop cursor
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @tmp: a &struct used for temporary storage
+ * @obj: the type * to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ */
+#define hash_for_each_safe(name, bkt, node, tmp, obj, member)			\
+	for (bkt = 0, node = NULL; node == NULL && bkt < HASH_SIZE(name); bkt++)\
+		hlist_for_each_entry_safe(obj, node, tmp, &name[bkt], member)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hashing to the
+ * same bucket
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible(name, obj, node, member, key)			\
+	hlist_for_each_entry(obj, node,	&name[hash_min(key, HASH_BITS(name))], member)
+
+/**
+ * hash_for_each_possible_rcu - iterate over all possible objects hashing to the
+ * same bucket in an rcu enabled hashtable
+ * in a rcu enabled hashtable
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible_rcu(name, obj, node, member, key)		\
+	hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, HASH_BITS(name))], member)
+
+/**
+ * hash_for_each_possible_safe - iterate over all possible objects hashing to the
+ * same bucket safe against removals
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @tmp: a &struct used for temporary storage
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible_safe(name, obj, node, tmp, member, key)		\
+	hlist_for_each_entry_safe(obj, node, tmp,				\
+		&name[hash_min(key, HASH_BITS(name))], member)
+
+
+#endif
-- 
1.7.12

RE: [PATCH v6] hashtable: introduce a small and naive hashtable

[David Laight]

Amazing how something simple gets lots of comments and versions :-)

> ...
> + * This has to be a macro since HASH_BITS() will not work on pointers since
> + * it calculates the size during preprocessing.
> + */
> +#define hash_empty(hashtable)							\
> +({										\
> +	int __i;								\
> +	bool __ret = true;							\
> +										\
> +	for (__i = 0; __i < HASH_SIZE(hashtable); __i++)			\
> +		if (!hlist_empty(&hashtable[__i]))				\
> +			__ret = false;						\
> +										\
> +	__ret;									\
> +})

Actually you could have a #define that calls a function
passing in the address and size.
Also, should the loop have a 'break' in it?

	David

Re: [PATCH v6] hashtable: introduce a small and naive hashtable

[Steven Rostedt]

On Wed, 2012-09-26 at 14:45 +0100, David Laight wrote:
> Amazing how something simple gets lots of comments and versions :-)
> 
> > ...
> > + * This has to be a macro since HASH_BITS() will not work on pointers since
> > + * it calculates the size during preprocessing.
> > + */
> > +#define hash_empty(hashtable)							\
> > +({										\
> > +	int __i;								\
> > +	bool __ret = true;							\
> > +										\
> > +	for (__i = 0; __i < HASH_SIZE(hashtable); __i++)			\
> > +		if (!hlist_empty(&hashtable[__i]))				\
> > +			__ret = false;						\
> > +										\
> > +	__ret;									\
> > +})
> 
> Actually you could have a #define that calls a function
> passing in the address and size.

Probably would be cleaner to do so.


> Also, should the loop have a 'break' in it?

Yeah it should, and could do:

	for (i = 0; i < HASH_SIZE(hashtable); i++)
		if (!hlist_empty(&hashtable[i]))
			break;

	return i < HASH_SIZE(hashtable);

-- Steve

Re: [PATCH v6] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 09/26/2012 03:59 PM, Steven Rostedt wrote:
> On Wed, 2012-09-26 at 14:45 +0100, David Laight wrote:
>> Amazing how something simple gets lots of comments and versions :-)
>>
>>> ...
>>> + * This has to be a macro since HASH_BITS() will not work on pointers since
>>> + * it calculates the size during preprocessing.
>>> + */
>>> +#define hash_empty(hashtable)							\
>>> +({										\
>>> +	int __i;								\
>>> +	bool __ret = true;							\
>>> +										\
>>> +	for (__i = 0; __i < HASH_SIZE(hashtable); __i++)			\
>>> +		if (!hlist_empty(&hashtable[__i]))				\
>>> +			__ret = false;						\
>>> +										\
>>> +	__ret;									\
>>> +})
>>
>> Actually you could have a #define that calls a function
>> passing in the address and size.
> 
> Probably would be cleaner to do so.

I think it's worth it if it was more complex than a simple loop. We were doing a similar thing with the _size() functions (see
version 4 of this patch), but decided to remove it since it was becoming too complex.
> 
> 
>> Also, should the loop have a 'break' in it?
> 
> Yeah it should, and could do:
> 
> 	for (i = 0; i < HASH_SIZE(hashtable); i++)
> 		if (!hlist_empty(&hashtable[i]))
> 			break;
> 
> 	return i < HASH_SIZE(hashtable);

Right.


Thanks,
Sasha

Re: [PATCH v6] hashtable: introduce a small and naive hashtable

[Mathieu Desnoyers]

* David Laight (David.Laight@ACULAB.COM) wrote:
> Amazing how something simple gets lots of comments and versions :-)
> 
> > ...
> > + * This has to be a macro since HASH_BITS() will not work on pointers since
> > + * it calculates the size during preprocessing.
> > + */
> > +#define hash_empty(hashtable)							\
> > +({										\
> > +	int __i;								\
> > +	bool __ret = true;							\
> > +										\
> > +	for (__i = 0; __i < HASH_SIZE(hashtable); __i++)			\
> > +		if (!hlist_empty(&hashtable[__i]))				\
> > +			__ret = false;						\
> > +										\
> > +	__ret;									\
> > +})
> 
> Actually you could have a #define that calls a function
> passing in the address and size.
> Also, should the loop have a 'break' in it?

+1   Removing unnecessary variables defined within a
statement-expression is indeed something we want, and your suggestion of
a macro calling a static inline is, IMHO, spot-on.

The same should be done for hash_init().

And yes, a break would be welcome in that loop: no need to continue if
we encounter a non-empty hlist.

Thanks,

Mathieu

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

Re: [PATCH v6] hashtable: introduce a small and naive hashtable

[Mathieu Desnoyers]

* Sasha Levin (levinsasha928@gmail.com) wrote:
> On 09/26/2012 03:59 PM, Steven Rostedt wrote:
> > On Wed, 2012-09-26 at 14:45 +0100, David Laight wrote:
> >> Amazing how something simple gets lots of comments and versions :-)
> >>
> >>> ...
> >>> + * This has to be a macro since HASH_BITS() will not work on pointers since
> >>> + * it calculates the size during preprocessing.
> >>> + */
> >>> +#define hash_empty(hashtable)							\
> >>> +({										\
> >>> +	int __i;								\
> >>> +	bool __ret = true;							\
> >>> +										\
> >>> +	for (__i = 0; __i < HASH_SIZE(hashtable); __i++)			\
> >>> +		if (!hlist_empty(&hashtable[__i]))				\
> >>> +			__ret = false;						\
> >>> +										\
> >>> +	__ret;									\
> >>> +})
> >>
> >> Actually you could have a #define that calls a function
> >> passing in the address and size.
> > 
> > Probably would be cleaner to do so.
> 
> I think it's worth it if it was more complex than a simple loop. We
> were doing a similar thing with the _size() functions (see version 4
> of this patch), but decided to remove it since it was becoming too
> complex.

Defining local variables within statement-expressions can have some
unexpected side-effects if the "caller" which embeds the macro use the
same variable name. See rcu_dereference() as an example (Paul uses an
awefully large number of underscores). It should be avoided whenever
possible.

> > 
> > 
> >> Also, should the loop have a 'break' in it?
> > 
> > Yeah it should, and could do:
> > 
> > 	for (i = 0; i < HASH_SIZE(hashtable); i++)
> > 		if (!hlist_empty(&hashtable[i]))
> > 			break;
> > 
> > 	return i < HASH_SIZE(hashtable);


Hrm, Steven, did you drink you morning coffee before writing this ? ;-)
It looks like you did 2 bugs in 4 LOC.

First, the condition should be reversed, because this function returns
whether the hash is empty, not the other way around.

And even then, if we would do:

 	for (i = 0; i < HASH_SIZE(hashtable); i++)
 		if (!hlist_empty(&hashtable[i]))
 			break;
 
 	return i >= HASH_SIZE(hashtable);

What happens if the last entry of the table is non-empty ?

So I would advise that Sasha keep his original flag-based
implementation, but add the missing break, and move the init and empty
define loops into static inlines.

Thanks,

Mathieu

> 
> Right.
> 
> 
> Thanks,
> Sasha

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

Re: [PATCH v6] hashtable: introduce a small and naive hashtable

[Steven Rostedt]

On Wed, 2012-09-26 at 10:39 -0400, Mathieu Desnoyers wrote:
> * Sasha Levin (levinsasha928@gmail.com) wrote:
> > On 09/26/2012 03:59 PM, Steven Rostedt wrote:
> > > On Wed, 2012-09-26 at 14:45 +0100, David Laight wrote:
> > >> Amazing how something simple gets lots of comments and versions :-)
> > >>
> > >>> ...
> > >>> + * This has to be a macro since HASH_BITS() will not work on pointers since
> > >>> + * it calculates the size during preprocessing.
> > >>> + */
> > >>> +#define hash_empty(hashtable)							\
> > >>> +({										\
> > >>> +	int __i;								\
> > >>> +	bool __ret = true;							\
> > >>> +										\
> > >>> +	for (__i = 0; __i < HASH_SIZE(hashtable); __i++)			\
> > >>> +		if (!hlist_empty(&hashtable[__i]))				\
> > >>> +			__ret = false;						\
> > >>> +										\
> > >>> +	__ret;									\
> > >>> +})
> > >>
> > >> Actually you could have a #define that calls a function
> > >> passing in the address and size.
> > > 
> > > Probably would be cleaner to do so.
> > 
> > I think it's worth it if it was more complex than a simple loop. We
> > were doing a similar thing with the _size() functions (see version 4
> > of this patch), but decided to remove it since it was becoming too
> > complex.
> 
> Defining local variables within statement-expressions can have some
> unexpected side-effects if the "caller" which embeds the macro use the
> same variable name. See rcu_dereference() as an example (Paul uses an
> awefully large number of underscores). It should be avoided whenever
> possible.
> 
> > > 
> > > 
> > >> Also, should the loop have a 'break' in it?
> > > 
> > > Yeah it should, and could do:
> > > 
> > > 	for (i = 0; i < HASH_SIZE(hashtable); i++)
> > > 		if (!hlist_empty(&hashtable[i]))
> > > 			break;
> > > 
> > > 	return i < HASH_SIZE(hashtable);
> 
> 
> Hrm, Steven, did you drink you morning coffee before writing this ? ;-)
> It looks like you did 2 bugs in 4 LOC.

Coffee yes, but head cold as well. :-p

> 
> First, the condition should be reversed, because this function returns
> whether the hash is empty, not the other way around.

Bah, I was looking at the code the code and got the ret confused. I
originally had it the opposite, and then reversed it before sending.

> 
> And even then, if we would do:
> 
>  	for (i = 0; i < HASH_SIZE(hashtable); i++)
>  		if (!hlist_empty(&hashtable[i]))
>  			break;
>  
>  	return i >= HASH_SIZE(hashtable);
> 
> What happens if the last entry of the table is non-empty ?

It still works, as 'i' is not incremented due to the break. And i will
still be less than HASH_SIZE(hashtable). Did you have *your* cup of
coffee today? ;-)


> 
> So I would advise that Sasha keep his original flag-based
> implementation, but add the missing break, and move the init and empty
> define loops into static inlines.
> 

Nah,

-- Steve

Re: [PATCH v6] hashtable: introduce a small and naive hashtable

[Mathieu Desnoyers]

* Steven Rostedt (rostedt@goodmis.org) wrote:
> On Wed, 2012-09-26 at 10:39 -0400, Mathieu Desnoyers wrote:
> > * Sasha Levin (levinsasha928@gmail.com) wrote:
> > > On 09/26/2012 03:59 PM, Steven Rostedt wrote:
> > > > On Wed, 2012-09-26 at 14:45 +0100, David Laight wrote:
> > > >> Amazing how something simple gets lots of comments and versions :-)
> > > >>
> > > >>> ...
> > > >>> + * This has to be a macro since HASH_BITS() will not work on pointers since
> > > >>> + * it calculates the size during preprocessing.
> > > >>> + */
> > > >>> +#define hash_empty(hashtable)							\
> > > >>> +({										\
> > > >>> +	int __i;								\
> > > >>> +	bool __ret = true;							\
> > > >>> +										\
> > > >>> +	for (__i = 0; __i < HASH_SIZE(hashtable); __i++)			\
> > > >>> +		if (!hlist_empty(&hashtable[__i]))				\
> > > >>> +			__ret = false;						\
> > > >>> +										\
> > > >>> +	__ret;									\
> > > >>> +})
> > > >>
> > > >> Actually you could have a #define that calls a function
> > > >> passing in the address and size.
> > > > 
> > > > Probably would be cleaner to do so.
> > > 
> > > I think it's worth it if it was more complex than a simple loop. We
> > > were doing a similar thing with the _size() functions (see version 4
> > > of this patch), but decided to remove it since it was becoming too
> > > complex.
> > 
> > Defining local variables within statement-expressions can have some
> > unexpected side-effects if the "caller" which embeds the macro use the
> > same variable name. See rcu_dereference() as an example (Paul uses an
> > awefully large number of underscores). It should be avoided whenever
> > possible.
> > 
> > > > 
> > > > 
> > > >> Also, should the loop have a 'break' in it?
> > > > 
> > > > Yeah it should, and could do:
> > > > 
> > > > 	for (i = 0; i < HASH_SIZE(hashtable); i++)
> > > > 		if (!hlist_empty(&hashtable[i]))
> > > > 			break;
> > > > 
> > > > 	return i < HASH_SIZE(hashtable);
> > 
> > 
> > Hrm, Steven, did you drink you morning coffee before writing this ? ;-)
> > It looks like you did 2 bugs in 4 LOC.
> 
> Coffee yes, but head cold as well. :-p
> 
> > 
> > First, the condition should be reversed, because this function returns
> > whether the hash is empty, not the other way around.
> 
> Bah, I was looking at the code the code and got the ret confused. I
> originally had it the opposite, and then reversed it before sending.
> 
> > 
> > And even then, if we would do:
> > 
> >  	for (i = 0; i < HASH_SIZE(hashtable); i++)
> >  		if (!hlist_empty(&hashtable[i]))
> >  			break;
> >  
> >  	return i >= HASH_SIZE(hashtable);
> > 
> > What happens if the last entry of the table is non-empty ?
> 
> It still works, as 'i' is not incremented due to the break. And i will
> still be less than HASH_SIZE(hashtable). Did you have *your* cup of
> coffee today? ;-)

Ahh, right! Actually I had it already ;-)

> 
> 
> > 
> > So I would advise that Sasha keep his original flag-based
> > implementation, but add the missing break, and move the init and empty
> > define loops into static inlines.
> > 
> 
> Nah,

Agreed that the flags should be removed. Moving to define + static
inline is still important though.

Thanks,

Mathieu


> 
> -- Steve
> 
> 

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

RE: [PATCH v6] hashtable: introduce a small and naive hashtable

[David Laight]

> > > And even then, if we would do:
> > >
> > >  	for (i = 0; i < HASH_SIZE(hashtable); i++)
> > >  		if (!hlist_empty(&hashtable[i]))
> > >  			break;
> > >
> > >  	return i >= HASH_SIZE(hashtable);
> > >
> > > What happens if the last entry of the table is non-empty ?
> >
> > It still works, as 'i' is not incremented due to the break. And i will
> > still be less than HASH_SIZE(hashtable). Did you have *your* cup of
> > coffee today? ;-)
> 
> Ahh, right! Actually I had it already ;-)

I tend to dislike the repeated test, gcc might be able to optimise
it away, but the code is cleaner written as:

	for (i = 0; i < HASH_SIZE(hashtable); i++)
		if (!hlist_empty(&hashtable[i]))
			return false;
	return true;

> Agreed that the flags should be removed. Moving to define + static
> inline is still important though.

Not sure I'd bother making the function inline.

	David

Re: [PATCH v6] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 09/27/2012 10:25 AM, David Laight wrote:
>>>> And even then, if we would do:
>>>>
>>>>  	for (i = 0; i < HASH_SIZE(hashtable); i++)
>>>>  		if (!hlist_empty(&hashtable[i]))
>>>>  			break;
>>>>
>>>>  	return i >= HASH_SIZE(hashtable);
>>>>
>>>> What happens if the last entry of the table is non-empty ?
>>>
>>> It still works, as 'i' is not incremented due to the break. And i will
>>> still be less than HASH_SIZE(hashtable). Did you have *your* cup of
>>> coffee today? ;-)
>>
>> Ahh, right! Actually I had it already ;-)
> 
> I tend to dislike the repeated test, gcc might be able to optimise
> it away, but the code is cleaner written as:
> 
> 	for (i = 0; i < HASH_SIZE(hashtable); i++)
> 		if (!hlist_empty(&hashtable[i]))
> 			return false;
> 	return true;

Right, the flag thing in the macro was there just to make it work properly as a macro.

>> Agreed that the flags should be removed. Moving to define + static
>> inline is still important though.
> 
> Not sure I'd bother making the function inline.

I usually never make anything 'inline', I just let gcc do it's own thing when it compiles the code. If there are any objections
please let me know before I send the new version.


Thanks,
Sasha

Re: [PATCH v6] hashtable: introduce a small and naive hashtable

[Steven Rostedt]

On Thu, 2012-09-27 at 10:33 +0200, Sasha Levin wrote:

> Right, the flag thing in the macro was there just to make it work properly as a macro.
> 
> >> Agreed that the flags should be removed. Moving to define + static
> >> inline is still important though.
> > 
> > Not sure I'd bother making the function inline.
> 
> I usually never make anything 'inline', I just let gcc do it's own thing when it compiles the code. If there are any objections
> please let me know before I send the new version.

But this is a header file. You guys have no problem with macros, but
refuse to use 'inline' for functions defined in header files? That
doesn't make sense. A 'static inline' is basically a gcc macro, but
without the side-effects.

-- Steve

Re: [PATCH v6] hashtable: introduce a small and naive hashtable

[Mathieu Desnoyers]

* David Laight (David.Laight@ACULAB.COM) wrote:
> > > > And even then, if we would do:
> > > >
> > > >  	for (i = 0; i < HASH_SIZE(hashtable); i++)
> > > >  		if (!hlist_empty(&hashtable[i]))
> > > >  			break;
> > > >
> > > >  	return i >= HASH_SIZE(hashtable);
> > > >
> > > > What happens if the last entry of the table is non-empty ?
> > >
> > > It still works, as 'i' is not incremented due to the break. And i will
> > > still be less than HASH_SIZE(hashtable). Did you have *your* cup of
> > > coffee today? ;-)
> > 
> > Ahh, right! Actually I had it already ;-)
> 
> I tend to dislike the repeated test, gcc might be able to optimise
> it away, but the code is cleaner written as:
> 
> 	for (i = 0; i < HASH_SIZE(hashtable); i++)
> 		if (!hlist_empty(&hashtable[i]))
> 			return false;
> 	return true;
> 

Agreed, this looks like a good way to write it.

> > Agreed that the flags should be removed. Moving to define + static
> > inline is still important though.
> 
> Not sure I'd bother making the function inline.

Do you mean you prefer to keep it as a macro, or that you don't think
the "inline" keyword is relevant anymore, and want to do a "static" only
function in the header file ?

In both cases, please explain the reasons for doing things that way.

Thanks,

Mathieu

> 
> 	David
> 
> 
> 

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

Re: [PATCH v6] hashtable: introduce a small and naive hashtable

[Mathieu Desnoyers]

* Sasha Levin (levinsasha928@gmail.com) wrote:
> On 09/27/2012 10:25 AM, David Laight wrote:
> >>>> And even then, if we would do:
> >>>>
> >>>>  	for (i = 0; i < HASH_SIZE(hashtable); i++)
> >>>>  		if (!hlist_empty(&hashtable[i]))
> >>>>  			break;
> >>>>
> >>>>  	return i >= HASH_SIZE(hashtable);
> >>>>
> >>>> What happens if the last entry of the table is non-empty ?
> >>>
> >>> It still works, as 'i' is not incremented due to the break. And i will
> >>> still be less than HASH_SIZE(hashtable). Did you have *your* cup of
> >>> coffee today? ;-)
> >>
> >> Ahh, right! Actually I had it already ;-)
> > 
> > I tend to dislike the repeated test, gcc might be able to optimise
> > it away, but the code is cleaner written as:
> > 
> > 	for (i = 0; i < HASH_SIZE(hashtable); i++)
> > 		if (!hlist_empty(&hashtable[i]))
> > 			return false;
> > 	return true;
> 
> Right, the flag thing in the macro was there just to make it work
> properly as a macro.
> 
> >> Agreed that the flags should be removed. Moving to define + static
> >> inline is still important though.
> > 
> > Not sure I'd bother making the function inline.
> 
> I usually never make anything 'inline', I just let gcc do it's own
> thing when it compiles the code. If there are any objections
> please let me know before I send the new version.

AFAIK, gcc nowadays use "inline" only as a hint, because programmers
were using it everywhere, even where it should not have been used. This
is where the attribute always_inline becomes useful, if you really,
really want to inline. However, for kernel coding style consistency, it
might be better to use "static inline", because it is used everywhere
else in kernel headers. Or maybe are there some headers that do not use
"inline" I am not aware of ?

Moreover, if your thinking is that we do not need a static inline
function replicated at every caller, maybe we should introduce a
lib/hashtable.c that implements those 2 functions.

Thanks,

Mathieu

> 
> 
> Thanks,
> Sasha
> 

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

Re: [PATCH v6] hashtable: introduce a small and naive hashtable

[Steven Rostedt]

On Thu, 2012-09-27 at 09:11 -0400, Mathieu Desnoyers wrote:

> AFAIK, gcc nowadays use "inline" only as a hint

Only if CONFIG_OPTIMIZE_INLINING is set.

>From include/linux/compiler-gcc.h:

#if !defined(CONFIG_ARCH_SUPPORTS_OPTIMIZED_INLINING) || \
    !defined(CONFIG_OPTIMIZE_INLINING) || (__GNUC__ < 4)
# define inline         inline          __attribute__((always_inline)) notrace
# define __inline__     __inline__      __attribute__((always_inline)) notrace
# define __inline       __inline        __attribute__((always_inline)) notrace
#else
/* A lot of inline functions can cause havoc with function tracing */
# define inline         inline          notrace
# define __inline__     __inline__      notrace
# define __inline       __inline        notrace
#endif

-- Steve

RE: [PATCH v6] hashtable: introduce a small and naive hashtable

[David Laight]

> Moreover, if your thinking is that we do not need a static inline
> function replicated at every caller, maybe we should introduce a
> lib/hashtable.c that implements those 2 functions.

That was my thought...
Given their nature, I'd guess they aren't critical path.
Probably not worth adding an entire source file though.

With regard to 'inline', when I say it, I really mean it!
Unfortunately some people seem to just type it anyway (rather
like 'register' used to get used) - so the compilers start
ignoring the request.
At least some versions of gcc will usually inline static
functions that are only called once - but even then it can
change its mind for almost no reason.

	David