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]>
---
include/asm-generic/qspinlock.h | 118 ++++++++++++++++++++
include/asm-generic/qspinlock_types.h | 61 ++++++++++
kernel/Kconfig.locks | 7 +
kernel/locking/Makefile | 1
kernel/locking/mcs_spinlock.h | 1
kernel/locking/qspinlock.c | 197 ++++++++++++++++++++++++++++++++++
6 files changed, 385 insertions(+)
create mode 100644 include/asm-generic/qspinlock.h
create mode 100644 include/asm-generic/qspinlock_types.h
create mode 100644 kernel/locking/qspinlock.c
Index: linux-2.6/include/asm-generic/qspinlock.h
===================================================================
--- /dev/null
+++ linux-2.6/include/asm-generic/qspinlock.h
@@ -0,0 +1,118 @@
+/*
+ * 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]>
+ */
+#ifndef __ASM_GENERIC_QSPINLOCK_H
+#define __ASM_GENERIC_QSPINLOCK_H
+
+#include <asm-generic/qspinlock_types.h>
+
+/**
+ * queue_spin_is_locked - is the spinlock locked?
+ * @lock: Pointer to queue spinlock structure
+ * Return: 1 if it is locked, 0 otherwise
+ */
+static __always_inline int queue_spin_is_locked(struct qspinlock *lock)
+{
+ return atomic_read(&lock->val);
+}
+
+/**
+ * queue_spin_value_unlocked - is the spinlock structure unlocked?
+ * @lock: queue spinlock structure
+ * Return: 1 if it is unlocked, 0 otherwise
+ *
+ * N.B. Whenever there are tasks waiting for the lock, it is considered
+ * locked wrt the lockref code to avoid lock stealing by the lockref
+ * code and change things underneath the lock. This also allows some
+ * optimizations to be applied without conflict with lockref.
+ */
+static __always_inline int queue_spin_value_unlocked(struct qspinlock lock)
+{
+ return !atomic_read(&lock.val);
+}
+
+/**
+ * queue_spin_is_contended - check if the lock is contended
+ * @lock : Pointer to queue spinlock structure
+ * Return: 1 if lock contended, 0 otherwise
+ */
+static __always_inline int queue_spin_is_contended(struct qspinlock *lock)
+{
+ return atomic_read(&lock->val) & ~_Q_LOCKED_MASK;
+}
+/**
+ * queue_spin_trylock - try to acquire the queue spinlock
+ * @lock : Pointer to queue spinlock structure
+ * Return: 1 if lock acquired, 0 if failed
+ */
+static __always_inline int queue_spin_trylock(struct qspinlock *lock)
+{
+ if (!atomic_read(&lock->val) &&
+ (atomic_cmpxchg(&lock->val, 0, _Q_LOCKED_VAL) == 0))
+ return 1;
+ return 0;
+}
+
+extern void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val);
+
+/**
+ * queue_spin_lock - acquire a queue spinlock
+ * @lock: Pointer to queue spinlock structure
+ */
+static __always_inline void queue_spin_lock(struct qspinlock *lock)
+{
+ u32 val;
+
+ val = atomic_cmpxchg(&lock->val, 0, _Q_LOCKED_VAL);
+ if (likely(val == 0))
+ return;
+ queue_spin_lock_slowpath(lock, val);
+}
+
+#ifndef queue_spin_unlock
+/**
+ * queue_spin_unlock - release a queue spinlock
+ * @lock : Pointer to queue spinlock structure
+ */
+static __always_inline void queue_spin_unlock(struct qspinlock *lock)
+{
+ /*
+ * smp_mb__before_atomic() in order to guarantee release semantics
+ */
+ smp_mb__before_atomic_dec();
+ atomic_sub(_Q_LOCKED_VAL, &lock->val);
+}
+#endif
+
+/*
+ * Initializier
+ */
+#define __ARCH_SPIN_LOCK_UNLOCKED { ATOMIC_INIT(0) }
+
+/*
+ * Remapping spinlock architecture specific functions to the corresponding
+ * queue spinlock functions.
+ */
+#define arch_spin_is_locked(l) queue_spin_is_locked(l)
+#define arch_spin_is_contended(l) queue_spin_is_contended(l)
+#define arch_spin_value_unlocked(l) queue_spin_value_unlocked(l)
+#define arch_spin_lock(l) queue_spin_lock(l)
+#define arch_spin_trylock(l) queue_spin_trylock(l)
+#define arch_spin_unlock(l) queue_spin_unlock(l)
+#define arch_spin_lock_flags(l, f) queue_spin_lock(l)
+
+#endif /* __ASM_GENERIC_QSPINLOCK_H */
Index: linux-2.6/include/asm-generic/qspinlock_types.h
===================================================================
--- /dev/null
+++ linux-2.6/include/asm-generic/qspinlock_types.h
@@ -0,0 +1,61 @@
+/*
+ * 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]>
+ */
+#ifndef __ASM_GENERIC_QSPINLOCK_TYPES_H
+#define __ASM_GENERIC_QSPINLOCK_TYPES_H
+
+/*
+ * Including atomic.h with PARAVIRT on will cause compilation errors because
+ * of recursive header file incluson via paravirt_types.h. A workaround is
+ * to include paravirt_types.h here.
+ */
+#ifdef CONFIG_PARAVIRT
+#include <asm/paravirt_types.h>
+#else
+#include <linux/types.h>
+#include <linux/atomic.h>
+#include <linux/bug.h>
+#endif
+
+typedef struct qspinlock {
+ atomic_t val;
+} arch_spinlock_t;
+
+/*
+ * Bitfields in the atomic value:
+ *
+ * 0- 7: locked byte
+ * 8- 9: tail index
+ * 10-31: tail cpu (+1)
+ */
+#define _Q_SET_MASK(type) (((1U << _Q_ ## type ## _BITS) - 1)\
+ << _Q_ ## type ## _OFFSET)
+#define _Q_LOCKED_OFFSET 0
+#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_TAIL_IDX_BITS 2
+#define _Q_TAIL_IDX_MASK _Q_SET_MASK(TAIL_IDX)
+
+#define _Q_TAIL_CPU_OFFSET (_Q_TAIL_IDX_OFFSET + _Q_TAIL_IDX_BITS)
+#define _Q_TAIL_CPU_BITS (32 - _Q_TAIL_CPU_OFFSET)
+#define _Q_TAIL_CPU_MASK _Q_SET_MASK(TAIL_CPU)
+
+#define _Q_LOCKED_VAL (1U << _Q_LOCKED_OFFSET)
+
+#endif /* __ASM_GENERIC_QSPINLOCK_TYPES_H */
Index: linux-2.6/kernel/Kconfig.locks
===================================================================
--- linux-2.6.orig/kernel/Kconfig.locks
+++ linux-2.6/kernel/Kconfig.locks
@@ -224,6 +224,13 @@ config MUTEX_SPIN_ON_OWNER
def_bool y
depends on SMP && !DEBUG_MUTEXES && !PARISC
+config ARCH_USE_QUEUE_SPINLOCK
+ bool
+
+config QUEUE_SPINLOCK
+ def_bool y if ARCH_USE_QUEUE_SPINLOCK
+ depends on SMP && !PARAVIRT_SPINLOCKS
+
config ARCH_USE_QUEUE_RWLOCK
bool
Index: linux-2.6/kernel/locking/Makefile
===================================================================
--- linux-2.6.orig/kernel/locking/Makefile
+++ linux-2.6/kernel/locking/Makefile
@@ -16,6 +16,7 @@ endif
obj-$(CONFIG_SMP) += spinlock.o
obj-$(CONFIG_SMP) += lglock.o
obj-$(CONFIG_PROVE_LOCKING) += spinlock.o
+obj-$(CONFIG_QUEUE_SPINLOCK) += qspinlock.o
obj-$(CONFIG_RT_MUTEXES) += rtmutex.o
obj-$(CONFIG_DEBUG_RT_MUTEXES) += rtmutex-debug.o
obj-$(CONFIG_RT_MUTEX_TESTER) += rtmutex-tester.o
Index: linux-2.6/kernel/locking/mcs_spinlock.h
===================================================================
--- linux-2.6.orig/kernel/locking/mcs_spinlock.h
+++ linux-2.6/kernel/locking/mcs_spinlock.h
@@ -17,6 +17,7 @@
struct mcs_spinlock {
struct mcs_spinlock *next;
int locked; /* 1 if lock acquired */
+ int count;
};
#ifndef arch_mcs_spin_lock_contended
Index: linux-2.6/kernel/locking/qspinlock.c
===================================================================
--- /dev/null
+++ linux-2.6/kernel/locking/qspinlock.c
@@ -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]);
+
+/*
+ * We must be able to distinguish between no-tail and the tail at 0:0,
+ * therefore increment the cpu number by one.
+ */
+
+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 */
+
+ 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;
+
+ return per_cpu_ptr(&mcs_nodes[idx], cpu);
+}
+
+/**
+ * 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 : ^--' :
+ *
+ */
+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++;
+ tail = encode_tail(smp_processor_id(), idx);
+
+ node += idx;
+ node->locked = 0;
+ node->next = NULL;
+
+ /*
+ * trylock || xchg(lock, node)
+ *
+ * 0,0 -> 0,1 ; trylock
+ * p,x -> n,x ; prev = xchg(lock, node)
+ */
+ for (;;) {
+ new = _Q_LOCKED_VAL;
+ if (val)
+ 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
+ */
+ for (;;) {
+ new = _Q_LOCKED_VAL;
+ if (val != tail)
+ new |= val;
+
+ old = atomic_cmpxchg(&lock->val, val, new);
+ if (old == val)
+ break;
+
+ val = old;
+ }
+
+ /*
+ * contended path; wait for next, release.
+ */
+ if (new != _Q_LOCKED_VAL) {
+ 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);
On Sun, Jun 15, 2014 at 02:46:58PM +0200, Peter Zijlstra wrote:
> 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]>
Thank you for the repost. I have some questions about the implementation
that hopefully will be easy to answer and said answers I hope can
be added in the code to enlighten other folks.
See below.
.. snip..
> Index: linux-2.6/kernel/locking/mcs_spinlock.h
> ===================================================================
> --- linux-2.6.orig/kernel/locking/mcs_spinlock.h
> +++ linux-2.6/kernel/locking/mcs_spinlock.h
> @@ -17,6 +17,7 @@
> struct mcs_spinlock {
> struct mcs_spinlock *next;
> int locked; /* 1 if lock acquired */
> + int count;
This could use a comment.
> };
>
> #ifndef arch_mcs_spin_lock_contended
> Index: linux-2.6/kernel/locking/qspinlock.c
> ===================================================================
> --- /dev/null
> +++ linux-2.6/kernel/locking/qspinlock.c
> @@ -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]);
> +
> +/*
> + * We must be able to distinguish between no-tail and the tail at 0:0,
> + * therefore increment the cpu number by one.
> + */
> +
> +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).
> +
> + 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;
> +
> + return per_cpu_ptr(&mcs_nodes[idx], cpu);
> +}
> +
> +/**
> + * 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'?
> + *
> + * 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?
> + * 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?
> + *
> + */
> +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?
> + 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?
> + 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)
> + */
> + 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. */
*/
> + 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
> + */
> + 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?
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?
> +
> + 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?
Thanks!
> + 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);
>
>
> > + 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);
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. */
> > + }
> > +
> > + /*
> > + * 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;
>
..snip..
>
> 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).
*/
> + * 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.
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?
Thanks.
On Mon, Jun 16, 2014 at 04:49:18PM -0400, Konrad Rzeszutek Wilk wrote:
> > Index: linux-2.6/kernel/locking/mcs_spinlock.h
> > ===================================================================
> > --- linux-2.6.orig/kernel/locking/mcs_spinlock.h
> > +++ linux-2.6/kernel/locking/mcs_spinlock.h
> > @@ -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 */
> > +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).
#ifdef CONFIG_DEBUG_SPINLOCK
BUG_ON(idx > 3);
#endif
might do, I suppose.
> > +/**
> > + * 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.
It is indeed, although that's an accident of implementation. I could do
s/bit// and not mention the entire storage angle at all?
> Is the queue tail at this point the composite of 'cpu|idx'?
Yes, as per {en,de}code_tail() above.
> > + *
> > + * 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).
> > + * 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?
'*' as in wildcard, any tail, specifically not 'n'.
> > +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.
> > + 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.
> > + 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)
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.
> > + */
> > + 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. */
> */
The idea was that:
0,0 -> 0,1
p,x -> n,x
Completely covers what this composite atomic does.
> > + 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
> > + */
> > + 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:
> > + 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.
> 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.
> > +
> > + 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?
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.
On Tue, Jun 17, 2014 at 04:03:29PM -0400, Konrad Rzeszutek Wilk wrote:
> > > + 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);
>
> 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. */
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./ ?
> > > + /*
> > > + * claim the lock:
> > > + *
> > > + * n,0 -> 0,1 : lock, uncontended
> > > + * *,0 -> *,1 : lock, contended
> > > + */
> > > + for (;;) {
> > > + new = _Q_LOCKED_VAL;
> > > + if (val != tail)
> > > + new |= val;
> >
> ..snip..
> >
> > 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.
> 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 :/
> 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.
> 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.
On Tue, Jun 17, 2014 at 04:05:31PM -0400, Konrad Rzeszutek Wilk wrote:
> > + * 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.
>
> 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?
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.
On Mon, Jun 23, 2014 at 05:56:50PM +0200, Peter Zijlstra wrote:
> On Mon, Jun 16, 2014 at 04:49:18PM -0400, Konrad Rzeszutek Wilk wrote:
> > > Index: linux-2.6/kernel/locking/mcs_spinlock.h
> > > ===================================================================
> > > --- linux-2.6.orig/kernel/locking/mcs_spinlock.h
> > > +++ linux-2.6/kernel/locking/mcs_spinlock.h
> > > @@ -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 */
/* nested level - in user, softirq, hard irq or nmi context. */ ?
>
>
> > > +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).
>
> #ifdef CONFIG_DEBUG_SPINLOCK
> BUG_ON(idx > 3);
> #endif
>
> might do, I suppose.
<nods>
>
> > > +/**
> > > + * 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.
>
> It is indeed, although that's an accident of implementation. I could do
> s/bit// and not mention the entire storage angle at all?
I think giving as much details as possible is good.
What you said 'accident of implementation' is a could be woven
in there?
>
> > Is the queue tail at this point the composite of 'cpu|idx'?
>
> Yes, as per {en,de}code_tail() above.
>
> > > + *
> > > + * 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).
>
> > > + * 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?
>
> '*' as in wildcard, any tail, specifically not 'n'.
Ah, thank you for the explanation! Would it be possible to include
that in the comment please?
>
> > > +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.
<blushes> Yes it does.
>
> > > + 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.
I've no idea what I was thinking, but thank you for setting me straight.
>
> > > + 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)
>
> 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.
Oh this is good!
>
> > > + */
> > > + 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. */
> > */
>
> The idea was that:
>
> 0,0 -> 0,1
> p,x -> n,x
>
> Completely covers what this composite atomic does.
>
> > > + 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
> > > + */
> > > + 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:
>
> > > + 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.
>
> > 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.
>
> > > +
> > > + 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?
>
> 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.
<nods>
>
> 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.
Thank you for your detailed explanation!
On Mon, Jun 23, 2014 at 06:26:22PM +0200, Peter Zijlstra wrote:
> On Tue, Jun 17, 2014 at 04:05:31PM -0400, Konrad Rzeszutek Wilk wrote:
> > > + * 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.
> >
> > 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?
>
> I _think_ I know what you mean.. So that is actually implied by the last
You do :-)
> 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.
>
>
On Mon, Jun 23, 2014 at 06:12:00PM +0200, Peter Zijlstra wrote:
> On Tue, Jun 17, 2014 at 04:03:29PM -0400, Konrad Rzeszutek Wilk wrote:
> > > > + 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);
> >
> > 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. */
>
> 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./ ?
Yes!
>
> > > > + /*
> > > > + * claim the lock:
> > > > + *
> > > > + * n,0 -> 0,1 : lock, uncontended
> > > > + * *,0 -> *,1 : lock, contended
> > > > + */
> > > > + for (;;) {
> > > > + new = _Q_LOCKED_VAL;
> > > > + if (val != tail)
> > > > + new |= val;
> > >
> > ..snip..
> > >
> > > 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.
>
> > 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 :/
s/ticket/be first in line/ ?
>
> > 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.
>
> > 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.
<nods>
>
> ---
>
> I don't do well with natural language comments like that; they tend to
> confuse me more than anything.
>