count_lim_atomic.c fails on POWER8
Hi Paul,
I just noticed occasional error of count_lim_atomic.c on POWER8 at current master. As I've recently touched the code under Codesamples/count/, I also tested on the tag "v2017.11.22a", and saw the same behavior.
The POWER8 virtual machine is Ubuntu 16.04.
Example output:
$ ./count_lim_atomic 6 uperf 1 !!! Count mismatch: 0 counted vs. 8 final value n_reads: 0 n_updates: 26038000 nreaders: 0 nupdaters: 6 duration: 240 ns/read: nan ns/update: 55.3038
$ ./count_lim_atomic 6 perf 1 !!! Count mismatch: 0 counted vs. 11 final value n_reads: 287000 n_updates: 1702000 nreaders: 6 nupdaters: 1 duration: 240 ns/read: 5017.42 ns/update: 141.011
As you see, the final count check of zero fails even when nupdaters == 1.
I have no idea what's wrong in count_lim_atomic.c.
Can you look into this? There might be something wrong in the header file under CodeSamples/arch-ppc64.h.
On x86_64, I've never seen the count mismatch.
Thanks, Akira
Quoted 15 lines · Akira Yokosawa
Hi Paul,
I just noticed occasional error of
count_lim_atomic.con POWER8 at current master. As I've recently touched the code under Codesamples/count/, I also tested on the tag "v2017.11.22a", and saw the same behavior.The POWER8 virtual machine is Ubuntu 16.04.
Example output:
$ ./count_lim_atomic 6 uperf 1 !!! Count mismatch: 0 counted vs. 8 final value n_reads: 0 n_updates: 26038000 nreaders: 0 nupdaters: 6 duration: 240 ns/read: nan ns/update: 55.3038
Quoted 6 lines
$ ./count_lim_atomic 6 perf 1 !!! Count mismatch: 0 counted vs. 11 final value n_reads: 287000 n_updates: 1702000 nreaders: 6 nupdaters: 1 duration: 240 ns/read: 5017.42 ns/update: 141.011As you see, the final count check of zero fails even when nupdaters == 1.
Yow!!! Thank you for checking this!
That said, it probably wasn't really single threaded, at least assuming that you had at least one reader.
Quoted 4 lines
I have no idea what's wrong in
count_lim_atomic.c.Can you look into this? There might be something wrong in the header file under
CodeSamples/arch-ppc64.h.
There isn't much in that file anymore because we now rely on the gcc intrinsics for the most part. Which might well be the problem, depending on compiler versions and so on.
Could you please send me the output of "objdump -d" on count_lim_atomic.o? And on the full count_lim_atomic binary, just in case gcc decides to be tricky in its code generation?
In the meantime, there might well be a generic bug in count_lim_atomic.c that just happens not to be exercised on x86, and I will look into that. I am on travel next week, so will be in odd timezones, but should have at least a little useful airplane time to look into this.
Quoted 1 line
On
x86_64, I've never seen the count mismatch.
Well, David Goldblatt's first C++11 signal-based litmus test wouldn't fail on PowerPC but did on x86, so I guess that they are now even. ;-)
Thanx, Paul
Hi Akira and Paul,
I checked the code today and the implementation of cmpxchg() looks very suspicious to me; Current cmpxchg() first executes function __atomic_compare_exchange_n, and then checks whether the value stored in field __actual (old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means __atomic_compare_exchange_n could fail even if the value of *ptr is equal to __actual (old). Unfortunately, current cmpxchg will treat this case as a success because the value of __actual(old) does not change.
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
--- CodeSamples/api-pthreads/api-gcc.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-)
(quoted diff) +0 -0
b/CodeSamples/api-pthreads/api-gcc.h
index 1dd26ca..38a16c0 100644
CodeSamples/api-pthreads/api-gcc.h +2 -5
@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1,
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \
+ (o) : (n); \
})
static __inline__ int atomic_cmpxchg(atomic_t *v, int old, int new)
Signature · 5 lines
2.7.4 Thanks, --Junchang
Quoted 54 lines · Paul E. McKenney
Quoted 15 lines · Akira Yokosawa
Hi Paul,
I just noticed occasional error of
count_lim_atomic.con POWER8 at current master. As I've recently touched the code under Codesamples/count/, I also tested on the tag "v2017.11.22a", and saw the same behavior.The POWER8 virtual machine is Ubuntu 16.04.
Example output:
$ ./count_lim_atomic 6 uperf 1 !!! Count mismatch: 0 counted vs. 8 final value n_reads: 0 n_updates: 26038000 nreaders: 0 nupdaters: 6 duration: 240 ns/read: nan ns/update: 55.3038Quoted 6 lines
$ ./count_lim_atomic 6 perf 1 !!! Count mismatch: 0 counted vs. 11 final value n_reads: 287000 n_updates: 1702000 nreaders: 6 nupdaters: 1 duration: 240 ns/read: 5017.42 ns/update: 141.011As you see, the final count check of zero fails even when nupdaters == 1.
Yow!!! Thank you for checking this!
That said, it probably wasn't really single threaded, at least assuming that you had at least one reader.
Quoted 4 lines
I have no idea what's wrong in
count_lim_atomic.c.Can you look into this? There might be something wrong in the header file under
CodeSamples/arch-ppc64.h.There isn't much in that file anymore because we now rely on the gcc intrinsics for the most part. Which might well be the problem, depending on compiler versions and so on.
Could you please send me the output of "objdump -d" on count_lim_atomic.o? And on the full
count_lim_atomicbinary, just in case gcc decides to be tricky in its code generation?In the meantime, there might well be a generic bug in
count_lim_atomic.cthat just happens not to be exercised on x86, and I will look into that. I am on travel next week, so will be in odd timezones, but should have at least a little useful airplane time to look into this.Quoted 1 line
On
x86_64, I've never seen the count mismatch.Well, David Goldblatt's first C++11 signal-based litmus test wouldn't fail on PowerPC but did on x86, so I guess that they are now even. ;-)
Thanx, Paul
Quoted 12 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.
Thanks for looking into this!
I also suspected the use of "weak" semantics of __atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.
I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 31 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
--- CodeSamples/api-pthreads/api-gcc.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +3
-5@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \ })static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Quoted 43 lines · Akira Yokosawa
Quoted 12 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 16 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
--- CodeSamples/api-pthreads/api-gcc.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +0
-0@@ -166,11 +166,9 @@ struct __xchg_dummy {
Quoted 11 lines
CodeSamples/api-pthreads/api-gcc.h struct __xchg_dummy {
Quoted 11 lines
CodeSamples/api-pthreads/api-gcc.h +3
-5#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \
BTW, returning (n) in the fail case would be problematic when "(o) == (n)" in the first place, wouldn't it?
Thanks, Akira
Quoted 5 lines
Quoted 4 lines
CodeSamples/api-pthreads/api-gcc.h +0
-0})static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Hi Akira,
Quoted 60 lines · Akira Yokosawa
Quoted 43 lines · Akira Yokosawa
Quoted 12 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 16 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
--- CodeSamples/api-pthreads/api-gcc.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +0
-0@@ -166,11 +166,9 @@ struct __xchg_dummy {Quoted 11 lines
CodeSamples/api-pthreads/api-gcc.h struct __xchg_dummy {
Quoted 11 lines
CodeSamples/api-pthreads/api-gcc.h +3
-5#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \BTW, returning (n) in the fail case would be problematic when "(o) == (n)" in the first place, wouldn't it?
Quoted 2 lines
Thanks, Akira
That's right. Then we should return (*ptr) if CAS fails. I think whether we return (n) or (*ptr) depends on the definition of xmpxchg :-)
Thanks,
--Junchang
Quoted 6 lines
Quoted 5 lines
Quoted 4 lines
CodeSamples/api-pthreads/api-gcc.h +0
-0})static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Hi Akira,
Thanks for the mail. My understanding is that PPC uses LL/SC to emulate CAS by using a tiny loop. Unfortunately, the LL/SC loop itself could fail (due to, for example, context switches) even if *ptr equals to old. In such a case, a CAS instruction in actually should return a success. I think this is what the term "spurious fail" describes. Here is a reference:
http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_family
It seems that __atomic_compare_exchange_n() provides option "weak" for performance. I tested these two solutions and got the following results:
1 4 8 16 32 64
my patch (ns) 35 34 37 73 142 281
strong (ns) 39 39 41 79 158 313
I tested the performance of count_lim_atomic by varying the number of updaters (./count_lim_atomic N uperf) on a 8-core PPC server. The first row in the table is the result when my patch is used, and the second row is the result when the 4th argument of the function is set to false(0). It seems performance improves slightly if option "weak" is used. However, there is no performance boost as we expected. So your solution sounds good if safety is one major concern because option "weak" seems risky to me :-)
Another interesting observation is that the performance of LL/SC-based CAS instruction deteriorates dramatically when the number of working threads exceeds the number of CPU cores.
Thanks,
--Junchang
Quoted 60 lines · Akira Yokosawa
Quoted 12 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 31 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
--- CodeSamples/api-pthreads/api-gcc.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +3
-5@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \ })static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Quoted 9 lines · Junchang Wang
Hi Akira,
Thanks for the mail. My understanding is that PPC uses LL/SC to emulate CAS by using a tiny loop. Unfortunately, the LL/SC loop itself could fail (due to, for example, context switches) even if *ptr equals to old. In such a case, a CAS instruction in actually should return a success. I think this is what the term "spurious fail" describes. Here is a reference:
http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_family
First, thank you both for your work on this! And yes, my cmpxchg() code is clearly quite broken.
Quoted 7 lines
It seems that
__atomic_compare_exchange_n()provides option "weak" for performance. I tested these two solutions and got the following results:1 4 8 16 32 64my patch (ns) 35 34 37 73 142 281
strong (ns) 39 39 41 79 158 313
So strong is a bit slower, correct?
Quoted 9 lines
I tested the performance of
count_lim_atomicby varying the number of updaters (./count_lim_atomic N uperf) on a 8-core PPC server. The first row in the table is the result when my patch is used, and the second row is the result when the 4th argument of the function is set to false(0). It seems performance improves slightly if option "weak" is used. However, there is no performance boost as we expected. So your solution sounds good if safety is one major concern because option "weak" seems risky to me :-)
Quoted 3 lines
Another interesting observation is that the performance of LL/SC-based CAS instruction deteriorates dramatically when the number of working threads exceeds the number of CPU cores.
If weak is faster, would it make sense to return (~o), that is, the bitwise complement of the expected arguement, when the weak __atomic_compare_exchange_n() fails? This would get the improved performance (if I understand your results above) while correctly handling the strange (but possible) case where o==n.
Does that make sense, or am I missing something?
Thanx, Paul
Quoted 66 lines
Thanks,
--JunchangQuoted 60 lines · Akira Yokosawa
Quoted 12 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 31 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
--- CodeSamples/api-pthreads/api-gcc.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +3
-5@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \ })static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Quoted 18 lines · Paul E. McKenney
Quoted 9 lines · Junchang Wang
Hi Akira,
Thanks for the mail. My understanding is that PPC uses LL/SC to emulate CAS by using a tiny loop. Unfortunately, the LL/SC loop itself could fail (due to, for example, context switches) even if *ptr equals to old. In such a case, a CAS instruction in actually should return a success. I think this is what the term "spurious fail" describes. Here is a reference:
http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_familyFirst, thank you both for your work on this! And yes, my
cmpxchg()code is clearly quite broken.Quoted 4 lines
It seems that
__atomic_compare_exchange_n()provides option "weak" for performance. I tested these two solutions and got the following results:
Quoted 5 lines
Quoted 3 lines
1 4 8 16 32 64my patch (ns) 35 34 37 73 142 281
strong (ns) 39 39 41 79 158 313So strong is a bit slower, correct?
Emitted code of strong has an extra conditional branch instruction for retry loop.
Diff of disassembled code of atomic_cmpxchg (current master vs. strong):
@@ -23,14 +23,15 @@
ac 04 00 7c hwsync
28 40 40 7d lwarx r10,0,r8 00 30 8a 7f cmpw cr7,r10,r6 -0c 00 9e 40 bne cr7,bc4 <atomic_cmpxchg+0x6c> +10 00 9e 40 bne cr7,bc8 <atomic_cmpxchg+0x70> 2d 41 e0 7c stwcx. r7,0,r8 00 00 80 4f mcrf cr7,cr0 +ec ff 9e 40 bne cr7,bb0 <atomic_cmpxchg+0x58> <--- extra branch 2c 01 00 4c isync 26 10 10 7d mfocrf r8,1 fe ff 08 55 rlwinm r8,r8,31,31,31 00 00 88 2f cmpwi cr7,r8,0 -08 00 9e 40 bne cr7,bdc <atomic_cmpxchg+0x84> +08 00 9e 40 bne cr7,be0 <atomic_cmpxchg+0x88> 00 00 49 91 stw r10,0(r9) 34 00 3f 81 lwz r9,52(r31) b4 07 29 7d extsw r9,r9
[...]
Quoted 14 lines
Quoted 10 lines
I tested the performance of
count_lim_atomicby varying the number of updaters (./count_lim_atomic N uperf) on a 8-core PPC server. The first row in the table is the result when my patch is used, and the second row is the result when the 4th argument of the function is set to false(0). It seems performance improves slightly if option "weak" is used. However, there is no performance boost as we expected. So your solution sounds good if safety is one major concern because option "weak" seems risky to me :-)Quoted 3 lines
Another interesting observation is that the performance of LL/SC-based CAS instruction deteriorates dramatically when the number of working threads exceeds the number of CPU cores.
Quoted 7 lines
If weak is faster, would it make sense to return (~o), that is, the bitwise complement of the expected arguement, when the weak
__atomic_compare_exchange_n()fails? This would get the improved performance (if I understand your results above) while correctly handling the strange (but possible) case where o==n.Does that make sense, or am I missing something?
Sounds reasonable to me.
Thanks, Akira
Quoted 70 lines
Thanx, Paul
Quoted 66 lines
Thanks,
--JunchangQuoted 60 lines · Akira Yokosawa
Quoted 12 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 31 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
--- CodeSamples/api-pthreads/api-gcc.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +3
-5@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \ })static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Quoted 38 lines · Paul E. McKenney
Quoted 9 lines · Junchang Wang
Hi Akira,
Thanks for the mail. My understanding is that PPC uses LL/SC to emulate CAS by using a tiny loop. Unfortunately, the LL/SC loop itself could fail (due to, for example, context switches) even if *ptr equals to old. In such a case, a CAS instruction in actually should return a success. I think this is what the term "spurious fail" describes. Here is a reference:
http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_familyFirst, thank you both for your work on this! And yes, my
cmpxchg()code is clearly quite broken.Quoted 7 lines
It seems that
__atomic_compare_exchange_n()provides option "weak" for performance. I tested these two solutions and got the following results:1 4 8 16 32 64my patch (ns) 35 34 37 73 142 281
strong (ns) 39 39 41 79 158 313So strong is a bit slower, correct?
Quoted 9 lines
I tested the performance of
count_lim_atomicby varying the number of updaters (./count_lim_atomic N uperf) on a 8-core PPC server. The first row in the table is the result when my patch is used, and the second row is the result when the 4th argument of the function is set to false(0). It seems performance improves slightly if option "weak" is used. However, there is no performance boost as we expected. So your solution sounds good if safety is one major concern because option "weak" seems risky to me :-)Quoted 3 lines
Another interesting observation is that the performance of LL/SC-based CAS instruction deteriorates dramatically when the number of working threads exceeds the number of CPU cores.
Quoted 7 lines
If weak is faster, would it make sense to return (~o), that is, the bitwise complement of the expected arguement, when the weak
__atomic_compare_exchange_n()fails? This would get the improved performance (if I understand your results above) while correctly handling the strange (but possible) case where o==n.Does that make sense, or am I missing something?
Hi Paul and Akira,
Yes, the weak version is faster. The solution looks good. But when I tried to use the following patch
#define cmpxchg(ptr, o, n) \
({ \
typeof(*ptr) old = (o); \
(__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1,
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \
(o) : (~o); \
})gcc complains of my use of complement symbol
../api.h:769:12: error: wrong type argument to bit-complement
(o) : (~o); \
^Any suggestions?
Thanks,
--Junchang
Quoted 70 lines
Thanx, Paul
Quoted 66 lines
Thanks,
--JunchangQuoted 60 lines · Akira Yokosawa
Quoted 12 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 31 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
--- CodeSamples/api-pthreads/api-gcc.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +3
-5@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \ })static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Quoted 49 lines · Junchang Wang
Quoted 38 lines · Paul E. McKenney
Quoted 9 lines · Junchang Wang
Hi Akira,
Thanks for the mail. My understanding is that PPC uses LL/SC to emulate CAS by using a tiny loop. Unfortunately, the LL/SC loop itself could fail (due to, for example, context switches) even if *ptr equals to old. In such a case, a CAS instruction in actually should return a success. I think this is what the term "spurious fail" describes. Here is a reference:
http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_familyFirst, thank you both for your work on this! And yes, my
cmpxchg()code is clearly quite broken.Quoted 7 lines
It seems that
__atomic_compare_exchange_n()provides option "weak" for performance. I tested these two solutions and got the following results:1 4 8 16 32 64my patch (ns) 35 34 37 73 142 281
strong (ns) 39 39 41 79 158 313So strong is a bit slower, correct?
Quoted 9 lines
I tested the performance of
count_lim_atomicby varying the number of updaters (./count_lim_atomic N uperf) on a 8-core PPC server. The first row in the table is the result when my patch is used, and the second row is the result when the 4th argument of the function is set to false(0). It seems performance improves slightly if option "weak" is used. However, there is no performance boost as we expected. So your solution sounds good if safety is one major concern because option "weak" seems risky to me :-)Quoted 3 lines
Another interesting observation is that the performance of LL/SC-based CAS instruction deteriorates dramatically when the number of working threads exceeds the number of CPU cores.
Quoted 7 lines
If weak is faster, would it make sense to return (~o), that is, the bitwise complement of the expected arguement, when the weak
__atomic_compare_exchange_n()fails? This would get the improved performance (if I understand your results above) while correctly handling the strange (but possible) case where o==n.Does that make sense, or am I missing something?
Hi Paul and Akira,
Quoted 7 lines
Yes, the weak version is faster. The solution looks good. But when I tried to use the following patch
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) old = (o); \ (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1,
You need a "\" at the end of the line above. (If it was not unintentionally wrapped.)
If it was wrapped by your mailer, which is troublesome in sending patches, please refer to:
https://www.kernel.org/doc/html/latest/process/email-clients.html.
Quoted 11 lines
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ (o) : (~o); \ })gcc complains of my use of complement symbol
../api.h:769:12: error: wrong type argument to bit-complement(o) : (~o); \ ^Any suggestions?
I don't see such error if I add the "\" mentioned above. Or do you use some strict error checking option of GCC?
Thanks, Akira
Quoted 75 lines
Thanks,
--JunchangQuoted 70 lines
Thanx, Paul
Quoted 66 lines
Thanks,
--JunchangQuoted 60 lines · Akira Yokosawa
Quoted 12 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 31 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
--- CodeSamples/api-pthreads/api-gcc.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +3
-5@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \ })static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Quoted 72 lines · Akira Yokosawa
Quoted 49 lines · Junchang Wang
Quoted 38 lines · Paul E. McKenney
Quoted 9 lines · Junchang Wang
Hi Akira,
Thanks for the mail. My understanding is that PPC uses LL/SC to emulate CAS by using a tiny loop. Unfortunately, the LL/SC loop itself could fail (due to, for example, context switches) even if *ptr equals to old. In such a case, a CAS instruction in actually should return a success. I think this is what the term "spurious fail" describes. Here is a reference:
http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_familyFirst, thank you both for your work on this! And yes, my
cmpxchg()code is clearly quite broken.Quoted 7 lines
It seems that
__atomic_compare_exchange_n()provides option "weak" for performance. I tested these two solutions and got the following results:1 4 8 16 32 64my patch (ns) 35 34 37 73 142 281
strong (ns) 39 39 41 79 158 313So strong is a bit slower, correct?
Quoted 9 lines
I tested the performance of
count_lim_atomicby varying the number of updaters (./count_lim_atomic N uperf) on a 8-core PPC server. The first row in the table is the result when my patch is used, and the second row is the result when the 4th argument of the function is set to false(0). It seems performance improves slightly if option "weak" is used. However, there is no performance boost as we expected. So your solution sounds good if safety is one major concern because option "weak" seems risky to me :-)Quoted 3 lines
Another interesting observation is that the performance of LL/SC-based CAS instruction deteriorates dramatically when the number of working threads exceeds the number of CPU cores.
Quoted 7 lines
If weak is faster, would it make sense to return (~o), that is, the bitwise complement of the expected arguement, when the weak
__atomic_compare_exchange_n()fails? This would get the improved performance (if I understand your results above) while correctly handling the strange (but possible) case where o==n.Does that make sense, or am I missing something?
Hi Paul and Akira,
Quoted 7 lines
Yes, the weak version is faster. The solution looks good. But when I tried to use the following patch
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) old = (o); \ (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1,You need a "\" at the end of the line above. (If it was not unintentionally wrapped.)
If it was wrapped by your mailer, which is troublesome in sending patches, please refer to:
https://www.kernel.org/doc/html/latest/process/email-clients.html.
Quoted 6 lines
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ (o) : (~o); \ })gcc complains of my use of complement symbol
Quoted 8 lines
Quoted 5 lines
../api.h:769:12: error: wrong type argument to bit-complement(o) : (~o); \ ^Any suggestions?
I don't see such error if I add the "\" mentioned above. Or do you use some strict error checking option of GCC?
Ah, I see that the error in compiling CodeSamples/advsync/q.c.
The call site is:
struct el *q_pop(struct queue *q)
{
struct el *p;
struct el *pnext;
for (;;) {
do {
p = q->head;
pnext = p->next;
if (pnext == NULL)
return NULL;
} while (cmpxchg(&q->head, p, pnext) != p);
if (p != &q->dummy)
return p;
q_push(&q->dummy, q);
if (q->head == &q->dummy)
return NULL;
}
}In this case, p and pnext are pointers, hence the error. returning (o)+1 instead should be OK in this case.
But now, "count_lim_atomic 3 hog" says:
FAIL: only reached -1829 rather than 0
on x86_64. Hmm. No such error is observed on POWER8. Hmm...
The strong version works both on x86_64 and POWER8.
Thanks, Akira
Quoted 79 lines
Thanks, Akira
Quoted 75 lines
Thanks,
--JunchangQuoted 70 lines
Thanx, Paul
Quoted 66 lines
Thanks,
--JunchangQuoted 60 lines · Akira Yokosawa
Quoted 12 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 31 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
--- CodeSamples/api-pthreads/api-gcc.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +3
-5@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \ })static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Quoted 107 lines · Akira Yokosawa
Quoted 72 lines · Akira Yokosawa
Quoted 49 lines · Junchang Wang
Quoted 38 lines · Paul E. McKenney
Quoted 9 lines · Junchang Wang
Hi Akira,
Thanks for the mail. My understanding is that PPC uses LL/SC to emulate CAS by using a tiny loop. Unfortunately, the LL/SC loop itself could fail (due to, for example, context switches) even if *ptr equals to old. In such a case, a CAS instruction in actually should return a success. I think this is what the term "spurious fail" describes. Here is a reference:
http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_familyFirst, thank you both for your work on this! And yes, my
cmpxchg()code is clearly quite broken.Quoted 7 lines
It seems that
__atomic_compare_exchange_n()provides option "weak" for performance. I tested these two solutions and got the following results:1 4 8 16 32 64my patch (ns) 35 34 37 73 142 281
strong (ns) 39 39 41 79 158 313So strong is a bit slower, correct?
Quoted 9 lines
I tested the performance of
count_lim_atomicby varying the number of updaters (./count_lim_atomic N uperf) on a 8-core PPC server. The first row in the table is the result when my patch is used, and the second row is the result when the 4th argument of the function is set to false(0). It seems performance improves slightly if option "weak" is used. However, there is no performance boost as we expected. So your solution sounds good if safety is one major concern because option "weak" seems risky to me :-)Quoted 3 lines
Another interesting observation is that the performance of LL/SC-based CAS instruction deteriorates dramatically when the number of working threads exceeds the number of CPU cores.
Quoted 7 lines
If weak is faster, would it make sense to return (~o), that is, the bitwise complement of the expected arguement, when the weak
__atomic_compare_exchange_n()fails? This would get the improved performance (if I understand your results above) while correctly handling the strange (but possible) case where o==n.Does that make sense, or am I missing something?
Hi Paul and Akira,
Quoted 7 lines
Yes, the weak version is faster. The solution looks good. But when I tried to use the following patch
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) old = (o); \ (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1,You need a "\" at the end of the line above. (If it was not unintentionally wrapped.)
If it was wrapped by your mailer, which is troublesome in sending patches, please refer to:
https://www.kernel.org/doc/html/latest/process/email-clients.html.
Quoted 6 lines
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ (o) : (~o); \ })gcc complains of my use of complement symbol
Quoted 8 lines
Quoted 5 lines
../api.h:769:12: error: wrong type argument to bit-complement(o) : (~o); \ ^Any suggestions?
I don't see such error if I add the "\" mentioned above. Or do you use some strict error checking option of GCC?
Ah, I see that the error in compiling
CodeSamples/advsync/q.c.The call site is:
struct el *q_pop(struct queue *q)
{ struct el *p; struct el *pnext; for (;;) { do { p = q->head; pnext = p->next; if (pnext == NULL) return NULL; } while (cmpxchg(&q->head, p, pnext) != p); if (p != &q->dummy) return p; q_push(&q->dummy, q); if (q->head == &q->dummy) return NULL; } }
Quoted 3 lines
In this case, p and pnext are pointers, hence the error. returning (o)+1 instead should be OK in this case.
Hi Akira and Paul,
Returning (o)+1 if the CAS primitive fails works fine. Thanks a lot!
Quoted 8 lines
But now, "
count_lim_atomic3 hog" says:FAIL: only reached -1829 rather than 0
on
x86_64. Hmm. No such error is observed on POWER8. Hmm...The strong version works both on
x86_64and POWER8.
Indeed (cry) ! Thanks for checking this. I will take a look and work on this.
BTW, I found I'm not good in writing C macro (e.g., cmpxchg). Do you know some specification/document on writing C macro functions in Linux?
Thanks,
--Junchang
Quoted 83 lines
Thanks, Akira
Quoted 79 lines
Thanks, Akira
Quoted 75 lines
Thanks,
--JunchangQuoted 70 lines
Thanx, Paul
Quoted 66 lines
Thanks,
--JunchangQuoted 60 lines · Akira Yokosawa
Quoted 12 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 31 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
--- CodeSamples/api-pthreads/api-gcc.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +3
-5@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \ })static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
On 2018/10/26 08:58:30 +0800, Junchang Wang wrote:
[...]
Quoted 4 lines
BTW, I found I'm not good in writing C macro (e.g., cmpxchg). Do you know some specification/document on writing C macro functions in Linux?
Although I'm not qualified as a kernel developer, Linux kernel's "coding style" has a section on this. See:
https://www.kernel.org/doc/html/latest/process/coding-style.html#macros-enums-and-rtl
In that regard, macros I added in commit b2acf6239a95 ("count: Tweak counttorture.h to avoid segfault") do not meet the style guide in a couple of ways:
1) Inline functions are preferable to macros resembling functions
2) Macros with multiple statements should be enclosed in a do - while block
3) ...
Any idea for improving them is more than welcome!
Thanks, Akira
Quoted 4 lines
Thanks,
--Junchang
[...]
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 73 lines · Paul E. McKenney
Quoted 16 lines · Akira Yokosawa
On 2018/10/26 08:58:30 +0800, Junchang Wang wrote:
[...]Quoted 4 lines
BTW, I found I'm not good in writing C macro (e.g., cmpxchg). Do you know some specification/document on writing C macro functions in Linux?
Although I'm not qualified as a kernel developer, Linux kernel's "coding style" has a section on this. See:
https://www.kernel.org/doc/html/latest/process/coding-style.html#macros-enums-and-rtl
In that regard, macros I added in commit
b2acf6239a95("count: Tweakcounttorture.hto avoid segfault") do not meet the style guide in a couple of ways:Quoted 5 lines
1) Inline functions are preferable to macros resembling functions
2) Macros with multiple statements should be enclosed in a do - while block
3) ...Any idea for improving them is more than welcome!
Let's see...
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____actual = (o); \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? (o) : (o)+1; \ })We cannot do #1 because
cmpxchg()is type-generic, and thus cannot be implemented as a C function. (C++ could use templates, but we are not writing C++ here.)We cannot do #2 because
cmpxchg()must return a value.Indentation is not perfect, but given the long names really cannot be improved all that much, if at all.
However, we do have a problem, namely the multiple uses of "o", which would be very bad if "o" was an expression with side-effects.
How about the following?
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? _____old : _____old + 1; \ })This still might have problems with signed integer overflow, but I am inclined to ignore that for the moment. Because paying attention to it results in something like this:
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) \ ? _____old \ : _____old > 0 ? _____old - 1; : _____old + 1; \ })
Quoted 2 lines
Thoughts? Most especially, any better ideas?
Hi Paul and Akira,
Thanks a lot for the mail. I have been curious about why cmpxchg() sticks to returning the old value to notify the caller if the CAS operation succeeds. Besides the overflow issue mentioned in Paul's last mail, current cmpxchg() can only be used in the control flow of "if CAS fails, do something" (Control Flow 1). However, it cannot be used in the control flow of "if CAS succeeds, do something" (Control Flow 2).
So another option is that cmpxchg() could just return true or false, and if the caller needs the current value of the content of the specified memory address, it could read the value out of field *old*. Of course, we must adjust the parameters of cmpxchg() slightly by passing the address of *old* to the function. Here is how cmpxchg() looks like in my mind:
#define cmpxchg(ptr, o, n) \
({ \
__atomic_compare_exchange_n(ptr, (void *)(o), (n), 1, \
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \
})static __inline__ int atomic_cmpxchg(atomic_t *v, int *old, int new)
{
return cmpxchg(&v->counter, old, new);
}Any thoughts? Or did I miss something here? I will send the full patch in another thread in case you want to review the code.
Thanks,
--Junchang
Quoted 2 lines
Thanx, Paul
Quoted 100 lines · Junchang Wang
Quoted 73 lines · Paul E. McKenney
Quoted 16 lines · Akira Yokosawa
On 2018/10/26 08:58:30 +0800, Junchang Wang wrote:
[...]Quoted 4 lines
BTW, I found I'm not good in writing C macro (e.g., cmpxchg). Do you know some specification/document on writing C macro functions in Linux?
Although I'm not qualified as a kernel developer, Linux kernel's "coding style" has a section on this. See:
https://www.kernel.org/doc/html/latest/process/coding-style.html#macros-enums-and-rtl
In that regard, macros I added in commit
b2acf6239a95("count: Tweakcounttorture.hto avoid segfault") do not meet the style guide in a couple of ways:Quoted 5 lines
1) Inline functions are preferable to macros resembling functions
2) Macros with multiple statements should be enclosed in a do - while block
3) ...Any idea for improving them is more than welcome!
Let's see...
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____actual = (o); \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? (o) : (o)+1; \ })We cannot do #1 because
cmpxchg()is type-generic, and thus cannot be implemented as a C function. (C++ could use templates, but we are not writing C++ here.)We cannot do #2 because
cmpxchg()must return a value.Indentation is not perfect, but given the long names really cannot be improved all that much, if at all.
However, we do have a problem, namely the multiple uses of "o", which would be very bad if "o" was an expression with side-effects.
How about the following?
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? _____old : _____old + 1; \ })This still might have problems with signed integer overflow, but I am inclined to ignore that for the moment. Because paying attention to it results in something like this:
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) \ ? _____old \ : _____old > 0 ? _____old - 1; : _____old + 1; \ })Quoted 2 lines
Thoughts? Most especially, any better ideas?
Hi Paul and Akira,
Thanks a lot for the mail. I have been curious about why
cmpxchg()sticks to returning the old value to notify the caller if the CAS operation succeeds. Besides the overflow issue mentioned in Paul's last mail, currentcmpxchg()can only be used in the control flow of "if CAS fails, do something" (Control Flow 1). However, it cannot be used in the control flow of "if CAS succeeds, do something" (Control Flow 2).So another option is that
cmpxchg()could just return true or false, and if the caller needs the current value of the content of the specified memory address, it could read the value out of field *old*. Of course, we must adjust the parameters ofcmpxchg()slightly by passing the address of *old* to the function. Here is howcmpxchg()looks like in my mind:#define
cmpxchg(ptr, o, n)\({ \ __atomic_compare_exchange_n(ptr, (void *)(o), (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ })
Quoted 7 lines
static
__inline__intatomic_cmpxchg(atomic_t *v, int *old, int new){ return cmpxchg(&v->counter, old, new); }Any thoughts? Or did I miss something here? I will send the full patch in another thread in case you want to review the code.
Well, perfbook CodeSamples' API mimics that of Linux kernel in user land. So changing behavior of existing API is not acceptable, I suppose.
There might already be such an API in Linux kernel, but I'm not sure.
Ah, looks like Paul has answered that point.
Thanks, Akira
Quoted 8 lines
Thanks,
--JunchangQuoted 2 lines
Thanx, Paul
Quoted 100 lines · Junchang Wang
Quoted 73 lines · Paul E. McKenney
Quoted 16 lines · Akira Yokosawa
On 2018/10/26 08:58:30 +0800, Junchang Wang wrote:
[...]Quoted 4 lines
BTW, I found I'm not good in writing C macro (e.g., cmpxchg). Do you know some specification/document on writing C macro functions in Linux?
Although I'm not qualified as a kernel developer, Linux kernel's "coding style" has a section on this. See:
https://www.kernel.org/doc/html/latest/process/coding-style.html#macros-enums-and-rtl
In that regard, macros I added in commit
b2acf6239a95("count: Tweakcounttorture.hto avoid segfault") do not meet the style guide in a couple of ways:Quoted 5 lines
1) Inline functions are preferable to macros resembling functions
2) Macros with multiple statements should be enclosed in a do - while block
3) ...Any idea for improving them is more than welcome!
Let's see...
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____actual = (o); \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? (o) : (o)+1; \ })We cannot do #1 because
cmpxchg()is type-generic, and thus cannot be implemented as a C function. (C++ could use templates, but we are not writing C++ here.)We cannot do #2 because
cmpxchg()must return a value.Indentation is not perfect, but given the long names really cannot be improved all that much, if at all.
However, we do have a problem, namely the multiple uses of "o", which would be very bad if "o" was an expression with side-effects.
How about the following?
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? _____old : _____old + 1; \ })This still might have problems with signed integer overflow, but I am inclined to ignore that for the moment. Because paying attention to it results in something like this:
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) \ ? _____old \ : _____old > 0 ? _____old - 1; : _____old + 1; \ })Quoted 2 lines
Thoughts? Most especially, any better ideas?
Hi Paul and Akira,
Thanks a lot for the mail. I have been curious about why
cmpxchg()sticks to returning the old value to notify the caller if the CAS operation succeeds. Besides the overflow issue mentioned in Paul's last mail, currentcmpxchg()can only be used in the control flow of "if CAS fails, do something" (Control Flow 1). However, it cannot be used in the control flow of "if CAS succeeds, do something" (Control Flow 2).So another option is that
cmpxchg()could just return true or false, and if the caller needs the current value of the content of the specified memory address, it could read the value out of field *old*. Of course, we must adjust the parameters ofcmpxchg()slightly by passing the address of *old* to the function. Here is howcmpxchg()looks like in my mind:#define
cmpxchg(ptr, o, n)\({ \ __atomic_compare_exchange_n(ptr, (void *)(o), (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ })
Quoted 7 lines
static
__inline__intatomic_cmpxchg(atomic_t *v, int *old, int new){ return cmpxchg(&v->counter, old, new); }Any thoughts? Or did I miss something here? I will send the full patch in another thread in case you want to review the code.
The reason perfbook's cmpxchg() returns the old value is that the Linux kernel's cmpxchg() returns the old value. The reason that the Linux kernel's cmpxchg() returns the old value is that doing so allows a tighter retry loop -- it is not necessary to separately reload the current value. This does mean that one disadvantage of returning a made-up value is that the next iteration would likely be starting from the wrong value, but this should not be a real problem given that spurious failure should be rare. After all, if spurious failure is not rare, we have way more serious performance issues. ;-)
Thanx, Paul
Quoted 25 lines · Paul E. McKenney
Quoted 16 lines · Akira Yokosawa
On 2018/10/26 08:58:30 +0800, Junchang Wang wrote:
[...]Quoted 4 lines
BTW, I found I'm not good in writing C macro (e.g., cmpxchg). Do you know some specification/document on writing C macro functions in Linux?
Although I'm not qualified as a kernel developer, Linux kernel's "coding style" has a section on this. See:
https://www.kernel.org/doc/html/latest/process/coding-style.html#macros-enums-and-rtl
In that regard, macros I added in commit
b2acf6239a95("count: Tweakcounttorture.hto avoid segfault") do not meet the style guide in a couple of ways:Quoted 5 lines
1) Inline functions are preferable to macros resembling functions
2) Macros with multiple statements should be enclosed in a do - while block
3) ...Any idea for improving them is more than welcome!
Let's see...
Quoted 7 lines
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____actual = (o); \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? (o) : (o)+1; \ })
Oh, my concern was macros I added in counttorture.h to support #ifndef KEEP_GCC_THREAD_LOCAL.
But those macros are used solely in the header file, so the current definition might be good enough.
OTH, macros defined in api-gcc.h should be made as robust as possible. Hence your review of cmpxchg() is quite instructive to me.
Quoted 7 lines
We cannot do #1 because
cmpxchg()is type-generic, and thus cannot be implemented as a C function. (C++ could use templates, but we are not writing C++ here.)We cannot do #2 because
cmpxchg()must return a value.
These reasoning might not be obvious to those who are new to C preprocessor programming. Current style guide of kernel doesn't look good enough, partly because of its intended audiences.
Quoted 5 lines
Indentation is not perfect, but given the long names really cannot be improved all that much, if at all.
However, we do have a problem, namely the multiple uses of "o", which would be very bad if "o" was an expression with side-effects.
I didn't notice this point.
Quoted 13 lines
How about the following?
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? _____old : _____old + 1; \ })
Quoted 2 lines
This still might have problems with signed integer overflow, but I am inclined to ignore that for the moment.
Behavior of overflow of signed integer is undefined in C standard, right?
Quoted 14 lines
Because paying attention to it
results in something like this:#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) \ ? _____old \ : _____old > 0 ? _____old - 1; : _____old + 1; \ })
Quoted 1 line
Thoughts? Most especially, any better ideas?
Let me think this over.
BTW, the purpose of using the name "_____old" and the like may not be obvious either.
If we use "old" instead, naming collision can happen if "old" is given as an argument to this macro in its call sites. Am I guessing right?
Thanks, Akira
Quoted 3 lines
Thanx, Paul
Quoted 34 lines · Akira Yokosawa
Quoted 25 lines · Paul E. McKenney
Quoted 16 lines · Akira Yokosawa
On 2018/10/26 08:58:30 +0800, Junchang Wang wrote:
[...]Quoted 4 lines
BTW, I found I'm not good in writing C macro (e.g., cmpxchg). Do you know some specification/document on writing C macro functions in Linux?
Although I'm not qualified as a kernel developer, Linux kernel's "coding style" has a section on this. See:
https://www.kernel.org/doc/html/latest/process/coding-style.html#macros-enums-and-rtl
In that regard, macros I added in commit
b2acf6239a95("count: Tweakcounttorture.hto avoid segfault") do not meet the style guide in a couple of ways:Quoted 5 lines
1) Inline functions are preferable to macros resembling functions
2) Macros with multiple statements should be enclosed in a do - while block
3) ...Any idea for improving them is more than welcome!
Let's see...
Quoted 7 lines
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____actual = (o); \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? (o) : (o)+1; \ })
Quoted 5 lines
Oh, my concern was macros I added in
counttorture.hto support #ifndefKEEP_GCC_THREAD_LOCAL.But those macros are used solely in the header file, so the current definition might be good enough.
These ones?
#define _wait_all_threads() { \
while (READ_ONCE(finalthreadcount) < nthreadsexpected) \
poll(NULL, 0, 1);}
#define _count_unregister_thread(n) count_unregister_thread(n + 1)
#define final_wait_all_threads() { \
WRITE_ONCE(finalthreadcount, nthreadsexpected + 1); \
wait_all_threads();}The _count_unregister_thread() is fine.
The _wait_all_threads() and final_wait_all_threads() are fine given their current usage. One not-yet-needed way to future-proof them would be as follows:
#define _wait_all_threads() \
do { \
while (READ_ONCE(finalthreadcount) < nthreadsexpected) \
poll(NULL, 0, 1); \
} while (0)
#define final_wait_all_threads() \
do { \
WRITE_ONCE(finalthreadcount, nthreadsexpected + 1); \
wait_all_threads(); \
} while (0)Your next question is "why does this matter", to which I would point you
here: https://kernelnewbies.org/FAQ/DoWhile0 Mostly because I never can remember all of the failure cases that led to the Linux-kernel coding-style rules. ;-)
Quoted 2 lines
OTH, macros defined in
api-gcc.hshould be made as robust as possible. Hence your review ofcmpxchg()is quite instructive to me.
Glad it helped!
Quoted 9 lines
Quoted 5 lines
We cannot do #1 because
cmpxchg()is type-generic, and thus cannot be implemented as a C function. (C++ could use templates, but we are not writing C++ here.)We cannot do #2 because
cmpxchg()must return a value.These reasoning might not be obvious to those who are new to C preprocessor programming. Current style guide of kernel doesn't look good enough, partly because of its intended audiences.
To be fair, it doesn't get updated as often as it should.
Quoted 7 lines
Quoted 5 lines
Indentation is not perfect, but given the long names really cannot be improved all that much, if at all.
However, we do have a problem, namely the multiple uses of "o", which would be very bad if "o" was an expression with side-effects.
I didn't notice this point.
Neither did I earlier in this thread. ;-)
Quoted 12 lines
Quoted 12 lines
How about the following?
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? _____old : _____old + 1; \ })
Quoted 4 lines
Quoted 2 lines
This still might have problems with signed integer overflow, but I am inclined to ignore that for the moment.
Behavior of overflow of signed integer is undefined in C standard, right?
Exactly. An alternative approach is to do as the Linux kernel does and tell gcc to wrap signed integers on overflow, as the standard mandates for unsigned integers. My preference would be to avoid signed overflow.
Quoted 14 lines
Quoted 14 lines
Because paying attention to it
results in something like this:#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) \ ? _____old \ : _____old > 0 ? _____old - 1; : _____old + 1; \ })
Quoted 8 lines
Quoted 1 line
Thoughts? Most especially, any better ideas?
Let me think this over.
BTW, the purpose of using the name "
_____old" and the like may not be obvious either.
If we use "old" instead, naming collision can happen if "old" is given as an argument to this macro in its call sites. Am I guessing right?
You got it exactly right! The "old" in the argument is intended to refer to something in an outer scope, but it would instead refer to the macro's local variable.
Thanx, Paul
Quoted 51 lines · Paul E. McKenney
Quoted 34 lines · Akira Yokosawa
Quoted 25 lines · Paul E. McKenney
Quoted 16 lines · Akira Yokosawa
On 2018/10/26 08:58:30 +0800, Junchang Wang wrote:
[...]Quoted 4 lines
BTW, I found I'm not good in writing C macro (e.g., cmpxchg). Do you know some specification/document on writing C macro functions in Linux?
Although I'm not qualified as a kernel developer, Linux kernel's "coding style" has a section on this. See:
https://www.kernel.org/doc/html/latest/process/coding-style.html#macros-enums-and-rtl
In that regard, macros I added in commit
b2acf6239a95("count: Tweakcounttorture.hto avoid segfault") do not meet the style guide in a couple of ways:Quoted 5 lines
1) Inline functions are preferable to macros resembling functions
2) Macros with multiple statements should be enclosed in a do - while block
3) ...Any idea for improving them is more than welcome!
Let's see...
Quoted 7 lines
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____actual = (o); \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? (o) : (o)+1; \ })Quoted 5 lines
Oh, my concern was macros I added in
counttorture.hto support #ifndefKEEP_GCC_THREAD_LOCAL.But those macros are used solely in the header file, so the current definition might be good enough.
These ones?
#define _wait_all_threads() { \ while (READ_ONCE(finalthreadcount) < nthreadsexpected) \ poll(NULL, 0, 1);} #define _count_unregister_thread(n) count_unregister_thread(n + 1) #define final_wait_all_threads() { \ WRITE_ONCE(finalthreadcount, nthreadsexpected + 1); \ wait_all_threads();}
Quoted 1 line
The
_count_unregister_thread()is fine.
Well, don't we need to protect "n"? That is,
#define _count_unregister_thread(n) count_unregister_thread((n) + 1)
Quoted 16 lines
The
_wait_all_threads()andfinal_wait_all_threads()are fine given their current usage. One not-yet-needed way to future-proof them would be as follows:#define
_wait_all_threads()\do { \ while (READ_ONCE(finalthreadcount) < nthreadsexpected) \ poll(NULL, 0, 1); \ } while (0) #define final_wait_all_threads() \ do { \ WRITE_ONCE(finalthreadcount, nthreadsexpected + 1); \ wait_all_threads(); \ } while (0)
Quoted 2 lines
Your next question is "why does this matter", to which I would point you
here: https://kernelnewbies.org/FAQ/DoWhile0
This is exactly what I've wanted to know!
Quoted 43 lines
Mostly because I never
can remember all of the failure cases that led to the Linux-kernel coding-style rules. ;-)Quoted 2 lines
OTH, macros defined in
api-gcc.hshould be made as robust as possible. Hence your review ofcmpxchg()is quite instructive to me.Glad it helped!
Quoted 9 lines
Quoted 5 lines
We cannot do #1 because
cmpxchg()is type-generic, and thus cannot be implemented as a C function. (C++ could use templates, but we are not writing C++ here.)We cannot do #2 because
cmpxchg()must return a value.These reasoning might not be obvious to those who are new to C preprocessor programming. Current style guide of kernel doesn't look good enough, partly because of its intended audiences.
To be fair, it doesn't get updated as often as it should.
Quoted 7 lines
Quoted 5 lines
Indentation is not perfect, but given the long names really cannot be improved all that much, if at all.
However, we do have a problem, namely the multiple uses of "o", which would be very bad if "o" was an expression with side-effects.
I didn't notice this point.
Neither did I earlier in this thread. ;-)
Quoted 12 lines
Quoted 12 lines
How about the following?
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? _____old : _____old + 1; \ })
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
This still might have problems with signed integer overflow, but I am inclined to ignore that for the moment.
Behavior of overflow of signed integer is undefined in C standard, right?
Exactly. An alternative approach is to do as the Linux kernel does and tell gcc to wrap signed integers on overflow, as the standard mandates for unsigned integers.
So, GCC provides such an option. Let's see...
Ah, include/linux/overflow.h has a variety of helper macros. They are hard to grasp in a short while, though!
Quoted 20 lines
My preference would be to avoid signed overflow.
Quoted 18 lines
Quoted 14 lines
Because paying attention to it
results in something like this:#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) \ ? _____old \ : _____old > 0 ? _____old - 1; : _____old + 1; \ })Quoted 1 line
Thoughts? Most especially, any better ideas?
Let me think this over.
Quoted 8 lines
Quoted 4 lines
BTW, the purpose of using the name "
_____old" and the like may not be obvious either.
If we use "old" instead, naming collision can happen if "old" is given as an argument to this macro in its call sites. Am I guessing right?You got it exactly right! The "old" in the argument is intended to refer to something in an outer scope, but it would instead refer to the macro's local variable.
Which might not end up in compile error, and could be hard to track down. Whew!
Thanks, Akira
Quoted 3 lines
Thanx, Paul
Quoted 52 lines · Akira Yokosawa
Quoted 51 lines · Paul E. McKenney
Quoted 34 lines · Akira Yokosawa
Quoted 25 lines · Paul E. McKenney
Quoted 16 lines · Akira Yokosawa
On 2018/10/26 08:58:30 +0800, Junchang Wang wrote:
[...]Quoted 4 lines
BTW, I found I'm not good in writing C macro (e.g., cmpxchg). Do you know some specification/document on writing C macro functions in Linux?
Although I'm not qualified as a kernel developer, Linux kernel's "coding style" has a section on this. See:
https://www.kernel.org/doc/html/latest/process/coding-style.html#macros-enums-and-rtl
In that regard, macros I added in commit
b2acf6239a95("count: Tweakcounttorture.hto avoid segfault") do not meet the style guide in a couple of ways:Quoted 5 lines
1) Inline functions are preferable to macros resembling functions
2) Macros with multiple statements should be enclosed in a do - while block
3) ...Any idea for improving them is more than welcome!
Let's see...
Quoted 7 lines
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____actual = (o); \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? (o) : (o)+1; \ })Quoted 5 lines
Oh, my concern was macros I added in
counttorture.hto support #ifndefKEEP_GCC_THREAD_LOCAL.But those macros are used solely in the header file, so the current definition might be good enough.
These ones?
#define _wait_all_threads() { \ while (READ_ONCE(finalthreadcount) < nthreadsexpected) \ poll(NULL, 0, 1);} #define _count_unregister_thread(n) count_unregister_thread(n + 1) #define final_wait_all_threads() { \ WRITE_ONCE(finalthreadcount, nthreadsexpected + 1); \ wait_all_threads();}
Quoted 5 lines
Quoted 1 line
The
_count_unregister_thread()is fine.Well, don't we need to protect "n"? That is,
#define
_count_unregister_thread(n)count_unregister_thread((n) + 1)
Indeed we do! Color me blind, and good catch!!!
Quoted 68 lines
Quoted 15 lines
The
_wait_all_threads()andfinal_wait_all_threads()are fine given their current usage. One not-yet-needed way to future-proof them would be as follows:#define
_wait_all_threads()\do { \ while (READ_ONCE(finalthreadcount) < nthreadsexpected) \ poll(NULL, 0, 1); \ } while (0) #define final_wait_all_threads() \ do { \ WRITE_ONCE(finalthreadcount, nthreadsexpected + 1); \ wait_all_threads(); \ } while (0)Quoted 2 lines
Your next question is "why does this matter", to which I would point you
here: https://kernelnewbies.org/FAQ/DoWhile0This is exactly what I've wanted to know!
Quoted 48 lines
Mostly because I never
can remember all of the failure cases that led to the Linux-kernel coding-style rules. ;-)Quoted 2 lines
OTH, macros defined in
api-gcc.hshould be made as robust as possible. Hence your review ofcmpxchg()is quite instructive to me.Glad it helped!
Quoted 9 lines
Quoted 5 lines
We cannot do #1 because
cmpxchg()is type-generic, and thus cannot be implemented as a C function. (C++ could use templates, but we are not writing C++ here.)We cannot do #2 because
cmpxchg()must return a value.These reasoning might not be obvious to those who are new to C preprocessor programming. Current style guide of kernel doesn't look good enough, partly because of its intended audiences.
To be fair, it doesn't get updated as often as it should.
Quoted 7 lines
Quoted 5 lines
Indentation is not perfect, but given the long names really cannot be improved all that much, if at all.
However, we do have a problem, namely the multiple uses of "o", which would be very bad if "o" was an expression with side-effects.
I didn't notice this point.
Neither did I earlier in this thread. ;-)
Quoted 16 lines
Quoted 12 lines
How about the following?
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? _____old : _____old + 1; \ })Quoted 2 lines
This still might have problems with signed integer overflow, but I am inclined to ignore that for the moment.
Behavior of overflow of signed integer is undefined in C standard, right?
Quoted 8 lines
Quoted 3 lines
Exactly. An alternative approach is to do as the Linux kernel does and tell gcc to wrap signed integers on overflow, as the standard mandates for unsigned integers.
So, GCC provides such an option. Let's see...
Ah,
include/linux/overflow.hhas a variety of helper macros. They are hard to grasp in a short while, though!
Maybe check_add_overflow()?
Quoted 25 lines
Quoted 25 lines
My preference would be to avoid signed overflow.
Quoted 22 lines
Quoted 14 lines
Because paying attention to it
results in something like this:#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) _____old = (o); \ typeof(*ptr) _____actual = _____old; \ \ __atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) \ ? _____old \ : _____old > 0 ? _____old - 1; : _____old + 1; \ })Quoted 1 line
Thoughts? Most especially, any better ideas?
Let me think this over.
BTW, the purpose of using the name "
_____old" and the like may not be obvious either.
If we use "old" instead, naming collision can happen if "old" is given as an argument to this macro in its call sites. Am I guessing right?
Quoted 6 lines
Quoted 3 lines
You got it exactly right! The "old" in the argument is intended to refer to something in an outer scope, but it would instead refer to the macro's local variable.
Which might not end up in compile error, and could be hard to track down. Whew!
It can be quite nasty! ;-)
Thanx, Paul
(from mobile, might be QP encoded)
Quoted 109 lines · 2018/10/26 7:04、Akira Yokosawa <[email protected]> wrote:
Quoted 73 lines · Akira Yokosawa
Quoted 50 lines · Junchang Wang
Quoted 39 lines · Paul E. McKenney
Quoted 11 lines · Junchang Wang
Hi Akira,
Thanks for the mail. My understanding is that PPC uses LL/SC to emulate CAS by using a tiny loop. Unfortunately, the LL/SC loop itself could fail (due to, for example, context switches) even if *ptr equals to old. In such a case, a CAS instruction in actually should return a success. I think this is what the term "spurious fail" describes. Here is a reference:
http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_familyFirst, thank you both for your work on this! And yes, my
cmpxchg()code is clearly quite broken.Quoted 7 lines
It seems that
__atomic_compare_exchange_n()provides option "weak" for performance. I tested these two solutions and got the following results:1 4 8 16 32 64my patch (ns) 35 34 37 73 142 281
strong (ns) 39 39 41 79 158 313So strong is a bit slower, correct?
Quoted 9 lines
I tested the performance of
count_lim_atomicby varying the number of updaters (./count_lim_atomic N uperf) on a 8-core PPC server. The first row in the table is the result when my patch is used, and the second row is the result when the 4th argument of the function is set to false(0). It seems performance improves slightly if option "weak" is used. However, there is no performance boost as we expected. So your solution sounds good if safety is one major concern because option "weak" seems risky to me :-)Quoted 3 lines
Another interesting observation is that the performance of LL/SC-based CAS instruction deteriorates dramatically when the number of working threads exceeds the number of CPU cores.
Quoted 7 lines
If weak is faster, would it make sense to return (~o), that is, the bitwise complement of the expected arguement, when the weak
__atomic_compare_exchange_n()fails? This would get the improved performance (if I understand your results above) while correctly handling the strange (but possible) case where o==n.Does that make sense, or am I missing something?
Hi Paul and Akira,
Quoted 7 lines
Yes, the weak version is faster. The solution looks good. But when I tried to use the following patch
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) old = (o); \ (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1,You need a "\" at the end of the line above. (If it was not unintentionally wrapped.)
If it was wrapped by your mailer, which is troublesome in sending patches, please refer to:
https://www.kernel.org/doc/html/latest/process/email-clients.html.
Quoted 6 lines
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ (o) : (~o); \ })gcc complains of my use of complement symbol
Quoted 8 lines
Quoted 5 lines
../api.h:769:12: error: wrong type argument to bit-complement(o) : (~o); \ ^Any suggestions?
I don't see such error if I add the "\" mentioned above. Or do you use some strict error checking option of GCC?
Ah, I see that the error in compiling
CodeSamples/advsync/q.c.The call site is:
struct el *q_pop(struct queue *q)
{ struct el *p; struct el *pnext; for (;;) { do { p = q->head; pnext = p->next; if (pnext == NULL) return NULL; } while (cmpxchg(&q->head, p, pnext) != p); if (p != &q->dummy) return p; q_push(&q->dummy, q); if (q->head == &q->dummy) return NULL; } }In this case, p and pnext are pointers, hence the error. returning (o)+1 instead should be OK in this case.
Quoted 6 lines
But now, "
count_lim_atomic3 hog" says:FAIL: only reached -1829 rather than 0
on
x86_64. Hmm. No such error is observed on POWER8. Hmm...
I tried the same source with (o)+1 on another x86_64 host (Ubuntu 16.04).
count_lim_atomic hog test runs flawlessly.
The host I tried earlier was a bit old SB laptop. I’ll try there again later.
Thanks, Akira
Quoted 85 lines
The strong version works both on
x86_64and POWER8.Thanks, Akira
Quoted 79 lines
Thanks, Akira
Quoted 75 lines
Thanks,
--JunchangQuoted 70 lines
Thanx, Paul
Quoted 66 lines
Thanks,
--JunchangQuoted 61 lines · Akira Yokosawa
Quoted 14 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 31 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
---
CodeSamples/api-pthreads/api-gcc.h| 8 +++-----1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +3
-5@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \ })static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Quoted 117 lines · Akira Yokosawa
(from mobile, might be QP encoded)
Quoted 113 lines · 2018/10/26 7:04、Akira Yokosawa <[email protected]> wrote:
Quoted 73 lines · Akira Yokosawa
Quoted 50 lines · Junchang Wang
Quoted 39 lines · Paul E. McKenney
Quoted 11 lines · Junchang Wang
Hi Akira,
Thanks for the mail. My understanding is that PPC uses LL/SC to emulate CAS by using a tiny loop. Unfortunately, the LL/SC loop itself could fail (due to, for example, context switches) even if *ptr equals to old. In such a case, a CAS instruction in actually should return a success. I think this is what the term "spurious fail" describes. Here is a reference:
http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_familyFirst, thank you both for your work on this! And yes, my
cmpxchg()code is clearly quite broken.Quoted 7 lines
It seems that
__atomic_compare_exchange_n()provides option "weak" for performance. I tested these two solutions and got the following results:1 4 8 16 32 64my patch (ns) 35 34 37 73 142 281
strong (ns) 39 39 41 79 158 313So strong is a bit slower, correct?
Quoted 9 lines
I tested the performance of
count_lim_atomicby varying the number of updaters (./count_lim_atomic N uperf) on a 8-core PPC server. The first row in the table is the result when my patch is used, and the second row is the result when the 4th argument of the function is set to false(0). It seems performance improves slightly if option "weak" is used. However, there is no performance boost as we expected. So your solution sounds good if safety is one major concern because option "weak" seems risky to me :-)Quoted 3 lines
Another interesting observation is that the performance of LL/SC-based CAS instruction deteriorates dramatically when the number of working threads exceeds the number of CPU cores.
Quoted 7 lines
If weak is faster, would it make sense to return (~o), that is, the bitwise complement of the expected arguement, when the weak
__atomic_compare_exchange_n()fails? This would get the improved performance (if I understand your results above) while correctly handling the strange (but possible) case where o==n.Does that make sense, or am I missing something?
Hi Paul and Akira,
Quoted 7 lines
Yes, the weak version is faster. The solution looks good. But when I tried to use the following patch
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) old = (o); \ (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1,You need a "\" at the end of the line above. (If it was not unintentionally wrapped.)
If it was wrapped by your mailer, which is troublesome in sending patches, please refer to:
https://www.kernel.org/doc/html/latest/process/email-clients.html.
Quoted 6 lines
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ (o) : (~o); \ })gcc complains of my use of complement symbol
Quoted 8 lines
Quoted 5 lines
../api.h:769:12: error: wrong type argument to bit-complement(o) : (~o); \ ^Any suggestions?
I don't see such error if I add the "\" mentioned above. Or do you use some strict error checking option of GCC?
Ah, I see that the error in compiling
CodeSamples/advsync/q.c.The call site is:
struct el *q_pop(struct queue *q)
{ struct el *p; struct el *pnext; for (;;) { do { p = q->head; pnext = p->next; if (pnext == NULL) return NULL; } while (cmpxchg(&q->head, p, pnext) != p); if (p != &q->dummy) return p; q_push(&q->dummy, q); if (q->head == &q->dummy) return NULL; } }In this case, p and pnext are pointers, hence the error. returning (o)+1 instead should be OK in this case.
But now, "
count_lim_atomic3 hog" says:FAIL: only reached -1829 rather than 0
Quoted 8 lines
Quoted 2 lines
on
x86_64. Hmm. No such error is observed on POWER8. Hmm...I tried the same source with (o)+1 on another
x86_64host (Ubuntu 16.04).
count_lim_atomichog test runs flawlessly.The host I tried earlier was a bit old SB laptop. I’ll try there again later.
And I _did_ make a stupid typo there. I tried with "(o+1)", not "(o)+1". Apologies...
So all clear for Junchang's patch with Paul's minor tweak.
FWIW, diff of my version looks like the following:
CodeSamples/api-pthreads/api-gcc.h +2 -3
@@ -168,9 +168,8 @@ struct __xchg_dummy { ({ \ typeof(*ptr) _____actual = (o); \ \ - (void )__atomic_compare_exchange_n (ptr, (void *)&_____actual, (n),1 , \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ +__atomic_compare_exchange_n (ptr, (void *)&_____actual, (n),1 , \ + __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? (o) : (o)+1 ; \ })static __inline__int atomic_cmpxchg (atomic_t *v,int old,int new)
---
Thanks, Akira
Quoted 88 lines
Thanks, Akira
Quoted 85 lines
The strong version works both on
x86_64and POWER8.Thanks, Akira
Quoted 79 lines
Thanks, Akira
Quoted 75 lines
Thanks,
--JunchangQuoted 70 lines
Thanx, Paul
Quoted 66 lines
Thanks,
--JunchangQuoted 61 lines · Akira Yokosawa
Quoted 14 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 31 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
---
CodeSamples/api-pthreads/api-gcc.h| 8 +++-----1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +3
-5@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \ })static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Quoted 142 lines · Akira Yokosawa
Quoted 117 lines · Akira Yokosawa
(from mobile, might be QP encoded)
Quoted 113 lines · 2018/10/26 7:04、Akira Yokosawa <[email protected]> wrote:
Quoted 73 lines · Akira Yokosawa
Quoted 50 lines · Junchang Wang
Quoted 39 lines · Paul E. McKenney
Quoted 11 lines · Junchang Wang
Hi Akira,
Thanks for the mail. My understanding is that PPC uses LL/SC to emulate CAS by using a tiny loop. Unfortunately, the LL/SC loop itself could fail (due to, for example, context switches) even if *ptr equals to old. In such a case, a CAS instruction in actually should return a success. I think this is what the term "spurious fail" describes. Here is a reference:
http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_familyFirst, thank you both for your work on this! And yes, my
cmpxchg()code is clearly quite broken.Quoted 7 lines
It seems that
__atomic_compare_exchange_n()provides option "weak" for performance. I tested these two solutions and got the following results:1 4 8 16 32 64my patch (ns) 35 34 37 73 142 281
strong (ns) 39 39 41 79 158 313So strong is a bit slower, correct?
Quoted 9 lines
I tested the performance of
count_lim_atomicby varying the number of updaters (./count_lim_atomic N uperf) on a 8-core PPC server. The first row in the table is the result when my patch is used, and the second row is the result when the 4th argument of the function is set to false(0). It seems performance improves slightly if option "weak" is used. However, there is no performance boost as we expected. So your solution sounds good if safety is one major concern because option "weak" seems risky to me :-)Quoted 3 lines
Another interesting observation is that the performance of LL/SC-based CAS instruction deteriorates dramatically when the number of working threads exceeds the number of CPU cores.
Quoted 7 lines
If weak is faster, would it make sense to return (~o), that is, the bitwise complement of the expected arguement, when the weak
__atomic_compare_exchange_n()fails? This would get the improved performance (if I understand your results above) while correctly handling the strange (but possible) case where o==n.Does that make sense, or am I missing something?
Hi Paul and Akira,
Quoted 7 lines
Yes, the weak version is faster. The solution looks good. But when I tried to use the following patch
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) old = (o); \ (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1,You need a "\" at the end of the line above. (If it was not unintentionally wrapped.)
If it was wrapped by your mailer, which is troublesome in sending patches, please refer to:
https://www.kernel.org/doc/html/latest/process/email-clients.html.
Quoted 6 lines
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ (o) : (~o); \ })gcc complains of my use of complement symbol
Quoted 8 lines
Quoted 5 lines
../api.h:769:12: error: wrong type argument to bit-complement(o) : (~o); \ ^Any suggestions?
I don't see such error if I add the "\" mentioned above. Or do you use some strict error checking option of GCC?
Ah, I see that the error in compiling
CodeSamples/advsync/q.c.The call site is:
struct el *q_pop(struct queue *q)
{ struct el *p; struct el *pnext; for (;;) { do { p = q->head; pnext = p->next; if (pnext == NULL) return NULL; } while (cmpxchg(&q->head, p, pnext) != p); if (p != &q->dummy) return p; q_push(&q->dummy, q); if (q->head == &q->dummy) return NULL; } }In this case, p and pnext are pointers, hence the error. returning (o)+1 instead should be OK in this case.
But now, "
count_lim_atomic3 hog" says:FAIL: only reached -1829 rather than 0
Quoted 8 lines
Quoted 2 lines
on
x86_64. Hmm. No such error is observed on POWER8. Hmm...I tried the same source with (o)+1 on another
x86_64host (Ubuntu 16.04).
count_lim_atomichog test runs flawlessly.The host I tried earlier was a bit old SB laptop. I’ll try there again later.
And I _did_ make a stupid typo there. I tried with "(o+1)", not "(o)+1". Apologies...
So all clear for Junchang's patch with Paul's minor tweak.
FWIW, diff of my version looks like the following:
CodeSamples/api-pthreads/api-gcc.h +0
-0@@ -168,9 +168,8 @@ struct __xchg_dummy { ({ \ typeof(*ptr) _____actual = (o); \
CodeSamples/api-pthreads/api-gcc.h struct __xchg_dummy {
Quoted 10 lines
CodeSamples/api-pthreads/api-gcc.h +2
-4\ - (void )__atomic_compare_exchange_n (ptr, (void *)&_____actual, (n),1 , \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ +__atomic_compare_exchange_n (ptr, (void *)&_____actual, (n),1 , \ + __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ? (o) : (o)+1 ; \ })static __inline__int atomic_cmpxchg (atomic_t *v,int old,int new) ---
Hi Akira,
Thanks a lot. Yes, the patch works for my x86 laptop and servers. I have submitted the path in an independent thread.
Thanks,
--Junchang
Quoted 92 lines
Thanks, Akira
Quoted 88 lines
Thanks, Akira
Quoted 85 lines
The strong version works both on
x86_64and POWER8.Thanks, Akira
Quoted 79 lines
Thanks, Akira
Quoted 75 lines
Thanks,
--JunchangQuoted 70 lines
Thanx, Paul
Quoted 66 lines
Thanks,
--JunchangQuoted 61 lines · Akira Yokosawa
Quoted 14 lines · Junchang Wang
Hi Akira and Paul,
I checked the code today and the implementation of
cmpxchg()looks very suspicious to me; Currentcmpxchg()first executes function__atomic_compare_exchange_n, and then checks whether the value stored in field__actual(old) has been changed to decide if the CAS instruction has been successfully performed. However, I saw the *weak* field is set, which, as far as I know, means__atomic_compare_exchange_ncould fail even if the value of *ptr is equal to__actual(old). Unfortunately, current cmpxchg will treat this case as a success because the value of__actual(old)does not change.Thanks for looking into this!
I also suspected the use of "weak" semantics of
__atomic_compare_exchange_n(), but did not quite understand what "spurious fail" actually means. Your theory sounds plausible to me.I've suggested in a private email to Paul to modify the 4th argument to false(0) as a workaround, which would prevent such "spurious fail".
Both approaches looks good to me. I'd defer to Paul on the choice.
Thanks, Akira
Quoted 31 lines
This bug happens in both Power8 and ARMv8. It seems it affects architectures that use LL/SC to emulate CAS. Following patch helps solve this issue on my testbeds. Please take a look. Any thoughts?
---
CodeSamples/api-pthreads/api-gcc.h| 8 +++-----1 file changed, 3 insertions(+), 5 deletions(-)CodeSamples/api-pthreads/api-gcc.h +3
-5@@ -166,11 +166,9 @@ struct __xchg_dummy {#define cmpxchg (ptr, o, n) \ ({ \ - typeof(*ptr) _____actual = (o); \ - \ - (void)__atomic_compare_exchange_n(ptr, (void *)&_____actual, (n), 1, \ - __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \ - _____actual; \ + typeof(*ptr) old = (o); \ + (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ + (o) : (n); \ })static
__inline__intatomic_cmpxchg(atomic_t *v, int old, int new)
Quoted 60 lines · Junchang Wang
Quoted 38 lines · Paul E. McKenney
Quoted 9 lines · Junchang Wang
Hi Akira,
Thanks for the mail. My understanding is that PPC uses LL/SC to emulate CAS by using a tiny loop. Unfortunately, the LL/SC loop itself could fail (due to, for example, context switches) even if *ptr equals to old. In such a case, a CAS instruction in actually should return a success. I think this is what the term "spurious fail" describes. Here is a reference:
http://liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_familyFirst, thank you both for your work on this! And yes, my
cmpxchg()code is clearly quite broken.Quoted 7 lines
It seems that
__atomic_compare_exchange_n()provides option "weak" for performance. I tested these two solutions and got the following results:1 4 8 16 32 64my patch (ns) 35 34 37 73 142 281
strong (ns) 39 39 41 79 158 313So strong is a bit slower, correct?
Quoted 9 lines
I tested the performance of
count_lim_atomicby varying the number of updaters (./count_lim_atomic N uperf) on a 8-core PPC server. The first row in the table is the result when my patch is used, and the second row is the result when the 4th argument of the function is set to false(0). It seems performance improves slightly if option "weak" is used. However, there is no performance boost as we expected. So your solution sounds good if safety is one major concern because option "weak" seems risky to me :-)Quoted 3 lines
Another interesting observation is that the performance of LL/SC-based CAS instruction deteriorates dramatically when the number of working threads exceeds the number of CPU cores.
Quoted 7 lines
If weak is faster, would it make sense to return (~o), that is, the bitwise complement of the expected arguement, when the weak
__atomic_compare_exchange_n()fails? This would get the improved performance (if I understand your results above) while correctly handling the strange (but possible) case where o==n.Does that make sense, or am I missing something?
Hi Paul and Akira,
Yes, the weak version is faster. The solution looks good. But when I tried to use the following patch
#define
cmpxchg(ptr, o, n)\({ \ typeof(*ptr) old = (o); \ (__atomic_compare_exchange_n(ptr, (void *)&old, (n), 1, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))? \ (o) : (~o); \ })
Quoted 7 lines
gcc complains of my use of complement symbol
../api.h:769:12: error: wrong type argument to bit-complement(o) : (~o); \ ^Any suggestions?
You might need to do this for the macro argument: "(~(o))".
Another possibility is ((o) + 1), which would work for pointers as well as for integers.
Thanx, Paul