Skip to contentSkip to conversation

qspinlock: Introducing a 4-byte queue spinlock implementation

RFC PATCH Waiman Long 5 participants 17 messages Aug 21, 2013 – Aug 30, 2013 2 messages not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw
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 of spin_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->locked to 0 and issuing smp_wmb()? Writes from the critical section from our thread might be delayed behind the write to lock->locked if 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 ending smp_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 of lock_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

#2 lore raw

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->locked to 0 and issuing smp_wmb()? Writes from the critical section from our thread might be delayed behind the write to lock->locked if 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 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.

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 the ARCH_QSPINLOCK setting. The smp_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 of lock_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.

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.

#3 lore raw
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->locked to 0 and issuing smp_wmb()? Writes from the critical section from our thread might be delayed behind the write to lock->locked if 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 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.

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.

Quoted 3 lines

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

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 the ARCH_QSPINLOCK setting. The smp_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

More on this in Documentation/memory-barriers.txt

Quoted 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 of lock_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 the ACCESS_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.

#4 lore raw

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

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() or smp_mb() at the beginning of the unlock function and a barrier() 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.

#5 lore raw
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 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.

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.

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() or smp_mb() at the beginning of the unlock function and a barrier() 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() 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.

I did read Documentation/memory-barriers.txt. I will read volatile-considered-harmful.txt.

Regards,
Longman

#6 lore raw
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_PREFIX will 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]

#8 lore raw
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.

#9 lore raw
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

#10 lore raw
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.

#11 lore raw
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

#12 lore raw
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?

#13 lore raw
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

#14 lore raw
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 ;-)

#15 lore raw
In reply to Alexander Fyodorov
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_PREFIX will 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?

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

#16 lore raw

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() or barrier() 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

#17 lore raw
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() or barrier() 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.

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

#18 lore raw

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.