test_and_set_bit implementation

test_and_set_bit implementation

[Zoltan Menyhart]

We have got a test_and_set_bit implementation as follows:

static __inline__ int
test_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

Re: test_and_set_bit implementation

[Matthew Wilcox]

On Tue, Dec 12, 2006 at 04:01:00PM +0100, Zoltan Menyhart wrote:
> 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.

Re: test_and_set_bit implementation

[Christoph Lameter]

On Tue, 12 Dec 2006, Zoltan Menyhart wrote:

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

Re: test_and_set_bit implementation

[Christoph Lameter]

On Tue, 12 Dec 2006, Matthew Wilcox wrote:

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

Re: test_and_set_bit implementation

[Matthew Wilcox]

On Tue, Dec 12, 2006 at 09:22:44AM -0800, Christoph Lameter wrote:
> On Tue, 12 Dec 2006, Matthew Wilcox wrote:
> 
> > 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.

Re: test_and_set_bit implementation

[Zoltan Menyhart]

Matthew Wilcox wrote:

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

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

Re: test_and_set_bit implementation

[Zoltan Menyhart]

Christoph Lameter wrote:

> 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

Re: test_and_set_bit implementation

[Matthew Wilcox]

On Wed, Dec 13, 2006 at 11:02:48AM +0100, Zoltan Menyhart wrote:
> 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?

> - let's keep on using "__u32" types

Why be so ugly?

> - not sure we need "new"

Good idea.

> - return the old bit

I don't understand what you mean here.

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

Re: test_and_set_bit implementation

[Christoph Lameter]

On Wed, 13 Dec 2006, Zoltan Menyhart wrote:

> How much is the probability that the bit is not set?

Depends on the load on the system. Typically very much near 100%

> Adding a test can cost only a few cycles, say max 4.

But it reduces the performance of the commonly taken code path.

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

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.

Re: test_and_set_bit implementation

[Zoltan Menyhart]

Matthew Wilcox wrote:
> On Wed, Dec 13, 2006 at 11:02:48AM +0100, Zoltan Menyhart wrote:
> 
>>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?

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))
		;


>>- let's keep on using "__u32" types
> 
> Why 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"
 
>>- 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

Re: test_and_set_bit implementation

[Zoltan Menyhart]

Christoph Lameter wrote:

>>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();
       } 

>>Adding a test can cost only a few cycles, say max 4.
> 
> But it reduces the performance of the commonly taken code path.
...
>>
>>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