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