Skip to contentSkip to conversation

spinlock: lockbreak cleanups

RFC PATCH In review Nick Piggin 4 participants 10 messages Jul 16, 2007 – Jul 17, 2007

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/2 spinlock: lockbreak cleanups

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.

---

include/linux/sched.h +5 -15
Index: 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.
include/linux/spinlock.h +6 -0
Index: 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.
fs/jbd/checkpoint.c +2 -1
Index: 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;
fs/jbd/commit.c +1 -1
Index: 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;
 		}
fs/jbd2/checkpoint.c +2 -1
Index: 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;
fs/jbd2/commit.c +1 -1
Index: 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;
 		}
include/linux/spinlock_up.h +2 -0
Index: 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))
 
kernel/sched.c +6 -10
Index: 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);
 	}
mm/memory.c +3 -5
Index: 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 */
arch/x86_64/Kconfig +5 -0
Index: 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
include/linux/spinlock_types.h +2 -2
Index: 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
kernel/spinlock.c +1 -2
Index: 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)
 {
#1 lore raw

RFC PATCH 2/2 x86_64: FIFO ticket spinlocks

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.

---

include/asm-x86_64/spinlock.h +57 -43
Index: 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)
include/asm-x86_64/spinlock_types.h +1 -1
Index: 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;
arch/x86_64/Kconfig +1 -2
Index: 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
#2 lore raw

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

Quoted 3 lines

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.

#3 lore raw

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

Quoted 6 lines · Alan Cox
Quoted 3 lines

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.

#4 lore raw

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

In reply to Nick Piggin
Quoted 2 lines · Nick Piggin

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

#5 lore raw

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

Quoted 9 lines · Ingo Molnar
Quoted 2 lines · Nick Piggin

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

#6 lore raw

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

Quoted 7 lines · Nick Piggin
Quoted 6 lines · Ingo Molnar
Quoted 2 lines · Nick Piggin

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

Quoted 6 lines
Quoted 3 lines

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

#7 lore raw

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

Quoted 31 lines · Ingo Molnar
Quoted 7 lines · Nick Piggin
Quoted 6 lines · Ingo Molnar
Quoted 2 lines · Nick Piggin

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

Quoted 6 lines
Quoted 3 lines

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);
Quoted 3 lines

}

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.

#8 lore raw

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

In reply to Nick Piggin

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.

include/asm-x86_64/spinlock.h line 92

Quoted 5 lines

static inline void __raw_spin_unlock(raw_spinlock_t *lock) {

include/asm-x86_64/spinlock.h +1 -1
-	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

#9 lore raw

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

Quoted 5 lines · 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.

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 :)

Quoted 11 lines

In general they look ok.

include/asm-x86_64/spinlock.h line 92

Quoted 5 lines

static inline void __raw_spin_unlock(raw_spinlock_t *lock) {

include/asm-x86_64/spinlock.h +1 -1
-	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.