linux.git/lib/rhashtable.c, branch v4.1-rc2

rhashtable: Do not schedule more than one rehash if we can't grow further

2015-04-22T18:17:22+00:00

The current code currently only stops inserting rehashes into the
chain when no resizes are currently scheduled. As long as resizes
are scheduled and while inserting above the utilization watermark,
more and more rehashes will be scheduled.

This lead to a perfect DoS storm with thousands of rehashes
scheduled which lead to thousands of spinlocks to be taken
sequentially.

Instead, only allow either a series of resizes or a single rehash.
Drop any further rehashes and return -EBUSY.

Fixes: ccd57b1bd324 ("rhashtable: Add immediate rehash during insertion")
Signed-off-by: Thomas Graf 
Acked-by: Herbert Xu 
Signed-off-by: David S. Miller

rhashtable: Schedule async resize when sync realloc fails

2015-04-22T18:17:22+00:00

When rhashtable_insert_rehash() fails with ENOMEM, this indicates that
we can't allocate the necessary memory in the current context but the
limits as set by the user would still allow to grow.

Thus attempt an async resize in the background where we can allocate
using GFP_KERNEL which is more likely to succeed. The insertion itself
will still fail to indicate pressure.

This fixes a bug where the table would never continue growing once the
utilization is above 100%.

Fixes: ccd57b1bd324 ("rhashtable: Add immediate rehash during insertion")
Signed-off-by: Thomas Graf 
Acked-by: Herbert Xu 
Signed-off-by: David S. Miller

rhashtable: provide len to obj_hashfn

2015-03-25T16:18:33+00:00

nftables sets will be converted to use so called setextensions, moving
the key to a non-fixed position. To hash it, the obj_hashfn must be used,
however it so far doesn't receive the length parameter.

Pass the key length to obj_hashfn() and convert existing users.

Signed-off-by: Patrick McHardy 
Signed-off-by: Pablo Neira Ayuso

rhashtable: Add rhashtable_free_and_destroy()

2015-03-24T21:48:40+00:00

rhashtable_destroy() variant which stops rehashes, iterates over
the table and calls a callback to release resources.

Avoids need for nft_hash to embed rhashtable internals and allows to
get rid of the being_destroyed flag. It also saves a 2nd mutex
lock upon destruction.

Also fixes an RCU lockdep splash on nft set destruction due to
calling rht_for_each_entry_safe() without holding bucket locks.
Open code this loop as we need know that no mutations may occur in
parallel.

Signed-off-by: Thomas Graf 
Signed-off-by: David S. Miller

rhashtable: Disable automatic shrinking by default

2015-03-24T21:48:40+00:00

Introduce a new bool automatic_shrinking to require the
user to explicitly opt-in to automatic shrinking of tables.

Signed-off-by: Thomas Graf 
Signed-off-by: David S. Miller

rhashtable: Use 'unsigned int' consistently

2015-03-24T21:48:39+00:00

Signed-off-by: Thomas Graf 
Signed-off-by: David S. Miller

rhashtable: Add comment on choice of elasticity value

2015-03-24T18:57:04+00:00

This patch adds a comment on the choice of the value 16 as the
maximum chain length before we force a rehash.

Signed-off-by: Herbert Xu 
Signed-off-by: David S. Miller

rhashtable: Fix sleeping inside RCU critical section in walk_stop

2015-03-24T02:16:07+00:00

The commit 963ecbd41a1026d99ec7537c050867428c397b89 ("rhashtable:
Fix use-after-free in rhashtable_walk_stop") fixed a real bug
but created another one because we may end up sleeping inside an
RCU critical section.

This patch fixes it properly by replacing the mutex with a spin
lock that specifically protects the walker lists.

Reported-by: Sasha Levin 
Signed-off-by: Herbert Xu 
Signed-off-by: David S. Miller

rhashtable: Add immediate rehash during insertion

2015-03-24T02:07:52+00:00

This patch reintroduces immediate rehash during insertion.  If
we find during insertion that the table is full or the chain
length exceeds a set limit (currently 16 but may be disabled
with insecure_elasticity) then we will force an immediate rehash.
The rehash will contain an expansion if the table utilisation
exceeds 75%.

If this rehash fails then the insertion will fail.  Otherwise the
insertion will be reattempted in the new hash table.

Signed-off-by: Herbert Xu 
Acked-by: Thomas Graf 
Signed-off-by: David S. Miller

rhashtable: Allow GFP_ATOMIC bucket table allocation

2015-03-24T02:07:52+00:00

This patch adds the ability to allocate bucket table with GFP_ATOMIC
instead of GFP_KERNEL.  This is needed when we perform an immediate
rehash during insertion.

Signed-off-by: Herbert Xu 
Acked-by: Thomas Graf 
Signed-off-by: David S. Miller