[rfc][patch 1/2] spinlock: lockbreak cleanups

[rfc][patch 1/2] spinlock: lockbreak cleanups

[Nick Piggin]

Hi,

These patches are not exactly complete yet (haven't tested many config
combinations or converted other architectures), but I want to post it
now to get consensus on whether and how to clean up the lockbreak stuff
in particular.

It gets in the way because ticket spinlocks shouldn't be just repeating
the low-level trylock to lock, because that never gives the locker a
ticket, so the FIFO order is ruined.

So RFC.

---

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?).

After this, we can no longer spin on any locks with preempt enabled
(unless that is done in arch code), but that (and spinning with
interrupts enabled) is hackish anyway: if the lock happens to be
called under a preempt or interrupt disabled section, then it is just
going to have the same problems. The real fix is to keep critical
sections short, and introduce fairer locks if there are starvation
issues.

---
Index: linux-2.6/include/linux/sched.h
===================================================================
--- linux-2.6.orig/include/linux/sched.h
+++ linux-2.6/include/linux/sched.h
@@ -1598,26 +1598,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)
+#ifdef CONFIG_PREEMPT
+# define spin_needbreak(lock)	spin_is_contended(lock)
 #else
-# define need_lockbreak(lock) 0
+# define spin_needbreak(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)
-{
-	if (need_lockbreak(lock) || need_resched())
-		return 1;
-	return 0;
-}
-
-/*
  * Reevaluate whether the task has signals pending delivery.
  * Wake the task if so.
  * This is required every time the blocked sigset_t changes.
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(&(lock)->raw_lock)
 
+#ifdef CONFIG_GENERIC_LOCKBREAK
+#define spin_is_contended(lock) ((lock)->break_lock)
+#else
+#define spin_is_contended(lock)	__raw_spin_is_contended(&(lock)->raw_lock)
+#endif
+
 /**
  * spin_unlock_wait - wait until the spinlock gets unlocked
  * @lock: the spinlock in question.
Index: linux-2.6/fs/jbd/checkpoint.c
===================================================================
--- linux-2.6.orig/fs/jbd/checkpoint.c
+++ linux-2.6/fs/jbd/checkpoint.c
@@ -347,7 +347,8 @@ restart:
 				break;
 			}
 			retry = __process_buffer(journal, jh, bhs,&batch_count);
-			if (!retry && lock_need_resched(&journal->j_list_lock)){
+			if (!retry && (need_resched() ||
+				spin_needbreak(&journal->j_list_lock))) {
 				spin_unlock(&journal->j_list_lock);
 				retry = 1;
 				break;
Index: linux-2.6/fs/jbd/commit.c
===================================================================
--- linux-2.6.orig/fs/jbd/commit.c
+++ linux-2.6/fs/jbd/commit.c
@@ -265,7 +265,7 @@ write_out_data:
 			put_bh(bh);
 		}
 
-		if (lock_need_resched(&journal->j_list_lock)) {
+		if (need_resched() || spin_needbreak(&journal->j_list_lock)) {
 			spin_unlock(&journal->j_list_lock);
 			goto write_out_data;
 		}
Index: linux-2.6/fs/jbd2/checkpoint.c
===================================================================
--- linux-2.6.orig/fs/jbd2/checkpoint.c
+++ linux-2.6/fs/jbd2/checkpoint.c
@@ -347,7 +347,8 @@ restart:
 				break;
 			}
 			retry = __process_buffer(journal, jh, bhs,&batch_count);
-			if (!retry && lock_need_resched(&journal->j_list_lock)){
+			if (!retry && (need_resched() ||
+				spin_needbreak(&journal->j_list_lock))) {
 				spin_unlock(&journal->j_list_lock);
 				retry = 1;
 				break;
Index: linux-2.6/fs/jbd2/commit.c
===================================================================
--- linux-2.6.orig/fs/jbd2/commit.c
+++ linux-2.6/fs/jbd2/commit.c
@@ -265,7 +265,7 @@ write_out_data:
 			put_bh(bh);
 		}
 
-		if (lock_need_resched(&journal->j_list_lock)) {
+		if (need_resched() || spin_needbreak(&journal->j_list_lock)) {
 			spin_unlock(&journal->j_list_lock);
 			goto write_out_data;
 		}
Index: linux-2.6/include/linux/spinlock_up.h
===================================================================
--- linux-2.6.orig/include/linux/spinlock_up.h
+++ linux-2.6/include/linux/spinlock_up.h
@@ -64,6 +64,8 @@ static inline void __raw_spin_unlock(raw
 # define __raw_spin_trylock(lock)	({ (void)(lock); 1; })
 #endif /* DEBUG_SPINLOCK */
 
+#define __raw_spin_is_contended(lock)	(((void)(lock), 0))
+
 #define __raw_read_can_lock(lock)	(((void)(lock), 1))
 #define __raw_write_can_lock(lock)	(((void)(lock), 1))
 
Index: linux-2.6/kernel/sched.c
===================================================================
--- linux-2.6.orig/kernel/sched.c
+++ linux-2.6/kernel/sched.c
@@ -4805,19 +4805,15 @@ EXPORT_SYMBOL(cond_resched);
  */
 int cond_resched_lock(spinlock_t *lock)
 {
+	int resched = need_resched() && system_state == SYSTEM_RUNNING;
 	int ret = 0;
 
-	if (need_lockbreak(lock)) {
+	if (spin_needbreak(lock) || resched) {
 		spin_unlock(lock);
-		cpu_relax();
-		ret = 1;
-		spin_lock(lock);
-	}
-	if (need_resched() && system_state == SYSTEM_RUNNING) {
-		spin_release(&lock->dep_map, 1, _THIS_IP_);
-		_raw_spin_unlock(lock);
-		preempt_enable_no_resched();
-		__cond_resched();
+		if (resched && need_resched())
+			__cond_resched();
+		else
+			cpu_relax();
 		ret = 1;
 		spin_lock(lock);
 	}
Index: linux-2.6/mm/memory.c
===================================================================
--- linux-2.6.orig/mm/memory.c
+++ linux-2.6/mm/memory.c
@@ -516,8 +516,7 @@ again:
 		if (progress >= 32) {
 			progress = 0;
 			if (need_resched() ||
-			    need_lockbreak(src_ptl) ||
-			    need_lockbreak(dst_ptl))
+			    spin_needbreak(src_ptl) || spin_needbreak(dst_ptl))
 				break;
 		}
 		if (pte_none(*src_pte)) {
@@ -856,7 +855,7 @@ unsigned long unmap_vmas(struct mmu_gath
 			tlb_finish_mmu(*tlbp, tlb_start, start);
 
 			if (need_resched() ||
-				(i_mmap_lock && need_lockbreak(i_mmap_lock))) {
+				(i_mmap_lock && spin_needbreak(i_mmap_lock))) {
 				if (i_mmap_lock) {
 					*tlbp = NULL;
 					goto out;
@@ -1838,8 +1837,7 @@ again:
 
 	restart_addr = zap_page_range(vma, start_addr,
 					end_addr - start_addr, details);
-	need_break = need_resched() ||
-			need_lockbreak(details->i_mmap_lock);
+	need_break = need_resched() || spin_needbreak(details->i_mmap_lock);
 
 	if (restart_addr >= end_addr) {
 		/* We have now completed this vma: mark it so */
Index: linux-2.6/arch/x86_64/Kconfig
===================================================================
--- linux-2.6.orig/arch/x86_64/Kconfig
+++ linux-2.6/arch/x86_64/Kconfig
@@ -32,6 +32,11 @@ config GENERIC_TIME_VSYSCALL
 	bool
 	default y
 
+config GENERIC_LOCKBREAK
+	bool
+	default y
+	depends on SMP && PREEMPT
+
 config ZONE_DMA32
 	bool
 	default y
Index: linux-2.6/include/linux/spinlock_types.h
===================================================================
--- linux-2.6.orig/include/linux/spinlock_types.h
+++ linux-2.6/include/linux/spinlock_types.h
@@ -19,7 +19,7 @@
 
 typedef struct {
 	raw_spinlock_t raw_lock;
-#if defined(CONFIG_PREEMPT) && defined(CONFIG_SMP)
+#ifdef CONFIG_GENERIC_LOCKBREAK
 	unsigned int break_lock;
 #endif
 #ifdef CONFIG_DEBUG_SPINLOCK
@@ -35,7 +35,7 @@ typedef struct {
 
 typedef struct {
 	raw_rwlock_t raw_lock;
-#if defined(CONFIG_PREEMPT) && defined(CONFIG_SMP)
+#ifdef CONFIG_GENERIC_LOCKBREAK
 	unsigned int break_lock;
 #endif
 #ifdef CONFIG_DEBUG_SPINLOCK
Index: linux-2.6/kernel/spinlock.c
===================================================================
--- linux-2.6.orig/kernel/spinlock.c
+++ linux-2.6/kernel/spinlock.c
@@ -65,8 +65,7 @@ EXPORT_SYMBOL(_write_trylock);
  * even on CONFIG_PREEMPT, because lockdep assumes that interrupts are
  * not re-enabled during lock-acquire (which the preempt-spin-ops do):
  */
-#if !defined(CONFIG_PREEMPT) || !defined(CONFIG_SMP) || \
-	defined(CONFIG_DEBUG_LOCK_ALLOC)
+#if !defined(CONFIG_GENERIC_LOCKBREAK) || defined(CONFIG_DEBUG_LOCK_ALLOC)
 
 void __lockfunc _read_lock(rwlock_t *lock)
 {

[rfc][patch 2/2] x86_64: FIFO ticket spinlocks

[Nick Piggin]

Introduce ticket lock spinlocks for x86-64 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.

The memory ordering of the lock does conform to Intel's standards, and the
implementation has been reviewed by an Intel engineer.

XXX: numbers here

The algorithm also tells us how many CPUs are contending the lock, so
lockbreak becomes trivial and we no longer waste 4 bytes per spinlock for it.

---
Index: linux-2.6/include/asm-x86_64/spinlock.h
===================================================================
--- linux-2.6.orig/include/asm-x86_64/spinlock.h
+++ linux-2.6/include/asm-x86_64/spinlock.h
@@ -19,67 +19,81 @@
 
 static inline int __raw_spin_is_locked(raw_spinlock_t *lock)
 {
-	return *(volatile signed int *)(&(lock)->slock) <= 0;
+	int tmp = *(volatile signed int *)(&(lock)->slock);
+
+	return (((tmp >> 8) & 0xff) != (tmp & 0xff));
 }
 
-static inline void __raw_spin_lock(raw_spinlock_t *lock)
+static inline int __raw_spin_is_contended(raw_spinlock_t *lock)
 {
-	asm volatile(
-		"\n1:\t"
-		LOCK_PREFIX " ; decl %0\n\t"
-		"jns 2f\n"
-		"3:\n"
-		"rep;nop\n\t"
-		"cmpl $0,%0\n\t"
-		"jle 3b\n\t"
-		"jmp 1b\n"
-		"2:\t" : "=m" (lock->slock) : : "memory");
+	int tmp = *(volatile signed int *)(&(lock)->slock);
+
+	return (((tmp >> 8) & 0xff) - (tmp & 0xff)) > 1;
 }
 
-/*
- * Same as __raw_spin_lock, but reenable interrupts during spinning.
- */
-#ifndef CONFIG_PROVE_LOCKING
-static inline void __raw_spin_lock_flags(raw_spinlock_t *lock, unsigned long flags)
+static inline void __raw_spin_lock(raw_spinlock_t *lock)
 {
-	asm volatile(
-		"\n1:\t"
-		LOCK_PREFIX " ; decl %0\n\t"
-		"jns 5f\n"
-		"testl $0x200, %1\n\t"	/* interrupts were disabled? */
-		"jz 4f\n\t"
-	        "sti\n"
-		"3:\t"
-		"rep;nop\n\t"
-		"cmpl $0, %0\n\t"
-		"jle 3b\n\t"
-		"cli\n\t"
+	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 head, which takes care of memory ordering issues
+	 * and should be optimal for the uncontended case. Note the tail must
+	 * be in the high byte, otherwise the 16-bit wide increment of the low
+	 * byte would carry up and contaminate the high byte.
+	 */
+
+	__asm__ __volatile__ (
+		LOCK_PREFIX "xaddw %w0, %1\n"
+		"1:\t"
+		"cmpb %h0, %b0\n\t"
+		"je 2f\n\t"
+		"rep ; nop\n\t"
+		"movb %1, %b0\n\t"
+		"lfence\n\t"
 		"jmp 1b\n"
-		"4:\t"
-		"rep;nop\n\t"
-		"cmpl $0, %0\n\t"
-		"jg 1b\n\t"
-		"jmp 4b\n"
-		"5:\n\t"
-		: "+m" (lock->slock) : "r" ((unsigned)flags) : "memory");
+		"2:"
+		:"+Q" (inc), "+m" (lock->slock)
+		:
+		:"memory", "cc");
 }
-#endif
+
+#define __raw_spin_lock_flags(lock, flags) __raw_spin_lock(lock)
 
 static inline int __raw_spin_trylock(raw_spinlock_t *lock)
 {
-	int oldval;
+	short tmp;
+        short oldval;
 
 	asm volatile(
-		"xchgl %0,%1"
-		:"=q" (oldval), "=m" (lock->slock)
-		:"0" (0) : "memory");
+                "movw %2,%w0\n\t"
+                "cmpb %h0, %b0\n\t"
+                "jne 1f\n\t"
+                "movw %w0,%w1\n\t"
+                "incb %h1\n\t"
+                LOCK_PREFIX "cmpxchgw %w1,%2\n\t"
+                "1:"
+                :"=a" (oldval), "=Q" (tmp), "+m" (lock->slock)
+                :
+		: "memory", "cc");
 
-	return oldval > 0;
+	return ((oldval & 0xff) == ((oldval >> 8) & 0xff));
 }
 
 static inline void __raw_spin_unlock(raw_spinlock_t *lock)
 {
-	asm volatile("movl $1,%0" :"=m" (lock->slock) :: "memory");
+	__asm__ __volatile__(
+		"incb %0"
+		:"+m" (lock->slock)
+		:
+		:"memory", "cc");
 }
 
 static inline void __raw_spin_unlock_wait(raw_spinlock_t *lock)
Index: linux-2.6/include/asm-x86_64/spinlock_types.h
===================================================================
--- linux-2.6.orig/include/asm-x86_64/spinlock_types.h
+++ linux-2.6/include/asm-x86_64/spinlock_types.h
@@ -9,7 +9,7 @@ typedef struct {
 	unsigned int slock;
 } raw_spinlock_t;
 
-#define __RAW_SPIN_LOCK_UNLOCKED	{ 1 }
+#define __RAW_SPIN_LOCK_UNLOCKED	{ 0 }
 
 typedef struct {
 	unsigned int lock;
Index: linux-2.6/arch/x86_64/Kconfig
===================================================================
--- linux-2.6.orig/arch/x86_64/Kconfig
+++ linux-2.6/arch/x86_64/Kconfig
@@ -34,8 +34,7 @@ config GENERIC_TIME_VSYSCALL
 
 config GENERIC_LOCKBREAK
 	bool
-	default y
-	depends on SMP && PREEMPT
+	default n
 
 config ZONE_DMA32
 	bool

Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks

[Alan Cox]

> 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.

This has a 255 processor limit (worst case). That should probably be
clearly documented for the future.

Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks

[Nick Piggin]

On Mon, Jul 16, 2007 at 10:16:54AM +0100, Alan Cox wrote:
> > 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.
> 
> This has a 255 processor limit (worst case). That should probably be
> clearly documented for the future.

Yeah good point. I added an #error for it.

Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks

[Ingo Molnar]

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

> [...] trylock is more significantly slower, but they are relatively 
> rare.

trylock is the main thing that the spinlock debugging code uses, and 
SPINLOCK_DEBUG is frequently enabled by distro kernels. OTOH, the cost 
looks like to be +5 instructions, right? Still ...

	Ingo

Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks

[Nick Piggin]

On Mon, Jul 16, 2007 at 11:26:46AM +0200, Ingo Molnar wrote:
> 
> * Nick Piggin <npiggin@suse.de> wrote:
> 
> > [...] trylock is more significantly slower, but they are relatively 
> > rare.
> 
> trylock is the main thing that the spinlock debugging code uses, and 
> SPINLOCK_DEBUG is frequently enabled by distro kernels. OTOH, the cost 
> looks like to be +5 instructions, right? Still ...

Which trylocks do you mean? The lockbreak spinlocks use trylock, but
those are not used with the ticket version.

I wouldn't be against adding an option between either of the lock
types, if there was value in it. But I would like to default ticket
locks to "y", at least in -rc kernels, in order to see if performance
goes down anywhere.

Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks

[Ingo Molnar]

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

> On Mon, Jul 16, 2007 at 11:26:46AM +0200, Ingo Molnar wrote:
> > 
> > * Nick Piggin <npiggin@suse.de> wrote:
> > 
> > > [...] trylock is more significantly slower, but they are relatively 
> > > rare.
> > 
> > trylock is the main thing that the spinlock debugging code uses, and 
> > SPINLOCK_DEBUG is frequently enabled by distro kernels. OTOH, the cost 
> > looks like to be +5 instructions, right? Still ...
> 
> Which trylocks do you mean? The lockbreak spinlocks use trylock, but 
> those are not used with the ticket version.

the trylocks in lib/spinlock-debug.c:

 static void __spin_lock_debug(spinlock_t *lock)
 {
 ...
                         if (__raw_spin_trylock(&lock->raw_lock))
                                 return;
 ...
 void _raw_spin_lock(spinlock_t *lock)
 {
         debug_spin_lock_before(lock);
         if (unlikely(!__raw_spin_trylock(&lock->raw_lock)))
                 __spin_lock_debug(lock);
         debug_spin_lock_after(lock);
 }

am i missing something?

	Ingo

Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks

[Nick Piggin]

On Mon, Jul 16, 2007 at 11:49:40AM +0200, Ingo Molnar wrote:
> 
> * Nick Piggin <npiggin@suse.de> wrote:
> 
> > On Mon, Jul 16, 2007 at 11:26:46AM +0200, Ingo Molnar wrote:
> > > 
> > > * Nick Piggin <npiggin@suse.de> wrote:
> > > 
> > > > [...] trylock is more significantly slower, but they are relatively 
> > > > rare.
> > > 
> > > trylock is the main thing that the spinlock debugging code uses, and 
> > > SPINLOCK_DEBUG is frequently enabled by distro kernels. OTOH, the cost 
> > > looks like to be +5 instructions, right? Still ...
> > 
> > Which trylocks do you mean? The lockbreak spinlocks use trylock, but 
> > those are not used with the ticket version.
> 
> the trylocks in lib/spinlock-debug.c:
> 
>  static void __spin_lock_debug(spinlock_t *lock)
>  {
>  ...
>                          if (__raw_spin_trylock(&lock->raw_lock))
>                                  return;
>  ...
>  void _raw_spin_lock(spinlock_t *lock)
>  {
>          debug_spin_lock_before(lock);
>          if (unlikely(!__raw_spin_trylock(&lock->raw_lock)))
>                  __spin_lock_debug(lock);
>          debug_spin_lock_after(lock);
>  }
> 
> am i missing something?

No, I missed that. Yeah, that would get a bit slower, but I'm not sure
if it would be a problem on a kernel where you have spinlock debuggin
on anyway.

If it becomes a problem, we could perhaps do a version for ticket locks
that first takes a ticket, and then is for up to a second before
printing the stuck lock message. That would make the performance hit go away.

Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks

[Andi Kleen]

When you revamp everything I guess it would make the locks
easier to read to just put them into a .S file? They're
out of line anyways.

In general they look ok.

>  
>  static inline void __raw_spin_unlock(raw_spinlock_t *lock)
>  {
> -	asm volatile("movl $1,%0" :"=m" (lock->slock) :: "memory");
> +	__asm__ __volatile__(

Minor nit: please don't use these underlined keywords. They just look
ugly and asm volatile works as well.

-Andi

Re: [rfc][patch 2/2] x86_64: FIFO ticket spinlocks

[Nick Piggin]

On Tue, Jul 17, 2007 at 04:25:42PM +0200, Andi Kleen wrote:
> 
> 
> When you revamp everything I guess it would make the locks
> easier to read to just put them into a .S file? They're
> out of line anyways.

It is a bit tricky because of the way kernel/spinlock.c uses
the the inline asm (that, and unlocks are inlined), and some
of the debugging code.

Also, I'm not exactly sure what is the best way to clean up
spinlocks, if it is even possible. I'm afraid to touch it
more than I have to :)

> 
> In general they look ok.
> 
> >  
> >  static inline void __raw_spin_unlock(raw_spinlock_t *lock)
> >  {
> > -	asm volatile("movl $1,%0" :"=m" (lock->slock) :: "memory");
> > +	__asm__ __volatile__(
> 
> Minor nit: please don't use these underlined keywords. They just look
> ugly and asm volatile works as well.

OK, I like that better too. I didn't even realise I changed this
because it is mechanical to do the __. That's good to know and I'll
change my habit now.