As reported by Guenter Roeck, the new rhashtable bit-locking
doesn't work on m68k as it only requires 2-byte alignment, so BIT(1)
is addresses is not unused.
We current use BIT(0) to identify a NULLS marker, but that is only
needed in ->next pointers. The bucket head does not need a NULLS
marker, so the lsb there can be used for locking.
the first 4 patches make some small improvements and re-arrange some
code. The final patch converts to using only BIT(0) for these two
different special purposes.
I had previously suggested dropping the series until I fix it. Given
that this was fairly easy, I retract that I think it best simply to
add these patches to fix the code.
Thanks,
NeilBrown
---
NeilBrown (5):
rhashtable: fix some __rcu annotation errors
rhashtable: reorder some inline functions and macros.
rhashtable: move dereference inside rht_ptr()
rhashtable: replace rht_ptr_locked() with rht_assign_locked()
rhashtable: use BIT(0) for locking.
include/linux/rhashtable.h | 226 +++++++++++++++++++++++++-------------------
lib/rhashtable.c | 24 ++---
lib/test_rhashtable.c | 2
3 files changed, 142 insertions(+), 110 deletions(-)
--
Signature
With these annotations, the rhashtable now gets no
warnings when compiled with "C=1" for sparse checking.
Signed-off-by: NeilBrown <[email protected]>
---
include/linux/rhashtable.h | 11 ++++++-----
lib/rhashtable.c | 4 ++--
2 files changed, 8 insertions(+), 7 deletions(-)
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 460c0eaf6b96..2711cbf01b64 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -40,7 +40,7 @@
* the chain. To avoid dereferencing this pointer without clearing
* the bit first, we use an opaque 'struct rhash_lock_head *' for the
* pointer stored in the bucket. This struct needs to be defined so
- * that rcu_derefernce() works on it, but it has no content so a
+ * that rcu_dereference() works on it, but it has no content so a
* cast is needed for it to be useful. This ensures it isn't
* used by mistake with clearing the lock bit first.
*/
@@ -130,10 +130,10 @@ static inline void rht_unlock(struct bucket_table *tbl,
}
static inline void rht_assign_unlock(struct bucket_table *tbl,
- struct rhash_lock_head **bkt,
+ struct rhash_lock_head __rcu **bkt,
struct rhash_head *obj)
{
- struct rhash_head **p = (struct rhash_head **)bkt;
+ struct rhash_head __rcu **p = (struct rhash_head __rcu **)bkt;
lock_map_release(&tbl->dep_map);
rcu_assign_pointer(*p, obj);
@@ -556,6 +556,7 @@ static inline struct rhash_head *__rhashtable_lookup(
};
struct rhash_lock_head __rcu * const *bkt;
struct bucket_table *tbl;
+ struct rhash_head __rcu *head;
struct rhash_head *he;
unsigned int hash;
@@ -564,8 +565,8 @@ static inline struct rhash_head *__rhashtable_lookup(
hash = rht_key_hashfn(ht, tbl, key, params);
bkt = rht_bucket(tbl, hash);
do {
- he = rht_ptr(rht_dereference_bucket_rcu(*bkt, tbl, hash));
- rht_for_each_rcu_from(he, he, tbl, hash) {
+ head = rht_ptr(rht_dereference_bucket_rcu(*bkt, tbl, hash));
+ rht_for_each_rcu_from(he, head, tbl, hash) {
if (params.obj_cmpfn ?
params.obj_cmpfn(&arg, rht_obj(ht, he)) :
rhashtable_compare(&arg, rht_obj(ht, he)))
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index a8583af43b59..ec485962de5f 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -224,7 +224,7 @@ static int rhashtable_rehash_one(struct rhashtable *ht,
struct bucket_table *new_tbl = rhashtable_last_table(ht, old_tbl);
int err = -EAGAIN;
struct rhash_head *head, *next, *entry;
- struct rhash_head **pprev = NULL;
+ struct rhash_head __rcu **pprev = NULL;
unsigned int new_hash;
if (new_tbl->nest)
@@ -487,7 +487,7 @@ static void *rhashtable_lookup_one(struct rhashtable *ht,
.ht = ht,
.key = key,
};
- struct rhash_head **pprev = NULL;
+ struct rhash_head __rcu **pprev = NULL;
struct rhash_head *head;
int elasticity;
This patch only moves some code around, it doesn't
change the code at all.
A subsequent patch will benefit from this as it needs
to add calls to functions which are now defined before the
call-site, but weren't before.
Signed-off-by: NeilBrown <[email protected]>
---
include/linux/rhashtable.h | 142 ++++++++++++++++++++++----------------------
1 file changed, 71 insertions(+), 71 deletions(-)
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 2711cbf01b64..c504cd820736 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -87,77 +87,6 @@ struct bucket_table {
struct rhash_lock_head __rcu *buckets[] ____cacheline_aligned_in_smp;
};
-/*
- * We lock a bucket by setting BIT(1) in the pointer - this is always
- * zero in real pointers and in the nulls marker.
- * bit_spin_locks do not handle contention well, but the whole point
- * of the hashtable design is to achieve minimum per-bucket contention.
- * A nested hash table might not have a bucket pointer. In that case
- * we cannot get a lock. For remove and replace the bucket cannot be
- * interesting and doesn't need locking.
- * For insert we allocate the bucket if this is the last bucket_table,
- * and then take the lock.
- * Sometimes we unlock a bucket by writing a new pointer there. In that
- * case we don't need to unlock, but we do need to reset state such as
- * local_bh. For that we have rht_assign_unlock(). As rcu_assign_pointer()
- * provides the same release semantics that bit_spin_unlock() provides,
- * this is safe.
- */
-
-static inline void rht_lock(struct bucket_table *tbl,
- struct rhash_lock_head **bkt)
-{
- local_bh_disable();
- bit_spin_lock(1, (unsigned long *)bkt);
- lock_map_acquire(&tbl->dep_map);
-}
-
-static inline void rht_lock_nested(struct bucket_table *tbl,
- struct rhash_lock_head **bucket,
- unsigned int subclass)
-{
- local_bh_disable();
- bit_spin_lock(1, (unsigned long *)bucket);
- lock_acquire_exclusive(&tbl->dep_map, subclass, 0, NULL, _THIS_IP_);
-}
-
-static inline void rht_unlock(struct bucket_table *tbl,
- struct rhash_lock_head **bkt)
-{
- lock_map_release(&tbl->dep_map);
- bit_spin_unlock(1, (unsigned long *)bkt);
- local_bh_enable();
-}
-
-static inline void rht_assign_unlock(struct bucket_table *tbl,
- struct rhash_lock_head __rcu **bkt,
- struct rhash_head *obj)
-{
- struct rhash_head __rcu **p = (struct rhash_head __rcu **)bkt;
-
- lock_map_release(&tbl->dep_map);
- rcu_assign_pointer(*p, obj);
- preempt_enable();
- __release(bitlock);
- local_bh_enable();
-}
-
-/*
- * If 'p' is a bucket head and might be locked:
- * rht_ptr() returns the address without the lock bit.
- * rht_ptr_locked() returns the address WITH the lock bit.
- */
-static inline struct rhash_head __rcu *rht_ptr(const struct rhash_lock_head *p)
-{
- return (void *)(((unsigned long)p) & ~BIT(1));
-}
-
-static inline struct rhash_lock_head __rcu *rht_ptr_locked(const
- struct rhash_head *p)
-{
- return (void *)(((unsigned long)p) | BIT(1));
-}
-
/*
* NULLS_MARKER() expects a hash value with the low
* bits mostly likely to be significant, and it discards
@@ -372,6 +301,77 @@ static inline struct rhash_lock_head __rcu **rht_bucket_insert(
&tbl->buckets[hash];
}
+/*
+ * We lock a bucket by setting BIT(1) in the pointer - this is always
+ * zero in real pointers and in the nulls marker.
+ * bit_spin_locks do not handle contention well, but the whole point
+ * of the hashtable design is to achieve minimum per-bucket contention.
+ * A nested hash table might not have a bucket pointer. In that case
+ * we cannot get a lock. For remove and replace the bucket cannot be
+ * interesting and doesn't need locking.
+ * For insert we allocate the bucket if this is the last bucket_table,
+ * and then take the lock.
+ * Sometimes we unlock a bucket by writing a new pointer there. In that
+ * case we don't need to unlock, but we do need to reset state such as
+ * local_bh. For that we have rht_assign_unlock(). As rcu_assign_pointer()
+ * provides the same release semantics that bit_spin_unlock() provides,
+ * this is safe.
+ */
+
+static inline void rht_lock(struct bucket_table *tbl,
+ struct rhash_lock_head **bkt)
+{
+ local_bh_disable();
+ bit_spin_lock(1, (unsigned long *)bkt);
+ lock_map_acquire(&tbl->dep_map);
+}
+
+static inline void rht_lock_nested(struct bucket_table *tbl,
+ struct rhash_lock_head **bucket,
+ unsigned int subclass)
+{
+ local_bh_disable();
+ bit_spin_lock(1, (unsigned long *)bucket);
+ lock_acquire_exclusive(&tbl->dep_map, subclass, 0, NULL, _THIS_IP_);
+}
+
+static inline void rht_unlock(struct bucket_table *tbl,
+ struct rhash_lock_head **bkt)
+{
+ lock_map_release(&tbl->dep_map);
+ bit_spin_unlock(1, (unsigned long *)bkt);
+ local_bh_enable();
+}
+
+/*
+ * If 'p' is a bucket head and might be locked:
+ * rht_ptr() returns the address without the lock bit.
+ * rht_ptr_locked() returns the address WITH the lock bit.
+ */
+static inline struct rhash_head __rcu *rht_ptr(const struct rhash_lock_head *p)
+{
+ return (void *)(((unsigned long)p) & ~BIT(1));
+}
+
+static inline struct rhash_lock_head __rcu *rht_ptr_locked(const
+ struct rhash_head *p)
+{
+ return (void *)(((unsigned long)p) | BIT(1));
+}
+
+static inline void rht_assign_unlock(struct bucket_table *tbl,
+ struct rhash_lock_head __rcu **bkt,
+ struct rhash_head *obj)
+{
+ struct rhash_head __rcu **p = (struct rhash_head __rcu **)bkt;
+
+ lock_map_release(&tbl->dep_map);
+ rcu_assign_pointer(*p, obj);
+ preempt_enable();
+ __release(bitlock);
+ local_bh_enable();
+}
+
/**
* rht_for_each_from - iterate over hash chain from given head
* @pos: the &struct rhash_head to use as a loop cursor.
The only times rht_ptr_locked() is used, it is to store a new
value in a bucket-head. This is the only time it makes sense
to use it too. So replace it by a function which does the
whole task: Sets the lock bit and assigns to a bucket head.
Signed-off-by: NeilBrown <[email protected]>
---
include/linux/rhashtable.h | 9 ++++++---
lib/rhashtable.c | 6 +++---
2 files changed, 9 insertions(+), 6 deletions(-)
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index b54e6436547e..882bc0fcea4b 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -316,6 +316,7 @@ static inline struct rhash_lock_head __rcu **rht_bucket_insert(
* local_bh. For that we have rht_assign_unlock(). As rcu_assign_pointer()
* provides the same release semantics that bit_spin_unlock() provides,
* this is safe.
+ * When we write to a bucket without unlocking, we use rht_assign_locked().
*/
static inline void rht_lock(struct bucket_table *tbl,
@@ -369,10 +370,12 @@ static inline struct rhash_head *rht_ptr_exclusive(
return (void *)(((unsigned long)p) & ~BIT(1));
}
-static inline struct rhash_lock_head __rcu *rht_ptr_locked(const
- struct rhash_head *p)
+static inline void rht_assign_locked(struct rhash_lock_head __rcu **bkt,
+ struct rhash_head *obj)
{
- return (void *)(((unsigned long)p) | BIT(1));
+ struct rhash_head __rcu **p = (struct rhash_head __rcu **)bkt;
+
+ rcu_assign_pointer(*p, (void *)((unsigned long)obj | BIT(1)));
}
static inline void rht_assign_unlock(struct bucket_table *tbl,
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 1f38f550ba76..3bae6b05b4ba 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -260,7 +260,7 @@ static int rhashtable_rehash_one(struct rhashtable *ht,
rcu_assign_pointer(*pprev, next);
else
/* Need to preserved the bit lock. */
- rcu_assign_pointer(*bkt, rht_ptr_locked(next));
+ rht_assign_locked(bkt, next);
out:
return err;
@@ -518,7 +518,7 @@ static void *rhashtable_lookup_one(struct rhashtable *ht,
rcu_assign_pointer(*pprev, obj);
else
/* Need to preserve the bit lock */
- rcu_assign_pointer(*bkt, rht_ptr_locked(obj));
+ rht_assign_locked(bkt, obj);
return NULL;
}
@@ -571,7 +571,7 @@ static struct bucket_table *rhashtable_insert_one(struct rhashtable *ht,
/* bkt is always the head of the list, so it holds
* the lock, which we need to preserve
*/
- rcu_assign_pointer(*bkt, rht_ptr_locked(obj));
+ rht_assign_locked(bkt, obj);
atomic_inc(&ht->nelems);
if (rht_grow_above_75(ht, tbl))
As reported by Guenter Roeck, the new bit-locking using
BIT(1) doesn't work on the m68k architecture. m68k only requires
2-byte alignment for words and longwords, so there is only one
unused bit in pointers to structs - We current use two, one for the
NULLS marker at the end of the linked list, and one for the bit-lock
in the head of the list.
The two uses don't need to conflict as we never need the head of the
list to be a NULLS marker - the marker is only needed to check if an
object has moved to a different table, and the bucket head cannot
move. The NULLS marker is only needed in a ->next pointer.
As we already have different types for the bucket head pointer (struct
rhash_lock_head) and the ->next pointers (struct rhash_head), it is
fairly easy to treat the lsb differently in each.
So: Initialize buckets heads to NULL, and use the lsb for locking.
When loading the pointer from the bucket head, if it is NULL (ignoring
the lock big), report as being the expected NULLS marker.
When storing a value into a bucket head, if it is a NULLS marker,
store NULL instead.
And convert all places that used bit 1 for locking, to use bit 0.
Fixes: 8f0db018006a ("rhashtable: use bit_spin_locks to protect hash bucket.")
Reported-by: Guenter Roeck <[email protected]>
Tested-by: Guenter Roeck <[email protected]>
Signed-off-by: NeilBrown <[email protected]>
---
include/linux/rhashtable.h | 35 ++++++++++++++++++++++++-----------
lib/rhashtable.c | 2 +-
2 files changed, 25 insertions(+), 12 deletions(-)
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 882bc0fcea4b..f7714d3b46bd 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -35,7 +35,7 @@
* the least significant bit set but otherwise stores the address of
* the hash bucket. This allows us to be be sure we've found the end
* of the right list.
- * The value stored in the hash bucket has BIT(2) used as a lock bit.
+ * The value stored in the hash bucket has BIT(0) used as a lock bit.
* This bit must be atomically set before any changes are made to
* the chain. To avoid dereferencing this pointer without clearing
* the bit first, we use an opaque 'struct rhash_lock_head *' for the
@@ -91,15 +91,19 @@ struct bucket_table {
* NULLS_MARKER() expects a hash value with the low
* bits mostly likely to be significant, and it discards
* the msb.
- * We git it an address, in which the bottom 2 bits are
+ * We give it an address, in which the bottom bit is
* always 0, and the msb might be significant.
* So we shift the address down one bit to align with
* expectations and avoid losing a significant bit.
+ *
+ * We never store the NULLS_MARKER in the hash table
+ * itself as we need the lsb for locking.
+ * Instead we store a NULL
*/
#define RHT_NULLS_MARKER(ptr) \
((void *)NULLS_MARKER(((unsigned long) (ptr)) >> 1))
#define INIT_RHT_NULLS_HEAD(ptr) \
- ((ptr) = RHT_NULLS_MARKER(&(ptr)))
+ ((ptr) = NULL)
static inline bool rht_is_a_nulls(const struct rhash_head *ptr)
{
@@ -302,8 +306,9 @@ static inline struct rhash_lock_head __rcu **rht_bucket_insert(
}
/*
- * We lock a bucket by setting BIT(1) in the pointer - this is always
- * zero in real pointers and in the nulls marker.
+ * We lock a bucket by setting BIT(0) in the pointer - this is always
+ * zero in real pointers. The NULLS mark is never stored in the bucket,
+ * rather we store NULL if the bucket is empty.
* bit_spin_locks do not handle contention well, but the whole point
* of the hashtable design is to achieve minimum per-bucket contention.
* A nested hash table might not have a bucket pointer. In that case
@@ -323,7 +328,7 @@ static inline void rht_lock(struct bucket_table *tbl,
struct rhash_lock_head **bkt)
{
local_bh_disable();
- bit_spin_lock(1, (unsigned long *)bkt);
+ bit_spin_lock(0, (unsigned long *)bkt);
lock_map_acquire(&tbl->dep_map);
}
@@ -332,7 +337,7 @@ static inline void rht_lock_nested(struct bucket_table *tbl,
unsigned int subclass)
{
local_bh_disable();
- bit_spin_lock(1, (unsigned long *)bucket);
+ bit_spin_lock(0, (unsigned long *)bucket);
lock_acquire_exclusive(&tbl->dep_map, subclass, 0, NULL, _THIS_IP_);
}
@@ -340,7 +345,7 @@ static inline void rht_unlock(struct bucket_table *tbl,
struct rhash_lock_head **bkt)
{
lock_map_release(&tbl->dep_map);
- bit_spin_unlock(1, (unsigned long *)bkt);
+ bit_spin_unlock(0, (unsigned long *)bkt);
local_bh_enable();
}
@@ -358,7 +363,9 @@ static inline struct rhash_head *rht_ptr(
const struct rhash_lock_head *p =
rht_dereference_bucket_rcu(*bkt, tbl, hash);
- return (void *)(((unsigned long)p) & ~BIT(1));
+ if ((((unsigned long)p) & ~BIT(0)) == 0)
+ return RHT_NULLS_MARKER(bkt);
+ return (void *)(((unsigned long)p) & ~BIT(0));
}
static inline struct rhash_head *rht_ptr_exclusive(
@@ -367,7 +374,9 @@ static inline struct rhash_head *rht_ptr_exclusive(
const struct rhash_lock_head *p =
rcu_dereference_protected(*bkt, 1);
- return (void *)(((unsigned long)p) & ~BIT(1));
+ if (!p)
+ return RHT_NULLS_MARKER(bkt);
+ return (void *)(((unsigned long)p) & ~BIT(0));
}
static inline void rht_assign_locked(struct rhash_lock_head __rcu **bkt,
@@ -375,7 +384,9 @@ static inline void rht_assign_locked(struct rhash_lock_head __rcu **bkt,
{
struct rhash_head __rcu **p = (struct rhash_head __rcu **)bkt;
- rcu_assign_pointer(*p, (void *)((unsigned long)obj | BIT(1)));
+ if (rht_is_a_nulls(obj))
+ obj = NULL;
+ rcu_assign_pointer(*p, (void *)((unsigned long)obj | BIT(0)));
}
static inline void rht_assign_unlock(struct bucket_table *tbl,
@@ -384,6 +395,8 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
{
struct rhash_head __rcu **p = (struct rhash_head __rcu **)bkt;
+ if (rht_is_a_nulls(obj))
+ obj = NULL;
lock_map_release(&tbl->dep_map);
rcu_assign_pointer(*p, obj);
preempt_enable();
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 3bae6b05b4ba..ad5ab98328c5 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -59,7 +59,7 @@ int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
return 1;
if (unlikely(tbl->nest))
return 1;
- return bit_spin_is_locked(1, (unsigned long *)&tbl->buckets[hash]);
+ return bit_spin_is_locked(0, (unsigned long *)&tbl->buckets[hash]);
}
EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
#else
Rather than dereferencing a pointer to a bucket and then passing the
result to rht_ptr(), we now pass in the pointer and do the dereference
in rht_ptr().
This requires that we pass in the tbl and hash as well to support RCU
checks, and means that the various rht_for_each functions can expect a
pointer that can be dereferenced without further care.
There are two places where we dereference a bucket pointer
where there is no testable protection - in each case we know
that we much have exclusive access without having taken a lock.
The previous code used rht_dereference() to pretend that holding
the mutex provided protects, but holding the mutex never provides
protection for accessing buckets.
So instead introduce rht_ptr_exclusive() that can be used when
there is known to be exclusive access without holding any locks.
Signed-off-by: NeilBrown <[email protected]>
---
include/linux/rhashtable.h | 69 +++++++++++++++++++++++++++-----------------
lib/rhashtable.c | 12 ++++----
lib/test_rhashtable.c | 2 +
3 files changed, 49 insertions(+), 34 deletions(-)
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index c504cd820736..b54e6436547e 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -344,12 +344,28 @@ static inline void rht_unlock(struct bucket_table *tbl,
}
/*
- * If 'p' is a bucket head and might be locked:
- * rht_ptr() returns the address without the lock bit.
- * rht_ptr_locked() returns the address WITH the lock bit.
+ * Where 'bkt' is a bucket and might be locked:
+ * rht_ptr() dereferences that pointer and clears the lock bit.
+ * rht_ptr_exclusive() dereferences in a context where exclusive
+ * access is guaranteed, such as when destroying the table.
*/
-static inline struct rhash_head __rcu *rht_ptr(const struct rhash_lock_head *p)
+static inline struct rhash_head *rht_ptr(
+ struct rhash_lock_head __rcu * const *bkt,
+ struct bucket_table *tbl,
+ unsigned int hash)
{
+ const struct rhash_lock_head *p =
+ rht_dereference_bucket_rcu(*bkt, tbl, hash);
+
+ return (void *)(((unsigned long)p) & ~BIT(1));
+}
+
+static inline struct rhash_head *rht_ptr_exclusive(
+ struct rhash_lock_head __rcu * const *bkt)
+{
+ const struct rhash_lock_head *p =
+ rcu_dereference_protected(*bkt, 1);
+
return (void *)(((unsigned long)p) & ~BIT(1));
}
@@ -380,8 +396,8 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
* @hash: the hash value / bucket index
*/
#define rht_for_each_from(pos, head, tbl, hash) \
- for (pos = rht_dereference_bucket(head, tbl, hash); \
- !rht_is_a_nulls(pos); \
+ for (pos = head; \
+ !rht_is_a_nulls(pos); \
pos = rht_dereference_bucket((pos)->next, tbl, hash))
/**
@@ -391,7 +407,8 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
* @hash: the hash value / bucket index
*/
#define rht_for_each(pos, tbl, hash) \
- rht_for_each_from(pos, rht_ptr(*rht_bucket(tbl, hash)), tbl, hash)
+ rht_for_each_from(pos, rht_ptr(rht_bucket(tbl, hash), tbl, hash), \
+ tbl, hash)
/**
* rht_for_each_entry_from - iterate over hash chain from given head
@@ -403,7 +420,7 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
* @member: name of the &struct rhash_head within the hashable struct.
*/
#define rht_for_each_entry_from(tpos, pos, head, tbl, hash, member) \
- for (pos = rht_dereference_bucket(head, tbl, hash); \
+ for (pos = head; \
(!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
pos = rht_dereference_bucket((pos)->next, tbl, hash))
@@ -416,8 +433,9 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
* @member: name of the &struct rhash_head within the hashable struct.
*/
#define rht_for_each_entry(tpos, pos, tbl, hash, member) \
- rht_for_each_entry_from(tpos, pos, rht_ptr(*rht_bucket(tbl, hash)), \
- tbl, hash, member)
+ rht_for_each_entry_from(tpos, pos, \
+ rht_ptr(rht_bucket(tbl, hash), tbl, hash), \
+ tbl, hash, member)
/**
* rht_for_each_entry_safe - safely iterate over hash chain of given type
@@ -432,8 +450,7 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
* remove the loop cursor from the list.
*/
#define rht_for_each_entry_safe(tpos, pos, next, tbl, hash, member) \
- for (pos = rht_dereference_bucket(rht_ptr(*rht_bucket(tbl, hash)), \
- tbl, hash), \
+ for (pos = rht_ptr(rht_bucket(tbl, hash), tbl, hash), \
next = !rht_is_a_nulls(pos) ? \
rht_dereference_bucket(pos->next, tbl, hash) : NULL; \
(!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
@@ -454,7 +471,7 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
*/
#define rht_for_each_rcu_from(pos, head, tbl, hash) \
for (({barrier(); }), \
- pos = rht_dereference_bucket_rcu(head, tbl, hash); \
+ pos = head; \
!rht_is_a_nulls(pos); \
pos = rcu_dereference_raw(pos->next))
@@ -469,10 +486,9 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
* traversal is guarded by rcu_read_lock().
*/
#define rht_for_each_rcu(pos, tbl, hash) \
- for (({barrier(); }), \
- pos = rht_ptr(rht_dereference_bucket_rcu( \
- *rht_bucket(tbl, hash), tbl, hash)); \
- !rht_is_a_nulls(pos); \
+ for (({barrier(); }), \
+ pos = rht_ptr(rht_bucket(tbl, hash), tbl, hash); \
+ !rht_is_a_nulls(pos); \
pos = rcu_dereference_raw(pos->next))
/**
@@ -490,7 +506,7 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
*/
#define rht_for_each_entry_rcu_from(tpos, pos, head, tbl, hash, member) \
for (({barrier(); }), \
- pos = rht_dereference_bucket_rcu(head, tbl, hash); \
+ pos = head; \
(!rht_is_a_nulls(pos)) && rht_entry(tpos, pos, member); \
pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
@@ -508,8 +524,9 @@ static inline void rht_assign_unlock(struct bucket_table *tbl,
*/
#define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member) \
rht_for_each_entry_rcu_from(tpos, pos, \
- rht_ptr(*rht_bucket(tbl, hash)), \
- tbl, hash, member)
+ rht_ptr(rht_bucket(tbl, hash), \
+ tbl, hash), \
+ tbl, hash, member)
/**
* rhl_for_each_rcu - iterate over rcu hash table list
@@ -556,7 +573,6 @@ static inline struct rhash_head *__rhashtable_lookup(
};
struct rhash_lock_head __rcu * const *bkt;
struct bucket_table *tbl;
- struct rhash_head __rcu *head;
struct rhash_head *he;
unsigned int hash;
@@ -565,8 +581,7 @@ static inline struct rhash_head *__rhashtable_lookup(
hash = rht_key_hashfn(ht, tbl, key, params);
bkt = rht_bucket(tbl, hash);
do {
- head = rht_ptr(rht_dereference_bucket_rcu(*bkt, tbl, hash));
- rht_for_each_rcu_from(he, head, tbl, hash) {
+ rht_for_each_rcu_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) {
if (params.obj_cmpfn ?
params.obj_cmpfn(&arg, rht_obj(ht, he)) :
rhashtable_compare(&arg, rht_obj(ht, he)))
@@ -699,7 +714,7 @@ static inline void *__rhashtable_insert_fast(
return rhashtable_insert_slow(ht, key, obj);
}
- rht_for_each_from(head, rht_ptr(*bkt), tbl, hash) {
+ rht_for_each_from(head, rht_ptr(bkt, tbl, hash), tbl, hash) {
struct rhlist_head *plist;
struct rhlist_head *list;
@@ -744,7 +759,7 @@ static inline void *__rhashtable_insert_fast(
goto slow_path;
/* Inserting at head of list makes unlocking free. */
- head = rht_ptr(rht_dereference_bucket(*bkt, tbl, hash));
+ head = rht_ptr(bkt, tbl, hash);
RCU_INIT_POINTER(obj->next, head);
if (rhlist) {
@@ -971,7 +986,7 @@ static inline int __rhashtable_remove_fast_one(
pprev = NULL;
rht_lock(tbl, bkt);
- rht_for_each_from(he, rht_ptr(*bkt), tbl, hash) {
+ rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) {
struct rhlist_head *list;
list = container_of(he, struct rhlist_head, rhead);
@@ -1130,7 +1145,7 @@ static inline int __rhashtable_replace_fast(
pprev = NULL;
rht_lock(tbl, bkt);
- rht_for_each_from(he, rht_ptr(*bkt), tbl, hash) {
+ rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) {
if (he != obj_old) {
pprev = &he->next;
continue;
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index ec485962de5f..1f38f550ba76 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -232,7 +232,8 @@ static int rhashtable_rehash_one(struct rhashtable *ht,
err = -ENOENT;
- rht_for_each_from(entry, rht_ptr(*bkt), old_tbl, old_hash) {
+ rht_for_each_from(entry, rht_ptr(bkt, old_tbl, old_hash),
+ old_tbl, old_hash) {
err = 0;
next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
@@ -249,8 +250,7 @@ static int rhashtable_rehash_one(struct rhashtable *ht,
rht_lock_nested(new_tbl, &new_tbl->buckets[new_hash], SINGLE_DEPTH_NESTING);
- head = rht_ptr(rht_dereference_bucket(new_tbl->buckets[new_hash],
- new_tbl, new_hash));
+ head = rht_ptr(new_tbl->buckets + new_hash, new_tbl, new_hash);
RCU_INIT_POINTER(entry->next, head);
@@ -492,7 +492,7 @@ static void *rhashtable_lookup_one(struct rhashtable *ht,
int elasticity;
elasticity = RHT_ELASTICITY;
- rht_for_each_from(head, rht_ptr(*bkt), tbl, hash) {
+ rht_for_each_from(head, rht_ptr(bkt, tbl, hash), tbl, hash) {
struct rhlist_head *list;
struct rhlist_head *plist;
@@ -558,7 +558,7 @@ static struct bucket_table *rhashtable_insert_one(struct rhashtable *ht,
if (unlikely(rht_grow_above_100(ht, tbl)))
return ERR_PTR(-EAGAIN);
- head = rht_ptr(rht_dereference_bucket(*bkt, tbl, hash));
+ head = rht_ptr(bkt, tbl, hash);
RCU_INIT_POINTER(obj->next, head);
if (ht->rhlist) {
@@ -1140,7 +1140,7 @@ void rhashtable_free_and_destroy(struct rhashtable *ht,
struct rhash_head *pos, *next;
cond_resched();
- for (pos = rht_ptr(rht_dereference(*rht_bucket(tbl, i), ht)),
+ for (pos = rht_ptr_exclusive(rht_bucket(tbl, i)),
next = !rht_is_a_nulls(pos) ?
rht_dereference(pos->next, ht) : NULL;
!rht_is_a_nulls(pos);
diff --git a/lib/test_rhashtable.c b/lib/test_rhashtable.c
index 02592c2a249c..084fe5a6ac57 100644
--- a/lib/test_rhashtable.c
+++ b/lib/test_rhashtable.c
@@ -500,7 +500,7 @@ static unsigned int __init print_ht(struct rhltable *rhlt)
struct rhash_head *pos, *next;
struct test_obj_rhl *p;
- pos = rht_ptr(rht_dereference(tbl->buckets[i], ht));
+ pos = rht_ptr_exclusive(tbl->buckets + i);
next = !rht_is_a_nulls(pos) ? rht_dereference(pos->next, ht) : NULL;
if (!rht_is_a_nulls(pos)) {
On 4/11/19 6:52 PM, NeilBrown wrote:
> As reported by Guenter Roeck, the new rhashtable bit-locking
> doesn't work on m68k as it only requires 2-byte alignment, so BIT(1)
> is addresses is not unused.
>
> We current use BIT(0) to identify a NULLS marker, but that is only
> needed in ->next pointers. The bucket head does not need a NULLS
> marker, so the lsb there can be used for locking.
>
> the first 4 patches make some small improvements and re-arrange some
> code. The final patch converts to using only BIT(0) for these two
> different special purposes.
>
> I had previously suggested dropping the series until I fix it. Given
> that this was fairly easy, I retract that I think it best simply to
> add these patches to fix the code.
>
For the series:
Tested-by: Guenter Roeck <[email protected]>
Tested with the series applied on top of next-20190412, running all
345 qemu tests. No boot failures or new warnings observed.
Guenter
From: Guenter Roeck <[email protected]>
Date: Fri, 12 Apr 2019 11:08:41 -0700
> On 4/11/19 6:52 PM, NeilBrown wrote:
>> As reported by Guenter Roeck, the new rhashtable bit-locking
>> doesn't work on m68k as it only requires 2-byte alignment, so BIT(1)
>> is addresses is not unused.
>> We current use BIT(0) to identify a NULLS marker, but that is only
>> needed in ->next pointers. The bucket head does not need a NULLS
>> marker, so the lsb there can be used for locking.
>> the first 4 patches make some small improvements and re-arrange some
>> code. The final patch converts to using only BIT(0) for these two
>> different special purposes.
>> I had previously suggested dropping the series until I fix it. Given
>> that this was fairly easy, I retract that I think it best simply to
>> add these patches to fix the code.
>>
> For the series:
>
> Tested-by: Guenter Roeck <[email protected]>
Series applied.
On Fri, 12 Apr 2019 11:52:08 +1000, NeilBrown wrote:
> This patch only moves some code around, it doesn't
> change the code at all.
> A subsequent patch will benefit from this as it needs
> to add calls to functions which are now defined before the
> call-site, but weren't before.
>
> Signed-off-by: NeilBrown <[email protected]>
Hi Neil, I think this patch introduces as slew of sparse warnigns:
include/linux/rhashtable.h:724:23: warning: incorrect type in argument 2 (different address spaces)
include/linux/rhashtable.h:724:23: expected struct rhash_lock_head **bkt
include/linux/rhashtable.h:724:23: got struct rhash_lock_head [noderef] <asn:4>**[assigned] bkt
include/linux/rhashtable.h:728:33: warning: incorrect type in argument 2 (different address spaces)
include/linux/rhashtable.h:728:33: expected struct rhash_lock_head **bkt
include/linux/rhashtable.h:728:33: got struct rhash_lock_head [noderef] <asn:4>**[assigned] bkt
include/linux/rhashtable.h:760:41: warning: incorrect type in argument 2 (different address spaces)
include/linux/rhashtable.h:760:41: expected struct rhash_lock_head **bkt
include/linux/rhashtable.h:760:41: got struct rhash_lock_head [noderef] <asn:4>**[assigned] bkt
include/linux/rhashtable.h:801:25: warning: incorrect type in argument 2 (different address spaces)
include/linux/rhashtable.h:801:25: expected struct rhash_lock_head **bkt
include/linux/rhashtable.h:801:25: got struct rhash_lock_head [noderef] <asn:4>**[assigned] bkt
include/linux/rhashtable.h:1003:23: warning: incorrect type in argument 2 (different address spaces)
include/linux/rhashtable.h:1003:23: expected struct rhash_lock_head **bkt
include/linux/rhashtable.h:1003:23: got struct rhash_lock_head [noderef] <asn:4>**[assigned] bkt
include/linux/rhashtable.h:1047:41: warning: incorrect type in argument 2 (different address spaces)
include/linux/rhashtable.h:1047:41: expected struct rhash_lock_head **bkt
include/linux/rhashtable.h:1047:41: got struct rhash_lock_head [noderef] <asn:4>**[assigned] bkt
include/linux/rhashtable.h:1054:25: warning: incorrect type in argument 2 (different address spaces)
include/linux/rhashtable.h:1054:25: expected struct rhash_lock_head **bkt
include/linux/rhashtable.h:1054:25: got struct rhash_lock_head [noderef] <asn:4>**[assigned] bkt
Is there any chance to get those fixed? Presumably a __force would be
appropriate? Maybe like this?
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index f7714d3b46bd..997017a85032 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -325,27 +325,28 @@ static inline struct rhash_lock_head __rcu **rht_bucket_insert(
*/
static inline void rht_lock(struct bucket_table *tbl,
- struct rhash_lock_head **bkt)
+ struct rhash_lock_head __rcu **bkt)
{
+
local_bh_disable();
- bit_spin_lock(0, (unsigned long *)bkt);
+ bit_spin_lock(0, (unsigned long __force *)bkt);
lock_map_acquire(&tbl->dep_map);
}
static inline void rht_lock_nested(struct bucket_table *tbl,
- struct rhash_lock_head **bucket,
+ struct rhash_lock_head __rcu **bkt,
unsigned int subclass)
{
local_bh_disable();
- bit_spin_lock(0, (unsigned long *)bucket);
+ bit_spin_lock(0, (unsigned long __force *)bkt);
lock_acquire_exclusive(&tbl->dep_map, subclass, 0, NULL, _THIS_IP_);
}
static inline void rht_unlock(struct bucket_table *tbl,
- struct rhash_lock_head **bkt)
+ struct rhash_lock_head __rcu **bkt)
{
lock_map_release(&tbl->dep_map);
- bit_spin_unlock(0, (unsigned long *)bkt);
+ bit_spin_unlock(0, (unsigned long __force *)bkt);
local_bh_enable();
}