Convert ia64 spinlocks to use "tickets"
RFC 1/1 Convert ia64 spinlocks to use "tickets"
Early last year x86 changed their spinlock implementation to use a fair "ticket" system (just like the one at deli counter in the grocery store). Here is the same conversion for ia64.
Notes:
1) This increases the size of a spinlock from 4 bytes to 8. This is not because I think that we'll have more that 65535 cpus waiting for the same lock (if that ever happens we really need to look at how the callers are using spinlocks!) but because ia64 doesn't have a version of the fetchadd instruction that works on anything smaller than 32-bit values.
2) I just did a naive implementation of the routines in C. The assembler generated by gcc doesn't look too hideous ... but if we switch to tickets we should definitely look to see if we can improve things.
3) This boots on a 4-socket Montecito (8 cores, 16 threads) and has been building kernels using "make -j12" for a little while. But this counts as rather light testing.
4) I haven't done a performance comparison against the old lock implementation yet.
---
arch/ia64/Kconfig | 4 arch/ia64/include/asm/spinlock.h | 170 ++++++++++++++++----------------- arch/ia64/include/asm/spinlock_types.h | 2 arch/ia64/kernel/head.S | 89 ----------------- arch/ia64/kernel/ia64_ksyms.c | 20 --- arch/ia64/oprofile/backtrace.c | 20 --- 6 files changed, 87 insertions(+), 218 deletions(-)
arch/ia64/Kconfig +1 -3
@@ -60,9 +60,7 @@ config IOMMU_HELPER bool config GENERIC_LOCKBREAK - bool - default y - depends on SMP && PREEMPT + def_bool n config RWSEM_XCHGADD_ALGORITHM bool
arch/ia64/include/asm/spinlock.h +84 -86
187 lines not on this page · raw message
arch/ia64/include/asm/spinlock_types.h +1 -1
@@ -6,7 +6,7 @@#endif typedef struct { -volatile unsigned int lock; +volatile unsigned long lock; }raw_spinlock_t ;#define __RAW_SPIN_LOCK_UNLOCKED { 0 }
arch/ia64/kernel/head.S +0 -89
95 lines not on this page · raw message
arch/ia64/kernel/ia64_ksyms.c +0 -20
@@ -84,26 +84,6 @@ EXPORT_SYMBOL(ia64_save_scratch_fpregs);#include <asm/unwind.h> EXPORT_SYMBOL (unw_init_running); -#ifdef ASM_SUPPORTED -# ifdef CONFIG_SMP -# if (__GNUC__ = 3 && __GNUC_MINOR__ < 3) -/* -* This is not a normal routine and we don't want a function descriptor for it, so we use -* a fake declaration here. -*/ -extern char ia64_spinlock_contention_pre3_4; -EXPORT_SYMBOL (ia64_spinlock_contention_pre3_4); -# else -/* -* This is not a normal routine and we don't want a function descriptor for it, so we use -* a fake declaration here. -*/ -extern char ia64_spinlock_contention; -EXPORT_SYMBOL (ia64_spinlock_contention); -# endif -# endif -#endif -#if defined(CONFIG_IA64_ESI ) || defined(CONFIG_IA64_ESI_MODULE )extern void esi_call_phys (void );EXPORT_SYMBOL_GPL (esi_call_phys);
arch/ia64/oprofile/backtrace.c +1 -19
@@ -32,24 +32,6 @@ typedef structu64 *prev_pfs_loc;/* state for WAR for old spinlock ool code */ } ia64_backtrace_t; -#if (__GNUC__ = 3 && __GNUC_MINOR__ < 3) -/* -* Returns non-zero if the PC is in the spinlock contention out-of-line code -* with non-standard calling sequence (on older compilers). -*/ -static __inline__int in_old_ool_spinlock_code (unsigned long pc) -{ - extern const char ia64_spinlock_contention_pre3_4[] __attribute__ ((weak)); - extern const char ia64_spinlock_contention_pre3_4_end[] __attribute__ ((weak)); -unsigned long sc_start = (unsigned long )ia64_spinlock_contention_pre3_4; -unsigned long sc_end = (unsigned long )ia64_spinlock_contention_pre3_4_end; -return (sc_start && sc_end && pc >= sc_start && pc < sc_end); -} -#else -/* Newer spinlock code does a proper br.call and works fine with the unwinder */ -#define in_old_ool_spinlock_code (pc) 0 -#endif -/* Returns non-zero if the PC is in the Interrupt Vector Table */ static __inline__int in_ivt_code (unsigned long pc) {
@@ -80,7 +62,7 @@ static __inline__ int next_frame(ia64_backtrace_t *bt)*/ if (bt->prev_pfs_loc && bt->regs && bt->frame.pfs_loc = bt->prev_pfs_loc) bt->frame.pfs_loc = &bt->regs->ar_pfs; - bt->prev_pfs_loc = (in_old_ool_spinlock_code (bt->frame.ip) ? bt->frame.pfs_loc :NULL ); + bt->prev_pfs_loc =NULL ;return unw_unwind (&bt->frame) =0 ; }
Quoted 3 lines · Tony
Early last year x86 changed their spinlock implementation to use a fair "ticket" system (just like the one at deli counter in the grocery store). Here is the same conversion for ia64.
A naieve comment, but doesn't a desire to implement "fairness" suggest lock contention that aught to be addressed?
rick jones
Quoted 6 lines
Quoted 3 lines
Early last year x86 changed their spinlock implementation to use a fair "ticket" system (just like the one at deli counter in the grocery store). Here is the same conversion for ia64.
A naieve comment, but doesn't a desire to implement "fairness" suggest lock contention that aught to be addressed?
No, that's a good point. I was a bit surprised that the ticket patch went into x86 with so little fuss given the long standing attitude that the fix for lock contention problems was not to go tweaking the locking code to make it faster ... but to go and do possibly major surgery on the code that was using to locks to reduce the contention by changing the algorithm or the locking scope, or moving to lockless algorithms when possible.
But the patch went in because the ticket locks were only very slightly slower in the uncontended case, and they did solve a real problem for a common two socket platform where the lack of fairness allowed the cores on one socket to freeze out the cores on the other socket for extremely long periods.
I do have a data point for the performance of ticket locks on ia64. For kernel compiles (using "make -j12" on a 4-socket, 8-core, 16-thread system), the impact is in the noise. Mean time to build across 300 builds was 0.2% slower with ticket locks ... but the run to run variation on these builds was 1.6% (for +/- one standard deviation).
-Tony
On Thu, Sep 10, 2009 at 10:34:30PM -0700, Luck, Tony wrote:
...
Quoted 16 lines
arch/ia64/include/asm/spinlock.h +1
-14-static inline void -__raw_spin_lock_flags (raw_spinlock_t *lock,unsigned long flags) +static __always_inline void __ticket_spin_lock(raw_spinlock_t *lock) { - register volatile unsigned int *ptr asm ("r31") = &lock->lock; - -#if (__GNUC__ = 3 && __GNUC_MINOR__ < 3) -# ifdef CONFIG_ITANIUM -/* don't use brl on Itanium... */ - asmvolatile ("{\n\t" -" mov ar.ccv = r0\n\t" -" mov r28 = ip\n\t" -" mov r30 = 1;;\n\t" -"}\n\t" -"cmpxchg4.acq r30 = [%1], r30, ar.ccv\n\t" - "movl r29 = ia64_spinlock_contention_pre3_4;;\n\t"
...
arch/ia64/include/asm/spinlock.h line 83
Quoted 1 line
arch/ia64/include/asm/spinlock.h +0
-1-"(p14) brl.call.spnt.many b6=ia64_spinlock_contention;;"
Have you done any testing where the spin with interrupts disabled was problematic?
I know we have had ages of problems with these, but I don't recall any specific instances right now (keep in mind it is 3:00 AM when I am finally getting to look at this).
Thanks,
Robin
Quoted 4 lines · Tony
But the patch went in because the ticket locks were only very slightly slower in the uncontended case, and they did solve a real problem for a common two socket platform where the lack of fairness allowed the
It was a eight socket platform. I'm not aware of any unfair two socket platforms.
Quoted 2 lines
cores on one socket to freeze out the cores on the other socket for extremely long periods.
Very long as a minute in extreme corner cases. So the motivation was more to limit the worst case than to tune a common case.
BTW the main problem of ticket locks is that they tend to cooperate badly with hypervisors, they can run into bad convoying issues with the vcpu scheduler. So you probably should have a way to turn them off.
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only.
Quoted 2 lines
Have you done any testing where the spin with interrupts disabled was problematic?
So far my testing has been limited to mild stress running kernel builds. Any pointers to other stress tests that might shed light on these kinds of problems would be gratefully received. Presumably some sort of heavy i/o (networking) benchmark so there are lots of interrupts to process?
Quoted 3 lines
I know we have had ages of problems with these, but I don't recall any specific instances right now (keep in mind it is 3:00 AM when I am finally getting to look at this).
Thanks for looking at it.
-Tony
Quoted 2 lines
It was a eight socket platform. I'm not aware of any unfair two socket platforms.
I got the two socket information from Nick's git commit comment:
commit 314cdbefd1fd0a7acf3780e9628465b77ea6a836
Author: Nick Piggin <[email protected]> Date: Wed Jan 30 13:31:21 2008 +0100
x86: FIFO ticket spinlocks
...
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.
Quoted 4 lines
BTW the main problem of ticket locks is that they tend to cooperate badly with hypervisors, they can run into bad convoying issues with the vcpu scheduler. So you probably should have a way to turn them off.
In the paravirtualized case the spinlock contention case should be a hypercall.
Yes, I see that in the native case the vcpu scheduler has less to worry about ... any spinner that it picks can acquire the lock with traditional spin locks ... whereas with ticket locks if it picks the wrong one it will just spin uselessly waiting for a "now serving" value to show up that can't happen until all the vcpus that hold lower number tickets have been run (in order!).
-Tony