Skip to contentSkip to conversation

queued spinlocks (i386)

RFC PATCH In review Nick Piggin 9 participants 25 messages Mar 23, 2007 – Mar 30, 2007

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 queued spinlocks (i386)

Implement queued spinlocks for i386. This shouldn't increase the size of the spinlock structure, while still able to handle 2^16 CPUs.

Not completely implemented with assembly yet, to make the algorithm a bit clearer.

The queued spinlock has 2 fields, a head and a tail, which are indexes into a FIFO of waiting CPUs. To take a spinlock, a CPU performs an "atomic_inc_return" on the head index, and keeps the returned value as a ticket. The CPU then spins until the tail index is equal to that ticket.

To unlock a spinlock, the tail index is incremented (this can be non atomic, because only the lock owner will modify tail).

Implementation inefficiencies aside, this change should have little effect on performance for uncontended locks, but will have quite a large cost for highly contended locks [O(N) cacheline transfers vs O(1) per lock aquisition, where N is the number of CPUs contending]. The benefit is is that contended locks will not cause any starvation.

Just an idea. Big NUMA hardware seems to have fairness logic that prevents starvation for the regular spinlock logic. But it might be interesting for -rt kernel or systems with starvation issues.

include/asm-i386/spinlock.h +10 -60
Index: linux-2.6/include/asm-i386/spinlock.h
===================================================================
@@ -29,69 +29,23 @@
 
 static inline int __raw_spin_is_locked(raw_spinlock_t *x)
 {
-	return *(volatile signed char *)(&(x)->slock) <= 0;
+	return unlikely(x->qhead != x->qtail);
 }
 
 static inline void __raw_spin_lock(raw_spinlock_t *lock)
 {
-	asm volatile("\n1:\t"
-		     LOCK_PREFIX " ; decb %0\n\t"
-		     "jns 3f\n"
-		     "2:\t"
-		     "rep;nop\n\t"
-		     "cmpb $0,%0\n\t"
-		     "jle 2b\n\t"
-		     "jmp 1b\n"
-		     "3:\n\t"
-		     : "+m" (lock->slock) : : "memory");
-}
+	unsigned short pos = 1;
 
-/*
- * It is easier for the lock validator if interrupts are not re-enabled
- * in the middle of a lock-acquire. This is a performance feature anyway
- * so we turn it off:
- *
- * NOTE: there's an irqs-on section here, which normally would have to be
- * irq-traced, but on CONFIG_TRACE_IRQFLAGS we never use this variant.
- */
-#ifndef CONFIG_PROVE_LOCKING
-static inline void __raw_spin_lock_flags(raw_spinlock_t *lock, unsigned long flags)
-{
-	asm volatile(
-		"\n1:\t"
-		LOCK_PREFIX " ; decb %[slock]\n\t"
-		"jns 5f\n"
-		"2:\t"
-		"testl $0x200, %[flags]\n\t"
-		"jz 4f\n\t"
-		STI_STRING "\n"
-		"3:\t"
-		"rep;nop\n\t"
-		"cmpb $0, %[slock]\n\t"
-		"jle 3b\n\t"
-		CLI_STRING "\n\t"
-		"jmp 1b\n"
-		"4:\t"
-		"rep;nop\n\t"
-		"cmpb $0, %[slock]\n\t"
-		"jg 1b\n\t"
-		"jmp 4b\n"
-		"5:\n\t"
-		: [slock] "+m" (lock->slock)
-		: [flags] "r" (flags)
-	 	  CLI_STI_INPUT_ARGS
-		: "memory" CLI_STI_CLOBBERS);
+	asm volatile(LOCK_PREFIX "xaddw %0, %1\n\t"
+		     : "+r" (pos), "+m" (lock->qhead) : : "memory");
+	while (unlikely(pos != lock->qtail))
+		cpu_relax();
 }
-#endif
 
 static inline int __raw_spin_trylock(raw_spinlock_t *lock)
 {
-	char oldval;
-	asm volatile(
-		"xchgb %b0,%1"
-		:"=q" (oldval), "+m" (lock->slock)
-		:"0" (0) : "memory");
-	return oldval > 0;
+	unsigned short qtail = lock->qtail;
+	return likely(cmpxchg(&lock->qhead, qtail, qtail+1) == qtail);
 }
 
 /*
@@ -105,18 +59,14 @@ static inline int __raw_spin_trylock(raw
 
 static inline void __raw_spin_unlock(raw_spinlock_t *lock)
 {
-	asm volatile("movb $1,%0" : "+m" (lock->slock) :: "memory");
+	asm volatile("addw $1,%0" : "+m" (lock->qtail) :: "memory");
 }
 
 #else
 
 static inline void __raw_spin_unlock(raw_spinlock_t *lock)
 {
-	char oldval = 1;
-
-	asm volatile("xchgb %b0, %1"
-		     : "=q" (oldval), "+m" (lock->slock)
-		     : "0" (oldval) : "memory");
+	asm volatile(LOCK_PREFIX "addw $1,%0" : "+m" (lock->qtail) :: "memory");
 }
 
 #endif
include/asm-i386/spinlock_types.h +3 -2
Index: linux-2.6/include/asm-i386/spinlock_types.h
===================================================================
@@ -6,10 +6,11 @@
 #endif
 
 typedef struct {
-	unsigned int slock;
+	unsigned short qhead;
+	unsigned short qtail;
 } raw_spinlock_t;
 
-#define __RAW_SPIN_LOCK_UNLOCKED	{ 1 }
+#define __RAW_SPIN_LOCK_UNLOCKED	{ 0, 0 }
 
 typedef struct {
 	unsigned int lock;
#1 lore raw
Quoted 22 lines · On Fri, 23 Mar 2007 09:59:11 +0100 Nick Piggin <[email protected]> wrote:

Implement queued spinlocks for i386. This shouldn't increase the size of the spinlock structure, while still able to handle 2^16 CPUs.

Not completely implemented with assembly yet, to make the algorithm a bit clearer.

The queued spinlock has 2 fields, a head and a tail, which are indexes into a FIFO of waiting CPUs. To take a spinlock, a CPU performs an "atomic_inc_return" on the head index, and keeps the returned value as a ticket. The CPU then spins until the tail index is equal to that ticket.

To unlock a spinlock, the tail index is incremented (this can be non atomic, because only the lock owner will modify tail).

Implementation inefficiencies aside, this change should have little effect on performance for uncontended locks, but will have quite a large cost for highly contended locks [O(N) cacheline transfers vs O(1) per lock aquisition, where N is the number of CPUs contending]. The benefit is is that contended locks will not cause any starvation.

Quoted 3 lines

Just an idea. Big NUMA hardware seems to have fairness logic that prevents starvation for the regular spinlock logic. But it might be interesting for -rt kernel or systems with starvation issues.

It's a very nice idea Nick.

You also have for free the number or cpus that are before you.

On big SMP/NUMA, we could use this information to call a special lock_cpu_relax() function to avoid cacheline transferts.

	asm volatile(LOCK_PREFIX "xaddw %0, %1\n\t"
		     : "+r" (pos), "+m" (lock->qhead) : : "memory");
	for (;;) {
		unsigned short nwait = pos - lock->qtail;
		if (likely(nwait == 0))
			break;
		lock_cpu_relax(lock, nwait);
	}

lock_cpu_relax(raw_spinlock_t *lock, unsigned int nwait) {
unsigned int cycles = nwait * lock->min_cycles_per_round; busy_loop(cycles);
}

#2 lore raw
Quoted 44 lines · Eric Dumazet
Quoted 22 lines · On Fri, 23 Mar 2007 09:59:11 +0100 Nick Piggin <[email protected]> wrote:

Implement queued spinlocks for i386. This shouldn't increase the size of the spinlock structure, while still able to handle 2^16 CPUs.

Not completely implemented with assembly yet, to make the algorithm a bit clearer.

The queued spinlock has 2 fields, a head and a tail, which are indexes into a FIFO of waiting CPUs. To take a spinlock, a CPU performs an "atomic_inc_return" on the head index, and keeps the returned value as a ticket. The CPU then spins until the tail index is equal to that ticket.

To unlock a spinlock, the tail index is incremented (this can be non atomic, because only the lock owner will modify tail).

Implementation inefficiencies aside, this change should have little effect on performance for uncontended locks, but will have quite a large cost for highly contended locks [O(N) cacheline transfers vs O(1) per lock aquisition, where N is the number of CPUs contending]. The benefit is is that contended locks will not cause any starvation.

Quoted 3 lines

Just an idea. Big NUMA hardware seems to have fairness logic that prevents starvation for the regular spinlock logic. But it might be interesting for -rt kernel or systems with starvation issues.

It's a very nice idea Nick.

You also have for free the number or cpus that are before you.

On big SMP/NUMA, we could use this information to call a special lock_cpu_relax() function to avoid cacheline transferts.

	asm volatile(LOCK_PREFIX "xaddw %0, %1\n\t"
		     : "+r" (pos), "+m" (lock->qhead) : : "memory");
	for (;;) {
		unsigned short nwait = pos - lock->qtail;
		if (likely(nwait == 0))
			break;
		lock_cpu_relax(lock, nwait);
	}
Quoted 5 lines

lock_cpu_relax(raw_spinlock_t *lock, unsigned int nwait) {
unsigned int cycles = nwait * lock->min_cycles_per_round; busy_loop(cycles);
}

Yeah that's true, it would give you a lot more information for use in a lock backoff system, so that might counter the lesser efficiency of queued locks under contention.

You could perhaps even wait using monitor/mwait on the lock cacheline if there are more than X CPUs in front of you. I'm not sure if the cost of mwait is entirely within the core that executes it, or whether it slows down cache coherency as well (which would make that idea a showstopper).

#3 lore raw
In reply to Eric Dumazet
Quoted 25 lines · Eric Dumazet
Quoted 22 lines · On Fri, 23 Mar 2007 09:59:11 +0100 Nick Piggin <[email protected]> wrote:

Implement queued spinlocks for i386. This shouldn't increase the size of the spinlock structure, while still able to handle 2^16 CPUs.

Not completely implemented with assembly yet, to make the algorithm a bit clearer.

The queued spinlock has 2 fields, a head and a tail, which are indexes into a FIFO of waiting CPUs. To take a spinlock, a CPU performs an "atomic_inc_return" on the head index, and keeps the returned value as a ticket. The CPU then spins until the tail index is equal to that ticket.

To unlock a spinlock, the tail index is incremented (this can be non atomic, because only the lock owner will modify tail).

Implementation inefficiencies aside, this change should have little effect on performance for uncontended locks, but will have quite a large cost for highly contended locks [O(N) cacheline transfers vs O(1) per lock aquisition, where N is the number of CPUs contending]. The benefit is is that contended locks will not cause any starvation.

Quoted 5 lines
Quoted 3 lines

Just an idea. Big NUMA hardware seems to have fairness logic that prevents starvation for the regular spinlock logic. But it might be interesting for -rt kernel or systems with starvation issues.

It's a very nice idea Nick.

Amen to that.

Quoted 14 lines

You also have for free the number or cpus that are before you.

On big SMP/NUMA, we could use this information to call a special lock_cpu_relax() function to avoid cacheline transferts.

	asm volatile(LOCK_PREFIX "xaddw %0, %1\n\t"
		     : "+r" (pos), "+m" (lock->qhead) : : "memory");
	for (;;) {
		unsigned short nwait = pos - lock->qtail;
		if (likely(nwait == 0))
			break;
		lock_cpu_relax(lock, nwait);
	}
Quoted 5 lines

lock_cpu_relax(raw_spinlock_t *lock, unsigned int nwait) {
unsigned int cycles = nwait * lock->min_cycles_per_round; busy_loop(cycles);
}

Good Idea. Hopefully, this should reduce the number of cacheline transfers in the contended case.

#4 lore raw
In reply to Nick Piggin
Quoted 1 line · Nick Piggin

Implement queued spinlocks for i386. [...]

isnt this patented by MS? (which might not worry you SuSE/Novell guys, but it might be a worry for the rest of the world ;-)

Ingo

#5 lore raw
Quoted 7 lines · Ingo Molnar
Quoted 1 line · Nick Piggin

Implement queued spinlocks for i386. [...]

isnt this patented by MS? (which might not worry you SuSE/Novell guys, but it might be a worry for the rest of the world ;-)

I never thought a FIFO queue would be patentable.

Do you have a reference to the patent number?

#6 lore raw
Quoted 5 lines · Nick Piggin <npiggin <at> suse.de> writes:
Quoted 3 lines · Ingo Molnar

* Nick Piggin <npiggin <at> suse.de> wrote:

Quoted 9 lines
Quoted 4 lines
Quoted 1 line

Implement queued spinlocks for i386. [...]

isnt this patented by MS? (which might not worry you SuSE/Novell guys, but it might be a worry for the rest of the world

I never thought a FIFO queue would be patentable.

Do you have a reference to the patent number?

The ReactOS guys none the less, seem to have implemented queued spin locks -
http://www.reactos.org/en/newsletter_10.html (see the HAL section.)

Now I haven't looked at the code to see if they are different from what MS has patented but given that it's a clone of Windows, one would think at least from the behavioral pov they are similar?

Parag

#7 lore raw
In reply to Nick Piggin
Quoted 4 lines · Nick Piggin
Quoted 3 lines · Ingo Molnar

* Nick Piggin <[email protected]> wrote:

Quoted 8 lines
Quoted 4 lines
Quoted 1 line

Implement queued spinlocks for i386. [...]

isnt this patented by MS? (which might not worry you SuSE/Novell guys, but it might be a worry for the rest of the world ;-)

I never thought a FIFO queue would be patentable.

Do you have a reference to the patent number?

FWIW, MS patented even the preprocessor in computer languages ;) Holding a patent does not make it automatically enforceable.
I remember thare was a discussion time ago about queued spinlocks on lkml.

- Davide

#8 lore raw
In reply to Ingo Molnar
Quoted 7 lines · Ingo Molnar
Quoted 1 line · Nick Piggin

Implement queued spinlocks for i386. [...]

isnt this patented by MS? (which might not worry you SuSE/Novell guys, but it might be a worry for the rest of the world ;-)

Hmm, it looks like they have implemented a system where the spinning cpu sleeps on a per-CPU variable rather than the lock itself, and the releasing cpu writes to that variable to wake it. They do this so that spinners don't continually perform exclusive->shared transitions on the lock cacheline. They call these things queued spinlocks. They don't seem to be very patent worthy either, but maybe it is what you're thinking of?

I'm not as concerned about the contended performance of spinlocks for Linux as MS seems to be for windows (they seem to be very proud of this lock). Because if it is a big problem then IMO it is a bug.

This was just something I had in mind when the hardware lock starvation issue came up, so I thought I should quickly code it up and RFC... actually it makes contended performance worse, but I'm not too worried about that because I'm happy I was able to implement it without increasing data size or number of locked operations.

#9 lore raw
Quoted 21 lines · On Fri, 23 Mar 2007 11:32:44 +0100 Nick Piggin <[email protected]> wrote:
Quoted 7 lines · Ingo Molnar
Quoted 1 line · Nick Piggin

Implement queued spinlocks for i386. [...]

isnt this patented by MS? (which might not worry you SuSE/Novell guys, but it might be a worry for the rest of the world ;-)

Hmm, it looks like they have implemented a system where the spinning cpu sleeps on a per-CPU variable rather than the lock itself, and the releasing cpu writes to that variable to wake it. They do this so that spinners don't continually perform exclusive->shared transitions on the lock cacheline. They call these things queued spinlocks. They don't seem to be very patent worthy either, but maybe it is what you're thinking of?

I'm not as concerned about the contended performance of spinlocks for Linux as MS seems to be for windows (they seem to be very proud of this lock). Because if it is a big problem then IMO it is a bug.

Quoted 5 lines

This was just something I had in mind when the hardware lock starvation issue came up, so I thought I should quickly code it up and RFC... actually it makes contended performance worse, but I'm not too worried about that because I'm happy I was able to implement it without increasing data size or number of locked operations.

Sure, but please note that you should rename your patch to :

"Implement queued spinlocks for i486"

:)

#10 lore raw
In reply to Nick Piggin
Quoted 2 lines · Ingo Molnar
Quoted 2 lines

isnt this patented by MS? (which might not worry you SuSE/Novell guys, but it might be a worry for the rest of the world ;-)

Quoted 7 lines · Nick Piggin

Hmm, it looks like they have implemented a system where the spinning cpu sleeps on a per-CPU variable rather than the lock itself, and the releasing cpu writes to that variable to wake it. They do this so that spinners don't continually perform exclusive->shared transitions on the lock cacheline. They call these things queued spinlocks. They don't seem to be very patent worthy either, but maybe it is what you're thinking of?

Those exclusive-to-shared transitions are among the cacheline transfers typically accounted to the algorithms in their complexity analyses.

-- wli

#11 lore raw
In reply to Nick Piggin
Quoted 9 lines · Nick Piggin
Quoted 7 lines · Ingo Molnar
Quoted 1 line · Nick Piggin

Implement queued spinlocks for i386. [...]

isnt this patented by MS? (which might not worry you SuSE/Novell guys, but it might be a worry for the rest of the world ;-)

Quoted 6 lines

Hmm, it looks like they have implemented a system where the spinning cpu sleeps on a per-CPU variable rather than the lock itself, and the releasing cpu writes to that variable to wake it. They do this so that spinners don't continually perform exclusive->shared transitions on the lock cacheline. They call these things queued spinlocks. They don't seem to be very patent worthy either, but

Indeed, this technique is very well known. E.g.,
http://citeseer.ist.psu.edu/anderson01sharedmemory.html has a whole section (3. Local-spin Algorithms) on them, citing papers from the 1990 onward.

Nikita.

#12 lore raw
Quoted 4 lines · Nikita Danilov

Indeed, this technique is very well known. E.g.,
http://citeseer.ist.psu.edu/anderson01sharedmemory.html has a whole section (3. Local-spin Algorithms) on them, citing papers from the 1990 onward.

that is a cool reference! So i'd suggest to do (redo?) the patch based on those concepts and that terminology and not use 'queued spinlocks' that are commonly associated with MS's stuff. And as a result the contended case would be optimized some more via local-spin algorithms. (which is not a key thing for us, but which would be nice to have nevertheless)

Ingo

#13 lore raw
Quoted 10 lines · Ingo Molnar
Quoted 4 lines · Nikita Danilov

Indeed, this technique is very well known. E.g.,
http://citeseer.ist.psu.edu/anderson01sharedmemory.html has a whole section (3. Local-spin Algorithms) on them, citing papers from the 1990 onward.

that is a cool reference! So i'd suggest to do (redo?) the patch based on those concepts and that terminology and not use 'queued spinlocks'

There is some old version:

http://namesys.com/pub/misc-patches/unsupported/extra/2004.02.04/p06-locallock.patch
http://namesys.com/pub/misc-patches/unsupported/extra/2004.02.04/p07-locallock-bkl.patch
http://namesys.com/pub/misc-patches/unsupported/extra/2004.02.04/p08-locallock-zone.patch

http://namesys.com/pub/misc-patches/unsupported/extra/2004.02.04/p0b-atomic_dec_and_locallock.patch
http://namesys.com/pub/misc-patches/unsupported/extra/2004.02.04/p0c-locallock-dcache.patch

This version retains original spin-lock interface (i.e., no additional "queue link" pointer is passed to the locking function). As a result, lock data structure contains an array of NR_CPU counters, so it's only suitable for global statically allocated locks.

Quoted 6 lines

that are commonly associated with MS's stuff. And as a result the contended case would be optimized some more via local-spin algorithms. (which is not a key thing for us, but which would be nice to have nevertheless)

Ingo

Nikita.

#14 lore raw
In reply to Ingo Molnar
Quoted 8 lines · Ingo Molnar
Quoted 4 lines · Nikita Danilov

Indeed, this technique is very well known. E.g.,
http://citeseer.ist.psu.edu/anderson01sharedmemory.html has a whole section (3. Local-spin Algorithms) on them, citing papers from the 1990 onward.

Quoted 6 lines

that is a cool reference! So i'd suggest to do (redo?) the patch based on those concepts and that terminology and not use 'queued spinlocks' that are commonly associated with MS's stuff. And as a result the contended case would be optimized some more via local-spin algorithms. (which is not a key thing for us, but which would be nice to have nevertheless)

Firstly, the terminology in that paper _is_ "queue lock", which isn't really surprising. I don't really know or care about what MS calls their locks, but I'd suggest that their queued spinlock is probably named in reference to its queueing property rather than its local spin property.

Mine is a queueing lock, so I'll continue to call it queued spinlocks (not that the terminology will make it into our API anyway, because I intend for them simply to be an implementation of spinlocks).

Secondly, as you say, local spin isn't really a must have. If SGI hasn't made a big stink about them by now, then I think queued locks (which are addressing a real hardware starvation issue on opterons) is more important.

That isn't to say that local spin might not help performance, or that my queued spinlocks would make it impossible to implement... it's just that it isn't my aim.

#15 lore raw
Quoted 16 lines · Nick Piggin
Quoted 8 lines · Ingo Molnar
Quoted 4 lines · Nikita Danilov

Indeed, this technique is very well known. E.g.,
http://citeseer.ist.psu.edu/anderson01sharedmemory.html has a whole section (3. Local-spin Algorithms) on them, citing papers from the 1990 onward.

Quoted 6 lines

that is a cool reference! So i'd suggest to do (redo?) the patch based on those concepts and that terminology and not use 'queued spinlocks' that are commonly associated with MS's stuff. And as a result the contended case would be optimized some more via local-spin algorithms. (which is not a key thing for us, but which would be nice to have nevertheless)

Quoted 4 lines

Firstly, the terminology in that paper _is_ "queue lock", which isn't really surprising. I don't really know or care about what MS calls their locks, but I'd suggest that their queued spinlock is probably named in reference to its queueing property rather than its local spin property.

The method you propose is otherwise called "Ticket Lock":

http://en.wikipedia.org/wiki/Ticket_lock
http://www.cs.rochester.edu/research/synchronization/pseudocode/ss.html#ticket

- Davide

#16 lore raw
Quoted 23 lines · Davide Libenzi
Quoted 16 lines · Nick Piggin
Quoted 8 lines · Ingo Molnar
Quoted 4 lines · Nikita Danilov

Indeed, this technique is very well known. E.g.,
http://citeseer.ist.psu.edu/anderson01sharedmemory.html has a whole section (3. Local-spin Algorithms) on them, citing papers from the 1990 onward.

Quoted 6 lines

that is a cool reference! So i'd suggest to do (redo?) the patch based on those concepts and that terminology and not use 'queued spinlocks' that are commonly associated with MS's stuff. And as a result the contended case would be optimized some more via local-spin algorithms. (which is not a key thing for us, but which would be nice to have nevertheless)

Quoted 4 lines

Firstly, the terminology in that paper _is_ "queue lock", which isn't really surprising. I don't really know or care about what MS calls their locks, but I'd suggest that their queued spinlock is probably named in reference to its queueing property rather than its local spin property.

Quoted 4 lines

The method you propose is otherwise called "Ticket Lock":

http://en.wikipedia.org/wiki/Ticket_lock
http://www.cs.rochester.edu/research/synchronization/pseudocode/ss.html#ticket

That this work prio-art dates to 1991:

http://www.cs.rochester.edu/u/scott/papers/1991_TOCS_synch.pdf

So I would not worry to much about patents here. At least W2K MS ones ;) What I would worry though, is to add another class of locks. There's no reason why Ticket Locks would perform worse than our spinlock, in both contended and not-contended case, AFAICS. And they have a nice FIFO behaviour.

- Davide

#17 lore raw
Quoted 7 lines · Davide Libenzi
Quoted 4 lines · Davide Libenzi

The method you propose is otherwise called "Ticket Lock":

http://en.wikipedia.org/wiki/Ticket_lock
http://www.cs.rochester.edu/research/synchronization/pseudocode/ss.html#ticket

Quoted 6 lines

That this work prio-art dates to 1991:

http://www.cs.rochester.edu/u/scott/papers/1991_TOCS_synch.pdf

So I would not worry to much about patents here. At least W2K MS ones ;) What I would worry though, is to add another class of locks. There's no

No, as you see from my patch I just change the spinlock implementation to a queued one. I agree it doesn't make sense to add a new type of lock.

Quoted 3 lines

reason why Ticket Locks would perform worse than our spinlock, in both contended and not-contended case, AFAICS. And they have a nice FIFO behaviour.

In most cases, no. For the uncontended case they should be about the same. They have the same spinning behaviour. However there is a little window where they might be a bit slower I think... actually perhaps I'm wrong!

Currently if you have 4 CPUs spinning and the lock is released, all 4 CPU cachelines will be invalidated, then they will be loaded again, and found to be 0, so they all try to atomic_dec_return the counter, each one invalidating others' cachelines. 1 gets through.

With my queued locks, all 4 cachelines are invalidated and loaded, but only one will be allowed to proceed, and there are 0 atomic operations or stores of any kind.

So I take that back: our current spinlocks have a worse thundering herd behaviour under contention than my queued ones. So I'll definitely push the patch through.

#18 lore raw
Quoted 10 lines · Nick Piggin

In most cases, no. For the uncontended case they should be about the same. They have the same spinning behaviour. However there is a little window where they might be a bit slower I think... actually perhaps I'm wrong!

Currently if you have 4 CPUs spinning and the lock is released, all 4 CPU cachelines will be invalidated, then they will be loaded again, and found to be 0, so they all try to atomic_dec_return the counter, each one invalidating others' cachelines. 1 gets through.

Quoted 7 lines

With my queued locks, all 4 cachelines are invalidated and loaded, but only one will be allowed to proceed, and there are 0 atomic operations or stores of any kind.

So I take that back: our current spinlocks have a worse thundering herd behaviour under contention than my queued ones. So I'll definitely push the patch through.

OK, it isn't a big difference, but a user-space test is showing slightly (~2%) improvement in the contended case on a 16 core Opteron.

There is a case where the present spinlocks are almost twice as fast on this machine (in terms of aggregate throughput), and that is when a lock is taken right after it is released. This is because the same CPU will often be able to retake the lock without transitioning the cache. This is going to be a rare case for us, and would suggest suboptimal code anyway (ie. the lock should just be kept rather than dropped and retaken).

Actually, one situation where it comes up is when we drop and retake a lock that needs_lockbreak. Of course, the queued lock behaviour is desired in that case anyway.

However single-thread performance is presently a bit down. OTOH, the assembly generated by gcc looks like it could be improved upon (even by me :P).

This is what I've got so far. Should work for i386 and x86_64. Any enhancements or results from other CPUs would be interesting.

--
#define _GNU_SOURCE
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <pthread.h>
#include <sched.h>
#include <sys/time.h>

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
static inline void cpu_relax(void)

{
	asm volatile("rep ; nop" : : : "memory");
}

static unsigned long delta(struct timeval start, struct timeval end)

{
	return (end.tv_sec - start.tv_sec) * 1000000
		+ end.tv_usec - start.tv_usec;
}

static unsigned long lps;
static void calibrate_delay(void)

{
	struct timeval start, now;
	unsigned long i;
	gettimeofday(&start, NULL);
	i = 0;
	gettimeofday(&start, NULL);
	do {
		gettimeofday(&now, NULL);
		i++;
	} while (delta(start, now) < 1000000 * 2);
	lps = i / 2;
	printf("%lu lps\n", lps);
}

static void delay(unsigned long usec)

{
	struct timeval now;
	unsigned long loops = (lps*usec + 999999) / 1000000;
	unsigned long i;

	for (i = 0; i < loops; i++)
		gettimeofday(&now, NULL);
}

#define QUEUE_LOCKS
#ifdef QUEUE_LOCKS

typedef struct {
	unsigned short qhead;
	unsigned short qtail;
} spinlock_t;

#define SPIN_LOCK_UNLOCKED (spinlock_t){ 0, 0 }

static inline void spin_lock(spinlock_t *lock)

{
	unsigned short pos = 1;

	asm volatile("lock ; xaddw %0, %1\n\t"
			: "+r" (pos), "+m" (lock->qhead) : : "memory");
	while (unlikely(pos != lock->qtail))
		cpu_relax();
}

static inline void spin_unlock(spinlock_t *lock)

{
	asm volatile("addw $1, %0\n\t"
			: "+m" (lock->qtail) : : "memory");
}
#else
typedef struct {
	unsigned int slock;
} spinlock_t;

#define SPIN_LOCK_UNLOCKED (spinlock_t){ 1 }

static inline void spin_lock(spinlock_t *lock)

{
	asm volatile(
		"1:\n\t"
		"lock ; decl %0\n\t"
		"jns 2f\n\t"
		"3:\n\t"
		"rep;nop\n\t"
		"cmpl $0,%0\n\t"
		"jle 3b\n\t"
		"jmp 1b\n\t"
		"2:\n\t" : "=m" (lock->slock) : : "memory");
}

static inline void spin_unlock(spinlock_t *lock)

{
	asm volatile("movl $1,%0" :"=m" (lock->slock) :: "memory");
}

#endif

static struct {
	spinlock_t lock;
	unsigned long count;
} __attribute__((__aligned__(128))) data;

#undef MULTI_THREAD
#ifdef MULTI_THREAD
#define NR_THREADS 16
#define NR_ITERS 200000
#else
#define NR_THREADS 1
#define NR_ITERS 1000000000
#endif

static long go = 0;

static void *thread(void *arg)

{
	cpu_set_t mask;
	struct sched_param param;
	long nr = (long)arg;
	long i;

	assert(nr < NR_THREADS);

	CPU_ZERO(&mask);
	CPU_SET(nr, &mask);

	if (sched_setaffinity(0, sizeof(mask), &mask) == -1)
		perror("sched_setaffinity"), exit(1);

	param.sched_priority = 90;
	if (sched_setscheduler(0, SCHED_FIFO, &param) == -1)
		perror("sched_setscheduler"), exit(1);

	while (!go)
		sched_yield();

	for (i = 0; i < NR_ITERS; i++) {
		/*
		 * delay outside the lock should be non-zero to simulate
		 * reasonable code. The larger the delay inside the lock
		 * in relation to the delay outside, the more contention.
		 * For single-thread mode, delays aren't so critical.
		 */
		spin_lock(&data.lock);
		data.count++;
		spin_unlock(&data.lock);
//		delay(1);
	}

	return NULL;
}

int main(void)

{
	pthread_t threads[NR_THREADS];
	struct sched_param param;
	long i;

	param.sched_priority = 90;
	if (sched_setscheduler(0, SCHED_FIFO, &param) == -1)
		perror("sched_setscheduler"), exit(1);
 	data.lock = SPIN_LOCK_UNLOCKED;
	data.count = 0;

	calibrate_delay();

	for (i = 0; i < NR_THREADS; i++) {
		if (pthread_create(&threads[i], NULL, thread, (void *)i) == -1)
			perror("pthread_create"), exit(1);
	}

	go = 1;
	sched_yield();
	
	for (i = 0; i < NR_THREADS; i++) {
		if (pthread_join(threads[i], NULL) == -1)
			perror("pthread_join"), exit(1);
	}

	assert(data.count == NR_ITERS*NR_THREADS);

	exit(0);
}
#19 lore raw
Quoted 33 lines · Nick Piggin
Quoted 10 lines · Nick Piggin

In most cases, no. For the uncontended case they should be about the same. They have the same spinning behaviour. However there is a little window where they might be a bit slower I think... actually perhaps I'm wrong!

Currently if you have 4 CPUs spinning and the lock is released, all 4 CPU cachelines will be invalidated, then they will be loaded again, and found to be 0, so they all try to atomic_dec_return the counter, each one invalidating others' cachelines. 1 gets through.

Quoted 7 lines

With my queued locks, all 4 cachelines are invalidated and loaded, but only one will be allowed to proceed, and there are 0 atomic operations or stores of any kind.

So I take that back: our current spinlocks have a worse thundering herd behaviour under contention than my queued ones. So I'll definitely push the patch through.

OK, it isn't a big difference, but a user-space test is showing slightly (~2%) improvement in the contended case on a 16 core Opteron.

There is a case where the present spinlocks are almost twice as fast on this machine (in terms of aggregate throughput), and that is when a lock is taken right after it is released. This is because the same CPU will often be able to retake the lock without transitioning the cache. This is going to be a rare case for us, and would suggest suboptimal code anyway (ie. the lock should just be kept rather than dropped and retaken).

Actually, one situation where it comes up is when we drop and retake a lock that needs_lockbreak. Of course, the queued lock behaviour is desired in that case anyway.

Quoted 6 lines

However single-thread performance is presently a bit down. OTOH, the assembly generated by gcc looks like it could be improved upon (even by me :P).

This is what I've got so far. Should work for i386 and x86_64. Any enhancements or results from other CPUs would be interesting.

I slightly modified it to use cycles:

http://www.xmailserver.org/qspins.c

Here (Dual Opteron 252) queued locks (ticklocks) are about 10% slower in both cases. This is really a microbench, and assembly matter a lot. I did not have time to look at the generated one yet, but optimizing branches can help in those cases.

- Davide

#20 lore raw
Quoted 39 lines · Davide Libenzi
Quoted 37 lines · Nick Piggin
Quoted 10 lines · Nick Piggin

In most cases, no. For the uncontended case they should be about the same. They have the same spinning behaviour. However there is a little window where they might be a bit slower I think... actually perhaps I'm wrong!

Currently if you have 4 CPUs spinning and the lock is released, all 4 CPU cachelines will be invalidated, then they will be loaded again, and found to be 0, so they all try to atomic_dec_return the counter, each one invalidating others' cachelines. 1 gets through.

Quoted 7 lines

With my queued locks, all 4 cachelines are invalidated and loaded, but only one will be allowed to proceed, and there are 0 atomic operations or stores of any kind.

So I take that back: our current spinlocks have a worse thundering herd behaviour under contention than my queued ones. So I'll definitely push the patch through.

OK, it isn't a big difference, but a user-space test is showing slightly (~2%) improvement in the contended case on a 16 core Opteron.

There is a case where the present spinlocks are almost twice as fast on this machine (in terms of aggregate throughput), and that is when a lock is taken right after it is released. This is because the same CPU will often be able to retake the lock without transitioning the cache. This is going to be a rare case for us, and would suggest suboptimal code anyway (ie. the lock should just be kept rather than dropped and retaken).

Actually, one situation where it comes up is when we drop and retake a lock that needs_lockbreak. Of course, the queued lock behaviour is desired in that case anyway.

However single-thread performance is presently a bit down. OTOH, the assembly generated by gcc looks like it could be improved upon (even by me :P).

Quoted 6 lines
Quoted 2 lines

This is what I've got so far. Should work for i386 and x86_64. Any enhancements or results from other CPUs would be interesting.

I slightly modified it to use cycles:

http://www.xmailserver.org/qspins.c

Slightly more than slightly ;)

You want to have a delay _outside_ the critical section as well, for multi-thread tests, otherwise the releasing CPU often just retakes the lock (in the unqueued lock case). As I said, most kernel code should _not_ be dropping and retaking locks.

Quoted 4 lines

Here (Dual Opteron 252) queued locks (ticklocks) are about 10% slower in both cases. This is really a microbench, and assembly matter a lot. I did not have time to look at the generated one yet, but optimizing branches can help in those cases.

#21 lore raw
Quoted 10 lines · Nick Piggin
Quoted 3 lines

I slightly modified it to use cycles:

http://www.xmailserver.org/qspins.c

Slightly more than slightly ;)

You want to have a delay _outside_ the critical section as well, for multi-thread tests, otherwise the releasing CPU often just retakes the lock (in the unqueued lock case). As I said, most kernel code should _not_ be dropping and retaking locks.

Yeah. ATM it mostly does double-takes.

- Davide

#22 lore raw
In reply to Davide Libenzi
Quoted 23 lines · Davide Libenzi
Quoted 16 lines · Nick Piggin
Quoted 8 lines · Ingo Molnar
Quoted 4 lines · Nikita Danilov

Indeed, this technique is very well known. E.g.,
http://citeseer.ist.psu.edu/anderson01sharedmemory.html has a whole section (3. Local-spin Algorithms) on them, citing papers from the 1990 onward.

Quoted 6 lines

that is a cool reference! So i'd suggest to do (redo?) the patch based on those concepts and that terminology and not use 'queued spinlocks' that are commonly associated with MS's stuff. And as a result the contended case would be optimized some more via local-spin algorithms. (which is not a key thing for us, but which would be nice to have nevertheless)

Quoted 4 lines

Firstly, the terminology in that paper _is_ "queue lock", which isn't really surprising. I don't really know or care about what MS calls their locks, but I'd suggest that their queued spinlock is probably named in reference to its queueing property rather than its local spin property.

Quoted 4 lines

The method you propose is otherwise called "Ticket Lock":

http://en.wikipedia.org/wiki/Ticket_lock
http://www.cs.rochester.edu/research/synchronization/pseudocode/ss.html#ticket

Yes, a ticket based FIFO queue isn't new... I think we have a lot of xamples already in the kernel. Using them to implement queue locks obviously isn't new either.

I don't think we'd have to worry about patents.

#23 lore raw
In reply to Nick Piggin
Quoted 4 lines · On Fri, 23 Mar 2007 11:32:44 +0100 Nick Piggin <[email protected]> wrote:

I'm not as concerned about the contended performance of spinlocks

The contended case matters. Back in 2.5.something I screwed up the debug version of one of the locks (rwlock, iirc) - it was simply missing a cpu_relax(), and some people's benchmarks halved.

Quoted 2 lines

This was just something I had in mind when the hardware lock starvation issue came up

It looks like a good way to address the lru_lock starvation/capture problem. But I think I'd be more comfortable if we were to introduce it as a new lock type, rather than as a reimplementation of the existing
spin_lock(). Initially, at least.

#24 lore raw
Quoted 8 lines · Andrew Morton
Quoted 4 lines · On Fri, 23 Mar 2007 11:32:44 +0100 Nick Piggin <[email protected]> wrote:

I'm not as concerned about the contended performance of spinlocks

The contended case matters. Back in 2.5.something I screwed up the debug version of one of the locks (rwlock, iirc) - it was simply missing a cpu_relax(), and some people's benchmarks halved.

Do you have a reference?

rwlocks are a bit funny, because if they are found to be useful (that is, they get used somewhere), then it indicates there can be situations with a lot of contention and spinning.

Wheras we usually prefer not to use spinlocks in situations like that.

Not that I'm claiming the contended case doesn't matter, but I think problems there indicate a bug (and I think rwlocks are almost always questionable).

Anyway, I'll look at doing some contended case optimisations afterward.

Quoted 7 lines
Quoted 2 lines

This was just something I had in mind when the hardware lock starvation issue came up

It looks like a good way to address the lru_lock starvation/capture problem. But I think I'd be more comfortable if we were to introduce it as a new lock type, rather than as a reimplementation of the existing
spin_lock(). Initially, at least.

I'd hate to have a proliferation of lock types though. I think my queued spinlock addresses a real hardware limitation of some systems.

In situations where contention isn't a problem, then queued locks won't cause a slowdown. In situations where it is, starvation could also be a problem.