[PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[David Laight]

This is a continuation of some patches I wrote over two years ago.
They go a lot further and reduce the per-cpu data to a structure
that only contains two cpu numbers.

I've fixed some broken/missing memory barriers but left the initial xchg()
when acquiring the lock as a full barrier, I think it could be relaxed.

Tested with a userspace harness that can conditionally sleep at various points.

David Laight (9):
  locking/osq_lock: Add some comments about how it works
  locking/osq_lock: Save the cpu number for 'prev' not the node address
  locking/osq_lock: Set prev_cpu=0 instead of locked=1
  locking/osq_lock: Delete 'fast path' code from osq_unlock()
  locking/osq_lock: Avoid writing to node->next in the osq_lock() fast
    path
  locking/osq: Use cpu number for 'next' pointer
  locking/osq: Use 'unsigned int' for next/prev/tail
  locking/osq: inline encode_cpu() and rename decode_cpu()
  locking/osq_lock: Swap next<->prev and tail<->head

 include/linux/osq_lock.h  |  10 +-
 kernel/locking/osq_lock.c | 286 ++++++++++++++++++++------------------
 2 files changed, 154 insertions(+), 142 deletions(-)

-- 
2.39.5

[PATCH v4 next 1/9] locking/osq_lock: Add some comments about how it works

[David Laight]

No code changes, just some extra explanations.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 kernel/locking/osq_lock.c | 27 ++++++++++++++++++++++++---
 1 file changed, 24 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
index b4233dc2c2b0..b17aa704c449 100644
--- a/kernel/locking/osq_lock.c
+++ b/kernel/locking/osq_lock.c
@@ -4,12 +4,33 @@
 #include <linux/osq_lock.h>
 
 /*
- * An MCS like lock especially tailored for optimistic spinning for sleeping
- * lock implementations (mutex, rwsem, etc).
+ * An MCS like spin lock especially tailored for optimistic spinning for
+ * sleeping lock implementations (mutex, rwsem, etc).
+ * Each CPU spins on a local variable to avoid cache-line bounces.
  *
- * Using a single mcs node per CPU is safe because sleeping locks should not be
+ * The CPU that holds the osq_lock checks the mutex/rwsem, the other CPU spin
+ * in osq_lock() until either the osq_lock is obtained or the scheduler
+ * requests the process be preempted.
+ *
+ * Using a single osq node per CPU is safe because sleeping locks should not be
  * called from interrupt context and we have preemption disabled while
  * spinning.
+ *
+ * The osq_nodes for the spinning CPU are put on a double-linked (non circular)
+ * list. The list 'pointers' can either be the address of the osq_node or the
+ * associated CPU number, the CPU numbers are offset by one so that zero can
+ * be used like a NULL ponter.
+ * The mutex/rwsem contains a pointer (CPU number) to the tail of the list.
+ * There is no equivalent pointer to the list head - the 'head' is the
+ * osq_node of the CPU that acquired the osq lock.
+ *
+ * The 'next' pointer of the tail must be NULL, all the other 'next' pointers
+ * must either be valid or transiently NULL.
+ * The 'prev' pointers only need to be valid when node->prev makes sense and,
+ * even then, can be transiently invalid (ie refer to the wrong node).
+ * They are only used for the node->prev->next = node->next update when
+ * 'node' is being removed. Atomically checking node->prev->next == node
+ * ensures the list doesn't get corrupted.
  */
 
 struct optimistic_spin_node {
-- 
2.39.5

[PATCH v4 next 2/9] locking/osq_lock: Save the cpu number for 'prev' not the node address

[David Laight]

The cpu number of node->prev is needed for both the vcpu_is_preempted()
test and to update lock->tail.
This saves reading the cache line for the other cpu's per-cpu data.

The cpu member of optimistic_spin_node is no longer needed.

Merges patches 2 and 3 from v3.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 kernel/locking/osq_lock.c | 33 ++++++++++++++-------------------
 1 file changed, 14 insertions(+), 19 deletions(-)

diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
index b17aa704c449..01988d00c480 100644
--- a/kernel/locking/osq_lock.c
+++ b/kernel/locking/osq_lock.c
@@ -34,9 +34,9 @@
  */
 
 struct optimistic_spin_node {
-	struct optimistic_spin_node *next, *prev;
+	struct optimistic_spin_node *next;
 	int locked; /* 1 if lock acquired */
-	int cpu; /* encoded CPU # + 1 value */
+	int prev; /* CPU number offset by 1 */
 };
 
 static DEFINE_PER_CPU_SHARED_ALIGNED(struct optimistic_spin_node, osq_node);
@@ -50,11 +50,6 @@ static inline int encode_cpu(int cpu_nr)
 	return cpu_nr + 1;
 }
 
-static inline int node_cpu(struct optimistic_spin_node *node)
-{
-	return node->cpu - 1;
-}
-
 static inline struct optimistic_spin_node *decode_cpu(int encoded_cpu_val)
 {
 	int cpu_nr = encoded_cpu_val - 1;
@@ -114,13 +109,12 @@ osq_wait_next(struct optimistic_spin_queue *lock,
 bool osq_lock(struct optimistic_spin_queue *lock)
 {
 	struct optimistic_spin_node *node = this_cpu_ptr(&osq_node);
-	struct optimistic_spin_node *prev, *next;
+	struct optimistic_spin_node *prev_ptr, *next;
 	int curr = encode_cpu(smp_processor_id());
-	int old;
+	int prev;
 
 	node->locked = 0;
 	node->next = NULL;
-	node->cpu = curr;
 
 	/*
 	 * We need both ACQUIRE (pairs with corresponding RELEASE in
@@ -128,11 +122,11 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	 * the node fields we just initialised) semantics when updating
 	 * the lock tail.
 	 */
-	old = atomic_xchg(&lock->tail, curr);
-	if (old == OSQ_UNLOCKED_VAL)
+	prev = atomic_xchg(&lock->tail, curr);
+	if (prev == OSQ_UNLOCKED_VAL)
 		return true;
 
-	prev = decode_cpu(old);
+	prev_ptr = decode_cpu(prev);
 	node->prev = prev;
 
 	/*
@@ -147,7 +141,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	 */
 	smp_wmb();
 
-	WRITE_ONCE(prev->next, node);
+	WRITE_ONCE(prev_ptr->next, node);
 
 	/*
 	 * Normally @prev is untouchable after the above store; because at that
@@ -165,7 +159,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	 * polling, be careful.
 	 */
 	if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
-				  vcpu_is_preempted(node_cpu(node->prev))))
+				  vcpu_is_preempted(node->prev - 1)))
 		return true;
 
 	/* unqueue */
@@ -182,8 +176,8 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 		 * cpu_relax() below implies a compiler barrier which would
 		 * prevent this comparison being optimized away.
 		 */
-		if (data_race(prev->next) == node &&
-		    cmpxchg(&prev->next, node, NULL) == node)
+		if (data_race(prev_ptr->next) == node &&
+		    cmpxchg(&prev_ptr->next, node, NULL) == node)
 			break;
 
 		/*
@@ -201,6 +195,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 		 * case its step-C will write us a new @node->prev pointer.
 		 */
 		prev = READ_ONCE(node->prev);
+		prev_ptr = decode_cpu(prev);
 	}
 
 	/*
@@ -210,7 +205,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	 * back to @prev.
 	 */
 
-	next = osq_wait_next(lock, node, prev->cpu);
+	next = osq_wait_next(lock, node, prev);
 	if (!next)
 		return false;
 
@@ -223,7 +218,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	 */
 
 	WRITE_ONCE(next->prev, prev);
-	WRITE_ONCE(prev->next, next);
+	WRITE_ONCE(prev_ptr->next, next);
 
 	return false;
 }
-- 
2.39.5

[PATCH v4 next 3/9] locking/osq_lock: Set prev_cpu=0 instead of locked=1

[David Laight]

There is no need for separate prev_cpu and locked members of
struct optimistic_spin_node.
Using a single field simplifies the code slightly.
It also removes any possibility of the two values being out of sync.

When cancelling a lock request explicitly set prev_cpu to zero.
Nothing actually looks at the field, but it means that it will be zero
after a subsequent 'fast path' osq_lock() call making things consistent.
The cache line is likely to be dirty (or be dirtied) so there shouldn't
be a performance hit.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 kernel/locking/osq_lock.c | 57 +++++++++++++++++++--------------------
 1 file changed, 28 insertions(+), 29 deletions(-)

diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
index 01988d00c480..23f00c670507 100644
--- a/kernel/locking/osq_lock.c
+++ b/kernel/locking/osq_lock.c
@@ -35,7 +35,6 @@
 
 struct optimistic_spin_node {
 	struct optimistic_spin_node *next;
-	int locked; /* 1 if lock acquired */
 	int prev; /* CPU number offset by 1 */
 };
 
@@ -113,7 +112,6 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	int curr = encode_cpu(smp_processor_id());
 	int prev;
 
-	node->locked = 0;
 	node->next = NULL;
 
 	/*
@@ -158,46 +156,47 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	 * is implemented with a monitor-wait. vcpu_is_preempted() relies on
 	 * polling, be careful.
 	 */
-	if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
-				  vcpu_is_preempted(node->prev - 1)))
-		return true;
+	prev = smp_cond_load_relaxed(&node->prev, !VAL || need_resched() ||
+				     vcpu_is_preempted(VAL - 1));
 
-	/* unqueue */
 	/*
-	 * Step - A  -- stabilize @prev
+	 * Step - A
 	 *
-	 * Undo our @prev->next assignment; this will make @prev's
-	 * unlock()/unqueue() wait for a next pointer since @lock points to us
-	 * (or later).
+	 * Loop until either node->prev is zero (lock acquired) or we
+	 * atomically change prev->next from node to NULL (stopping prev
+	 * handing on the lock).
+	 * Note that 'prev' can unlink itself concurrently with this
+	 * test so that prev/prev_ptr can be stale, but since it
+	 * is per-cpu data the memory can always be read.
 	 */
 
-	for (;;) {
-		/*
-		 * cpu_relax() below implies a compiler barrier which would
-		 * prevent this comparison being optimized away.
-		 */
+	for (;; prev = READ_ONCE(node->prev)) {
+		if (!prev)
+			/* Lock acquired */
+			return true;
+
+		prev_ptr = decode_cpu(prev);
+
 		if (data_race(prev_ptr->next) == node &&
 		    cmpxchg(&prev_ptr->next, node, NULL) == node)
 			break;
 
 		/*
-		 * We can only fail the cmpxchg() racing against an unlock(),
-		 * in which case we should observe @node->locked becoming
-		 * true.
+		 * 'prev' must have unlinked (or be in the process of unlinking)
+		 * itself from the list.
 		 */
-		if (smp_load_acquire(&node->locked))
-			return true;
 
 		cpu_relax();
-
-		/*
-		 * Or we race against a concurrent unqueue()'s step-B, in which
-		 * case its step-C will write us a new @node->prev pointer.
-		 */
-		prev = READ_ONCE(node->prev);
-		prev_ptr = decode_cpu(prev);
 	}
 
+	/*
+	 * If 'prev' tries to remove itself from the list before we write
+	 * a new value to prev->next it will spin in osq_wait_next().
+	 */
+
+	/* Invalidate prev_cpu matching osq_unlock() */
+	node->prev = 0;
+
 	/*
 	 * Step - B -- stabilize @next
 	 *
@@ -240,11 +239,11 @@ void osq_unlock(struct optimistic_spin_queue *lock)
 	node = this_cpu_ptr(&osq_node);
 	next = xchg(&node->next, NULL);
 	if (next) {
-		WRITE_ONCE(next->locked, 1);
+		WRITE_ONCE(next->prev, 0);
 		return;
 	}
 
 	next = osq_wait_next(lock, node, OSQ_UNLOCKED_VAL);
 	if (next)
-		WRITE_ONCE(next->locked, 1);
+		WRITE_ONCE(next->prev, 0);
 }
-- 
2.39.5

[PATCH v4 next 4/9] locking/osq_lock: Delete 'fast path' code from osq_unlock()

[David Laight]

The 'fast path' code in osq_unlock() is pretty much exactly the same as
the first pass of the loop in osq_wait_next() except that it doesn't
have the optimisation to avoid the locked RMW when not the tail of
the list.
So just call osq_wait_next().

Move the assignment next->prev_cpu = old_cpu into osq_wait_next()
as it is always the next line.
Rename osq_wait_next() to osq_unlink_from_next() since that is what is does.

Change osq_wait_next() to use atomic_cmpxchg_release() (not _acquire)
on lock->tail.
This is what osq_unlock() did and seems right to me.

Add an smp_wmb() before the 'prev->next = next' assignment when cancelling
a lock. The previous 'next->prev = prev' assignment lets the 'prev' cpu
complete an unlocking sequence and do its 'next->prev = prev' assignment
first - corrupting the list.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 kernel/locking/osq_lock.c | 140 ++++++++++++++++++++------------------
 1 file changed, 73 insertions(+), 67 deletions(-)

diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
index 23f00c670507..f39f77c3a07d 100644
--- a/kernel/locking/osq_lock.c
+++ b/kernel/locking/osq_lock.c
@@ -57,52 +57,67 @@ static inline struct optimistic_spin_node *decode_cpu(int encoded_cpu_val)
 }
 
 /*
- * Get a stable @node->next pointer, either for unlock() or unqueue() purposes.
- * Can return NULL in case we were the last queued and we updated @lock instead.
+ * Unlink the current cpu's node from the lock's node->prev list.
  *
- * If osq_lock() is being cancelled there must be a previous node
- * and 'old_cpu' is its CPU #.
- * For osq_unlock() there is never a previous node and old_cpu is
- * set to OSQ_UNLOCKED_VAL.
+ * More specifically atomically write its node->prev over the link that
+ * currently points to node.
+ * This is either:
+ *    lock->tail = node->prev
+ * or:
+ *    node->next->prev = node->prev
+ * The first is a simple cmpxchg(), the second is protected against
+ * node->next trying to unlink itself (after need_resched() is set) by using
+ * an xchg() on node->next that sets it to NULL.
+ *
+ * When a lock request is being cancelled the caller needs 'next' to
+ * set node->prev->next = next.
  */
 static inline struct optimistic_spin_node *
-osq_wait_next(struct optimistic_spin_queue *lock,
-	      struct optimistic_spin_node *node,
-	      int old_cpu)
+osq_unlink_from_next(struct optimistic_spin_queue *lock, int prev)
 {
 	int curr = encode_cpu(smp_processor_id());
+	struct optimistic_spin_node *node, *next;
 
 	for (;;) {
-		if (atomic_read(&lock->tail) == curr &&
-		    atomic_cmpxchg_acquire(&lock->tail, curr, old_cpu) == curr) {
+		int tail = atomic_read(&lock->tail);
+		if (curr == tail &&
+		    atomic_try_cmpxchg_release(&lock->tail, &tail, prev)) {
 			/*
-			 * We were the last queued, we moved @lock back. @prev
-			 * will now observe @lock and will complete its
-			 * unlock()/unqueue().
+			 * We were the last queued, lock->tail now references
+			 * prev (or is 0 if the list is now empty).
+			 * If prev was spinning in this loop it can continue.
 			 */
 			return NULL;
 		}
 
+		node = this_cpu_ptr(&osq_node);
+
 		/*
-		 * We must xchg() the @node->next value, because if we were to
-		 * leave it in, a concurrent unlock()/unqueue() from
-		 * @node->next might complete Step-A and think its @prev is
-		 * still valid.
+		 * We must xchg() the @node->next value to ensure that a
+		 * concurrent unqueue() from @node->next will find an invalid
+		 * @prev value (node_next->prev->next != node_next).
 		 *
-		 * If the concurrent unlock()/unqueue() wins the race, we'll
-		 * wait for either @lock to point to us, through its Step-B, or
-		 * wait for a new @node->next from its Step-C.
+		 * If @node->next is already NULL then we need to wait until
+		 * the concurrent unqueue completes.
 		 */
 		if (node->next) {
-			struct optimistic_spin_node *next;
-
 			next = xchg(&node->next, NULL);
 			if (next)
-				return next;
+				break;
 		}
 
 		cpu_relax();
 	}
+
+	/*
+	 * When called from osq_unlock() prev is zero and this hands
+	 * over the lock ownership.
+	 * When called while unqueueing in osq_lock() this completes the
+	 * backwards link, the forwards link is done by the caller.
+	 */
+	WRITE_ONCE(next->prev, prev);
+
+	return next;
 }
 
 bool osq_lock(struct optimistic_spin_queue *lock)
@@ -130,7 +145,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	/*
 	 * osq_lock()			unqueue
 	 *
-	 * node->prev = prev		osq_wait_next()
+	 * node->prev = prev		osq_unlink_from_next()
 	 * WMB				MB
 	 * prev->next = node		next->prev = prev // unqueue-C
 	 *
@@ -160,8 +175,6 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 				     vcpu_is_preempted(VAL - 1));
 
 	/*
-	 * Step - A
-	 *
 	 * Loop until either node->prev is zero (lock acquired) or we
 	 * atomically change prev->next from node to NULL (stopping prev
 	 * handing on the lock).
@@ -191,59 +204,52 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 
 	/*
 	 * If 'prev' tries to remove itself from the list before we write
-	 * a new value to prev->next it will spin in osq_wait_next().
+	 * a new value to prev->next it will spin in osq_unlink_from_next().
+	 * This means we can no longer be given the lock and always
+	 * return false.
 	 */
 
-	/* Invalidate prev_cpu matching osq_unlock() */
+	/*
+	 * Invalidate prev matching osq_unlock().
+	 * This isn't necessary but ensures that both unlocked and fast-path
+	 * locked nodes (where the initial xchg() returned 0) have prev set
+	 * to zero.
+	 * If nothing else it lets the lock chain be followed from lock->tail
+	 * whch may help diagnostics.
+	 */
 	node->prev = 0;
 
 	/*
-	 * Step - B -- stabilize @next
-	 *
-	 * Similar to unlock(), wait for @node->next or move @lock from @node
-	 * back to @prev.
+	 * Now that the linkage to prev cannot change underneath us
+	 * remove ourselves from the node->prev list.
+	 * This does:
+	 * (node->next ? node->next->prev : lock->tail) = node->prev
 	 */
-
-	next = osq_wait_next(lock, node, prev);
-	if (!next)
-		return false;
+	next = osq_unlink_from_next(lock, prev);
 
 	/*
-	 * Step - C -- unlink
-	 *
-	 * @prev is stable because its still waiting for a new @prev->next
-	 * pointer, @next is stable because our @node->next pointer is NULL and
-	 * it will wait in Step-A.
+	 * Finally mend the node->next list that was 'broken' to
+	 * stop node->prev trying to unlink from us.
+	 * If next is NULL then lock->tail is prev_ptr and another node
+	 * can be added - so we must not re-write the NULL.
 	 */
-
-	WRITE_ONCE(next->prev, prev);
-	WRITE_ONCE(prev_ptr->next, next);
+	if (next) {
+		/*
+		 * This must happen after the write to node->next->prev.
+		 * If swapped then prev could unlink itself before our
+		 * write to node->next->prev and the the wrong value would
+		 * end up in node->next->prev.
+		 * Probably can't actually happen due to re-ordering of writes,
+		 * but could happen without a compiler barrier.
+		 */
+		smp_wmb();
+		WRITE_ONCE(prev_ptr->next, next);
+	}
 
 	return false;
 }
 
 void osq_unlock(struct optimistic_spin_queue *lock)
 {
-	struct optimistic_spin_node *node, *next;
-	int curr = encode_cpu(smp_processor_id());
-
-	/*
-	 * Fast path for the uncontended case.
-	 */
-	if (atomic_try_cmpxchg_release(&lock->tail, &curr, OSQ_UNLOCKED_VAL))
-		return;
-
-	/*
-	 * Second most likely case.
-	 */
-	node = this_cpu_ptr(&osq_node);
-	next = xchg(&node->next, NULL);
-	if (next) {
-		WRITE_ONCE(next->prev, 0);
-		return;
-	}
-
-	next = osq_wait_next(lock, node, OSQ_UNLOCKED_VAL);
-	if (next)
-		WRITE_ONCE(next->prev, 0);
+	osq_unlink_from_next(lock, OSQ_UNLOCKED_VAL);
 }
-- 
2.39.5

[PATCH v4 next 5/9] locking/osq_lock: Avoid writing to node->next in the osq_lock() fast path

[David Laight]

osq_unlink_from_next() is called by osq_unlock() and when osq_lock() returns
false (lock not acquired).
osq_unlink_from_next() will either have done an explicit xchg(&node->next, NULL)
or a cmpxchg() that checked that node was lock->tail.
In both cases node->next will be NULL in exit.
Since it can't be changed when not referenced by an osq_lock there is no
need to initialise it at the top of osq_lock().

The atomic_xchg(&lock->tail, curr) could probably changed back to
the '_acquire' version or even the _relaxed version.
The important barrier is after the write to node->prev.

Defer determining the address of the CPU's 'node' until after the
atomic_exchange() so that it isn't done in the uncontented path.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 kernel/locking/osq_lock.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
index f39f77c3a07d..2f92d3d63da9 100644
--- a/kernel/locking/osq_lock.c
+++ b/kernel/locking/osq_lock.c
@@ -86,6 +86,9 @@ osq_unlink_from_next(struct optimistic_spin_queue *lock, int prev)
 			 * We were the last queued, lock->tail now references
 			 * prev (or is 0 if the list is now empty).
 			 * If prev was spinning in this loop it can continue.
+			 *
+			 * Since we are the tail of the list, node->next
+			 * must be NULL.
 			 */
 			return NULL;
 		}
@@ -122,13 +125,10 @@ osq_unlink_from_next(struct optimistic_spin_queue *lock, int prev)
 
 bool osq_lock(struct optimistic_spin_queue *lock)
 {
-	struct optimistic_spin_node *node = this_cpu_ptr(&osq_node);
-	struct optimistic_spin_node *prev_ptr, *next;
+	struct optimistic_spin_node *node, *prev_ptr, *next;
 	int curr = encode_cpu(smp_processor_id());
 	int prev;
 
-	node->next = NULL;
-
 	/*
 	 * We need both ACQUIRE (pairs with corresponding RELEASE in
 	 * unlock() uncontended, or fastpath) and RELEASE (to publish
@@ -139,6 +139,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	if (prev == OSQ_UNLOCKED_VAL)
 		return true;
 
+	node = this_cpu_ptr(&osq_node);
 	prev_ptr = decode_cpu(prev);
 	node->prev = prev;
 
-- 
2.39.5

[PATCH v4 next 6/9] locking/osq: Use cpu number for 'next' pointer

[David Laight]

There is only one write done through node->next (setting prev)
when 'node' is being removed.
So the code can consistently use the cpu numbers pretty much
throughout (this was suggested by Linux a while back).

This reduces struct optimistic_spin_node to 8 bytes.
This is currently padded out to a cache line which is silly.
Change to be __aligned(8) so that it isn't split between cache lines.

Accesses to 'other cpu' data are very limited and only happen during
the enque and deque operation.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 kernel/locking/osq_lock.c | 43 ++++++++++++++++++++-------------------
 1 file changed, 22 insertions(+), 21 deletions(-)

diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
index 2f92d3d63da9..0f68ee017b54 100644
--- a/kernel/locking/osq_lock.c
+++ b/kernel/locking/osq_lock.c
@@ -24,21 +24,21 @@
  * There is no equivalent pointer to the list head - the 'head' is the
  * osq_node of the CPU that acquired the osq lock.
  *
- * The 'next' pointer of the tail must be NULL, all the other 'next' pointers
- * must either be valid or transiently NULL.
- * The 'prev' pointers only need to be valid when node->prev makes sense and,
- * even then, can be transiently invalid (ie refer to the wrong node).
- * They are only used for the node->prev->next = node->next update when
- * 'node' is being removed. Atomically checking node->prev->next == node
+ * The 'next' pointer of the tail must be zero, all the other 'next' pointers
+ * must either be valid or transiently zero.
+ * The 'prev' pointer is zero unless the node is waiting for the lock, when
+ * waiting it may refer to the wrong node (node->prev->next != node).
+ * The 'prev' value is only needed for the node->prev->next = node->next update
+ * when 'node' is being removed. Atomically checking node->prev->next == node
  * ensures the list doesn't get corrupted.
  */
 
 struct optimistic_spin_node {
-	struct optimistic_spin_node *next;
-	int prev; /* CPU number offset by 1 */
-};
+	int next; /* CPU number offset by 1, 0 if no next */
+	int prev; /* CPU number offset by 1, 0 if lock held */
+} __aligned(8);
 
-static DEFINE_PER_CPU_SHARED_ALIGNED(struct optimistic_spin_node, osq_node);
+static DEFINE_PER_CPU(struct optimistic_spin_node, osq_node);
 
 /*
  * We use the value 0 to represent "no CPU", thus the encoded value
@@ -72,11 +72,12 @@ static inline struct optimistic_spin_node *decode_cpu(int encoded_cpu_val)
  * When a lock request is being cancelled the caller needs 'next' to
  * set node->prev->next = next.
  */
-static inline struct optimistic_spin_node *
+static inline int
 osq_unlink_from_next(struct optimistic_spin_queue *lock, int prev)
 {
 	int curr = encode_cpu(smp_processor_id());
-	struct optimistic_spin_node *node, *next;
+	struct optimistic_spin_node *node;
+	int next;
 
 	for (;;) {
 		int tail = atomic_read(&lock->tail);
@@ -88,9 +89,9 @@ osq_unlink_from_next(struct optimistic_spin_queue *lock, int prev)
 			 * If prev was spinning in this loop it can continue.
 			 *
 			 * Since we are the tail of the list, node->next
-			 * must be NULL.
+			 * must be zero.
 			 */
-			return NULL;
+			return 0;
 		}
 
 		node = this_cpu_ptr(&osq_node);
@@ -104,7 +105,7 @@ osq_unlink_from_next(struct optimistic_spin_queue *lock, int prev)
 		 * the concurrent unqueue completes.
 		 */
 		if (node->next) {
-			next = xchg(&node->next, NULL);
+			next = xchg(&node->next, 0);
 			if (next)
 				break;
 		}
@@ -118,16 +119,16 @@ osq_unlink_from_next(struct optimistic_spin_queue *lock, int prev)
 	 * When called while unqueueing in osq_lock() this completes the
 	 * backwards link, the forwards link is done by the caller.
 	 */
-	WRITE_ONCE(next->prev, prev);
+	WRITE_ONCE(decode_cpu(next)->prev, prev);
 
 	return next;
 }
 
 bool osq_lock(struct optimistic_spin_queue *lock)
 {
-	struct optimistic_spin_node *node, *prev_ptr, *next;
+	struct optimistic_spin_node *node, *prev_ptr;
 	int curr = encode_cpu(smp_processor_id());
-	int prev;
+	int next, prev;
 
 	/*
 	 * We need both ACQUIRE (pairs with corresponding RELEASE in
@@ -155,7 +156,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	 */
 	smp_wmb();
 
-	WRITE_ONCE(prev_ptr->next, node);
+	WRITE_ONCE(prev_ptr->next, curr);
 
 	/*
 	 * Normally @prev is untouchable after the above store; because at that
@@ -191,8 +192,8 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 
 		prev_ptr = decode_cpu(prev);
 
-		if (data_race(prev_ptr->next) == node &&
-		    cmpxchg(&prev_ptr->next, node, NULL) == node)
+		if (data_race(prev_ptr->next) == curr &&
+		    cmpxchg(&prev_ptr->next, curr, 0) == curr)
 			break;
 
 		/*
-- 
2.39.5

[PATCH v4 next 7/9] locking/osq: Use 'unsigned int' for next/prev/tail

[David Laight]

Consistently use 'unsigned int' for all the 'offset by 1' cpu numbers.
This makes the code only use one set of xchg primitives.
The unsigned type gives marginally better code inside per_cpu_ptr().

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 include/linux/osq_lock.h  |  8 ++++----
 kernel/locking/osq_lock.c | 31 +++++++++++++++----------------
 2 files changed, 19 insertions(+), 20 deletions(-)

diff --git a/include/linux/osq_lock.h b/include/linux/osq_lock.h
index ea8fb31379e3..9e637e265189 100644
--- a/include/linux/osq_lock.h
+++ b/include/linux/osq_lock.h
@@ -12,17 +12,17 @@ struct optimistic_spin_queue {
 	 * Stores an encoded value of the CPU # of the tail node in the queue.
 	 * If the queue is empty, then it's set to OSQ_UNLOCKED_VAL.
 	 */
-	atomic_t tail;
+	unsigned int tail;
 };
 
 #define OSQ_UNLOCKED_VAL (0)
 
 /* Init macro and function. */
-#define OSQ_LOCK_UNLOCKED { ATOMIC_INIT(OSQ_UNLOCKED_VAL) }
+#define OSQ_LOCK_UNLOCKED { OSQ_UNLOCKED_VAL }
 
 static inline void osq_lock_init(struct optimistic_spin_queue *lock)
 {
-	atomic_set(&lock->tail, OSQ_UNLOCKED_VAL);
+	WRITE_ONCE(lock->tail, OSQ_UNLOCKED_VAL);
 }
 
 extern bool osq_lock(struct optimistic_spin_queue *lock);
@@ -30,7 +30,7 @@ extern void osq_unlock(struct optimistic_spin_queue *lock);
 
 static inline bool osq_is_locked(struct optimistic_spin_queue *lock)
 {
-	return atomic_read(&lock->tail) != OSQ_UNLOCKED_VAL;
+	return READ_ONCE(lock->tail) != OSQ_UNLOCKED_VAL;
 }
 
 #endif
diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
index 0f68ee017b54..144eb446c867 100644
--- a/kernel/locking/osq_lock.c
+++ b/kernel/locking/osq_lock.c
@@ -34,8 +34,8 @@
  */
 
 struct optimistic_spin_node {
-	int next; /* CPU number offset by 1, 0 if no next */
-	int prev; /* CPU number offset by 1, 0 if lock held */
+	unsigned int next; /* CPU number offset by 1, 0 if no next */
+	unsigned int prev; /* CPU number offset by 1, 0 if lock held */
 } __aligned(8);
 
 static DEFINE_PER_CPU(struct optimistic_spin_node, osq_node);
@@ -44,16 +44,15 @@ static DEFINE_PER_CPU(struct optimistic_spin_node, osq_node);
  * We use the value 0 to represent "no CPU", thus the encoded value
  * will be the CPU number incremented by 1.
  */
-static inline int encode_cpu(int cpu_nr)
+static inline unsigned int encode_cpu(unsigned int cpu_nr)
 {
 	return cpu_nr + 1;
 }
 
-static inline struct optimistic_spin_node *decode_cpu(int encoded_cpu_val)
+static inline struct optimistic_spin_node *
+decode_cpu(unsigned int encoded_cpu_val)
 {
-	int cpu_nr = encoded_cpu_val - 1;
-
-	return per_cpu_ptr(&osq_node, cpu_nr);
+	return per_cpu_ptr(&osq_node, encoded_cpu_val - 1);
 }
 
 /*
@@ -72,17 +71,17 @@ static inline struct optimistic_spin_node *decode_cpu(int encoded_cpu_val)
  * When a lock request is being cancelled the caller needs 'next' to
  * set node->prev->next = next.
  */
-static inline int
-osq_unlink_from_next(struct optimistic_spin_queue *lock, int prev)
+static inline unsigned int
+osq_unlink_from_next(struct optimistic_spin_queue *lock, unsigned int prev)
 {
-	int curr = encode_cpu(smp_processor_id());
+	unsigned int curr = encode_cpu(smp_processor_id());
 	struct optimistic_spin_node *node;
-	int next;
+	unsigned int next;
 
 	for (;;) {
-		int tail = atomic_read(&lock->tail);
+		unsigned int tail = READ_ONCE(lock->tail);
 		if (curr == tail &&
-		    atomic_try_cmpxchg_release(&lock->tail, &tail, prev)) {
+		    try_cmpxchg_release(&lock->tail, &tail, prev)) {
 			/*
 			 * We were the last queued, lock->tail now references
 			 * prev (or is 0 if the list is now empty).
@@ -127,8 +126,8 @@ osq_unlink_from_next(struct optimistic_spin_queue *lock, int prev)
 bool osq_lock(struct optimistic_spin_queue *lock)
 {
 	struct optimistic_spin_node *node, *prev_ptr;
-	int curr = encode_cpu(smp_processor_id());
-	int next, prev;
+	unsigned int curr = encode_cpu(smp_processor_id());
+	unsigned int next, prev;
 
 	/*
 	 * We need both ACQUIRE (pairs with corresponding RELEASE in
@@ -136,7 +135,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	 * the node fields we just initialised) semantics when updating
 	 * the lock tail.
 	 */
-	prev = atomic_xchg(&lock->tail, curr);
+	prev = xchg(&lock->tail, curr);
 	if (prev == OSQ_UNLOCKED_VAL)
 		return true;
 
-- 
2.39.5

[PATCH v4 next 8/9] locking/osq: inline encode_cpu() and rename decode_cpu()

[David Laight]

Having a function to add the 1 offset to the cpu number doesn't
make the code any easier to read.
Just use smp_processor_id() + 1.

Rename decode_cpu() to cpu_spin_node() to match what it does.

No functional change.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 kernel/locking/osq_lock.c | 23 +++++++----------------
 1 file changed, 7 insertions(+), 16 deletions(-)

diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
index 144eb446c867..8dfd729d1a81 100644
--- a/kernel/locking/osq_lock.c
+++ b/kernel/locking/osq_lock.c
@@ -40,19 +40,10 @@ struct optimistic_spin_node {
 
 static DEFINE_PER_CPU(struct optimistic_spin_node, osq_node);
 
-/*
- * We use the value 0 to represent "no CPU", thus the encoded value
- * will be the CPU number incremented by 1.
- */
-static inline unsigned int encode_cpu(unsigned int cpu_nr)
-{
-	return cpu_nr + 1;
-}
-
 static inline struct optimistic_spin_node *
-decode_cpu(unsigned int encoded_cpu_val)
+cpu_spin_node(unsigned int offset_cpu_num)
 {
-	return per_cpu_ptr(&osq_node, encoded_cpu_val - 1);
+	return per_cpu_ptr(&osq_node, offset_cpu_num - 1);
 }
 
 /*
@@ -74,7 +65,7 @@ decode_cpu(unsigned int encoded_cpu_val)
 static inline unsigned int
 osq_unlink_from_next(struct optimistic_spin_queue *lock, unsigned int prev)
 {
-	unsigned int curr = encode_cpu(smp_processor_id());
+	unsigned int curr = smp_processor_id() + 1;
 	struct optimistic_spin_node *node;
 	unsigned int next;
 
@@ -118,7 +109,7 @@ osq_unlink_from_next(struct optimistic_spin_queue *lock, unsigned int prev)
 	 * When called while unqueueing in osq_lock() this completes the
 	 * backwards link, the forwards link is done by the caller.
 	 */
-	WRITE_ONCE(decode_cpu(next)->prev, prev);
+	WRITE_ONCE(cpu_spin_node(next)->prev, prev);
 
 	return next;
 }
@@ -126,7 +117,7 @@ osq_unlink_from_next(struct optimistic_spin_queue *lock, unsigned int prev)
 bool osq_lock(struct optimistic_spin_queue *lock)
 {
 	struct optimistic_spin_node *node, *prev_ptr;
-	unsigned int curr = encode_cpu(smp_processor_id());
+	unsigned int curr = smp_processor_id() + 1;
 	unsigned int next, prev;
 
 	/*
@@ -140,7 +131,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 		return true;
 
 	node = this_cpu_ptr(&osq_node);
-	prev_ptr = decode_cpu(prev);
+	prev_ptr = cpu_spin_node(prev);
 	node->prev = prev;
 
 	/*
@@ -189,7 +180,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 			/* Lock acquired */
 			return true;
 
-		prev_ptr = decode_cpu(prev);
+		prev_ptr = cpu_spin_node(prev);
 
 		if (data_race(prev_ptr->next) == curr &&
 		    cmpxchg(&prev_ptr->next, curr, 0) == curr)
-- 
2.39.5

[PATCH v4 next 9/9] locking/osq_lock: Swap next<->prev and tail<->head

[David Laight]

I think it is easier to understand this code if you think that cpu
add themselves to the head of the list and the cpu at the tail
owns the lock.
Remember nodes are never removed from the list - they only remove
themselves.

So swap the field names over.

Pretty much all the code has already been changed in this series
so it doesn't make that much difference to the overall lines changed.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 include/linux/osq_lock.h  |   8 +-
 kernel/locking/osq_lock.c | 165 +++++++++++++++++++-------------------
 2 files changed, 86 insertions(+), 87 deletions(-)

diff --git a/include/linux/osq_lock.h b/include/linux/osq_lock.h
index 9e637e265189..d471f3ab4238 100644
--- a/include/linux/osq_lock.h
+++ b/include/linux/osq_lock.h
@@ -9,10 +9,10 @@
 
 struct optimistic_spin_queue {
 	/*
-	 * Stores an encoded value of the CPU # of the tail node in the queue.
+	 * Stores an encoded value of the CPU # of the head node in the queue.
 	 * If the queue is empty, then it's set to OSQ_UNLOCKED_VAL.
 	 */
-	unsigned int tail;
+	unsigned int head;
 };
 
 #define OSQ_UNLOCKED_VAL (0)
@@ -22,7 +22,7 @@ struct optimistic_spin_queue {
 
 static inline void osq_lock_init(struct optimistic_spin_queue *lock)
 {
-	WRITE_ONCE(lock->tail, OSQ_UNLOCKED_VAL);
+	WRITE_ONCE(lock->head, OSQ_UNLOCKED_VAL);
 }
 
 extern bool osq_lock(struct optimistic_spin_queue *lock);
@@ -30,7 +30,7 @@ extern void osq_unlock(struct optimistic_spin_queue *lock);
 
 static inline bool osq_is_locked(struct optimistic_spin_queue *lock)
 {
-	return READ_ONCE(lock->tail) != OSQ_UNLOCKED_VAL;
+	return READ_ONCE(lock->head) != OSQ_UNLOCKED_VAL;
 }
 
 #endif
diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
index 8dfd729d1a81..8dd01fee80bf 100644
--- a/kernel/locking/osq_lock.c
+++ b/kernel/locking/osq_lock.c
@@ -17,25 +17,24 @@
  * spinning.
  *
  * The osq_nodes for the spinning CPU are put on a double-linked (non circular)
- * list. The list 'pointers' can either be the address of the osq_node or the
- * associated CPU number, the CPU numbers are offset by one so that zero can
- * be used like a NULL ponter.
- * The mutex/rwsem contains a pointer (CPU number) to the tail of the list.
- * There is no equivalent pointer to the list head - the 'head' is the
- * osq_node of the CPU that acquired the osq lock.
+ * list similar to an hlist.
+ * The list 'pointers' are the CPU numbers (offset by one so that zero can
+ * be used like a NULL ponter).
+ * Waiting cpu are added to the head of the list, the tail of the list is
+ * the osq_node of the CPU that acquired the osq lock.
  *
- * The 'next' pointer of the tail must be zero, all the other 'next' pointers
+ * The 'prev' pointer of the head must be zero, all the other 'prev' pointers
  * must either be valid or transiently zero.
- * The 'prev' pointer is zero unless the node is waiting for the lock, when
- * waiting it may refer to the wrong node (node->prev->next != node).
- * The 'prev' value is only needed for the node->prev->next = node->next update
- * when 'node' is being removed. Atomically checking node->prev->next == node
+ * The 'next' pointer is zero unless the node is waiting for the lock, when
+ * waiting it may refer to the wrong node (node->next->prev != node).
+ * The 'next' value is only needed for the node->next->prev = node->prev update
+ * when 'node' is being removed. Atomically checking node->next->prev == node
  * ensures the list doesn't get corrupted.
  */
 
 struct optimistic_spin_node {
-	unsigned int next; /* CPU number offset by 1, 0 if no next */
-	unsigned int prev; /* CPU number offset by 1, 0 if lock held */
+	unsigned int next; /* CPU number offset by 1, 0 if lock held */
+	unsigned int prev; /* CPU number offset by 1, 0 if no prev */
 } __aligned(8);
 
 static DEFINE_PER_CPU(struct optimistic_spin_node, osq_node);
@@ -47,38 +46,38 @@ cpu_spin_node(unsigned int offset_cpu_num)
 }
 
 /*
- * Unlink the current cpu's node from the lock's node->prev list.
+ * Unlink the current cpu's node from the lock's node->next list.
  *
- * More specifically atomically write its node->prev over the link that
+ * More specifically atomically write its node->next over the link that
  * currently points to node.
  * This is either:
- *    lock->tail = node->prev
+ *    lock->head = node->next
  * or:
- *    node->next->prev = node->prev
+ *    node->prev->next = node->next
  * The first is a simple cmpxchg(), the second is protected against
- * node->next trying to unlink itself (after need_resched() is set) by using
- * an xchg() on node->next that sets it to NULL.
+ * node->prev trying to unlink itself (after need_resched() is set) by using
+ * an xchg() on node->prev that sets it to NULL.
  *
- * When a lock request is being cancelled the caller needs 'next' to
- * set node->prev->next = next.
+ * When a lock request is being cancelled the caller needs 'prev' to
+ * set node->next->prev = prev.
  */
 static inline unsigned int
-osq_unlink_from_next(struct optimistic_spin_queue *lock, unsigned int prev)
+osq_unlink_from_prev(struct optimistic_spin_queue *lock, unsigned int next)
 {
 	unsigned int curr = smp_processor_id() + 1;
 	struct optimistic_spin_node *node;
-	unsigned int next;
+	unsigned int prev;
 
 	for (;;) {
-		unsigned int tail = READ_ONCE(lock->tail);
-		if (curr == tail &&
-		    try_cmpxchg_release(&lock->tail, &tail, prev)) {
+		unsigned int head = READ_ONCE(lock->head);
+		if (curr == head &&
+		    try_cmpxchg_release(&lock->head, &head, next)) {
 			/*
-			 * We were the last queued, lock->tail now references
-			 * prev (or is 0 if the list is now empty).
-			 * If prev was spinning in this loop it can continue.
+			 * We were the last queued, lock->head now references
+			 * next (or is 0 if the list is now empty).
+			 * If next was spinning in this loop it can continue.
 			 *
-			 * Since we are the tail of the list, node->next
+			 * Since we are the head of the list, node->prev
 			 * must be zero.
 			 */
 			return 0;
@@ -87,16 +86,16 @@ osq_unlink_from_next(struct optimistic_spin_queue *lock, unsigned int prev)
 		node = this_cpu_ptr(&osq_node);
 
 		/*
-		 * We must xchg() the @node->next value to ensure that a
-		 * concurrent unqueue() from @node->next will find an invalid
-		 * @prev value (node_next->prev->next != node_next).
+		 * We must xchg() the @node->prev value to ensure that a
+		 * concurrent unqueue() from @node->prev will find an invalid
+		 * @next value (node_prev->next->prev != node_prev).
 		 *
-		 * If @node->next is already NULL then we need to wait until
+		 * If @node->prev is already NULL then we need to wait until
 		 * the concurrent unqueue completes.
 		 */
-		if (node->next) {
-			next = xchg(&node->next, 0);
-			if (next)
+		if (node->prev) {
+			prev = xchg(&node->prev, 0);
+			if (prev)
 				break;
 		}
 
@@ -104,52 +103,52 @@ osq_unlink_from_next(struct optimistic_spin_queue *lock, unsigned int prev)
 	}
 
 	/*
-	 * When called from osq_unlock() prev is zero and this hands
+	 * When called from osq_unlock() next is zero and this hands
 	 * over the lock ownership.
 	 * When called while unqueueing in osq_lock() this completes the
 	 * backwards link, the forwards link is done by the caller.
 	 */
-	WRITE_ONCE(cpu_spin_node(next)->prev, prev);
+	WRITE_ONCE(cpu_spin_node(prev)->next, next);
 
-	return next;
+	return prev;
 }
 
 bool osq_lock(struct optimistic_spin_queue *lock)
 {
-	struct optimistic_spin_node *node, *prev_ptr;
+	struct optimistic_spin_node *node, *next_ptr;
 	unsigned int curr = smp_processor_id() + 1;
-	unsigned int next, prev;
+	unsigned int prev, next;
 
 	/*
 	 * We need both ACQUIRE (pairs with corresponding RELEASE in
 	 * unlock() uncontended, or fastpath) and RELEASE (to publish
 	 * the node fields we just initialised) semantics when updating
-	 * the lock tail.
+	 * the lock head.
 	 */
-	prev = xchg(&lock->tail, curr);
-	if (prev == OSQ_UNLOCKED_VAL)
+	next = xchg(&lock->head, curr);
+	if (next == OSQ_UNLOCKED_VAL)
 		return true;
 
 	node = this_cpu_ptr(&osq_node);
-	prev_ptr = cpu_spin_node(prev);
-	node->prev = prev;
+	next_ptr = cpu_spin_node(next);
+	node->next = next;
 
 	/*
 	 * osq_lock()			unqueue
 	 *
-	 * node->prev = prev		osq_unlink_from_next()
+	 * node->next = next		osq_unlink_from_prev()
 	 * WMB				MB
-	 * prev->next = node		next->prev = prev // unqueue-C
+	 * next->prev = node		prev->next = next // unqueue-C
 	 *
-	 * Here 'node->prev' and 'next->prev' are the same variable and we need
+	 * Here 'node->next' and 'prev->next' are the same variable and we need
 	 * to ensure these stores happen in-order to avoid corrupting the list.
 	 */
 	smp_wmb();
 
-	WRITE_ONCE(prev_ptr->next, curr);
+	WRITE_ONCE(next_ptr->prev, curr);
 
 	/*
-	 * Normally @prev is untouchable after the above store; because at that
+	 * Normally @next is untouchable after the above store; because at that
 	 * moment unlock can proceed and wipe the node element from stack.
 	 *
 	 * However, since our nodes are static per-cpu storage, we're
@@ -163,31 +162,31 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	 * is implemented with a monitor-wait. vcpu_is_preempted() relies on
 	 * polling, be careful.
 	 */
-	prev = smp_cond_load_relaxed(&node->prev, !VAL || need_resched() ||
+	next = smp_cond_load_relaxed(&node->next, !VAL || need_resched() ||
 				     vcpu_is_preempted(VAL - 1));
 
 	/*
-	 * Loop until either node->prev is zero (lock acquired) or we
-	 * atomically change prev->next from node to NULL (stopping prev
+	 * Loop until either node->next is zero (lock acquired) or we
+	 * atomically change next->prev from node to NULL (stopping next
 	 * handing on the lock).
-	 * Note that 'prev' can unlink itself concurrently with this
-	 * test so that prev/prev_ptr can be stale, but since it
+	 * Note that 'next' can unlink itself concurrently with this
+	 * test so that next/next_ptr can be stale, but since it
 	 * is per-cpu data the memory can always be read.
 	 */
 
-	for (;; prev = READ_ONCE(node->prev)) {
-		if (!prev)
+	for (;; next = READ_ONCE(node->next)) {
+		if (!next)
 			/* Lock acquired */
 			return true;
 
-		prev_ptr = cpu_spin_node(prev);
+		next_ptr = cpu_spin_node(next);
 
-		if (data_race(prev_ptr->next) == curr &&
-		    cmpxchg(&prev_ptr->next, curr, 0) == curr)
+		if (data_race(next_ptr->prev) == curr &&
+		    cmpxchg(&next_ptr->prev, curr, 0) == curr)
 			break;
 
 		/*
-		 * 'prev' must have unlinked (or be in the process of unlinking)
+		 * 'next' must have unlinked (or be in the process of unlinking)
 		 * itself from the list.
 		 */
 
@@ -195,47 +194,47 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	}
 
 	/*
-	 * If 'prev' tries to remove itself from the list before we write
-	 * a new value to prev->next it will spin in osq_unlink_from_next().
+	 * If 'next' tries to remove itself from the list before we write
+	 * a new value to next->prev it will spin in osq_unlink_from_prev().
 	 * This means we can no longer be given the lock and always
 	 * return false.
 	 */
 
 	/*
-	 * Invalidate prev matching osq_unlock().
+	 * Invalidate next matching osq_unlock().
 	 * This isn't necessary but ensures that both unlocked and fast-path
-	 * locked nodes (where the initial xchg() returned 0) have prev set
+	 * locked nodes (where the initial xchg() returned 0) have next set
 	 * to zero.
-	 * If nothing else it lets the lock chain be followed from lock->tail
+	 * If nothing else it lets the lock chain be followed from lock->head
 	 * whch may help diagnostics.
 	 */
-	node->prev = 0;
+	node->next = 0;
 
 	/*
-	 * Now that the linkage to prev cannot change underneath us
-	 * remove ourselves from the node->prev list.
+	 * Now that the linkage to next cannot change underneath us
+	 * remove ourselves from the node->next list.
 	 * This does:
-	 * (node->next ? node->next->prev : lock->tail) = node->prev
+	 * (node->prev ? node->prev->next : lock->head) = node->next
 	 */
-	next = osq_unlink_from_next(lock, prev);
+	prev = osq_unlink_from_prev(lock, next);
 
 	/*
-	 * Finally mend the node->next list that was 'broken' to
-	 * stop node->prev trying to unlink from us.
-	 * If next is NULL then lock->tail is prev_ptr and another node
+	 * Finally mend the node->prev list that was 'broken' to
+	 * stop node->next trying to unlink from us.
+	 * If prev is NULL then lock->head is next_ptr and another node
 	 * can be added - so we must not re-write the NULL.
 	 */
-	if (next) {
+	if (prev) {
 		/*
-		 * This must happen after the write to node->next->prev.
-		 * If swapped then prev could unlink itself before our
-		 * write to node->next->prev and the the wrong value would
-		 * end up in node->next->prev.
+		 * This must happen after the write to node->prev->next.
+		 * If swapped then next could unlink itself before our
+		 * write to node->prev->next and the the wrong value would
+		 * end up in node->prev->next.
 		 * Probably can't actually happen due to re-ordering of writes,
 		 * but could happen without a compiler barrier.
 		 */
 		smp_wmb();
-		WRITE_ONCE(prev_ptr->next, next);
+		WRITE_ONCE(next_ptr->prev, prev);
 	}
 
 	return false;
@@ -243,5 +242,5 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 
 void osq_unlock(struct optimistic_spin_queue *lock)
 {
-	osq_unlink_from_next(lock, OSQ_UNLOCKED_VAL);
+	osq_unlink_from_prev(lock, OSQ_UNLOCKED_VAL);
 }
-- 
2.39.5

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[Linus Torvalds]

On Mon, 7 Sept 2026 at 01:41, David Laight <david.laight.linux@gmail.com> wrote:
>
> I've fixed some broken/missing memory barriers but left the initial xchg()
> when acquiring the lock as a full barrier, I think it could be relaxed.

Well, it should almost certainly be at least an
atomic_cmpxchg_acquire(), since that's what osq_wait_next() uses for
the contention case.

It's a bit odd that the first initial xchg uses a different memory
ordering than the later one. Maybe there's some reason for it.

But even more importantly, that code right now  explicitly *states*
that it needs a full barrier ("We need both ACQUIRE [..] and
RELEASE"), so that *comment* would also have to be fixed with a why
the ordering isn't as important as it states.

And finally: none of that will ever be noticeable on x86, since there
are no memory orderings on atomics there: lock is all-or-nothing.

End result: I'd love to see actual performance numbers if they exist.
And any memory ordering change would require explaining why it's ok
and some other architecture to test it.

Or am I missing something?

            Linus

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[David Laight]

On Mon, 7 Sep 2026 09:08:28 -0700
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Mon, 7 Sept 2026 at 01:41, David Laight <david.laight.linux@gmail.com> wrote:
> >
> > I've fixed some broken/missing memory barriers but left the initial xchg()
> > when acquiring the lock as a full barrier, I think it could be relaxed.  
> 
> Well, it should almost certainly be at least an
> atomic_cmpxchg_acquire(), since that's what osq_wait_next() uses for
> the contention case.

I'm not sure, but am no expert on acquire/release barriers.
The 'fast path' osq_lock() code only has one memory access so there
isn't anything to sequence it with.
The important one is the smp_wmb() a bit lower down that ensures the
list tail (or head) is written before the back link.
When that was missing things went badly wrong.
(I think the WRITE_ONCE() could be a store_release() instead.)

The ACQUIRE semantics were added to ensure the 'node->next = NULL'
assignment happened before the xchg().
That assignment goes away in patch 5.
But I'd want someone who really understands arm64 to comment.

> 
> It's a bit odd that the first initial xchg uses a different memory
> ordering than the later one. Maybe there's some reason for it.

I think the 'entry' ones want to be acquire and the 'exit' ones release.
osq_unlock() used release, but the equivalent code in osq_wait_next()
used acquire.
They can't both have been correct!

> 
> But even more importantly, that code right now  explicitly *states*
> that it needs a full barrier ("We need both ACQUIRE [..] and
> RELEASE"), so that *comment* would also have to be fixed with a why
> the ordering isn't as important as it states.

I left that comment alone - matching the xchg().
Even though there are now no fields to publish.

> And finally: none of that will ever be noticeable on x86, since there
> are no memory orderings on atomics there: lock is all-or-nothing.

Indeed.
I don't have a little arm test system, never mind a big one where this
would all show up.

> End result: I'd love to see actual performance numbers if they exist.
> And any memory ordering change would require explaining why it's ok
> and some other architecture to test it.

This could even be one of the strange places where making the code
slower actually speeds things up overall.
osq_lock() is only used for contended sleep locks, and then not even for
the first thread to be waiting.
If you get a lot of threads queued you really need to fix the locking!

> 
> Or am I missing something?

Probably the same thing as I am....

David

> 
>             Linus

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[Haakon Bugge]

> On 7 Sep 2026, at 19:27, David Laight <david.laight.linux@gmail.com> wrote:
> 
> On Mon, 7 Sep 2026 09:08:28 -0700
> Linus Torvalds <torvalds@linux-foundation.org> wrote:
> 
>> On Mon, 7 Sept 2026 at 01:41, David Laight <david.laight.linux@gmail.com> wrote:
>>> 
>>> I've fixed some broken/missing memory barriers but left the initial xchg()
>>> when acquiring the lock as a full barrier, I think it could be relaxed.  
>> 
>> Well, it should almost certainly be at least an
>> atomic_cmpxchg_acquire(), since that's what osq_wait_next() uses for
>> the contention case.
> 
> I'm not sure, but am no expert on acquire/release barriers.
> The 'fast path' osq_lock() code only has one memory access so there
> isn't anything to sequence it with.
> The important one is the smp_wmb() a bit lower down that ensures the
> list tail (or head) is written before the back link.
> When that was missing things went badly wrong.
> (I think the WRITE_ONCE() could be a store_release() instead.)
> 
> The ACQUIRE semantics were added to ensure the 'node->next = NULL'
> assignment happened before the xchg().
> That assignment goes away in patch 5.
> But I'd want someone who really understands arm64 to comment.

These are preliminary results. I added osq_lock's to my
mutual-exclusion selftest [1], which has not yet been reviewed. The
test is based on v7.3-rc2.

For lock acquisition, I used:

	preempt_disable();
	while (!osq_lock(&el->mx_osq_lock.lock)) {
		preempt_enable();
		cond_resched();
		preempt_disable();
	}

with the corresponding release:

	osq_unlock(&el->mx_osq_lock.lock);
	preempt_enable();

Assuming that this is a correct use of the OSQ API, the OSQ test fails
on a 160-CPU bare-metal Arm system. The same test passes on a 512-CPU
AMD x86_64 system as expected, showing at least that the test is
capable of passing.

I then applied this series, but the OSQ test still failed in the same
way on Arm. I observed no new mutex or rwsem test failures on Arm, and
the test continued to pass on the x86_64 system.


Thxs, Håkon

[1] https://lore.kernel.org/lkml/20260817130239.343594-1-haakon.bugge@oracle.com/


> 
>> 
>> It's a bit odd that the first initial xchg uses a different memory
>> ordering than the later one. Maybe there's some reason for it.
> 
> I think the 'entry' ones want to be acquire and the 'exit' ones release.
> osq_unlock() used release, but the equivalent code in osq_wait_next()
> used acquire.
> They can't both have been correct!
> 
>> 
>> But even more importantly, that code right now  explicitly *states*
>> that it needs a full barrier ("We need both ACQUIRE [..] and
>> RELEASE"), so that *comment* would also have to be fixed with a why
>> the ordering isn't as important as it states.
> 
> I left that comment alone - matching the xchg().
> Even though there are now no fields to publish.
> 
>> And finally: none of that will ever be noticeable on x86, since there
>> are no memory orderings on atomics there: lock is all-or-nothing.
> 
> Indeed.
> I don't have a little arm test system, never mind a big one where this
> would all show up.
> 
>> End result: I'd love to see actual performance numbers if they exist.
>> And any memory ordering change would require explaining why it's ok
>> and some other architecture to test it.
> 
> This could even be one of the strange places where making the code
> slower actually speeds things up overall.
> osq_lock() is only used for contended sleep locks, and then not even for
> the first thread to be waiting.
> If you get a lot of threads queued you really need to fix the locking!
> 
>> 
>> Or am I missing something?
> 
> Probably the same thing as I am....
> 
> David
> 
>> 
>>            Linus

Re: [PATCH v4 next 1/9] locking/osq_lock: Add some comments about how it works

[Waiman Long]

On 9/7/26 4:41 AM, David Laight wrote:
> No code changes, just some extra explanations.
>
> Signed-off-by: David Laight <david.laight.linux@gmail.com>
> ---
>   kernel/locking/osq_lock.c | 27 ++++++++++++++++++++++++---
>   1 file changed, 24 insertions(+), 3 deletions(-)
>
> diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
> index b4233dc2c2b0..b17aa704c449 100644
> --- a/kernel/locking/osq_lock.c
> +++ b/kernel/locking/osq_lock.c
> @@ -4,12 +4,33 @@
>   #include <linux/osq_lock.h>
>   
>   /*
> - * An MCS like lock especially tailored for optimistic spinning for sleeping
> - * lock implementations (mutex, rwsem, etc).
> + * An MCS like spin lock especially tailored for optimistic spinning for
> + * sleeping lock implementations (mutex, rwsem, etc).
> + * Each CPU spins on a local variable to avoid cache-line bounces.
>    *
> - * Using a single mcs node per CPU is safe because sleeping locks should not be
> + * The CPU that holds the osq_lock checks the mutex/rwsem, the other CPU spin
> + * in osq_lock() until either the osq_lock is obtained or the scheduler
> + * requests the process be preempted.
> + *
> + * Using a single osq node per CPU is safe because sleeping locks should not be
>    * called from interrupt context and we have preemption disabled while
>    * spinning.
> + *
> + * The osq_nodes for the spinning CPU are put on a double-linked (non circular)
> + * list. The list 'pointers' can either be the address of the osq_node or the
> + * associated CPU number, the CPU numbers are offset by one so that zero can
> + * be used like a NULL ponter.

Typo: "ponter" -> "pointer".

This description seems to describe the optimistic_spin_node structure 
after patch 2. So should you swap patch 1 and 2 to be more accurate?

Saying that 'pointers' can either be the osq_node address or the 
associated CPU numbers is a bit vague. next is the osq_node address and 
prev is the offset'ed CPU numbers. It is not really either one or the 
other. Other than that, the description looks good.

Cheers,
Longman

Re: [PATCH v4 next 2/9] locking/osq_lock: Save the cpu number for 'prev' not the node address

[Waiman Long]

On 9/7/26 4:41 AM, David Laight wrote:
> The cpu number of node->prev is needed for both the vcpu_is_preempted()
> test and to update lock->tail.
> This saves reading the cache line for the other cpu's per-cpu data.
>
> The cpu member of optimistic_spin_node is no longer needed.
>
> Merges patches 2 and 3 from v3.
>
> Signed-off-by: David Laight <david.laight.linux@gmail.com>
> ---
>   kernel/locking/osq_lock.c | 33 ++++++++++++++-------------------
>   1 file changed, 14 insertions(+), 19 deletions(-)
>
> diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
> index b17aa704c449..01988d00c480 100644
> --- a/kernel/locking/osq_lock.c
> +++ b/kernel/locking/osq_lock.c
> @@ -34,9 +34,9 @@
>    */
>   
>   struct optimistic_spin_node {
> -	struct optimistic_spin_node *next, *prev;
> +	struct optimistic_spin_node *next;
>   	int locked; /* 1 if lock acquired */
> -	int cpu; /* encoded CPU # + 1 value */
> +	int prev; /* CPU number offset by 1 */
>   };
>   
>   static DEFINE_PER_CPU_SHARED_ALIGNED(struct optimistic_spin_node, osq_node);
> @@ -50,11 +50,6 @@ static inline int encode_cpu(int cpu_nr)
>   	return cpu_nr + 1;
>   }
>   
> -static inline int node_cpu(struct optimistic_spin_node *node)
> -{
> -	return node->cpu - 1;
> -}
> -
>   static inline struct optimistic_spin_node *decode_cpu(int encoded_cpu_val)
>   {
>   	int cpu_nr = encoded_cpu_val - 1;
> @@ -114,13 +109,12 @@ osq_wait_next(struct optimistic_spin_queue *lock,
>   bool osq_lock(struct optimistic_spin_queue *lock)
>   {
>   	struct optimistic_spin_node *node = this_cpu_ptr(&osq_node);
> -	struct optimistic_spin_node *prev, *next;
> +	struct optimistic_spin_node *prev_ptr, *next;
>   	int curr = encode_cpu(smp_processor_id());
> -	int old;
> +	int prev;
>   
>   	node->locked = 0;
>   	node->next = NULL;
> -	node->cpu = curr;
>   
>   	/*
>   	 * We need both ACQUIRE (pairs with corresponding RELEASE in
> @@ -128,11 +122,11 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>   	 * the node fields we just initialised) semantics when updating
>   	 * the lock tail.
>   	 */
> -	old = atomic_xchg(&lock->tail, curr);
> -	if (old == OSQ_UNLOCKED_VAL)
> +	prev = atomic_xchg(&lock->tail, curr);
> +	if (prev == OSQ_UNLOCKED_VAL)
>   		return true;
>   
> -	prev = decode_cpu(old);
> +	prev_ptr = decode_cpu(prev);
>   	node->prev = prev;
>   
>   	/*
> @@ -147,7 +141,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>   	 */
>   	smp_wmb();
>   
> -	WRITE_ONCE(prev->next, node);
> +	WRITE_ONCE(prev_ptr->next, node);
>   
>   	/*
>   	 * Normally @prev is untouchable after the above store; because at that
> @@ -165,7 +159,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>   	 * polling, be careful.
>   	 */
>   	if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
> -				  vcpu_is_preempted(node_cpu(node->prev))))
> +				  vcpu_is_preempted(node->prev - 1)))
>   		return true;
>   
>   	/* unqueue */
> @@ -182,8 +176,8 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>   		 * cpu_relax() below implies a compiler barrier which would
>   		 * prevent this comparison being optimized away.
>   		 */
> -		if (data_race(prev->next) == node &&
> -		    cmpxchg(&prev->next, node, NULL) == node)
> +		if (data_race(prev_ptr->next) == node &&
> +		    cmpxchg(&prev_ptr->next, node, NULL) == node)
>   			break;
>   
>   		/*
> @@ -201,6 +195,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>   		 * case its step-C will write us a new @node->prev pointer.
>   		 */
>   		prev = READ_ONCE(node->prev);
> +		prev_ptr = decode_cpu(prev);
>   	}
>   
>   	/*
> @@ -210,7 +205,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>   	 * back to @prev.
>   	 */
>   
> -	next = osq_wait_next(lock, node, prev->cpu);
> +	next = osq_wait_next(lock, node, prev);
>   	if (!next)
>   		return false;
>   
> @@ -223,7 +218,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>   	 */
>   
>   	WRITE_ONCE(next->prev, prev);
> -	WRITE_ONCE(prev->next, next);
> +	WRITE_ONCE(prev_ptr->next, next);
>   
>   	return false;
>   }

LKTM

Reviewed-by: Waiman Long <longman@redhat.com>

Re: [PATCH v4 next 3/9] locking/osq_lock: Set prev_cpu=0 instead of locked=1

[Waiman Long]

On 9/7/26 4:41 AM, David Laight wrote:
> There is no need for separate prev_cpu and locked members of
> struct optimistic_spin_node.
> Using a single field simplifies the code slightly.
> It also removes any possibility of the two values being out of sync.
>
> When cancelling a lock request explicitly set prev_cpu to zero.
> Nothing actually looks at the field, but it means that it will be zero
> after a subsequent 'fast path' osq_lock() call making things consistent.
> The cache line is likely to be dirty (or be dirtied) so there shouldn't
> be a performance hit.
>
> Signed-off-by: David Laight <david.laight.linux@gmail.com>
> ---
>   kernel/locking/osq_lock.c | 57 +++++++++++++++++++--------------------
>   1 file changed, 28 insertions(+), 29 deletions(-)
>
> diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
> index 01988d00c480..23f00c670507 100644
> --- a/kernel/locking/osq_lock.c
> +++ b/kernel/locking/osq_lock.c
> @@ -35,7 +35,6 @@
>   
>   struct optimistic_spin_node {
>   	struct optimistic_spin_node *next;
> -	int locked; /* 1 if lock acquired */
>   	int prev; /* CPU number offset by 1 */
>   };
>   
I think we should document the fact that prev=0 can be viewed as a 
marker that the osq lock has been acquired.
> @@ -113,7 +112,6 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>   	int curr = encode_cpu(smp_processor_id());
>   	int prev;
>   
> -	node->locked = 0;
>   	node->next = NULL;
>   
>   	/*
> @@ -158,46 +156,47 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>   	 * is implemented with a monitor-wait. vcpu_is_preempted() relies on
>   	 * polling, be careful.
>   	 */
> -	if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
> -				  vcpu_is_preempted(node->prev - 1)))
> -		return true;
> +	prev = smp_cond_load_relaxed(&node->prev, !VAL || need_resched() ||
> +				     vcpu_is_preempted(VAL - 1));
>   
What is the purpose of assigning the return value to prev and 
immediately read node->prev into prev again in the next statement?
> -	/* unqueue */
>   	/*
> -	 * Step - A  -- stabilize @prev
> +	 * Step - A
>   	 *
> -	 * Undo our @prev->next assignment; this will make @prev's
> -	 * unlock()/unqueue() wait for a next pointer since @lock points to us
> -	 * (or later).
> +	 * Loop until either node->prev is zero (lock acquired) or we
> +	 * atomically change prev->next from node to NULL (stopping prev
> +	 * handing on the lock).
> +	 * Note that 'prev' can unlink itself concurrently with this
> +	 * test so that prev/prev_ptr can be stale, but since it
> +	 * is per-cpu data the memory can always be read.
I don't quite understand what you mean by "it is per-cpu data the memory 
can always be read".
>   	 */
>   
> -	for (;;) {
> -		/*
> -		 * cpu_relax() below implies a compiler barrier which would
> -		 * prevent this comparison being optimized away.
> -		 */
> +	for (;; prev = READ_ONCE(node->prev)) {
> +		if (!prev)
> +			/* Lock acquired */
> +			return true;
> +
> +		prev_ptr = decode_cpu(prev);
> +
>   		if (data_race(prev_ptr->next) == node &&
>   		    cmpxchg(&prev_ptr->next, node, NULL) == node)
>   			break;
>   
>   		/*
> -		 * We can only fail the cmpxchg() racing against an unlock(),
> -		 * in which case we should observe @node->locked becoming
> -		 * true.
> +		 * 'prev' must have unlinked (or be in the process of unlinking)
> +		 * itself from the list.

Should we also moved the deleted comment about cpu_relax() to here?

Cheers,
Longman

Re: [PATCH v4 next 3/9] locking/osq_lock: Set prev_cpu=0 instead of locked=1

[David Laight]

On Wed, 9 Sep 2026 14:01:59 -0400
Waiman Long <longman@redhat.com> wrote:

> On 9/7/26 4:41 AM, David Laight wrote:
> > There is no need for separate prev_cpu and locked members of
> > struct optimistic_spin_node.
> > Using a single field simplifies the code slightly.
> > It also removes any possibility of the two values being out of sync.
> >
> > When cancelling a lock request explicitly set prev_cpu to zero.
> > Nothing actually looks at the field, but it means that it will be zero
> > after a subsequent 'fast path' osq_lock() call making things consistent.
> > The cache line is likely to be dirty (or be dirtied) so there shouldn't
> > be a performance hit.
> >
> > Signed-off-by: David Laight <david.laight.linux@gmail.com>
> > ---
> >   kernel/locking/osq_lock.c | 57 +++++++++++++++++++--------------------
> >   1 file changed, 28 insertions(+), 29 deletions(-)
> >
> > diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
> > index 01988d00c480..23f00c670507 100644
> > --- a/kernel/locking/osq_lock.c
> > +++ b/kernel/locking/osq_lock.c
> > @@ -35,7 +35,6 @@
> >   
> >   struct optimistic_spin_node {
> >   	struct optimistic_spin_node *next;
> > -	int locked; /* 1 if lock acquired */
> >   	int prev; /* CPU number offset by 1 */
> >   };
> >     
> I think we should document the fact that prev=0 can be viewed as a 
> marker that the osq lock has been acquired.

I think that happens a bit later in the series.
Trying to keep the comments in step is quite hard work.
That is part the reason why patch 1 partially describes 'where we are
aiming at'.
I also got in a slight mess with pointers that are cpu numbers.
Mostly trying to keep the comments concise.

> > @@ -113,7 +112,6 @@ bool osq_lock(struct optimistic_spin_queue *lock)
> >   	int curr = encode_cpu(smp_processor_id());
> >   	int prev;
> >   
> > -	node->locked = 0;
> >   	node->next = NULL;
> >   
> >   	/*
> > @@ -158,46 +156,47 @@ bool osq_lock(struct optimistic_spin_queue *lock)
> >   	 * is implemented with a monitor-wait. vcpu_is_preempted() relies on
> >   	 * polling, be careful.
> >   	 */
> > -	if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
> > -				  vcpu_is_preempted(node->prev - 1)))
> > -		return true;
> > +	prev = smp_cond_load_relaxed(&node->prev, !VAL || need_resched() ||
> > +				     vcpu_is_preempted(VAL - 1));
> >     
> What is the purpose of assigning the return value to prev and 
> immediately read node->prev into prev again in the next statement?

It isn't, it is only re-read when the code goes around the loop.

> > -	/* unqueue */
> >   	/*
> > -	 * Step - A  -- stabilize @prev
> > +	 * Step - A
> >   	 *
> > -	 * Undo our @prev->next assignment; this will make @prev's
> > -	 * unlock()/unqueue() wait for a next pointer since @lock points to us
> > -	 * (or later).
> > +	 * Loop until either node->prev is zero (lock acquired) or we
> > +	 * atomically change prev->next from node to NULL (stopping prev
> > +	 * handing on the lock).
> > +	 * Note that 'prev' can unlink itself concurrently with this
> > +	 * test so that prev/prev_ptr can be stale, but since it
> > +	 * is per-cpu data the memory can always be read.  
> I don't quite understand what you mean by "it is per-cpu data the memory 
> can always be read".
> >   	 */
> >   
> > -	for (;;) {
> > -		/*
> > -		 * cpu_relax() below implies a compiler barrier which would
> > -		 * prevent this comparison being optimized away.
> > -		 */
> > +	for (;; prev = READ_ONCE(node->prev)) {
> > +		if (!prev)
> > +			/* Lock acquired */
> > +			return true;
> > +
> > +		prev_ptr = decode_cpu(prev);
> > +
> >   		if (data_race(prev_ptr->next) == node &&
> >   		    cmpxchg(&prev_ptr->next, node, NULL) == node)
> >   			break;
> >   
> >   		/*
> > -		 * We can only fail the cmpxchg() racing against an unlock(),
> > -		 * in which case we should observe @node->locked becoming
> > -		 * true.
> > +		 * 'prev' must have unlinked (or be in the process of unlinking)
> > +		 * itself from the list.  
> 
> Should we also moved the deleted comment about cpu_relax() to here?

I nearly gave that comment its own paragraph in the commit message.
It was added when the data_race() was added (because of a KASAN splat).
The real comment should have been that the initial compare is only
there to make it less likely that an expensive atomic operation fails.
The loop now has a READ_ONCE() at the top so nothing can be lifted out
of the loop.

Thinking about it, I'm not even sure the test is worth while.
If 'prev' isn't zero/NULL then we expect to be able to unlink ourselves
from it - so the cmpxchg() is expected to succeed.
The extra compare only makes sense when there is a reasonably likely hood
of the cmpxchg failing.

I could add a patch to remove it/them.

David

> 
> Cheers,
> Longman
> 

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[David Laight]

On Wed, 9 Sep 2026 14:15:03 +0000
Haakon Bugge <haakon.bugge@oracle.com> wrote:

> > On 7 Sep 2026, at 19:27, David Laight <david.laight.linux@gmail.com> wrote:
> > 
> > On Mon, 7 Sep 2026 09:08:28 -0700
> > Linus Torvalds <torvalds@linux-foundation.org> wrote:
> >   
> >> On Mon, 7 Sept 2026 at 01:41, David Laight <david.laight.linux@gmail.com> wrote:  
> >>> 
> >>> I've fixed some broken/missing memory barriers but left the initial xchg()
> >>> when acquiring the lock as a full barrier, I think it could be relaxed.    
> >> 
> >> Well, it should almost certainly be at least an
> >> atomic_cmpxchg_acquire(), since that's what osq_wait_next() uses for
> >> the contention case.  
> > 
> > I'm not sure, but am no expert on acquire/release barriers.
> > The 'fast path' osq_lock() code only has one memory access so there
> > isn't anything to sequence it with.
> > The important one is the smp_wmb() a bit lower down that ensures the
> > list tail (or head) is written before the back link.
> > When that was missing things went badly wrong.
> > (I think the WRITE_ONCE() could be a store_release() instead.)
> > 
> > The ACQUIRE semantics were added to ensure the 'node->next = NULL'
> > assignment happened before the xchg().
> > That assignment goes away in patch 5.
> > But I'd want someone who really understands arm64 to comment.  
> 
> These are preliminary results. I added osq_lock's to my
> mutual-exclusion selftest [1], which has not yet been reviewed. The
> test is based on v7.3-rc2.
> 
> For lock acquisition, I used:
> 
> 	preempt_disable();
> 	while (!osq_lock(&el->mx_osq_lock.lock)) {
> 		preempt_enable();
> 		cond_resched();
> 		preempt_disable();
> 	}
> 
> with the corresponding release:
> 
> 	osq_unlock(&el->mx_osq_lock.lock);
> 	preempt_enable();
> 
> Assuming that this is a correct use of the OSQ API,

Looks reasonable.
I doubt the rwsem code ever stresses it that much.

> the OSQ test fails on a 160-CPU bare-metal Arm system.

The inter-cpu delays will definitely show up any memory ordering issues.
I don't have access to anything of that nature.

> The same test passes on a 512-CPU
> AMD x86_64 system as expected, showing at least that the test is
> capable of passing.
> 
> I then applied this series, but the OSQ test still failed in the same
> way on Arm. I observed no new mutex or rwsem test failures on Arm, and
> the test continued to pass on the x86_64 system.

At least I haven't made it worse :-)
Might be worth removing all the _release and _acquire (so all the xchg
become full barriers) to see if that makes a difference.

For testing you want the option of compiling a separate copy of the lock
code into the module itself.
Then you can test changes to the lock code as well as changes to the
test itself.
I did that for mul_u64_add_u64_div_u64() so I could test the 32bit code
on x86-64.
It required some pretty horrid #defines - and I missed redefining
EXPORT_SYMBOL() to be a no-op.

David

> 
> 
> Thxs, Håkon
> 
> [1] https://lore.kernel.org/lkml/20260817130239.343594-1-haakon.bugge@oracle.com/
> 
> 
> >   
> >> 
> >> It's a bit odd that the first initial xchg uses a different memory
> >> ordering than the later one. Maybe there's some reason for it.  
> > 
> > I think the 'entry' ones want to be acquire and the 'exit' ones release.
> > osq_unlock() used release, but the equivalent code in osq_wait_next()
> > used acquire.
> > They can't both have been correct!
> >   
> >> 
> >> But even more importantly, that code right now  explicitly *states*
> >> that it needs a full barrier ("We need both ACQUIRE [..] and
> >> RELEASE"), so that *comment* would also have to be fixed with a why
> >> the ordering isn't as important as it states.  
> > 
> > I left that comment alone - matching the xchg().
> > Even though there are now no fields to publish.
> >   
> >> And finally: none of that will ever be noticeable on x86, since there
> >> are no memory orderings on atomics there: lock is all-or-nothing.  
> > 
> > Indeed.
> > I don't have a little arm test system, never mind a big one where this
> > would all show up.
> >   
> >> End result: I'd love to see actual performance numbers if they exist.
> >> And any memory ordering change would require explaining why it's ok
> >> and some other architecture to test it.  
> > 
> > This could even be one of the strange places where making the code
> > slower actually speeds things up overall.
> > osq_lock() is only used for contended sleep locks, and then not even for
> > the first thread to be waiting.
> > If you get a lot of threads queued you really need to fix the locking!
> >   
> >> 
> >> Or am I missing something?  
> > 
> > Probably the same thing as I am....
> > 
> > David
> >   
> >> 
> >>            Linus  
> 
> 

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[Waiman Long]

On 9/9/26 10:15 AM, Haakon Bugge wrote:
>
>> On 7 Sep 2026, at 19:27, David Laight <david.laight.linux@gmail.com> wrote:
>>
>> On Mon, 7 Sep 2026 09:08:28 -0700
>> Linus Torvalds <torvalds@linux-foundation.org> wrote:
>>
>>> On Mon, 7 Sept 2026 at 01:41, David Laight <david.laight.linux@gmail.com> wrote:
>>>> I've fixed some broken/missing memory barriers but left the initial xchg()
>>>> when acquiring the lock as a full barrier, I think it could be relaxed.
>>> Well, it should almost certainly be at least an
>>> atomic_cmpxchg_acquire(), since that's what osq_wait_next() uses for
>>> the contention case.
>> I'm not sure, but am no expert on acquire/release barriers.
>> The 'fast path' osq_lock() code only has one memory access so there
>> isn't anything to sequence it with.
>> The important one is the smp_wmb() a bit lower down that ensures the
>> list tail (or head) is written before the back link.
>> When that was missing things went badly wrong.
>> (I think the WRITE_ONCE() could be a store_release() instead.)
>>
>> The ACQUIRE semantics were added to ensure the 'node->next = NULL'
>> assignment happened before the xchg().
>> That assignment goes away in patch 5.
>> But I'd want someone who really understands arm64 to comment.
> These are preliminary results. I added osq_lock's to my
> mutual-exclusion selftest [1], which has not yet been reviewed. The
> test is based on v7.3-rc2.
>
> For lock acquisition, I used:
>
> 	preempt_disable();
> 	while (!osq_lock(&el->mx_osq_lock.lock)) {
> 		preempt_enable();
> 		cond_resched();
> 		preempt_disable();
> 	}
>
> with the corresponding release:
>
> 	osq_unlock(&el->mx_osq_lock.lock);
> 	preempt_enable();
>
> Assuming that this is a correct use of the OSQ API, the OSQ test fails
> on a 160-CPU bare-metal Arm system. The same test passes on a 512-CPU
> AMD x86_64 system as expected, showing at least that the test is
> capable of passing.

osq_unlock() must provide the release barrier. I think the two 
"WRITE_ONCE(next->locked, 1)" should have been 
"smp_store_release(&next->locked, 1)".  There is an xchg() call before 
the WRITE_ONCE's, but it is on a different cacheline so it may not apply.

Could you make that change to the existing code and rerun the test again 
on arm64 to see if it can pass?

Thanks,
Longman

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[Waiman Long]

On 9/9/26 4:14 PM, Waiman Long wrote:
> On 9/9/26 10:15 AM, Haakon Bugge wrote:
>>
>>> On 7 Sep 2026, at 19:27, David Laight <david.laight.linux@gmail.com> 
>>> wrote:
>>>
>>> On Mon, 7 Sep 2026 09:08:28 -0700
>>> Linus Torvalds <torvalds@linux-foundation.org> wrote:
>>>
>>>> On Mon, 7 Sept 2026 at 01:41, David Laight 
>>>> <david.laight.linux@gmail.com> wrote:
>>>>> I've fixed some broken/missing memory barriers but left the 
>>>>> initial xchg()
>>>>> when acquiring the lock as a full barrier, I think it could be 
>>>>> relaxed.
>>>> Well, it should almost certainly be at least an
>>>> atomic_cmpxchg_acquire(), since that's what osq_wait_next() uses for
>>>> the contention case.
>>> I'm not sure, but am no expert on acquire/release barriers.
>>> The 'fast path' osq_lock() code only has one memory access so there
>>> isn't anything to sequence it with.
>>> The important one is the smp_wmb() a bit lower down that ensures the
>>> list tail (or head) is written before the back link.
>>> When that was missing things went badly wrong.
>>> (I think the WRITE_ONCE() could be a store_release() instead.)
>>>
>>> The ACQUIRE semantics were added to ensure the 'node->next = NULL'
>>> assignment happened before the xchg().
>>> That assignment goes away in patch 5.
>>> But I'd want someone who really understands arm64 to comment.
>> These are preliminary results. I added osq_lock's to my
>> mutual-exclusion selftest [1], which has not yet been reviewed. The
>> test is based on v7.3-rc2.
>>
>> For lock acquisition, I used:
>>
>>     preempt_disable();
>>     while (!osq_lock(&el->mx_osq_lock.lock)) {
>>         preempt_enable();
>>         cond_resched();
>>         preempt_disable();
>>     }
>>
>> with the corresponding release:
>>
>>     osq_unlock(&el->mx_osq_lock.lock);
>>     preempt_enable();
>>
>> Assuming that this is a correct use of the OSQ API, the OSQ test fails
>> on a 160-CPU bare-metal Arm system. The same test passes on a 512-CPU
>> AMD x86_64 system as expected, showing at least that the test is
>> capable of passing.
>
> osq_unlock() must provide the release barrier. I think the two 
> "WRITE_ONCE(next->locked, 1)" should have been 
> "smp_store_release(&next->locked, 1)".  There is an xchg() call before 
> the WRITE_ONCE's, but it is on a different cacheline so it may not apply.
>
> Could you make that change to the existing code and rerun the test 
> again on arm64 to see if it can pass? 

osq_lock/unlock() is special in the sense that lock transfer can happen 
either in the lock cacheline or the node->locked cacheline. Try the 
patch below to see if it helps to pass the test.

Thanks,
Longman

diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
index b4233dc2c2b0..51cecf297692 100644
--- a/kernel/locking/osq_lock.c
+++ b/kernel/locking/osq_lock.c
@@ -143,7 +143,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
          * is implemented with a monitor-wait. vcpu_is_preempted() 
relies on
          * polling, be careful.
          */
-       if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
+       if (smp_cond_load_acquire(&node->locked, VAL || need_resched() ||
vcpu_is_preempted(node_cpu(node->prev))))
                 return true;

@@ -224,11 +224,11 @@ void osq_unlock(struct optimistic_spin_queue *lock)
         node = this_cpu_ptr(&osq_node);
         next = xchg(&node->next, NULL);
         if (next) {
-               WRITE_ONCE(next->locked, 1);
+               smp_store_release(&next->locked, 1);
                 return;
         }

         next = osq_wait_next(lock, node, OSQ_UNLOCKED_VAL);
         if (next)
-               WRITE_ONCE(next->locked, 1);
+               smp_store_release(&next->locked, 1);
  }

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[Haakon Bugge]

> On 9 Sep 2026, at 22:33, Waiman Long <longman@redhat.com> wrote:

[snip]

> > Could you make that change to the existing code and rerun the test 
> > again on arm64 to see if it can pass? 
> 
> osq_lock/unlock() is special in the sense that lock transfer can happen 
> either in the lock cacheline or the node->locked cacheline. Try the 
> patch below to see if it helps to pass the test.
> 
> Thanks,
> Longman
> 
> diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
> index b4233dc2c2b0..51cecf297692 100644
> --- a/kernel/locking/osq_lock.c
> +++ b/kernel/locking/osq_lock.c
> @@ -143,7 +143,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>          * is implemented with a monitor-wait. vcpu_is_preempted() 
> relies on
>          * polling, be careful.
>          */
> -       if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
> +       if (smp_cond_load_acquire(&node->locked, VAL || need_resched() ||
> vcpu_is_preempted(node_cpu(node->prev))))
>                 return true;
> 
> @@ -224,11 +224,11 @@ void osq_unlock(struct optimistic_spin_queue *lock)
>         node = this_cpu_ptr(&osq_node);
>         next = xchg(&node->next, NULL);
>         if (next) {
> -               WRITE_ONCE(next->locked, 1);
> +               smp_store_release(&next->locked, 1);
>                 return;
>         }
> 
>         next = osq_wait_next(lock, node, OSQ_UNLOCKED_VAL);
>         if (next)
> -               WRITE_ONCE(next->locked, 1);
> +               smp_store_release(&next->locked, 1);
>  }

The test passes with the above patch:

# dmesg|grep mx
[    7.010502] mx_test: osq_lock                    padding:  8 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
[   12.014144] mx_test: osq_lock                    padding: 16 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
[   17.017572] mx_test: osq_lock                    padding: 24 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
[   22.019636] mx_test: osq_lock                    padding: 32 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
[   27.022192] mx_test: osq_lock                    padding: 40 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
[   32.024907] mx_test: osq_lock                    padding: 48 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
[   37.026035] mx_test: osq_lock                    padding: 56 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds

I'll use David's advise about including the osq_lock code in my test,
so I can test it as a module, which will be more thorough.

If you submit this patch, feel free to add:

Tested-by: Håkon Bugge <haakon.bugge@oracle.com>


Thxs, Håkon

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[David Laight]

On Thu, 10 Sep 2026 09:45:47 +0000
Haakon Bugge <haakon.bugge@oracle.com> wrote:

> > On 9 Sep 2026, at 22:33, Waiman Long <longman@redhat.com> wrote:  
> 
> [snip]
> 
> > > Could you make that change to the existing code and rerun the test 
> > > again on arm64 to see if it can pass?   
> > 
> > osq_lock/unlock() is special in the sense that lock transfer can happen 
> > either in the lock cacheline or the node->locked cacheline. Try the 
> > patch below to see if it helps to pass the test.
> > 
> > Thanks,
> > Longman
> > 
> > diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
> > index b4233dc2c2b0..51cecf297692 100644
> > --- a/kernel/locking/osq_lock.c
> > +++ b/kernel/locking/osq_lock.c
> > @@ -143,7 +143,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
> >          * is implemented with a monitor-wait. vcpu_is_preempted() 
> > relies on
> >          * polling, be careful.
> >          */
> > -       if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
> > +       if (smp_cond_load_acquire(&node->locked, VAL || need_resched() ||
> > vcpu_is_preempted(node_cpu(node->prev))))
> >                 return true;
> > 
> > @@ -224,11 +224,11 @@ void osq_unlock(struct optimistic_spin_queue *lock)
> >         node = this_cpu_ptr(&osq_node);
> >         next = xchg(&node->next, NULL);
> >         if (next) {
> > -               WRITE_ONCE(next->locked, 1);
> > +               smp_store_release(&next->locked, 1);
> >                 return;
> >         }
> > 
> >         next = osq_wait_next(lock, node, OSQ_UNLOCKED_VAL);
> >         if (next)
> > -               WRITE_ONCE(next->locked, 1);
> > +               smp_store_release(&next->locked, 1);
> >  }  
> 
> The test passes with the above patch:

Do you know which part matters?

> 
> # dmesg|grep mx
> [    7.010502] mx_test: osq_lock                    padding:  8 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> [   12.014144] mx_test: osq_lock                    padding: 16 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> [   17.017572] mx_test: osq_lock                    padding: 24 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> [   22.019636] mx_test: osq_lock                    padding: 32 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> [   27.022192] mx_test: osq_lock                    padding: 40 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> [   32.024907] mx_test: osq_lock                    padding: 48 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> [   37.026035] mx_test: osq_lock                    padding: 56 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> 
> I'll use David's advise about including the osq_lock code in my test,
> so I can test it as a module, which will be more thorough.

At least with a build/run option...

> If you submit this patch, feel free to add:

I'll roll it into my patches (as 1/n).

David

> 
> Tested-by: Håkon Bugge <haakon.bugge@oracle.com>
> 
> 
> Thxs, Håkon
> 
> 

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[Haakon Bugge]

> On Thu, 10 Sep 2026 09:45:47 +0000
> Haakon Bugge <haakon.bugge@oracle.com> wrote:
> 
> > > On 9 Sep 2026, at 22:33, Waiman Long <longman@redhat.com> wrote:  
> > 
> > [snip]
> > 
> > > > Could you make that change to the existing code and rerun the test 
> > > > again on arm64 to see if it can pass?   
> > > 
> > > osq_lock/unlock() is special in the sense that lock transfer can happen 
> > > either in the lock cacheline or the node->locked cacheline. Try the 
> > > patch below to see if it helps to pass the test.
> > > 
> > > Thanks,
> > > Longman
> > > 
> > > diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
> > > index b4233dc2c2b0..51cecf297692 100644
> > > --- a/kernel/locking/osq_lock.c
> > > +++ b/kernel/locking/osq_lock.c
> > > @@ -143,7 +143,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
> > >          * is implemented with a monitor-wait. vcpu_is_preempted() 
> > > relies on
> > >          * polling, be careful.
> > >          */
> > > -       if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
> > > +       if (smp_cond_load_acquire(&node->locked, VAL || need_resched() ||
> > > vcpu_is_preempted(node_cpu(node->prev))))
> > >                 return true;
> > > 
> > > @@ -224,11 +224,11 @@ void osq_unlock(struct optimistic_spin_queue *lock)
> > >         node = this_cpu_ptr(&osq_node);
> > >         next = xchg(&node->next, NULL);
> > >         if (next) {
> > > -               WRITE_ONCE(next->locked, 1);
> > > +               smp_store_release(&next->locked, 1);
> > >                 return;
> > >         }
> > > 
> > >         next = osq_wait_next(lock, node, OSQ_UNLOCKED_VAL);
> > >         if (next)
> > > -               WRITE_ONCE(next->locked, 1);
> > > +               smp_store_release(&next->locked, 1);
> > >  }  
> > 
> > The test passes with the above patch:

Confirming that a much more thorough test (permutating the test array
size and padding) passed.

What concerns me is that I am unable to observe this bug testing
mutexes or rwlocks.

> Do you know which part matters?

No, but now that I am able to test the OSQ locks as a module, I'll
quickly find out.

> > # dmesg|grep mx
> > [    7.010502] mx_test: osq_lock                    padding:  8 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> > [   12.014144] mx_test: osq_lock                    padding: 16 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > [   17.017572] mx_test: osq_lock                    padding: 24 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > [   22.019636] mx_test: osq_lock                    padding: 32 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > [   27.022192] mx_test: osq_lock                    padding: 40 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> > [   32.024907] mx_test: osq_lock                    padding: 48 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > [   37.026035] mx_test: osq_lock                    padding: 56 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> > 
> > I'll use David's advise about including the osq_lock code in my test,
> > so I can test it as a module, which will be more thorough.
> 
> At least with a build/run option...

Yes, I'll send a v2 of my mx_test including OSQ locks both as
compiled-in and as a module. For the latter, I just did:

#include "osq_lock.c"

> > If you submit this patch, feel free to add:
> 
> I'll roll it into my patches (as 1/n).

Be aware that Waiman's patch did not apply on the top of your series,
so the testing is solely v7.3-rc2 plus Waiman's patch.


Thxs, Håkon

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[David Laight]

On Thu, 10 Sep 2026 11:31:19 +0000
Haakon Bugge <haakon.bugge@oracle.com> wrote:

> > On Thu, 10 Sep 2026 09:45:47 +0000
> > Haakon Bugge <haakon.bugge@oracle.com> wrote:
> >   
> > > > On 9 Sep 2026, at 22:33, Waiman Long <longman@redhat.com> wrote:    
> > > 
> > > [snip]
> > >   
> > > > > Could you make that change to the existing code and rerun the test 
> > > > > again on arm64 to see if it can pass?     
> > > > 
> > > > osq_lock/unlock() is special in the sense that lock transfer can happen 
> > > > either in the lock cacheline or the node->locked cacheline. Try the 
> > > > patch below to see if it helps to pass the test.
> > > > 
> > > > Thanks,
> > > > Longman
> > > > 
> > > > diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
> > > > index b4233dc2c2b0..51cecf297692 100644
> > > > --- a/kernel/locking/osq_lock.c
> > > > +++ b/kernel/locking/osq_lock.c
> > > > @@ -143,7 +143,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
> > > >          * is implemented with a monitor-wait. vcpu_is_preempted() 
> > > > relies on
> > > >          * polling, be careful.
> > > >          */
> > > > -       if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
> > > > +       if (smp_cond_load_acquire(&node->locked, VAL || need_resched() ||
> > > > vcpu_is_preempted(node_cpu(node->prev))))
> > > >                 return true;
> > > > 
> > > > @@ -224,11 +224,11 @@ void osq_unlock(struct optimistic_spin_queue *lock)
> > > >         node = this_cpu_ptr(&osq_node);
> > > >         next = xchg(&node->next, NULL);
> > > >         if (next) {
> > > > -               WRITE_ONCE(next->locked, 1);
> > > > +               smp_store_release(&next->locked, 1);
> > > >                 return;
> > > >         }
> > > > 
> > > >         next = osq_wait_next(lock, node, OSQ_UNLOCKED_VAL);
> > > >         if (next)
> > > > -               WRITE_ONCE(next->locked, 1);
> > > > +               smp_store_release(&next->locked, 1);
> > > >  }    
> > > 
> > > The test passes with the above patch:  
> 
> Confirming that a much more thorough test (permutating the test array
> size and padding) passed.
> 
> What concerns me is that I am unable to observe this bug testing
> mutexes or rwlocks.

The explicit test will be a lot more aggressive.
Especially if the lock hold time matters.

> 
> > Do you know which part matters?  
> 
> No, but now that I am able to test the OSQ locks as a module, I'll
> quickly find out.

That also means you can quickly check which _acquire/_release are definitely
required.
I'm pretty sure that (with my patches) the initial xchg() at the top of
osq_lock() only needs _acquire (_release was added to publish node->cpu).
But I think it doesn't even need _acquire.
osq_lock() itself relies on a data dependency.
Any concurrent osq_lock() relies on the smp_wmp() a bit further down
(I think that could be a store_release).

> 
> > > # dmesg|grep mx
> > > [    7.010502] mx_test: osq_lock                    padding:  8 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> > > [   12.014144] mx_test: osq_lock                    padding: 16 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > > [   17.017572] mx_test: osq_lock                    padding: 24 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > > [   22.019636] mx_test: osq_lock                    padding: 32 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > > [   27.022192] mx_test: osq_lock                    padding: 40 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> > > [   32.024907] mx_test: osq_lock                    padding: 48 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > > [   37.026035] mx_test: osq_lock                    padding: 56 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> > > 
> > > I'll use David's advise about including the osq_lock code in my test,
> > > so I can test it as a module, which will be more thorough.  
> > 
> > At least with a build/run option...  
> 
> Yes, I'll send a v2 of my mx_test including OSQ locks both as
> compiled-in and as a module. For the latter, I just did:
> 
> #include "osq_lock.c"

I tried to rename everything just to be certain the correct functions
are called.

> > > If you submit this patch, feel free to add:  
> > 
> > I'll roll it into my patches (as 1/n).  
> 
> Be aware that Waiman's patch did not apply on the top of your series,
> so the testing is solely v7.3-rc2 plus Waiman's patch.

The equivalent changes should be obvious.
Note that I merged the unlock and lock-fail paths.

David

> 
> 
> Thxs, Håkon
> 

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[Haakon Bugge]

> On 10 Sep 2026, at 14:05, David Laight <david.laight.linux@gmail.com> wrote:
> On Thu, 10 Sep 2026 11:31:19 +0000
> Haakon Bugge <haakon.bugge@oracle.com> wrote:
> 
> > > On Thu, 10 Sep 2026 09:45:47 +0000
> > > Haakon Bugge <haakon.bugge@oracle.com> wrote:
> > > 
> > > > > On 9 Sep 2026, at 22:33, Waiman Long <longman@redhat.com> wrote: 
> > > > 
> > > > [snip]
> > > > 
> > > > > > Could you make that change to the existing code and rerun the test 
> > > > > > again on arm64 to see if it can pass? 
> > > > > 
> > > > > osq_lock/unlock() is special in the sense that lock transfer can happen 
> > > > > either in the lock cacheline or the node->locked cacheline. Try the 
> > > > > patch below to see if it helps to pass the test.
> > > > > 
> > > > > Thanks,
> > > > > Longman
> > > > > 
> > > > > diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
> > > > > index b4233dc2c2b0..51cecf297692 100644
> > > > > --- a/kernel/locking/osq_lock.c
> > > > > +++ b/kernel/locking/osq_lock.c
> > > > > @@ -143,7 +143,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
> > > > > * is implemented with a monitor-wait. vcpu_is_preempted() 
> > > > > relies on
> > > > > * polling, be careful.
> > > > > */
> > > > > - if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
> > > > > + if (smp_cond_load_acquire(&node->locked, VAL || need_resched() ||
> > > > > vcpu_is_preempted(node_cpu(node->prev))))
> > > > > return true;
> > > > > 
> > > > > @@ -224,11 +224,11 @@ void osq_unlock(struct optimistic_spin_queue *lock)
> > > > > node = this_cpu_ptr(&osq_node);
> > > > > next = xchg(&node->next, NULL);
> > > > > if (next) {
> > > > > - WRITE_ONCE(next->locked, 1);
> > > > > + smp_store_release(&next->locked, 1);
> > > > > return;
> > > > > }
> > > > > 
> > > > > next = osq_wait_next(lock, node, OSQ_UNLOCKED_VAL);
> > > > > if (next)
> > > > > - WRITE_ONCE(next->locked, 1);
> > > > > + smp_store_release(&next->locked, 1);
> > > > > } 
> > > > 
> > > > The test passes with the above patch: 
> > 
> > Confirming that a much more thorough test (permutating the test array
> > size and padding) passed.
> > 
> > What concerns me is that I am unable to observe this bug testing
> > mutexes or rwlocks.
> 
> The explicit test will be a lot more aggressive.
> Especially if the lock hold time matters.

The algorithm is the same for all lock types. osq_lock failed, whereas mutex
and rwlock, based on osq_lock, passes. Weird.

> > > Do you know which part matters? 
> > 
> > No, but now that I am able to test the OSQ locks as a module, I'll
> > quickly find out.

Only the first hunk is allegedly required:

@@ -143,7 +143,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
         * is implemented with a monitor-wait. vcpu_is_preempted() relies on
         * polling, be careful.
         */
-       if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
+       if (smp_cond_load_acquire(&node->locked, VAL || need_resched() ||
	    vcpu_is_preempted(node_cpu(node->prev))))
                return true;

I say allegedly because a passing test doesn't prove anything, it just
gives a good indication that it is working.

> That also means you can quickly check which _acquire/_release are definitely
> required.

I did it in another way. I just added an "atomic_xchg" test to my
mutual exclusion framework.

Lock acquire:
                while (atomic_xchg_acquire(&el->mx_atomic_xchg.lock, 1) != 0)
                        cpu_relax();

Lock release:
                atomic_set_release(&el->mx_atomic_xchg.lock, 0);

This passes. It also (obviously) passes with atomic_xchg() in the lock
acquire. But the _release _is_ required in the lock release.

> I'm pretty sure that (with my patches) the initial xchg() at the top of
> osq_lock() only needs _acquire (_release was added to publish node->cpu).
> But I think it doesn't even need _acquire.

atomic_xchg_acquire() relaxes ordering as compared to
atomic_xchg(). So, atomic_xchg_acquire() in the top of osq_lock() and
atomic_try_cmpxchg_release() in osq_unlock() makes sense to me.

> osq_lock() itself relies on a data dependency.
> Any concurrent osq_lock() relies on the smp_wmp() a bit further down
> (I think that could be a store_release).
> 
> > 
> > > > # dmesg|grep mx
> > > > [ 7.010502] mx_test: osq_lock padding: 8 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> > > > [ 12.014144] mx_test: osq_lock padding: 16 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > > > [ 17.017572] mx_test: osq_lock padding: 24 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > > > [ 22.019636] mx_test: osq_lock padding: 32 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > > > [ 27.022192] mx_test: osq_lock padding: 40 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> > > > [ 32.024907] mx_test: osq_lock padding: 48 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.004 seconds
> > > > [ 37.026035] mx_test: osq_lock padding: 56 result: SUCCESS sum: 0 elements: 1000 elapsed: 5.000 seconds
> > > > 
> > > > I'll use David's advise about including the osq_lock code in my test,
> > > > so I can test it as a module, which will be more thorough. 
> > > 
> > > At least with a build/run option... 
> > 
> > Yes, I'll send a v2 of my mx_test including OSQ locks both as
> > compiled-in and as a module. For the latter, I just did:
> > 
> > #include "osq_lock.c"
> 
> I tried to rename everything just to be certain the correct functions
> are called.

I put in a WARN_ON_ONCE() and it fired :-)

> > > > If you submit this patch, feel free to add: 
> > > 
> > > I'll roll it into my patches (as 1/n). 
> > 
> > Be aware that Waiman's patch did not apply on the top of your series,
> > so the testing is solely v7.3-rc2 plus Waiman's patch.
> 
> The equivalent changes should be obvious.
> Note that I merged the unlock and lock-fail paths.

I like to change one thing at a time. FYI, I am unable to work on this
until Monday. I'll re-apply your series and Waiman's first hunk and
re-test.


Thxs, Håkon

Re: [PATCH v4 next 0/9] locking/osq_lock: Optimisations to osq_lock code

[Waiman Long]

On 9/10/26 11:30 AM, Haakon Bugge wrote:
>
>> On 10 Sep 2026, at 14:05, David Laight <david.laight.linux@gmail.com> wrote:
>> On Thu, 10 Sep 2026 11:31:19 +0000
>> Haakon Bugge <haakon.bugge@oracle.com> wrote:
>>
>>>> On Thu, 10 Sep 2026 09:45:47 +0000
>>>> Haakon Bugge <haakon.bugge@oracle.com> wrote:
>>>>
>>>>>> On 9 Sep 2026, at 22:33, Waiman Long <longman@redhat.com> wrote:
>>>>> [snip]
>>>>>
>>>>>>> Could you make that change to the existing code and rerun the test
>>>>>>> again on arm64 to see if it can pass?
>>>>>> osq_lock/unlock() is special in the sense that lock transfer can happen
>>>>>> either in the lock cacheline or the node->locked cacheline. Try the
>>>>>> patch below to see if it helps to pass the test.
>>>>>>
>>>>>> Thanks,
>>>>>> Longman
>>>>>>
>>>>>> diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
>>>>>> index b4233dc2c2b0..51cecf297692 100644
>>>>>> --- a/kernel/locking/osq_lock.c
>>>>>> +++ b/kernel/locking/osq_lock.c
>>>>>> @@ -143,7 +143,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>>>>>> * is implemented with a monitor-wait. vcpu_is_preempted()
>>>>>> relies on
>>>>>> * polling, be careful.
>>>>>> */
>>>>>> - if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
>>>>>> + if (smp_cond_load_acquire(&node->locked, VAL || need_resched() ||
>>>>>> vcpu_is_preempted(node_cpu(node->prev))))
>>>>>> return true;
>>>>>>
>>>>>> @@ -224,11 +224,11 @@ void osq_unlock(struct optimistic_spin_queue *lock)
>>>>>> node = this_cpu_ptr(&osq_node);
>>>>>> next = xchg(&node->next, NULL);
>>>>>> if (next) {
>>>>>> - WRITE_ONCE(next->locked, 1);
>>>>>> + smp_store_release(&next->locked, 1);
>>>>>> return;
>>>>>> }
>>>>>>
>>>>>> next = osq_wait_next(lock, node, OSQ_UNLOCKED_VAL);
>>>>>> if (next)
>>>>>> - WRITE_ONCE(next->locked, 1);
>>>>>> + smp_store_release(&next->locked, 1);
>>>>>> }
>>>>> The test passes with the above patch:
>>> Confirming that a much more thorough test (permutating the test array
>>> size and padding) passed.
>>>
>>> What concerns me is that I am unable to observe this bug testing
>>> mutexes or rwlocks.
>> The explicit test will be a lot more aggressive.
>> Especially if the lock hold time matters.
> The algorithm is the same for all lock types. osq_lock failed, whereas mutex
> and rwlock, based on osq_lock, passes. Weird.

The purpose of osq_lock is for queuing the lock waiters with minimal 
contention on the lock cacheline. Even when the locking semantics isn't 
fully correct, it won't have an ill effect on the locking behavior of 
rwsem and mutex.  We may have 2 waiters spinning on the lock cacheline 
instead of one, for instance.

>>>> Do you know which part matters?
>>> No, but now that I am able to test the OSQ locks as a module, I'll
>>> quickly find out.
> Only the first hunk is allegedly required:
>
> @@ -143,7 +143,7 @@ bool osq_lock(struct optimistic_spin_queue *lock)
>           * is implemented with a monitor-wait. vcpu_is_preempted() relies on
>           * polling, be careful.
>           */
> -       if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
> +       if (smp_cond_load_acquire(&node->locked, VAL || need_resched() ||
> 	    vcpu_is_preempted(node_cpu(node->prev))))
>                  return true;
>
> I say allegedly because a passing test doesn't prove anything, it just
> gives a good indication that it is working.

Yes, as said in my patch, the other two hunks are not really necessary 
for arm64 due to what how its barriers work.

Cheers,
Longman