Skip to contentSkip to conversation

qrwlock: Use smp_store_release() in write_unlock()

PATCH Daniel J Blueman 7 participants 30 messages Jan 13, 2014 – Jan 21, 2014 1 message not in the archive Sparse checker

lore
Share & tools
lore
#0 lore raw
Quoted 20 lines · Waiman Long

This patch modifies the queue_write_unlock() function to use the new smp_store_release() function in another pending patch. It also removes the temporary implementation of smp_load_acquire() and smp_store_release() function in qrwlock.c.

This patch should only be merged if PeterZ's linux-arch patch patch was merged.

---
 include/asm-generic/qrwlock.h |    4 +---
 kernel/locking/qrwlock.c      |   34 ----------------------------------
 2 files changed, 1 insertions(+), 37 deletions(-)
include/asm-generic/qrwlock.h +0 -0
index 2b9a7b4..4d4bd04 100644

include/asm-generic/qrwlock.h static inline void queue_write_unlock(struct qrwlock *lock) · line 182

Quoted 7 lines
include/asm-generic/qrwlock.h +1 -3
@@ -179,9 +179,7 @@ static inline void queue_write_unlock(struct qrwlock *lock)
 	/*
 	 * Make sure that none of the critical section will be leaked out.
 	 */
-	smp_mb__before_clear_bit();
-	ACCESS_ONCE(lock->cnts.writer) = 0;
-	smp_mb__after_clear_bit();
+	smp_store_release(&lock->cnts.writer, 0)

This will fail compilation, so probably needs further testing with Peter's load_acquire/store_release barrier patches.

Thanks,
Daniel

Signature · 2 lines
Daniel J Blueman
Principal Software Engineer, Numascale
#1 lore raw
Quoted 23 lines · Daniel J Blueman
Quoted 8 lines · Waiman Long

This patch modifies the queue_write_unlock() function to use the new smp_store_release() function in another pending patch. It also removes the temporary implementation of smp_load_acquire() and smp_store_release() function in qrwlock.c.

This patch should only be merged if PeterZ's linux-arch patch patch was merged.

Review

Quoted 8 lines
---
 include/asm-generic/qrwlock.h |    4 +---
 kernel/locking/qrwlock.c      |   34 ----------------------------------
 2 files changed, 1 insertions(+), 37 deletions(-)
(quoted diff) +0 -0

b/include/asm-generic/qrwlock.h

include/asm-generic/qrwlock.h static inline void queue_write_unlock(struct

Quoted 4 lines

index 2b9a7b4..4d4bd04 100644

include/asm-generic/qrwlock.h +0 -0
@@ -179,9 +179,7 @@ static inline void queue_write_unlock(struct

qrwlock *lock)

Quoted 10 lines

include/asm-generic/qrwlock.h static inline void queue_write_unlock(struct · line 182

Quoted 7 lines
include/asm-generic/qrwlock.h +1 -3
 	/*
 	 * Make sure that none of the critical section will be leaked out.
 	 */
-	smp_mb__before_clear_bit();
-	ACCESS_ONCE(lock->cnts.writer) = 0;
-	smp_mb__after_clear_bit();
+	smp_store_release(&lock->cnts.writer, 0)

This will fail compilation, so probably needs further testing with Peter's load_acquire/store_release barrier patches.

Peter's patch just hit -tip, so this should be esay to do. In Waiman's defense, he does call attention to this in the commit log.

Thanx, Paul

#2 lore raw
In reply to Daniel J Blueman
Quoted 32 lines · Daniel J Blueman
Quoted 5 lines · Waiman Long

This patch modifies the queue_write_unlock() function to use the new smp_store_release() function in another pending patch. It also removes the temporary implementation of smp_load_acquire() and smp_store_release() function in qrwlock.c.

Quoted 8 lines

This patch should only be merged if PeterZ's linux-arch patch patch was merged.

---
 include/asm-generic/qrwlock.h |    4 +---
 kernel/locking/qrwlock.c      |   34 

----------------------------------

Review

Quoted 3 lines
 2 files changed, 1 insertions(+), 37 deletions(-)
(quoted diff) +0 -0

b/include/asm-generic/qrwlock.h

include/asm-generic/qrwlock.h static inline void queue_write_unlock(struct

Quoted 4 lines

index 2b9a7b4..4d4bd04 100644

include/asm-generic/qrwlock.h +0 -0
@@ -179,9 +179,7 @@ static inline void queue_write_unlock(struct 

qrwlock *lock)

include/asm-generic/qrwlock.h static inline void queue_write_unlock(struct · line 182

Quoted 7 lines
include/asm-generic/qrwlock.h +1 -3
     /*
      * Make sure that none of the critical section will be leaked out.
      */
-    smp_mb__before_clear_bit();
-    ACCESS_ONCE(lock->cnts.writer) = 0;
-    smp_mb__after_clear_bit();
+    smp_store_release(&lock->cnts.writer, 0)
Quoted 2 lines

This will fail compilation, so probably needs further testing with Peter's load_acquire/store_release barrier patches.

Peter,

I found out that the build failure was caused by the fact that the __native_word() macro (used internally by compiletime_assert_atomic()) allows only a size of 4 or 8 for x86-64. The data type that I used is a byte. Is there a reason why byte and short are not considered native?

-Longman

#3 lore raw
Quoted 37 lines · Waiman Long
Quoted 32 lines · Daniel J Blueman
Quoted 5 lines · Waiman Long

This patch modifies the queue_write_unlock() function to use the new smp_store_release() function in another pending patch. It also removes the temporary implementation of smp_load_acquire() and smp_store_release() function in qrwlock.c.

Quoted 8 lines

This patch should only be merged if PeterZ's linux-arch patch patch was merged.

---
 include/asm-generic/qrwlock.h |    4 +---
 kernel/locking/qrwlock.c      |   34

----------------------------------

Review

Quoted 3 lines
 2 files changed, 1 insertions(+), 37 deletions(-)
(quoted diff) +0 -0

b/include/asm-generic/qrwlock.h

include/asm-generic/qrwlock.h static inline void queue_write_unlock(struct

Quoted 4 lines

index 2b9a7b4..4d4bd04 100644

include/asm-generic/qrwlock.h +0 -0
@@ -179,9 +179,7 @@ static inline void queue_write_unlock(struct

qrwlock *lock)

include/asm-generic/qrwlock.h static inline void queue_write_unlock(struct · line 182

Quoted 7 lines
include/asm-generic/qrwlock.h +1 -3
     /*
      * Make sure that none of the critical section will be leaked out.
      */
-    smp_mb__before_clear_bit();
-    ACCESS_ONCE(lock->cnts.writer) = 0;
-    smp_mb__after_clear_bit();
+    smp_store_release(&lock->cnts.writer, 0)
Quoted 3 lines

This will fail compilation, so probably needs further testing with Peter's load_acquire/store_release barrier patches.

Quoted 6 lines

Peter,

I found out that the build failure was caused by the fact that the __native_word() macro (used internally by compiletime_assert_atomic()) allows only a size of 4 or 8 for x86-64. The data type that I used is a byte. Is there a reason why byte and short are not considered native?

It seems likely it was implemented like that since there was no existing need; long can be relied on as the largest native type, so this should suffice and works here:

include/linux/compiler.h +4 -4
index fe7a686..dac91d7 100644
@@ -299,8 +299,8 @@ void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect);
 #endif
 
 /* Is this type a native word size -- useful for atomic operations */
-#ifndef __native_word
-# define __native_word(t) (sizeof(t) == sizeof(int) || sizeof(t) == sizeof(long))
+#ifndef __native_type
+# define __native_type(t) (sizeof(t) <= sizeof(long))
 #endif
 
 /* Compile time object size, -1 for unknown */
@@ -343,8 +343,8 @@ void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect);
 	_compiletime_assert(condition, msg, __compiletime_assert_, __LINE__)
 
 #define compiletime_assert_atomic_type(t)				\
-	compiletime_assert(__native_word(t),				\
-		"Need native word sized stores/loads for atomicity.")
+	compiletime_assert(__native_type(t),				\
+		"Need native sized stores/loads for atomicity.")
 
 /*
  * Prevent the compiler from merging or refetching accesses.  The compiler
Signature · 2 lines
Daniel J Blueman
Principal Software Engineer, Numascale
#4 lore raw
Quoted 10 lines · Daniel J Blueman
Quoted 6 lines

Peter,

I found out that the build failure was caused by the fact that the __native_word() macro (used internally by compiletime_assert_atomic()) allows only a size of 4 or 8 for x86-64. The data type that I used is a byte. Is there a reason why byte and short are not considered native?

It seems likely it was implemented like that since there was no existing need; long can be relied on as the largest native type, so this should suffice and works here:

There's Alphas that cannot actually atomically adres a byte; I do not konw if Linux cares about them, but if it does, we cannot in fact rely on this in generic primitives like this.

#5 lore raw
Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Daniel J Blueman
Quoted 6 lines

Peter,

I found out that the build failure was caused by the fact that the __native_word() macro (used internally by compiletime_assert_atomic()) allows only a size of 4 or 8 for x86-64. The data type that I used is a byte. Is there a reason why byte and short are not considered native?

Quoted 6 lines
Quoted 3 lines

It seems likely it was implemented like that since there was no existing need; long can be relied on as the largest native type, so this should suffice and works here:

There's Alphas that cannot actually atomically adres a byte; I do not konw if Linux cares about them, but if it does, we cannot in fact rely on this in generic primitives like this.

Thank for the explanation.

Can we allow architectural override of __native_word() macro? Like

#ifdef __arch_native_word
#define __native_word(t) __arch_native_word(t)
#else
#define __native_word(t) (sizeof(t) == sizeof(int) || sizeof(t) == sizeof(long))
#endif

In this way, we can allow x86 to support byte-based atomic type while restricting the generic macro to int and long only. I will also modify the code to use cmpxchg() when byte is not an atomic type.

-Longman

#6 lore raw
In reply to Peter Zijlstra
Quoted 8 lines · Peter Zijlstra
Quoted 7 lines · Daniel J Blueman
Quoted 6 lines

Peter,

I found out that the build failure was caused by the fact that the __native_word() macro (used internally by compiletime_assert_atomic()) allows only a size of 4 or 8 for x86-64. The data type that I used is a byte. Is there a reason why byte and short are not considered native?

Quoted 7 lines
Quoted 3 lines

It seems likely it was implemented like that since there was no existing need; long can be relied on as the largest native type, so this should suffice and works here:

There's Alphas that cannot actually atomically adres a byte; I do not konw if Linux cares about them, but if it does, we cannot in fact rely on this in generic primitives like this.

That's right, and thanks for the heads-up. Alpha can only address 4 and 8 bytes atomically. (LDL_L, LDQ_L, STL_C, STQ_C).

The Byte-Word extension in EV56 doesn't add new atomics, so in fact no Alphas can address < 4 bytes atomically.

#7 lore raw
Quoted 17 lines · Matt Turner
Quoted 8 lines · Peter Zijlstra
Quoted 7 lines · Daniel J Blueman
Quoted 6 lines

Peter,

I found out that the build failure was caused by the fact that the __native_word() macro (used internally by compiletime_assert_atomic()) allows only a size of 4 or 8 for x86-64. The data type that I used is a byte. Is there a reason why byte and short are not considered native?

Quoted 7 lines
Quoted 3 lines

It seems likely it was implemented like that since there was no existing need; long can be relied on as the largest native type, so this should suffice and works here:

There's Alphas that cannot actually atomically adres a byte; I do not konw if Linux cares about them, but if it does, we cannot in fact rely on this in generic primitives like this.

Quoted 6 lines

That's right, and thanks for the heads-up. Alpha can only address 4 and 8 bytes atomically. (LDL_L, LDQ_L, STL_C, STQ_C).

The Byte-Word extension in EV56 doesn't add new atomics, so in fact no Alphas can address < 4 bytes atomically.

Emulated with aligned 4 byte atomics, and masking. The same is true for arm, ppc, mips which, depending on cpu, also lack < 4 byte atomics.

r~

#8 lore raw
Quoted 15 lines · Richard Henderson
Quoted 14 lines · Matt Turner
Quoted 13 lines · Peter Zijlstra
Quoted 9 lines · Daniel J Blueman
Quoted 6 lines

Peter,

I found out that the build failure was caused by the fact that the __native_word() macro (used internally by compiletime_assert_atomic()) allows only a size of 4 or 8 for x86-64. The data type that I used is a byte. Is there a reason why byte and short are not considered native?

It seems likely it was implemented like that since there was no existing need; long can be relied on as the largest native type, so this should suffice and works here:

There's Alphas that cannot actually atomically adres a byte; I do not konw if Linux cares about them, but if it does, we cannot in fact rely on this in generic primitives like this.

Quoted 9 lines
Quoted 6 lines

That's right, and thanks for the heads-up. Alpha can only address 4 and 8 bytes atomically. (LDL_L, LDQ_L, STL_C, STQ_C).

The Byte-Word extension in EV56 doesn't add new atomics, so in fact no Alphas can address< 4 bytes atomically.

Emulated with aligned 4 byte atomics, and masking. The same is true for arm, ppc, mips which, depending on cpu, also lack< 4 byte atomics.

I would like to know if the action of writing out a byte (e.g. *byte = 0) is atomic in those architectures or is emulated by a compiler-generated software read-modify-write.

-Longman

#9 lore raw
Quoted 3 lines · Waiman Long

I would like to know if the action of writing out a byte (e.g. *byte = 0) is atomic in those architectures or is emulated by a compiler-generated software read-modify-write.

So on Alpha pre ev56 something like:

  *(volatile u8 *)foo = 0;

_Should_ cause a compile error as the hardware has to do a rmw which is not compatible with the requirements for volatile -- that said I do not know if a compiler will actually generate this error.

I can well imagine other load-store archs suffering similar problems, although I'm not aware of any.

#10 lore raw
In reply to Richard Henderson
Quoted 18 lines · Richard Henderson
Quoted 17 lines · Matt Turner
Quoted 15 lines · Peter Zijlstra
Quoted 10 lines · Daniel J Blueman
Quoted 6 lines

Peter,

I found out that the build failure was caused by the fact that the __native_word() macro (used internally by compiletime_assert_atomic()) allows only a size of 4 or 8 for x86-64. The data type that I used is a byte. Is there a reason why byte and short are not considered native?

It seems likely it was implemented like that since there was no existing need; long can be relied on as the largest native type, so this should suffice and works here:

There's Alphas that cannot actually atomically adres a byte; I do not konw if Linux cares about them, but if it does, we cannot in fact rely on this in generic primitives like this.

Quoted 8 lines
Quoted 5 lines

That's right, and thanks for the heads-up. Alpha can only address 4 and 8 bytes atomically. (LDL_L, LDQ_L, STL_C, STQ_C).

The Byte-Word extension in EV56 doesn't add new atomics, so in fact no Alphas can address < 4 bytes atomically.

Emulated with aligned 4 byte atomics, and masking. The same is true for arm, ppc, mips which, depending on cpu, also lack < 4 byte atomics.

Which means that Alpha should be able to similarly emulate 1-byte and 2-byte atomics, correct?

Thanx, Paul

#11 lore raw
Quoted 3 lines · Paul E. McKenney

Which means that Alpha should be able to similarly emulate 1-byte and 2-byte atomics, correct?

Not reasonably, no.

The ldl/stc implementation on early alpha was so broken as to be unusable. It's not actually done in the cache, it WENT OUT ON THE BUS. We're talking 70's style "external lock signal" kind of things like the 8086 did for locked cycles before the advent of caches, the kind that nobody sane has done for a long long time.

So realistically, you absolutely do not want to use those things to emulate atomic byte/word accesses. The whole point of "load_acquire()" and "store_release()" is that it's supposed to be cheaper than a locked access, and can be done with just a barrier instruction or a special instruction flag.

If you just want to do a store release, on alpha you'd want to implement that as a full memory barrier followed by a store. It doesn't get the advantage of a real release consistency model, but at least it's not doing an external bus access. But you can only do that store as a 4-byte or 8-byte store.on the older alphas (byte and word stores work on newer ones).

Of course, it's entirely possible that nobody cares..

Linus

#12 lore raw
Quoted 20 lines · Linus Torvalds
Quoted 3 lines · Paul E. McKenney

Which means that Alpha should be able to similarly emulate 1-byte and 2-byte atomics, correct?

Not reasonably, no.

The ldl/stc implementation on early alpha was so broken as to be unusable. It's not actually done in the cache, it WENT OUT ON THE BUS. We're talking 70's style "external lock signal" kind of things like the 8086 did for locked cycles before the advent of caches, the kind that nobody sane has done for a long long time.

So realistically, you absolutely do not want to use those things to emulate atomic byte/word accesses. The whole point of "load_acquire()" and "store_release()" is that it's supposed to be cheaper than a locked access, and can be done with just a barrier instruction or a special instruction flag.

Quoted 8 lines

If you just want to do a store release, on alpha you'd want to implement that as a full memory barrier followed by a store. It doesn't get the advantage of a real release consistency model, but at least it's not doing an external bus access. But you can only do that store as a 4-byte or 8-byte store.on the older alphas (byte and word stores work on newer ones).

Of course, it's entirely possible that nobody cares..

That would be my hope. ;-)

If nobody cares about Alpha period, it is easy. However, the last time that I tried that approach, they sent me a URL of a wiki showing Alpha systems still running mainline. But a slow-but-working approach for Alpha does seem reasonable, even for those still running Linux on Alpha.

Thanx, Paul

#13 lore raw
Quoted 7 lines · Paul E. McKenney
Quoted 7 lines

If you just want to do a store release, on alpha you'd want to implement that as a full memory barrier followed by a store. It doesn't get the advantage of a real release consistency model, but at least it's not doing an external bus access. But you can only do that store as a 4-byte or 8-byte store.on the older alphas (byte and word stores work on newer ones).

Quoted 8 lines
Quoted 1 line

Of course, it's entirely possible that nobody cares..

That would be my hope. ;-)

If nobody cares about Alpha period, it is easy. However, the last time that I tried that approach, they sent me a URL of a wiki showing Alpha systems still running mainline. But a slow-but-working approach for Alpha does seem reasonable, even for those still running Linux on Alpha.

Well, if they're all EV56 or later we're still good as they can actually do what we need.

But I don't think a ll/sc implementation of the store_release can even work, because in that case all users of the other bytes also need a ll/sc around them but how are we to know about them?

So the only real way to allow store_release on 8/16 bit values is by removing all Alpha support _pre_ EV56 :/

#14 lore raw
Quoted 20 lines · Peter Zijlstra
Quoted 7 lines · Paul E. McKenney
Quoted 7 lines

If you just want to do a store release, on alpha you'd want to implement that as a full memory barrier followed by a store. It doesn't get the advantage of a real release consistency model, but at least it's not doing an external bus access. But you can only do that store as a 4-byte or 8-byte store.on the older alphas (byte and word stores work on newer ones).

Quoted 8 lines
Quoted 1 line

Of course, it's entirely possible that nobody cares..

That would be my hope. ;-)

If nobody cares about Alpha period, it is easy. However, the last time that I tried that approach, they sent me a URL of a wiki showing Alpha systems still running mainline. But a slow-but-working approach for Alpha does seem reasonable, even for those still running Linux on Alpha.

Well, if they're all EV56 or later we're still good as they can actually do what we need.

Quoted 6 lines

But I don't think a ll/sc implementation of the store_release can even work, because in that case all users of the other bytes also need a ll/sc around them but how are we to know about them?

So the only real way to allow store_release on 8/16 bit values is by removing all Alpha support _pre_ EV56 :/

Fair point... We could demand Alpha-specific alignment, but that would get really ugly really quickly.

But we did drop support for SMP i386 quite some time ago, so perhaps it is time to drop support for SMP Alpha pre-EV56.

Thanx, Paul

#15 lore raw
Quoted 2 lines · Paul E. McKenney

But we did drop support for SMP i386 quite some time ago, so perhaps it is time to drop support for SMP Alpha pre-EV56.

So while the primitive is called smp_store_release() the !SMP variant still does:

  *(volatile __type *) = ptr;

which should not compile on any Alpha pre EV56, SMP or no for __type == u8.

A message that is not in the archive (sent off-list or not yet received): CA+55aFydYLQeBq=4AQQp_4dAnq09ocLmde1LFaXiNAJ=wJzfFA@mail.gmail.com

#17 lore raw
Quoted 10 lines · Linus Torvalds
Quoted 8 lines · Peter Zijlstra

So while the primitive is called smp_store_release() the !SMP variant still does:

  *(volatile __type *) = ptr;

which should not compile on any Alpha pre EV56, SMP or no for __type == u8.

Quoted 6 lines

I'm not sure where you get that "should not compile" theory from.

I'm pretty sure it will compile just fine. It will just generate the same standard read-modify-write sequence (and not using the ldl/stc sequence either). Do you have any actual reason to believe it won't, apart from your theoretical wishes of how the world should work?

No, I earlier even said it probably would compile. My usage of 'should' comes from how we've 'defined' volatile/ACCESS_ONCE in Documentation/memory-barriers.txt. According to those constraints the rmw cycle is not proper code.

#18 lore raw
Quoted 18 lines · Peter Zijlstra
Quoted 10 lines · Linus Torvalds
Quoted 8 lines · Peter Zijlstra

So while the primitive is called smp_store_release() the !SMP variant still does:

  *(volatile __type *) = ptr;

which should not compile on any Alpha pre EV56, SMP or no for __type == u8.

Quoted 6 lines

I'm not sure where you get that "should not compile" theory from.

I'm pretty sure it will compile just fine. It will just generate the same standard read-modify-write sequence (and not using the ldl/stc sequence either). Do you have any actual reason to believe it won't, apart from your theoretical wishes of how the world should work?

Quoted 4 lines

No, I earlier even said it probably would compile. My usage of 'should' comes from how we've 'defined' volatile/ACCESS_ONCE in Documentation/memory-barriers.txt. According to those constraints the rmw cycle is not proper code.

OK, I will bite... Aside from fine-grained code timing, what code could you write to tell the difference between a real one-byte store and an RMW emulating that store?

Thanx, Paul

#19 lore raw
Quoted 3 lines · Paul E. McKenney

OK, I will bite... Aside from fine-grained code timing, what code could you write to tell the difference between a real one-byte store and an RMW emulating that store?

Why isn't fine-grained code timing an issue? I'm sure Alpha people will love it when their machine magically keels over every so often.

Suppose we have two bytes in a word that get concurrent updates:

union {
	struct {
		u8 a;
		u8 b;
	};
	int word;
} ponies = { .word = 0, };

then two threads concurrently do:

CPU0: CPU1:

ponies.a = 5 ponies.b = 10

At which point you'd expect: a == 5 && b == 10

However, with a rmw you could end up like:

load r, ponies.word
load r, ponies.word
and r, ~0xFF
or r, 5
store ponies.word, r

			and r, ~0xFF00
			or r, 10 << 8
			store ponies.word, r

which gives: a == 0 && b == 10

The same can be had on a single CPU if you make the second RMW an interrupt.

In fact, we recently had such a RMW issue on PPC64 although from a slightly different angle, but we managed to hit it quite consistently. See commit ba1f14fbe7096.

The thing is, if we allow the above RMW 'atomic' store, we have to be _very_ careful that there cannot be such overlapping stores, otherwise things will go BOOM!

However, if we already have to make sure there's no overlapping stores, we might as well write a wide store and not allow the narrow stores to begin with, to force people to think about the issue.

#20 lore raw
Quoted 49 lines · Peter Zijlstra
Quoted 3 lines · Paul E. McKenney

OK, I will bite... Aside from fine-grained code timing, what code could you write to tell the difference between a real one-byte store and an RMW emulating that store?

Why isn't fine-grained code timing an issue? I'm sure Alpha people will love it when their machine magically keels over every so often.

Suppose we have two bytes in a word that get concurrent updates:

union {
	struct {
		u8 a;
		u8 b;
	};
	int word;
} ponies = { .word = 0, };

then two threads concurrently do:

CPU0: CPU1:

ponies.a = 5 ponies.b = 10

At which point you'd expect: a == 5 && b == 10

However, with a rmw you could end up like:

load r, ponies.word
load r, ponies.word
and r, ~0xFF
or r, 5
store ponies.word, r

			and r, ~0xFF00
			or r, 10 << 8
			store ponies.word, r

which gives: a == 0 && b == 10

The same can be had on a single CPU if you make the second RMW an interrupt.

In fact, we recently had such a RMW issue on PPC64 although from a slightly different angle, but we managed to hit it quite consistently. See commit ba1f14fbe7096.

Quoted 7 lines

The thing is, if we allow the above RMW 'atomic' store, we have to be _very_ careful that there cannot be such overlapping stores, otherwise things will go BOOM!

However, if we already have to make sure there's no overlapping stores, we might as well write a wide store and not allow the narrow stores to begin with, to force people to think about the issue.

Ah, I was assuming atomic rmw, which for Alpha would be implemented using the LL and SC instructions. Yes, lots of overhead, but if the CPU designers chose not to provide a load/store byte...

Thanx, Paul

#21 lore raw
Quoted 54 lines · Paul E. McKenney
Quoted 53 lines · Peter Zijlstra
Quoted 3 lines · Paul E. McKenney

OK, I will bite... Aside from fine-grained code timing, what code could you write to tell the difference between a real one-byte store and an RMW emulating that store?

Why isn't fine-grained code timing an issue? I'm sure Alpha people will love it when their machine magically keels over every so often.

Suppose we have two bytes in a word that get concurrent updates:

union {
	struct {
		u8 a;
		u8 b;
	};
	int word;
} ponies = { .word = 0, };

then two threads concurrently do:

CPU0: CPU1:

ponies.a = 5 ponies.b = 10

At which point you'd expect: a == 5 && b == 10

However, with a rmw you could end up like:

load r, ponies.word
load r, ponies.word
and r, ~0xFF
or r, 5
store ponies.word, r

			and r, ~0xFF00
			or r, 10 << 8
			store ponies.word, r

which gives: a == 0 && b == 10

The same can be had on a single CPU if you make the second RMW an interrupt.

In fact, we recently had such a RMW issue on PPC64 although from a slightly different angle, but we managed to hit it quite consistently. See commit ba1f14fbe7096.

The thing is, if we allow the above RMW 'atomic' store, we have to be _very_ careful that there cannot be such overlapping stores, otherwise things will go BOOM!

Quoted 7 lines
Quoted 3 lines

However, if we already have to make sure there's no overlapping stores, we might as well write a wide store and not allow the narrow stores to begin with, to force people to think about the issue.

Ah, I was assuming atomic rmw, which for Alpha would be implemented using the LL and SC instructions. Yes, lots of overhead, but if the CPU designers chose not to provide a load/store byte...

I don't see how ll/sc will help any. Suppose we do the a store as smp_store_release() using ll/sc but the b store is unaware and doesn't do an ll/sc.

Then we're still up shit creek without no paddle.

Whatever you're going to do, you need to be intimately aware of what the other bits in your word are doing.

#22 lore raw
Quoted 63 lines · Peter Zijlstra
Quoted 54 lines · Paul E. McKenney
Quoted 53 lines · Peter Zijlstra
Quoted 3 lines · Paul E. McKenney

OK, I will bite... Aside from fine-grained code timing, what code could you write to tell the difference between a real one-byte store and an RMW emulating that store?

Why isn't fine-grained code timing an issue? I'm sure Alpha people will love it when their machine magically keels over every so often.

Suppose we have two bytes in a word that get concurrent updates:

union {
	struct {
		u8 a;
		u8 b;
	};
	int word;
} ponies = { .word = 0, };

then two threads concurrently do:

CPU0: CPU1:

ponies.a = 5 ponies.b = 10

At which point you'd expect: a == 5 && b == 10

However, with a rmw you could end up like:

load r, ponies.word
load r, ponies.word
and r, ~0xFF
or r, 5
store ponies.word, r

			and r, ~0xFF00
			or r, 10 << 8
			store ponies.word, r

which gives: a == 0 && b == 10

The same can be had on a single CPU if you make the second RMW an interrupt.

In fact, we recently had such a RMW issue on PPC64 although from a slightly different angle, but we managed to hit it quite consistently. See commit ba1f14fbe7096.

The thing is, if we allow the above RMW 'atomic' store, we have to be _very_ careful that there cannot be such overlapping stores, otherwise things will go BOOM!

Quoted 7 lines
Quoted 3 lines

However, if we already have to make sure there's no overlapping stores, we might as well write a wide store and not allow the narrow stores to begin with, to force people to think about the issue.

Ah, I was assuming atomic rmw, which for Alpha would be implemented using the LL and SC instructions. Yes, lots of overhead, but if the CPU designers chose not to provide a load/store byte...

Quoted 8 lines

I don't see how ll/sc will help any. Suppose we do the a store as smp_store_release() using ll/sc but the b store is unaware and doesn't do an ll/sc.

Then we're still up shit creek without no paddle.

Whatever you're going to do, you need to be intimately aware of what the other bits in your word are doing.

Yes, this requires that -all- updates to the fields in the machine word in question use atomic rmw. Which would not be pretty from a core-code perspective. Hence my suggestion of ceasing Linux-kernel support for DEC Alpha CPUs that don't support byte operations. Also need 16-bit operations as well, of course...

Thanx, Paul

#23 lore raw
Quoted 6 lines · Paul E. McKenney

Yes, this requires that -all- updates to the fields in the machine word in question use atomic rmw. Which would not be pretty from a core-code perspective. Hence my suggestion of ceasing Linux-kernel support for DEC Alpha CPUs that don't support byte operations. Also need 16-bit operations as well, of course...

I'm not seeing this.

Why the hell would you have byte- or halfword-sized versions of the store_release or load_acquire things on alpha anyway?

What it means is that data structures that do locking or atomics need to be "int" or "long" on alpha. That has always been true. What do you claim has changed?

Linus

#24 lore raw
Quoted 9 lines · Linus Torvalds
Quoted 6 lines · Paul E. McKenney

Yes, this requires that -all- updates to the fields in the machine word in question use atomic rmw. Which would not be pretty from a core-code perspective. Hence my suggestion of ceasing Linux-kernel support for DEC Alpha CPUs that don't support byte operations. Also need 16-bit operations as well, of course...

Quoted 8 lines

I'm not seeing this.

Why the hell would you have byte- or halfword-sized versions of the store_release or load_acquire things on alpha anyway?

What it means is that data structures that do locking or atomics need to be "int" or "long" on alpha. That has always been true. What do you claim has changed?

OK, another approach would be to never add "select ARCH_USE_QUEUE_RWLOCK" on Alpha, at least if the queued rwlocks really do want to atomically manipulate bytes. After all, the Alpha systems that I know about don't have enough CPUs to make queued rwlocks necessary anyway.

Much simpler solution!

Is this what you were getting at, or am I missing your point?

Thanx, Paul

#25 lore raw
Quoted 9 lines · Paul E. McKenney

OK, another approach would be to never add "select ARCH_USE_QUEUE_RWLOCK" on Alpha, at least if the queued rwlocks really do want to atomically manipulate bytes. After all, the Alpha systems that I know about don't have enough CPUs to make queued rwlocks necessary anyway.

Much simpler solution!

Is this what you were getting at, or am I missing your point?

You're missing something.

Just make the "writer" field be an "int" on little-endian archiectures (like alpha).

There is no reason for that field to be a "char" to begin with, as far as I can tell, since the padding of the structure means that it doesn't save any space. But even if that wasn't true, we could make an arch-specific type for "minimum type for locking".

So my *point* was that it should be easy enough to just make sure that any data structures used for locking have types that are appropriate for that locking.

Linus

#26 lore raw
Quoted 14 lines · Linus Torvalds
Quoted 9 lines · Paul E. McKenney

OK, another approach would be to never add "select ARCH_USE_QUEUE_RWLOCK" on Alpha, at least if the queued rwlocks really do want to atomically manipulate bytes. After all, the Alpha systems that I know about don't have enough CPUs to make queued rwlocks necessary anyway.

Much simpler solution!

Is this what you were getting at, or am I missing your point?

You're missing something.

Quoted 7 lines

Just make the "writer" field be an "int" on little-endian archiectures (like alpha).

There is no reason for that field to be a "char" to begin with, as far as I can tell, since the padding of the structure means that it doesn't save any space. But even if that wasn't true, we could make an arch-specific type for "minimum type for locking".

On 64-bit systems (which includes Alpha), agreed, the field can be a 32-bit portion of a 64-bit structure that is then manipulated atomically. Many 32-bit systems need the reader and writer counts to fix in 32 bits in order to allow things like queue_read_trylock() to correctly account for both readers and writers.

If there was a 32-bit system running Linux that did not support byte accesses, there would be a problem, but I don't know of any such system.

Quoted 3 lines

So my *point* was that it should be easy enough to just make sure that any data structures used for locking have types that are appropriate for that locking.

So something like the following for the qrwlock definition, with appropriate C-preprocessor wrappers for the atomic-add accesses?

Thanx, Paul

------------------------------------------------------------------------

typedef struct qrwlock {
	union qrwcnts {
#ifdef CONFIG_64B
		struct (
			int writer;
			int reader;
		};
		atomic_long_t rwa;
		u64	 rwc;
#else
		struct {
#ifdef __LITTLE_ENDIAN
			u8  writer;	/* Writer state		*/
#else
			u16 r16;	/* Reader count - msb	*/
			u8  r8;		/* Reader count - lsb	*/
			u8  writer;	/* Writer state		*/
#endif
		};
		atomic_t    rwa;	/* Reader/writer atomic	*/
		u32	    rwc;	/* Reader/writer counts */
	} cnts;

#endif
struct mcs_spinlock *waitq; /* Tail of waiting queue */
} arch_rwlock_t;

#27 lore raw
In reply to Paul E. McKenney
Quoted 21 lines · Paul E. McKenney
Quoted 7 lines · Linus Torvalds
Quoted 5 lines · Paul E. McKenney

Yes, this requires that -all- updates to the fields in the machine word in question use atomic rmw. Which would not be pretty from a core-code perspective. Hence my suggestion of ceasing Linux-kernel support for DEC Alpha CPUs that don't support byte operations. Also need 16-bit operations as well, of course...

Quoted 8 lines

I'm not seeing this.

Why the hell would you have byte- or halfword-sized versions of the store_release or load_acquire things on alpha anyway?

What it means is that data structures that do locking or atomics need to be "int" or "long" on alpha. That has always been true. What do you claim has changed?

OK, another approach would be to never add "select ARCH_USE_QUEUE_RWLOCK" on Alpha, at least if the queued rwlocks really do want to atomically manipulate bytes. After all, the Alpha systems that I know about don't have enough CPUs to make queued rwlocks necessary anyway.

Quoted 6 lines

Much simpler solution!

Is this what you were getting at, or am I missing your point?

Thanx, Paul

My latest v9 series of qrwlock patch will automatically adapt to the lack of atomic byte access by using an atomic integer instruction instead. So the new series should work for pre-EV56 Alpha, it is just a bit less efficient in this case.

-Longman

#28 lore raw
Quoted 4 lines · Waiman Long

My latest v9 series of qrwlock patch will automatically adapt to the lack of atomic byte access by using an atomic integer instruction instead. So the new series should work for pre-EV56 Alpha, it is just a bit less efficient in this case.

See my other email; I don't think you can do that without also changing the implementation of the queue_read_{try}lock() functions.

Without those changes you can have transient values in your 'read-count' part of the word and a full word write will wreck things.

#29 lore raw
Quoted 10 lines · Peter Zijlstra
Quoted 4 lines · Waiman Long

My latest v9 series of qrwlock patch will automatically adapt to the lack of atomic byte access by using an atomic integer instruction instead. So the new series should work for pre-EV56 Alpha, it is just a bit less efficient in this case.

See my other email; I don't think you can do that without also changing the implementation of the queue_read_{try}lock() functions.

Without those changes you can have transient values in your 'read-count' part of the word and a full word write will wreck things.

I don't see any problem with my current logic. If a writer has the write lock, the writer byte has to have a value of 0xff. So atomically subtracting 0xff from it will guarantee that the writer byte will become zero, which is the same as assigning a zero value to that byte. The only difference is that an atomic subtract instruction will need to be used instead of a simple byte assignment.

Please let me know if there is any flaw in my logic.

-Longman

#30 lore raw
In reply to Paul E. McKenney
Quoted 22 lines · Paul E. McKenney
Quoted 21 lines · Richard Henderson
Quoted 20 lines · Matt Turner
Quoted 8 lines · Peter Zijlstra
Quoted 7 lines · Daniel J Blueman
Quoted 6 lines

Peter,

I found out that the build failure was caused by the fact that the __native_word() macro (used internally by compiletime_assert_atomic()) allows only a size of 4 or 8 for x86-64. The data type that I used is a byte. Is there a reason why byte and short are not considered native?

Quoted 7 lines
Quoted 3 lines

It seems likely it was implemented like that since there was no existing need; long can be relied on as the largest native type, so this should suffice and works here:

There's Alphas that cannot actually atomically adres a byte; I do not konw if Linux cares about them, but if it does, we cannot in fact rely on this in generic primitives like this.

That's right, and thanks for the heads-up. Alpha can only address 4 and 8 bytes atomically. (LDL_L, LDQ_L, STL_C, STQ_C).

Quoted 8 lines
Quoted 5 lines
Quoted 2 lines

The Byte-Word extension in EV56 doesn't add new atomics, so in fact no Alphas can address < 4 bytes atomically.

Emulated with aligned 4 byte atomics, and masking. The same is true for arm, ppc, mips which, depending on cpu, also lack < 4 byte atomics.

Which means that Alpha should be able to similarly emulate 1-byte and 2-byte atomics, correct?

If it's not possible to guarantee that GCC emits the 4-byte atomics by using a union, then we could emit the instructions via assembly. We'd introduce a macro to ensure lock word alignment, and this would be safe for unsigned counting up to the packed type limit. Maybe that's just too over-constrained though.

Thanks,
Daniel

Signature · 2 lines
Daniel J Blueman
Principal Software Engineer, Numascale