The ABA Problem

The ABA Problem

This example is an instance of a general problem called the ABA problem. The ABA problem is the situation where a thread is context switched off the virtual CPU when the program is in state A. While it is off-CPU, the system changes into a second state, B, before returning to state A. This state is different from the original state but looks identi-cal to the thread that is now switched back onto a virtual CPU. When the first thread returns to the CPU, it continues to act as if the program state had not changed, and this causes an error.

In the circular buffer problem described in the previous section, the first thread is taken off the virtual CPU while believing it has a pointer to a free slot. When it returns to CPU, it has a pointer to what it believes is the free slot, but it has no indication that the state of the rest of the system has changed.

A general solution to the ABA problem is to encode a version number with any stored data. In this example of the circular buffer, the data would be accompanied by this version number, and the version number would be incremented every time the circular buffer was traversed.

With this version number, the thread that was taken off-CPU would have to match both the version number and the data for it to successfully add or remove an element from the buffer.

Adding the version number has reduced but not eliminated the possibility that a thread might return to the CPU to find a match of both version number and data. However, the probability can be made so small as to be practically impossible.

For example, if the version number is held as a 4-byte integer, then there are more than 4 billion possible values. If the code traverses the circular buffer 1,000 times a sec-ond, then it would take about one and a half months before the version number was repeated. The race condition can occur only if the version number when a thread is context switched off the virtual CPU matches the version number when the thread is switched back onto the CPU. No thread would be context switched off the CPU for a month and a half, so the race condition will not occur.

The code in Listing 8.29 is a modified version of the circular buffer code that includes a version number for each element of the buffer. The version is incremented in the routine nextupdate() every time the counter wraps around the buffer.

This code uses a structure of two integers to hold the value to be stored and the ver-sion number. It is necessary to use an atomic operation to perform the store. Most hard-ware supports an 8-byte atomic operation, but a 16-byte atomic is rarely supported, so the code will work only for 32-bit values.

Listing 8.29   Using Version Numbers to Avoid the ABA Problem

union ABAvalue

{

long long llvalue;

struct element

{

int version; int value;

} nested;

};

union ABAvalue buffer[16];

int counter = 0;

void clearbuffer()

{

addhere = 0; removehere = 0;

for ( int i=0; i<16;i++ )

{

buffer[i].llvalue = 0;

}

}

int next( int current )

{

return ( current + 1 ) & 15;

}

int nextupdate( int current )

{

if ( current == 15 ) { counter++; } return ( current + 1 ) & 15 ;

}

The code shown in Listing 8.30 is the modified version of the routines to add and remove elements from the circular buffer. The compare and swap operation needs to work on 8-byte values; hence, the assembly for the compare and swap needs to be modi-fied, and the x86 code will work only when compiled to use 64-bit instruction set extensions.

Listing 8.30   Adding and Removing Elements from Buffer

#ifdef __sparc

long long CAS( volatile long long* addr, long long ov, long long nv)

{

asm volatile( "casx %1, %2, %0":

"=r"(nv):

"m"(*addr),"r"(ov),"0"(nv):

"memory" );

return nv;

}

#else

long long CAS( volatile long long * addr, long long ov, long long nv )

{

asm volatile( "lock; cmpxchg %2, %1": "=a"(ov): "m"(*addr),"r"(nv),"a"(ov): "memory" );

return ov;

}

#endif

void addtobuffer( int value )

{

int success = 0;

union ABAvalue current; while ( !success )

{

current = buffer[ next(addhere) ]; if ( current.nested.value == 0 )

{

union ABAvalue nextvalue; nextvalue.nested.version = counter; nextvalue.nested.value = value;

if ( CAS( &buffer[ next(addhere) ].llvalue,

current.llvalue,

nextvalue.llvalue )

== current.llvalue )

{

addhere = nextupdate(addhere);

success = 1;

}

}

}

}

int removefrombuffer()

{

union ABAvalue current; int success = 0;

int value;

while ( !success )

{

current = buffer[ next(removehere) ]; if ( current.nested.value != 0 )

{

value = current.nested.value;

union ABAvalue nextvalue;

nextvalue.nested.version = counter;

nextvalue.nested.value = 0;

if ( CAS( &buffer[ next(removehere)].llvalue,

current.llvalue,

nextvalue.llvalue )

== current.llvalue )

{

removehere = next(removehere); success = 1;

}

}

}

return value;

}

It should be apparent from the previous discussion that it is not trivial to use atomic operations to manage the addition and removal of elements from a circular buffer. The basic problem is that the atomic operation allows the atomic modification of the circular list but is a separate operation to update the shared pointer to the next element. These two operations would need to be somehow combined into a single atomic operation for the code to work correctly.