test_and_set_bit implementation
We have got a test_and_set_bit implementation as follows:
static __inline__ inttest_and_set_bit (int nr, volatile void *addr)
{
__u32 bit, old, new;
volatile __u32 *m;
m = (volatile __u32 *) addr + (nr >> 5);
bit = 1 << (nr & 31);
do {
old = *m;
new = old | bit;
} while (cmpxchg_acq(m, old, new) != old);
return (old & bit) != 0;
}Let's assume the bit test & set is already set, why is then the cmpxchg_acq() executed? Cannot we just return, e.g. like this?
do {
old = *m;
if (old & bit)
return 1;
new = old | bit;
} while (cmpxchg_acq(m, old, new) != old);Thanks,
Zoltán Menyhárt
Quoted 9 lines · Zoltan Menyhart
Let's assume the bit test & set is already set, why is then the
cmpxchg_acq()executed? Cannot we just return, e.g. like this?do { old = *m; if (old & bit) return 1; new = old | bit; } while (cmpxchg_acq(m, old, new) != old);
The original code and your rewrite both access memory twice in the loop. Why don't we do it with one memory reference per loop instead?
{
CMPXCHG_BUGCHECK_DECL
u32 *m = (u32 *)addr + (nr >> 5);
u32 bit = 1 << (nr & 31);
u32 old = *m;
while (!(old & bit)) {
u32 new = old | bit;
u32 prev = cmpxchg_acq(m, old, new);
CMPXCHG_BUGCHECK(m);
if (prev = old)
return 1;
old = prev;
}
return 0;
}Looking at the disassembly of grab_block() in fs/ext2/balloc.c, I don't see much difference. The ld4.acq turns into a regular ld4 (because 'm' is no longer tagged as volatile), and is hoisted out of the loop. Interestingly, gcc chooses to reorder the tests, and make the loop four bundles long instead of three, but will 'goto repeat' in two bundles instead of four. Using likely()/unlikely() doesn't persuade gcc to change the order of the two branches, so I assume it actually is better to do it this way.
Quoted 9 lines · Zoltan Menyhart
Let's assume the bit test & set is already set, why is then the
cmpxchg_acq()executed? Cannot we just return, e.g. like this?do { old = *m; if (old & bit) return 1; new = old | bit; } while (cmpxchg_acq(m, old, new) != old);
I think this will work. However, usually you execute bit test and test because the bit is not set and you want to set it. This change would optimize a rarely taken path. Probably not worth it.
Quoted 2 lines · Matthew Wilcox
The original code and your rewrite both access memory twice in the loop. Why don't we do it with one memory reference per loop instead?
Because the the cmpxchg usually succeeds. It is rare that we have to redo the loop.
Quoted 7 lines · Christoph Lameter
Quoted 2 lines · Matthew Wilcox
The original code and your rewrite both access memory twice in the loop. Why don't we do it with one memory reference per loop instead?
Because the the cmpxchg usually succeeds. It is rare that we have to redo the loop.
Even if the loop executes exactly once, we still win by an ld4 vs an ld4.acq. It can't be less expensive to do an ld4.acq than it is to do an ld4.
Quoted 22 lines · Matthew Wilcox
The original code and your rewrite both access memory twice in the loop. Why don't we do it with one memory reference per loop instead?
{ CMPXCHG_BUGCHECK_DECL u32 *m = (u32 *)addr + (nr >> 5); u32 bit = 1 << (nr & 31); u32 old = *m; while (!(old & bit)) { u32 new = old | bit; u32 prev = cmpxchg_acq(m, old, new); CMPXCHG_BUGCHECK(m); if (prev = old) return 1; old = prev; } return 0; }
Quoted 8 lines
Looking at the disassembly of
grab_block()infs/ext2/balloc.c, I don't see much difference. The ld4.acq turns into a regular ld4 (because 'm' is no longer tagged as volatile), and is hoisted out of the loop. Interestingly, gcc chooses to reorder the tests, and make the loop four bundles long instead of three, but will 'goto repeat' in two bundles instead of four. Using likely()/unlikely() doesn't persuade gcc to change the order of the two branches, so I assume it actually is better to do it this way.
I like this code with the following slight modifications:
- let's keep "m" as pointer to volatile
- let's keep on using "__u32" types
- not sure we need "new"
- return the old bit
volatile __u32 *m = (volatile __u32 *)addr + (nr >> 5);
__u32 bit = 1 << (nr & 31);
__u32 old = *m;
while (!(old & bit)) {
__u32 prev = cmpxchg_acq(m, old, old | bit);
CMPXCHG_BUGCHECK(m);
if (prev = old)
return 0;
old = prev;
}
return 1;It compiles to:
0: and r151,r32 6: mov r14=1 c: extr r32=r32,5,27;; 10: shladd r18=r32,2,r33;; 16: ld4.acq r16=[r18] 1c: shl r17=r14,r15;; 20: and r14=r17,r16;; 26: nop.m 0x0 2c: cmp4.eq p7,p6=0,r14 30: nop.b 0x0 36: nop.b 0x0 3c: (p06) br.cond.dpnt.few a0 <+0xa0> 40: nop.m 0x0 46: zxt4 r14=r16 4c: nop.b 0x0;; 50: mov.m ar.ccv=r14;; 56: nop.m 0x0 5c: or r14=r17,r16 60: nop.m 0x0;; 66: cmpxchg4.acq r14=[r18],r14,ar.ccv 6c: nop.i 0x0;; 70: cmp4.eq p7,p6=r14,r16 76: nop.f 0x0 7c: and r15=r17,r14 80: mov r16=r14 86: nop.f 0x0 8c: (p07) br.cond.dpnt.few b0 <+0xb0>;; 90: nop.m 0x0 96: cmp4.eq p7,p6=0,r15 9c: (p07) br.cond.dptk.few 40 <+0x40> a0: nop.m 0x0 a6: mov r8=1 ac: br.ret.sptk.many b0;; b0: nop.m 0x0 b6: mov r8=r0 bc: br.ret.sptk.many b0;;
It seems to be o.k., thanks.
Zoltán Menyhárt
Quoted 3 lines · Christoph Lameter
I think this will work. However, usually you execute bit test and test because the bit is not set and you want to set it. This change would optimize a rarely taken path. Probably not worth it.
How much is the probability that the bit is not set?
Adding a test can cost only a few cycles, say max 4.
For an atomic operation, you need to go out and snoop.
Let's have a look at e.g. the "bit_spin_lock()":
static inline void bit_spin_lock(int bitnum, unsigned long *addr)
{
preempt_disable();
while (test_and_set_bit(bitnum, addr)) {
while (test_bit(bitnum, addr)) {
preempt_enable();
cpu_relax();
preempt_disable();
}
}
__acquire(bitlock);
}By executing the atomic operation unconditionally, you kill the cache line all the other waiting processors looping at.
Thanks,
Zoltán Menyhárt
Quoted 2 lines · Zoltan Menyhart
I like this code with the following slight modifications:
- let's keep "m" as pointer to volatile
Why? What benefit is there to doing an ld4.acq instead of a plain ld4?
Quoted 1 line
- let's keep on using "
__u32" types
Why be so ugly?
Quoted 1 line
- not sure we need "new"
Good idea.
Quoted 1 line
- return the old bit
I don't understand what you mean here.
Quoted 56 lines
volatile __u32 *m = (volatile __u32 *)addr + (nr >> 5); __u32 bit = 1 << (nr & 31); __u32 old = *m; while (!(old & bit)) { __u32 prev = cmpxchg_acq(m, old, old | bit); CMPXCHG_BUGCHECK(m); if (prev = old) return 0; old = prev; } return 1;It compiles to:
0: and r151,r32 6: mov r14=1 c: extr r32=r32,5,27;; 10: shladd r18=r32,2,r33;; 16: ld4.acq r16=[r18] 1c: shl r17=r14,r15;; 20: and r14=r17,r16;; 26: nop.m 0x0 2c: cmp4.eq p7,p6=0,r14 30: nop.b 0x0 36: nop.b 0x0 3c: (p06) br.cond.dpnt.few a0 <+0xa0> 40: nop.m 0x0 46: zxt4 r14=r16 4c: nop.b 0x0;; 50: mov.m ar.ccv=r14;; 56: nop.m 0x0 5c: or r14=r17,r16 60: nop.m 0x0;; 66: cmpxchg4.acq r14=[r18],r14,ar.ccv 6c: nop.i 0x0;; 70: cmp4.eq p7,p6=r14,r16 76: nop.f 0x0 7c: and r15=r17,r14 80: mov r16=r14 86: nop.f 0x0 8c: (p07) br.cond.dpnt.few b0 <+0xb0>;; 90: nop.m 0x0 96: cmp4.eq p7,p6=0,r15 9c: (p07) br.cond.dptk.few 40 <+0x40> a0: nop.m 0x0 a6: mov r8=1 ac: br.ret.sptk.many b0;; b0: nop.m 0x0 b6: mov r8=r0 bc: br.ret.sptk.many b0;;It seems to be o.k., thanks.
Zolt?n Menyh?rt
Quoted 1 line · Zoltan Menyhart
How much is the probability that the bit is not set?
Depends on the load on the system. Typically very much near 100%
Quoted 1 line
Adding a test can cost only a few cycles, say max 4.
But it reduces the performance of the commonly taken code path.
Quoted 17 lines
For an atomic operation, you need to go out and snoop.
Let's have a look at e.g. the "
bit_spin_lock()":static inline void
bit_spin_lock(int bitnum, unsigned long *addr){ preempt_disable(); while (test_and_set_bit(bitnum, addr)) { while (test_bit(bitnum, addr)) { preempt_enable(); cpu_relax(); preempt_disable(); } } __acquire(bitlock); }
Quoted 2 lines
By executing the atomic operation unconditionally, you kill the cache line all the other waiting processors looping at.
But note also that we optimize the common case, the case that the test and set bit are successful. Only if it was not successful will we do non atomic loads. This is done to avoid cachelines bouncing while the lock is contended.
Quoted 6 lines · Matthew Wilcox
Quoted 2 lines · Zoltan Menyhart
I like this code with the following slight modifications:
- let's keep "m" as pointer to volatileWhy? What benefit is there to doing an ld4.acq instead of a plain ld4?
It is not about the ld4.acq, but the volatile storage class (= don't assume it wont be changed by someone else, do reload it each time).
Not using the volatile key word allows the compiler to optimize out the actual load in loops like:
while (test_and_set_bit(bitnum, addr)) ;
Quoted 3 lines
Quoted 1 line
- let's keep on using "
__u32" typesWhy be so ugly?
- It has been like that for a while, I got used to it :-)
- grep-ing for "__u32" gives less false positives that grep-ing for "u32"
Quoted 3 lines
Quoted 1 line
- return the old bit
I don't understand what you mean here.
In your code:
...
while (!(old & bit)) {
...
return 1;
...
}
return 0;You return the inverse of the old bit, while the orig. code says:
" * test_and_set_bit - Set a bit and return its old value"
Thanks.
Zoltán Menyhárt
Quoted 3 lines · Christoph Lameter
Quoted 1 line
How much is the probability that the bit is not set?
Depends on the load on the system. Typically very much near 100%
If you are right, why do we need "bit_spin_lock()" that much complicated?
while (test_and_set_bit(bitnum, addr)) {
while (test_bit(bitnum, addr)) {
preempt_enable();
cpu_relax();
preempt_disable();
}
} If "test_and_set_bit()" did not modify the lock while it's busy, a simpler solution would do:
while (test_and_set_bit(bitnum, addr)) {
preempt_enable();
cpu_relax();
preempt_disable();
} Quoted 3 lines
Quoted 1 line
Adding a test can cost only a few cycles, say max 4.
But it reduces the performance of the commonly taken code path.
...
Quoted 8 lines
Quoted 3 lines
By executing the atomic operation unconditionally, you kill the cache line all the other waiting processors looping at.
But note also that we optimize the common case, the case that the test and set bit are successful. Only if it was not successful will we do non atomic loads. This is done to avoid cachelines bouncing while the lock is contended.
I can accept these arguments for small, not too much busy systems.
As the snooping and the cache line bouncing costs increases quadratically with the system size...
Have you got some lock benchmarks to measure it?
Thanks,
Zoltán Menyhárt