qspinlock: Introducing a 4-byte queue spinlock implementation
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 24 lines · Alexander Fyodorov
Hi Waiman,
I'm not subscribed to the lkml so I'm writing to you instead. In your patch you put
smp_wmb()at the end ofspin_unlock():(quoted diff) +19
-0+static __always_inline void queue_spin_unlock(struct qspinlock *lock) +{ + /* + * This unlock function may get inlined into the caller. The + * compiler barrier is needed to make sure that the lock will + * not be released before changes to the critical section is done. + * The ending smp_wmb() allows queue head process to get the lock ASAP. + */ + barrier(); +#ifndef QSPINLOCK_MANYCPUS + { + u16 qcode = ACCESS_ONCE(lock->locked); + if (unlikely(qcode != QSPINLOCK_LOCKED)) + queue_spin_unlock_slowpath(lock, qcode); + } +#endif + ACCESS_ONCE(lock->locked) = 0; + smp_wmb(); +}
Quoted 1 line
Isn't a race possible if another thread acquires the spinlock in the window between setting
lock->lockedto 0 and issuingsmp_wmb()? Writes from the critical section from our thread might be delayed behind the write tolock->lockedif the corresponding cache bank is busy.
The purpose of smp_wmb() is to make sure that content in the cache will be flushed out to the memory in case the cache coherency protocol cannot guarantee a single view of memory content on all processor. In other word, smp_wmb() is used to make other processors see that the lock has been freed ASAP. If another processor see that before smp_wmb(), it will be even better as the latency is reduced. As the lock holder is the only one that can release the lock, there is no race condition here.
Quoted 1 line
And shouldn't it be a full memory barrier (
smp_mb()) instead? Because we want loads from critical section to finish too before giving spinlock to another thread (which might change memory contents).
That is a legitimate question. I don't think it is a problem on x86 as the x86 spinlock code doesn't do a full mb() in the lock and unlock paths. However, other architectures like ARM do requires a full mb() in the lock and unlock paths. A full mb() will be costly in x86. A possible solution is to make ARCH_QSPINLOCK a tri-state variable whose value can be off, on with mb, on without mb. The QSPINLOCK parameter will then become a hidden one.
Quoted 10 lines
Comment in
queue_spin_unlock()says: "The endingsmp_wmb()allows queue head process to get the lock ASAP". But memory barriers can be costly on some architectures so issuing one just to empty write buffers might result in performance loss on them. Such things should be left to hardware IMHO.So I think
unlock()should look like this:(quoted diff) +6
-0+static __always_inline void queue_spin_unlock(struct qspinlock *lock) +{ + /* + * Wait for the critical section to finish memory accesses. + */ + smp_mb();
Review
Quoted 10 lines
(quoted diff) +10
-0+ +#ifndef QSPINLOCK_MANYCPUS + { + u16 qcode = ACCESS_ONCE(lock->locked); + if (unlikely(qcode != QSPINLOCK_LOCKED)) + queue_spin_unlock_slowpath(lock, qcode); + } +#endif + ACCESS_ONCE(lock->locked) = 0; +}
The smp_mb() will be conditionalized depending on the ARCH_QSPINLOCK setting. The smp_wmb() may not be needed, but a compiler barrier should still be there.
Quoted 1 line
Also I don't understand why there are so many uses of
ACCESS_ONCE()macro. It does not guarantee memory ordering with regard to other CPUs, so probably most of the uses can be removed (with exception oflock_is_contended(), where it prohibits gcc from optimizing the loop away).
All the lock/unlock code can be inlined and we don't know what the compiler will do to optimize code. The ACCESS_ONCE() macro is used to make sure that the compiler won't optimize away the actual fetch or write of the memory. Even if the compiler won't optimize away the memory access, adding the ACCESS_ONCE() macro won't have any extra overhead. So a more liberal use of it won't hurt performance.
Regards,
Longman
21.08.2013, 07:01, "Waiman Long" <[email protected]>:
Quoted 9 lines · Alexander Fyodorov
Quoted 4 lines
Isn't a race possible if another thread acquires the spinlock in the window between setting
lock->lockedto 0 and issuingsmp_wmb()? Writes from the critical section from our thread might be delayed behind the write tolock->lockedif the corresponding cache bank is busy.The purpose of
smp_wmb()is to make sure that content in the cache will be flushed out to the memory in case the cache coherency protocol cannot guarantee a single view of memory content on all processor.
Linux kernel does not support architectures without cache coherency, and while using memory barriers just for flushing write buffers ASAP on cache-coherent processors might benefit performance on some architectures it will hurt performance on others. So it must not be done in architecture-independent code.
Quoted 5 lines
In other
word,smp_wmb()is used to make other processors see that the lock has been freed ASAP. If another processor see that beforesmp_wmb(), it will be even better as the latency is reduced. As the lock holder is the only one that can release the lock, there is no race condition here.
No, I was talking about the window between freeing lock and issuing smp_wmb(). What I meant is:
1) A = 0
2) CPU0 locks the spinlock protecting A.
3) CPU0 writes 1 to A, but the write gets stalled because the corresponding cache bank is busy.
4) CPU0 calls spin_unlock() and sets lock->locked to 0.
If CPU1 does a spin_lock() right now, it will succeed (since lock->locked == 0). But the write to A hasn't reached cache yet, so CPU1 will see A == 0.
More examples on this are in Documentation/memory-barriers.txt
Quoted 3 lines
That is a legitimate question. I don't think it is a problem on x86 as the x86 spinlock code doesn't do a full
mb()in the lock and unlock paths.
It does because "lock" prefix implies a full memory barrier.
Quoted 3 lines
The
smp_mb()will be conditionalized depending on theARCH_QSPINLOCKsetting. Thesmp_wmb()may not be needed, but a compiler barrier should still be there.
Do you mean because of inline? That shouldn't be a problem because smp_mb() prohibits compiler from doing any optimizations across the barrier (thanks to the "volatile" keyword).
More on this in Documentation/memory-barriers.txt
Quoted 11 lines
Quoted 4 lines
Also I don't understand why there are so many uses of
ACCESS_ONCE()macro. It does not guarantee memory ordering with regard to other CPUs, so probably most of the uses can be removed (with exception oflock_is_contended(), where it prohibits gcc from optimizing the loop away).All the lock/unlock code can be inlined and we don't know what the compiler will do to optimize code. The
ACCESS_ONCE()macro is used to make sure that the compiler won't optimize away the actual fetch or write of the memory. Even if the compiler won't optimize away the memory access, adding theACCESS_ONCE()macro won't have any extra overhead. So a more liberal use of it won't hurt performance.
If compiler optimized memory access away it would be a bug. And I'm not so sure about overhead... For example, on some VLIW architectures ACCESS_ONCE() might prohibit compiler from mixing other instructions to the unlock.
Quoted 22 lines · Alexander Fyodorov
21.08.2013, 07:01, "Waiman Long"<[email protected]>:
Quoted 8 lines · Alexander Fyodorov
Quoted 4 lines
Isn't a race possible if another thread acquires the spinlock in the window between setting
lock->lockedto 0 and issuingsmp_wmb()? Writes from the critical section from our thread might be delayed behind the write tolock->lockedif the corresponding cache bank is busy.The purpose of
smp_wmb()is to make sure that content in the cache will be flushed out to the memory in case the cache coherency protocol cannot guarantee a single view of memory content on all processor.Linux kernel does not support architectures without cache coherency, and while using memory barriers just for flushing write buffers ASAP on cache-coherent processors might benefit performance on some architectures it will hurt performance on others. So it must not be done in architecture-independent code.
Quoted 5 lines
In other
word,smp_wmb()is used to make other processors see that the lock has been freed ASAP. If another processor see that beforesmp_wmb(), it will be even better as the latency is reduced. As the lock holder is the only one that can release the lock, there is no race condition here.No, I was talking about the window between freeing lock and issuing
smp_wmb(). What I meant is:
1) A = 0
2) CPU0 locks the spinlock protecting A.
3) CPU0 writes 1 to A, but the write gets stalled because the corresponding cache bank is busy.
4) CPU0 callsspin_unlock()and setslock->lockedto 0.
Quoted 3 lines
If CPU1 does a
spin_lock()right now, it will succeed (sincelock->locked== 0). But the write to A hasn't reached cache yet, so CPU1 will see A == 0.More examples on this are in
Documentation/memory-barriers.txt
In this case, we should have smp_wmb() before freeing the lock. The question is whether we need to do a full mb() instead. The x86 ticket spinlock unlock code is just a regular add instruction except for some exotic processors. So it is a compiler barrier but not really a memory fence. However, we may need to do a full memory fence for some other processors.
Quoted 9 lines
Quoted 3 lines
That is a legitimate question. I don't think it is a problem on x86 as the x86 spinlock code doesn't do a full
mb()in the lock and unlock paths.It does because "lock" prefix implies a full memory barrier.
Quoted 3 lines
The
smp_mb()will be conditionalized depending on theARCH_QSPINLOCKsetting. Thesmp_wmb()may not be needed, but a compiler barrier should still be there.Do you mean because of inline? That shouldn't be a problem because
smp_mb()prohibits compiler from doing any optimizations across the barrier (thanks to the "volatile" keyword).
What I mean is that I don't want any delay in issuing the unlock instruction because of compiler rearrangement. So there should be at least a barrier() call at the end of the unlock function.
At this point, I am inclined to have either a smp_wmb() or smp_mb() at the beginning of the unlock function and a barrier() at the end.
Quoted 6 lines
Documentation/memory-barriers.txtQuoted 4 lines
Quoted 4 lines
Also I don't understand why there are so many uses of
ACCESS_ONCE()
macro. It does not guarantee memory ordering with regard to other CPUs, so probably most of the uses can be removed (with exception oflock_is_contended(), where it prohibits gcc from optimizing the loop away).
Quoted 7 lines
Quoted 6 lines
All the lock/unlock code can be inlined and we don't know what the compiler will do to optimize code. The
ACCESS_ONCE()macro is used to make sure that the compiler won't optimize away the actual fetch or write of the memory. Even if the compiler won't optimize away the memory access, adding theACCESS_ONCE()macro won't have any extra overhead. So a more liberal use of it won't hurt performance.If compiler optimized memory access away it would be a bug. And I'm not so sure about overhead... For example, on some VLIW architectures
ACCESS_ONCE()might prohibit compiler from mixing other instructions to the unlock.
As the lock/unlock functions can be inlined, it is possible that a memory variable can be accessed earlier in the calling function and the stale copy may be used in the inlined lock/unlock function instead of fetching a new copy. That is why I prefer a more liberal use of ACCESS_ONCE() for safety purpose.
22.08.2013, 05:04, "Waiman Long" <[email protected]>:
Quoted 7 lines · Alexander Fyodorov
In this case, we should have
smp_wmb()before freeing the lock. The question is whether we need to do a fullmb()instead. The x86 ticket spinlock unlock code is just a regular add instruction except for some exotic processors. So it is a compiler barrier but not really a memory fence. However, we may need to do a full memory fence for some other processors.
The thing is that x86 ticket spinlock code does have full memory barriers both in lock() and unlock() code: "add" instruction there has "lock" prefix which implies a full memory barrier. So it is better to use smp_mb() and let each architecture define it.
Quoted 8 lines
At this point, I am inclined to have either a
smp_wmb()orsmp_mb()at the beginning of the unlock function and abarrier()at the end.As the lock/unlock functions can be inlined, it is possible that a memory variable can be accessed earlier in the calling function and the stale copy may be used in the inlined lock/unlock function instead of fetching a new copy. That is why I prefer a more liberal use of
ACCESS_ONCE()for safety purpose.
That is impossible: both lock() and unlock() must have either full memory barrier or an atomic operation which returns value. Both of them prohibit optimizations and compiler cannot reuse any global variable. So this usage of ACCESS_ONCE() is unneeded.
You can read more on this in Documentation/volatile-considered-harmful.txt
And although I already suggested that, have you read Documentation/memory-barriers.txt? There is a lot of valuable information there.
Quoted 9 lines · Alexander Fyodorov
22.08.2013, 05:04, "Waiman Long"<[email protected]>:
Quoted 7 lines · Alexander Fyodorov
In this case, we should have
smp_wmb()before freeing the lock. The question is whether we need to do a fullmb()instead. The x86 ticket spinlock unlock code is just a regular add instruction except for some exotic processors. So it is a compiler barrier but not really a memory fence. However, we may need to do a full memory fence for some other processors.The thing is that x86 ticket spinlock code does have full memory barriers both in
lock()andunlock()code: "add" instruction there has "lock" prefix which implies a full memory barrier. So it is better to usesmp_mb()and let each architecture define it.
I also thought that the x86 spinlock unlock path was an atomic add. It just comes to my realization recently that this is not the case. The UNLOCK_LOCK_PREFIX will be mapped to "" except for some old 32-bit x86 processors.
Quoted 8 lines
Quoted 8 lines
At this point, I am inclined to have either a
smp_wmb()orsmp_mb()at the beginning of the unlock function and abarrier()at the end.As the lock/unlock functions can be inlined, it is possible that a memory variable can be accessed earlier in the calling function and the stale copy may be used in the inlined lock/unlock function instead of fetching a new copy. That is why I prefer a more liberal use of
ACCESS_ONCE()for safety purpose.
Quoted 5 lines
That is impossible: both
lock()andunlock()must have either full memory barrier or an atomic operation which returns value. Both of them prohibit optimizations and compiler cannot reuse any global variable. So this usage ofACCESS_ONCE()is unneeded.You can read more on this in
Documentation/volatile-considered-harmful.txtAnd although I already suggested that, have you read
Documentation/memory-barriers.txt? There is a lot of valuable information there.
I did read Documentation/memory-barriers.txt. I will read volatile-considered-harmful.txt.
Regards,
Longman
Quoted 4 lines
I also thought that the x86 spinlock unlock path was an atomic add. It just comes to my realization recently that this is not the case. The
UNLOCK_LOCK_PREFIXwill be mapped to "" except for some old 32-bit x86 processors.
Hmm, I didn't know that. Looking through Google found these rules for x86 memory ordering:
* Loads are not reordered with other loads.
* Stores are not reordered with other stores.
* Stores are not reordered with older loads.
So x86 memory model is rather strict and memory barrier is really not needed in the unlock path - xadd is a store and thus behaves like a memory barrier, and since only lock's owner modifies "ticket.head" the "add" instruction need not be atomic.
But this is true only for x86, other architectures have more relaxed memory ordering. Maybe we should allow arch code to redefine queue_spin_unlock()? And define a version without smp_mb() for x86?
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 2 lines · Steven Rostedt
I just had this conversation with Paul McKenney. Should there be a
smp_mb_after_spin_unlock()?
Depends on the benefits I suppose :-) Oleg and Linus did recently add smp_mb__before_spinlock();
Quoted 2 lines
Although we blew it off as adding too many extensions to
smp_mb(). But it may be better than reimplementing something as complex as a lock.
Locks should be as light weight as possible and never implement anything heavier than the ACQUISITION / RELEASE barriers if at all possible. We should certainly not re-implement spinlocks just to get full barriers out of them, that's crazy.
Quoted 8 lines · Peter Zijlstra
Quoted 2 lines · Steven Rostedt
I just had this conversation with Paul McKenney. Should there be a
smp_mb_after_spin_unlock()?Depends on the benefits I suppose :-) Oleg and Linus did recently add
smp_mb__before_spinlock();
Quoted 7 lines
Quoted 2 lines
Although we blew it off as adding too many extensions to
smp_mb(). But it may be better than reimplementing something as complex as a lock.Locks should be as light weight as possible and never implement anything heavier than the ACQUISITION / RELEASE barriers if at all possible. We should certainly not re-implement spinlocks just to get full barriers out of them, that's crazy.
An unlock followed by a lock needs to act like a full barrier, but there is no requirement that a lock or unlock taken separately act like a full barrier.
Thanx, Paul
Quoted 12 lines · Paul E. McKenney
Quoted 11 lines · Peter Zijlstra
Quoted 2 lines · Steven Rostedt
I just had this conversation with Paul McKenney. Should there be a
smp_mb_after_spin_unlock()?Depends on the benefits I suppose :-) Oleg and Linus did recently add
smp_mb__before_spinlock();Quoted 2 lines
Although we blew it off as adding too many extensions to
smp_mb(). But it may be better than reimplementing something as complex as a lock.
Quoted 8 lines
Quoted 4 lines
Locks should be as light weight as possible and never implement anything heavier than the ACQUISITION / RELEASE barriers if at all possible. We should certainly not re-implement spinlocks just to get full barriers out of them, that's crazy.
An unlock followed by a lock needs to act like a full barrier, but there is no requirement that a lock or unlock taken separately act like a full barrier.
But that is already a property of the acquisition/release barrier.
Quoted 5 lines · On Wed, 28 Aug 2013 10:19:37 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 3 lines
An unlock followed by a lock needs to act like a full barrier, but there is no requirement that a lock or unlock taken separately act like a full barrier.
But that is already a property of the acquisition/release barrier.
As I mentioned in my fixes for the -rt swait barrier patches I sent. Spin locks only prevent leaks out of the critical section. It does not guarantee leaks into the critical section, thus:
A = 1 spin_lock() spin_unlock() B = C
Can turn into:
(A = 1) spin_lock() load C store 1 into A spin_unlock() B = C
This shows that a spin_lock()/unlock() combo is not equivalent to a mb(). But as Paul has mentioned, if we had:
A = 1 spin_unlock() spin_lock() B = C
That would be equivalent to
A = 1 mb() B = C
as the unlock prevents leaks going past it, and lock prevents leaks going before it.
-- Steve
Quoted 11 lines · Steven Rostedt
Quoted 5 lines · On Wed, 28 Aug 2013 10:19:37 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 3 lines
An unlock followed by a lock needs to act like a full barrier, but there is no requirement that a lock or unlock taken separately act like a full barrier.
But that is already a property of the acquisition/release barrier.
As I mentioned in my fixes for the -rt swait barrier patches I sent.
Not to me you didn't ;-)
Quoted 2 lines
Spin locks only prevent leaks out of the critical section. It does not guarantee leaks into the critical section, thus:
What's your point? You're just re-iterating the semantics in case anybody forgot about them?
Quoted 10 lines · On Wed, 28 Aug 2013 15:05:29 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 6 lines · Steven Rostedt
On Wed, 28 Aug 2013 10:19:37 +0200
Peter Zijlstra <[email protected]> wrote:Spin locks only prevent leaks out of the critical section. It does not guarantee leaks into the critical section, thus:
What's your point? You're just re-iterating the semantics in case anybody forgot about them?
I think we are all misunderstanding each other. It sounded like you didn't want to reimplement a lock to remove memory barriers.
Are you for the smp_mb__after_spin_unlock() ?
I'm getting confused by who is arguing what :-)
-- Steve
Quoted 1 line · Steven Rostedt
Are you for the
smp_mb__after_spin_unlock()?
Sure, if the performance gains of having it out-weight the added complexity of having it :-)
Nice non answer methinks, no? Muwhaha. To me having one more or less 'conditional' full mb primitive really doesn't matter anymore.
I'm presuming you're doing this for performance gains on anything other than x86 though, as x86 has a non-atomic unlock and thus always requires the full barrier thing here (yes yes I know ia32 still exists but people should really really really kill that thing already).
Quoted 1 line
I'm getting confused by who is arguing what :-)
Hehe ;-)
Quoted 11 lines · Alexander Fyodorov
Quoted 4 lines
I also thought that the x86 spinlock unlock path was an atomic add. It just comes to my realization recently that this is not the case. The
UNLOCK_LOCK_PREFIXwill be mapped to "" except for some old 32-bit x86 processors.Hmm, I didn't know that. Looking through Google found these rules for x86 memory ordering:
* Loads are not reordered with other loads.
* Stores are not reordered with other stores.
* Stores are not reordered with older loads.
So x86 memory model is rather strict and memory barrier is really not needed in the unlock path - xadd is a store and thus behaves like a memory barrier, and since only lock's owner modifies "ticket.head" the "add" instruction need not be atomic.But this is true only for x86, other architectures have more relaxed memory ordering. Maybe we should allow arch code to redefine
queue_spin_unlock()? And define a version withoutsmp_mb()for x86?
What I have been thinking is to set a flag in an architecture specific header file to tell if the architecture need a memory barrier. The generic code will then either do a smp_mb() or barrier() depending on the presence or absence of the flag. I would prefer to do more in the generic code, if possible.
Regards,
Longman
29.08.2013, 19:25, "Waiman Long" <[email protected]>:
Quoted 5 lines
What I have been thinking is to set a flag in an architecture specific header file to tell if the architecture need a memory barrier. The generic code will then either do a
smp_mb()orbarrier()depending on the presence or absence of the flag. I would prefer to do more in the generic code, if possible.
If you use flag then you'll have to check it manually. It is better to add new smp_mb variant, I suggest calling it smp_mb_before_store(), and define it to barrier() on x86.
But the same constraints as to UNLOCK_LOCK_PREFIX should apply here, so it will be something like this:
arch/x86/include/asm/barrier.h:
+#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 full memory barrier
+ * (PPro errata 66, 92)
+ */
+# define smp_mb_before_store() smp_mb()
+#else
+# define smp_mb_before_store() barrier()
+#endif
Quoted 7 lines · Alexander Fyodorov
29.08.2013, 19:25, "Waiman Long"<[email protected]>:
Quoted 5 lines
What I have been thinking is to set a flag in an architecture specific header file to tell if the architecture need a memory barrier. The generic code will then either do a
smp_mb()orbarrier()depending on the presence or absence of the flag. I would prefer to do more in the generic code, if possible.If you use flag then you'll have to check it manually. It is better to add new
smp_mbvariant, I suggest calling itsmp_mb_before_store(), and define it tobarrier()on x86.
I am sorry that I was not clear in my previous mail. I mean a flag/macro for compile time checking rather than doing runtime checking.
Regards,
Longman
30.08.2013, 07:16, "Waiman Long" <[email protected]>:
Quoted 2 lines
I am sorry that I was not clear in my previous mail. I mean a flag/macro for compile time checking rather than doing runtime checking.
Still a new smp_mb_xxx is better IMO since it can be used in other places too if a need arises.