Re: [PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
On 08/02/2014 11:47 AM, Thomas Graf wrote: > Generic implementation of a resizable, scalable, concurrent hash table > based on [0]. The implementation supports both, fixed size keys specified > via an offset and length, or arbitrary keys via own hash and compare > functions. > > Lookups are lockless and protected as RCU read side critical sections. > Automatic growing/shrinking based on user configurable watermarks is > available while allowing concurrent lookups to take place. > > Objects to be hashed must include a struct rhash_head. The reason for not > using the existing struct hlist_head is that the expansion and shrinking > will have two buckets point to a single entry which would lead in obscure > reverse chaining behaviour. > > Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined. > > [0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf > > Signed-off-by: Thomas Graf > --- > include/linux/rhashtable.h | 213 > lib/Kconfig.debug | 8 + > lib/Makefile | 2 +- > lib/rhashtable.c | 797 > + > 4 files changed, 1019 insertions(+), 1 deletion(-) > create mode 100644 include/linux/rhashtable.h > create mode 100644 lib/rhashtable.c > Reviewed-by: Nikolay Aleksandrov -- 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/
[PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
Generic implementation of a resizable, scalable, concurrent hash table
based on [0]. The implementation supports both, fixed size keys specified
via an offset and length, or arbitrary keys via own hash and compare
functions.
Lookups are lockless and protected as RCU read side critical sections.
Automatic growing/shrinking based on user configurable watermarks is
available while allowing concurrent lookups to take place.
Objects to be hashed must include a struct rhash_head. The reason for not
using the existing struct hlist_head is that the expansion and shrinking
will have two buckets point to a single entry which would lead in obscure
reverse chaining behaviour.
Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined.
[0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
Signed-off-by: Thomas Graf
---
include/linux/rhashtable.h | 213
lib/Kconfig.debug | 8 +
lib/Makefile | 2 +-
lib/rhashtable.c | 797 +
4 files changed, 1019 insertions(+), 1 deletion(-)
create mode 100644 include/linux/rhashtable.h
create mode 100644 lib/rhashtable.c
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
new file mode 100644
index 000..9cda293
--- /dev/null
+++ b/include/linux/rhashtable.h
@@ -0,0 +1,213 @@
+/*
+ * Resizable, Scalable, Concurrent Hash Table
+ *
+ * Copyright (c) 2014 Thomas Graf
+ * Copyright (c) 2008-2014 Patrick McHardy
+ *
+ * Based on the following paper by Josh Triplett, Paul E. McKenney
+ * and Jonathan Walpole:
+ * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
+ *
+ * Code partially derived from nft_hash
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#ifndef _LINUX_RHASHTABLE_H
+#define _LINUX_RHASHTABLE_H
+
+#include
+
+struct rhash_head {
+ struct rhash_head *next;
+};
+
+#define INIT_HASH_HEAD(ptr) ((ptr)->next = NULL)
+
+struct bucket_table {
+ size_t size;
+ struct rhash_head __rcu *buckets[];
+};
+
+typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
+typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 seed);
+
+struct rhashtable;
+
+/**
+ * struct rhashtable_params - Hash table construction parameters
+ * @nelem_hint: Hint on number of elements, should be 75% of desired size
+ * @key_len: Length of key
+ * @key_offset: Offset of key in struct to be hashed
+ * @head_offset: Offset of rhash_head in struct to be hashed
+ * @hash_rnd: Seed to use while hashing
+ * @max_shift: Maximum number of shifts while expanding
+ * @hashfn: Function to hash key
+ * @obj_hashfn: Function to hash object
+ * @grow_decision: If defined, may return true if table should expand
+ * @shrink_decision: If defined, may return true if table should shrink
+ * @mutex_is_held: Must return true if protecting mutex is held
+ */
+struct rhashtable_params {
+ size_t nelem_hint;
+ size_t key_len;
+ size_t key_offset;
+ size_t head_offset;
+ u32 hash_rnd;
+ size_t max_shift;
+ rht_hashfn_thashfn;
+ rht_obj_hashfn_tobj_hashfn;
+ bool(*grow_decision)(const struct rhashtable *ht,
+size_t new_size);
+ bool(*shrink_decision)(const struct rhashtable *ht,
+ size_t new_size);
+ int (*mutex_is_held)(void);
+};
+
+/**
+ * struct rhashtable - Hash table handle
+ * @tbl: Bucket table
+ * @nelems: Number of elements in table
+ * @shift: Current size (1 << shift)
+ * @p: Configuration parameters
+ */
+struct rhashtable {
+ struct bucket_table __rcu *tbl;
+ size_t nelems;
+ size_t shift;
+ struct rhashtable_paramsp;
+};
+
+#ifdef CONFIG_PROVE_LOCKING
+int lockdep_rht_mutex_is_held(const struct rhashtable *ht);
+#else
+static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
+{
+ return 1;
+}
+#endif /* CONFIG_PROVE_LOCKING */
+
+int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);
+
+u32 rhashtable_hashfn(const struct rhashtable *ht, const void *key, u32 len);
+u32 rhashtable_obj_hashfn(const struct rhashtable *ht, void *ptr);
+
+void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
+struct rhash_head **pprev, gfp_t flags);
+
+bool
[PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
Generic implementation of a resizable, scalable, concurrent hash table
based on [0]. The implementation supports both, fixed size keys specified
via an offset and length, or arbitrary keys via own hash and compare
functions.
Lookups are lockless and protected as RCU read side critical sections.
Automatic growing/shrinking based on user configurable watermarks is
available while allowing concurrent lookups to take place.
Objects to be hashed must include a struct rhash_head. The reason for not
using the existing struct hlist_head is that the expansion and shrinking
will have two buckets point to a single entry which would lead in obscure
reverse chaining behaviour.
Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined.
[0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
Signed-off-by: Thomas Graf tg...@suug.ch
---
include/linux/rhashtable.h | 213
lib/Kconfig.debug | 8 +
lib/Makefile | 2 +-
lib/rhashtable.c | 797 +
4 files changed, 1019 insertions(+), 1 deletion(-)
create mode 100644 include/linux/rhashtable.h
create mode 100644 lib/rhashtable.c
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
new file mode 100644
index 000..9cda293
--- /dev/null
+++ b/include/linux/rhashtable.h
@@ -0,0 +1,213 @@
+/*
+ * Resizable, Scalable, Concurrent Hash Table
+ *
+ * Copyright (c) 2014 Thomas Graf tg...@suug.ch
+ * Copyright (c) 2008-2014 Patrick McHardy ka...@trash.net
+ *
+ * Based on the following paper by Josh Triplett, Paul E. McKenney
+ * and Jonathan Walpole:
+ * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
+ *
+ * Code partially derived from nft_hash
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#ifndef _LINUX_RHASHTABLE_H
+#define _LINUX_RHASHTABLE_H
+
+#include linux/rculist.h
+
+struct rhash_head {
+ struct rhash_head *next;
+};
+
+#define INIT_HASH_HEAD(ptr) ((ptr)-next = NULL)
+
+struct bucket_table {
+ size_t size;
+ struct rhash_head __rcu *buckets[];
+};
+
+typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
+typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 seed);
+
+struct rhashtable;
+
+/**
+ * struct rhashtable_params - Hash table construction parameters
+ * @nelem_hint: Hint on number of elements, should be 75% of desired size
+ * @key_len: Length of key
+ * @key_offset: Offset of key in struct to be hashed
+ * @head_offset: Offset of rhash_head in struct to be hashed
+ * @hash_rnd: Seed to use while hashing
+ * @max_shift: Maximum number of shifts while expanding
+ * @hashfn: Function to hash key
+ * @obj_hashfn: Function to hash object
+ * @grow_decision: If defined, may return true if table should expand
+ * @shrink_decision: If defined, may return true if table should shrink
+ * @mutex_is_held: Must return true if protecting mutex is held
+ */
+struct rhashtable_params {
+ size_t nelem_hint;
+ size_t key_len;
+ size_t key_offset;
+ size_t head_offset;
+ u32 hash_rnd;
+ size_t max_shift;
+ rht_hashfn_thashfn;
+ rht_obj_hashfn_tobj_hashfn;
+ bool(*grow_decision)(const struct rhashtable *ht,
+size_t new_size);
+ bool(*shrink_decision)(const struct rhashtable *ht,
+ size_t new_size);
+ int (*mutex_is_held)(void);
+};
+
+/**
+ * struct rhashtable - Hash table handle
+ * @tbl: Bucket table
+ * @nelems: Number of elements in table
+ * @shift: Current size (1 shift)
+ * @p: Configuration parameters
+ */
+struct rhashtable {
+ struct bucket_table __rcu *tbl;
+ size_t nelems;
+ size_t shift;
+ struct rhashtable_paramsp;
+};
+
+#ifdef CONFIG_PROVE_LOCKING
+int lockdep_rht_mutex_is_held(const struct rhashtable *ht);
+#else
+static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
+{
+ return 1;
+}
+#endif /* CONFIG_PROVE_LOCKING */
+
+int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);
+
+u32 rhashtable_hashfn(const struct rhashtable *ht, const void *key, u32 len);
+u32 rhashtable_obj_hashfn(const struct rhashtable *ht, void *ptr);
+
+void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
+struct
Re: [PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
On 08/02/2014 11:47 AM, Thomas Graf wrote: Generic implementation of a resizable, scalable, concurrent hash table based on [0]. The implementation supports both, fixed size keys specified via an offset and length, or arbitrary keys via own hash and compare functions. Lookups are lockless and protected as RCU read side critical sections. Automatic growing/shrinking based on user configurable watermarks is available while allowing concurrent lookups to take place. Objects to be hashed must include a struct rhash_head. The reason for not using the existing struct hlist_head is that the expansion and shrinking will have two buckets point to a single entry which would lead in obscure reverse chaining behaviour. Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined. [0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf Signed-off-by: Thomas Graf tg...@suug.ch --- include/linux/rhashtable.h | 213 lib/Kconfig.debug | 8 + lib/Makefile | 2 +- lib/rhashtable.c | 797 + 4 files changed, 1019 insertions(+), 1 deletion(-) create mode 100644 include/linux/rhashtable.h create mode 100644 lib/rhashtable.c Reviewed-by: Nikolay Aleksandrov niko...@redhat.com -- 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/
[PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
Generic implementation of a resizable, scalable, concurrent hash table
based on [0]. The implementation supports both, fixed size keys specified
via an offset and length, or arbitrary keys via own hash and compare
functions.
Lookups are lockless and protected as RCU read side critical sections.
Automatic growing/shrinking based on user configurable watermarks is
available while allowing concurrent lookups to take place.
Objects to be hashed must include a struct rhash_head. The reason for not
using the existing struct hlist_head is that the expansion and shrinking
will have two buckets point to a single entry which would lead in obscure
reverse chaining behaviour.
Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined.
[0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
Signed-off-by: Thomas Graf
---
include/linux/rhashtable.h | 213
lib/Kconfig.debug | 8 +
lib/Makefile | 2 +-
lib/rhashtable.c | 797 +
4 files changed, 1019 insertions(+), 1 deletion(-)
create mode 100644 include/linux/rhashtable.h
create mode 100644 lib/rhashtable.c
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
new file mode 100644
index 000..9cda293
--- /dev/null
+++ b/include/linux/rhashtable.h
@@ -0,0 +1,213 @@
+/*
+ * Resizable, Scalable, Concurrent Hash Table
+ *
+ * Copyright (c) 2014 Thomas Graf
+ * Copyright (c) 2008-2014 Patrick McHardy
+ *
+ * Based on the following paper by Josh Triplett, Paul E. McKenney
+ * and Jonathan Walpole:
+ * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
+ *
+ * Code partially derived from nft_hash
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#ifndef _LINUX_RHASHTABLE_H
+#define _LINUX_RHASHTABLE_H
+
+#include
+
+struct rhash_head {
+ struct rhash_head *next;
+};
+
+#define INIT_HASH_HEAD(ptr) ((ptr)->next = NULL)
+
+struct bucket_table {
+ size_t size;
+ struct rhash_head __rcu *buckets[];
+};
+
+typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
+typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 seed);
+
+struct rhashtable;
+
+/**
+ * struct rhashtable_params - Hash table construction parameters
+ * @nelem_hint: Hint on number of elements, should be 75% of desired size
+ * @key_len: Length of key
+ * @key_offset: Offset of key in struct to be hashed
+ * @head_offset: Offset of rhash_head in struct to be hashed
+ * @hash_rnd: Seed to use while hashing
+ * @max_shift: Maximum number of shifts while expanding
+ * @hashfn: Function to hash key
+ * @obj_hashfn: Function to hash object
+ * @grow_decision: If defined, may return true if table should expand
+ * @shrink_decision: If defined, may return true if table should shrink
+ * @mutex_is_held: Must return true if protecting mutex is held
+ */
+struct rhashtable_params {
+ size_t nelem_hint;
+ size_t key_len;
+ size_t key_offset;
+ size_t head_offset;
+ u32 hash_rnd;
+ size_t max_shift;
+ rht_hashfn_thashfn;
+ rht_obj_hashfn_tobj_hashfn;
+ bool(*grow_decision)(const struct rhashtable *ht,
+size_t new_size);
+ bool(*shrink_decision)(const struct rhashtable *ht,
+ size_t new_size);
+ int (*mutex_is_held)(void);
+};
+
+/**
+ * struct rhashtable - Hash table handle
+ * @tbl: Bucket table
+ * @nelems: Number of elements in table
+ * @shift: Current size (1 << shift)
+ * @p: Configuration parameters
+ */
+struct rhashtable {
+ struct bucket_table __rcu *tbl;
+ size_t nelems;
+ size_t shift;
+ struct rhashtable_paramsp;
+};
+
+#ifdef CONFIG_PROVE_LOCKING
+int lockdep_rht_mutex_is_held(const struct rhashtable *ht);
+#else
+static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
+{
+ return 1;
+}
+#endif /* CONFIG_PROVE_LOCKING */
+
+int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);
+
+u32 rhashtable_hashfn(const struct rhashtable *ht, const void *key, u32 len);
+u32 rhashtable_obj_hashfn(const struct rhashtable *ht, void *ptr);
+
+void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
+struct rhash_head **pprev, gfp_t flags);
+
+bool
Re: [PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
On 08/01/14 at 12:01pm, Nikolay Aleksandrov wrote: > I see that ht->shift is being set but then ht is being zeroed, wouldn't this > allow for the table to double ilog2(tbl->size) times more ? Absolutely, thanks for catching this! -- 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 net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
On 08/01/14 at 12:26pm, Patrick McHardy wrote: > On Fri, Aug 01, 2014 at 10:51:58AM +0200, Thomas Graf wrote: > > --- /dev/null > > +++ b/include/linux/rhashtable.h > > @@ -0,0 +1,213 @@ > > +/* > > + * Resizable, Scalable, Concurrent Hash Table > > + * > > + * Copyright (c) 2014 Thomas Graf > > + * > > + * Based on the following paper by Josh Triplett, Paul E. McKenney > > + * and Jonathan Walpole: > > + * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf > > + * > > + * Code partially derived from nft_hash: > > + * Copyright (c) 2008-2014 Patrick McHardy > > Minor request: german copyright law as an assumption of authorship for > authors marked in the work. When doing GPL enforcement I would prefer > any discussions about what derived from specifically means in this > case and whether this constitutes a normal statement of authorship, > and since this clearly contains a lot of literal code I have written, > please change this to something like > > Copyright ... Thomas Graf > Copyright ... Patrick McHardy > > ... > > Code partially derived from nft_hash. > > Thanks! Sure, it was not my intention to hide ownership in any way. -- 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 net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
On Fri, Aug 01, 2014 at 10:51:58AM +0200, Thomas Graf wrote: > --- /dev/null > +++ b/include/linux/rhashtable.h > @@ -0,0 +1,213 @@ > +/* > + * Resizable, Scalable, Concurrent Hash Table > + * > + * Copyright (c) 2014 Thomas Graf > + * > + * Based on the following paper by Josh Triplett, Paul E. McKenney > + * and Jonathan Walpole: > + * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf > + * > + * Code partially derived from nft_hash: > + * Copyright (c) 2008-2014 Patrick McHardy Minor request: german copyright law as an assumption of authorship for authors marked in the work. When doing GPL enforcement I would prefer any discussions about what derived from specifically means in this case and whether this constitutes a normal statement of authorship, and since this clearly contains a lot of literal code I have written, please change this to something like Copyright ... Thomas Graf Copyright ... Patrick McHardy ... Code partially derived from nft_hash. Thanks! > + * > + * This program is free software; you can redistribute it and/or modify > + * it under the terms of the GNU General Public License version 2 as > + * published by the Free Software Foundation. > + */ -- 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 net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
On 08/01/2014 10:51 AM, Thomas Graf wrote:
> Generic implementation of a resizable, scalable, concurrent hash table
> based on [0]. The implementation supports both, fixed size keys specified
> via an offset and length, or arbitrary keys via own hash and compare
> functions.
>
> Lookups are lockless and protected as RCU read side critical sections.
> Automatic growing/shrinking based on user configurable watermarks is
> available while allowing concurrent lookups to take place.
>
> Objects to be hashed must include a struct rhash_head. The reason for not
> using the existing struct hlist_head is that the expansion and shrinking
> will have two buckets point to a single entry which would lead in obscure
> reverse chaining behaviour.
>
> Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined.
>
> [0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
>
> Signed-off-by: Thomas Graf
> ---
> include/linux/rhashtable.h | 213
> lib/Kconfig.debug | 8 +
> lib/Makefile | 2 +-
> lib/rhashtable.c | 797
> +
> 4 files changed, 1019 insertions(+), 1 deletion(-)
> create mode 100644 include/linux/rhashtable.h
> create mode 100644 lib/rhashtable.c
>
<>
> +
> +/**
> + * rhashtable_init - initialize a new hash table
> + * @ht: hash table to be initialized
> + * @params: configuration parameters
> + *
> + * Initializes a new hash table based on the provided configuration
> + * parameters. A table can be configured either with a variable or
> + * fixed length key:
> + *
> + * Configuration Example 1: Fixed length keys
> + * struct test_obj {
> + * int key;
> + * void * my_member;
> + * struct rhash_head node;
> + * };
> + *
> + * struct rhashtable_params params = {
> + * .head_offset = offsetof(struct test_obj, node),
> + * .key_offset = offsetof(struct test_obj, key),
> + * .key_len = sizeof(int),
> + * .hashfn = arch_fast_hash,
> + * .mutex_is_held = _mutex_is_held,
> + * };
> + *
> + * Configuration Example 2: Variable length keys
> + * struct test_obj {
> + * [...]
> + * struct rhash_head node;
> + * };
> + *
> + * u32 my_hash_fn(const void *data, u32 seed)
> + * {
> + * struct test_obj *obj = data;
> + *
> + * return [... hash ...];
> + * }
> + *
> + * struct rhashtable_params params = {
> + * .head_offset = offsetof(struct test_obj, node),
> + * .hashfn = arch_fast_hash,
> + * .obj_hashfn = my_hash_fn,
> + * .mutex_is_held = _mutex_is_held,
> + * };
> + */
> +int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
> +{
> + struct bucket_table *tbl;
> + size_t size;
> +
> + size = HASH_MIN_SIZE;
> +
> + if ((params->key_len && !params->hashfn) ||
> + (!params->key_len && !params->obj_hashfn))
> + return -EINVAL;
> +
> + if (params->nelem_hint)
> + size = rounded_hashtable_size(params->nelem_hint);
> +
> + tbl = bucket_table_alloc(size, GFP_KERNEL);
> + if (tbl == NULL)
> + return -ENOMEM;
> +
> + ht->shift = ilog2(tbl->size);
> +
> + memset(ht, 0, sizeof(*ht));
Hi Thomas,
I see that ht->shift is being set but then ht is being zeroed, wouldn't this
allow for the table to double ilog2(tbl->size) times more ?
Nik
> + memcpy(>p, params, sizeof(*params));
> + RCU_INIT_POINTER(ht->tbl, tbl);
> +
> + if (!ht->p.hash_rnd)
> + get_random_bytes(>p.hash_rnd, sizeof(ht->p.hash_rnd));
> +
> + return 0;
> +}
> +EXPORT_SYMBOL_GPL(rhashtable_init);
> +
> +/**
> + * rhashtable_destroy - destroy hash table
> + * @ht: the hash table to destroy
> + *
> + * Frees the bucket array.
> + */
> +void rhashtable_destroy(const struct rhashtable *ht)
> +{
> + const struct bucket_table *tbl = rht_dereference(ht->tbl, ht);
> +
> + bucket_table_free(tbl);
> +}
> +EXPORT_SYMBOL_GPL(rhashtable_destroy);
<>
--
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/
[PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
Generic implementation of a resizable, scalable, concurrent hash table
based on [0]. The implementation supports both, fixed size keys specified
via an offset and length, or arbitrary keys via own hash and compare
functions.
Lookups are lockless and protected as RCU read side critical sections.
Automatic growing/shrinking based on user configurable watermarks is
available while allowing concurrent lookups to take place.
Objects to be hashed must include a struct rhash_head. The reason for not
using the existing struct hlist_head is that the expansion and shrinking
will have two buckets point to a single entry which would lead in obscure
reverse chaining behaviour.
Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined.
[0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
Signed-off-by: Thomas Graf
---
include/linux/rhashtable.h | 213
lib/Kconfig.debug | 8 +
lib/Makefile | 2 +-
lib/rhashtable.c | 797 +
4 files changed, 1019 insertions(+), 1 deletion(-)
create mode 100644 include/linux/rhashtable.h
create mode 100644 lib/rhashtable.c
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
new file mode 100644
index 000..0a8f6cc
--- /dev/null
+++ b/include/linux/rhashtable.h
@@ -0,0 +1,213 @@
+/*
+ * Resizable, Scalable, Concurrent Hash Table
+ *
+ * Copyright (c) 2014 Thomas Graf
+ *
+ * Based on the following paper by Josh Triplett, Paul E. McKenney
+ * and Jonathan Walpole:
+ * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
+ *
+ * Code partially derived from nft_hash:
+ * Copyright (c) 2008-2014 Patrick McHardy
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#ifndef _LINUX_RHASHTABLE_H
+#define _LINUX_RHASHTABLE_H
+
+#include
+
+struct rhash_head {
+ struct rhash_head *next;
+};
+
+#define INIT_HASH_HEAD(ptr) ((ptr)->next = NULL)
+
+struct bucket_table {
+ size_t size;
+ struct rhash_head __rcu *buckets[];
+};
+
+typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
+typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 seed);
+
+struct rhashtable;
+
+/**
+ * struct rhashtable_params - Hash table construction parameters
+ * @nelem_hint: Hint on number of elements expected
+ * @key_len: Length of key
+ * @key_offset: Offset of key in struct to be hashed
+ * @head_offset: Offset of rhash_head in struct to be hashed
+ * @hash_rnd: Seed to use while hashing
+ * @max_shift: Maximum number of shifts while expanding
+ * @hashfn: Function to hash key
+ * @obj_hashfn: Function to hash object
+ * @grow_decision: If defined, may return true if table should expand
+ * @shrink_decision: If defined, may return true if table should shrink
+ * @mutex_is_held: Must return true if protecting mutex is held
+ */
+struct rhashtable_params {
+ size_t nelem_hint;
+ size_t key_len;
+ size_t key_offset;
+ size_t head_offset;
+ u32 hash_rnd;
+ size_t max_shift;
+ rht_hashfn_thashfn;
+ rht_obj_hashfn_tobj_hashfn;
+ bool(*grow_decision)(const struct rhashtable *ht,
+size_t new_size);
+ bool(*shrink_decision)(const struct rhashtable *ht,
+ size_t new_size);
+ int (*mutex_is_held)(void);
+};
+
+/**
+ * struct rhashtable - Hash table handle
+ * @tbl: Bucket table
+ * @nelems: Number of elements in table
+ * @shift: Current size (1 << shift)
+ * @p: Configuration parameters
+ */
+struct rhashtable {
+ struct bucket_table __rcu *tbl;
+ size_t nelems;
+ size_t shift;
+ struct rhashtable_paramsp;
+};
+
+#ifdef CONFIG_PROVE_LOCKING
+int lockdep_rht_mutex_is_held(const struct rhashtable *ht);
+#else
+static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
+{
+ return 1;
+}
+#endif /* CONFIG_PROVE_LOCKING */
+
+int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);
+
+u32 rhashtable_hashfn(const struct rhashtable *ht, const void *key, u32 len);
+u32 rhashtable_obj_hashfn(const struct rhashtable *ht, void *ptr);
+
+void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
+struct rhash_head **pprev, gfp_t flags);
+
+bool rht_grow_above_75(const struct
[PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
Generic implementation of a resizable, scalable, concurrent hash table
based on [0]. The implementation supports both, fixed size keys specified
via an offset and length, or arbitrary keys via own hash and compare
functions.
Lookups are lockless and protected as RCU read side critical sections.
Automatic growing/shrinking based on user configurable watermarks is
available while allowing concurrent lookups to take place.
Objects to be hashed must include a struct rhash_head. The reason for not
using the existing struct hlist_head is that the expansion and shrinking
will have two buckets point to a single entry which would lead in obscure
reverse chaining behaviour.
Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined.
[0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
Signed-off-by: Thomas Graf tg...@suug.ch
---
include/linux/rhashtable.h | 213
lib/Kconfig.debug | 8 +
lib/Makefile | 2 +-
lib/rhashtable.c | 797 +
4 files changed, 1019 insertions(+), 1 deletion(-)
create mode 100644 include/linux/rhashtable.h
create mode 100644 lib/rhashtable.c
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
new file mode 100644
index 000..0a8f6cc
--- /dev/null
+++ b/include/linux/rhashtable.h
@@ -0,0 +1,213 @@
+/*
+ * Resizable, Scalable, Concurrent Hash Table
+ *
+ * Copyright (c) 2014 Thomas Graf tg...@suug.ch
+ *
+ * Based on the following paper by Josh Triplett, Paul E. McKenney
+ * and Jonathan Walpole:
+ * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
+ *
+ * Code partially derived from nft_hash:
+ * Copyright (c) 2008-2014 Patrick McHardy ka...@trash.net
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#ifndef _LINUX_RHASHTABLE_H
+#define _LINUX_RHASHTABLE_H
+
+#include linux/rculist.h
+
+struct rhash_head {
+ struct rhash_head *next;
+};
+
+#define INIT_HASH_HEAD(ptr) ((ptr)-next = NULL)
+
+struct bucket_table {
+ size_t size;
+ struct rhash_head __rcu *buckets[];
+};
+
+typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
+typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 seed);
+
+struct rhashtable;
+
+/**
+ * struct rhashtable_params - Hash table construction parameters
+ * @nelem_hint: Hint on number of elements expected
+ * @key_len: Length of key
+ * @key_offset: Offset of key in struct to be hashed
+ * @head_offset: Offset of rhash_head in struct to be hashed
+ * @hash_rnd: Seed to use while hashing
+ * @max_shift: Maximum number of shifts while expanding
+ * @hashfn: Function to hash key
+ * @obj_hashfn: Function to hash object
+ * @grow_decision: If defined, may return true if table should expand
+ * @shrink_decision: If defined, may return true if table should shrink
+ * @mutex_is_held: Must return true if protecting mutex is held
+ */
+struct rhashtable_params {
+ size_t nelem_hint;
+ size_t key_len;
+ size_t key_offset;
+ size_t head_offset;
+ u32 hash_rnd;
+ size_t max_shift;
+ rht_hashfn_thashfn;
+ rht_obj_hashfn_tobj_hashfn;
+ bool(*grow_decision)(const struct rhashtable *ht,
+size_t new_size);
+ bool(*shrink_decision)(const struct rhashtable *ht,
+ size_t new_size);
+ int (*mutex_is_held)(void);
+};
+
+/**
+ * struct rhashtable - Hash table handle
+ * @tbl: Bucket table
+ * @nelems: Number of elements in table
+ * @shift: Current size (1 shift)
+ * @p: Configuration parameters
+ */
+struct rhashtable {
+ struct bucket_table __rcu *tbl;
+ size_t nelems;
+ size_t shift;
+ struct rhashtable_paramsp;
+};
+
+#ifdef CONFIG_PROVE_LOCKING
+int lockdep_rht_mutex_is_held(const struct rhashtable *ht);
+#else
+static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
+{
+ return 1;
+}
+#endif /* CONFIG_PROVE_LOCKING */
+
+int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);
+
+u32 rhashtable_hashfn(const struct rhashtable *ht, const void *key, u32 len);
+u32 rhashtable_obj_hashfn(const struct rhashtable *ht, void *ptr);
+
+void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
+struct rhash_head **pprev, gfp_t
Re: [PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
On 08/01/2014 10:51 AM, Thomas Graf wrote:
Generic implementation of a resizable, scalable, concurrent hash table
based on [0]. The implementation supports both, fixed size keys specified
via an offset and length, or arbitrary keys via own hash and compare
functions.
Lookups are lockless and protected as RCU read side critical sections.
Automatic growing/shrinking based on user configurable watermarks is
available while allowing concurrent lookups to take place.
Objects to be hashed must include a struct rhash_head. The reason for not
using the existing struct hlist_head is that the expansion and shrinking
will have two buckets point to a single entry which would lead in obscure
reverse chaining behaviour.
Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined.
[0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
Signed-off-by: Thomas Graf tg...@suug.ch
---
include/linux/rhashtable.h | 213
lib/Kconfig.debug | 8 +
lib/Makefile | 2 +-
lib/rhashtable.c | 797
+
4 files changed, 1019 insertions(+), 1 deletion(-)
create mode 100644 include/linux/rhashtable.h
create mode 100644 lib/rhashtable.c
snip
+
+/**
+ * rhashtable_init - initialize a new hash table
+ * @ht: hash table to be initialized
+ * @params: configuration parameters
+ *
+ * Initializes a new hash table based on the provided configuration
+ * parameters. A table can be configured either with a variable or
+ * fixed length key:
+ *
+ * Configuration Example 1: Fixed length keys
+ * struct test_obj {
+ * int key;
+ * void * my_member;
+ * struct rhash_head node;
+ * };
+ *
+ * struct rhashtable_params params = {
+ * .head_offset = offsetof(struct test_obj, node),
+ * .key_offset = offsetof(struct test_obj, key),
+ * .key_len = sizeof(int),
+ * .hashfn = arch_fast_hash,
+ * .mutex_is_held = my_mutex_is_held,
+ * };
+ *
+ * Configuration Example 2: Variable length keys
+ * struct test_obj {
+ * [...]
+ * struct rhash_head node;
+ * };
+ *
+ * u32 my_hash_fn(const void *data, u32 seed)
+ * {
+ * struct test_obj *obj = data;
+ *
+ * return [... hash ...];
+ * }
+ *
+ * struct rhashtable_params params = {
+ * .head_offset = offsetof(struct test_obj, node),
+ * .hashfn = arch_fast_hash,
+ * .obj_hashfn = my_hash_fn,
+ * .mutex_is_held = my_mutex_is_held,
+ * };
+ */
+int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
+{
+ struct bucket_table *tbl;
+ size_t size;
+
+ size = HASH_MIN_SIZE;
+
+ if ((params-key_len !params-hashfn) ||
+ (!params-key_len !params-obj_hashfn))
+ return -EINVAL;
+
+ if (params-nelem_hint)
+ size = rounded_hashtable_size(params-nelem_hint);
+
+ tbl = bucket_table_alloc(size, GFP_KERNEL);
+ if (tbl == NULL)
+ return -ENOMEM;
+
+ ht-shift = ilog2(tbl-size);
+
+ memset(ht, 0, sizeof(*ht));
Hi Thomas,
I see that ht-shift is being set but then ht is being zeroed, wouldn't this
allow for the table to double ilog2(tbl-size) times more ?
Nik
+ memcpy(ht-p, params, sizeof(*params));
+ RCU_INIT_POINTER(ht-tbl, tbl);
+
+ if (!ht-p.hash_rnd)
+ get_random_bytes(ht-p.hash_rnd, sizeof(ht-p.hash_rnd));
+
+ return 0;
+}
+EXPORT_SYMBOL_GPL(rhashtable_init);
+
+/**
+ * rhashtable_destroy - destroy hash table
+ * @ht: the hash table to destroy
+ *
+ * Frees the bucket array.
+ */
+void rhashtable_destroy(const struct rhashtable *ht)
+{
+ const struct bucket_table *tbl = rht_dereference(ht-tbl, ht);
+
+ bucket_table_free(tbl);
+}
+EXPORT_SYMBOL_GPL(rhashtable_destroy);
snip
--
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 net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
On Fri, Aug 01, 2014 at 10:51:58AM +0200, Thomas Graf wrote: --- /dev/null +++ b/include/linux/rhashtable.h @@ -0,0 +1,213 @@ +/* + * Resizable, Scalable, Concurrent Hash Table + * + * Copyright (c) 2014 Thomas Graf tg...@suug.ch + * + * Based on the following paper by Josh Triplett, Paul E. McKenney + * and Jonathan Walpole: + * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf + * + * Code partially derived from nft_hash: + * Copyright (c) 2008-2014 Patrick McHardy ka...@trash.net Minor request: german copyright law as an assumption of authorship for authors marked in the work. When doing GPL enforcement I would prefer any discussions about what derived from specifically means in this case and whether this constitutes a normal statement of authorship, and since this clearly contains a lot of literal code I have written, please change this to something like Copyright ... Thomas Graf Copyright ... Patrick McHardy ... Code partially derived from nft_hash. Thanks! + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + */ -- 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 net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
On 08/01/14 at 12:26pm, Patrick McHardy wrote: On Fri, Aug 01, 2014 at 10:51:58AM +0200, Thomas Graf wrote: --- /dev/null +++ b/include/linux/rhashtable.h @@ -0,0 +1,213 @@ +/* + * Resizable, Scalable, Concurrent Hash Table + * + * Copyright (c) 2014 Thomas Graf tg...@suug.ch + * + * Based on the following paper by Josh Triplett, Paul E. McKenney + * and Jonathan Walpole: + * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf + * + * Code partially derived from nft_hash: + * Copyright (c) 2008-2014 Patrick McHardy ka...@trash.net Minor request: german copyright law as an assumption of authorship for authors marked in the work. When doing GPL enforcement I would prefer any discussions about what derived from specifically means in this case and whether this constitutes a normal statement of authorship, and since this clearly contains a lot of literal code I have written, please change this to something like Copyright ... Thomas Graf Copyright ... Patrick McHardy ... Code partially derived from nft_hash. Thanks! Sure, it was not my intention to hide ownership in any way. -- 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 net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
On 08/01/14 at 12:01pm, Nikolay Aleksandrov wrote: I see that ht-shift is being set but then ht is being zeroed, wouldn't this allow for the table to double ilog2(tbl-size) times more ? Absolutely, thanks for catching this! -- 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/
[PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
Generic implementation of a resizable, scalable, concurrent hash table
based on [0]. The implementation supports both, fixed size keys specified
via an offset and length, or arbitrary keys via own hash and compare
functions.
Lookups are lockless and protected as RCU read side critical sections.
Automatic growing/shrinking based on user configurable watermarks is
available while allowing concurrent lookups to take place.
Objects to be hashed must include a struct rhash_head. The reason for not
using the existing struct hlist_head is that the expansion and shrinking
will have two buckets point to a single entry which would lead in obscure
reverse chaining behaviour.
Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined.
[0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
Signed-off-by: Thomas Graf tg...@suug.ch
---
include/linux/rhashtable.h | 213
lib/Kconfig.debug | 8 +
lib/Makefile | 2 +-
lib/rhashtable.c | 797 +
4 files changed, 1019 insertions(+), 1 deletion(-)
create mode 100644 include/linux/rhashtable.h
create mode 100644 lib/rhashtable.c
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
new file mode 100644
index 000..9cda293
--- /dev/null
+++ b/include/linux/rhashtable.h
@@ -0,0 +1,213 @@
+/*
+ * Resizable, Scalable, Concurrent Hash Table
+ *
+ * Copyright (c) 2014 Thomas Graf tg...@suug.ch
+ * Copyright (c) 2008-2014 Patrick McHardy ka...@trash.net
+ *
+ * Based on the following paper by Josh Triplett, Paul E. McKenney
+ * and Jonathan Walpole:
+ * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
+ *
+ * Code partially derived from nft_hash
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#ifndef _LINUX_RHASHTABLE_H
+#define _LINUX_RHASHTABLE_H
+
+#include linux/rculist.h
+
+struct rhash_head {
+ struct rhash_head *next;
+};
+
+#define INIT_HASH_HEAD(ptr) ((ptr)-next = NULL)
+
+struct bucket_table {
+ size_t size;
+ struct rhash_head __rcu *buckets[];
+};
+
+typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
+typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 seed);
+
+struct rhashtable;
+
+/**
+ * struct rhashtable_params - Hash table construction parameters
+ * @nelem_hint: Hint on number of elements, should be 75% of desired size
+ * @key_len: Length of key
+ * @key_offset: Offset of key in struct to be hashed
+ * @head_offset: Offset of rhash_head in struct to be hashed
+ * @hash_rnd: Seed to use while hashing
+ * @max_shift: Maximum number of shifts while expanding
+ * @hashfn: Function to hash key
+ * @obj_hashfn: Function to hash object
+ * @grow_decision: If defined, may return true if table should expand
+ * @shrink_decision: If defined, may return true if table should shrink
+ * @mutex_is_held: Must return true if protecting mutex is held
+ */
+struct rhashtable_params {
+ size_t nelem_hint;
+ size_t key_len;
+ size_t key_offset;
+ size_t head_offset;
+ u32 hash_rnd;
+ size_t max_shift;
+ rht_hashfn_thashfn;
+ rht_obj_hashfn_tobj_hashfn;
+ bool(*grow_decision)(const struct rhashtable *ht,
+size_t new_size);
+ bool(*shrink_decision)(const struct rhashtable *ht,
+ size_t new_size);
+ int (*mutex_is_held)(void);
+};
+
+/**
+ * struct rhashtable - Hash table handle
+ * @tbl: Bucket table
+ * @nelems: Number of elements in table
+ * @shift: Current size (1 shift)
+ * @p: Configuration parameters
+ */
+struct rhashtable {
+ struct bucket_table __rcu *tbl;
+ size_t nelems;
+ size_t shift;
+ struct rhashtable_paramsp;
+};
+
+#ifdef CONFIG_PROVE_LOCKING
+int lockdep_rht_mutex_is_held(const struct rhashtable *ht);
+#else
+static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
+{
+ return 1;
+}
+#endif /* CONFIG_PROVE_LOCKING */
+
+int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);
+
+u32 rhashtable_hashfn(const struct rhashtable *ht, const void *key, u32 len);
+u32 rhashtable_obj_hashfn(const struct rhashtable *ht, void *ptr);
+
+void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
+struct
[PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
Generic implementation of a resizable, scalable, concurrent hash table
based on [0]. The implementation supports both, fixed size keys specified
via an offset and length, or arbitrary keys via own hash and compare
functions.
Lookups are lockless and protected as RCU read side critical sections.
Automatic growing/shrinking based on user configurable watermarks is
available while allowing concurrent lookups to take place.
Objects to be hashed must include a struct rhash_head. The reason for not
using the existing struct hlist_head is that the expansion and shrinking
will have two buckets point to a single entry which would lead in obscure
reverse chaining behaviour.
Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined.
[0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
Signed-off-by: Thomas Graf
---
include/linux/rhashtable.h | 213
lib/Kconfig.debug | 8 +
lib/Makefile | 2 +-
lib/rhashtable.c | 797 +
4 files changed, 1019 insertions(+), 1 deletion(-)
create mode 100644 include/linux/rhashtable.h
create mode 100644 lib/rhashtable.c
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
new file mode 100644
index 000..0a8f6cc
--- /dev/null
+++ b/include/linux/rhashtable.h
@@ -0,0 +1,213 @@
+/*
+ * Resizable, Scalable, Concurrent Hash Table
+ *
+ * Copyright (c) 2014 Thomas Graf
+ *
+ * Based on the following paper by Josh Triplett, Paul E. McKenney
+ * and Jonathan Walpole:
+ * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
+ *
+ * Code partially derived from nft_hash:
+ * Copyright (c) 2008-2014 Patrick McHardy
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#ifndef _LINUX_RHASHTABLE_H
+#define _LINUX_RHASHTABLE_H
+
+#include
+
+struct rhash_head {
+ struct rhash_head *next;
+};
+
+#define INIT_HASH_HEAD(ptr) ((ptr)->next = NULL)
+
+struct bucket_table {
+ size_t size;
+ struct rhash_head __rcu *buckets[];
+};
+
+typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
+typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 seed);
+
+struct rhashtable;
+
+/**
+ * struct rhashtable_params - Hash table construction parameters
+ * @nelem_hint: Hint on number of elements expected
+ * @key_len: Length of key
+ * @key_offset: Offset of key in struct to be hashed
+ * @head_offset: Offset of rhash_head in struct to be hashed
+ * @hash_rnd: Seed to use while hashing
+ * @max_shift: Maximum number of shifts while expanding
+ * @hashfn: Function to hash key
+ * @obj_hashfn: Function to hash object
+ * @grow_decision: If defined, may return true if table should expand
+ * @shrink_decision: If defined, may return true if table should shrink
+ * @mutex_is_held: Must return true if protecting mutex is held
+ */
+struct rhashtable_params {
+ size_t nelem_hint;
+ size_t key_len;
+ size_t key_offset;
+ size_t head_offset;
+ u32 hash_rnd;
+ size_t max_shift;
+ rht_hashfn_thashfn;
+ rht_obj_hashfn_tobj_hashfn;
+ bool(*grow_decision)(const struct rhashtable *ht,
+size_t new_size);
+ bool(*shrink_decision)(const struct rhashtable *ht,
+ size_t new_size);
+ int (*mutex_is_held)(void);
+};
+
+/**
+ * struct rhashtable - Hash table handle
+ * @tbl: Bucket table
+ * @nelems: Number of elements in table
+ * @shift: Current size (1 << shift)
+ * @p: Configuration parameters
+ */
+struct rhashtable {
+ struct bucket_table __rcu *tbl;
+ size_t nelems;
+ size_t shift;
+ struct rhashtable_paramsp;
+};
+
+#ifdef CONFIG_PROVE_LOCKING
+int lockdep_rht_mutex_is_held(const struct rhashtable *ht);
+#else
+static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
+{
+ return 1;
+}
+#endif /* CONFIG_PROVE_LOCKING */
+
+int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);
+
+u32 rhashtable_hashfn(const struct rhashtable *ht, const void *key, u32 len);
+u32 rhashtable_obj_hashfn(const struct rhashtable *ht, void *ptr);
+
+void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
+struct rhash_head **pprev, gfp_t flags);
+
+bool rht_grow_above_75(const struct
[PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
Generic implementation of a resizable, scalable, concurrent hash table
based on [0]. The implementation supports both, fixed size keys specified
via an offset and length, or arbitrary keys via own hash and compare
functions.
Lookups are lockless and protected as RCU read side critical sections.
Automatic growing/shrinking based on user configurable watermarks is
available while allowing concurrent lookups to take place.
Objects to be hashed must include a struct rhash_head. The reason for not
using the existing struct hlist_head is that the expansion and shrinking
will have two buckets point to a single entry which would lead in obscure
reverse chaining behaviour.
Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined.
[0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
Signed-off-by: Thomas Graf tg...@suug.ch
---
include/linux/rhashtable.h | 213
lib/Kconfig.debug | 8 +
lib/Makefile | 2 +-
lib/rhashtable.c | 797 +
4 files changed, 1019 insertions(+), 1 deletion(-)
create mode 100644 include/linux/rhashtable.h
create mode 100644 lib/rhashtable.c
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
new file mode 100644
index 000..0a8f6cc
--- /dev/null
+++ b/include/linux/rhashtable.h
@@ -0,0 +1,213 @@
+/*
+ * Resizable, Scalable, Concurrent Hash Table
+ *
+ * Copyright (c) 2014 Thomas Graf tg...@suug.ch
+ *
+ * Based on the following paper by Josh Triplett, Paul E. McKenney
+ * and Jonathan Walpole:
+ * https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
+ *
+ * Code partially derived from nft_hash:
+ * Copyright (c) 2008-2014 Patrick McHardy ka...@trash.net
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#ifndef _LINUX_RHASHTABLE_H
+#define _LINUX_RHASHTABLE_H
+
+#include linux/rculist.h
+
+struct rhash_head {
+ struct rhash_head *next;
+};
+
+#define INIT_HASH_HEAD(ptr) ((ptr)-next = NULL)
+
+struct bucket_table {
+ size_t size;
+ struct rhash_head __rcu *buckets[];
+};
+
+typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
+typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 seed);
+
+struct rhashtable;
+
+/**
+ * struct rhashtable_params - Hash table construction parameters
+ * @nelem_hint: Hint on number of elements expected
+ * @key_len: Length of key
+ * @key_offset: Offset of key in struct to be hashed
+ * @head_offset: Offset of rhash_head in struct to be hashed
+ * @hash_rnd: Seed to use while hashing
+ * @max_shift: Maximum number of shifts while expanding
+ * @hashfn: Function to hash key
+ * @obj_hashfn: Function to hash object
+ * @grow_decision: If defined, may return true if table should expand
+ * @shrink_decision: If defined, may return true if table should shrink
+ * @mutex_is_held: Must return true if protecting mutex is held
+ */
+struct rhashtable_params {
+ size_t nelem_hint;
+ size_t key_len;
+ size_t key_offset;
+ size_t head_offset;
+ u32 hash_rnd;
+ size_t max_shift;
+ rht_hashfn_thashfn;
+ rht_obj_hashfn_tobj_hashfn;
+ bool(*grow_decision)(const struct rhashtable *ht,
+size_t new_size);
+ bool(*shrink_decision)(const struct rhashtable *ht,
+ size_t new_size);
+ int (*mutex_is_held)(void);
+};
+
+/**
+ * struct rhashtable - Hash table handle
+ * @tbl: Bucket table
+ * @nelems: Number of elements in table
+ * @shift: Current size (1 shift)
+ * @p: Configuration parameters
+ */
+struct rhashtable {
+ struct bucket_table __rcu *tbl;
+ size_t nelems;
+ size_t shift;
+ struct rhashtable_paramsp;
+};
+
+#ifdef CONFIG_PROVE_LOCKING
+int lockdep_rht_mutex_is_held(const struct rhashtable *ht);
+#else
+static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
+{
+ return 1;
+}
+#endif /* CONFIG_PROVE_LOCKING */
+
+int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);
+
+u32 rhashtable_hashfn(const struct rhashtable *ht, const void *key, u32 len);
+u32 rhashtable_obj_hashfn(const struct rhashtable *ht, void *ptr);
+
+void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node, gfp_t);
+void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
+struct rhash_head **pprev, gfp_t
