Serata di apertura

Operazioni atomiche

Una singola istruzione può sembrare un'azione indivisibile mentre non lo è affatto. Prendi l'aggiunta di cinque a un valore in memoria:

add qword [rel counter], 5

Sotto il cofano, il processore non ha un modo per sommare direttamente in memoria. Suddivide questa singola istruzione in tre passaggi più piccoli, chiamati micro-operazioni:

1. lettura del valore corrente dalla memoria;
2. modifica di questo valore in un registro, sommandogli cinque;
3. scrittura del risultato.

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

Questo è un pattern comune chiamato read-modify-write (RMW).

Nota che la lettura (o load) e la scrittura (o store) sono eventi separati: c'è quindi una finestra temporale tra l'una e l'altra. Di solito non ce ne accorgiamo perché su un singolo core ogni istruzione ha la garanzia di produrre il suo effetto per intero prima della successiva. Quella finestra è quindi invisibile e add si comporta come un'unica unità.

Tuttavia, le CPU moderne raramente hanno un solo core, e le applicazioni spesso girano su molti core contemporaneamente, senza alcun ordine tra loro. Con diversi core in esecuzione nello stesso istante, un altro core può leggere o scrivere counter dentro quella finestra, dopo il load di questo core e prima del suo store. Due thread caricano ciascuno lo stesso vecchio valore, ciascuno aggiunge cinque e ciascuno memorizza il proprio risultato. Sono avvenute due addizioni, ma il valore è avanzato solo di cinque. Un aggiornamento è andato perso in silenzio.

Questa è una data race, un problema comune nel codice multi-thread.

Non ogni valore è esposto in questo modo. Ogni thread ha i propri registri e il proprio stack, quindi un valore contenuto in un registro, o una variabile locale sullo stack di un thread, è esclusivo di quel thread e non può entrare in una data race. Solo la memoria condivisa tra i thread, come counter qui sopra, ha bisogno di protezione.

x86-64 offre una serie di istruzioni per risolvere questo problema, rendendo un'istruzione indivisibile. Questa si comporta come un'unica unità non solo per il core che la esegue, ma anche per ogni altro core. Un'operazione che resta compatta, che nessun altro core può dividere, si dice atomica.

Scambio atomico

L'istruzione xchg scambia due operandi. L'operando di destinazione diventa uguale al valore precedente dell'operando sorgente, mentre l'operando sorgente diventa uguale al valore precedente dell'operando di destinazione. Concettualmente, la si può pensare come due istruzioni mov che avvengono nello stesso momento.

Come al solito, la si può usare con due operandi registro oppure con un operando in memoria e uno in registro:

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

Quando viene usata con un operando in memoria, xchg è sempre atomica.

Il prefisso lock

Il modo più comune per rendere atomica un'istruzione in x86-64 è aggiungere il prefisso lock. Esso fonde la lettura, la modifica e la scrittura in un unico passaggio indivisibile. Questo significa che il core mantiene la memoria in esclusiva per tutto il processo, così nessun altro core può leggere o scrivere quella locazione nel frattempo.

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lock funziona solo quando la destinazione è in memoria, e solo su istruzioni che eseguono un read-modify-write su quella memoria:

1. operazioni aritmetiche, come add, sub, inc, dec, neg;
2. operazioni bit a bit, come and, or, xor, not;
3. le operazioni sui bit bts, btr, btc;
4. alcune altre istruzioni dedicate, come xadd e cmpxchg, descritte più avanti.

Scambio e somma

Un semplice lock add aggiorna la memoria ma butta via il vecchio valore. Spesso il vecchio valore è proprio quello che serve, per esempio per assegnare a ogni thread un numero di ticket distinto.

L'istruzione xadd (x sta per exchange) restituisce il valore precedente mentre somma. Scrive la somma nella destinazione e lascia il valore originale della destinazione nel registro sorgente.

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

Con il prefisso lock questa è una fetch-and-add atomica. Eseguita da molti thread sullo stesso contatore, ogni chiamata restituisce un vecchio valore diverso.

Come con lock add, il contatore finisce esattamente al numero di chiamate. A differenza di lock add, però, anche ogni valore intermedio viene restituito, uno a ciascun chiamante.

Confronto e scambio

xadd somma e xchg sovrascrive, ma nessuna delle due può far dipendere il nuovo valore da quello corrente e applicarlo solo se nulla è cambiato nel frattempo. È questo aggiornamento condizionale che offre cmpxchg, compare-and-exchange, la più generale di queste primitive.

cmpxchg dest, src usa rax come accumulatore implicito e lo confronta con dest:

• Se dest == rax, allora dest = src e ZF = 1.
• Se dest != rax, allora rax = dest e ZF = 0.

Nota che dest viene aggiornato solo quando è uguale al valore atteso, caricato in precedenza in rax. Questa uguaglianza garantisce che dest contenga ancora il valore da cui è stato calcolato quello nuovo, così un aggiornamento basato su una lettura obsoleta non viene mai applicato. Questo rende cmpxchg il mattone su cui costruire un aggiornamento atomico, noto anche come compare-and-swap (CAS):

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

Questo ciclo di retry è il cuore degli aggiornamenti lock-free. La finestra tra la lettura e il compare-and-exchange è esattamente il momento in cui un altro thread potrebbe intromettersi, e cmpxchg se ne accorge rifiutandosi di memorizzare un valore calcolato da una lettura obsoleta.

Ordinamento della memoria

Ogni operazione vista finora ha toccato una sola locazione. Quando i thread si coordinano attraverso più di una locazione, compare una nuova domanda: in quale ordine le scritture di un thread diventano visibili a un altro. Le regole che rispondono a questa domanda costituiscono l'ordinamento della memoria del processore.

Il concetto di codice senza rami ha introdotto l'idea che un core moderno non procede un'istruzione alla volta. Ne tiene molte in volo contemporaneamente e corre avanti dove può. Questo significa che una scrittura può diventare visibile agli altri core più tardi di quanto il programma lasci intendere, mentre le istruzioni successive sono già andate avanti.

x86-64 mantiene un ordinamento della memoria forte tra normali load e store, così che su ciascun core:

1. un load non viene mai riordinato dopo un load successivo;
2. uno store non viene mai riordinato dopo uno store successivo;
3. un load non viene mai riordinato dopo uno store successivo.

L'unico riordino possibile è uno store che sembra completarsi dopo un load successivo di un indirizzo diverso.

Un'istruzione con il prefisso lock, o una xchg con un operando in memoria, è una barriera completa: nulla sembra attraversarla in nessuna delle due direzioni. Ecco perché bastano a garantire l'ordinamento completo nella maggior parte delle situazioni.

Attesa in spin e pause

Le istruzioni che impostano un flag restituendo anche il suo stato precedente sono note come test-and-set. Possono essere usate come base di uno spinlock, garantendo a un core l'accesso esclusivo a una parte del codice.

Questo è l'algoritmo generale, usando l'istruzione xchg con un flag binario:

1. Il flag parte da 0.
2. Per acquisire il lock, un core scambia il valore del flag con 1.
3. Se il valore restituito è 1, significa che il lock è occupato da un altro core. Il core corrente allora aspetta e prova di nuovo ad acquisire il lock.
4. Se il valore restituito è 0, significa che il lock era libero. Ora xchg lo ha impostato a 1, e gli altri core aspetteranno finché questo core non lo rilascia.
5. Quando il core corrente ha finito di lavorare, aggiornare il flag a 0 rilascia il lock.

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

L'istruzione pause nel ciclo di attesa non cambia ciò che il codice calcola. Suggerisce al processore che si tratta di un'attesa attiva. La CPU può così ridurre il consumo di energia del thread in attesa e cedere il passo a un thread fratello che condivide lo stesso core. Un ciclo di spin senza pause è comunque corretto, solo dispendioso.

Quando il thread ha finito il suo lavoro, può rilasciare il lock con un semplice store di 0 usando mov. Non serve nulla più di un mov, perché su x86-64 i load e gli store non vengono mai riordinati dopo uno store successivo. Uno store che non supera mai gli accessi che lo precedono si dice che ha ordinamento di rilascio, e su x86 ogni store semplice lo possiede.