Quando parliamo di applicazioni multi-thread ci vengono subito in mente i concetti di locking, conosciuti praticamente da tutti i programmatori. Non tutti pero` hanno ben presente l'importanza e la natura delle memory barrier. Tali oggetti permettono di forzare il preciso ordine delle operazioni di lettura/scrittura che la CPU effettua da e verso la memoria centrale.

In questo articolo verranno illustrati tramite esempi pratici alcuni comportamenti inattesi che si possono manifestare omettendo l'uso delle memory barrier.

Memory barrier a compile-time

Come tutti sappiamo il compito del compilatore e` quello di tradurre codice da un linguaggio di alto livello piu` comprensibile per l'umano (esempio C/C++, etc.) al linguaggio macchina.

Durante il processo di traduzione il compilatore e` libero di prendere qualsiasi iniziativa a patto che il comportamento definito dal codice sorgente sia sempre rispettato. Tuttavia, pur rispettando questo vincolo, il compilatore si prende delle liberta` per cercare di generare codice piu` efficiente e attuare ottimizzazioni di varia natura.

Senza alcuna indicazione esplicita sui vincoli da rispettare nelle letture/scritture in memoria la regola generale usata dai compilatori e` la seguente:

[1] Garantire che il comportamento dei programmi *single-thread* non venga modificato.

Cerchiamo di vedere il risultato di tali ottimizzazioni tramite un semplice esempio pratico (test.c):

int a, b;

void foo(void)
{
	a = b + 1;
	b = 0;
}

Se proviamo a compilarlo con gcc, abilitando il livello di ottimizzazione 2 (-O2), e ne produciamo l'assembly equivalente (-S -masm=intel) possiamo vedere che la funzione "foo" viene tradotta in questo modo:

$ gcc -O2 -S -masm=intel test.c
$ cat test.s

	mov	eax, DWORD PTR b[rip]  # leggi b nel registro eax
	mov	DWORD PTR b[rip], 0    # b = 0
	add	eax, 1                 # aggiungi 1 al registro eax
	mov	DWORD PTR a[rip], eax  # a = b + 1

Le istruzioni "mov" rappresentano le letture/scritture in memoria. Anche chi non ha familiarita` con l'assembly x86 puo` notare chiaramente che la scrittura "a = b + 1" viene eseguita dopo la scrittura "b = 0", contrariamente a quanto specificato nel codice C sorgente.

In questo caso il comportamento del codice dal punto di vista single-thread non viene modificato (quindi la regola generale dei compilatori enunciata sopra [1] viene rispettata), ma l'ordine delle operazioni di lettura/scrittura in memoria e` diverso da quello che ha specificato il programmatore.

Ad esempio, se la nostra istruzione "a = b + 1" rappresentasse l'acquisizione di un lock e l'istruzione "b = 0" fosse l'istruzione da proteggere il compilatore avrebbe spostato l'acquisizione del lock _dopo_ la scrittura del dato protetto!

Quindi, quali sono gli strumenti che il programmatore puo` usare per forzare un preciso ordinamento delle operazioni in memoria? Risposta: le memory barrier.

(NOTA: questo ci fa intuire anche che i lock stessi internamente usano le memory barrier per garantire un comportamenteo coerente).

La prima memory barrier che prendiamo in analisi e` la memory barrier a compile-time. Il gcc permette di definire una memory barrier di questo tipo nel modo seguente:

int a, b;

void foo(void)
{
	a = b + 1;
	asm volatile ("" : : : "memory");
	b = 0;
}

In questo caso il codice generato dal compilatore diventa:

	mov	eax, DWORD PTR b[rip]  # leggi b nel registro eax
	add	eax, 1                 # aggiungi 1 a eax
	mov	DWORD PTR a[rip], eax  # a = b + 1
	mov	DWORD PTR b[rip], 0    # b = 0

Perfetto! Adesso anche l'ordine delle operazioni in memoria e` rispettato.
Di fatto la memory barrier non introduce nessuna istruzione aggiuntiva al codice macchina, ma vincola il compilatore a generare del codice dove tutte le letture/scritture in memoria specificate sopra la memory barrier sono eseguite prima delle letture/scritture specificate sotto la memory barrier.

Un caso d'uso pratico abbastanza semplice potrebbe essere il seguente:

#define memory_barrier()	asm volatile("" : : : "memory")

int data, data_is_ready;

/*
* Imposta data=x e setta data_is_ready=1 per notificare che il dato e` pronto.
*/
void send_message(int x)
{
	data = x;
	/*
	 * Vogliamo esser sicuri di aver scritto data=x in memoria prima di
	 * notificare che il dato e` pronto tramite data_is_ready.
	 */
	memory_barrier();
	data_is_ready = 1;
}

/*
* Ritorna il valore di data quando data_is_ready e` impostato.
*/
int recv_message(void)
{
	if (data_is_ready) {
		/*
		 * Vogliamo esser sicuri che data_is_ready sia impostato prima
		 * di leggere l'effettivo valore di "data" dalla memoria.
		 */
		memory_barrier();
		return data;
	}
	return -1;
}

Memory barrier a run-time

Purtroppo il problema del riordinamento delle letture/scritture in memoria non si limita al solo compilatore. Anche le CPU possono effettuare riordinamenti delle micro-istruzioni a livello macchina, per gli stessi identici motivi del compilatore: produrre codice piu` efficiente.

Ovviamente anche le CPU, come i compilatori, mettono a disposizione primitive per forzare un preciso ordinamento delle operazioni in memoria.

L'architettura Intel, ad esempio, mette a disposizione la micro-istruzione "mfence" per implementare una memory barrier architetturale (consultare http://download.intel.com/products/processor/manual/253667.pdf per approfondimenti).

Il nostro primo esempio dovrebbe quindi essere modificato come segue per avere garanzia che l'ordinamento delle letture/scritture in memoria sia rispettato anche dalla CPU:

int a, b;

void foo(void)
{
	a = b + 1;
	asm volatile ("mfence" : : : "memory");
	b = 0;
}

In questo caso abbiamo aggiunto al codice sia una memory barrier per il compilatore, sia una memory barrier per la CPU.

L'assembly della funzione "foo" in questo caso diventa il seguente:

	mov	eax, DWORD PTR b[rip]  # leggi b nel registro eax
	add	eax, 1                 # aggiungi 1 a eax
	mov	DWORD PTR a[rip], eax  # a = b + 1
	mfence                         # memory barrier per la CPU
	mov	DWORD PTR b[rip], 0    # b = 0

Purtroppo questo ha reso il nostro codice non portabile (mence viene riconosciuta solo su Intel), quindi per scrivere memory barrier totalmente generiche e piu` portabili dovremmo wrappare il tutto usando delle macro di preprocessore che rimpiazzano l'istruzione mfence nelle istruzioni equivalenti a seconda dell'architettura target usata per generare il codice oggetto.

Ma possiamo spingerci anche oltre. Alcune architetture introducono tipologie diverse di memory barrier, tipicamente tre tipi:
1) memory barrier completa
2) memory barrier per le letture
3) memory barrier per le scritture

Questo perche` l'utilizzo di una memory barrier completa (es. mfence) potrebbe rivelarsi troppo oneroso in certi casi e non strettamente necessario, ad esempio, quando vogliamo garantire l'ordinamento delle letture dalla memoria centrale e non le scritture o viceversa.

Sempre restando su Intel possiamo notare che l'architettura mappa le tre diverse tipologie di memory barrier sulle micro-istruzioni seguenti:
1) mfence: memory barrier completa
2) lfence: memory barrier per le letture
3) sfence: memory barrier per le scritture

A questo punto un'implementazione piu` efficiente per Intel del nostro pratico caso d'uso potrebbe essere la seguente:

#define memory_barrier()        asm volatile("mfence" : : : "memory")
#define read_memory_barrier()   asm volatile("lfence" : : : "memory")
#define write_memory_barrier()  asm volatile("sfence" : : : "memory")

int data, data_is_ready;

/*
* Imposta data=x e setta data_is_ready=1 per notificare che il dato e` pronto.
*/
void send_message(int x)
{
	data = x;
	/*
	 * Vogliamo esser sicuri di aver scritto data=x in memoria prima di
	 * notificare che il dato e` pronto tramite data_is_ready.
	 *
	 * NOTA: in questo caso ci interessa rispettare l'ordinamento delle
	 * scritture in memoria, non ci interessa l'ordine delle letture, per
	 * questo usiamo la write_memory_barrier.
	 */
	write_memory_barrier();
	data_is_ready = 1;
}

/*
* Ritorna il valore di data quando data_is_ready e` settato.
*/
int recv_message(void)
{
	if (data_is_ready) {
		/*
		 * Vogliamo esser sicuri che data_is_ready sia settato prima di
		 * leggere il valore di "data".
		 *
		 * NOTA: in questo caso ci interessa rispettare l'ordinamento delle
		 * letture in memoria, non ci interessa l'ordine delle
		 * eventuali scritture, per questo usiamo la
		 * read_memory_barrier.
		 */
		read_memory_barrier();
		return data;
	}
	return -1;
}

Conclusioni

In questo articolo abbiamo fatto una rapida panoramica delle varie tipologie di memory barrier e abbiamo cercato di mettere in evidenza la loro importanza nella programmazione in ambiti multi-thread.

Spesso il programmatore si limita ad usare sempre i lock per proteggere gli accessi alle strutture dati condivise da piu` thread. Se usati correttamente i lock garantiscono sempre la coerenza del loro comportamento (un interessante aspetto che possiamo intuire, e che non tutti conoscono, e` che le primitive di locking stesse usano le memory barrier al loro interno).

Certe volte, pero`, per ragioni di scalabilita`, ci troviamo di fronte a dover scrivere del codice lock-free. In questo caso l'uso di memory barrier diventa di fondamentale importanza per evitare di imbattersi in bug o problemi estremamente diffcili da tracciare e aggirare.

Riferimenti

- Memory Barriers: a Hardware View for Software Hackers:
http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.06.07c.pdf

- Intel(R) 64 and IA-32 Architecture Software Developer Manuals:
http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html

- Documentazione delle memory barrier nel kernel Linux:
http://lxr.linux.no/linux/Documentation/memory-barriers.txt

Ti potrebbe interessare anche:

Progetto di un misuratore di corrente elettrica basato sul sensore ad effetto Hall ACS712 – Parte 4

Progetto di un sistema hacker di intrusione al CAN-BUS di un veicolo con Arduino e la scheda CAN-BUS Shield V2

NanoBASIC: un “Nano Computer”

Articoli Correlati

Come velocizzare il tuo progetto utilizzando “build server farm”

Gcc e i sistemi embedded