Hazard pointer e problema ABA

Nel codice lock-free con puntatori, un valore può essere A, cambiare in B e poi tornare ad A. Un CAS che confronta solo il valore non può rilevare che nel frattempo sia cambiato qualcosa.

Il thread 1 legge il puntatore A e si prepara a eseguire un CAS. Nel frattempo, il thread 2 elimina A, alloca un nuovo nodo che, per caso, riutilizza l'indirizzo di A e il CAS del thread 1 ha esito positivo in modo errato.

Una soluzione consiste nel memorizzare un contatore insieme al puntatore. Il valore combinato cambia a ogni operazione, rendendo rilevabile l'ABA.

I tag richiedono atomiche a doppia larghezza, ad esempio CMPXCHG16B su x86. Occupano più spazio e potrebbero non essere disponibili su tutte le piattaforme.

Il problema fondamentale è il seguente: come si può eliminare un nodo a cui altri thread potrebbero ancora accedere? Il codice lock-free non può usare un semplice delete.

Ogni thread pubblica il puntatore a cui sta accedendo in quel momento in un elenco degli hazard globale. Prima di recuperare la memoria, un thread esamina l'elenco degli hazard: se qualcuno sta usando il puntatore, rimanda l'eliminazione.

Per ogni accesso:

1. Legga il puntatore atomically
2. Lo pubblichi come hazard
3. Lo rilegga per verificare che non sia cambiato ed evitare una race condition
4. Lo utilizzi
5. Cancelli l'hazard

Quando un nodo non è più raggiungibile, lo aggiunga a una lista di ritiro specifica del thread. Esamini periodicamente tutti gli hazard: i nodi non presenti in alcun hazard possono essere eliminati in sicurezza.

Un'alternativa consiste nel dividere il tempo in epoche. Un nodo può essere eliminato quando tutti i thread sono avanzati oltre l'epoca in cui è stato ritirato. Questo approccio è usato in Crossbeam (Rust) e nelle strutture dati concorrenti.

Incrementi un contatore specifico del nodo durante la lettura e lo decrementi dopo l'uso. È semplice, ma più lento degli hazard: ogni operazione aggiunge incrementi e decrementi atomici.

L'ABA è un problema solo quando si dispone di una "free list" o si riutilizzano gli indirizzi di memoria. Con un recupero sicuro della memoria, tramite hazard o epoche, il problema spesso scompare.

Le strutture dati lock-free sono piene di insidie. Utilizzi implementazioni collaudate di Folly, Boost o Crossbeam (Rust). Sviluppi una propria implementazione solo per scopi didattici o per percorsi specifici in cui le prestazioni sono critiche, dopo aver eseguito misurazioni accurate.

ThreadSanitizer rileva le race condition, ma non tutti i problemi di correttezza del codice lock-free. Gli strumenti di verifica formale, come CDSChecker e Relacy, esplorano sistematicamente le possibili interleaving.

A che cosa si riferisce il problema ABA nella programmazione lock-free?

Il problema ABA colpisce il codice lock-free che riutilizza gli indirizzi di memoria. I puntatori con tag, gli Hazard Pointer e il recupero basato sulle epoche sono le soluzioni canoniche. Ottenere codice lock-free corretto è difficile: preferisca librerie collaudate alle implementazioni scritte a mano.