lock cmpxchg fails to execute threads in core order

Question

The following 64-bit NASM code uses lock cmpxchg to take each core in core order, execute some code, then reset the core number variable using xchg so the next core can execute the code. The core number for each core is stored in rbx -- the four cores are numbered 0, 8, 16 and 24. The variable [spin_lock_core] starts at zero and when each core is finished it updates the core number by 8 at the final line xchg [spin_lock_core],rax.

Spin_lock:
xor rax,rax
lock cmpxchg [spin_lock_core],rbx
jnz Spin_lock

; Test
mov rbp,extra_test_array
mov [rbp+rbx],rbx

; Execute some code before looping out
mov rax,1234
mov rdx,23435
add rax,rbx
mov rcx,rax
;jmp label_899

mov rax,rbx
add rax,8
xchg [spin_lock_core],rax

But before the code reaches xchg [spin_lock_core],rax the first core loops out of the program (jmp label_899), which should cause the other threads to freeze because they would be waiting for the [spin_lock_core] var to be updated, which never happens. But instead all four cores are written to the output array extra_test_array, which is displayed on the terminal when the program exits. In other words, this fails to stop the cores until the core number is updated.

The full, minimal code is below (as minimal as NASM can be in this case). The code is written for a shared object, and it's reproducible if it gets an input array (as written it doesn't matter if the input array is int or float):

; Header Section
[BITS 64]

[default rel]

global Main_Entry_fn
extern pthread_create, pthread_join, pthread_exit, pthread_self,    sched_getcpu
global FreeMem_fn
extern malloc, realloc, free
extern sprintf

section .data align=16
X_ctr: dq 0
data_master_ptr: dq 0
initial_dynamic_length: dq 0
XMM_Stack: dq 0, 0, 0, 0, 0, 0, 0
ThreadID: dq 0
X_ptr: dq 0
X_length: dq 0
X: dq 0
collect_ptr: dq 0
collect_length: dq 0
collect_ctr: dq 0
even_squares_list_ptrs: dq 0, 0, 0, 0
even_squares_list_ctr: dq 0
even_squares_list_length: dq 0
Number_Of_Cores: dq 32
pthread_attr_t: dq 0
pthread_arg: dq 0
Join_Ret_Val: dq 0
tcounter: dq 0
sched_getcpu_array: times 4 dq 0
ThreadIDLocked: dq 0
spin_lock_core: dq 0
extra_test_array: dq 0

; __________

section .text

Init_Cores_fn:

; _____
; Create Threads

label_0:

mov rdi,ThreadID            ; ThreadCount
mov rsi,pthread_attr_t  ; Thread Attributes
mov rdx,Test_fn         ; Function Pointer
mov rcx,pthread_arg
call pthread_create wrt ..plt

mov rdi,[ThreadID]      ; id to wait on
mov rsi,Join_Ret_Val        ; return value
call pthread_join wrt ..plt

mov rax,[tcounter]
add rax,8
mov [tcounter],rax
mov rbx,[Number_Of_Cores]
cmp rax,rbx
jl label_0

; _____

jmp label_900 ; All threads return here, and exit

; ______________________________________

Test_fn:

; Get the core number
call sched_getcpu wrt ..plt
mov rbx,8 ; multiply by 8
mul rbx
push rax

pop rax
mov rbx,rax
push rax

Spin_lock:
lock cmpxchg [spin_lock_core],rbx
jnz Spin_lock

; Test
mov rbp,extra_test_array
mov [rbp+rbx],rbx

; Execute some code before looping out
mov rax,1234
mov rdx,23435
add rax,rbx
mov rcx,rax
jmp label_899

mov rax,rbx
add rax,8
xchg [spin_lock_core],rax

;__________

label_899:

pop rax

ret

; __________

label_900:

mov rdi,extra_test_array ;audit_array
mov rax,rdi

ret

;__________
;Free the memory

FreeMem_fn:

;The pointer is passed back in rcx (of course)

sub rsp,40
call free wrt ..plt
add rsp,40
ret

; __________
; Main Entry


Main_Entry_fn:
push rdi
push rbp
push rbx
push r15
xor r15,r15
push r14
xor r14,r14
push r13
xor r13,r13
push r12
xor r12,r12
push r11
xor r11,r11
push r10
xor r10,r10
push r9
xor r9,r9
push r8
xor r8,r8
movsd [XMM_Stack+0],xmm13
movsd [XMM_Stack+8],xmm12
movsd [XMM_Stack+16],xmm11
movsd [XMM_Stack+24],xmm15
movsd [XMM_Stack+32],xmm14
movsd [XMM_Stack+40],xmm10
mov [X_ptr],rdi
mov [data_master_ptr],rsi
; Now assign lengths
lea rdi,[data_master_ptr]
mov rbp,[rdi]
xor rcx,rcx
movsd xmm0,qword[rbp+rcx]
cvttsd2si rax,xmm0
mov [X_length],rax
add rcx,8

; __________
; Write variables to assigned registers

mov r15,0
lea rdi,[rel collect_ptr]
mov r14,qword[rdi]
mov r13,[collect_ctr]
mov r12,[collect_length]
lea rdi,[rel X_ptr]
mov r11,qword[rdi]
mov r10,[X_length]

; __________

call Init_Cores_fn

movsd xmm10,[XMM_Stack+0]
movsd xmm14,[XMM_Stack+8]
movsd xmm15,[XMM_Stack+16]
movsd xmm11,[XMM_Stack+24]
movsd xmm12,[XMM_Stack+32]
movsd xmm13,[XMM_Stack+40]
pop r8
pop r9
pop r10
pop r11
pop r12
pop r13
pop r14
pop r15
pop rbx
pop rbp
pop rdi
ret

The instruction "lock cmpxchg" should fail until the [spin_lock_core] variable is updated, but it doesn't do that.

Thanks for any help in understanding why lock cmpxchg doesn't prevent the cores after core zero from firing in this area of code.

UPDATE: other research shows that xor rax,rax is needed at the top of the Spin_lock: section. When I insert that line, it reads like this:

Spin_lock:
xor rax,rax
lock cmpxchg [spin_lock_core],rbx
jnz Spin_lock

With that change it freezes, as expected. But when I remove the line jmp label_899 it still freezes, but it shouldn't do that.

EDIT 122219:

Based on the comments on this question yesterday, I revised the spinlock code to (1) eliminate atomic operations in favor of faster mov and cmp instructions, (2) assign a unique memory location to each core, and (3) separate the memory locations by > 256 bytes to avoid memory on the same cache line.

Each core's memory location will be changed to 1 when the previous core is finished. When each core finishes, it sets its own memory location back to 0.

The code successfully executes core 0 IF I have all other cores loop out before the spinlock. When I let all four cores run through the spinlock, the program again hangs.

I've verified that each separate memory location is set to 1 when the previous core is finished.

Here's the updated spinlock section:

section .data
spin_lock_core: times 140 dq 0
spin_lock_core_offsets: dq 0,264,528,792

section .text

; Calculate the offset to spin_lock_core
mov rbp,spin_lock_core
mov rdi,spin_lock_core_offsets
mov rax,[rdi+rbx]
add rbp,rax

; ________

Spin_lock:
pause
cmp byte[rbp],1
jnz Spin_lock

xor rax,rax
mov [rbp],rax ; Set current memory location to zero

; Execute some code before looping out
mov rax,1234
mov rdx,23435
add rax,rdx
mov rcx,rax

; Loop out if this is the last core
mov rax,rbx
add rax,8
cmp rax,[Number_Of_Cores]
jge label_899

; Set next core to 1 by adding 264 to the base address
add rbp,264
mov rax,1
mov [rbp],rax

Why does this code still hang?

Answer 1

I solved this spinlock problem, but after Peter Cordes' comment below I see that it is not correct. I won't delete this answer because I hope it can lead to the solution.

I use lock cmpxchg [rbp+rbx],rbx, which assembles without error, but the NASM assembler should return a "invalid combination of operands" error because the source operand can only be rax, so it shouldn't assemble with any other register. I also note that the online resources (for example, https://www.felixcloutier.com/x86/cmpxchg) show the format as CMPXCHG r/m64,r64, but the source operand can't be any r64 -- it must be rax, as that entry goes on to say.

Without the "mov rax,rbx" line it works because on the first iteration the rax register is set to 0 which matches the memory location. On the second iteration it succeeds by default.

When I add "mov rax,rbx" -- which resets rax -- the program once again hangs. I would really appreciate any ideas on why this program should hang as written.

At the start of this block rbx is the core number:

section .data
spin_lock_core: times 4 dq 0

section .text

[ Code leading up to this spinlock section shown above ]

mov rbp,spin_lock_core

Spin_lock:
pause
mov rax,rbx
lock cmpxchg [rbp+rbx],rax
jnz Spin_lock

mov rax,rbx
add rax,8
cmp rax,[Number_Of_Cores]
jge spin_lock_out

xchg [rbp+rax],rax

spin_lock_out:

The differences from my original post are:

1. Each core spins on (and reads from) its own unique memory location.

2. I use the "pause" instruction on the spinlock.

3. Each unique memory location is updated in core order.

But it does not work when I include mov rax,rbx. Intuitively that should work, so I will really appreciate any ideas on why it doesn't in this case.

Answer 2

I don't think you should use cmpxchg for this at all. Try this:

Spin_lock:
pause
cmp [spin_lock_core],rbx
jnz Spin_lock

; Test
mov rbp,extra_test_array
mov [rbp+rbx],rbx

; Execute some code before looping out
mov rax,1234
mov rdx,23435
add rax,rbx
mov rcx,rax
;jmp label_899

lea rax,[rbx+8]
mov [spin_lock_core],rax