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/
