Atomic Exchange Implementation

[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?

[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?

[Love4Boobies]

So what's wrong with:

Code: Select all

mov rax,qword [rdi]
mov rdx,qword [rsi]
mov [rdi],rdx
mov [rsi],rax

[Brendan]

Hi,

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

[Brendan]

Hi,

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

[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

Code: Select all

int atomicExchange(int* a, int b)

And just use a normal xchg instruction.

[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).

[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.