qspinlock with paravirt support

From: Waiman Long <[email protected]>

This patch introduces a new generic queue spinlock implementation that can serve as an alternative to the default ticket spinlock. Compared with the ticket spinlock, this queue spinlock should be almost as fair as the ticket spinlock. It has about the same speed in single-thread and it can be much faster in high contention situations especially when the spinlock is embedded within the data structure to be protected.

Only in light to moderate contention where the average queue depth is around 1-3 will this queue spinlock be potentially a bit slower due to the higher slowpath overhead.

This queue spinlock is especially suit to NUMA machines with a large number of cores as the chance of spinlock contention is much higher in those machines. The cost of contention is also higher because of slower inter-node memory traffic.

Due to the fact that spinlocks are acquired with preemption disabled, the process will not be migrated to another CPU while it is trying to get a spinlock. Ignoring interrupt handling, a CPU can only be contending in one spinlock at any one time. Counting soft IRQ, hard IRQ and NMI, a CPU can only have a maximum of 4 concurrent lock waiting activities. By allocating a set of per-cpu queue nodes and used them to form a waiting queue, we can encode the queue node address into a much smaller 24-bit size (including CPU number and queue node index) leaving one byte for the lock.

Please note that the queue node is only needed when waiting for the lock. Once the lock is acquired, the queue node can be released to be used later.

Signed-off-by Waiman Long <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

kernel/locking/mcs_spinlock.h +0 -0

 };
 
 #ifndef arch_mcs_spin_lock_contended

Index: linux-2.6/kernel/locking/qspinlock.c
===================================================================

kernel/locking/qspinlock.c new file +63 -0

@@ -0,0 +1,197 @@
+/*
+ * Queue spinlock
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * (C) Copyright 2013-2014 Hewlett-Packard Development Company, L.P.
+ *
+ * Authors: Waiman Long <[email protected]>
+ *          Peter Zijlstra <[email protected]>
+ */
+#include <linux/smp.h>
+#include <linux/bug.h>
+#include <linux/cpumask.h>
+#include <linux/percpu.h>
+#include <linux/hardirq.h>
+#include <linux/mutex.h>
+#include <asm/qspinlock.h>
+
+/*
+ * The basic principle of a queue-based spinlock can best be understood
+ * by studying a classic queue-based spinlock implementation called the
+ * MCS lock. The paper below provides a good description for this kind
+ * of lock.
+ *
+ * http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf
+ *
+ * This queue spinlock implementation is based on the MCS lock, however to make
+ * it fit the 4 bytes we assume spinlock_t to be, and preserve its existing
+ * API, we must modify it some.
+ *
+ * In particular; where the traditional MCS lock consists of a tail pointer
+ * (8 bytes) and needs the next pointer (another 8 bytes) of its own node to
+ * unlock the next pending (next->locked), we compress both these: {tail,
+ * next->locked} into a single u32 value.
+ *
+ * Since a spinlock disables recursion of its own context and there is a limit
+ * to the contexts that can nest; namely: task, softirq, hardirq, nmi, we can
+ * encode the tail as and index indicating this context and a cpu number.
+ *
+ * We can further change the first spinner to spin on a bit in the lock word
+ * instead of its node; whereby avoiding the need to carry a node from lock to
+ * unlock, and preserving API.
+ */
+
+#include "mcs_spinlock.h"
+
+/*
+ * Per-CPU queue node structures; we can never have more than 4 nested
+ * contexts: task, softirq, hardirq, nmi.
+ *
+ * Exactly fits one cacheline.
+ */
+static DEFINE_PER_CPU_ALIGNED(struct mcs_spinlock, mcs_nodes[4]);
+
+/*

kernel/locking/qspinlock.c new file +8 -0

+
+	return tail;
+}
+
+static inline struct mcs_spinlock *decode_tail(u32 tail)
+{
+	int cpu = (tail >> _Q_TAIL_CPU_OFFSET) - 1;
+	int idx = (tail &  _Q_TAIL_IDX_MASK) >> _Q_TAIL_IDX_OFFSET;

kernel/locking/qspinlock.c new file +33 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+
+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);
+	}
+
+	/*
+	 * we're at the head of the waitqueue, wait for the owner to go away.
+	 *
+	 * *,x -> *,0
+	 */
+	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
+		cpu_relax();
+

kernel/locking/qspinlock.c new file +13 -0

+		while (!(next = ACCESS_ONCE(node->next)))
+			cpu_relax();
+
+		arch_mcs_spin_unlock_contended(&next->locked);
+	}
+
+release:
+	/*
+	 * release the node
+	 */
+	this_cpu_dec(mcs_nodes[0].count);
+}
+EXPORT_SYMBOL(queue_spin_lock_slowpath);

Quoted 15 lines

kernel/locking/qspinlock.c new file +15 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+

kernel/locking/qspinlock.c line 152

Quoted 8 lines

kernel/locking/qspinlock.c new file +8 -0

+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);

Quoted 20 lines

kernel/locking/qspinlock.c new file +20 -0

+	}
+
+	/*
+	 * we're at the head of the waitqueue, wait for the owner to go away.
+	 *
+	 * *,x -> *,0
+	 */
+	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
+		cpu_relax();
+
+	/*
+	 * claim the lock:
+	 *
+	 * n,0 -> 0,1 : lock, uncontended
+	 * *,0 -> *,1 : lock, contended
+	 */
+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val != tail)
+			new |= val;

Could you help a bit in explaining it in English please?

Quoted 15 lines

Quoted 15 lines

kernel/locking/qspinlock.c new file +15 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+

Quoted 8 lines

kernel/locking/qspinlock.c line 152

Quoted 8 lines

kernel/locking/qspinlock.c new file +8 -0

+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);

Could you add a comment here:

/* We are spinning forever until the previous node updates locked - which it does once the it has updated lock->val with our tail number. */

Quoted 11 lines

Quoted 10 lines

kernel/locking/qspinlock.c new file +10 -0

+	/*
+	 * claim the lock:
+	 *
+	 * n,0 -> 0,1 : lock, uncontended
+	 * *,0 -> *,1 : lock, contended
+	 */
+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val != tail)
+			new |= val;

..snip..

Quoted 1 line

Quoted 1 line

Could you help a bit in explaining it in English please?

After looking at the assembler code I finally figured out how we can get here. And the 'contended' part threw me off. Somehow I imagined there are two more more CPUs stampeding here and trying to update the lock->val. But in reality the other CPUs are stuck in the arch_mcs_spin_lock_contended spinning on their local value.

Perhaps you could add this comment.

/* Once queue_spin_unlock is called (which _subtracts_ _Q_LOCKED_VAL from the lock->val and still preserving the tail data), the winner gets to claim the ticket.

Since we still need the other CPUs to continue and
preserve the strict ordering in which they setup node->next, we:
1) update lock->val to the tail value (so tail CPU and its index) with

    _Q_LOCKED_VAL.

2). Once we are done, we poke the other CPU (the one that linked to

    us) by writting to node->locked (below) so they can make progress and
    loop on lock->val changing from _Q_LOCKED_MASK to zero).

Quoted 26 lines · Konrad Rzeszutek Wilk

Quoted 15 lines

Quoted 15 lines

kernel/locking/qspinlock.c new file +15 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+

Quoted 8 lines

kernel/locking/qspinlock.c line 152

Quoted 8 lines

kernel/locking/qspinlock.c new file +8 -0

+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);

Could you add a comment here:

Quoted 2 lines

/* We are spinning forever until the previous node updates locked - which it does once the it has updated lock->val with our tail number. */

That's incorrect -- or at least, I understand that to be incorrect. The previous node will not have changed the tail to point to us. You always change to tail to point to yourself, seeing how you add yourself to the tail.

Is the existing comment any better if I s/wait./wait for it to release us./ ?

Quoted 14 lines

Quoted 12 lines

Quoted 11 lines

kernel/locking/qspinlock.c new file +10 -0

+	/*
+	 * claim the lock:
+	 *
+	 * n,0 -> 0,1 : lock, uncontended
+	 * *,0 -> *,1 : lock, contended
+	 */
+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val != tail)
+			new |= val;

..snip..

Quoted 1 line

Quoted 8 lines

Quoted 1 line

Could you help a bit in explaining it in English please?

After looking at the assembler code I finally figured out how we can get here. And the 'contended' part threw me off. Somehow I imagined there are two more more CPUs stampeding here and trying to update the lock->val. But in reality the other CPUs are stuck in the arch_mcs_spin_lock_contended spinning on their local value.

Well, the lock as a whole is contended (there's >1 waiters), and the point of MCS style locks it to make sure they're not actually pounding on the same cacheline. So the whole thing is consistent.

Quoted 5 lines

Perhaps you could add this comment.

/* Once queue_spin_unlock is called (which _subtracts_ _Q_LOCKED_VAL from the lock->val and still preserving the tail data), the winner gets to claim the ticket.

There's no tickets :/

Quoted 5 lines

Since we still need the other CPUs to continue and
preserve the strict ordering in which they setup node->next, we:
1) update lock->val to the tail value (so tail CPU and its index) with

    _Q_LOCKED_VAL.

We don't, we preserve the tail value, unless we're the tail, in which case we clear the tail.

Quoted 3 lines

2). Once we are done, we poke the other CPU (the one that linked to

    us) by writting to node->locked (below) so they can make progress and
    loop on lock->val changing from _Q_LOCKED_MASK to zero).

_If_ there was another cpu, ie. the tail didn't point to us.

---

I don't do well with natural language comments like that; they tend to confuse me more than anything.

Quoted 26 lines · Konrad Rzeszutek Wilk

Quoted 15 lines

Quoted 15 lines

kernel/locking/qspinlock.c new file +15 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+

Quoted 8 lines

kernel/locking/qspinlock.c line 152

Quoted 8 lines

kernel/locking/qspinlock.c new file +8 -0

+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);

Could you add a comment here:

Quoted 2 lines

/* We are spinning forever until the previous node updates locked - which it does once the it has updated lock->val with our tail number. */

That's incorrect -- or at least, I understand that to be incorrect. The previous node will not have changed the tail to point to us. You always change to tail to point to yourself, seeing how you add yourself to the tail.

Is the existing comment any better if I s/wait./wait for it to release us./ ?

Quoted 14 lines

Quoted 12 lines

Quoted 11 lines

kernel/locking/qspinlock.c new file +10 -0

+	/*
+	 * claim the lock:
+	 *
+	 * n,0 -> 0,1 : lock, uncontended
+	 * *,0 -> *,1 : lock, contended
+	 */
+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val != tail)
+			new |= val;

..snip..

Quoted 1 line

Quoted 8 lines

Quoted 1 line

Could you help a bit in explaining it in English please?

After looking at the assembler code I finally figured out how we can get here. And the 'contended' part threw me off. Somehow I imagined there are two more more CPUs stampeding here and trying to update the lock->val. But in reality the other CPUs are stuck in the arch_mcs_spin_lock_contended spinning on their local value.

Well, the lock as a whole is contended (there's >1 waiters), and the point of MCS style locks it to make sure they're not actually pounding on the same cacheline. So the whole thing is consistent.

Quoted 5 lines

Perhaps you could add this comment.

/* Once queue_spin_unlock is called (which _subtracts_ _Q_LOCKED_VAL from the lock->val and still preserving the tail data), the winner gets to claim the ticket.

There's no tickets :/

Quoted 5 lines

Since we still need the other CPUs to continue and
preserve the strict ordering in which they setup node->next, we:
1) update lock->val to the tail value (so tail CPU and its index) with

    _Q_LOCKED_VAL.

We don't, we preserve the tail value, unless we're the tail, in which case we clear the tail.

Quoted 3 lines

2). Once we are done, we poke the other CPU (the one that linked to

    us) by writting to node->locked (below) so they can make progress and
    loop on lock->val changing from _Q_LOCKED_MASK to zero).

_If_ there was another cpu, ie. the tail didn't point to us.

---

I don't do well with natural language comments like that; they tend to confuse me more than anything.

Quoted 15 lines

Quoted 15 lines

kernel/locking/qspinlock.c new file +15 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+

Quoted 8 lines

kernel/locking/qspinlock.c line 152

Quoted 8 lines

kernel/locking/qspinlock.c new file +8 -0

+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);

Could you add a comment here:

/* We are spinning forever until the previous node updates locked - which it does once the it has updated lock->val with our tail number. */

Quoted 11 lines

Quoted 10 lines

kernel/locking/qspinlock.c new file +10 -0

+	/*
+	 * claim the lock:
+	 *
+	 * n,0 -> 0,1 : lock, uncontended
+	 * *,0 -> *,1 : lock, contended
+	 */
+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val != tail)
+			new |= val;

..snip..

Quoted 1 line

Quoted 1 line

Could you help a bit in explaining it in English please?

After looking at the assembler code I finally figured out how we can get here. And the 'contended' part threw me off. Somehow I imagined there are two more more CPUs stampeding here and trying to update the lock->val. But in reality the other CPUs are stuck in the arch_mcs_spin_lock_contended spinning on their local value.

Perhaps you could add this comment.

/* Once queue_spin_unlock is called (which _subtracts_ _Q_LOCKED_VAL from the lock->val and still preserving the tail data), the winner gets to claim the ticket.

Since we still need the other CPUs to continue and
preserve the strict ordering in which they setup node->next, we:
1) update lock->val to the tail value (so tail CPU and its index) with

    _Q_LOCKED_VAL.

2). Once we are done, we poke the other CPU (the one that linked to

    us) by writting to node->locked (below) so they can make progress and
    loop on lock->val changing from _Q_LOCKED_MASK to zero).

Quoted 15 lines

kernel/locking/qspinlock.c new file +15 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+

kernel/locking/qspinlock.c line 152

Quoted 8 lines

kernel/locking/qspinlock.c new file +8 -0

+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);

Quoted 20 lines

kernel/locking/qspinlock.c new file +20 -0

+	}
+
+	/*
+	 * we're at the head of the waitqueue, wait for the owner to go away.
+	 *
+	 * *,x -> *,0
+	 */
+	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
+		cpu_relax();
+
+	/*
+	 * claim the lock:
+	 *
+	 * n,0 -> 0,1 : lock, uncontended
+	 * *,0 -> *,1 : lock, contended
+	 */
+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val != tail)
+			new |= val;

Could you help a bit in explaining it in English please?

kernel/locking/mcs_spinlock.h line 20

Quoted 9 lines

Index: linux-2.6/kernel/locking/mcs_spinlock.h
===================================================================

kernel/locking/mcs_spinlock.h +1 -0

@@ -17,6 +17,7 @@
 struct mcs_spinlock {
 	struct mcs_spinlock *next;
 	int locked; /* 1 if lock acquired */
+	int count;

This could use a comment.

kernel/locking/mcs_spinlock.h

Quoted 6 lines

kernel/locking/mcs_spinlock.h +6 -0

+static inline u32 encode_tail(int cpu, int idx)
+{
+	u32 tail;
+
+	tail  = (cpu + 1) << _Q_TAIL_CPU_OFFSET;
+	tail |= idx << _Q_TAIL_IDX_OFFSET; /* assume < 4 */

Should there an

ASSSERT (idx < 4)

just in case we screw up somehow (I can't figure out how, but that is partially why ASSERTS are added).

Quoted 6 lines

+/**
+ * queue_spin_lock_slowpath - acquire the queue spinlock
+ * @lock: Pointer to queue spinlock structure
+ * @val: Current value of the queue spinlock 32-bit word
+ *
+ * (queue tail, lock bit)

Except it is not a lock bit. It is a lock uint8_t.

Is the queue tail at this point the composite of 'cpu|idx'?

Quoted 7 lines

+ *

+ *              fast      :    slow                                  :    unlock
+ *                        :                                          :
+ * uncontended  (0,0)   --:--> (0,1) --------------------------------:--> (*,0)
+ *                        :       | ^--------.                    /  :
+ *                        :       v           \                   |  :
+ * uncontended            :    (n,x) --+--> (n,0)                 |  :

So many CPUn come in right? Is 'n' for the number of CPUs?

Quoted 4 lines

+ *   queue                :       | ^--'                          |  :
+ *                        :       v                               |  :
+ * contended              :    (*,x) --+--> (*,0) -----> (*,1) ---'  :
+ *   queue                :         ^--'                             :

And here um, what are the '*' for? Are they the four different types of handlers that can be nested? So task, sofitrq, hardisk, and nmi?

Quoted 5 lines

kernel/locking/mcs_spinlock.h +5 -0

+void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val)
+{
+	struct mcs_spinlock *prev, *next, *node;
+	u32 new, old, tail;
+	int idx;

kernel/locking/mcs_spinlock.h

Quoted 5 lines

kernel/locking/mcs_spinlock.h +5 -0

+
+	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
+
+	node = this_cpu_ptr(&mcs_nodes[0]);
+	idx = node->count++;

If this is the first time we enter this, wouldn't idx end up being 1?

kernel/locking/mcs_spinlock.h

Quoted 3 lines

kernel/locking/mcs_spinlock.h +3 -0

+	tail = encode_tail(smp_processor_id(), idx);
+
+	node += idx;

Meaning we end up skipping the 'mcs_nodes[0]' one altogether - even on the first 'level' (task, softirq, hardirq, nmi)? Won't that cause us to blow past the array when we are nested at the nmi handler?

kernel/locking/mcs_spinlock.h

Quoted 8 lines

kernel/locking/mcs_spinlock.h +8 -0

+	node->locked = 0;
+	node->next = NULL;
+
+	/*
+	 * trylock || xchg(lock, node)
+	 *
+	 * 0,0 -> 0,1 ; trylock
+	 * p,x -> n,x ; prev = xchg(lock, node)

I looked at that for 10 seconds and I was not sure what you meant. Is this related to the MCS document you had pointed to? It would help if you mention that the comments follow the document. (But they don't seem to)

I presume what you mean is that if we are the next after the lock-holder we need only to update the 'next' (or the composite value of smp_processor_idx | idx) to point to us.

As in, swap the 'L' with 'I' (looking at the doc)

kernel/locking/mcs_spinlock.h

Quoted 4 lines

kernel/locking/mcs_spinlock.h +4 -0

+	 */
+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val)

Could you add a comment here, like this:

/*
* N.B. Initially 'val' will have some value (as we are called
* after the _Q_LOCKED_VAL could not be set by queue_spin_lock).
* But on subsequent iterations, either the lock holder will
* decrement the val (queue_spin_unlock - to zero) and we
* needn't to record our status in the queue as we have set the
* Q_LOCKED_VAL (new) and are the lock holder. Or we are next
* in line and need to record our 'next' (aka, smp_processor_id() | idx)
* position. */
*/

Quoted 39 lines

kernel/locking/mcs_spinlock.h +39 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+
+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);
+	}
+
+	/*
+	 * we're at the head of the waitqueue, wait for the owner to go away.
+	 *
+	 * *,x -> *,0
+	 */
+	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
+		cpu_relax();
+
+	/*
+	 * claim the lock:
+	 *
+	 * n,0 -> 0,1 : lock, uncontended
+	 * *,0 -> *,1 : lock, contended
+	 */

kernel/locking/mcs_spinlock.h

Quoted 4 lines

kernel/locking/mcs_spinlock.h +4 -0

+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val != tail)
+			new |= val;

You lost me here. If we are at the head of the queue, and the owner has called queue_spin_unlock (hence made us get out of the 'val = atomic_read' loop, how can val != tail?

kernel/locking/mcs_spinlock.h

Quoted 1 line

kernel/locking/mcs_spinlock.h +1 -0

+	tail = encode_tail(smp_processor_id(), idx);

I suspect it has something to do with the comment, but I am still unsure what it means.

Could you help a bit in explaining it in English please?

kernel/locking/mcs_spinlock.h

Quoted 12 lines

kernel/locking/mcs_spinlock.h +12 -0

+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * contended path; wait for next, release.
+	 */
+	if (new != _Q_LOCKED_VAL) {

Hm, wouldn't it be just easier to do a 'goto restart' where restart label points at the first loop statement? Ah never mind - we have already inserted ourselves in the previous's node.

But that is confusing - we have done: "prev->next = node;"

And then exited out of 'val = atomic_read(&lock->val))' which suggests that queue_spin_unlock has called us. How can we be contended again?

Quoted 11 lines · Konrad Rzeszutek Wilk

kernel/locking/mcs_spinlock.h line 20

Quoted 9 lines

Index: linux-2.6/kernel/locking/mcs_spinlock.h
===================================================================

kernel/locking/mcs_spinlock.h +1 -0

@@ -17,6 +17,7 @@
 struct mcs_spinlock {
 	struct mcs_spinlock *next;
 	int locked; /* 1 if lock acquired */
+	int count;

This could use a comment.

like so?

int count; /* nesting count, see qspinlock.c */

Quoted 13 lines

kernel/locking/mcs_spinlock.h

Quoted 8 lines

kernel/locking/mcs_spinlock.h +6 -0

+static inline u32 encode_tail(int cpu, int idx)
+{
+	u32 tail;
+
+	tail  = (cpu + 1) << _Q_TAIL_CPU_OFFSET;
+	tail |= idx << _Q_TAIL_IDX_OFFSET; /* assume < 4 */

Should there an

ASSSERT (idx < 4)

Quoted 2 lines

just in case we screw up somehow (I can't figure out how, but that is partially why ASSERTS are added).

#ifdef CONFIG_DEBUG_SPINLOCK
	BUG_ON(idx > 3);

#endif

might do, I suppose.

Quoted 8 lines

Quoted 7 lines

+/**
+ * queue_spin_lock_slowpath - acquire the queue spinlock
+ * @lock: Pointer to queue spinlock structure
+ * @val: Current value of the queue spinlock 32-bit word
+ *
+ * (queue tail, lock bit)

Quoted 1 line

Except it is not a lock bit. It is a lock uint8_t.

It is indeed, although that's an accident of implementation. I could do s/bit// and not mention the entire storage angle at all?

Quoted 2 lines

Is the queue tail at this point the composite of 'cpu|idx'?

Yes, as per {en,de}code_tail() above.

Quoted 9 lines

Quoted 7 lines

+ *

+ *              fast      :    slow                                  :    unlock
+ *                        :                                          :
+ * uncontended  (0,0)   --:--> (0,1) --------------------------------:--> (*,0)
+ *                        :       | ^--------.                    /  :
+ *                        :       v           \                   |  :
+ * uncontended            :    (n,x) --+--> (n,0)                 |  :

So many CPUn come in right? Is 'n' for the number of CPUs?

Nope, 'n' for any one specific tail, in particular the first one to arrive. This is the 'uncontended queue' case as per the label, so we need a named value for the first, in order to distinguish between the state to the right (same tail, but unlocked) and the state below (different tail).

Quoted 5 lines

Quoted 4 lines

+ *   queue                :       | ^--'                          |  :
+ *                        :       v                               |  :
+ * contended              :    (*,x) --+--> (*,0) -----> (*,1) ---'  :
+ *   queue                :         ^--'                             :

Quoted 3 lines

And here um, what are the '*' for? Are they the four different types of handlers that can be nested? So task, sofitrq, hardisk, and nmi?

'*' as in wildcard, any tail, specifically not 'n'.

Quoted 14 lines

kernel/locking/mcs_spinlock.h

Quoted 11 lines

kernel/locking/mcs_spinlock.h +10 -0

+void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val)
+{
+	struct mcs_spinlock *prev, *next, *node;
+	u32 new, old, tail;
+	int idx;
+
+	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
+
+	node = this_cpu_ptr(&mcs_nodes[0]);
+	idx = node->count++;

If this is the first time we enter this, wouldn't idx end up being 1?

Nope, postfix ++ returns first and increments later.

Quoted 9 lines

kernel/locking/mcs_spinlock.h

Quoted 4 lines

kernel/locking/mcs_spinlock.h +3 -0

+	tail = encode_tail(smp_processor_id(), idx);
+
+	node += idx;

Meaning we end up skipping the 'mcs_nodes[0]' one altogether - even on the first 'level' (task, softirq, hardirq, nmi)? Won't that cause us to blow past the array when we are nested at the nmi handler?

Seeing how its all static storage, which is automagically initialized to 0, combined with the postfix ++ (as opposed to the prefix ++) we should be getting 0 here.

Quoted 15 lines

kernel/locking/mcs_spinlock.h

Quoted 9 lines

kernel/locking/mcs_spinlock.h +8 -0

+	node->locked = 0;
+	node->next = NULL;
+
+	/*
+	 * trylock || xchg(lock, node)
+	 *
+	 * 0,0 -> 0,1 ; trylock
+	 * p,x -> n,x ; prev = xchg(lock, node)

I looked at that for 10 seconds and I was not sure what you meant. Is this related to the MCS document you had pointed to? It would help if you mention that the comments follow the document. (But they don't seem to)

Quoted 5 lines

I presume what you mean is that if we are the next after the lock-holder we need only to update the 'next' (or the composite value of smp_processor_idx | idx) to point to us.

As in, swap the 'L' with 'I' (looking at the doc)

They are the 'tail','lock' tuples, so this composite atomic operation completes either:

0,0 -> 0,1 -- we had no tail, not locked; into: no tail, locked.

OR

p,x -> n,x -- tail was p; into: tail is n; preserving locked.

Quoted 8 lines

kernel/locking/mcs_spinlock.h

Quoted 5 lines

kernel/locking/mcs_spinlock.h +4 -0

+	 */
+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val)

Could you add a comment here, like this:

Quoted 10 lines

/*
* N.B. Initially 'val' will have some value (as we are called
* after the _Q_LOCKED_VAL could not be set by queue_spin_lock).
* But on subsequent iterations, either the lock holder will
* decrement the val (queue_spin_unlock - to zero) and we
* needn't to record our status in the queue as we have set the
* Q_LOCKED_VAL (new) and are the lock holder. Or we are next
* in line and need to record our 'next' (aka, smp_processor_id() | idx)
* position. */
*/

The idea was that:

0,0 -> 0,1
p,x -> n,x

Completely covers what this composite atomic does.

Quoted 39 lines

Quoted 39 lines

kernel/locking/mcs_spinlock.h +39 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+
+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);
+	}
+
+	/*
+	 * we're at the head of the waitqueue, wait for the owner to go away.
+	 *
+	 * *,x -> *,0
+	 */
+	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
+		cpu_relax();
+
+	/*
+	 * claim the lock:
+	 *
+	 * n,0 -> 0,1 : lock, uncontended
+	 * *,0 -> *,1 : lock, contended
+	 */

Quoted 8 lines

kernel/locking/mcs_spinlock.h

Quoted 4 lines

kernel/locking/mcs_spinlock.h +4 -0

+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val != tail)
+			new |= val;

You lost me here. If we are at the head of the queue, and the owner has called queue_spin_unlock (hence made us get out of the 'val = atomic_read' loop, how can val != tail?

Remember:

Quoted 1 line

kernel/locking/mcs_spinlock.h

Quoted 1 line

kernel/locking/mcs_spinlock.h +1 -0

+	tail = encode_tail(smp_processor_id(), idx);

So if value != tail, that means the tail pointer doesn't point to us anymore, another cpu/idx queued itself and is now last.

Quoted 4 lines

I suspect it has something to do with the comment, but I am still unsure what it means.

Could you help a bit in explaining it in English please?

(refer to the state diagram, if we count states left->right, top->bottom, then this is: 5->2 or 7->8

n,0 -> 0,1:

the lock is free and the tail points to the first queued; this means that unqueueing implies wiping the tail, at the same time, acquire the lock.

*,0 -> *,1:

the lock is free and the tail doesn't point to the first queued; this means that unqueueing doesn't touch the tail pointer but only sets the lock.

Quoted 20 lines

kernel/locking/mcs_spinlock.h

Quoted 12 lines

kernel/locking/mcs_spinlock.h +12 -0

+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * contended path; wait for next, release.
+	 */
+	if (new != _Q_LOCKED_VAL) {

Hm, wouldn't it be just easier to do a 'goto restart' where restart label points at the first loop statement? Ah never mind - we have already inserted ourselves in the previous's node.

But that is confusing - we have done: "prev->next = node;"

Quoted 3 lines

And then exited out of 'val = atomic_read(&lock->val))' which suggests that queue_spin_unlock has called us. How can we be contended again?

We're not contended again; we're in the 'contended queued' case, which means that 'tail' didn't point to us anymore, in that case, we must kick our next node such that it will now drop out of arch_mcs_spin_lock_contended() and goes wait on the 'locked' state.

So what we do here is wait for 'node->next' to be set; it might still be NULL if the other cpu is between:

  prev = xchg(lock->tail, node);

and:

  prev->next = node;

Once we observe the next node, we call arch_mcs_spin_unlock_contended() on it, which sets its mcs_spinlock::locked and makes the new 'top of queue' drop out of arch_mcs_spin_lock_contended and spin on the 'locked' state as said above.

Quoted 11 lines · Konrad Rzeszutek Wilk

kernel/locking/mcs_spinlock.h line 20

Quoted 9 lines

Index: linux-2.6/kernel/locking/mcs_spinlock.h
===================================================================

kernel/locking/mcs_spinlock.h +1 -0

@@ -17,6 +17,7 @@
 struct mcs_spinlock {
 	struct mcs_spinlock *next;
 	int locked; /* 1 if lock acquired */
+	int count;

This could use a comment.

like so?

int count; /* nesting count, see qspinlock.c */

Quoted 13 lines

kernel/locking/mcs_spinlock.h

Quoted 8 lines

kernel/locking/mcs_spinlock.h +6 -0

+static inline u32 encode_tail(int cpu, int idx)
+{
+	u32 tail;
+
+	tail  = (cpu + 1) << _Q_TAIL_CPU_OFFSET;
+	tail |= idx << _Q_TAIL_IDX_OFFSET; /* assume < 4 */

Should there an

ASSSERT (idx < 4)

Quoted 2 lines

just in case we screw up somehow (I can't figure out how, but that is partially why ASSERTS are added).

#ifdef CONFIG_DEBUG_SPINLOCK
	BUG_ON(idx > 3);

#endif

might do, I suppose.

Quoted 8 lines

Quoted 7 lines

+/**
+ * queue_spin_lock_slowpath - acquire the queue spinlock
+ * @lock: Pointer to queue spinlock structure
+ * @val: Current value of the queue spinlock 32-bit word
+ *
+ * (queue tail, lock bit)

Quoted 1 line

Except it is not a lock bit. It is a lock uint8_t.

It is indeed, although that's an accident of implementation. I could do s/bit// and not mention the entire storage angle at all?

Quoted 2 lines

Is the queue tail at this point the composite of 'cpu|idx'?

Yes, as per {en,de}code_tail() above.

Quoted 9 lines

Quoted 7 lines

+ *

+ *              fast      :    slow                                  :    unlock
+ *                        :                                          :
+ * uncontended  (0,0)   --:--> (0,1) --------------------------------:--> (*,0)
+ *                        :       | ^--------.                    /  :
+ *                        :       v           \                   |  :
+ * uncontended            :    (n,x) --+--> (n,0)                 |  :

So many CPUn come in right? Is 'n' for the number of CPUs?

Nope, 'n' for any one specific tail, in particular the first one to arrive. This is the 'uncontended queue' case as per the label, so we need a named value for the first, in order to distinguish between the state to the right (same tail, but unlocked) and the state below (different tail).

Quoted 5 lines

Quoted 4 lines

+ *   queue                :       | ^--'                          |  :
+ *                        :       v                               |  :
+ * contended              :    (*,x) --+--> (*,0) -----> (*,1) ---'  :
+ *   queue                :         ^--'                             :

Quoted 3 lines

And here um, what are the '*' for? Are they the four different types of handlers that can be nested? So task, sofitrq, hardisk, and nmi?

'*' as in wildcard, any tail, specifically not 'n'.

Quoted 14 lines

kernel/locking/mcs_spinlock.h

Quoted 11 lines

kernel/locking/mcs_spinlock.h +10 -0

+void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val)
+{
+	struct mcs_spinlock *prev, *next, *node;
+	u32 new, old, tail;
+	int idx;
+
+	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
+
+	node = this_cpu_ptr(&mcs_nodes[0]);
+	idx = node->count++;

If this is the first time we enter this, wouldn't idx end up being 1?

Nope, postfix ++ returns first and increments later.

Quoted 9 lines

kernel/locking/mcs_spinlock.h

Quoted 4 lines

kernel/locking/mcs_spinlock.h +3 -0

+	tail = encode_tail(smp_processor_id(), idx);
+
+	node += idx;

Meaning we end up skipping the 'mcs_nodes[0]' one altogether - even on the first 'level' (task, softirq, hardirq, nmi)? Won't that cause us to blow past the array when we are nested at the nmi handler?

Seeing how its all static storage, which is automagically initialized to 0, combined with the postfix ++ (as opposed to the prefix ++) we should be getting 0 here.

Quoted 15 lines

kernel/locking/mcs_spinlock.h

Quoted 9 lines

kernel/locking/mcs_spinlock.h +8 -0

+	node->locked = 0;
+	node->next = NULL;
+
+	/*
+	 * trylock || xchg(lock, node)
+	 *
+	 * 0,0 -> 0,1 ; trylock
+	 * p,x -> n,x ; prev = xchg(lock, node)

I looked at that for 10 seconds and I was not sure what you meant. Is this related to the MCS document you had pointed to? It would help if you mention that the comments follow the document. (But they don't seem to)

Quoted 5 lines

I presume what you mean is that if we are the next after the lock-holder we need only to update the 'next' (or the composite value of smp_processor_idx | idx) to point to us.

As in, swap the 'L' with 'I' (looking at the doc)

They are the 'tail','lock' tuples, so this composite atomic operation completes either:

0,0 -> 0,1 -- we had no tail, not locked; into: no tail, locked.

OR

p,x -> n,x -- tail was p; into: tail is n; preserving locked.

Quoted 8 lines

kernel/locking/mcs_spinlock.h

Quoted 5 lines

kernel/locking/mcs_spinlock.h +4 -0

+	 */
+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val)

Could you add a comment here, like this:

Quoted 10 lines

/*
* N.B. Initially 'val' will have some value (as we are called
* after the _Q_LOCKED_VAL could not be set by queue_spin_lock).
* But on subsequent iterations, either the lock holder will
* decrement the val (queue_spin_unlock - to zero) and we
* needn't to record our status in the queue as we have set the
* Q_LOCKED_VAL (new) and are the lock holder. Or we are next
* in line and need to record our 'next' (aka, smp_processor_id() | idx)
* position. */
*/

The idea was that:

0,0 -> 0,1
p,x -> n,x

Completely covers what this composite atomic does.

Quoted 39 lines

Quoted 39 lines

kernel/locking/mcs_spinlock.h +39 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+
+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);
+	}
+
+	/*
+	 * we're at the head of the waitqueue, wait for the owner to go away.
+	 *
+	 * *,x -> *,0
+	 */
+	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
+		cpu_relax();
+
+	/*
+	 * claim the lock:
+	 *
+	 * n,0 -> 0,1 : lock, uncontended
+	 * *,0 -> *,1 : lock, contended
+	 */

Quoted 8 lines

kernel/locking/mcs_spinlock.h

Quoted 4 lines

kernel/locking/mcs_spinlock.h +4 -0

+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val != tail)
+			new |= val;

You lost me here. If we are at the head of the queue, and the owner has called queue_spin_unlock (hence made us get out of the 'val = atomic_read' loop, how can val != tail?

Remember:

Quoted 1 line

kernel/locking/mcs_spinlock.h

Quoted 1 line

kernel/locking/mcs_spinlock.h +1 -0

+	tail = encode_tail(smp_processor_id(), idx);

So if value != tail, that means the tail pointer doesn't point to us anymore, another cpu/idx queued itself and is now last.

Quoted 4 lines

I suspect it has something to do with the comment, but I am still unsure what it means.

Could you help a bit in explaining it in English please?

(refer to the state diagram, if we count states left->right, top->bottom, then this is: 5->2 or 7->8

n,0 -> 0,1:

the lock is free and the tail points to the first queued; this means that unqueueing implies wiping the tail, at the same time, acquire the lock.

*,0 -> *,1:

the lock is free and the tail doesn't point to the first queued; this means that unqueueing doesn't touch the tail pointer but only sets the lock.

Quoted 20 lines

kernel/locking/mcs_spinlock.h

Quoted 12 lines

kernel/locking/mcs_spinlock.h +12 -0

+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * contended path; wait for next, release.
+	 */
+	if (new != _Q_LOCKED_VAL) {

Hm, wouldn't it be just easier to do a 'goto restart' where restart label points at the first loop statement? Ah never mind - we have already inserted ourselves in the previous's node.

But that is confusing - we have done: "prev->next = node;"

Quoted 3 lines

And then exited out of 'val = atomic_read(&lock->val))' which suggests that queue_spin_unlock has called us. How can we be contended again?

We're not contended again; we're in the 'contended queued' case, which means that 'tail' didn't point to us anymore, in that case, we must kick our next node such that it will now drop out of arch_mcs_spin_lock_contended() and goes wait on the 'locked' state.

So what we do here is wait for 'node->next' to be set; it might still be NULL if the other cpu is between:

  prev = xchg(lock->tail, node);

and:

  prev->next = node;

Once we observe the next node, we call arch_mcs_spin_unlock_contended() on it, which sets its mcs_spinlock::locked and makes the new 'top of queue' drop out of arch_mcs_spin_lock_contended and spin on the 'locked' state as said above.

kernel/locking/mcs_spinlock.h line 20

Quoted 9 lines

Index: linux-2.6/kernel/locking/mcs_spinlock.h
===================================================================

kernel/locking/mcs_spinlock.h +1 -0

@@ -17,6 +17,7 @@
 struct mcs_spinlock {
 	struct mcs_spinlock *next;
 	int locked; /* 1 if lock acquired */
+	int count;

This could use a comment.

kernel/locking/mcs_spinlock.h

Quoted 6 lines

kernel/locking/mcs_spinlock.h +6 -0

+static inline u32 encode_tail(int cpu, int idx)
+{
+	u32 tail;
+
+	tail  = (cpu + 1) << _Q_TAIL_CPU_OFFSET;
+	tail |= idx << _Q_TAIL_IDX_OFFSET; /* assume < 4 */

Should there an

ASSSERT (idx < 4)

just in case we screw up somehow (I can't figure out how, but that is partially why ASSERTS are added).

Quoted 6 lines

+/**
+ * queue_spin_lock_slowpath - acquire the queue spinlock
+ * @lock: Pointer to queue spinlock structure
+ * @val: Current value of the queue spinlock 32-bit word
+ *
+ * (queue tail, lock bit)

Except it is not a lock bit. It is a lock uint8_t.

Is the queue tail at this point the composite of 'cpu|idx'?

Quoted 7 lines

+ *

+ *              fast      :    slow                                  :    unlock
+ *                        :                                          :
+ * uncontended  (0,0)   --:--> (0,1) --------------------------------:--> (*,0)
+ *                        :       | ^--------.                    /  :
+ *                        :       v           \                   |  :
+ * uncontended            :    (n,x) --+--> (n,0)                 |  :

So many CPUn come in right? Is 'n' for the number of CPUs?

Quoted 4 lines

+ *   queue                :       | ^--'                          |  :
+ *                        :       v                               |  :
+ * contended              :    (*,x) --+--> (*,0) -----> (*,1) ---'  :
+ *   queue                :         ^--'                             :

And here um, what are the '*' for? Are they the four different types of handlers that can be nested? So task, sofitrq, hardisk, and nmi?

Quoted 5 lines

kernel/locking/mcs_spinlock.h +5 -0

+void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val)
+{
+	struct mcs_spinlock *prev, *next, *node;
+	u32 new, old, tail;
+	int idx;

kernel/locking/mcs_spinlock.h

Quoted 5 lines

kernel/locking/mcs_spinlock.h +5 -0

+
+	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
+
+	node = this_cpu_ptr(&mcs_nodes[0]);
+	idx = node->count++;

If this is the first time we enter this, wouldn't idx end up being 1?

kernel/locking/mcs_spinlock.h

Quoted 3 lines

kernel/locking/mcs_spinlock.h +3 -0

+	tail = encode_tail(smp_processor_id(), idx);
+
+	node += idx;

Meaning we end up skipping the 'mcs_nodes[0]' one altogether - even on the first 'level' (task, softirq, hardirq, nmi)? Won't that cause us to blow past the array when we are nested at the nmi handler?

kernel/locking/mcs_spinlock.h

Quoted 8 lines

kernel/locking/mcs_spinlock.h +8 -0

+	node->locked = 0;
+	node->next = NULL;
+
+	/*
+	 * trylock || xchg(lock, node)
+	 *
+	 * 0,0 -> 0,1 ; trylock
+	 * p,x -> n,x ; prev = xchg(lock, node)

I looked at that for 10 seconds and I was not sure what you meant. Is this related to the MCS document you had pointed to? It would help if you mention that the comments follow the document. (But they don't seem to)

I presume what you mean is that if we are the next after the lock-holder we need only to update the 'next' (or the composite value of smp_processor_idx | idx) to point to us.

As in, swap the 'L' with 'I' (looking at the doc)

kernel/locking/mcs_spinlock.h

Quoted 4 lines

kernel/locking/mcs_spinlock.h +4 -0

+	 */
+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val)

Could you add a comment here, like this:

/*
* N.B. Initially 'val' will have some value (as we are called
* after the _Q_LOCKED_VAL could not be set by queue_spin_lock).
* But on subsequent iterations, either the lock holder will
* decrement the val (queue_spin_unlock - to zero) and we
* needn't to record our status in the queue as we have set the
* Q_LOCKED_VAL (new) and are the lock holder. Or we are next
* in line and need to record our 'next' (aka, smp_processor_id() | idx)
* position. */
*/

Quoted 39 lines

kernel/locking/mcs_spinlock.h +39 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+
+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);
+	}
+
+	/*
+	 * we're at the head of the waitqueue, wait for the owner to go away.
+	 *
+	 * *,x -> *,0
+	 */
+	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
+		cpu_relax();
+
+	/*
+	 * claim the lock:
+	 *
+	 * n,0 -> 0,1 : lock, uncontended
+	 * *,0 -> *,1 : lock, contended
+	 */

kernel/locking/mcs_spinlock.h

Quoted 4 lines

kernel/locking/mcs_spinlock.h +4 -0

+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val != tail)
+			new |= val;

You lost me here. If we are at the head of the queue, and the owner has called queue_spin_unlock (hence made us get out of the 'val = atomic_read' loop, how can val != tail?

kernel/locking/mcs_spinlock.h

Quoted 1 line

kernel/locking/mcs_spinlock.h +1 -0

+	tail = encode_tail(smp_processor_id(), idx);

I suspect it has something to do with the comment, but I am still unsure what it means.

Could you help a bit in explaining it in English please?

kernel/locking/mcs_spinlock.h

Quoted 12 lines

kernel/locking/mcs_spinlock.h +12 -0

+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * contended path; wait for next, release.
+	 */
+	if (new != _Q_LOCKED_VAL) {

Hm, wouldn't it be just easier to do a 'goto restart' where restart label points at the first loop statement? Ah never mind - we have already inserted ourselves in the previous's node.

But that is confusing - we have done: "prev->next = node;"

And then exited out of 'val = atomic_read(&lock->val))' which suggests that queue_spin_unlock has called us. How can we be contended again?

kernel/locking/mcs_spinlock.h line 20

Quoted 9 lines

Index: linux-2.6/kernel/locking/mcs_spinlock.h
===================================================================

kernel/locking/mcs_spinlock.h +1 -0

@@ -17,6 +17,7 @@
 struct mcs_spinlock {
 	struct mcs_spinlock *next;
 	int locked; /* 1 if lock acquired */
+	int count;

This could use a comment.

kernel/locking/mcs_spinlock.h

Quoted 6 lines

kernel/locking/mcs_spinlock.h +6 -0

+static inline u32 encode_tail(int cpu, int idx)
+{
+	u32 tail;
+
+	tail  = (cpu + 1) << _Q_TAIL_CPU_OFFSET;
+	tail |= idx << _Q_TAIL_IDX_OFFSET; /* assume < 4 */

Should there an

ASSSERT (idx < 4)

just in case we screw up somehow (I can't figure out how, but that is partially why ASSERTS are added).

Quoted 6 lines

+/**
+ * queue_spin_lock_slowpath - acquire the queue spinlock
+ * @lock: Pointer to queue spinlock structure
+ * @val: Current value of the queue spinlock 32-bit word
+ *
+ * (queue tail, lock bit)

Except it is not a lock bit. It is a lock uint8_t.

Is the queue tail at this point the composite of 'cpu|idx'?

Quoted 7 lines

+ *

+ *              fast      :    slow                                  :    unlock
+ *                        :                                          :
+ * uncontended  (0,0)   --:--> (0,1) --------------------------------:--> (*,0)
+ *                        :       | ^--------.                    /  :
+ *                        :       v           \                   |  :
+ * uncontended            :    (n,x) --+--> (n,0)                 |  :

So many CPUn come in right? Is 'n' for the number of CPUs?

Quoted 4 lines

+ *   queue                :       | ^--'                          |  :
+ *                        :       v                               |  :
+ * contended              :    (*,x) --+--> (*,0) -----> (*,1) ---'  :
+ *   queue                :         ^--'                             :

And here um, what are the '*' for? Are they the four different types of handlers that can be nested? So task, sofitrq, hardisk, and nmi?

Quoted 5 lines

kernel/locking/mcs_spinlock.h +5 -0

+void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val)
+{
+	struct mcs_spinlock *prev, *next, *node;
+	u32 new, old, tail;
+	int idx;

kernel/locking/mcs_spinlock.h

Quoted 5 lines

kernel/locking/mcs_spinlock.h +5 -0

+
+	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
+
+	node = this_cpu_ptr(&mcs_nodes[0]);
+	idx = node->count++;

If this is the first time we enter this, wouldn't idx end up being 1?

kernel/locking/mcs_spinlock.h

Quoted 3 lines

kernel/locking/mcs_spinlock.h +3 -0

+	tail = encode_tail(smp_processor_id(), idx);
+
+	node += idx;

Meaning we end up skipping the 'mcs_nodes[0]' one altogether - even on the first 'level' (task, softirq, hardirq, nmi)? Won't that cause us to blow past the array when we are nested at the nmi handler?

kernel/locking/mcs_spinlock.h

Quoted 8 lines

kernel/locking/mcs_spinlock.h +8 -0

+	node->locked = 0;
+	node->next = NULL;
+
+	/*
+	 * trylock || xchg(lock, node)
+	 *
+	 * 0,0 -> 0,1 ; trylock
+	 * p,x -> n,x ; prev = xchg(lock, node)

I looked at that for 10 seconds and I was not sure what you meant. Is this related to the MCS document you had pointed to? It would help if you mention that the comments follow the document. (But they don't seem to)

I presume what you mean is that if we are the next after the lock-holder we need only to update the 'next' (or the composite value of smp_processor_idx | idx) to point to us.

As in, swap the 'L' with 'I' (looking at the doc)

kernel/locking/mcs_spinlock.h

Quoted 4 lines

kernel/locking/mcs_spinlock.h +4 -0

+	 */
+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val)

Could you add a comment here, like this:

/*
* N.B. Initially 'val' will have some value (as we are called
* after the _Q_LOCKED_VAL could not be set by queue_spin_lock).
* But on subsequent iterations, either the lock holder will
* decrement the val (queue_spin_unlock - to zero) and we
* needn't to record our status in the queue as we have set the
* Q_LOCKED_VAL (new) and are the lock holder. Or we are next
* in line and need to record our 'next' (aka, smp_processor_id() | idx)
* position. */
*/

Quoted 39 lines

kernel/locking/mcs_spinlock.h +39 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+
+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);
+	}
+
+	/*
+	 * we're at the head of the waitqueue, wait for the owner to go away.
+	 *
+	 * *,x -> *,0
+	 */
+	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
+		cpu_relax();
+
+	/*
+	 * claim the lock:
+	 *
+	 * n,0 -> 0,1 : lock, uncontended
+	 * *,0 -> *,1 : lock, contended
+	 */

kernel/locking/mcs_spinlock.h

Quoted 4 lines

kernel/locking/mcs_spinlock.h +4 -0

+	for (;;) {
+		new = _Q_LOCKED_VAL;
+		if (val != tail)
+			new |= val;

You lost me here. If we are at the head of the queue, and the owner has called queue_spin_unlock (hence made us get out of the 'val = atomic_read' loop, how can val != tail?

kernel/locking/mcs_spinlock.h

Quoted 1 line

kernel/locking/mcs_spinlock.h +1 -0

+	tail = encode_tail(smp_processor_id(), idx);

I suspect it has something to do with the comment, but I am still unsure what it means.

Could you help a bit in explaining it in English please?

kernel/locking/mcs_spinlock.h

Quoted 12 lines

kernel/locking/mcs_spinlock.h +12 -0

+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * contended path; wait for next, release.
+	 */
+	if (new != _Q_LOCKED_VAL) {

Hm, wouldn't it be just easier to do a 'goto restart' where restart label points at the first loop statement? Ah never mind - we have already inserted ourselves in the previous's node.

But that is confusing - we have done: "prev->next = node;"

And then exited out of 'val = atomic_read(&lock->val))' which suggests that queue_spin_unlock has called us. How can we be contended again?

From: Waiman Long <[email protected]>

This patch introduces a new generic queue spinlock implementation that can serve as an alternative to the default ticket spinlock. Compared with the ticket spinlock, this queue spinlock should be almost as fair as the ticket spinlock. It has about the same speed in single-thread and it can be much faster in high contention situations especially when the spinlock is embedded within the data structure to be protected.

Only in light to moderate contention where the average queue depth is around 1-3 will this queue spinlock be potentially a bit slower due to the higher slowpath overhead.

This queue spinlock is especially suit to NUMA machines with a large number of cores as the chance of spinlock contention is much higher in those machines. The cost of contention is also higher because of slower inter-node memory traffic.

Due to the fact that spinlocks are acquired with preemption disabled, the process will not be migrated to another CPU while it is trying to get a spinlock. Ignoring interrupt handling, a CPU can only be contending in one spinlock at any one time. Counting soft IRQ, hard IRQ and NMI, a CPU can only have a maximum of 4 concurrent lock waiting activities. By allocating a set of per-cpu queue nodes and used them to form a waiting queue, we can encode the queue node address into a much smaller 24-bit size (including CPU number and queue node index) leaving one byte for the lock.

Please note that the queue node is only needed when waiting for the lock. Once the lock is acquired, the queue node can be released to be used later.

Signed-off-by Waiman Long <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

kernel/locking/mcs_spinlock.h +0 -0

 };
 
 #ifndef arch_mcs_spin_lock_contended

Index: linux-2.6/kernel/locking/qspinlock.c
===================================================================

kernel/locking/qspinlock.c new file +63 -0

@@ -0,0 +1,197 @@
+/*
+ * Queue spinlock
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * (C) Copyright 2013-2014 Hewlett-Packard Development Company, L.P.
+ *
+ * Authors: Waiman Long <[email protected]>
+ *          Peter Zijlstra <[email protected]>
+ */
+#include <linux/smp.h>
+#include <linux/bug.h>
+#include <linux/cpumask.h>
+#include <linux/percpu.h>
+#include <linux/hardirq.h>
+#include <linux/mutex.h>
+#include <asm/qspinlock.h>
+
+/*
+ * The basic principle of a queue-based spinlock can best be understood
+ * by studying a classic queue-based spinlock implementation called the
+ * MCS lock. The paper below provides a good description for this kind
+ * of lock.
+ *
+ * http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf
+ *
+ * This queue spinlock implementation is based on the MCS lock, however to make
+ * it fit the 4 bytes we assume spinlock_t to be, and preserve its existing
+ * API, we must modify it some.
+ *
+ * In particular; where the traditional MCS lock consists of a tail pointer
+ * (8 bytes) and needs the next pointer (another 8 bytes) of its own node to
+ * unlock the next pending (next->locked), we compress both these: {tail,
+ * next->locked} into a single u32 value.
+ *
+ * Since a spinlock disables recursion of its own context and there is a limit
+ * to the contexts that can nest; namely: task, softirq, hardirq, nmi, we can
+ * encode the tail as and index indicating this context and a cpu number.
+ *
+ * We can further change the first spinner to spin on a bit in the lock word
+ * instead of its node; whereby avoiding the need to carry a node from lock to
+ * unlock, and preserving API.
+ */
+
+#include "mcs_spinlock.h"
+
+/*
+ * Per-CPU queue node structures; we can never have more than 4 nested
+ * contexts: task, softirq, hardirq, nmi.
+ *
+ * Exactly fits one cacheline.
+ */
+static DEFINE_PER_CPU_ALIGNED(struct mcs_spinlock, mcs_nodes[4]);
+
+/*

kernel/locking/qspinlock.c new file +8 -0

+
+	return tail;
+}
+
+static inline struct mcs_spinlock *decode_tail(u32 tail)
+{
+	int cpu = (tail >> _Q_TAIL_CPU_OFFSET) - 1;
+	int idx = (tail &  _Q_TAIL_IDX_MASK) >> _Q_TAIL_IDX_OFFSET;

kernel/locking/qspinlock.c new file +33 -0

+			new = tail | (val & _Q_LOCKED_MASK);
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock; forget about queueing.
+	 */
+	if (new == _Q_LOCKED_VAL)
+		goto release;
+
+	/*
+	 * if there was a previous node; link it and wait.
+	 */
+	if (old & ~_Q_LOCKED_MASK) {
+		prev = decode_tail(old);
+		ACCESS_ONCE(prev->next) = node;
+
+		arch_mcs_spin_lock_contended(&node->locked);
+	}
+
+	/*
+	 * we're at the head of the waitqueue, wait for the owner to go away.
+	 *
+	 * *,x -> *,0
+	 */
+	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
+		cpu_relax();
+

kernel/locking/qspinlock.c new file +13 -0

+		while (!(next = ACCESS_ONCE(node->next)))
+			cpu_relax();
+
+		arch_mcs_spin_unlock_contended(&next->locked);
+	}
+
+release:
+	/*
+	 * release the node
+	 */
+	this_cpu_dec(mcs_nodes[0].count);
+}
+EXPORT_SYMBOL(queue_spin_lock_slowpath);

+ * The basic principle of a queue-based spinlock can best be understood
+ * by studying a classic queue-based spinlock implementation called the
+ * MCS lock. The paper below provides a good description for this kind
+ * of lock.
+ *
+ * http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf
+ *
+ * This queue spinlock implementation is based on the MCS lock, however to make
+ * it fit the 4 bytes we assume spinlock_t to be, and preserve its existing
+ * API, we must modify it some.
+ *
+ * In particular; where the traditional MCS lock consists of a tail pointer
+ * (8 bytes) and needs the next pointer (another 8 bytes) of its own node to
+ * unlock the next pending (next->locked), we compress both these: {tail,
+ * next->locked} into a single u32 value.

+ *
+ * Since a spinlock disables recursion of its own context and there is a limit
+ * to the contexts that can nest; namely: task, softirq, hardirq, nmi, we can
+ * encode the tail as and index indicating this context and a cpu number.
+ *
+ * We can further change the first spinner to spin on a bit in the lock word
+ * instead of its node; whereby avoiding the need to carry a node from lock to
+ * unlock, and preserving API.

Quoted 15 lines

+ * The basic principle of a queue-based spinlock can best be understood
+ * by studying a classic queue-based spinlock implementation called the
+ * MCS lock. The paper below provides a good description for this kind
+ * of lock.
+ *
+ * http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf
+ *
+ * This queue spinlock implementation is based on the MCS lock, however to make
+ * it fit the 4 bytes we assume spinlock_t to be, and preserve its existing
+ * API, we must modify it some.
+ *
+ * In particular; where the traditional MCS lock consists of a tail pointer
+ * (8 bytes) and needs the next pointer (another 8 bytes) of its own node to
+ * unlock the next pending (next->locked), we compress both these: {tail,
+ * next->locked} into a single u32 value.

Quoted 8 lines

+ *
+ * Since a spinlock disables recursion of its own context and there is a limit
+ * to the contexts that can nest; namely: task, softirq, hardirq, nmi, we can
+ * encode the tail as and index indicating this context and a cpu number.
+ *
+ * We can further change the first spinner to spin on a bit in the lock word
+ * instead of its node; whereby avoiding the need to carry a node from lock to
+ * unlock, and preserving API.

You also made changes (compared to the MCS) in that the unlock path is not spinning waiting for the successor and that the job of passing the lock is not done in the unlock path either.

Instead all of that is now done in the path of the lock acquirer logic.

Could you update the comment to say that please?

Quoted 28 lines · Konrad Rzeszutek Wilk

Quoted 15 lines

+ * The basic principle of a queue-based spinlock can best be understood
+ * by studying a classic queue-based spinlock implementation called the
+ * MCS lock. The paper below provides a good description for this kind
+ * of lock.
+ *
+ * http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf
+ *
+ * This queue spinlock implementation is based on the MCS lock, however to make
+ * it fit the 4 bytes we assume spinlock_t to be, and preserve its existing
+ * API, we must modify it some.
+ *
+ * In particular; where the traditional MCS lock consists of a tail pointer
+ * (8 bytes) and needs the next pointer (another 8 bytes) of its own node to
+ * unlock the next pending (next->locked), we compress both these: {tail,
+ * next->locked} into a single u32 value.

Quoted 8 lines

+ *
+ * Since a spinlock disables recursion of its own context and there is a limit
+ * to the contexts that can nest; namely: task, softirq, hardirq, nmi, we can
+ * encode the tail as and index indicating this context and a cpu number.
+ *
+ * We can further change the first spinner to spin on a bit in the lock word
+ * instead of its node; whereby avoiding the need to carry a node from lock to
+ * unlock, and preserving API.

You also made changes (compared to the MCS) in that the unlock path is not spinning waiting for the successor and that the job of passing the lock is not done in the unlock path either.

Quoted 3 lines

Instead all of that is now done in the path of the lock acquirer logic.

Could you update the comment to say that please?

I _think_ I know what you mean.. So that is actually implied by the last

paragraph, but I suppose I can make it explicit; something like:

*
* Another way to look at it is:
*
* lock(tail,locked)

  *    struct mcs_spinlock node;
  *    mcs_spin_lock(tail, &node);
  *    test-and-set locked;
  *    mcs_spin_unlock(tail, &node);

*
* unlock(tail,locked)
* clear locked
*
* Where we have compressed (tail,locked) into a single u32 word.

Quoted 28 lines · Konrad Rzeszutek Wilk

Quoted 15 lines

+ * The basic principle of a queue-based spinlock can best be understood
+ * by studying a classic queue-based spinlock implementation called the
+ * MCS lock. The paper below provides a good description for this kind
+ * of lock.
+ *
+ * http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf
+ *
+ * This queue spinlock implementation is based on the MCS lock, however to make
+ * it fit the 4 bytes we assume spinlock_t to be, and preserve its existing
+ * API, we must modify it some.
+ *
+ * In particular; where the traditional MCS lock consists of a tail pointer
+ * (8 bytes) and needs the next pointer (another 8 bytes) of its own node to
+ * unlock the next pending (next->locked), we compress both these: {tail,
+ * next->locked} into a single u32 value.

Quoted 8 lines

+ *
+ * Since a spinlock disables recursion of its own context and there is a limit
+ * to the contexts that can nest; namely: task, softirq, hardirq, nmi, we can
+ * encode the tail as and index indicating this context and a cpu number.
+ *
+ * We can further change the first spinner to spin on a bit in the lock word
+ * instead of its node; whereby avoiding the need to carry a node from lock to
+ * unlock, and preserving API.

You also made changes (compared to the MCS) in that the unlock path is not spinning waiting for the successor and that the job of passing the lock is not done in the unlock path either.

Quoted 3 lines

Instead all of that is now done in the path of the lock acquirer logic.

Could you update the comment to say that please?

I _think_ I know what you mean.. So that is actually implied by the last

paragraph, but I suppose I can make it explicit; something like:

*
* Another way to look at it is:
*
* lock(tail,locked)

  *    struct mcs_spinlock node;
  *    mcs_spin_lock(tail, &node);
  *    test-and-set locked;
  *    mcs_spin_unlock(tail, &node);

*
* unlock(tail,locked)
* clear locked
*
* Where we have compressed (tail,locked) into a single u32 word.

Quoted 15 lines

+ * The basic principle of a queue-based spinlock can best be understood
+ * by studying a classic queue-based spinlock implementation called the
+ * MCS lock. The paper below provides a good description for this kind
+ * of lock.
+ *
+ * http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf
+ *
+ * This queue spinlock implementation is based on the MCS lock, however to make
+ * it fit the 4 bytes we assume spinlock_t to be, and preserve its existing
+ * API, we must modify it some.
+ *
+ * In particular; where the traditional MCS lock consists of a tail pointer
+ * (8 bytes) and needs the next pointer (another 8 bytes) of its own node to
+ * unlock the next pending (next->locked), we compress both these: {tail,
+ * next->locked} into a single u32 value.

Quoted 8 lines

+ *
+ * Since a spinlock disables recursion of its own context and there is a limit
+ * to the contexts that can nest; namely: task, softirq, hardirq, nmi, we can
+ * encode the tail as and index indicating this context and a cpu number.
+ *
+ * We can further change the first spinner to spin on a bit in the lock word
+ * instead of its node; whereby avoiding the need to carry a node from lock to
+ * unlock, and preserving API.

You also made changes (compared to the MCS) in that the unlock path is not spinning waiting for the successor and that the job of passing the lock is not done in the unlock path either.

Instead all of that is now done in the path of the lock acquirer logic.

Could you update the comment to say that please?

+ * The basic principle of a queue-based spinlock can best be understood
+ * by studying a classic queue-based spinlock implementation called the
+ * MCS lock. The paper below provides a good description for this kind
+ * of lock.
+ *
+ * http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf
+ *
+ * This queue spinlock implementation is based on the MCS lock, however to make
+ * it fit the 4 bytes we assume spinlock_t to be, and preserve its existing
+ * API, we must modify it some.
+ *
+ * In particular; where the traditional MCS lock consists of a tail pointer
+ * (8 bytes) and needs the next pointer (another 8 bytes) of its own node to
+ * unlock the next pending (next->locked), we compress both these: {tail,
+ * next->locked} into a single u32 value.

+ *
+ * Since a spinlock disables recursion of its own context and there is a limit
+ * to the contexts that can nest; namely: task, softirq, hardirq, nmi, we can
+ * encode the tail as and index indicating this context and a cpu number.
+ *
+ * We can further change the first spinner to spin on a bit in the lock word
+ * instead of its node; whereby avoiding the need to carry a node from lock to
+ * unlock, and preserving API.

Because the qspinlock needs to touch a second cacheline; add a pending bit and allow a single in-word spinner before we punt to the second cacheline.

Signed-off-by Peter Zijlstra <[email protected]>

---
 include/asm-generic/qspinlock_types.h |   12 ++-
 kernel/locking/qspinlock.c            |  109 +++++++++++++++++++++++++++-------
 2 files changed, 97 insertions(+), 24 deletions(-)

include/asm-generic/qspinlock_types.h +9 -3

@@ -39,8 +39,9 @@ typedef struct qspinlock {
  * Bitfields in the atomic value:
  *
  *  0- 7: locked byte
- *  8- 9: tail index
- * 10-31: tail cpu (+1)
+ *     8: pending
+ *  9-10: tail index
+ * 11-31: tail cpu (+1)
  */
 #define	_Q_SET_MASK(type)	(((1U << _Q_ ## type ## _BITS) - 1)\
 				      << _Q_ ## type ## _OFFSET)

@@ -48,7 +49,11 @@ typedef struct qspinlock {
 #define _Q_LOCKED_BITS		8
 #define _Q_LOCKED_MASK		_Q_SET_MASK(LOCKED)
 
-#define _Q_TAIL_IDX_OFFSET	(_Q_LOCKED_OFFSET + _Q_LOCKED_BITS)
+#define _Q_PENDING_OFFSET	(_Q_LOCKED_OFFSET + _Q_LOCKED_BITS)
+#define _Q_PENDING_BITS		1
+#define _Q_PENDING_MASK		_Q_SET_MASK(PENDING)
+
+#define _Q_TAIL_IDX_OFFSET	(_Q_PENDING_OFFSET + _Q_PENDING_BITS)
 #define _Q_TAIL_IDX_BITS	2
 #define _Q_TAIL_IDX_MASK	_Q_SET_MASK(TAIL_IDX)
 

@@ -57,5 +62,6 @@ typedef struct qspinlock {
 #define _Q_TAIL_CPU_MASK	_Q_SET_MASK(TAIL_CPU)
 
 #define _Q_LOCKED_VAL		(1U << _Q_LOCKED_OFFSET)
+#define _Q_PENDING_VAL		(1U << _Q_PENDING_OFFSET)
 
 #endif /* __ASM_GENERIC_QSPINLOCK_TYPES_H */

kernel/locking/qspinlock.c +88 -21

@@ -83,24 +83,28 @@ static inline struct mcs_spinlock *decod
 	return per_cpu_ptr(&mcs_nodes[idx], cpu);
 }
 
+#define _Q_LOCKED_PENDING_MASK	(_Q_LOCKED_MASK | _Q_PENDING_MASK)
+
 /**
  * queue_spin_lock_slowpath - acquire the queue spinlock
  * @lock: Pointer to queue spinlock structure
  * @val: Current value of the queue spinlock 32-bit word
  *
- * (queue tail, lock bit)
- *
- *              fast      :    slow                                  :    unlock
- *                        :                                          :
- * uncontended  (0,0)   --:--> (0,1) --------------------------------:--> (*,0)
- *                        :       | ^--------.                    /  :
- *                        :       v           \                   |  :
- * uncontended            :    (n,x) --+--> (n,0)                 |  :
- *   queue                :       | ^--'                          |  :
- *                        :       v                               |  :
- * contended              :    (*,x) --+--> (*,0) -----> (*,1) ---'  :
- *   queue                :         ^--'                             :
+ * (queue tail, pending bit, lock bit)
  *
+ *              fast     :    slow                                  :    unlock
+ *                       :                                          :
+ * uncontended  (0,0,0) -:--> (0,0,1) ------------------------------:--> (*,*,0)
+ *                       :       | ^--------.------.             /  :
+ *                       :       v           \      \            |  :
+ * pending               :    (0,1,1) +--> (0,1,0)   \           |  :
+ *                       :       | ^--'              |           |  :
+ *                       :       v                   |           |  :
+ * uncontended           :    (n,x,y) +--> (n,0,0) --'           |  :
+ *   queue               :       | ^--'                          |  :
+ *                       :       v                               |  :
+ * contended             :    (*,x,y) +--> (*,0,0) ---> (*,0,1) -'  :
+ *   queue               :         ^--'                             :
  */
 void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 {

@@ -110,6 +114,65 @@ void queue_spin_lock_slowpath(struct qsp
 
 	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
 
+	/*
+	 * trylock || pending
+	 *
+	 * 0,0,0 -> 0,0,1 ; trylock
+	 * 0,0,1 -> 0,1,1 ; pending
+	 */
+	for (;;) {
+		/*
+		 * If we observe any contention; queue.
+		 */
+		if (val & ~_Q_LOCKED_MASK)
+			goto queue;
+
+		new = _Q_LOCKED_VAL;
+		if (val == new)
+			new |= _Q_PENDING_VAL;
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+
+	/*
+	 * we won the trylock
+	 */
+	if (new == _Q_LOCKED_VAL)
+		return;
+
+	/*
+	 * we're pending, wait for the owner to go away.
+	 *
+	 * *,1,1 -> *,1,0
+	 */
+	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
+		cpu_relax();
+
+	/*
+	 * take ownership and clear the pending bit.
+	 *
+	 * *,1,0 -> *,0,1
+	 */
+	for (;;) {
+		new = (val & ~_Q_PENDING_MASK) | _Q_LOCKED_VAL;
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == val)
+			break;
+
+		val = old;
+	}
+	return;
+
+	/*
+	 * End of pending bit optimistic spinning and beginning of MCS
+	 * queuing.
+	 */
+queue:
 	node = this_cpu_ptr(&mcs_nodes[0]);
 	idx = node->count++;
 	tail = encode_tail(smp_processor_id(), idx);

@@ -119,15 +182,18 @@ void queue_spin_lock_slowpath(struct qsp
 	node->next = NULL;
 
 	/*
+	 * we already touched the queueing cacheline; don't bother with pending
+	 * stuff.
+	 *
 	 * trylock || xchg(lock, node)
 	 *
-	 * 0,0 -> 0,1 ; trylock
-	 * p,x -> n,x ; prev = xchg(lock, node)
+	 * 0,0,0 -> 0,0,1 ; trylock
+	 * p,y,x -> n,y,x ; prev = xchg(lock, node)
 	 */
 	for (;;) {
 		new = _Q_LOCKED_VAL;
 		if (val)
-			new = tail | (val & _Q_LOCKED_MASK);
+			new = tail | (val & _Q_LOCKED_PENDING_MASK);
 
 		old = atomic_cmpxchg(&lock->val, val, new);
 		if (old == val)

@@ -145,7 +211,7 @@ void queue_spin_lock_slowpath(struct qsp
 	/*
 	 * if there was a previous node; link it and wait.
 	 */
-	if (old & ~_Q_LOCKED_MASK) {
+	if (old & ~_Q_LOCKED_PENDING_MASK) {
 		prev = decode_tail(old);
 		ACCESS_ONCE(prev->next) = node;
 

@@ -153,18 +219,19 @@ void queue_spin_lock_slowpath(struct qsp
 	}
 
 	/*
-	 * we're at the head of the waitqueue, wait for the owner to go away.
+	 * we're at the head of the waitqueue, wait for the owner & pending to
+	 * go away.
 	 *
-	 * *,x -> *,0
+	 * *,x,y -> *,0,0
 	 */
-	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
+	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_PENDING_MASK)
 		cpu_relax();
 
 	/*
 	 * claim the lock:
 	 *
-	 * n,0 -> 0,1 : lock, uncontended
-	 * *,0 -> *,1 : lock, contended
+	 * n,0,0 -> 0,0,1 : lock, uncontended
+	 * *,0,0 -> *,0,1 : lock, contended
 	 */
 	for (;;) {
 		new = _Q_LOCKED_VAL;

Quoted 3 lines · Peter Zijlstra

Because the qspinlock needs to touch a second cacheline; add a pending bit and allow a single in-word spinner before we punt to the second cacheline.

Could you add this in the description please:

And by second cacheline we mean the local 'node'. That is the:
mcs_nodes[0] and mcs_nodes[idx]

Perhaps it might be better then to split this in the header file as this is trying to not be a slowpath code - but rather - a pre-slow-path-lets-try-if-we can do another cmpxchg in case the unlocker has just unlocked itself.

So something like:

include/asm-generic/qspinlock.h +1 -1

index e8a7ae8..29cc9c7 100644
@@ -75,11 +75,21 @@ extern void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val);
   */
  static __always_inline void queue_spin_lock(struct qspinlock *lock)
  {
-	u32 val;
+	u32 val, new;
 
  	val = atomic_cmpxchg(&lock->val, 0, _Q_LOCKED_VAL);

Quoted 27 lines · Konrad Rzeszutek Wilk

Quoted 3 lines · Peter Zijlstra

Because the qspinlock needs to touch a second cacheline; add a pending bit and allow a single in-word spinner before we punt to the second cacheline.

Could you add this in the description please:

And by second cacheline we mean the local 'node'. That is the:
mcs_nodes[0] and mcs_nodes[idx]

Perhaps it might be better then to split this in the header file as this is trying to not be a slowpath code - but rather - a pre-slow-path-lets-try-if-we can do another cmpxchg in case the unlocker has just unlocked itself.

So something like:

include/asm-generic/qspinlock.h +1 -1

index e8a7ae8..29cc9c7 100644
@@ -75,11 +75,21 @@ extern void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val);
  */
 static __always_inline void queue_spin_lock(struct qspinlock *lock)
 {
-	u32 val;
+	u32 val, new;
 

include/asm-generic/qspinlock.h extern void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val); · line 90

Quoted 11 lines

include/asm-generic/qspinlock.h +8 -0

 	val = atomic_cmpxchg(&lock->val, 0, _Q_LOCKED_VAL);
 	if (likely(val == 0))
 		return;
+
+	/* One more attempt - but if we fail mark it as pending. */
+	if (val == _Q_LOCKED_VAL) {
+		new = Q_LOCKED_VAL |_Q_PENDING_VAL;
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == _Q_LOCKED_VAL) /* YEEY! */
+			return;

No, it can leave like that. The unlock path will not clear the pending bit.

We are trying to make the fastpath as simple as possible as it may be inlined. The complexity of the queue spinlock is in the slowpath.

Moreover, an cmpxchg followed immediately followed by another cmpxchg will just increase the level of memory contention when a lock is fairly contended. The chance of second cmpxchg() succeeding will be pretty low.

-Longman

Quoted 28 lines · Waiman Long

Quoted 27 lines · Konrad Rzeszutek Wilk

Quoted 3 lines · Peter Zijlstra

Because the qspinlock needs to touch a second cacheline; add a pending bit and allow a single in-word spinner before we punt to the second cacheline.

Could you add this in the description please:

And by second cacheline we mean the local 'node'. That is the:
mcs_nodes[0] and mcs_nodes[idx]

Perhaps it might be better then to split this in the header file as this is trying to not be a slowpath code - but rather - a pre-slow-path-lets-try-if-we can do another cmpxchg in case the unlocker has just unlocked itself.

So something like:

include/asm-generic/qspinlock.h +1 -1

index e8a7ae8..29cc9c7 100644
@@ -75,11 +75,21 @@ extern void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val);
  */
 static __always_inline void queue_spin_lock(struct qspinlock *lock)
 {
-	u32 val;
+	u32 val, new;
 

Quoted 13 lines

include/asm-generic/qspinlock.h extern void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val); · line 90

Quoted 11 lines

include/asm-generic/qspinlock.h +8 -0

 	val = atomic_cmpxchg(&lock->val, 0, _Q_LOCKED_VAL);
 	if (likely(val == 0))
 		return;
+
+	/* One more attempt - but if we fail mark it as pending. */
+	if (val == _Q_LOCKED_VAL) {
+		new = Q_LOCKED_VAL |_Q_PENDING_VAL;
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == _Q_LOCKED_VAL) /* YEEY! */
+			return;

No, it can leave like that. The unlock path will not clear the pending bit.

Err, you are right. It needs to go back in the slowpath.

Quoted 3 lines

We are trying to make the fastpath as simple as possible as it may be inlined. The complexity of the queue spinlock is in the slowpath.

Sure, but then it shouldn't be called slowpath anymore as it is not slow. It is a combination of fast path (the potential chance of grabbing the lock and setting the pending lock) and the real slow path (the queuing). Perhaps it should be called 'queue_spinlock_complex' ?

Quoted 4 lines

Moreover, an cmpxchg followed immediately followed by another cmpxchg will just increase the level of memory contention when a lock is fairly contended. The chance of second cmpxchg() succeeding will be pretty low.

Then why even do the pending bit - which is what the slowpath does for the first time. And if it grabs it (And sets the pending bit) it immediately exits. Why not perculate that piece of code in-to this header.

And the leave all that slow code (queing, mcs_lock access, etc) in the slowpath.

Quoted 4 lines

-Longman

Quoted 41 lines · Konrad Rzeszutek Wilk

Quoted 40 lines · Waiman Long

Quoted 28 lines · Konrad Rzeszutek Wilk

Quoted 3 lines · Peter Zijlstra

Because the qspinlock needs to touch a second cacheline; add a pending bit and allow a single in-word spinner before we punt to the second cacheline.

Could you add this in the description please:

And by second cacheline we mean the local 'node'. That is the:
mcs_nodes[0] and mcs_nodes[idx]

Perhaps it might be better then to split this in the header file as this is trying to not be a slowpath code - but rather - a pre-slow-path-lets-try-if-we can do another cmpxchg in case the unlocker has just unlocked itself.

So something like:

include/asm-generic/qspinlock.h +1 -1

index e8a7ae8..29cc9c7 100644
@@ -75,11 +75,21 @@ extern void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val);
   */
  static __always_inline void queue_spin_lock(struct qspinlock *lock)
  {
-	u32 val;
+	u32 val, new;
 
  	val = atomic_cmpxchg(&lock->val, 0, _Q_LOCKED_VAL);

include/asm-generic/qspinlock.h extern void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val); · line 90

Quoted 10 lines

include/asm-generic/qspinlock.h +8 -0

  	if (likely(val == 0))
  		return;
+
+	/* One more attempt - but if we fail mark it as pending. */
+	if (val == _Q_LOCKED_VAL) {
+		new = Q_LOCKED_VAL |_Q_PENDING_VAL;
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == _Q_LOCKED_VAL) /* YEEY! */
+			return;

No, it can leave like that. The unlock path will not clear the pending bit.

Quoted 1 line

Err, you are right. It needs to go back in the slowpath.

What I should have wrote is:

if (old == 0) /* YEEY */
return;

As that would the same thing as this patch does on the pending bit - that is if we can on the second compare and exchange set the pending bit (and the lock) and the lock has been released - we are good.

And it is a quick path.

Quoted 2 lines

Quoted 2 lines

We are trying to make the fastpath as simple as possible as it may be inlined. The complexity of the queue spinlock is in the slowpath.

Quoted 5 lines

Sure, but then it shouldn't be called slowpath anymore as it is not slow. It is a combination of fast path (the potential chance of grabbing the lock and setting the pending lock) and the real slow path (the queuing). Perhaps it should be called 'queue_spinlock_complex' ?

I forgot to mention - that was the crux of my comments - just change the slowpath to complex name at that point to better reflect what it does.

Quoted 41 lines · Konrad Rzeszutek Wilk

Quoted 40 lines · Waiman Long

Quoted 28 lines · Konrad Rzeszutek Wilk

Quoted 3 lines · Peter Zijlstra

Because the qspinlock needs to touch a second cacheline; add a pending bit and allow a single in-word spinner before we punt to the second cacheline.

Could you add this in the description please:

And by second cacheline we mean the local 'node'. That is the:
mcs_nodes[0] and mcs_nodes[idx]

Perhaps it might be better then to split this in the header file as this is trying to not be a slowpath code - but rather - a pre-slow-path-lets-try-if-we can do another cmpxchg in case the unlocker has just unlocked itself.

So something like:

include/asm-generic/qspinlock.h +1 -1

index e8a7ae8..29cc9c7 100644
@@ -75,11 +75,21 @@ extern void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val);
   */
  static __always_inline void queue_spin_lock(struct qspinlock *lock)
  {
-	u32 val;
+	u32 val, new;
 
  	val = atomic_cmpxchg(&lock->val, 0, _Q_LOCKED_VAL);

include/asm-generic/qspinlock.h extern void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val); · line 90

Quoted 10 lines

include/asm-generic/qspinlock.h +8 -0

  	if (likely(val == 0))
  		return;
+
+	/* One more attempt - but if we fail mark it as pending. */
+	if (val == _Q_LOCKED_VAL) {
+		new = Q_LOCKED_VAL |_Q_PENDING_VAL;
+
+		old = atomic_cmpxchg(&lock->val, val, new);
+		if (old == _Q_LOCKED_VAL) /* YEEY! */
+			return;

No, it can leave like that. The unlock path will not clear the pending bit.

Quoted 1 line

Err, you are right. It needs to go back in the slowpath.

What I should have wrote is:

if (old == 0) /* YEEY */
return;