Skip to contentSkip to conversation

hashtable: introduce a small and naive hashtable

PATCH Superseded Sasha Levin 2 participants 5 messages Sep 15, 2012 – Sep 16, 2012

v5 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

PATCH v5 1/1 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.

---

Changes from v4:

- Addressed comments by Mathieu Desnoyers.

 include/linux/hashtable.h | 190 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 190 insertions(+)
 create mode 100644 include/linux/hashtable.h
include/linux/hashtable.h new file +190 -0
new file mode 100644
index 0000000..6d0c6c2
@@ -0,0 +1,190 @@
+/*
+ * Hash table implementation
+ * (C) 2012  Sasha Levin <[email protected]>
+ */
+
+#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_BITS(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
Signature · 1 line
1.7.12
#1 lore raw
Quoted 57 lines · * Sasha Levin ([email protected]) wrote:

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

---

Changes from v4:

- Addressed comments by Mathieu Desnoyers.

 include/linux/hashtable.h | 190 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 190 insertions(+)
 create mode 100644 include/linux/hashtable.h
include/linux/hashtable.h new file +37 -0
new file mode 100644
index 0000000..6d0c6c2
@@ -0,0 +1,190 @@
+/*
+ * Hash table implementation
+ * (C) 2012  Sasha Levin <[email protected]>
+ */
+
+#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

include/linux/hashtable.h line 47

Quoted 10 lines
include/linux/hashtable.h new file +10 -0
+ * 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_BITS(hashtable); __i++)			\

I think this fails to initialize the whole table. You'd need

HASH_BITS -> HASH_SIZE

Which brings the following question: how did you test this code ? It would be nice to have a small test module along with this patchset that stress-tests this simple hash table in various configurations (on stack, in data, etc).

Also, I don't see how hash_init() can be useful, since DEFINE_HASHTABLE already initialize the array entries. If it is for dynamically allocated hash tables, this also won't work, considering the comment "This has to be a macro since HASH_BITS() will not work on pointers since it calculates the size during preprocessing."

Quoted 23 lines
include/linux/hashtable.h new file +23 -0
+		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

include/linux/hashtable.h line 80

Quoted 10 lines
include/linux/hashtable.h new file +10 -0
+ * @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.

So I get that hash_empty is only expected to be used for statically defined hash tables ? Does it support hash tables in dynamically allocated memory ? On the stack ? If these are never expected to be supported, this should be documented.

Thanks,

Mathieu

Quoted 113 lines
include/linux/hashtable.h new file +110 -0
+ */
+#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
Signature · 1 line
1.7.12
Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#2 lore raw
Quoted 71 lines · Mathieu Desnoyers
Quoted 57 lines · * Sasha Levin ([email protected]) wrote:

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

---

Changes from v4:

- Addressed comments by Mathieu Desnoyers.

 include/linux/hashtable.h | 190 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 190 insertions(+)
 create mode 100644 include/linux/hashtable.h
include/linux/hashtable.h new file +37 -0
new file mode 100644
index 0000000..6d0c6c2
@@ -0,0 +1,190 @@
+/*
+ * Hash table implementation
+ * (C) 2012  Sasha Levin <[email protected]>
+ */
+
+#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

include/linux/hashtable.h line 47

Quoted 10 lines
include/linux/hashtable.h new file +10 -0
+ * 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_BITS(hashtable); __i++)                        \

I think this fails to initialize the whole table. You'd need

Quoted 1 line

HASH_BITS -> HASH_SIZE

Right.

Unfortunately it's pretty hard catching something like this :/

Quoted 4 lines

Which brings the following question: how did you test this code ? It would be nice to have a small test module along with this patchset that stress-tests this simple hash table in various configurations (on stack, in data, etc).

I do two things:

- A small userspace test (since this header works just fine from
userspace as well).
- Build a kernel with all ~20 commits and stresstest it a bit, since
things like workqueue were converted, it finds issues pretty fast.

I agree that there should be something similar to the list sort test we currently have, but I'm not sure if it should be in the scope of this initial patch.

Quoted 5 lines

Also, I don't see how hash_init() can be useful, since DEFINE_HASHTABLE already initialize the array entries. If it is for dynamically allocated hash tables, this also won't work, considering the comment "This has to be a macro since HASH_BITS() will not work on pointers since it calculates the size during preprocessing."

hash_init() is actually used to clear the hashtable in two of the commits I've used to send along with this one. Since as you've said we now have DEFINE_HASHTABLE and DECLARE_HASHTABLE, maybe it should be now called hash_clear() or something similar. I don't have a strong opinion about this.

Quoted 30 lines
Quoted 30 lines
include/linux/hashtable.h new file +30 -0
+             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
Quoted 8 lines

include/linux/hashtable.h line 41

Quoted 3 lines
include/linux/hashtable.h new file +3 -0
+ *
+ * This has to be a macro since HASH_BITS() will not work on pointers since
+ * it calculates the size during preprocessing.

So I get that hash_empty is only expected to be used for statically defined hash tables ? Does it support hash tables in dynamically allocated memory ? On the stack ? If these are never expected to be supported, this should be documented.

Like the rest of the code, this hashtable implementation only works with non-dynamically allocated hashtables (on the stack/statically defined/etc are supported).

How would you create a dynamic hashtable with this code to begin with?

Thanks,
Sasha

#3 lore raw
Quoted 86 lines · * Sasha Levin ([email protected]) wrote:
Quoted 71 lines · Mathieu Desnoyers
Quoted 57 lines · * Sasha Levin ([email protected]) wrote:

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

---

Changes from v4:

- Addressed comments by Mathieu Desnoyers.

 include/linux/hashtable.h | 190 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 190 insertions(+)
 create mode 100644 include/linux/hashtable.h
include/linux/hashtable.h new file +37 -0
new file mode 100644
index 0000000..6d0c6c2
@@ -0,0 +1,190 @@
+/*
+ * Hash table implementation
+ * (C) 2012  Sasha Levin <[email protected]>
+ */
+
+#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

include/linux/hashtable.h line 47

Quoted 10 lines
include/linux/hashtable.h new file +10 -0
+ * 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_BITS(hashtable); __i++)                        \

I think this fails to initialize the whole table. You'd need

Quoted 1 line

HASH_BITS -> HASH_SIZE

Right.

Unfortunately it's pretty hard catching something like this :/

Quoted 4 lines

Which brings the following question: how did you test this code ? It would be nice to have a small test module along with this patchset that stress-tests this simple hash table in various configurations (on stack, in data, etc).

I do two things:

Quoted 8 lines

- A small userspace test (since this header works just fine from
userspace as well).
- Build a kernel with all ~20 commits and stresstest it a bit, since
things like workqueue were converted, it finds issues pretty fast.

I agree that there should be something similar to the list sort test we currently have, but I'm not sure if it should be in the scope of this initial patch.

Fair enough.

Quoted 7 lines
Quoted 6 lines

Also, I don't see how hash_init() can be useful, since DEFINE_HASHTABLE already initialize the array entries. If it is for dynamically allocated hash tables, this also won't work, considering the comment "This has to be a macro since HASH_BITS() will not work on pointers since it calculates the size during preprocessing."

Quoted 5 lines

hash_init() is actually used to clear the hashtable in two of the commits I've used to send along with this one. Since as you've said we now have DEFINE_HASHTABLE and DECLARE_HASHTABLE, maybe it should be now called hash_clear() or something similar. I don't have a strong opinion about this.

If it's used somewhere, then it's fine. People are used to "*_init" functions, so I don't think there is a point in renaming this to "clear".

Quoted 40 lines
Quoted 31 lines
Quoted 31 lines
include/linux/hashtable.h new file +30 -0
+             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
Quoted 8 lines

include/linux/hashtable.h line 41

Quoted 3 lines
include/linux/hashtable.h new file +3 -0
+ *
+ * This has to be a macro since HASH_BITS() will not work on pointers since
+ * it calculates the size during preprocessing.

So I get that hash_empty is only expected to be used for statically defined hash tables ? Does it support hash tables in dynamically allocated memory ? On the stack ? If these are never expected to be supported, this should be documented.

Quoted 5 lines

Like the rest of the code, this hashtable implementation only works with non-dynamically allocated hashtables (on the stack/statically defined/etc are supported).

How would you create a dynamic hashtable with this code to begin with?

With a var. sized array in a structure, e.g.:

struct hashtable {
        size_t len;
        struct hlist_head t[];
};

Then create a hash table allocation function, and turn both hash_empty and hash_init into functions that take a struct simplehash pointer as parameter. The downside is to consume extra space (especially because the array always has a power of 2 len), but the nice thing is that we could use this code with a kmalloc'd/vmalloc'd hash table.

I'm not saying we need to do it (due to the space consumption downside), but that we should at least document this limitation.

Thanks,

Mathieu

Quoted 4 lines

Thanks,
Sasha

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#4 lore raw
Quoted 8 lines · Mathieu Desnoyers
Quoted 1 line

How would you create a dynamic hashtable with this code to begin with?

With a var. sized array in a structure, e.g.:

struct hashtable {
        size_t len;
        struct hlist_head t[];
};
Quoted 8 lines

Then create a hash table allocation function, and turn both hash_empty and hash_init into functions that take a struct simplehash pointer as parameter. The downside is to consume extra space (especially because the array always has a power of 2 len), but the nice thing is that we could use this code with a kmalloc'd/vmalloc'd hash table.

I'm not saying we need to do it (due to the space consumption downside), but that we should at least document this limitation.

We've gone through the process of attempting to support dynamic hashtables in the previous versions of this patch, this turned to complicate the code a lot beyond simply changing the array of hlist_heads into the struct you proposed, so it was decided to not support dynamic hashtables at this point at all.

I thought we've agreed that non-dynamically allocated hashtables are widespread enough to have a dedicated abstraction of their own, and further hashtable implementations may introduce their own API for that.

We can ofcourse open that for discussion again, but I'd rather not go back and forth adding support for dynamic hashtables and removing it again.

Thanks,
Sasha