linux-toradex.git/lib/rhashtable.c, branch v4.0-rc1

rhashtable: using ERR_PTR requires linux/err.h

2015-02-09T05:52:24+00:00

Signed-off-by: Stephen Rothwell 
Signed-off-by: David S. Miller

rhashtable: Fix remove logic to avoid cross references between buckets

2015-02-06T23:19:17+00:00

The remove logic properly searched the remaining chain for a matching
entry with an identical hash but it did this while searching from both
the old and new table. Instead in order to not leave stale references
behind we need to:

 1. When growing and searching from the new table:
    Search remaining chain for entry with same hash to avoid having
    the new table directly point to a entry with a different hash.

 2. When shrinking and searching from the old table:
    Check if the element after the removed would create a cross
    reference and avoid it if so.

These bugs were present from the beginning in nft_hash.

Also, both insert functions calculated the hash based on the mask of
the new table. This worked while growing. Wwhile shrinking, the mask
of the inew table is smaller than the mask of the old table. This lead
to a bit not being taken into account when selecting the bucket lock
and thus caused the wrong bucket to be locked eventually.

Fixes: 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table")
Fixes: 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
Reported-by: Ying Xue 
Signed-off-by: Thomas Graf 
Signed-off-by: David S. Miller

rhashtable: Avoid bucket cross reference after removal

2015-02-06T23:18:35+00:00

During a resize, when two buckets in the larger table map to
a single bucket in the smaller table and the new table has already
been (partially) linked to the old table. Removal of an element
may result the bucket in the larger table to point to entries
which all hash to a different value than the bucket index. Thus
causing two buckets to point to the same sub chain after unzipping.
This is not illegal *during* the resize phase but after it has
completed.

Keep the old table around until all of the unzipping is done to
allow the removal code to only search for matching hashed entries
during this special period.

Reported-by: Ying Xue 
Fixes: 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
Signed-off-by: Thomas Graf 
Signed-off-by: David S. Miller

rhashtable: Add more lock verification

2015-02-06T23:18:34+00:00

Catch hash miscalculations which result in hard to track down race
conditions.

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

rhashtable: Dump bucket tables on locking violation under PROVE_LOCKING

2015-02-06T23:18:34+00:00

This simplifies debugging of locking violations if compiled with
CONFIG_PROVE_LOCKING.

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

rhashtable: Wait for RCU readers after final unzip work

2015-02-06T23:18:34+00:00

We need to wait for all RCU readers to complete after the last bit of
unzipping has been completed. Otherwise the old table is freed up
prematurely.

Fixes: 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table")
Signed-off-by: Thomas Graf 
Signed-off-by: David S. Miller

rhashtable: Use a single bucket lock for sibling buckets

2015-02-06T23:18:34+00:00

rhashtable currently allows to use a bucket lock per bucket. This
requires multiple levels of complicated nested locking because when
resizing, a single bucket of the smaller table will map to two
buckets in the larger table. So far rhashtable has explicitly locked
both buckets in the larger table.

By excluding the highest bit of the hash from the bucket lock map and
thus only allowing locks to buckets in a ratio of 1:2, the locking
can be simplified a lot without losing the benefits of multiple locks.
Larger tables which benefit from multiple locks will not have a single
lock per bucket anyway.

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

rhashtable: key_hashfn() must return full hash value

2015-02-06T23:18:34+00:00

The value computed by key_hashfn() is used by rhashtable_lookup_compare()
to traverse both tables during a resize. key_hashfn() must therefore
return the hash value without the buckets mask applied so it can be
masked to the size of each individual table.

Fixes: 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
Signed-off-by: Thomas Graf 
Signed-off-by: David S. Miller

rhashtable: Introduce rhashtable_walk_*

2015-02-05T04:34:52+00:00

Some existing rhashtable users get too intimate with it by walking
the buckets directly.  This prevents us from easily changing the
internals of rhashtable.

This patch adds the helpers rhashtable_walk_init/exit/start/next/stop
which will replace these custom walkers.

They are meant to be usable for both procfs seq_file walks as well
as walking by a netlink dump.  The iterator structure should fit
inside a netlink dump cb structure, with at least one element to
spare.

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

rhashtable: Fix potential crash on destroy in rhashtable_shrink

2015-02-05T04:34:52+00:00

The current being_destroyed check in rhashtable_expand is not
enough since if we start a shrinking process after freeing all
elements in the table that's also going to crash.

This patch adds a being_destroyed check to the deferred worker
thread so that we bail out as soon as we take the lock.

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