[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@xxxxxxxxx>
---
 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