Hi,
I'd like to propose these patches for the x86 tree for a bit more exposure

and testing. Or at least get some discussion going again.
Just for fun I also had a shot at merging the headers, as they become a

lot more similar after this with the removal of the paravirt crud.
Nick

-

Glommer posted a set of patches the other day to implement x86-64

paravirt, which unifies lots of things including spinlocks.  But if

you've removed the need to diddle with sti/cli, then that works too...
    J

-

Merge spinlock_32.h and spinlock_64.h into spinlock.h.
Signed-off-by: Nick Piggin <npiggin@suse.de>

---

Index: linux-2.6/include/asm-x86/spinlock.h

===================================================================

--- linux-2.6.orig/include/asm-x86/spinlock.h

+++ linux-2.6/include/asm-x86/spinlock.h

@@ -1,5 +1,211 @@

-#ifdef CONFIG_X86_32

-# include "spinlock_32.h"

+#ifndef __ASM_SPINLOCK_H

+#define __ASM_SPINLOCK_H

+

+#include <asm/atomic.h>

+#include <asm/rwlock.h>

+#include <asm/page.h>

+#include <asm/processor.h>

+#include <linux/compiler.h>

+

+/*

+ * Your basic SMP spinlocks, allowing only a single CPU anywhere

+ *

+ * Simple spin lock operations.  There are two variants, one clears IRQ's

+ * on the local processor, one does not.

+ *

+ * These are fair FIFO ticket locks, which are currently limited to 256

+ * CPUs.

+ *

+ * (the type definitions are in asm/spinlock_types.h)

+ */

+

+#if (NR_CPUS > 256)

+#error spinlock supports a maximum of 256 CPUs

+#endif

+

+static inline int __raw_spin_is_locked(raw_spinlock_t *lock)

+{

+	int tmp = *(volatile signed int *)(&(lock)->slock);

+

+	return (((tmp >> 8) & 0xff) != (tmp & 0xff));

+}

+

+static inline int __raw_spin_is_contended(raw_spinlock_t *lock)

+{

+	int tmp = *(volatile signed int *)(&(lock)->slock);

+

+	return (((tmp >> 8) & 0xff) - (tmp & 0xff)) > 1;

+}

+

+static inline void __raw_spin_lock(raw_spinlock_t *lock)

+{

+	short inc = 0x0100;

+

+	/*

+	 * Ticket locks are conceptually two bytes, one indicating the current

+	 * head of the queue, and the other indicating the current tail. The

+	 * lock is acquired by atomically noting the tail and incrementing it

+	 * by one (thus adding ourself to the queue and noting our position),

+	 * then waiting until the head becomes equal to the the initial value

+	 * of the tail.

+	 *

+	 * This uses a 16-bit xadd to increment the tail and also load the

+	 * position of the he...
[ message continues ]

Prepare for merging 32 and 64 bit spinlocks, by making them identical

(except for the OOSTORE thing). raw_read_lock and raw_write_lock get a

relaxed register constraint, and 64-bit has a few "=m" constraints changed

to "+m". I hope these things actually make the code better.
Signed-off-by: Nick Piggin <npiggin@suse.de>

---

Index: linux-2.6/include/asm-x86/spinlock_32.h

===================================================================

--- linux-2.6.orig/include/asm-x86/spinlock_32.h

+++ linux-2.6/include/asm-x86/spinlock_32.h

@@ -98,14 +98,15 @@ static inline int __raw_spin_trylock(raw

 	return ret;

 }
-#if defined(CONFIG_X86_OOSTORE) || defined(CONFIG_X86_PPRO_FENCE)

+#if defined(CONFIG_X86_32) && \

+	(defined(CONFIG_X86_OOSTORE) || defined(CONFIG_X86_PPRO_FENCE))

 /*

  * On PPro SMP or if we are using OOSTORE, we use a locked operation to unlock

  * (PPro errata 66, 92)

  */

-#define UNLOCK_LOCK_PREFIX LOCK_PREFIX

+# define UNLOCK_LOCK_PREFIX LOCK_PREFIX

 #else

-#define UNLOCK_LOCK_PREFIX

+# define UNLOCK_LOCK_PREFIX

 #endif
 static inline void __raw_spin_unlock(raw_spinlock_t *lock)

@@ -135,49 +136,42 @@ static inline void __raw_spin_unlock_wai

  *

  * On x86, we implement read-write locks as a 32-bit counter

  * with the high bit (sign) being the "contended" bit.

- *

- * The inline assembly is non-obvious. Think about it.

- *

- * Changed to use the same technique as rw semaphores.  See

- * semaphore.h for details.  -ben

- *

- * the helpers are in arch/i386/kernel/semaphore.c

  */
 /**

  * read_can_lock - would read_trylock() succeed?

  * @lock: the rwlock in question.

  */

-static inline int __raw_read_can_lock(raw_rwlock_t *x)

+static inline int __raw_read_can_lock(raw_rwlock_t *lock)

 {

-	return (int)(x)->lock > 0;

+	return (int)(lock)->lock > 0;

 }
 /**

  * write_can_lock - would write_trylock() succeed?

  * @lock: the rwlock in question.

  */

-static inline int __raw_write_can_lock(raw_rwlock_t *x)

+static inl...
[ message continues ]

Introduce ticket lock spinlocks for x86 which are FIFO. The implementation

is described in the comments. The straight-line lock/unlock instruction

sequence is slightly slower than the dec based locks on modern x86 CPUs,

however the difference is quite small on Core2 and Opteron when working out of

cache, and becomes almost insignificant even on P4 when the lock misses cache.

trylock is more significantly slower, but they are relatively rare.
On an 8 core (2 socket) Opteron, spinlock unfairness is extremely noticable,

with a userspace test having a difference of up to 2x runtime per thread, and

some threads are starved or "unfairly" granted the lock up to 1 000 000 (!)

times. After this patch, all threads appear to finish at exactly the same

time.
The memory ordering of the lock does conform to x86 standards, and the

implementation has been reviewed by Intel and AMD engineers.
The algorithm also tells us how many CPUs are contending the lock, so

lockbreak becomes trivial and we no longer have to waste 4 bytes per

spinlock for it.
After this, we can no longer spin on any locks with preempt enabled

and cannot reenable interrupts when spinning on an irq safe lock, because

at that point we have already taken a ticket and the would deadlock if

the same CPU tries to take the lock again.  These are questionable anyway:

if the lock happens to be called under a preempt or interrupt disabled section,

then it will just have the same latency problems. The real fix is to keep

critical sections short, and ensure locks are reasonably fair (which this

patch does).
Signed-off-by: Nick Piggin <npiggin@suse.de>
---

Index: linux-2.6/include/asm-x86/spinlock_64.h

===================================================================

--- linux-2.6.orig/include/asm-x86/spinlock_64.h

+++ linux-2.6/include/asm-x86/spinlock_64.h

@@ -12,74 +12,98 @@

  * Simple spin lock operations.  There are two variants, one clears IRQ's

  * on the local processor, one does not.

  *

- * We make no fairnes...
[ message continues ]

There's also a very easy way to get better fairness with our current spinlocks:

use xchg to release the lock instead of mov.
-

That does nothing at all.
Yes, it slows the unlock down, which in turn on some machines will make it

easier for another core/socket to get it, but it's purely about the

slowdown, nothing else. 
			Linus

-

Yeah, it's not such a good idea... it slows down the single threaded case

like crazy. On my dual core core2:
_Single thread_

inc-lock in cache takes 21.94ns

xadd-lock in cache takes 22.64ns

xchg-lock in cache takes 35.21ns
inc-lock out of cache takes 140.73ns

xadd-lock out of cache takes 141.15ns

xchg-lock out of cache takes 155.13ns
In the contended multi-threaded tight loop, the xchg lock is slower than inc

lock but still beats the fair xadd lock, but that's only because it is

just as unfair if not more so on this hardware (runtime difference of up to

about 10%)

-

I meant xchg for unlock, not lock.
-

That is for unlock. 2x the number of atomic operations ~= 2x the cost.
-

On 11/01/2007 10:03 AM, Nick Piggin wrote:
If you really thought you might get long queues, you could figure out

how far back you are and use that to determine how long to wait before

testing the lock again. That cmpb could become a subb without adding

overhead to the fast path -- that would give you the queue length (or

its complement anyway.)
-

Indeed. You can use this as a really nice input into a backoff

algorithm (eg. if you're next in line, don't back off, or at least

don't go into exponential backoff; if you've got people in front

of you, start throttling harder).
I think I'll leave that to SGI if they come up with a big x86 SSI ;)

-

I had observed this phenomenon on some 8-ways here as well, but I didn't

have the bandwidth to code something up.  Thumbs up!
Regards,

-Greg

-

Can you test under interesting loads?
We're interested in:

 - is the unfairness fix really noticeable (or does it just move the

   problem somewhere else, and there is no real change in behaviour)

 - what is the performance impact?
In particular, unfair spinlocks have the potential to perform much better.

Not so much because the spinlock itself acts all that differently, but

because being unfair also fundmanetally tends to keep the data structures

that are *protected* by the spinlock on just one CPU.
So "unfair" is obviously always bad. Except when it isn't. I'd personally

like to merge the ticket spinlocks, but I'd really like to have people who

have real loads where they matter actually also do some performance

testing. Because I do think it will potentially be a performance downer. 
(I obviously hope it won't be, but..)
		Linus

-

I see where you are going here, and I mostly agree.  I think the key is

that "given equal contention, let the guy with the hottest cache win".

The problem with the current implementation is that the spinlocks have

no way to gauge the details of the contention.  They can only gauge

instantaneous snapshots of state as viewed by each TSL invocation, which

effectively resets your position each time.
On the flip side, Nick's patches take the opposite extreme.  If a lock

is contended, get in line. ;)  This has the desirable property of

avoiding starvation.  However, it will also tend to cause more bouncing

since you are virtually guaranteed not to re-win the contended lock, as
My issue here is that this behavior can also be described as precisely

part of the problem being addressed:  That is, both CPUs presumably

*want/need* access to the data or they wouldn't be taking the spinlock

to begin with.  So its really not a question of keeping the structures

on one cpu per se (at least, not for unbounded durations or the system

won't operate properly).
Rather, I think the key is to minimize the impact by bouncing things

intelligently. ;)  I.e. If all things are equal, favor the hottest task

so the data only bounces once instead of twice.  Outside of this

condition, operate strict FIFO.  If we can reasonably calculate when

this optimization is possible, we will have the best of both worlds.  I

have some ideas about ways to extend Nicks algorithm to support this

which I will submit ASAP.
I think the rest of what you said is very fair:  Prove that it's a

problem, this concept helps, and we don't make things worse ;)
Will do, ASAP.
Regards,

-Greg
-

On Thu, 1 Nov 2007 09:38:22 -0700 (PDT)
Larry Woodman managed to wedge the VM into a state where, on his

4x dual core system, only 2 cores (on the same CPU) could get the

zone->lru_lock overnight.  The other 6 cores on the system were

just spinning, without being able to get the lock.
On the other hand, spinlock contention in the page replacement

code is just a symptom of the fact that we scan too many pages.

It can probably be fixed in other ways...
--

"Debugging is twice as hard as writing the code in the first place.

Therefore, if you write the code as cleverly as possible, you are,

by definition, not smart enough to debug it." - Brian W. Kernighan

-

.. and this is almost always the result of a locking *bug*, not unfairness

per se. IOW, unfairness just ends up showing the bug in the first place.
		Linus

-

That's quite incredible, considering that the CPUs actually _taking_

the locks also drop the locks and do quite a bit of work before taking

them again (ie. they take them to pull pages off the LRU, but then

do a reasonable amount of work to remove each one from pagecache before

refilling from the LRU).
Possibly actually that is a *more* difficult case for the HW to handle:

once the CPU actually goes away and operates on other cachelines, it

may get a little more difficult to detect that it is causing starvation
I'd almost agree, but there are always going to be corner cases where

we get multiple contentions on a spinlock -- the fact that a lock is

needed at all obviously suggests that it can be contended. The LRU locking

could be improved, but you could have eg. scheduler runqueue lock starvation

if the planets lined up just right, and it is a little more difficult to

improve on runqueue locking.
Anyway, I also think this is partially a hardware issue, and as muliple

cores, threads, and sockets get more common, I hope it will improve (it

affects Intel CPUs as well as AMD). So it is possible to have an option

to switch between locks if the hardware is fairer, but I want to get

as much exposure with this locking as possible for now, to see if there

is any funny performance corner cases exposed (which quite possibly will

turn out to be caused by suboptimal locking itself).
Anyway, if this can make its way to the x86 tree, I think it will get

pulled into -mm (?) and get some exposure...
-

ok, we can certainly try it there. Your code is really nifty.
	Ingo

-

Anything particular I have to do to get it into the x86 tree? And

presumably that tree is going to be picked up by Andrew at some

point? (-mm exposure is the main objective here, the only reason I

didn't send it to Andrew directly is in the interests of doing the
Thanks. One of the CPU engineers at Intel asked to use it as their reference

ticket lock code sequence, which was pretty cool :)

-

On Fri, 2 Nov 2007 07:42:20 +0100
In case of the zone->lru_lock, grabbing the spinlock does

not mean that the process is letting go of the cacheline.
On the contrary, once the spinlock has been grabbed, the

real cacheline prodding begins.
--

"Debugging is twice as hard as writing the code in the first place.

Therefore, if you write the code as cleverly as possible, you are,

by definition, not smart enough to debug it." - Brian W. Kernighan

-

I didn't say that, though. Obviously the hardware can't do anything

about starvating until a lock is released.

-

On Thu, 1 Nov 2007 18:19:41 -0700 (PDT)
No argument there.  If you have the kind of lock contention where

fairness matters, the contention is probably what needs to be fixed,

not the locking mechanism.
Having said that, making bugs like that less likely to totally wedge

a system would be a good thing for everybody who uses Linux in

production.  Exposing bugs is good for development, bad for business.
--

"Debugging is twice as hard as writing the code in the first place.

Therefore, if you write the code as cleverly as possible, you are,

by definition, not smart enough to debug it." - Brian W. Kernighan

-

The break_lock data structure and code for spinlocks is quite nasty.

Not only does it double the size of a spinlock but it changes locking to

a potentially less optimal trylock.
Put all of that under CONFIG_GENERIC_LOCKBREAK, and introduce a

__raw_spin_is_contended that uses the lock data itself to determine whether

there are waiters on the lock, to be used if CONFIG_GENERIC_LOCKBREAK is

not set.
Rename need_lockbreak to spin_needbreak, make it use spin_is_contended to

decouple it from the spinlock implementation, and make it typesafe (rwlocks

do not have any need_lockbreak sites -- why do they even get bloated up

with that break_lock then?).
Signed-off-by: Nick Piggin <npiggin@suse.de>
---

Index: linux-2.6/include/linux/sched.h

===================================================================

--- linux-2.6.orig/include/linux/sched.h

+++ linux-2.6/include/linux/sched.h

@@ -1854,23 +1854,16 @@ extern int cond_resched_softirq(void);
 /*

  * Does a critical section need to be broken due to another

- * task waiting?:

+ * task waiting?: (technically does not depend on CONFIG_PREEMPT,

+ * but a general need for low latency)

  */

-#if defined(CONFIG_PREEMPT) && defined(CONFIG_SMP)

-# define need_lockbreak(lock) ((lock)->break_lock)

-#else

-# define need_lockbreak(lock) 0

-#endif

-

-/*

- * Does a critical section need to be broken due to another

- * task waiting or preemption being signalled:

- */

-static inline int lock_need_resched(spinlock_t *lock)

+static inline int spin_needbreak(spinlock_t *lock)

 {

-	if (need_lockbreak(lock) || need_resched())

-		return 1;

+#ifdef CONFIG_PREEMPT

+	return spin_is_contended(lock);

+#else

 	return 0;

+#endif

 }
 /*

Index: linux-2.6/include/linux/spinlock.h

===================================================================

--- linux-2.6.orig/include/linux/spinlock.h

+++ linux-2.6/include/linux/spinlock.h

@@ -120,6 +120,12 @@ do {								\
 #define spin_is_locked(lock)	__raw_spin_is_locked(&(l...
[ message continues ]

IIRC Lee has a few patches floating about that do introduce lockbreak

stuff for rwlocks.
-

Well that would be a good reason to introduce a break_lock for them,

but previously not so much... we have rwlocks in some slightly space

critical structures (vmas, inodes, etc).
I guess it was done to make the "template" hacks eaiser. I don't really

find that in good taste, especially for important core infrastructure.

Anyway.

-

Actually, what I had/have is a cond_resched_rwlock() that I needed to

convert the i_mmap_lock() to rw for testing reclaim scalability.  [I've

seen a large system running an Oracle OLTP load hang spitting "cpu soft

lockup" messages with all cpus spinning on a i_mmap_lock spin lock.]

One of the i_mmap_lock paths uses cond_resched_lock() for spin locks.

To do a straight forward conversion [and maybe that isn't the right

approach], I created the cond_resched_rwlock() function by generalizing

the cond_sched_lock() code and creating both spin and rw lock wrappers.

I took advantage of the fact that, currently, need_lockbreak() is a

macro and that both spin and rw locks have/had the break_lock member.

Typesafe functions would probably be preferrable, if we want to keep

break_lock for rw spin locks.
Here's the most recent posting:
	http://marc.info/?l=linux-mm&m=118980356306014&w=4
See the changes to sched.[ch].  Should apply to 23-mm1 with offsets and

minor fixup in fs/inode.c.
Lee
-

yep. I'm too in favor of keeping the need-lockbreak mechanism and its

type-insensitive data structure. We've got way too many locking

primitives and keeping them all sorted is nontrivial already. I wouldnt

mind seeing the need_lockbreak flag move into one of the high bits of

spinlocks though, to compress size.
	Ingo

-

I think a large contributor to that is being a bit clever with indirections

and cute code (eg. like this template stuff), rather than having two types of

spinlocks instead of one.
-