| Message ID | E1YZarZ-0000v8-7e@gondolin.me.apana.org.au |
|---|---|
| State | Changes Requested, archived |
| Delegated to: | David Miller |
| Headers | show |
On 03/22/15 at 07:04pm, Herbert Xu wrote: > @@ -134,6 +136,7 @@ struct rhashtable { > struct bucket_table __rcu *tbl; > atomic_t nelems; > bool being_destroyed; > + unsigned int key_len; Why is this needed? It looks like you're always initializing this with ht->p.key_len > struct rhashtable_params p; > struct work_struct run_work; > struct mutex mutex; > @@ -199,12 +202,30 @@ static inline unsigned int rht_key_hashfn( > struct rhashtable *ht, const struct bucket_table *tbl, > const void *key, const struct rhashtable_params params) > { > - unsigned key_len = __builtin_constant_p(params.key_len) ? > - (params.key_len ?: ht->p.key_len) : > - params.key_len; > + unsigned hash; unsigned int In several places as well > + if (!__builtin_constant_p(params.key_len)) > + hash = ht->p.hashfn(key, ht->key_len, tbl->hash_rnd); I don't understand this. It looks like you only consider params->key_len if it's constant. > + else if (params.key_len) { > + unsigned key_len = params.key_len; > + > + if (params.hashfn) > + hash = params.hashfn(key, key_len, tbl->hash_rnd); > + else if (key_len & (sizeof(u32) - 1)) > + hash = jhash(key, key_len, tbl->hash_rnd); > + else > + hash = jhash2(key, key_len / sizeof(u32), > + tbl->hash_rnd); > + } else { > + unsigned key_len = ht->p.key_len; > + > + if (params.hashfn) > + hash = params.hashfn(key, key_len, tbl->hash_rnd); > + else > + hash = jhash(key, key_len, tbl->hash_rnd); Why don't we opt-in to jhash2 in this case? -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Sun, Mar 22, 2015 at 11:55:05AM +0000, Thomas Graf wrote: > On 03/22/15 at 07:04pm, Herbert Xu wrote: > > @@ -134,6 +136,7 @@ struct rhashtable { > > struct bucket_table __rcu *tbl; > > atomic_t nelems; > > bool being_destroyed; > > + unsigned int key_len; > > Why is this needed? It looks like you're always initializing this > with ht->p.key_len It's ht->p.key_len/4 if we use jhash2. > > + if (!__builtin_constant_p(params.key_len)) > > + hash = ht->p.hashfn(key, ht->key_len, tbl->hash_rnd); > > I don't understand this. It looks like you only consider > params->key_len if it's constant. If params->key_len is not constant, then params == ht->p. > > + else if (params.key_len) { > > + unsigned key_len = params.key_len; > > + > > + if (params.hashfn) > > + hash = params.hashfn(key, key_len, tbl->hash_rnd); > > + else if (key_len & (sizeof(u32) - 1)) > > + hash = jhash(key, key_len, tbl->hash_rnd); > > + else > > + hash = jhash2(key, key_len / sizeof(u32), > > + tbl->hash_rnd); > > + } else { > > + unsigned key_len = ht->p.key_len; > > + > > + if (params.hashfn) > > + hash = params.hashfn(key, key_len, tbl->hash_rnd); > > + else > > + hash = jhash(key, key_len, tbl->hash_rnd); > > Why don't we opt-in to jhash2 in this case? Because if key_len == 0 it means that key_len is not known at compile-time. Cheers,
On 03/22/15 at 11:04pm, Herbert Xu wrote: > On Sun, Mar 22, 2015 at 11:55:05AM +0000, Thomas Graf wrote: > > On 03/22/15 at 07:04pm, Herbert Xu wrote: > > > @@ -134,6 +136,7 @@ struct rhashtable { > > > struct bucket_table __rcu *tbl; > > > atomic_t nelems; > > > bool being_destroyed; > > > + unsigned int key_len; > > > > Why is this needed? It looks like you're always initializing this > > with ht->p.key_len > > It's ht->p.key_len/4 if we use jhash2. Sure but why not just store key_len/4 in ht->p.key_len then if you opt in to jhash2() in rhashtable_init()? > > > + if (!__builtin_constant_p(params.key_len)) > > > + hash = ht->p.hashfn(key, ht->key_len, tbl->hash_rnd); > > > > I don't understand this. It looks like you only consider > > params->key_len if it's constant. > > If params->key_len is not constant, then params == ht->p. I must be missing something obvious. Who guarantees that? I can see that's true for the current callers but what prevents anybody from using rhashtable_lookup_fast() with a key length not known at compile time and pass it as rhashtable_params? > > > + else if (params.key_len) { > > > + unsigned key_len = params.key_len; > > > + > > > + if (params.hashfn) > > > + hash = params.hashfn(key, key_len, tbl->hash_rnd); > > > + else if (key_len & (sizeof(u32) - 1)) > > > + hash = jhash(key, key_len, tbl->hash_rnd); > > > + else > > > + hash = jhash2(key, key_len / sizeof(u32), > > > + tbl->hash_rnd); > > > + } else { > > > + unsigned key_len = ht->p.key_len; > > > + > > > + if (params.hashfn) > > > + hash = params.hashfn(key, key_len, tbl->hash_rnd); > > > + else > > > + hash = jhash(key, key_len, tbl->hash_rnd); > > > > Why don't we opt-in to jhash2 in this case? > > Because if key_len == 0 it means that key_len is not known at > compile-time. I still don't get this. Why do we fall back to jhash2() if params.key_len is set but not if only ht->p.key_len is set? -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Sun, Mar 22, 2015 at 12:32:57PM +0000, Thomas Graf wrote: > On 03/22/15 at 11:04pm, Herbert Xu wrote: > > On Sun, Mar 22, 2015 at 11:55:05AM +0000, Thomas Graf wrote: > > > On 03/22/15 at 07:04pm, Herbert Xu wrote: > > > > @@ -134,6 +136,7 @@ struct rhashtable { > > > > struct bucket_table __rcu *tbl; > > > > atomic_t nelems; > > > > bool being_destroyed; > > > > + unsigned int key_len; > > > > > > Why is this needed? It looks like you're always initializing this > > > with ht->p.key_len > > > > It's ht->p.key_len/4 if we use jhash2. > > Sure but why not just store key_len/4 in ht->p.key_len then if you > opt in to jhash2() in rhashtable_init()? Because that breaks rhashtable_compare/memcmp. > > > > > + if (!__builtin_constant_p(params.key_len)) > > > > + hash = ht->p.hashfn(key, ht->key_len, tbl->hash_rnd); > > > > > > I don't understand this. It looks like you only consider > > > params->key_len if it's constant. > > > > If params->key_len is not constant, then params == ht->p. > > I must be missing something obvious. Who guarantees that? I can see > that's true for the current callers but what prevents anybody from > using rhashtable_lookup_fast() with a key length not known at compile > time and pass it as rhashtable_params? They shouldn't be doing that. The whole point of this function is to have it inlined so all external callers of it should be supplying a constant parameter. We could add a __ variant that is only called by rhashtable if you like so we can enforce this in rhashtable_lookup_fast. > I still don't get this. Why do we fall back to jhash2() if > params.key_len is set but not if only ht->p.key_len is set? Because if params.key_len is not set then we have no idea whether we should use jhash or jhash2 because ht->p.key_len cannot be known at compile time. This is only used by netfilter currently as it has a key-length set at run-time. Cheers,
On 03/23/15 at 08:12am, Herbert Xu wrote: > On Sun, Mar 22, 2015 at 12:32:57PM +0000, Thomas Graf wrote: > > Sure but why not just store key_len/4 in ht->p.key_len then if you > > opt in to jhash2() in rhashtable_init()? > > Because that breaks rhashtable_compare/memcmp. Thanks. Didn't see that. > > > > > + if (!__builtin_constant_p(params.key_len)) > > > > > + hash = ht->p.hashfn(key, ht->key_len, tbl->hash_rnd); > > > > > > > > I don't understand this. It looks like you only consider > > > > params->key_len if it's constant. > > > > > > If params->key_len is not constant, then params == ht->p. > > > > I must be missing something obvious. Who guarantees that? I can see > > that's true for the current callers but what prevents anybody from > > using rhashtable_lookup_fast() with a key length not known at compile > > time and pass it as rhashtable_params? > > They shouldn't be doing that. The whole point of this function > is to have it inlined so all external callers of it should be > supplying a constant parameter. We could add a __ variant that > is only called by rhashtable if you like so we can enforce this > in rhashtable_lookup_fast. If you add such constraints it must be clearly documented. There is no way of figuring this out right now without reading the entire rhashtable code (and talking to you). > > I still don't get this. Why do we fall back to jhash2() if > > params.key_len is set but not if only ht->p.key_len is set? > > Because if params.key_len is not set then we have no idea whether > we should use jhash or jhash2 because ht->p.key_len cannot be > known at compile time. This is only used by netfilter currently > as it has a key-length set at run-time. Sorry, still not getting this ;-) nft_hash sets key_len to set->klen and passes it to rhashtable_init(). rhashtable_init() should then fall back to jhash() or jhash2() if no hashfn is provided. Why is the logic in rht_key_hashfn() different? Actually, in which case is ht->p.hashfn not set in rht_key_hashfn()? -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Mar 23, 2015 at 09:58:42AM +0000, Thomas Graf wrote: > > nft_hash sets key_len to set->klen and passes it to rhashtable_init(). > rhashtable_init() should then fall back to jhash() or jhash2() if no > hashfn is provided. Why is the logic in rht_key_hashfn() different? > Actually, in which case is ht->p.hashfn not set in rht_key_hashfn()? jhash can be used in place of jhash2, the only difference is that jhash is less optimised and uses unaligned loads. Cheers,
From: Herbert Xu > Since every current rhashtable user uses jhash as their hash > function, the fact that jhash is an inline function causes each > user to generate a copy of its code. > > This function provides a solution to this problem by allowing > hashfn to be unset. In which case rhashtable will automatically > set it to jhash. Furthermore, if the key length is a multiple > of 4, we will switch over to jhash2. Would it make sense to do this as a run-time check for the NULL function pointer so that the jhash code itself can be inlined? The cost of the test is likely to be less that the indirect call. David -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h index 287b609..2a98b95 100644 --- a/include/linux/rhashtable.h +++ b/include/linux/rhashtable.h @@ -19,6 +19,7 @@ #include <linux/compiler.h> #include <linux/errno.h> +#include <linux/jhash.h> #include <linux/list_nulls.h> #include <linux/workqueue.h> #include <linux/mutex.h> @@ -103,7 +104,7 @@ struct rhashtable; * @min_size: Minimum size while shrinking * @nulls_base: Base value to generate nulls marker * @locks_mul: Number of bucket locks to allocate per cpu (default: 128) - * @hashfn: Function to hash key + * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash) * @obj_hashfn: Function to hash object * @obj_cmpfn: Function to compare key with object */ @@ -125,6 +126,7 @@ struct rhashtable_params { * struct rhashtable - Hash table handle * @tbl: Bucket table * @nelems: Number of elements in table + * @key_len: Key length for hashfn * @p: Configuration parameters * @run_work: Deferred worker to expand/shrink asynchronously * @mutex: Mutex to protect current/future table swapping @@ -134,6 +136,7 @@ struct rhashtable { struct bucket_table __rcu *tbl; atomic_t nelems; bool being_destroyed; + unsigned int key_len; struct rhashtable_params p; struct work_struct run_work; struct mutex mutex; @@ -199,12 +202,30 @@ static inline unsigned int rht_key_hashfn( struct rhashtable *ht, const struct bucket_table *tbl, const void *key, const struct rhashtable_params params) { - unsigned key_len = __builtin_constant_p(params.key_len) ? - (params.key_len ?: ht->p.key_len) : - params.key_len; + unsigned hash; + + if (!__builtin_constant_p(params.key_len)) + hash = ht->p.hashfn(key, ht->key_len, tbl->hash_rnd); + else if (params.key_len) { + unsigned key_len = params.key_len; + + if (params.hashfn) + hash = params.hashfn(key, key_len, tbl->hash_rnd); + else if (key_len & (sizeof(u32) - 1)) + hash = jhash(key, key_len, tbl->hash_rnd); + else + hash = jhash2(key, key_len / sizeof(u32), + tbl->hash_rnd); + } else { + unsigned key_len = ht->p.key_len; + + if (params.hashfn) + hash = params.hashfn(key, key_len, tbl->hash_rnd); + else + hash = jhash(key, key_len, tbl->hash_rnd); + } - return rht_bucket_index(tbl, params.hashfn(key, key_len, - tbl->hash_rnd)); + return rht_bucket_index(tbl, hash); } static inline unsigned int rht_head_hashfn( diff --git a/lib/rhashtable.c b/lib/rhashtable.c index 618a3f0..798f01d 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -532,6 +532,11 @@ static size_t rounded_hashtable_size(const struct rhashtable_params *params) (unsigned long)params->min_size); } +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 @@ -583,7 +588,7 @@ int rhashtable_init(struct rhashtable *ht, size = HASH_DEFAULT_SIZE; - if ((!(params->key_len && params->hashfn) && !params->obj_hashfn) || + if ((!params->key_len && !params->obj_hashfn) || (params->obj_hashfn && !params->obj_cmpfn)) return -EINVAL; @@ -610,6 +615,16 @@ int rhashtable_init(struct rhashtable *ht, else ht->p.locks_mul = BUCKET_LOCKS_PER_CPU; + ht->key_len = ht->p.key_len; + if (!params->hashfn) { + ht->p.hashfn = jhash; + + if (!(ht->key_len & (sizeof(u32) - 1))) { + ht->key_len /= sizeof(u32); + ht->p.hashfn = rhashtable_jhash2; + } + } + tbl = bucket_table_alloc(ht, size); if (tbl == NULL) return -ENOMEM;
Since every current rhashtable user uses jhash as their hash function, the fact that jhash is an inline function causes each user to generate a copy of its code. This function provides a solution to this problem by allowing hashfn to be unset. In which case rhashtable will automatically set it to jhash. Furthermore, if the key length is a multiple of 4, we will switch over to jhash2. Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au> --- include/linux/rhashtable.h | 33 +++++++++++++++++++++++++++------ lib/rhashtable.c | 17 ++++++++++++++++- 2 files changed, 43 insertions(+), 7 deletions(-) -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html