linux-toradex.git/include/linux/rhashtable.h, branch v5.1-rc1

rhashtable: Remove obsolete rhashtable_walk_init function

2019-02-22T12:49:00+00:00

The rhashtable_walk_init function has been obsolete for more than
two years.  This patch finally converts its last users over to
rhashtable_walk_enter and removes it.

Signed-off-by: Herbert Xu 
Signed-off-by: Johannes Berg

rhashtable: detect when object movement between tables might have invalidated a lookup

2018-12-03T23:31:55+00:00

Some users of rhashtables might need to move an object from one table
to another -  this appears to be the reason for the incomplete usage
of NULLS markers.

To support these, we store a unique NULLS_MARKER at the end of
each chain, and when a search fails to find a match, we check
if the NULLS marker found was the expected one.  If not, the search
may not have examined all objects in the target bucket, so it is
repeated.

The unique NULLS_MARKER is derived from the address of the
head of the chain.  As this cannot be derived at load-time the
static rhnull in rht_bucket_nested() needs to be initialised
at run time.

Any caller of a lookup function must still be prepared for the
possibility that the object returned is in a different table - it
might have been there for some time.

Note that this does NOT provide support for other uses of
NULLS_MARKERs such as allocating with SLAB_TYPESAFE_BY_RCU or changing
the key of an object and re-inserting it in the same table.
These could only be done safely if new objects were inserted
at the *start* of a hash chain, and that is not currently the case.

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

rhashtable: clean up dereference of ->future_tbl.

2018-06-22T04:43:28+00:00

Using rht_dereference_bucket() to dereference
->future_tbl looks like a type error, and could be confusing.
Using rht_dereference_rcu() to test a pointer for NULL
adds an unnecessary barrier - rcu_access_pointer() is preferred
for NULL tests when no lock is held.

This uses 3 different ways to access ->future_tbl.
- if we know the mutex is held, use rht_dereference()
- if we don't hold the mutex, and are only testing for NULL,
  use rcu_access_pointer()
- otherwise (using RCU protection for true dereference),
  use rht_dereference_rcu().

Note that this includes a simplification of the call to
rhashtable_last_table() - we don't do an extra dereference
before the call any more.

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

rhashtable: simplify INIT_RHT_NULLS_HEAD()

2018-06-22T04:43:27+00:00

The 'ht' and 'hash' arguments to INIT_RHT_NULLS_HEAD() are
no longer used - so drop them.  This allows us to also
remove the nhash argument from nested_table_alloc().

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

rhashtable: remove nulls_base and related code.

2018-06-22T04:43:27+00:00

This "feature" is unused, undocumented, and untested and so doesn't
really belong.  A patch is under development to properly implement
support for detecting when a search gets diverted down a different
chain, which the common purpose of nulls markers.

This patch actually fixes a bug too.  The table resizing allows a
table to grow to 2^31 buckets, but the hash is truncated to 27 bits -
any growth beyond 2^27 is wasteful an ineffective.

This patch results in NULLS_MARKER(0) being used for all chains,
and leaves the use of rht_is_a_null() to test for it.

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

rhashtable: split rhashtable.h

2018-06-22T04:43:27+00:00

Due to the use of rhashtables in net namespaces,
rhashtable.h is included in lots of the kernel,
so a small changes can required a large recompilation.
This makes development painful.

This patch splits out rhashtable-types.h which just includes
the major type declarations, and does not include (non-trivial)
inline code.  rhashtable.h is no longer included by anything
in the include/ directory.
Common include files only include rhashtable-types.h so a large
recompilation is only triggered when that changes.

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

rhashtable: Revise incorrect comment on r{hl, hash}table_walk_enter()

2018-04-24T17:21:45+00:00

Neither rhashtable_walk_enter() or rhltable_walk_enter() sleep, though
they do take a spinlock without irq protection.
So revise the comments to accurately state the contexts in which
these functions can be called.

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

rhashtable: remove outdated comments about grow_decision etc

2018-04-24T17:21:45+00:00

grow_decision and shink_decision no longer exist, so remove
the remaining references to them.

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

rhashtable: reorganize struct rhashtable layout

2018-04-01T03:25:39+00:00

While under frags DDOS I noticed unfortunate false sharing between
@nelems and @params.automatic_shrinking

Move @nelems at the end of struct rhashtable so that first cache line
is shared between all cpus, because almost never dirtied.

Signed-off-by: Eric Dumazet 
Signed-off-by: David S. Miller

rhashtable: Fix rhlist duplicates insertion

2018-03-07T15:44:02+00:00

When inserting duplicate objects (those with the same key),
current rhlist implementation messes up the chain pointers by
updating the bucket pointer instead of prev next pointer to the
newly inserted node. This causes missing elements on removal and
travesal.

Fix that by properly updating pprev pointer to point to
the correct rhash_head next pointer.

Issue: 1241076
Change-Id: I86b2c140bcb4aeb10b70a72a267ff590bb2b17e7
Fixes: ca26893f05e8 ('rhashtable: Add rhlist interface')
Signed-off-by: Paul Blakey 
Acked-by: Herbert Xu 
Signed-off-by: David S. Miller