fast queue spinlocks

I would like to propose a fast queue spinlock implementation, which could be used on selected spinlocks instead of the default ticket spinlock.

I understand that in the past, such proposals have been defeated by two main arguments:
- That it is generally preferable to use smart algorithms that can avoid lock contention altogether, rather than spending effort on the lock itself to deal with the contention, and
- That the lightly contended case matters more to real workloads than the highly contended case, and that the most well known scalable spinlock algorithms tend to be relatively slow in the lightly contended case.

I am hoping for a different result this time around based on the following counter-arguments:
- There are situations where the lock contention is directly driven by user events, with little opportunity to reduce it in-kernel. One example might be when the user requests that the kernel acquires or releases semaphores on its behalf using sysv IPC APIs - it is hard to imagine how the kernel could mitigate spinlock contention issues for the user.
- More importantly, the queue spinlock implementation I am proposing seems to behave well both under light and heavy contention. It uses one single atomic opearation on the lock side, and (on x86) only a single memory store on the unlock side, with fairly short code sections on both sides, and just compares well with the ticket spinlock on the benchmarks I have tried.
To be clear, I am not proposing replacing every ticket spinlock usage with queue spinlocks; I am only proposing to have both APIs available and pick them as appropriate for each use case.

In order to have concrete examples, I have converted two spinlocks to the proposed queue spinlock API:
- The IPC object spinlock, which protects each individually allocated IPC message queue, IPC shared memory segment or IPC semaphore array.
- The network qdisc busylock, which if I understand correctly seems to be a way to prevent multiple network writers starving the thread that wants to actually dequeue packets to send them on the wire.
I picked these two locks because I knew of situations where they get contended; additionally I wanted to have examples of one lock that gets taken in process context and one that can be taken in softirq context, in order to demonstrate that the proposed spinlock can deal with the resulting reentrancy issues. I am not very familiar with either the sysv IPC or the networking code, however I know that these areas have been looked at by competent people so I assume there are no obvious ways to avoid contention on these two spinlocks (but feel free to propose better examples if I'm wrong :)

The first 3 patches are a bit of a strawman, as they introduce a classic MCS queue lock implementation and convert the IPC and qdisc spinlocks to use the corresponding locking API. I expect this might be rejected since MCS spinlocks have some higher cost than ticket based ones under light contention; however I consider this a useful step as it lets us implement most of the mechanical changes to convert our two spinlocks to the proposed queue spinlock API.

Patch 4 implements my proposed fast queue spinlock algorithm, which seems to performs better than MCS at all contention levels and is competitive with ticket spinlocks at low contention levels. This comes with a few limitations, mostly due to the fact that spinlocks must point to a dynamically allocated ticket structure - so they can't have a static initializer, they may be inappropriate for short lived objects, the init function may fail, and they need to be explicitly destroyed before the object they're in is freed.

Patches 5-6 convert the IPC and qdisc spinlocks to deal with the API limitations introduced by the fast queue spinlock algorithm in patch 4.

Michel Lespinasse (6):
kernel: implement queue spinlock API
net: convert qdisc busylock to use queue spinlock API
ipc: convert ipc objects to use queue spinlock API
kernel: faster queue spinlock implementation
net: qdisc busylock updates to account for queue spinlock api change
ipc: object locking updates to account for queue spinlock api change

 arch/x86/include/asm/queue_spinlock.h |   20 +++++
 include/asm-generic/queue_spinlock.h  |    7 ++
 include/linux/ipc.h                   |    9 +--
 include/linux/msg.h                   |    2 +-
 include/linux/queue_spinlock.h        |  113 +++++++++++++++++++++++++++++
 include/linux/shm.h                   |    2 +-
 include/net/sch_generic.h             |    3 +-
 init/main.c                           |    2 +
 ipc/msg.c                             |   61 +++++++++-------
 ipc/namespace.c                       |    8 ++-
 ipc/sem.c                             |  115 +++++++++++++++++-------------
 ipc/shm.c                             |   95 ++++++++++++++-----------
 ipc/util.c                            |  122 +++++++++++++++++++++-----------
 ipc/util.h                            |   25 ++++---
 kernel/Makefile                       |    2 +-
 kernel/queue_spinlock.c               |  125 +++++++++++++++++++++++++++++++++
 net/core/dev.c                        |    9 ++-
 net/sched/sch_generic.c               |   19 +++--
 18 files changed, 546 insertions(+), 193 deletions(-)
 create mode 100644 arch/x86/include/asm/queue_spinlock.h
 create mode 100644 include/asm-generic/queue_spinlock.h
 create mode 100644 include/linux/queue_spinlock.h
 create mode 100644 kernel/queue_spinlock.c

Now for the obligatory benchmarks:

First, testing IPC locking using rik's semop_test benchmark:

On 4 socket AMD Barcelona system (16 cores total):
1 thread (no contention): ~5.38 Mop/s queue spinlock vs ~5.45 baseline (-1%)

2 threads:                ~1.47 Mop/s queue spinlock vs ~1.48 baseline
4 threads:                ~1.57 Mop/s queue spinlock vs ~1.21 baseline (+30%)
8 threads:                ~1.41 Mop/s queue spinlock vs ~0.83 baseline (+70%)
16 threads:               ~1.40 Mop/s queue spinlock vs ~0.47 baseline (+200%)

For comparison, rik's proportional backoff (v3) gets ~1.18 Mop/s at 16 threads

On 2 socket Intel Sandybridge system (16 cores / 32 threads total):
1 thread (no contention): ~8.36 Mop/s queue spinlock vs ~8.25 baseline (+1%) 2 threads: results are noisy there, from ~5 to ~6.5 Mops/s with either trees 4 threads: ~4.5 to ~5.8 Mops/s queue spinlock (noisy), ~5.5 baseline 8 threads: ~4.3 to ~5 Mops/s queue spinlock, ~4.1 to ~4.2 baseline 16 threads: ~3.2 to ~3.6 Mops/s queue spinlock, ~1.5 to ~2.4 baseline 32 threads: ~2.7 to ~3.2 Mops/s queue spinlock, ~1.5 to ~1.9 baseline For comparison, rik's proposal gets ~1.75 to ~2.1 at 32 threads

Basically for semop_test, the data is noisy on one of the test machines but the queue spinlock is never measurably slower than the ticket spinlock, except by 1% in the uncontended case on the AMD system (and it's 1% faster in the uncontended case on the other system, so I'd call it a draw :)

32 instances of netperf -t UDP_STREAM -H <server> -- -m 128 on a 32 hypercores machine (2 sandybridge sockets) and htb root qdisc:
~650 to ~680 Mbps total with baseline 3.7
~895 to ~915 Mbps total with fast queue spinlock
~860 to ~890 Mbps total with rik's proportional backoff (v3)

Additionally I will attach (as a reply to this email) graphs showing total spinlock throughput for a microbenchmark consisting of N threads doing lock/unlock operations in a tight loop. We can see that the proposed fast queue spinlock is comparable to ticket spinlocks for low number of threads, scales much better for high number of threads, and is always faster than the MCS strawman proposal (which did have the issue of being kinda slow at around 2-3 threads).
mach1 is a 4 socket AMD Barcelona system (16 cores total) mach2 is a 2 socket Intel Westmere system (12 cores / 24 threads total) mach3 is a 2 socket Intel Sandybridge system (16 cores / 32 threads total)

1.7.7.3

Introduce queue spinlocks, to be used in situations where it is desired to have good throughput even under the occasional high-contention situation.

This initial implementation is based on the classic MCS spinlock, because I think this represents the nicest API we can hope for in a fast queue spinlock algorithm. The MCS spinlock has known limitations in that it performs very well under high contention, but is not as good as the ticket spinlock under low contention. I will address these limitations in a later patch, which will propose an alternative, higher performance implementation using (mostly) the same API.

Sample use case acquiring mystruct->lock:

struct q_spinlock_node node;

  q_spin_lock(&mystruct->lock, &node);
  ...
  q_spin_unlock(&mystruct->lock, &node);

The q_spinlock_node must be used by a single lock holder / waiter and it must stay allocated for the entire duration when the lock is held (or waited on).

---
 arch/x86/include/asm/queue_spinlock.h |   20 ++++++++
 include/asm-generic/queue_spinlock.h  |    7 +++
 include/linux/queue_spinlock.h        |   61 ++++++++++++++++++++++++
 kernel/Makefile                       |    2 +-
 kernel/queue_spinlock.c               |   82 +++++++++++++++++++++++++++++++++
 5 files changed, 171 insertions(+), 1 deletions(-)
 create mode 100644 arch/x86/include/asm/queue_spinlock.h
 create mode 100644 include/asm-generic/queue_spinlock.h
 create mode 100644 include/linux/queue_spinlock.h
 create mode 100644 kernel/queue_spinlock.c

new file mode 100644
index 000000000000..655e01c1c2e8
@@ -0,0 +1,20 @@
+#ifndef _ASM_QUEUE_SPINLOCK_H
+#define _ASM_QUEUE_SPINLOCK_H
+
+#if defined(CONFIG_X86_PPRO_FENCE) || defined(CONFIG_X86_OOSTORE)
+
+#define q_spin_lock_mb() mb()
+#define q_spin_unlock_mb() mb()
+
+#else
+
+/*
+ * x86 memory ordering only needs compiler barriers to implement
+ * acquire load / release store semantics
+ */
+#define q_spin_lock_mb() barrier()
+#define q_spin_unlock_mb() barrier()
+
+#endif
+
+#endif /* _ASM_QUEUE_SPINLOCK_H */

new file mode 100644
index 000000000000..01fb9fbfb8dc
@@ -0,0 +1,7 @@
+#ifndef _ASM_GENERIC_QUEUE_SPINLOCK_H
+#define _ASM_GENERIC_QUEUE_SPINLOCK_H
+
+#define q_spin_lock_mb() mb()
+#define q_spin_unlock_mb() mb()
+
+#endif /* _ASM_GENERIC_QUEUE_SPINLOCK_H */

index 86e3285ae7e5..ec91cfef4d4e 100644
@@ -49,7 +49,7 @@ obj-$(CONFIG_SMP) += smp.o
 ifneq ($(CONFIG_SMP),y)
 obj-y += up.o
 endif
-obj-$(CONFIG_SMP) += spinlock.o
+obj-$(CONFIG_SMP) += spinlock.o queue_spinlock.o
 obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock.o
 obj-$(CONFIG_PROVE_LOCKING) += spinlock.o
 obj-$(CONFIG_UID16) += uid16.o

1.7.7.3

It is possible to keep the normal API for MCS locks by having the lock holder remember the parameter in the lock word itself. While spinning, the node is on the stack, is not needed once the lock is acquired. The pointer to the next node in the queue -is- needed, but this can be stored in the lock word.

I believe that John Stultz worked on something like this some years back, so added him to CC.

Thanx, Paul

Hmm...

This could easily break if the spin_lock() is embedded in a function, and the unlock done in another one.

(storage for the node would disappear at function epilogue )

But that is OK -- the storage is used only for spinning on. Once a given task has actually acquired the lock, that storage is no longer needed. What -is- needed is the pointer to the next CPU's node, and that node is guaranteed to persist until the next CPU acquires the lock, which cannot happen until this CPU releases that lock.

Thanx, Paul

No, I think that's doable. The trick would be that once a thread acquires the lock, the only remaining use of the node is to receive the 'next' pointer if/when another thread starts contending for the lock. So if the lock state would need to distinguish between a lock that is currently locked but not contended (the next value would then be NULL), and a lock that is currently locked and contended (the lock->next value is the node that goes after the current lock owner)

Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

It adds yet another memory write to store the node pointer in the lock...

I suspect it's going to increase false sharing.

On the other hand, compared to straight MCS, it reduces the need to pass the node address around. Furthermore, the node pointer is likely to be in the same cache line as the lock word itself, and finally some architectures can do a double-pointer store.

Of course, it might well be slower, but it seems like it is worth giving it a try.

Thanx, Paul

Right. Another nice point about this approach is that there needs to be only one node per spinning CPU, so the node pointers (both tail and next) might be replaced with CPU identifiers, which would bring the spinlock size down to the same as with the ticket spinlock (which in turns makes it that much more likely that we'll have atomic stores of that size).

Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Good point! I must admit that this is one advantage of having the various _irq spinlock acquisition primitives disable irqs before spinning. ;-)

Thanx, Paul

Right... For spinlocks that -don't- disable irqs, you need to deal with the possibility that a CPU gets interrupted while spinning, and the interrupt handler also tries to acquire a queued lock. One way to deal with this is to have a node per CPUxirq. Of course, if interrupts handlers always disable irqs when acquiring a spinlock, then you only need CPUx2.

Thanx, Paul

The simple solution would be to do like I proposed in my faster queue spinlock proposal, have one function for process context lock acquisitions, another for bh-disabled acquisitions, and just say that hardirqs can't use the queue spinlocks (I don't expect we have any locks taken from hardirq context where contention might be an issue ?)

Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Makes sense! The spinlocks that disable hardirqs should get extra contention-reduction attention, after which the main benefit for queued spinlocks is process-level spinlocks.

Thanx, Paul

Oh yea, its been quite awhile.

Here are some of the discussion threads google remembers for me:

http://marc.info/?l=lse-tech&m=101227079817027&w=2

http://marc.info/?l=lse-tech&m=101380783015065&w=2 (missing the patch)

    http://marc.info/?l=lse-tech&m=101380783615084&w=2 (patch for above)

thanks
-john

While we're talking about MCS spinlocks, I should point out a potential issue I found about my 'faster queue spinlock' proposed MCS alternative. It is nice in that it avoids an atomic operation in the unlock path; however each unlocked lock must have a 'token' allocated and this token is accessed by the lock function. The issue with this is that if two threads don't actually block on each other, but they both access a lock that bounces between them, now the token will have to bounce between these threads as well, which is going to be more expansive than the atomic operation that was saved.

Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Convert qdisc busylock to use the proposed queue spinlock API.

---
 include/net/sch_generic.h |    3 ++-
 net/core/dev.c            |    9 +++++----
 net/sched/sch_generic.c   |   10 +++-------
 3 files changed, 10 insertions(+), 12 deletions(-)

index 4616f468d599..456c06581a57 100644
@@ -6,6 +6,7 @@
 #include <linux/rcupdate.h>
 #include <linux/pkt_sched.h>
 #include <linux/pkt_cls.h>
+#include <linux/queue_spinlock.h>
 #include <net/gen_stats.h>
 #include <net/rtnetlink.h>
 

@@ -81,7 +82,7 @@ struct Qdisc {
 	unsigned int		__state;
 	struct gnet_stats_queue	qstats;
 	struct rcu_head		rcu_head;
-	spinlock_t		busylock;
+	struct q_spinlock	busylock;
 	u32			limit;
 };
 

index e5942bf45a6d..058c984cd024 100644
@@ -2440,6 +2440,7 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 {
 	spinlock_t *root_lock = qdisc_lock(q);
 	bool contended;
+	struct q_spinlock_node busylock_node;
 	int rc;
 
 	qdisc_skb_cb(skb)->pkt_len = skb->len;

@@ -2452,7 +2453,7 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 	 */
 	contended = qdisc_is_running(q);
 	if (unlikely(contended))
-		spin_lock(&q->busylock);
+		q_spin_lock(&q->busylock, &busylock_node);
 
 	spin_lock(root_lock);
 	if (unlikely(test_bit(__QDISC_STATE_DEACTIVATED, &q->state))) {

@@ -2472,7 +2473,7 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 
 		if (sch_direct_xmit(skb, q, dev, txq, root_lock)) {
 			if (unlikely(contended)) {
-				spin_unlock(&q->busylock);
+				q_spin_unlock(&q->busylock, &busylock_node);
 				contended = false;
 			}
 			__qdisc_run(q);

@@ -2485,7 +2486,7 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 		rc = q->enqueue(skb, q) & NET_XMIT_MASK;
 		if (qdisc_run_begin(q)) {
 			if (unlikely(contended)) {
-				spin_unlock(&q->busylock);
+				q_spin_unlock(&q->busylock, &busylock_node);
 				contended = false;
 			}
 			__qdisc_run(q);

@@ -2493,7 +2494,7 @@ static inline int __dev_xmit_skb(struct sk_buff *skb, struct Qdisc *q,
 	}
 	spin_unlock(root_lock);
 	if (unlikely(contended))
-		spin_unlock(&q->busylock);
+		q_spin_unlock(&q->busylock, &busylock_node);
 	return rc;
 }
 

index aefc1504dc88..6675d30d526a 100644
@@ -362,7 +362,7 @@ struct Qdisc noop_qdisc = {
 	.list		=	LIST_HEAD_INIT(noop_qdisc.list),
 	.q.lock		=	__SPIN_LOCK_UNLOCKED(noop_qdisc.q.lock),
 	.dev_queue	=	&noop_netdev_queue,
-	.busylock	=	__SPIN_LOCK_UNLOCKED(noop_qdisc.busylock),
+	.busylock	=	__Q_SPIN_LOCK_UNLOCKED(noop_qdisc.busylock),
 };
 EXPORT_SYMBOL(noop_qdisc);
 

@@ -389,7 +389,7 @@ static struct Qdisc noqueue_qdisc = {
 	.list		=	LIST_HEAD_INIT(noqueue_qdisc.list),
 	.q.lock		=	__SPIN_LOCK_UNLOCKED(noqueue_qdisc.q.lock),
 	.dev_queue	=	&noqueue_netdev_queue,
-	.busylock	=	__SPIN_LOCK_UNLOCKED(noqueue_qdisc.busylock),
+	.busylock	=	__Q_SPIN_LOCK_UNLOCKED(noqueue_qdisc.busylock),
 };
 
 

@@ -527,8 +527,6 @@ struct Qdisc_ops pfifo_fast_ops __read_mostly = {
 };
 EXPORT_SYMBOL(pfifo_fast_ops);
 
-static struct lock_class_key qdisc_tx_busylock;
-
 struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
 			  struct Qdisc_ops *ops)
 {

@@ -557,9 +555,7 @@ struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
 	INIT_LIST_HEAD(&sch->list);
 	skb_queue_head_init(&sch->q);
 
-	spin_lock_init(&sch->busylock);
-	lockdep_set_class(&sch->busylock,
-			  dev->qdisc_tx_busylock ?: &qdisc_tx_busylock);
+	q_spin_lock_init(&sch->busylock);
 
 	sch->ops = ops;
 	sch->enqueue = ops->enqueue;

1.7.7.3

This change converts the IPC message queues, semaphores and shm segments to use the queue spinlock API.

This is relatively large, but mostly mechanical, mostly adding struct q_spinlock_node variables before locking ipc objects and passing them all the way to the actual locking and unlocking functions.

In most cases the struct q_spinlock_node is allocated on stack, but there are exceptions such as the sysvipc_proc_seqops allocating it within their iterator structure.

---
 include/linux/ipc.h |    4 +-
 ipc/msg.c           |   61 ++++++++++++++++------------
 ipc/namespace.c     |    8 ++-
 ipc/sem.c           |  112 ++++++++++++++++++++++++++++----------------------
 ipc/shm.c           |   95 ++++++++++++++++++++++++-------------------
 ipc/util.c          |   55 ++++++++++++++----------
 ipc/util.h          |   25 +++++++----
 7 files changed, 207 insertions(+), 153 deletions(-)

index 8d861b2651f7..81693a8a5177 100644
@@ -1,7 +1,7 @@
 #ifndef _LINUX_IPC_H
 #define _LINUX_IPC_H
 
-#include <linux/spinlock.h>
+#include <linux/queue_spinlock.h>
 #include <linux/uidgid.h>
 #include <uapi/linux/ipc.h>
 

@@ -10,7 +10,7 @@
 /* used by in-kernel data structures */
 struct kern_ipc_perm
 {
-	spinlock_t	lock;
+	struct q_spinlock	lock;
 	int		deleted;
 	int		id;
 	key_t		key;

index f362298c5ce4..ba4f87c18870 100644
@@ -70,11 +70,13 @@ struct ipc_namespace *copy_ipcs(unsigned long flags,
  * Called for each kind of ipc when an ipc_namespace exits.
  */
 void free_ipcs(struct ipc_namespace *ns, struct ipc_ids *ids,
-	       void (*free)(struct ipc_namespace *, struct kern_ipc_perm *))
+	       void (*free)(struct ipc_namespace *, struct kern_ipc_perm *,
+			    struct q_spinlock_node *))
 {
 	struct kern_ipc_perm *perm;
 	int next_id;
 	int total, in_use;
+	struct q_spinlock_node node;
 
 	down_write(&ids->rw_mutex);
 

@@ -84,8 +86,8 @@ void free_ipcs(struct ipc_namespace *ns, struct ipc_ids *ids,
 		perm = idr_find(&ids->ipcs_idr, next_id);
 		if (perm == NULL)
 			continue;
-		ipc_lock_by_ptr(perm);
-		free(ns, perm);
+		ipc_lock_by_ptr(perm, &node);
+		free(ns, perm, &node);
 		total++;
 	}
 	up_write(&ids->rw_mutex);

index c8fe2f7631e9..f03c36188cc3 100644
@@ -94,7 +94,8 @@ void __init ipc_init_proc_interface(const char *path, const char *header,
 #define ipcid_to_idx(id) ((id) % SEQ_MULTIPLIER)
 
 /* must be called with ids->rw_mutex acquired for writing */
-int ipc_addid(struct ipc_ids *, struct kern_ipc_perm *, int);
+int ipc_addid(struct ipc_ids *, struct kern_ipc_perm *, int,
+	      struct q_spinlock_node *);
 
 /* must be called with ids->rw_mutex acquired for reading */
 int ipc_get_maxid(struct ipc_ids *);

@@ -121,14 +122,16 @@ void* ipc_rcu_alloc(int size);
 void ipc_rcu_getref(void *ptr);
 void ipc_rcu_putref(void *ptr);
 
-struct kern_ipc_perm *ipc_lock(struct ipc_ids *, int);
+struct kern_ipc_perm *ipc_lock(struct ipc_ids *, int,
+			       struct q_spinlock_node *);
 
 void kernel_to_ipc64_perm(struct kern_ipc_perm *in, struct ipc64_perm *out);
 void ipc64_perm_to_ipc_perm(struct ipc64_perm *in, struct ipc_perm *out);
 int ipc_update_perm(struct ipc64_perm *in, struct kern_ipc_perm *out);
 struct kern_ipc_perm *ipcctl_pre_down(struct ipc_namespace *ns,
 				      struct ipc_ids *ids, int id, int cmd,
-				      struct ipc64_perm *perm, int extra_perm);
+				      struct ipc64_perm *perm, int extra_perm,
+				      struct q_spinlock_node *node);
 
 #ifndef CONFIG_ARCH_WANT_IPC_PARSE_VERSION
   /* On IA-64, we always use the "64-bit version" of the IPC structures.  */ 

@@ -158,21 +161,25 @@ static inline int ipc_checkid(struct kern_ipc_perm *ipcp, int uid)
 	return 0;
 }
 
-static inline void ipc_lock_by_ptr(struct kern_ipc_perm *perm)
+static inline void ipc_lock_by_ptr(struct kern_ipc_perm *perm,
+				   struct q_spinlock_node *node)
 {
 	rcu_read_lock();
-	spin_lock(&perm->lock);
+	q_spin_lock(&perm->lock, node);
 }
 
-static inline void ipc_unlock(struct kern_ipc_perm *perm)
+static inline void ipc_unlock(struct kern_ipc_perm *perm,
+			      struct q_spinlock_node *node)
 {
-	spin_unlock(&perm->lock);
+	q_spin_unlock(&perm->lock, node);
 	rcu_read_unlock();
 }
 
-struct kern_ipc_perm *ipc_lock_check(struct ipc_ids *ids, int id);
+struct kern_ipc_perm *ipc_lock_check(struct ipc_ids *ids, int id,
+				     struct q_spinlock_node *node);
 int ipcget(struct ipc_namespace *ns, struct ipc_ids *ids,
 			struct ipc_ops *ops, struct ipc_params *params);
 void free_ipcs(struct ipc_namespace *ns, struct ipc_ids *ids,
-		void (*free)(struct ipc_namespace *, struct kern_ipc_perm *));
+	       void (*free)(struct ipc_namespace *, struct kern_ipc_perm *,
+			    struct q_spinlock_node *));
 #endif

1.7.7.3

The MCS based queue spinlock implementation was easy to use, but it has a few annoying performance limitations under moderate contention.

- In the uncontended case, it uses atomic operations on both the acquire and the release paths, as opposed to the ticket spinlock which can use (on x86) a simple store on the release path.

- In the contended case, a thread will write both to its own q_spinlock_node (to initialize the wait field), to the previous node (to set the next field), and to the next node (to release the spinlock). It would be nice to reduce the number of locations accessed.

- When some thread's unlock operation races with the next thread's lock operation, there is a short window where the unlocker might have to spin waiting for the locker to fully register itself. This race is most likely to hit with a small number of threads and a short lock hold time, and it may reduce performance in that case.

Because of these limitations, the MCS queue spinlock implementation does not always compare favorably to ticket spinlocks under moderate contention.

This alternative queue spinlock implementation has some nice properties:

- One single atomic operation (xchg) during acquire
- One single memory store for unlock. No busy looping either. Actually, the unlock is so short that we can just inline it.
- Same basic API as with the MCS spinlock

It does however have a couple downsides:

- Spinlock initialization makes use of kmalloc(), and can fail. This is easy enough to deal with for dynamically allocated objects, where the object allocation could have failed too; however this is slightly inconvenient for statically allocated objects.
- trylock() is not sanely implementable in this framework, while the MCS queue spinlock implementation could have supported it without issues.
- This proposal does not support acquiring queue spinlocks from hardirq or nmi contexts (I don't expect this to be a significant downside).

Each spinlock points to a q_spinlock_token structure, which consists of a single 'wait' field. That value is true whenever the spinlock is locked. Each CPU has a private stash of two tokens. To acquire the spinlock, we must use one of the per-CPU stashed tokens, set the wait field to true, and atomically exchange it with the spinlock's token, thus getting the previous lock holder/waiter's token. Then we wait for the previous holder to release the lock, by waiting for that previous token's wait field to become false. At that point, the previous holder won't access that token anymore so we can stash it back into our per-CPU reserve. To unlock, we must simply remember the token we had exchanged into the spinlock variable (it gets passed from the lock function to the unlock function through the q_spinlock_node structure) and set its wait field to false.

Since the spinlock acquisition takes one token out of our per-CPU stash at the start of the operation, and returns a new token to the per-CPU stash only after it's done spinning for the previous lock owner to unlock, we need to deal with the possibility of getting interrupted during that process and needing to acquire a separate spinlock during that interrupt. This situation is dealt with by having two stashed tokens per CPU, and by not supporting queue spinlock acquisition in hardirq or nmi contexts, so that we never need more than two levels of nesting here (for process and softirq contexts).

---
 include/linux/queue_spinlock.h |   80 ++++++++++++++++++----
 init/main.c                    |    2 +
 kernel/queue_spinlock.c        |  149 ++++++++++++++++++++++++++--------------
 3 files changed, 164 insertions(+), 67 deletions(-)

index 84b2470d232b..992b72be27e3 100644
@@ -2,38 +2,80 @@
 #define __LINUX_QUEUE_SPINLOCK_H
 
 #include <linux/bug.h>
+#include <linux/preempt.h>
+#include <linux/bottom_half.h>
+#include <asm/queue_spinlock.h>
 
-struct q_spinlock_node {
-	struct q_spinlock_node *next;
+struct q_spinlock_token {
 	bool wait;
 };
 
-struct q_spinlock {
-	struct q_spinlock_node *node;
+struct q_spinlock_node {
+	struct q_spinlock_token *token;
 };
 
-#define __Q_SPIN_LOCK_UNLOCKED(name) { NULL }
+struct q_spinlock {
+	struct q_spinlock_token *token;
+};
 
 #ifdef CONFIG_SMP
 
-void q_spin_lock(struct q_spinlock *lock, struct q_spinlock_node *node);
-void q_spin_lock_bh(struct q_spinlock *lock, struct q_spinlock_node *node);
-void q_spin_unlock(struct q_spinlock *lock, struct q_spinlock_node *node);
-void q_spin_unlock_bh(struct q_spinlock *lock, struct q_spinlock_node *node);
+struct q_spinlock_token *__q_spin_lock(struct q_spinlock *lock);
+struct q_spinlock_token *__q_spin_lock_bh(struct q_spinlock *lock);
+struct q_spinlock_token *__q_spin_lock_process(struct q_spinlock *lock);
+int q_spin_lock_init(struct q_spinlock *lock);
+void q_spin_lock_destroy(struct q_spinlock *lock);
+void q_spin_lock_percpu_init(void);
+
+static inline void
+q_spin_lock(struct q_spinlock *lock, struct q_spinlock_node *node)
+{
+	node->token = __q_spin_lock(lock);
+}
+
+static inline void
+q_spin_lock_bh(struct q_spinlock *lock, struct q_spinlock_node *node)
+{
+	node->token = __q_spin_lock_bh(lock);
+}
+
+static inline void
+q_spin_lock_process(struct q_spinlock *lock, struct q_spinlock_node *node)
+{
+	node->token = __q_spin_lock_process(lock);
+}
+
+static inline void
+q_spin_unlock(struct q_spinlock *lock, struct q_spinlock_node *node)
+{
+	q_spin_unlock_mb();	/* guarantee release store semantics */
+	ACCESS_ONCE(node->token->wait) = false;
+	preempt_enable();
+}
+
+static inline void
+q_spin_unlock_bh(struct q_spinlock *lock, struct q_spinlock_node *node)
+{
+	q_spin_unlock_mb();	/* guarantee release store semantics */
+	ACCESS_ONCE(node->token->wait) = false;
+	preempt_enable_no_resched();
+	local_bh_enable_ip((unsigned long)__builtin_return_address(0));
+}
 
-static inline void q_spin_lock_init(struct q_spinlock *lock)
+static inline void
+q_spin_unlock_process(struct q_spinlock *lock, struct q_spinlock_node *node)
 {
-	lock->node = NULL;
+	q_spin_unlock(lock, node);
 }
 
 static inline void assert_q_spin_locked(struct q_spinlock *lock)
 {
-	BUG_ON(!lock->node);
+	BUG_ON(!lock->token->wait);
 }
 
 static inline void assert_q_spin_unlocked(struct q_spinlock *lock)
 {
-	BUG_ON(lock->node);
+	BUG_ON(lock->token->wait);
 }
 
 #else /* !CONFIG_SMP */

@@ -45,17 +87,27 @@ static inline void
 q_spin_lock_bh(struct q_spinlock *lock, struct q_spinlock_node *node) {}
 
 static inline void
+q_spin_lock_process(struct q_spinlock *lock, struct q_spinlock_node *node) {}
+
+static inline void
 q_spin_unlock(struct q_spinlock *lock, struct q_spinlock_node *node) {}
 
 static inline void
 q_spin_unlock_bh(struct q_spinlock *lock, struct q_spinlock_node *node) {}
 
-static inline void q_spin_lock_init(struct q_spinlock *lock) {}
+static inline void
+q_spin_unlock_process(struct q_spinlock *lock, struct q_spinlock_node *node) {}
+
+static inline int q_spin_lock_init(struct q_spinlock *lock) { return 0; }
+
+static inline void q_spin_lock_destroy(struct q_spinlock *lock) {}
 
 static inline void assert_q_spin_locked(struct q_spinlock *lock) {}
 
 static inline void assert_q_spin_unlocked(struct q_spinlock *lock) {}
 
+static inline void q_spin_lock_percpu_init(void) {};
+
 #endif /* CONFIG_SMP */
 
 #endif /* __LINUX_QUEUE_SPINLOCK_H */

index e33e09df3cbc..ebfb6bd4a819 100644
@@ -70,6 +70,7 @@
 #include <linux/perf_event.h>
 #include <linux/file.h>
 #include <linux/ptrace.h>
+#include <linux/queue_spinlock.h>
 
 #include <asm/io.h>
 #include <asm/bugs.h>

@@ -525,6 +526,7 @@ asmlinkage void __init start_kernel(void)
 	sort_main_extable();
 	trap_init();
 	mm_init();
+	q_spin_lock_percpu_init();
 
 	/*
 	 * Set up the scheduler prior starting any interrupts (such as the

1.7.7.3

There is one thing I do not understand about these locks.

Ah, I need to explain it better then :)

No, it won't use the same token. Besically, setting token->wait = false does two things:
- it indicates to the next waiter (if any) that it doesn't need to spin anymore;
- it releases ownership of the token so that the next thread to acquire the spinlock (or that may be already spinning on it) can reuse the token.

No, they'll use a different token every time.
I think what confused you is that in __q_spin_lock_process(), percpu_token always points to q_spinlock_token[0]. But that in turns points to a new token every time (actually points to the token that was reclaimed on the last spinlock acquisition), so that consecutive spinlock acquisitions on the same CPU won't keep reusing the same token.

This get the token that was reclaimed during the last spinlock acquisition. We know the token is available to us, because the previous spinlock acquisition waited for token->wait to become false, and this condition got satisfied only when the previous spinlock holder released ownership of the token.

This stores the token we're waiting on in our per-cpu stash so we can reuse it on the next spinlock acquisition. It doesn't belong to us yet, but it will as soon as we're done spinning.

We also have the __q_spin_lock_process() vs __q_spin_lock_bh() distinction to ensure interrupts won't cause us to reuse per-cpu tokens before we're done spinning on them.

Hope this helps,

Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Document the fast queue spinlocks in a way that I can understand.

---
This may still not be clear to others. Please let me know if you would like me to change/enhance the documentation, so you can understand it too.

 kernel/queue_spinlock.c |   20 ++++++++++++++++++++
 1 files changed, 20 insertions(+), 0 deletions(-)

index b571508..dc740fe 100644
@@ -9,6 +9,23 @@
 #include <asm/processor.h>	/* for cpu_relax() */
 #include <asm/queue_spinlock.h>
 
+/*
+ * Fast queue spinlocks use a pool of tokens, which contain the actual locks,
+ * and are continuously moved around. Every spinlock is associated with one
+ * token, and every CPU is associated with two tokens. 
+ *
+ * When taking a lock, one of the CPU's tokens is associated with the lock,
+ * and the lock's token is associated with the CPU.
+ *
+ * The token that gets associated with the spinlock at lock time will indicate
+ * the lock is busy. The token that was previously associated with the spinlock,
+ * and is now associated with the CPU taking the lock, will indicate whether
+ * the previous lock holder has already unlocked the lock.
+ *
+ * To unlock a fast ticket spinlock, the CPU will unlock the token that it
+ * associated with the spinlock.
+ */
+
 DEFINE_PER_CPU(struct q_spinlock_token *, q_spinlock_token[2]);
 
 static inline struct q_spinlock_token *

@@ -25,8 +42,11 @@ ____q_spin_lock(struct q_spinlock *lock,
 
 	token = __this_cpu_read(*percpu_token);
 	token->wait = true;
+	/* Associate our (marked busy) token with the spinlock. */
 	prev = xchg(&lock->token, token);
+	/* The spinlock's old token is ours now. */
 	__this_cpu_write(*percpu_token, prev);
+	/* Wait for the spinlock's old token to be unlocked. */
 	while (ACCESS_ONCE(prev->wait))
 		cpu_relax();
 	q_spin_lock_mb();	/* guarantee acquire load semantics */

Due to limitations of the second queue spinlock implementation, a static spinlock initializer is not available anymore, so we must use an init function instead. Additionally, for dynamically allocated qdiscs we must handle the case of running out of memory as we try to initialize the busylock spinlock.

---
 net/sched/sch_generic.c |   15 +++++++++++----
 1 files changed, 11 insertions(+), 4 deletions(-)

index 6675d30d526a..1f9458b54ad6 100644
@@ -362,7 +362,6 @@ struct Qdisc noop_qdisc = {
 	.list		=	LIST_HEAD_INIT(noop_qdisc.list),
 	.q.lock		=	__SPIN_LOCK_UNLOCKED(noop_qdisc.q.lock),
 	.dev_queue	=	&noop_netdev_queue,
-	.busylock	=	__Q_SPIN_LOCK_UNLOCKED(noop_qdisc.busylock),
 };
 EXPORT_SYMBOL(noop_qdisc);
 

@@ -389,9 +388,14 @@ static struct Qdisc noqueue_qdisc = {
 	.list		=	LIST_HEAD_INIT(noqueue_qdisc.list),
 	.q.lock		=	__SPIN_LOCK_UNLOCKED(noqueue_qdisc.q.lock),
 	.dev_queue	=	&noqueue_netdev_queue,
-	.busylock	=	__Q_SPIN_LOCK_UNLOCKED(noqueue_qdisc.busylock),
 };
 
+static int __init sch_generic_init(void)
+{
+	return q_spin_lock_init(&noop_qdisc.busylock) ||
+		q_spin_lock_init(&noqueue_qdisc.busylock);
+}
+module_init(sch_generic_init);
 
 static const u8 prio2band[TC_PRIO_MAX + 1] = {
 	1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1

@@ -552,11 +556,11 @@ struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
 		sch = (struct Qdisc *) QDISC_ALIGN((unsigned long) p);
 		sch->padded = (char *) sch - (char *) p;
 	}
+	if (q_spin_lock_init(&sch->busylock))
+		goto freeout;
 	INIT_LIST_HEAD(&sch->list);
 	skb_queue_head_init(&sch->q);
 
-	q_spin_lock_init(&sch->busylock);
-
 	sch->ops = ops;
 	sch->enqueue = ops->enqueue;
 	sch->dequeue = ops->dequeue;

@@ -565,6 +569,8 @@ struct Qdisc *qdisc_alloc(struct netdev_queue *dev_queue,
 	atomic_set(&sch->refcnt, 1);
 
 	return sch;
+freeout:
+	kfree(p);
 errout:
 	return ERR_PTR(err);
 }

@@ -609,6 +615,7 @@ static void qdisc_rcu_free(struct rcu_head *head)
 {
 	struct Qdisc *qdisc = container_of(head, struct Qdisc, rcu_head);
 
+	q_spin_lock_destroy(&qdisc->busylock);
 	kfree((char *) qdisc - qdisc->padded);
 }
 

1.7.7.3

Compared to the previous change updating the ipc subsystem to use queue spinlocks, this is very minimal. The changes are:

- As we run in process context without disabling BH processing, it is possible that we get interrupted in the middle of a spinlock acquisition. Use q_spin_lock_process() instead of q_spin_lock() in order to account for that by using the per-CPU token that is reserved for such process context processing.

- Deal with the possibility of running out of memory as we initialize a dynamically allocated IPC object's spinlock, and destroy the spinlock when the ipc object is freed. There is a bit of complexity here as IPC objects use a scheme where object deletion is delayed by one RCU grace period, during which the object lock may still be accessed. In order to address this we have to make the ipc rcu allocation/freeing system aware of where the object spinlocks are located within the allocated object. This is not too hard in practice, as all ipc objects start with the kern_ipc_perm structure, which is where the object's spinlock is located.

---
 include/linux/ipc.h |    5 +--
 include/linux/msg.h |    2 +-
 include/linux/shm.h |    2 +-
 ipc/sem.c           |    3 +-
 ipc/util.c          |   77 ++++++++++++++++++++++++++++++++++----------------
 ipc/util.h          |    4 +-
 6 files changed, 60 insertions(+), 33 deletions(-)

index 81693a8a5177..4bc1751664fe 100644
@@ -7,9 +7,8 @@
 
 #define IPCMNI 32768  /* <= MAX_INT limit for ipc arrays (including sysctl changes) */
 
-/* used by in-kernel data structures */
-struct kern_ipc_perm
-{
+/* used by in-kernel data structures, must be placed first */
+struct kern_ipc_perm {
 	struct q_spinlock	lock;
 	int		deleted;
 	int		id;

index 7a4b9e97d29a..36a69d8d9a95 100644
@@ -16,7 +16,7 @@ struct msg_msg {
 
 /* one msq_queue structure for each present queue on the system */
 struct msg_queue {
-	struct kern_ipc_perm q_perm;
+	struct kern_ipc_perm q_perm;	/* permissions, must be first */
 	time_t q_stime;			/* last msgsnd time */
 	time_t q_rtime;			/* last msgrcv time */
 	time_t q_ctime;			/* last change time */

index bcf8a6a3ec00..2e74b96922df 100644
@@ -8,7 +8,7 @@
 #include <asm/shmparam.h>
 struct shmid_kernel /* private to the kernel */
 {	
-	struct kern_ipc_perm	shm_perm;
+	struct kern_ipc_perm	shm_perm;	/* must be first */
 	struct file *		shm_file;
 	unsigned long		shm_nattch;
 	unsigned long		shm_segsz;

index 84b7f3b2c632..e1f24942b294 100644
@@ -309,7 +309,6 @@ static int newary(struct ipc_namespace *ns, struct ipc_params *params)
 	if (!sma) {
 		return -ENOMEM;
 	}
-	memset (sma, 0, size);
 
 	sma->sem_perm.mode = (semflg & S_IRWXUGO);
 	sma->sem_perm.key = key;

@@ -330,6 +329,7 @@ static int newary(struct ipc_namespace *ns, struct ipc_params *params)
 	ns->used_sems += nsems;
 
 	sma->sem_base = (struct sem *) &sma[1];
+	memset (sma->sem_base, 0, nsems * sizeof (struct sem));
 
 	for (i = 0; i < nsems; i++)
 		INIT_LIST_HEAD(&sma->sem_base[i].sem_pending);

@@ -338,6 +338,7 @@ static int newary(struct ipc_namespace *ns, struct ipc_params *params)
 	INIT_LIST_HEAD(&sma->sem_pending);
 	INIT_LIST_HEAD(&sma->list_id);
 	sma->sem_nsems = nsems;
+	sma->sem_otime = 0;
 	sma->sem_ctime = get_seconds();
 	sem_unlock(sma, &node);
 

index f03c36188cc3..eb547e35ffbe 100644
@@ -165,13 +165,13 @@ static inline void ipc_lock_by_ptr(struct kern_ipc_perm *perm,
 				   struct q_spinlock_node *node)
 {
 	rcu_read_lock();
-	q_spin_lock(&perm->lock, node);
+	q_spin_lock_process(&perm->lock, node);
 }
 
 static inline void ipc_unlock(struct kern_ipc_perm *perm,
 			      struct q_spinlock_node *node)
 {
-	q_spin_unlock(&perm->lock, node);
+	q_spin_unlock_process(&perm->lock, node);
 	rcu_read_unlock();
 }
 

1.7.7.3

Graphs are attached (admittedly not the most interesting benchmark).

Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.