ARC: spinlocks/atomics rework
Subsystems (3)
v2 cover ARC: spinlocks/atomics rework
The PREFETCHW workaround for llock/scond livelock was not sufficient after all and we had to do some work there. Extending testing of quad core FPGA builds shows things pretty stable, whereas w/o patches some of the LTP tests (shm_open/23-1) would cause the system to go bonkers.
Changes since v1* (all thx to Peter Zijlstra)
* 3/6 - updated changelog
* 4/6 - updated changelog
arch_write_unlock() need not use LLOCK/SCOND
* 5/6 - Conditional implementation of SCOND_FAIL_RETRY* in atomics (reduced dup) Handle overflow of delay counter in SCOND_FAIL_RETRY_ASM
* 6/6 - updated changelog
[*] http://lkml.kernel.org/r/[email protected]
Vineet Gupta (6):
Revert "ARCv2: STAR 9000837815 workaround hardware exclusive
transactions livelock"
ARC: refactor atomic inline asm operands with symbolic names
ARC: LLOCK/SCOND based spin_lock
ARC: LLOCK/SCOND based rwlock
ARCv2: spinlock/rwlock/atomics: Delayed retry of failed SCOND with
exponential backoff
ARCv2: spinlock/rwlock: Reset retry delay when starting a new
spin-wait cycle
arch/arc/Kconfig | 5 + arch/arc/include/asm/atomic.h | 79 +++-- arch/arc/include/asm/spinlock.h | 539 +++++++++++++++++++++++++++++++++- arch/arc/include/asm/spinlock_types.h | 2 + arch/arc/kernel/setup.c | 4 + 5 files changed, 591 insertions(+), 38 deletions(-)
Signature · 1 line
1.9.1
PATCH v2 1/6 Revert "ARCv2: STAR 9000837815 workaround hardware exclusive transactions livelock"
Extended testing of quad core configuration revealed that this fix was insufficient. Specifically LTP open posix shm_op/23-1 would cause the hardware livelock in llock/scond loop in update_cpu_load_active()
So remove this and make way for a proper workaround
This reverts commit a5c8b52abe677977883655166796f167ef1e0084.
--- arch/arc/include/asm/atomic.h | 14 ++------------ 1 file changed, 2 insertions(+), 12 deletions(-)
arch/arc/include/asm/atomic.h +2 -12
@@ -23,21 +23,13 @@#define atomic_set (v, i) (((v)->counter) = (i)) -#ifdef CONFIG_ISA_ARCV2 -#define PREFETCHW " prefetchw [%1] \n" -#else -#define PREFETCHW -#endif -#define ATOMIC_OP (op, c_op, asm_op) \ static inline void atomic_##op(int i, atomic_t *v) \ { \ unsigned int temp; \ \ __asm__ __volatile__( \ - "1: \n" \ - PREFETCHW \ - " llock %0, [%1] \n" \ + "1: llock %0, [%1] \n" \ " " #asm_op " %0, %0, %2 \n" \ " scond %0, [%1] \n" \ " bnz 1b \n" \
@@ -58,9 +50,7 @@ static inline int atomic_##op##_return(int i, atomic_t *v) \smp_mb (); \ \ __asm__ __volatile__( \ - "1: \n" \ - PREFETCHW \ - " llock %0, [%1] \n" \ + "1: llock %0, [%1] \n" \ " " #asm_op " %0, %0, %2 \n" \ " scond %0, [%1] \n" \ " bnz 1b \n" \
Signature · 1 line
1.9.1
PATCH v2 2/6 ARC: refactor atomic inline asm operands with symbolic names
In reply to Vineet GuptaThis reduces the diff in forth-coming patches and also helps understand better the incremental changes to inline asm.
--- arch/arc/include/asm/atomic.h | 32 +++++++++++++++++--------------- 1 file changed, 17 insertions(+), 15 deletions(-)
arch/arc/include/asm/atomic.h +17 -15
@@ -26,22 +26,23 @@ #define ATOMIC_OP(op, c_op, asm_op) \ static inline void atomic_##op(int i, atomic_t *v) \ { \ - unsigned int temp; \ + unsigned int val; \ \ __asm__ __volatile__( \ - "1: llock %0, [%1] \n" \ - " " #asm_op " %0, %0, %2 \n" \ - " scond %0, [%1] \n" \ - " bnz 1b \n" \ - : "=&r"(temp) /* Early clobber, to prevent reg reuse */ \ - : "r"(&v->counter), "ir"(i) \ + "1: llock %[val], [%[ctr]] \n" \ + " " #asm_op " %[val], %[val], %[i] \n" \ + " scond %[val], [%[ctr]] \n" \ + " bnz 1b \n" \ + : [val] "=&r" (val) /* Early clobber to prevent reg reuse */ \ + : [ctr] "r" (&v->counter), /* Not "m": llock only supports reg direct addr mode */ \ + [i] "ir" (i) \ : "cc"); \ } \#define ATOMIC_OP_RETURN (op, c_op, asm_op) \ static inline int atomic_##op##_return(int i, atomic_t *v) \ { \ - unsigned int temp; \ + unsigned int val; \ \/* \ * Explicit full memory barrier needed before/after as \
@@ -50,17 +51,18 @@ static inline int atomic_##op##_return(int i, atomic_t *v) \smp_mb (); \ \ __asm__ __volatile__( \ - "1: llock %0, [%1] \n" \ - " " #asm_op " %0, %0, %2 \n" \ - " scond %0, [%1] \n" \ - " bnz 1b \n" \ - : "=&r"(temp) \ - : "r"(&v->counter), "ir"(i) \ + "1: llock %[val], [%[ctr]] \n" \ + " " #asm_op " %[val], %[val], %[i] \n" \ + " scond %[val], [%[ctr]] \n" \ + " bnz 1b \n" \ + : [val] "=&r" (val) \ + : [ctr] "r" (&v->counter), \ + [i] "ir" (i) \ : "cc"); \ \ smp_mb(); \ \ - return temp; \ + return val; \ }#else /* !CONFIG_ARC_HAS_LLSC */
Signature · 1 line
1.9.1
PATCH v2 3/6 ARC: LLOCK/SCOND based spin_lock
In reply to Vineet GuptaCurrent spin_lock uses EXchange instruction to implement the atomic test and set of lock location (reads orig value and ST 1). This however forces the cacheline into exclusive state (because of the ST) and concurrent loops in multiple cores will bounce the line around between cores.
Instead, use LLOCK/SCOND to implement the atomic test and set which is better as line is in shared state while lock is spinning on LLOCK
The real motivation of this change however is to make way for future changes in atomics to implement delayed retry (with backoff). Initial experiment with delayed retry in atomics combined with orig EX based spinlock was a total disaster (broke even LMBench) as struct sock has a cache line sharing an atomic_t and spinlock. The tight spinning on lock, caused the atomic retry to keep backing off such that it would never finish.
--- arch/arc/include/asm/spinlock.h | 76 +++++++++++++++++++++++++++++++++++++---- 1 file changed, 69 insertions(+), 7 deletions(-)
arch/arc/include/asm/spinlock.h +69 -7
@@ -18,9 +18,68 @@#define arch_spin_unlock_wait (x) \ do { while (arch_spin_is_locked(x)) cpu_relax(); } while (0) +#ifdef CONFIG_ARC_HAS_LLSC + +static inline void arch_spin_lock (arch_spinlock_t *lock) +{ +unsigned int val; + +smp_mb (); + + __asm__ __volatile__( +"1: llock %[val], [%[slock]] \n" +" breq %[val], %[LOCKED], 1b \n" /* spin while LOCKED */ +" scond %[LOCKED], [%[slock]] \n" /* acquire */ +" bnz 1b \n" +" \n" + : [val]"=&r" (val) + : [slock]"r" (&(lock->slock)), + [LOCKED ]"r" (__ARCH_SPIN_LOCK_LOCKED__) + :"memory" ,"cc" ); + +smp_mb (); +} + +/* 1 - lock taken successfully */ +static inline int arch_spin_trylock (arch_spinlock_t *lock) +{ +unsigned int val, got_it =0 ; + +smp_mb (); + + __asm__ __volatile__( +"1: llock %[val], [%[slock]] \n" +" breq %[val], %[LOCKED], 4f \n" /* already LOCKED, just bail */ +" scond %[LOCKED], [%[slock]] \n" /* acquire */ +" bnz 1b \n" +" mov %[got_it], 1 \n" +"4: \n" +" \n" + : [val]"=&r" (val), + [got_it]"+&r" (got_it) + : [slock]"r" (&(lock->slock)), + [LOCKED ]"r" (__ARCH_SPIN_LOCK_LOCKED__) + :"memory" ,"cc" ); + +smp_mb (); + +return got_it; +} + +static inline void arch_spin_unlock (arch_spinlock_t *lock) +{ +smp_mb (); + + lock->slock = __ARCH_SPIN_LOCK_UNLOCKED__; + +smp_mb (); +} + +#else /* !CONFIG_ARC_HAS_LLSC */ +static inline void arch_spin_lock (arch_spinlock_t *lock) { -unsigned int tmp = __ARCH_SPIN_LOCK_LOCKED__; +unsigned int val = __ARCH_SPIN_LOCK_LOCKED__;/* * This smp_mb() is technically superfluous, we only need the one
@@ -33,7 +92,7 @@ static inline void arch_spin_lock(arch_spinlock_t *lock) __asm__ __volatile__("1: ex %0, [%1] \n" " breq %0, %2, 1b \n" - :"+&r" (tmp) + :"+&r" (val) :"r" (&(lock->slock)),"ir" (__ARCH_SPIN_LOCK_LOCKED__) :"memory" );
@@ -48,26 +107,27 @@ static inline void arch_spin_lock(arch_spinlock_t *lock)smp_mb (); } +/* 1 - lock taken successfully */ static inline int arch_spin_trylock (arch_spinlock_t *lock) { -unsigned int tmp = __ARCH_SPIN_LOCK_LOCKED__; +unsigned int val = __ARCH_SPIN_LOCK_LOCKED__;smp_mb (); __asm__ __volatile__("1: ex %0, [%1] \n" - :"+r" (tmp) + :"+r" (val) :"r" (&(lock->slock)) :"memory" );smp_mb (); -return (tmp == __ARCH_SPIN_LOCK_UNLOCKED__); +return (val == __ARCH_SPIN_LOCK_UNLOCKED__); }static inline void arch_spin_unlock (arch_spinlock_t *lock) { -unsigned int tmp = __ARCH_SPIN_LOCK_UNLOCKED__; +unsigned int val = __ARCH_SPIN_LOCK_UNLOCKED__;/* * RELEASE barrier: given the instructions avail on ARCv2, full barrier
@@ -77,7 +137,7 @@ static inline void arch_spin_unlock(arch_spinlock_t *lock) __asm__ __volatile__(" ex %0, [%1] \n" - :"+r" (tmp) + :"+r" (val) :"r" (&(lock->slock)) :"memory" );
@@ -88,6 +148,8 @@ static inline void arch_spin_unlock(arch_spinlock_t *lock) smp_mb(); } +#endif +/* * Read-write spinlocks, allowing multiple readers but only one writer. *
Signature · 1 line
1.9.1
PATCH v2 4/6 ARC: LLOCK/SCOND based rwlock
In reply to Vineet GuptaWith LLOCK/SCOND, the rwlock counter can be atomically updated w/o need for a guarding spin lock.
This in turn elides the EXchange instruction based spinning which causes the cacheline transition to exclusive state and concurrent spinning across cores would cause the line to keep bouncing around. LLOCK/SCOND based implementation is superior as spinning on LLOCK keeps the cacheline in shared state.
--- arch/arc/include/asm/spinlock.h | 174 ++++++++++++++++++++++++++++++++-- arch/arc/include/asm/spinlock_types.h | 2 + 2 files changed, 166 insertions(+), 10 deletions(-)
arch/arc/include/asm/spinlock.h +164 -10
@@ -75,6 +75,164 @@ static inline void arch_spin_unlock(arch_spinlock_t *lock) smp_mb(); } +/* +* Read-write spinlocks, allowing multiple readers but only one writer. +* Unfair locking as Writers could be starved indefinitely by Reader(s) +*/ + +static inline void arch_read_lock (arch_rwlock_t *rw) +{ +unsigned int val; + +smp_mb (); + +/* +* zero means writer holds the lock exclusively, deny Reader. +* Otherwise grant lock to first/subseq reader +* +* if (rw->counter > 0) { +* rw->counter--; +* ret = 1; +* } +*/ + + __asm__ __volatile__( +"1: llock %[val], [%[rwlock]] \n" +" brls %[val], %[WR_LOCKED], 1b\n" /* <= 0: spin while write locked */ +" sub %[val], %[val], 1 \n" /* reader lock */ +" scond %[val], [%[rwlock]] \n" +" bnz 1b \n" +" \n" + : [val]"=&r" (val) + : [rwlock]"r" (&(rw->counter)), + [WR_LOCKED ]"ir" (0 ) + :"memory" ,"cc" ); + +smp_mb (); +} + +/* 1 - lock taken successfully */ +static inline int arch_read_trylock (arch_rwlock_t *rw) +{ +unsigned int val, got_it =0 ; + +smp_mb (); + + __asm__ __volatile__( +"1: llock %[val], [%[rwlock]] \n" +" brls %[val], %[WR_LOCKED], 4f\n" /* <= 0: already write locked, bail */ +" sub %[val], %[val], 1 \n" /* counter-- */ +" scond %[val], [%[rwlock]] \n" +" bnz 1b \n" /* retry if collided with someone */ +" mov %[got_it], 1 \n" +" \n" +"4: ; --- done --- \n" + + : [val]"=&r" (val), + [got_it]"+&r" (got_it) + : [rwlock]"r" (&(rw->counter)), + [WR_LOCKED ]"ir" (0 ) + :"memory" ,"cc" ); + +smp_mb (); + +return got_it; +} + +static inline void arch_write_lock (arch_rwlock_t *rw) +{ +unsigned int val; + +smp_mb (); + +/* +* If reader(s) hold lock (lock < __ARCH_RW_LOCK_UNLOCKED__), +* deny writer. Otherwise if unlocked grant to writer +* Hence the claim that Linux rwlocks are unfair to writers. +* (can be starved for an indefinite time by readers). +* +* if (rw->counter == __ARCH_RW_LOCK_UNLOCKED__) { +* rw->counter = 0; +* ret = 1; +* } +*/ + + __asm__ __volatile__( +"1: llock %[val], [%[rwlock]] \n" +" brne %[val], %[UNLOCKED], 1b \n" /* while !UNLOCKED spin */ +" mov %[val], %[WR_LOCKED] \n" +" scond %[val], [%[rwlock]] \n" +" bnz 1b \n" +" \n" + : [val]"=&r" (val) + : [rwlock]"r" (&(rw->counter)), + [UNLOCKED ]"ir" (__ARCH_RW_LOCK_UNLOCKED__), + [WR_LOCKED ]"ir" (0 ) + :"memory" ,"cc" ); + +smp_mb (); +} + +/* 1 - lock taken successfully */ +static inline int arch_write_trylock (arch_rwlock_t *rw) +{ +unsigned int val, got_it =0 ; + +smp_mb (); + + __asm__ __volatile__( +"1: llock %[val], [%[rwlock]] \n" +" brne %[val], %[UNLOCKED], 4f \n" /* !UNLOCKED, bail */ +" mov %[val], %[WR_LOCKED] \n" +" scond %[val], [%[rwlock]] \n" +" bnz 1b \n" /* retry if collided with someone */ +" mov %[got_it], 1 \n" +" \n" +"4: ; --- done --- \n" + + : [val]"=&r" (val), + [got_it]"+&r" (got_it) + : [rwlock]"r" (&(rw->counter)), + [UNLOCKED ]"ir" (__ARCH_RW_LOCK_UNLOCKED__), + [WR_LOCKED ]"ir" (0 ) + :"memory" ,"cc" ); + +smp_mb (); + +return got_it; +} + +static inline void arch_read_unlock (arch_rwlock_t *rw) +{ +unsigned int val; + +smp_mb (); + +/* +* rw->counter++; +*/ + __asm__ __volatile__( +"1: llock %[val], [%[rwlock]] \n" +" add %[val], %[val], 1 \n" +" scond %[val], [%[rwlock]] \n" +" bnz 1b \n" +" \n" + : [val]"=&r" (val) + : [rwlock]"r" (&(rw->counter)) + :"memory" ,"cc" ); + +smp_mb (); +} + +static inline void arch_write_unlock (arch_rwlock_t *rw) +{ +smp_mb (); + + rw->counter = __ARCH_RW_LOCK_UNLOCKED__; + +smp_mb (); +} +#else /* !CONFIG_ARC_HAS_LLSC */ static inline void arch_spin_lock (arch_spinlock_t *lock)
@@ -148,23 +306,14 @@ static inline void arch_spin_unlock(arch_spinlock_t *lock)smp_mb (); } -#endif -/* * Read-write spinlocks, allowing multiple readers but only one writer. +* Unfair locking as Writers could be starved indefinitely by Reader(s) * * The spinlock itself is contained in @counter and access to it is * serialized with @lock_mutex. -* -* Unfair locking as Writers could be starved indefinitely by Reader(s) */ -/* Would read_trylock() succeed? */ -#define arch_read_can_lock (x) ((x)->counter > 0) - -/* Would write_trylock() succeed? */ -#define arch_write_can_lock (x) ((x)->counter == __ARCH_RW_LOCK_UNLOCKED__) -/* 1 - lock taken successfully */ static inline int arch_read_trylock (arch_rwlock_t *rw) {
@@ -235,6 +384,11 @@ static inline void arch_write_unlock(arch_rwlock_t *rw) arch_spin_unlock(&(rw->lock_mutex)); } +#endif + +#define arch_read_can_lock (x) ((x)->counter > 0) +#define arch_write_can_lock (x) ((x)->counter == __ARCH_RW_LOCK_UNLOCKED__) +#define arch_read_lock_flags (lock, flags) arch_read_lock(lock)#define arch_write_lock_flags (lock, flags) arch_write_lock(lock)
arch/arc/include/asm/spinlock_types.h +2 -0
@@ -26,7 +26,9 @@ typedef struct {*/ typedef struct {volatile unsigned int counter; +#ifndef CONFIG_ARC_HAS_LLSC arch_spinlock_t lock_mutex; +#endif }arch_rwlock_t ;#define __ARCH_RW_LOCK_UNLOCKED__ 0x01000000
Signature · 1 line
1.9.1
PATCH v2 5/6 ARCv2: spinlock/rwlock/atomics: Delayed retry of failed SCOND with exponential backoff
In reply to Vineet GuptaThis is to workaround the llock/scond livelock
HS38x4 could get into a LLOCK/SCOND livelock in case of multiple overlapping coherency transactions in the SCU. The exclusive line state keeps rotating among contenting cores leading to a never ending cycle. So break the cycle by deferring the retry of failed exclusive access (SCOND). The actual delay needed is function of number of contending cores as well as the unrelated coherency traffic from other cores. To keep the code simple, start off with small delay of 1 which would suffice most cases and in case of contention double the delay. Eventually the delay is sufficient such that the coherency pipeline is drained, thus a subsequent exclusive access would succeed.
--- arch/arc/Kconfig | 5 + arch/arc/include/asm/atomic.h | 49 ++++++- arch/arc/include/asm/spinlock.h | 293 ++++++++++++++++++++++++++++++++++++++++ arch/arc/kernel/setup.c | 4 + 4 files changed, 347 insertions(+), 4 deletions(-)
arch/arc/Kconfig +5 -0
@@ -365,6 +365,11 @@ config ARC_HAS_LLSC default y depends on !ARC_CANT_LLSC +config ARC_STAR_9000923308 + bool "Workaround for llock/scond livelock" + default y + depends on ISA_ARCV2 && SMP && ARC_HAS_LLSC + config ARC_HAS_SWAPE bool "Insn: SWAPE (endian-swap)" default y
arch/arc/include/asm/atomic.h +45 -4
83 lines not on this page · raw message
arch/arc/include/asm/spinlock.h +293 -0
305 lines not on this page · raw message
arch/arc/kernel/setup.c +4 -0
@@ -336,6 +336,10 @@ static void arc_chk_core_config(void)pr_warn ("CONFIG_ARC_FPU_SAVE_RESTORE needed for working apps\n" ); else if (!cpu->extn.fpu_dp && fpu_enabled)panic ("FPU non-existent, disable CONFIG_ARC_FPU_SAVE_RESTORE\n" ); + +if (is_isa_arcv2 () &&IS_ENABLED (CONFIG_SMP ) && cpu->isa.atomic && + !IS_ENABLED (CONFIG_ARC_STAR_9000923308 )) +panic ("llock/scond livelock workaround missing\n" ); }/*
Signature · 1 line
1.9.1
PATCH v2 6/6 ARCv2: spinlock/rwlock: Reset retry delay when starting a new spin-wait cycle
In reply to Vineet GuptaThe previous commit for delayed retry of SCOND needs some fine tuning for spin locks.
The backoff from delayed retry in conjunction with spin looping of lock itself can potentially cause the delay counter to reach high values. So to provide fairness to any lock operation, after a lock "seems" available (i.e. just before first SCOND try0, reset the delay counter back to starting value of 1
Essentially reset delay to 1 for a new spin-wait-loop-acquire cycle.
--- arch/arc/include/asm/spinlock.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
arch/arc/include/asm/spinlock.h +3 -3
@@ -279,7 +279,7 @@ static inline void arch_spin_lock(arch_spinlock_t *lock) __asm__ __volatile__("0: mov %[delay], 1 \n" "1: llock %[val], [%[slock]] \n" -" breq %[val], %[LOCKED], 1b \n" /* spin while LOCKED */ +" breq %[val], %[LOCKED], 0b \n" /* spin while LOCKED */ " scond %[LOCKED], [%[slock]] \n" /* acquire */ " bz 4f \n" /* done */ " \n"
@@ -358,7 +358,7 @@ static inline void arch_read_lock(arch_rwlock_t *rw) __asm__ __volatile__("0: mov %[delay], 1 \n" "1: llock %[val], [%[rwlock]] \n" -" brls %[val], %[WR_LOCKED], 1b\n" /* <= 0: spin while write locked */ +" brls %[val], %[WR_LOCKED], 0b\n" /* <= 0: spin while write locked */ " sub %[val], %[val], 1 \n" /* reader lock */ " scond %[val], [%[rwlock]] \n" " bz 4f \n" /* done */
@@ -427,7 +427,7 @@ static inline void arch_write_lock(arch_rwlock_t *rw) __asm__ __volatile__("0: mov %[delay], 1 \n" "1: llock %[val], [%[rwlock]] \n" -" brne %[val], %[UNLOCKED], 1b \n" /* while !UNLOCKED spin */ +" brne %[val], %[UNLOCKED], 0b \n" /* while !UNLOCKED spin */ " mov %[val], %[WR_LOCKED] \n" " scond %[val], [%[rwlock]] \n" " bz 4f \n"
Signature · 1 line
1.9.1
Quoted 5 lines · Vineet Gupta
The PREFETCHW workaround for llock/scond livelock was not sufficient after all and we had to do some work there. Extending testing of quad core FPGA builds shows things pretty stable, whereas w/o patches some of the LTP tests (shm_open/23-1) would cause the system to go bonkers.
Nothing obviously broken with this,