Skip to contentSkip to conversation

test_and_set_bit implementation

DISCUSSION Zoltan Menyhart 3 participants 11 messages Dec 12, 2006 – Dec 14, 2006

lore
Share & tools
lore
#0 lore raw

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

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

#2 lore raw
In reply to Zoltan Menyhart
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.

#3 lore raw
In reply to Zoltan Menyhart
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.

#4 lore raw
In reply to Zoltan Menyhart
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.

#5 lore raw
In reply to Zoltan Menyhart
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() 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

#6 lore raw
In reply to Zoltan Menyhart
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

#7 lore raw
In reply to Zoltan Menyhart
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

#8 lore raw
In reply to Zoltan Menyhart
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.

#9 lore raw
In reply to Zoltan Menyhart
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 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))
		;
Quoted 3 lines
Quoted 1 line

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

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

#10 lore raw
In reply to Zoltan Menyhart
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