bit test and set (BTS) on a tbb atomic variable

Question

I want to do bitTestAndSet on a tbb atomic variable.

atomic.h from tbb does not seem to have any bit operations.

If I treat the tbb atomic variable as a normal pointer and do __sync_or_and_fetch gcc compiler doesn't allow that.

Is there a workaround for this?

Related question:

assembly intrinsic for bit test and set (BTS)

Answer 1

A compare_and_swap loop can be used, like this:

// Atomically perform i|=j. Return previous value of i.
int bitTestAndSet( tbb::atomic<int>& i, int j ) {
    int o = i;                  // Atomic read (o = "old value")
    while( (o|j)!=o ) {         // Loop exits if another thread sets the bits
        int k = o;
        o = i.compare_and_swap(k|j,k);
        if( o==k ) break;       // Successful swap
    }
    return o;
}

Note that if the while condition succeeds on the first try, there will be only an acquire fence, not a full fence. Whether that matters depends on context.

If there is risk of high contention, then some sort of backoff scheme should be be used in the loop. TBB uses a class atomic_backoff for contention management internally, but it's not currently part of the public TBB API.

There is a second way, if portability is not a concern and you are willing to exploit the undocumented fact that the layout of a tbb::atomic and T are the same on x86 platforms. In that case, just operate on the tbb::atomic using assembly code. The program below demonstrates this technique:

#include <tbb/tbb.h>
#include <cstdio>

inline int SetBit(int array[], int bit) {
    int x=1, y=0;
    asm("bts %2,%0\ncmovc %3,%1" : "+m" (*array), "+r"(y) : "r" (bit), "r"(x));
    return y;
}

tbb::atomic<int> Flags;
volatile int Result;

int main() {
    for( int i=0; i<16; ++i ) {
        int k = i*i%32;
        std::printf("bit at %2d was %d.  Flags=%8x\n", k, SetBit((int*)&Flags,k), +Flags);
    }
}