rhashtable: Convert bucket iterators to take table and index

Factors out bucket dereferences into rht_dereference_bucket() to
introduce proper per bucket lock validation when per bucket locks
are introduced.

Signed-off-by: Thomas Graf <tgraf@suug.ch>
rhashtable: Factor out bucket_tail() function

Subsequent patches will require access to the bucket tail. Factor out
the code to simplify further patching.

Access to the tail is relatively cheap as resizing of the table should
keep the number of entries per bucket to 1..handful.

Signed-off-by: Thomas Graf <tgraf@suug.ch>
nft_hash: Remove rhashtable_remove_pprev()

The removal function of nft_hash currently stores a reference to the
previous element during lookup which is used to optimize removal later
on. This is possible because a lock is held while calling
rhashtable_lookup() and rhashtable_remove().

The addition of deferred resizing leads to concurrent modification
between lookup and removal which no longer allows for this optimization.

However, deferring the resizing leads to predictable insertion and
removal times and the expensive resize is deferred.

Signed-off-by: Thomas Graf <tgraf@suug.ch>
netlink: Lockless lookup with RCU grace period in socket release

Defers the release of the socket reference using call_rcu() to
allow using an RCU read-side protected call to rhashtable_lookup()

Signed-off-by: Thomas Graf <tgraf@suug.ch>
spinlock: Add spin_lock_bh_nested()

Signed-off-by: Thomas Graf <tgraf@suug.ch>
rhashtable: Per bucket locks & expansion/shrinking in work queue

Introduces an array of spinlocks to protect bucket mutations. The number
of spinlocks per CPU is configurable and selected based on the hash of
the bucket. This allows for parallel insertions and removals of entries
which do not share a lock.

The patch also defers expansion and shrinking to a worker queue which
allow insertion and removal from atomic context. Insertions and
deletions may occur in parallel to it and are only held up briefly
while the particular bucket is linked or unzipped.

Mutations of the bucket table pointer is protected by a new mutex, read
access to that pointer for insertion and deletion is RCU protected.

In the event of an expansion or shrinking, the new bucket table allocated
is exposed as a so called future table right away. Lookups, deletions, and
insertions will briefly use both tables.. The future table becomes the main
table after an RCU grace period and initial relinking was performed which
guarantees that no new insertions occur on the old table but all entries
can be found.

The side effect of this is that during that RCU grace period, a bucket
traversal using any rht_for_each() variant on the main table will not see
any insertions performed during the RCU grace period which would at that
point land in the future table. The lookup will see them as it searches
both tables if needed.

Signed-off-by: Thomas Graf <tgraf@suug.ch>
rhashtable: Supports for nulls marker

In order to allow for wider usage of rhashtable, use a special nulls
marker to terminate each chain. The reason for not using the existing
nulls_list is that the pprev pointer usage would not be valid as entries
can be linked in two different buckets at the same time.

The 4 nulls base bits can be set through the rhashtable_params structure
like this:

struct rhashtable_params params = {
        [...]
        .nulls_base = (1U << RHT_BASE_SHIFT),
};

This reduces the hash length from 32 bits to 27 bits.

Signed-off-by: Thomas Graf <tgraf@suug.ch>