Home
Accesso / Registrazione
 di 

Introduzione alle memory barrier

Linux-Compilatori-Gcc e Memory Barrier

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

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

 

 

Scrivi un commento all'articolo esprimendo la tua opinione sul tema, chiedendo eventuali spiegazioni e/o approfondimenti e contribuendo allo sviluppo dell'argomento proposto. Verranno accettati solo commenti a tema con l'argomento dell'articolo stesso. Commenti NON a tema dovranno essere necessariamente inseriti nel Forum creando un "nuovo argomento di discussione". Per commentare devi accedere al Blog
ritratto di Piero Boccadoro

Confesso che ero un po' a digiuno su questo tema! Ottimo appr

Confesso che ero un po' a digiuno su questo tema!
Ottimo approfondimento!

ritratto di Mirko77

Mi ha molto interessato questo aspetto (o falla?) dei compilator

Mi ha molto interessato questo aspetto (o falla?) dei compilatori. Ma succede anche con i compilatori C per microcontrollori tipo Microchip Mplab e Atmel AVRStudio?

ritratto di Andrea Righi

Piu` il compilatore e` "semplice", cioe` minore e` il livello di

Piu` il compilatore e` "semplice", cioe` minore e` il livello di ottimizzazione che applica, e minore e` la probabilita` di incappare in tali inconvenienti. Onestamente non ho molta esperienza con i compilatori in questione, ma in genere quasi tutti mettono a disposizione la scelta del livello di ottimizzazione.

Anche il gcc ad esempio con -O0 (livello di ottimizzazione minimo, che e` il default) non rende necessarie la maggior parte delle memory barrier a compile time.

Lo stesso discorso vale per le architetture: se l'architettura non prevede l'esecuzione out-of-order delle istruzioni, e` single-core, etc. sicuramente non richiede istruzioni speciali per la sincronizzazione delle operazioni in memoria centrale.

Tuttavia in assenza di informazioni precise e` sempre bene tenere conto di queste problematiche e usare le memory barrier quando scriviamo codice lock-free. Oppure affidarci alle primitive di locking che le librerie e/o i built-in del compilatore ci mettono a disposizione, dato che esse hanno gia` al loro interno tutto quello che serve per garantire la coerenza del codice.

ritratto di Emanuele

Mi complimento ancora una volta con Andrea per la specificità de

Mi complimento ancora una volta con Andrea per la specificità dei suoi articoli, in grado di mettere in evidenza problematiche poco conosciute ma assolutamente rilevanti!

Detto questo però vorrei spezzare una lancia a favore della mia posizione sul confronto ASM Vs C. Ci sono molte cose che si possono fare semplicemente in assembler (basta organizzarsi con le librerie) su piattaforme ad 8, 16 o anche a 32bit quindi prima di usare linguaggi ad alto livello e bene meditare, e meditare bene.

In questi anni ho visto tanti programmi in Basic, Pascal o addirittura C++ su micro ad 8 bit con 3 livelli di stack ed un solo puntatore....

Inoltre l'assembler è sempre bene conoscerlo, proprio perché se c'è un problema è l'unica via di uscita!

ritratto di Emanuele

Porca miseria, lo sai che mi hai messo in testa un bel tarlo (no

Porca miseria, lo sai che mi hai messo in testa un bel tarlo (non solo tu ma anche Andrea con il suo Post ovviamente). Domani devo svolgere un attività che comprende il debug di un sorgente su piattaforma AVRstudio, appunto!

Stai sicuro che la prova la faccio anche col compilatore Atmel!! E poi come mi capita anche con i vari Microchip, Freescale etc...

ritratto di Andrea Righi

Come semplice test case puoi provare a compilare il primo esempi

Come semplice test case puoi provare a compilare il primo esempio (test.c) e dare un'occhiata all'assembly generato. Se l'ordine delle istruzioni e` rispettato probabilmente vuol dire che il compilatore che stai usando (con le relative opzioni di ottimizzazione) non prende troppe iniziative. :-)

ritratto di Antonimo

Totalmente sconosciute!!! Grazie per la dritta!

Totalmente sconosciute!!!
Grazie per la dritta!

ritratto di Emanuele

Ho compilato il codice di test.c con Atmel AvrStudio utilizzando

Ho compilato il codice di test.c con Atmel AvrStudio utilizzando il compilatore avr-gcc e questo è il risultato:

---- Test_memorybarrier.c -------------------------------------------------------------------------
2: void main() {
+0000005F: 93DF PUSH R29 Push register on stack
+00000060: 93CF PUSH R28 Push register on stack
+00000061: D000 RCALL PC+0x0001 Relative call subroutine
+00000062: D000 RCALL PC+0x0001 Relative call subroutine
+00000063: B7CD IN R28,0x3D In from I/O location
+00000064: B7DE IN R29,0x3E In from I/O location
6: a = b + 1;
+00000065: 8189 LDD R24,Y+1 Load indirect with displacement
+00000066: 819A LDD R25,Y+2 Load indirect with displacement
+00000067: 9601 ADIW R24,0x01 Add immediate to word
+00000068: 839C STD Y+4,R25 Store indirect with displacement
+00000069: 838B STD Y+3,R24 Store indirect with displacement
7: b = 0;
+0000006A: 821A STD Y+2,R1 Store indirect with displacement
+0000006B: 8219 STD Y+1,R1 Store indirect with displacement
10: }
+0000006C: 900F POP R0 Pop register from stack
+0000006D: 900F POP R0 Pop register from stack
+0000006E: 900F POP R0 Pop register from stack
+0000006F: 900F POP R0 Pop register from stack
+00000070: 91CF POP R28 Pop register from stack
+00000071: 91DF POP R29 Pop register from stack
+00000072: 9508 RET Subroutine return

Sembra tutto OK, infatti in assembler avviene prima la somma di 1 ad a e poi il clear di b

Anche se un po' difficile da interpretare ho verificato in debug con una watch window aperta su a e b

Assolutamente da notare la moltitudine di instruzioni assembler che vengono generate in un microcontroller ad 8 bit come ATMEGA128

 

 

Login   
 Twitter Facebook LinkedIn Youtube Google RSS

Chi è online

Ci sono attualmente 3 utenti e 38 visitatori collegati.

Ultimi Commenti