CAS on multi-core

[softarts]

hi there,
the question is about CAS behaviour on multi-core system
I encounter this situation:
volatile listheader* next;

thread 1:
do{
addelement to the list
}while CAS(next,newval,oldval)

thread 2
do{
delete element from the list
}while CAS(next,newval,oldval)

unless the CAS successfully done,the 'next' won't be changed,right?but I can detect the 'next' sometimes changed to astranger value(the value seemsrelated to the other thread action.
i.e.
thread 2 is trying to set 'next' to 'A',then in thread 1do{sometimes can detect next='A'}

anyone can explain that?

CAS implementation:

inline int MP_compare_and_swap_full(unsigned long *mem,unsigned long newval,unsigned long oldval)
{

__typeof (*mem) ret;
__asm __volatile ("lock; cmpxchgl %2, %1"
: "=a" (ret), "=m" (*mem)
: "r" (newval), "m" (*mem), "0" (oldval));
return (int) ret;

}

[Lingfeng_C_Intel]

Quoting - softarts

hi there,
the question is about CAS behaviour on multi-core system
I encounter this situation:
volatile listheader* next;

thread 1:
do{
addelement to the list
}while CAS(next,newval,oldval)

thread 2
do{
delete element from the list
}while CAS(next,newval,oldval)

unless the CAS successfully done,the 'next' won't be changed,right?but I can detect the 'next' sometimes changed to astranger value(the value seemsrelated to the other thread action.
i.e.
thread 2 is trying to set 'next' to 'A',then in thread 1do{sometimes can detect next='A'}

anyone can explain that?

CAS implementation:

inline int MP_compare_and_swap_full(unsigned long *mem,unsigned long newval,unsigned long oldval)
{

__typeof (*mem) ret;
__asm __volatile ("lock; cmpxchgl %2, %1"
: "=a" (ret), "=m" (*mem)
: "r" (newval), "m" (*mem), "0" (oldval));
return (int) ret;

}

What's meaning of CAS?

[jimdempseyatthecove]

Whileenqueue to FIFO single linked list can be performed with CAS, dequeue must use DCAS with ABA counter or other means to protect against ABA problem. First hit on google

http://research.sun.com/scalable/pubs/SPAA04.pdf

Jim Dempsey

[jimdempseyatthecove]

Quoting - softarts

hi there,
the question is about CAS behaviour on multi-core system
I encounter this situation:
volatile listheader* next;

thread 1:
do{
addelement to the list
}while CAS(next,newval,oldval)

thread 2
do{
delete element from the list
}while CAS(next,newval,oldval)

unless the CAS successfully done,the 'next' won't be changed,right?but I can detect the 'next' sometimes changed to astranger value(the value seemsrelated to the other thread action.
i.e.
thread 2 is trying to set 'next' to 'A',then in thread 1do{sometimes can detect next='A'}

anyone can explain that?

CAS implementation:

inline int MP_compare_and_swap_full(unsigned long *mem,unsigned long newval,unsigned long oldval)
{

__typeof (*mem) ret;
__asm __volatile ("lock; cmpxchgl %2, %1"
: "=a" (ret), "=m" (*mem)
: "r" (newval), "m" (*mem), "0" (oldval));
return (int) ret;

}

Normal implementation of CAS should return either

true (success) or false (fail)

or

return the contents of memory regardless of success or fail

I'm not up on the gnu style of assembler, but it looks like you are returning the the value you expect to be in memory. (IOW wrong return value when CAS fails).

Jim Dempsey

[Dmitry_Vyukov]

Quoting - jimdempseyatthecove

Whileenqueue to FIFO single linked list can be performed with CAS, dequeue must use DCAS with ABA counter or other means to protect against ABA problem.

The same equally applies to LIFO lists. And since both producers and consumers access the same variable 'next' one can't use CAS for enqueue and DWCAS for dequeue:

Intel 64 and IA-32 Architectures Software Developer's Manual Volume
3A: System Programming Guide, Part 1

7.1.2.2 Software Controlled Bus Locking

Software should access semaphores (shared memory used for signalling
between multiple processors) using identical addresses *and operand lengths*.
For example, if one processor accesses a semaphore using a word access, other
processors should not access the semaphore using a byte access.

[Dmitry_Vyukov]

Try to use compiler intrinsics (_InterlockedCompareExchange()) instead of hand-coded assembly, at least that will give you confidence that there are no problems on that side.

As Jim said, you most likely hit ABA problem. You need to use DWCAS + persistent memory, or DWCAS + SEH/signal handling, or safe object lifetime management to fight ABA.

[Dmitry_Vyukov]

Quoting - softarts

inline int MP_compare_and_swap_full(unsigned long *mem,unsigned long newval,unsigned long oldval)
{

__typeof (*mem) ret;
__asm __volatile ("lock; cmpxchgl %2, %1"
: "=a" (ret), "=m" (*mem)
: "r" (newval), "m" (*mem), "0" (oldval));
return (int) ret;

}

You need to add "memory" to the list of clobbered registers in order to prevent undesirable reorderings on compiler level, "cc" would not be a bad thing too:

__asm __volatile ("lock; cmpxchgl %2, %1"
: "=a" (ret), "=m" (*mem)
: "r" (newval), "m" (*mem), "0" (oldval)
: "memory", "cc");

[softarts]

Quoting - Dmitriy Vyukov

Try to use compiler intrinsics (_InterlockedCompareExchange()) instead of hand-coded assembly, at least that will give you confidence that there are no problems on that side.

As Jim said, you most likely hit ABA problem. You need to use DWCAS + persistent memory, or DWCAS + SEH/signal handling, or safe object lifetime management to fight ABA.

on IA32 platform:

I allocone MemoryPoolper thread like this,ABA should not happen:

class MemoryPool
{
public:
void *alloc()
{
...
do{
oldhead=next;
assert(next!=this);//failedhere!!!!!
}
while(!CAS(&next,oldval,newval);
...
}
void free(void *mem)
{//enqueue
do{
}
while (!CAS(&next,oldval,newval);
assert(next!=this);
}
public:
volatile MemoryPool *next;//indicate the next free OBJ
xxx
};

//main entry:
void *alloc()
{
MemoryPool *pool=pthread_getspecifical(poolkey);//poolkey createdbefore;
void *mem=pool->alloc();
*(unsigned long*)mem=pool;
return (char*)mem+4;//I use the offset -4 to store the pool pointer;
}

void free(void*mem)
{
//get the pool pointervia access mem-4;
pool->free(mem-4);
}

[softarts]

**********************************
see these firstly,thank you!
**********************************




even that I put such assertion at free() I still can not prevent the "next==this" happening at alloc(),
class MemoryPool {

void* alloc()
{
do{
oldheader =(MemoryPoolV1*) next;
target = oldheader;
}
while(!CAS(&next,oldheader,(void*)target->next) );

assert(next!=this);//failed here
return target;
}

inline void free (volatile void *doomed)
{
assert(doomed!=this);
MemoryPoolV1 *head = (MemoryPoolV1*)(doomed);
MemoryPoolV1 *oldhead;
do
{
oldhead = (MemoryPoolV1*)next;
head->next = (MemoryPoolV1*)next;//seems this doesn't work!
}while (!CAS(&next,oldhead,head));
assert(next!=this);
}
};
i.e,when invoke free(),doomed=0x804e5e0
(gdb) x/64xw 0x804e5e0
0x804e5e0: 0x0804da48(the pool ptr I put here at alloc,to indicate which pool the ptr belongs to) 0x0804da48 0x03030303 0x03030303
0x804e5f0: 0x03030303 0x03030303 0x03030303 0x03030303
I expect when CAS successfully done, the 'next'=0x804e5e0,and next->next(that's 0x804e5e0) should point to the original next,but when I check this at the assertion failure
it is still 0x0804da48(pool itself),I guess that is why the 'next==this' will happen.

I am quite curious that whether it is related to persistent memory?

[Lingfeng_C_Intel]

Quoting - (Intel)

What's meaning of CAS?

CAS, I got some help and CAS means Compare And Swap, an atomic operation used for synchronization in parallel programming.

Thanks,
Wise