path: root/lib
diff options
authorHerbert Xu <herbert@gondor.apana.org.au>2015-05-15 11:30:47 +0800
committerDavid S. Miller <davem@davemloft.net>2015-05-16 18:08:26 -0400
commit07ee0722bf941960fb3888f9c9b5839473372fd1 (patch)
treed80ad157b570da14e08e25bb32c5d58af5d969c3 /lib
parentdb9683fb412d4af33f66b9fe3d8dace1c6d113c9 (diff)
rhashtable: Add cap on number of elements in hash table
We currently have no limit on the number of elements in a hash table. This is a problem because some users (tipc) set a ceiling on the maximum table size and when that is reached the hash table may degenerate. Others may encounter OOM when growing and if we allow insertions when that happens the hash table perofrmance may also suffer. This patch adds a new paramater insecure_max_entries which becomes the cap on the table. If unset it defaults to max_size * 2. If it is also zero it means that there is no cap on the number of elements in the table. However, the table will grow whenever the utilisation hits 100% and if that growth fails, you will get ENOMEM on insertion. As allowing oversubscription is potentially dangerous, the name contains the word insecure. Note that the cap is not a hard limit. This is done for performance reasons as enforcing a hard limit will result in use of atomic ops that are heavier than the ones we currently use. The reasoning is that we're only guarding against a gross over- subscription of the table, rather than a small breach of the limit. Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'lib')
1 files changed, 11 insertions, 0 deletions
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index b28df4019ade..4396434e4715 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -14,6 +14,7 @@
* published by the Free Software Foundation.
+#include <linux/atomic.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/log2.h>
@@ -446,6 +447,10 @@ int rhashtable_insert_slow(struct rhashtable *ht, const void *key,
if (key && rhashtable_lookup_fast(ht, key, ht->p))
goto exit;
+ err = -E2BIG;
+ if (unlikely(rht_grow_above_max(ht, tbl)))
+ goto exit;
err = -EAGAIN;
if (rhashtable_check_elasticity(ht, tbl, hash) ||
rht_grow_above_100(ht, tbl))
@@ -738,6 +743,12 @@ 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);
/* The maximum (not average) chain length grows with the

Privacy Policy