aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJonathan Neuschäfer <j.neuschaefer@gmx.net>2018-07-27 04:02:30 +0200
committerJonathan Neuschäfer <j.neuschaefer@gmx.net>2018-07-27 04:02:30 +0200
commitfa0cceb888e0c712b2c509e1994a9507554df7b1 (patch)
tree285f77ac461f6f946a4cf6de8eaf2ad4da6e3790
parentLinux 4.18-rc6 (diff)
downloadlinux-dev-jn/rhashtable.tar.xz
linux-dev-jn/rhashtable.zip
[WIP] rhashtable: add SipHash supportjn/rhashtable
The trick here is that rhashtable_init_siphash assigns rhashtable_siphash as the hash function, but in rht_key_get_hash it calls siphash directly, in order to pass more random bits. TODO: More text.
-rw-r--r--include/linux/rhashtable.h35
-rw-r--r--lib/rhashtable.c122
2 files changed, 101 insertions, 56 deletions
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 4e1f535c2034..037b8936c6e2 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -22,6 +22,7 @@
#include <linux/err.h>
#include <linux/errno.h>
#include <linux/jhash.h>
+#include <linux/siphash.h>
#include <linux/list_nulls.h>
#include <linux/workqueue.h>
#include <linux/mutex.h>
@@ -91,7 +92,7 @@ struct bucket_table {
unsigned int size;
unsigned int nest;
unsigned int rehash;
- u32 hash_rnd;
+ u32 hash_rnd[4];
unsigned int locks_mask;
spinlock_t *locks;
struct list_head walkers;
@@ -117,6 +118,8 @@ typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
const void *obj);
+u32 rhashtable_siphash(const void *key, u32 length, u32 seed);
+
struct rhashtable;
/**
@@ -242,29 +245,40 @@ static inline unsigned int rht_bucket_index(const struct bucket_table *tbl,
static inline unsigned int rht_key_get_hash(struct rhashtable *ht,
const void *key, const struct rhashtable_params params,
- unsigned int hash_rnd)
+ const u32 hash_rnd[4])
{
unsigned int hash;
/* params must be equal to ht->p if it isn't constant. */
if (!__builtin_constant_p(params.key_len))
- hash = ht->p.hashfn(key, ht->key_len, hash_rnd);
+ if (ht->p.hashfn == rhashtable_siphash) {
+ /*
+ * If siphash is used, call the siphash function
+ * directly, in order to pass a longer than 32 bits
+ * random seed.
+ */
+ BUILD_BUG_ON(sizeof(u32[4]) != sizeof(siphash_key_t));
+ hash = siphash(key, ht->key_len,
+ (const siphash_key_t *)hash_rnd);
+ } else {
+ hash = ht->p.hashfn(key, ht->key_len, hash_rnd[0]);
+ }
else if (params.key_len) {
unsigned int key_len = params.key_len;
if (params.hashfn)
- hash = params.hashfn(key, key_len, hash_rnd);
+ hash = params.hashfn(key, key_len, hash_rnd[0]);
else if (key_len & (sizeof(u32) - 1))
- hash = jhash(key, key_len, hash_rnd);
+ hash = jhash(key, key_len, hash_rnd[0]);
else
- hash = jhash2(key, key_len / sizeof(u32), hash_rnd);
+ hash = jhash2(key, key_len / sizeof(u32), hash_rnd[0]);
} else {
unsigned int key_len = ht->p.key_len;
if (params.hashfn)
- hash = params.hashfn(key, key_len, hash_rnd);
+ hash = params.hashfn(key, key_len, hash_rnd[0]);
else
- hash = jhash(key, key_len, hash_rnd);
+ hash = jhash(key, key_len, hash_rnd[0]);
}
return hash;
@@ -288,7 +302,7 @@ static inline unsigned int rht_head_hashfn(
return likely(params.obj_hashfn) ?
rht_bucket_index(tbl, params.obj_hashfn(ptr, params.key_len ?:
ht->p.key_len,
- tbl->hash_rnd)) :
+ tbl->hash_rnd[0])) :
rht_key_hashfn(ht, tbl, ptr + params.key_offset, params);
}
@@ -378,6 +392,8 @@ static inline int lockdep_rht_bucket_is_held(const struct bucket_table *tbl,
int rhashtable_init(struct rhashtable *ht,
const struct rhashtable_params *params);
+int rhashtable_init_siphash(struct rhashtable *ht,
+ const struct rhashtable_params *params);
int rhltable_init(struct rhltable *hlt,
const struct rhashtable_params *params);
@@ -397,6 +413,7 @@ static inline void rhashtable_walk_start(struct rhashtable_iter *iter)
void *rhashtable_walk_next(struct rhashtable_iter *iter);
void *rhashtable_walk_peek(struct rhashtable_iter *iter);
void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases(RCU);
+u32 rhashtable_siphash(const void *key, u32 length, u32 seed);
void rhashtable_free_and_destroy(struct rhashtable *ht,
void (*free_fn)(void *ptr, void *arg),
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index e5c8586cf717..b4c59d92553a 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -24,6 +24,7 @@
#include <linux/vmalloc.h>
#include <linux/mm.h>
#include <linux/jhash.h>
+#include <linux/siphash.h>
#include <linux/random.h>
#include <linux/rhashtable.h>
#include <linux/err.h>
@@ -203,7 +204,7 @@ static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
INIT_LIST_HEAD(&tbl->walkers);
- tbl->hash_rnd = get_random_u32();
+ get_random_bytes(tbl->hash_rnd, sizeof(tbl->hash_rnd));
for (i = 0; i < nbuckets; i++)
INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);
@@ -981,51 +982,21 @@ static u32 rhashtable_jhash2(const void *key, u32 length, u32 seed)
return jhash2(key, length, seed);
}
-/**
- * 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 = jhash,
- * .nulls_base = (1U << RHT_BASE_SHIFT),
- * };
- *
- * Configuration Example 2: Variable length keys
- * struct test_obj {
- * [...]
- * struct rhash_head node;
- * };
- *
- * u32 my_hash_fn(const void *data, u32 len, u32 seed)
- * {
- * struct test_obj *obj = data;
- *
- * return [... hash ...];
- * }
- *
- * struct rhashtable_params params = {
- * .head_offset = offsetof(struct test_obj, node),
- * .hashfn = jhash,
- * .obj_hashfn = my_hash_fn,
- * };
- */
-int rhashtable_init(struct rhashtable *ht,
- const struct rhashtable_params *params)
+u32 rhashtable_siphash(const void *key, u32 length, u32 seed)
+{
+ siphash_key_t siphash_key = {
+ .key = { seed, 0 }
+ };
+
+ WARN_ONCE("%s should not be called directly", __func__);
+
+ return siphash(key, length, &siphash_key);
+}
+EXPORT_SYMBOL_GPL(rhashtable_siphash);
+
+static int __rhashtable_init(struct rhashtable *ht,
+ const struct rhashtable_params *params,
+ rht_hashfn_t hashfn)
{
struct bucket_table *tbl;
size_t size;
@@ -1041,6 +1012,7 @@ int rhashtable_init(struct rhashtable *ht,
mutex_init(&ht->mutex);
spin_lock_init(&ht->lock);
memcpy(&ht->p, params, sizeof(*params));
+ ht->p.hashfn = hashfn;
if (params->min_size)
ht->p.min_size = roundup_pow_of_two(params->min_size);
@@ -1064,7 +1036,7 @@ int rhashtable_init(struct rhashtable *ht,
ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;
ht->key_len = ht->p.key_len;
- if (!params->hashfn) {
+ if (!hashfn) {
ht->p.hashfn = jhash;
if (!(ht->key_len & (sizeof(u32) - 1))) {
@@ -1085,8 +1057,64 @@ int rhashtable_init(struct rhashtable *ht,
return 0;
}
+
+/**
+ * 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 = jhash,
+ * .nulls_base = (1U << RHT_BASE_SHIFT),
+ * };
+ *
+ * Configuration Example 2: Variable length keys
+ * struct test_obj {
+ * [...]
+ * struct rhash_head node;
+ * };
+ *
+ * u32 my_hash_fn(const void *data, u32 len, u32 seed)
+ * {
+ * struct test_obj *obj = data;
+ *
+ * return [... hash ...];
+ * }
+ *
+ * struct rhashtable_params params = {
+ * .head_offset = offsetof(struct test_obj, node),
+ * .hashfn = jhash,
+ * .obj_hashfn = my_hash_fn,
+ * };
+ */
+int rhashtable_init(struct rhashtable *ht,
+ const struct rhashtable_params *params)
+{
+ return __rhashtable_init(ht, params, params->hashfn);
+}
EXPORT_SYMBOL_GPL(rhashtable_init);
+int rhashtable_init_siphash(struct rhashtable *ht,
+ const struct rhashtable_params *params)
+{
+ return __rhashtable_init(ht, params, rhashtable_siphash);
+}
+EXPORT_SYMBOL_GPL(rhashtable_init_siphash);
+
/**
* rhltable_init - initialize a new hash list table
* @hlt: hash list table to be initialized