Re: [PATCH 01/16] hashtable: introduce a small and naive hashtable
Hello, (Sasha, would it be possible to change your MUA so that it breaks long lines. It's pretty difficult to reply to.) On Wed, Aug 15, 2012 at 02:24:49AM +0200, Sasha Levin wrote: > The hashtable uses hlist. hlist provides us with an entire family of > init functions which I'm supposed to use to initialize hlist heads. > > So while a memset(0) will work perfectly here, I consider that > cheating - it results in an uglier code that assumes to know about > hlist internals, and will probably break as soon as someone tries to > do something to hlist. I think we should stick with INIT_HLIST_HEAD(). It's not a hot path and we might add, say, debug fields or initialization magics added later. If this really matters, the right thing to do would be adding something like INIT_HLIST_HEAD_ARRAY(). Thanks. -- tejun -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 01/16] hashtable: introduce a small and naive hashtable
On 08/15/2012 01:25 AM, NeilBrown wrote:
> On Tue, 14 Aug 2012 18:24:35 +0200 Sasha Levin
> wrote:
>
>
>> +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);
>> +}
>
> This seems like an inefficient way to do "memset(hashtable, 0, ...);".
> And in many cases it isn't needed as the hash table is static and initialised
> to zero.
> I note that in the SUNRPC/cache patch you call hash_init(), but in the lockd
> patch you don't. You don't actually need to in either case.
Agreed that the code will run just fine if we wouldn't use hash_init().
> I realise that any optimisation here is for code that is only executed once
> per boot, so no big deal, and even the presence of extra code making the
> kernel bigger is unlikely to be an issue. But I'd at least like to see
> consistency: Either use hash_init everywhere, even when not needed, or only
> use it where absolutely needed which might be no-where because static tables
> are already initialised, and dynamic tables can use GFP_ZERO.
This is a consistency problem. I didn't want to add a module_init() to modules
that didn't have it just to get hash_init() in there.
I'll get it fixed.
> And if you keep hash_init_size I would rather see a memset(0)
My concern with using a memset(0) is that I'm going to break layering.
The hashtable uses hlist. hlist provides us with an entire family of init
functions which I'm supposed to use to initialize hlist heads.
So while a memset(0) will work perfectly here, I consider that cheating - it
results in an uglier code that assumes to know about hlist internals, and will
probably break as soon as someone tries to do something to hlist.
I can think of several alternatives here, and all of them involve changes to
hlist instead of the hashtable:
- Remove INIT_HLIST_HEAD()/HLIST_HEAD()/HLIST_HEAD_INIT() and introduce a
CLEAR_HLIST instead, documenting that it's enough to memset(0) the hlist to
initialize it properly.
- Add a block initializer INIT_HLIST_HEADS() or something similar that would
initialize an array of heads.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 01/16] hashtable: introduce a small and naive hashtable
On Tue, 14 Aug 2012 18:24:35 +0200 Sasha Levin
wrote:
> +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);
> +}
This seems like an inefficient way to do "memset(hashtable, 0, ...);".
And in many cases it isn't needed as the hash table is static and initialised
to zero.
I note that in the SUNRPC/cache patch you call hash_init(), but in the lockd
patch you don't. You don't actually need to in either case.
I realise that any optimisation here is for code that is only executed once
per boot, so no big deal, and even the presence of extra code making the
kernel bigger is unlikely to be an issue. But I'd at least like to see
consistency: Either use hash_init everywhere, even when not needed, or only
use it where absolutely needed which might be no-where because static tables
are already initialised, and dynamic tables can use GFP_ZERO.
And if you keep hash_init_size I would rather see a memset(0)
Thanks,
NeilBrown
signature.asc
Description: PGP signature
[PATCH 01/16] hashtable: introduce a small and naive hashtable
This hashtable implementation is using hlist buckets to provide a simple
hashtable to prevent it from getting reimplemented all over the kernel.
Signed-off-by: Sasha Levin
---
include/linux/hashtable.h | 284 +
1 files changed, 284 insertions(+), 0 deletions(-)
create mode 100644 include/linux/hashtable.h
diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
new file mode 100644
index 000..b18827a
--- /dev/null
+++ b/include/linux/hashtable.h
@@ -0,0 +1,284 @@
+/*
+ * Hash table implementation
+ * (C) 2012 Sasha Levin
+ */
+
+#ifndef _LINUX_HASHTABLE_H
+#define _LINUX_HASHTABLE_H
+
+#include
+#include
+#include
+#include
+#include
+
+#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)))
+
+/* 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 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, [hash_min(key, bits)]);
+
+/**
+ * hash_add - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @node: the 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 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, [hash_min(key, bits)]);
+
+/**
+ * hash_add_rcu - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @node: the 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 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([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: 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: 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 list_head to use as a loop cursor for each bucket
+ * @obj: the type * to use as a loop cursor for each bucket
+ * @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, [bkt], member)
+
+/**
+
[PATCH 01/16] hashtable: introduce a small and naive hashtable
This hashtable implementation is using hlist buckets to provide a simple
hashtable to prevent it from getting reimplemented all over the kernel.
Signed-off-by: Sasha Levin levinsasha...@gmail.com
---
include/linux/hashtable.h | 284 +
1 files changed, 284 insertions(+), 0 deletions(-)
create mode 100644 include/linux/hashtable.h
diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
new file mode 100644
index 000..b18827a
--- /dev/null
+++ b/include/linux/hashtable.h
@@ -0,0 +1,284 @@
+/*
+ * Hash table implementation
+ * (C) 2012 Sasha Levin levinsasha...@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)];
+
+#define HASH_SIZE(bits) (1 (bits))
+#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_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 bucket
+ * @obj: the type * to use as a loop cursor for each bucket
+ * @member: the name of the hlist_node within the struct
+ */
+#define hash_for_each_size(name, bits, bkt, node,
Re: [PATCH 01/16] hashtable: introduce a small and naive hashtable
On Tue, 14 Aug 2012 18:24:35 +0200 Sasha Levin levinsasha...@gmail.com
wrote:
+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);
+}
This seems like an inefficient way to do memset(hashtable, 0, ...);.
And in many cases it isn't needed as the hash table is static and initialised
to zero.
I note that in the SUNRPC/cache patch you call hash_init(), but in the lockd
patch you don't. You don't actually need to in either case.
I realise that any optimisation here is for code that is only executed once
per boot, so no big deal, and even the presence of extra code making the
kernel bigger is unlikely to be an issue. But I'd at least like to see
consistency: Either use hash_init everywhere, even when not needed, or only
use it where absolutely needed which might be no-where because static tables
are already initialised, and dynamic tables can use GFP_ZERO.
And if you keep hash_init_size I would rather see a memset(0)
Thanks,
NeilBrown
signature.asc
Description: PGP signature
Re: [PATCH 01/16] hashtable: introduce a small and naive hashtable
On 08/15/2012 01:25 AM, NeilBrown wrote:
On Tue, 14 Aug 2012 18:24:35 +0200 Sasha Levin levinsasha...@gmail.com
wrote:
+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);
+}
This seems like an inefficient way to do memset(hashtable, 0, ...);.
And in many cases it isn't needed as the hash table is static and initialised
to zero.
I note that in the SUNRPC/cache patch you call hash_init(), but in the lockd
patch you don't. You don't actually need to in either case.
Agreed that the code will run just fine if we wouldn't use hash_init().
I realise that any optimisation here is for code that is only executed once
per boot, so no big deal, and even the presence of extra code making the
kernel bigger is unlikely to be an issue. But I'd at least like to see
consistency: Either use hash_init everywhere, even when not needed, or only
use it where absolutely needed which might be no-where because static tables
are already initialised, and dynamic tables can use GFP_ZERO.
This is a consistency problem. I didn't want to add a module_init() to modules
that didn't have it just to get hash_init() in there.
I'll get it fixed.
And if you keep hash_init_size I would rather see a memset(0)
My concern with using a memset(0) is that I'm going to break layering.
The hashtable uses hlist. hlist provides us with an entire family of init
functions which I'm supposed to use to initialize hlist heads.
So while a memset(0) will work perfectly here, I consider that cheating - it
results in an uglier code that assumes to know about hlist internals, and will
probably break as soon as someone tries to do something to hlist.
I can think of several alternatives here, and all of them involve changes to
hlist instead of the hashtable:
- Remove INIT_HLIST_HEAD()/HLIST_HEAD()/HLIST_HEAD_INIT() and introduce a
CLEAR_HLIST instead, documenting that it's enough to memset(0) the hlist to
initialize it properly.
- Add a block initializer INIT_HLIST_HEADS() or something similar that would
initialize an array of heads.
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 01/16] hashtable: introduce a small and naive hashtable
Hello, (Sasha, would it be possible to change your MUA so that it breaks long lines. It's pretty difficult to reply to.) On Wed, Aug 15, 2012 at 02:24:49AM +0200, Sasha Levin wrote: The hashtable uses hlist. hlist provides us with an entire family of init functions which I'm supposed to use to initialize hlist heads. So while a memset(0) will work perfectly here, I consider that cheating - it results in an uglier code that assumes to know about hlist internals, and will probably break as soon as someone tries to do something to hlist. I think we should stick with INIT_HLIST_HEAD(). It's not a hot path and we might add, say, debug fields or initialization magics added later. If this really matters, the right thing to do would be adding something like INIT_HLIST_HEAD_ARRAY(). Thanks. -- tejun -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
