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 <tgraf@xxxxxxx> > --- > 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 netfilter-devel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
