Operazioni atomiche in

Informazioni su Operazioni atomiche

Una singola istruzione può sembrare un'azione indivisibile, ma non lo è affatto. Prendiamo 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. leggere il valore corrente dalla memoria;
2. modificare questo valore in un registro, aggiungendovi cinque;
3. riscrivere il 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 è uno schema comune chiamato read-modify-write (RMW).

Nota che la lettura (o load) e la scrittura (o store) sono eventi separati, quindi tra loro c'è una finestra di tempo. 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 eseguono ciascuno il load dello stesso vecchio valore, vi aggiungono ciascuno cinque ed eseguono ciascuno lo store del proprio risultato. Sono avvenute due addizioni, ma il valore è avanzato solo di cinque. Un aggiornamento è andato perso in silenzio.

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

Non tutti i valori sono esposti 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ò andare incontro a una race. Solo la memoria condivisa dai 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ò spezzare, 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 di registro oppure con un operando in memoria e uno di 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 processore acquisisce un lock sulla locazione per tutta la durata, lo stesso meccanismo che il prefisso lock usa per altre istruzioni, descritto qui di seguito.

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

Su qualsiasi altra istruzione, come un semplice mov, il prefisso non è valido e il processore genera un fault di opcode non valido. Un load isolato o uno store isolato non richiedono alcun prefisso: un accesso allineato naturalmente è già atomico di per sé.

Operazioni atomiche sui bit

Tra le istruzioni che si possono bloccare, quelle di test sui bit si abbinano naturalmente allo spinlock descritto alla fine di questo documento. Ognuna di bts, btr e btc copia un bit scelto nel flag di carry e poi lo imposta, lo azzera o lo inverte. Con il prefisso lock, questo diventa un read-modify-write su un solo bit: il bit viene modificato in modo atomico, e CF riporta qual era il suo valore precedente.

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

Un set che trova il bit già impostato significa che un altro thread se n'è impossessato per primo. Questa è la versione a un solo bit della presa di possesso di un flag che xchg fa per un'intera word.

Scambio e addizione

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

L'istruzione xadd (la x sta per exchange) restituisce il valore precedente mentre esegue l'addizione. 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ò, viene restituito anche ogni valore intermedio, uno a ciascun chiamante.

La sorgente può essere un registro di uso generale qualsiasi, e la larghezza dell'operando va da un byte a un quadword. Aggiungendo un valore negativo, la stessa istruzione diventa una fetch-and-subtract.

Compare and exchange

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. Quell'aggiornamento condizionale è ciò che offre cmpxchg, compare-and-exchange, ed è 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.

L'accumulatore segue la dimensione dell'operando: al per un byte, poi ax, eax e rax per le forme più larghe.

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 con cui si costruisce 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 retry loop è 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 intervenire, e cmpxchg lo intercetta rifiutandosi di memorizzare un valore calcolato da una lettura obsoleta.

Vale la pena conoscere una sottigliezza. cmpxchg verifica che il valore sia uguale a quello letto, non che la locazione non sia mai stata toccata. Se un altro thread sposta il valore da A a B e poi di nuovo ad A dentro la finestra, lo scambio riesce comunque, anche se il mondo sotto è cambiato.

Per un semplice contatore è innocuo, dato che un conteggio uguale va altrettanto bene. Per un indirizzo di memoria in testa a una lista lock-free non lo è, perché lo stesso indirizzo ora può portare altrove. Questo è il problema ABA.

La soluzione abituale a questo problema abbina al valore una specie di «stamp», per esempio un contatore che non fa che crescere. Poiché lo stamp avanza soltanto, uno stamp corrispondente dimostra che la locazione non è stata toccata nel frattempo, non semplicemente che sembra immutata.

Perché però questo funzioni in un ambiente multi-thread, l'indirizzo di memoria e il suo stamp devono essere aggiornati insieme. Dato che in x86-64 un indirizzo di memoria è un qword intero, un cmpxchg non basta ad aggiornarlo e contemporaneamente aggiornare un altro valore.

Esiste un'istruzione a doppia larghezza chiamata cmpxchg16b che è semanticamente identica a cmpxchg ma lavora su 16 byte alla volta e può essere usata in quella situazione. Non ha un operando sorgente, usando invece rcx:rbx come valore di sostituzione. Il suo unico operando è una locazione di memoria allineata a 16 byte. Questa istruzione usa anche rdx:rax come accumulatore, invece del solo rax.

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 sono il memory ordering del processore.

Il concetto branchless-code ha introdotto l'idea che un core moderno non procede a passo lento 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 suggerisca, mentre le istruzioni successive sono già andate avanti.

x86-64 mantiene un strong memory ordering tra normali load e store, così che su ogni 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 è quello di uno store che sembra completarsi dopo un load successivo di un indirizzo diverso.

Un'istruzione con prefisso lock, o un 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.

Il meccanismo dietro l'unico riordino che sopravvive è lo store buffer. Per continuare a correre avanti, un core parcheggia ogni store in quel buffer e lascia che le istruzioni successive procedano prima che lo store raggiunga la memoria visibile agli altri core. Una scrittura seguita dalla lettura di una locazione diversa può quindi apparire fuori ordine: la scrittura può essere ancora nel buffer mentre la lettura successiva va avanti. Questo modello, in cui tutto è ordinato tranne quel varco tra scrittura e lettura, si chiama total store order.

Quel singolo varco basta a rompere un handshake store-then-check. Se due thread scrivono ciascuno il proprio flag e poi leggono quello dell'altro, entrambe le letture possono tornare con il valore non impostato, perché nessuno dei due store ha ancora lasciato il proprio store buffer. L'istruzione mfence chiude il varco svuotando lo store buffer: ogni scrittura che la precede diventa visibile prima di qualsiasi lettura che la segue.

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

Esistono anche due barriere più strette:

• sfence ordina le scritture tra loro e conta soprattutto con gli store streaming, non temporali;
• lfence ordina le letture.

Per i normali schemi atomici visti sopra, le istruzioni con prefisso lock portano già con sé l'ordinamento completo, quindi una barriera esplicita serve solo per un handshake costruito con normali store e load come quello qui sopra.

Queste garanzie hanno nomi che vanno oltre x86. Un'operazione ha ordinamento acquire quando nessun accesso successivo può apparire spostarsi prima di essa, e ordinamento release quando nessun accesso precedente può apparire spostarsi dopo di essa. Su x86 ogni load è un acquire, ogni store è un release, e un'istruzione con prefisso lock, o un xchg su memoria, è entrambe le cose insieme.

Lo spinning e pause

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

Questo è l'algoritmo complessivo, che usa 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 è detenuto da un altro core. Il core corrente allora aspetta e prova ad acquisire di nuovo il lock.
4. Se il valore restituito è 0, significa che il lock era libero. xchg ora l'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 con 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 questa è un'attesa in spinning. La CPU può così ridurre il consumo di energia del thread in attesa e cedere il passo a un thread gemello che condivide lo stesso core. Un ciclo di spinning senza pause è comunque corretto, solo sprecato.

Nota che in un test-and-set un'istruzione come xchg imposta sempre il flag, anche quando era già impostato. Questo significa che ottiene l'accesso esclusivo alla memoria a ogni spin, anche quando è probabile che il lock sia ancora detenuto.

Esiste una variante di questo algoritmo, nota come test-and-test-and-set, che prima testa (legge) il flag per controllare se è già impostato. Poi tenta il test-and-set (in questo caso lo xchg) solo quando il lock sembra libero:

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

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