From 5f8ddeab10ce45d3d3de8ae7ea8811512845c497 Mon Sep 17 00:00:00 2001 From: Florian Westphal Date: Sun, 16 Apr 2017 02:55:09 +0200 Subject: rhashtable: remove insecure_elasticity commit 83e7e4ce9e93c3 ("mac80211: Use rhltable instead of rhashtable") removed the last user that made use of 'insecure_elasticity' parameter, i.e. the default of 16 is used everywhere. Replace it with a constant. Signed-off-by: Florian Westphal Signed-off-by: David S. Miller --- lib/rhashtable.c | 17 +---------------- 1 file changed, 1 insertion(+), 16 deletions(-) (limited to 'lib/rhashtable.c') diff --git a/lib/rhashtable.c b/lib/rhashtable.c index f8635fd57442..d22a5ef109fb 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -535,7 +535,7 @@ static void *rhashtable_lookup_one(struct rhashtable *ht, struct rhash_head *head; int elasticity; - elasticity = ht->elasticity; + elasticity = RHT_ELASTICITY; pprev = rht_bucket_var(tbl, hash); rht_for_each_continue(head, *pprev, tbl, hash) { struct rhlist_head *list; @@ -972,21 +972,6 @@ int rhashtable_init(struct rhashtable *ht, if (params->nelem_hint) size = rounded_hashtable_size(&ht->p); - /* The maximum (not average) chain length grows with the - * size of the hash table, at a rate of (log N)/(log log N). - * The value of 16 is selected so that even if the hash - * table grew to 2^32 you would not expect the maximum - * chain length to exceed it unless we are under attack - * (or extremely unlucky). - * - * As this limit is only to detect attacks, we don't need - * to set it to a lower value as you'd need the chain - * length to vastly exceed 16 to have any real effect - * on the system. - */ - if (!params->insecure_elasticity) - ht->elasticity = 16; - if (params->locks_mul) ht->p.locks_mul = roundup_pow_of_two(params->locks_mul); else -- cgit v1.2.3 From 038a3e858de4e3ddf42c330a22b7efcddbc0a81a Mon Sep 17 00:00:00 2001 From: Florian Westphal Date: Tue, 25 Apr 2017 11:41:34 +0200 Subject: rhashtable: remove insecure_max_entries param no users in the tree, insecure_max_entries is always set to ht->p.max_size * 2 in rhtashtable_init(). Replace only spot that uses it with a ht->p.max_size check. Signed-off-by: Florian Westphal Signed-off-by: David S. Miller --- include/linux/rhashtable.h | 6 ++---- lib/rhashtable.c | 6 ------ 2 files changed, 2 insertions(+), 10 deletions(-) (limited to 'lib/rhashtable.c') diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h index ae87dcdf52d2..ae93b65d13d7 100644 --- a/include/linux/rhashtable.h +++ b/include/linux/rhashtable.h @@ -125,7 +125,6 @@ struct rhashtable; * @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 - * @insecure_max_entries: Maximum number of entries (may be exceeded) * @max_size: Maximum size while expanding * @min_size: Minimum size while shrinking * @nulls_base: Base value to generate nulls marker @@ -140,7 +139,6 @@ struct rhashtable_params { size_t key_len; size_t key_offset; size_t head_offset; - unsigned int insecure_max_entries; unsigned int max_size; unsigned int min_size; u32 nulls_base; @@ -329,8 +327,8 @@ static inline bool rht_grow_above_100(const struct rhashtable *ht, static inline bool rht_grow_above_max(const struct rhashtable *ht, const struct bucket_table *tbl) { - return ht->p.insecure_max_entries && - atomic_read(&ht->nelems) >= ht->p.insecure_max_entries; + return ht->p.max_size && + (atomic_read(&ht->nelems) / 2u) >= ht->p.max_size; } /* The bucket lock is selected based on the hash and protects mutations diff --git a/lib/rhashtable.c b/lib/rhashtable.c index d22a5ef109fb..f3b82e0d417b 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -961,12 +961,6 @@ int rhashtable_init(struct rhashtable *ht, if (params->max_size) ht->p.max_size = rounddown_pow_of_two(params->max_size); - if (params->insecure_max_entries) - ht->p.insecure_max_entries = - rounddown_pow_of_two(params->insecure_max_entries); - else - ht->p.insecure_max_entries = ht->p.max_size * 2; - ht->p.min_size = max(ht->p.min_size, HASH_MIN_SIZE); if (params->nelem_hint) -- cgit v1.2.3 From 6d684e54690caef45cf14051ddeb7c71beeb681b Mon Sep 17 00:00:00 2001 From: Herbert Xu Date: Thu, 27 Apr 2017 13:44:51 +0800 Subject: rhashtable: Cap total number of entries to 2^31 When max_size is not set or if it set to a sufficiently large value, the nelems counter can overflow. This would cause havoc with the automatic shrinking as it would then attempt to fit a huge number of entries into a tiny hash table. This patch fixes this by adding max_elems to struct rhashtable to cap the number of elements. This is set to 2^31 as nelems is not a precise count. This is sufficiently smaller than UINT_MAX that it should be safe. When max_size is set max_elems will be lowered to at most twice max_size as is the status quo. Signed-off-by: Herbert Xu Signed-off-by: David S. Miller --- include/linux/rhashtable.h | 5 +++-- lib/rhashtable.c | 5 +++++ 2 files changed, 8 insertions(+), 2 deletions(-) (limited to 'lib/rhashtable.c') diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h index ae93b65d13d7..45f89369c4c8 100644 --- a/include/linux/rhashtable.h +++ b/include/linux/rhashtable.h @@ -155,6 +155,7 @@ struct rhashtable_params { * @nelems: Number of elements in table * @key_len: Key length for hashfn * @p: Configuration parameters + * @max_elems: Maximum number of elements in table * @rhlist: True if this is an rhltable * @run_work: Deferred worker to expand/shrink asynchronously * @mutex: Mutex to protect current/future table swapping @@ -165,6 +166,7 @@ struct rhashtable { atomic_t nelems; unsigned int key_len; struct rhashtable_params p; + unsigned int max_elems; bool rhlist; struct work_struct run_work; struct mutex mutex; @@ -327,8 +329,7 @@ static inline bool rht_grow_above_100(const struct rhashtable *ht, static inline bool rht_grow_above_max(const struct rhashtable *ht, const struct bucket_table *tbl) { - return ht->p.max_size && - (atomic_read(&ht->nelems) / 2u) >= ht->p.max_size; + return atomic_read(&ht->nelems) >= ht->max_elems; } /* The bucket lock is selected based on the hash and protects mutations diff --git a/lib/rhashtable.c b/lib/rhashtable.c index f3b82e0d417b..751630bbe409 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -961,6 +961,11 @@ int rhashtable_init(struct rhashtable *ht, if (params->max_size) ht->p.max_size = rounddown_pow_of_two(params->max_size); + /* Cap total entries at 2^31 to avoid nelems overflow. */ + ht->max_elems = 1u << 31; + if (ht->p.max_size < ht->max_elems / 2) + ht->max_elems = ht->p.max_size * 2; + ht->p.min_size = max(ht->p.min_size, HASH_MIN_SIZE); if (params->nelem_hint) -- cgit v1.2.3 From 2d2ab658d2debcb4c0e29c9e6f18e5683f3077bf Mon Sep 17 00:00:00 2001 From: Herbert Xu Date: Fri, 28 Apr 2017 14:10:48 +0800 Subject: rhashtable: Do not lower max_elems when max_size is zero The commit 6d684e54690c ("rhashtable: Cap total number of entries to 2^31") breaks rhashtable users that do not set max_size. This is because when max_size is zero max_elems is also incorrectly set to zero instead of 2^31. This patch fixes it by only lowering max_elems when max_size is not zero. Fixes: 6d684e54690c ("rhashtable: Cap total number of entries to 2^31") Reported-by: Florian Fainelli Reported-by: kernel test robot Signed-off-by: Herbert Xu Signed-off-by: David S. Miller --- lib/rhashtable.c | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'lib/rhashtable.c') diff --git a/lib/rhashtable.c b/lib/rhashtable.c index 751630bbe409..3895486ef551 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -958,13 +958,14 @@ int rhashtable_init(struct rhashtable *ht, if (params->min_size) ht->p.min_size = roundup_pow_of_two(params->min_size); - if (params->max_size) - ht->p.max_size = rounddown_pow_of_two(params->max_size); - /* Cap total entries at 2^31 to avoid nelems overflow. */ ht->max_elems = 1u << 31; - if (ht->p.max_size < ht->max_elems / 2) - ht->max_elems = ht->p.max_size * 2; + + if (params->max_size) { + ht->p.max_size = rounddown_pow_of_two(params->max_size); + if (ht->p.max_size < ht->max_elems / 2) + ht->max_elems = ht->p.max_size * 2; + } ht->p.min_size = max(ht->p.min_size, HASH_MIN_SIZE); -- cgit v1.2.3 From 48e75b430670ebdbb00ba008e1d3690f61ab9824 Mon Sep 17 00:00:00 2001 From: Florian Westphal Date: Mon, 1 May 2017 22:18:01 +0200 Subject: rhashtable: compact struct rhashtable_params By using smaller datatypes this (rather large) struct shrinks considerably (80 -> 48 bytes on x86_64). As this is embedded in other structs, this also rerduces size of several others, e.g. cls_fl_head or nft_hash. Signed-off-by: Florian Westphal Signed-off-by: David S. Miller --- include/linux/rhashtable.h | 18 +++++++++--------- lib/rhashtable.c | 2 +- 2 files changed, 10 insertions(+), 10 deletions(-) (limited to 'lib/rhashtable.c') diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h index 45f89369c4c8..7d56a7ea2b2e 100644 --- a/include/linux/rhashtable.h +++ b/include/linux/rhashtable.h @@ -127,23 +127,23 @@ struct rhashtable; * @head_offset: Offset of rhash_head in struct to be hashed * @max_size: Maximum size while expanding * @min_size: Minimum size while shrinking - * @nulls_base: Base value to generate nulls marker - * @automatic_shrinking: Enable automatic shrinking of tables * @locks_mul: Number of bucket locks to allocate per cpu (default: 128) + * @automatic_shrinking: Enable automatic shrinking of tables + * @nulls_base: Base value to generate nulls marker * @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 */ struct rhashtable_params { - size_t nelem_hint; - size_t key_len; - size_t key_offset; - size_t head_offset; + u16 nelem_hint; + u16 key_len; + u16 key_offset; + u16 head_offset; unsigned int max_size; - unsigned int min_size; - u32 nulls_base; + u16 min_size; bool automatic_shrinking; - size_t locks_mul; + u8 locks_mul; + u32 nulls_base; rht_hashfn_t hashfn; rht_obj_hashfn_t obj_hashfn; rht_obj_cmpfn_t obj_cmpfn; diff --git a/lib/rhashtable.c b/lib/rhashtable.c index 3895486ef551..a930e436db5d 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -967,7 +967,7 @@ int rhashtable_init(struct rhashtable *ht, ht->max_elems = ht->p.max_size * 2; } - ht->p.min_size = max(ht->p.min_size, HASH_MIN_SIZE); + ht->p.min_size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE); if (params->nelem_hint) size = rounded_hashtable_size(&ht->p); -- cgit v1.2.3 From 43ca5bc4f72ed22e6e20feabdd3eab3c721d98cd Mon Sep 17 00:00:00 2001 From: Michal Hocko Date: Mon, 8 May 2017 15:57:18 -0700 Subject: lib/rhashtable.c: simplify a strange allocation pattern alloc_bucket_locks allocation pattern is quite unusual. We are preferring vmalloc when CONFIG_NUMA is enabled. The rationale is that vmalloc will respect the memory policy of the current process and so the backing memory will get distributed over multiple nodes if the requester is configured properly. At least that is the intention, in reality rhastable is shrunk and expanded from a kernel worker so no mempolicy can be assumed. Let's just simplify the code and use kvmalloc helper, which is a transparent way to use kmalloc with vmalloc fallback, if the caller is allowed to block and use the flag otherwise. Link: http://lkml.kernel.org/r/20170306103032.2540-4-mhocko@kernel.org Signed-off-by: Michal Hocko Acked-by: Vlastimil Babka Cc: Tom Herbert Cc: Eric Dumazet Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/rhashtable.c | 13 +++---------- 1 file changed, 3 insertions(+), 10 deletions(-) (limited to 'lib/rhashtable.c') diff --git a/lib/rhashtable.c b/lib/rhashtable.c index a930e436db5d..d9e7274a04cd 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -86,16 +86,9 @@ static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl, size = min(size, 1U << tbl->nest); if (sizeof(spinlock_t) != 0) { - tbl->locks = NULL; -#ifdef CONFIG_NUMA - if (size * sizeof(spinlock_t) > PAGE_SIZE && - gfp == GFP_KERNEL) - tbl->locks = vmalloc(size * sizeof(spinlock_t)); -#endif - if (gfp != GFP_KERNEL) - gfp |= __GFP_NOWARN | __GFP_NORETRY; - - if (!tbl->locks) + if (gfpflags_allow_blocking(gfp)) + tbl->locks = kvmalloc(size * sizeof(spinlock_t), gfp); + else tbl->locks = kmalloc_array(size, sizeof(spinlock_t), gfp); if (!tbl->locks) -- cgit v1.2.3