Page 1 of 1
Atomic Exchange Implementation
Posted: Sat Jan 10, 2009 1:22 pm
by JohnnyTheDon
I'm working on an atomic exchange operation without locks, semaphores, etc.
From looking on the internet I'm fairly certain this is possible. However, I can't figure out how to do it properly.
My function is in the form atomicexchange(int* a,int* b); Any ideas?
Re: Atomic Exchange Implementation
Posted: Sat Jan 10, 2009 1:41 pm
by JohnnyTheDon
Okay, i think i have something that might work.
Code: Select all
SyncExchangeQ:
.start:
mov rax, qword [rdi]
mov rdx, qword [rsi]
.tryagain_rdi:
lock cmpxchg qword [rdi], rdx
jnz .tryagain_rdi
xchg rax, rdx
.tryagain_rsi
lock cmpxchg qword [rsi], rdx
jnz .tryagain_rsi
ret
It seems to work okay. Any problems?
Re: Atomic Exchange Implementation
Posted: Sat Jan 10, 2009 2:20 pm
by Love4Boobies
So what's wrong with:
Code: Select all
mov rax,qword [rdi]
mov rdx,qword [rsi]
mov [rdi],rdx
mov [rsi],rax
Re: Atomic Exchange Implementation
Posted: Sat Jan 10, 2009 2:42 pm
by Brendan
Hi,
JohnnyTheDon wrote:Okay, i think i have something that might work.
It seems to work okay. Any problems?
Sure - another CPU can read both values after you've written the new value to [rdi] but before you've written the new value to [rsi] (which means it's not atomic). For example:
Code: Select all
SyncExchangeQ:
.start:
mov rax, qword [rdi]
mov rdx, qword [rsi]
.tryagain_rdi:
lock cmpxchg qword [rdi], rdx
jnz .tryagain_rdi
xchg rax, rdx
;*** ANOTHER CPU READS BOTH [RDI] and [RSI] HERE ***
.tryagain_rsi
lock cmpxchg qword [rsi], rdx
jnz .tryagain_rsi
ret
Also, another CPU can modify the values, causing your code to corrupt the value that's moved to [rsi]. For example:
Code: Select all
SyncExchangeQ:
.start:
mov rax, qword [rdi]
mov rdx, qword [rsi]
.tryagain_rdi:
lock cmpxchg qword [rdi], rdx
jnz .tryagain_rdi
xchg rax, rdx
;*** ANOTHER CPU MODIFIES BOTH [RDI] and [RSI] HERE ***
.tryagain_rsi
lock cmpxchg qword [rsi], rdx
jnz .tryagain_rsi
ret
AFAIK the only way this can be done is:
Code: Select all
.retry:
mov rax, [rdi]
mov rdx, [rdi+8]
mov rcx, rax
mov rbx, rdx
lock cmpxchg16b [rdi]
jne .retry
Of course this has limitations - the qwords need to be next to each other in memory, and CMPXCHG16B isn't supported on some 64-bit CPUs. If the values were 32-bit then you could use CMPXCHG8B instead (which should be supported on all 64-bit CPUs).
Cheers,
Brendan
Re: Atomic Exchange Implementation
Posted: Sat Jan 10, 2009 2:47 pm
by Brendan
Hi,
Love4Boobies wrote:So what's wrong with:
That's not atomic at all:
Code: Select all
mov rax,qword [rdi]
;** Other CPUs modify [rsi] and [rdi] here ***
mov rdx,qword [rsi]
;** Other CPUs modify [rsi] and [rdi] here ***
mov [rdi],rdx
;** Other CPUs read or modify [rsi] and [rdi] here ***
mov [rsi],rax
;** Values at [rsi] and [rdi] not guaranteed to be in sync anymore ***
Cheers,
Brendan
Re: Atomic Exchange Implementation
Posted: Sat Jan 10, 2009 2:56 pm
by JohnnyTheDon
Okay, that makes sense. I just realized there isn't much of a use for this in my code, I can get away with
And just use a normal xchg instruction.
Re: Atomic Exchange Implementation
Posted: Sat Jan 10, 2009 6:04 pm
by Love4Boobies
I'm sorry, I was thinking of atomic in the sense of threads, not CPUs. Perhaps I should have noticed the LOCK prefix. Anyway, I've never actually written any code for multiple CPUs, nor HT/SMT and I had no clue that one CPU could modify the register of another. I thought that each had their own set of register and just had access to the same memory (at least for SMP).
Re: Atomic Exchange Implementation
Posted: Sat Jan 10, 2009 6:10 pm
by JohnnyTheDon
I thought that each had their own set of register and just had access to the same memory (at least for SMP).
They do have their own registers and access to the same memory. The problem isn't that registers are getting edited, the problem is that the memory values are getting edited.