- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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;
}
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;
}
Link Copied
9 Replies
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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;
}
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?
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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;
}
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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");
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
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);
}
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
**********************************
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?
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
Reply
Topic Options
- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page