linux.git/include/linux/rhashtable.h, branch v4.1-rc2

rhashtable: don't attempt to grow when at max_size

2015-04-24T15:38:12+00:00

The conversion of mac80211's station table to rhashtable had a bug
that I found by accident in code review, that hadn't been found as
rhashtable apparently managed to have a maximum hash chain length
of one (!) in all our testing.

In order to test the bug and verify the fix I set my rhashtable's
max_size very low (4) in order to force getting hash collisions.

At that point, rhashtable WARNed in rhashtable_insert_rehash() but
didn't actually reject the hash table insertion. This caused it to
lose insertions - my master list of stations would have 9 entries,
but the rhashtable only had 5. This may warrant a deeper look, but
that WARN_ON() just shouldn't happen.

Fix this by not returning true from rht_grow_above_100() when the
rhashtable's max_size has been reached - in this case the user is
explicitly configuring it to be at most that big, so even if it's
now above 100% it shouldn't attempt to resize.

This fixes the "lost insertion" issue and consequently allows my
code to display its error (and verify my fix for it.)

Signed-off-by: Johannes Berg 
Acked-by: Thomas Graf 
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: Mark internal/private inline functions as such

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

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: Extend RCU read lock into rhashtable_insert_rehash()

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

rhashtable_insert_rehash() requires RCU locks to be held in order
to access ht->tbl and traverse to the last table.

Fixes: ccd57b1bd324 ("rhashtable: Add immediate rehash during insertion")
Signed-off-by: Thomas Graf 
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: Add multiple rehash support

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

This patch adds the missing bits to allow multiple rehashes.  The
read-side as well as remove already handle this correctly.  So it's
only the rehasher and insertion that need modification to handle
this.

Note that this patch doesn't actually enable it so for now rehashing
is still only performed by the worker thread.

This patch also disables the explicit expand/shrink interface because
the table is meant to expand and shrink automatically, and continuing
to export these interfaces unnecessarily complicates the life of the
rehasher since the rehash process is now composed of two parts.

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