Può x86 riordinare un negozio ristretto con un carico più ampio che lo contiene completamente?

Il Manuale dello sviluppatore del software per le architetture Intel® 64 e IA-32 dice:

8.2.3.4 I carichi possono essere riordinati con i depositi precedenti in posizioni diverse
Il modello di ordinamento della memoria Intel 64 consente di riordinare un carico con un negozio precedente in una posizione diversa. Tuttavia, i carichi non vengono riordinati con i negozi nella stessa posizione.

Che dire dei carichi che si sovrappongono parzialmente o completamente ai precedenti negozi, ma non hanno lo stesso indirizzo iniziale? (Vedi la fine di questo post per un caso specifico)


Supponiamo che il seguente codice simile a C:

// lock - pointer to an aligned int64 variable // threadNum - integer in the range 0..7 // volatiles here just to show direct r/w of the memory as it was suggested in the comments int TryLock(volatile INT64* lock, INT64 threadNum) { if (0 != *lock) return 0; // another thread already had the lock ((volatile INT8*)lock)[threadNum] = 1; // take the lock by setting our byte if (1LL << 8*threadNum != *lock) { // another thread set its byte between our 1st and 2nd check. unset ours ((volatile INT8*)lock)[threadNum] = 0; return 0; } return 1; } 

O il suo equivalente x64 asm:

 ; rcx - address of an aligned int64 variable ; rdx - integer in the range 0..7 TryLock PROC cmp qword ptr [rcx], 0 jne @fail mov r8, rdx mov rax, 8 mul rdx mov byte ptr [rcx+r8], 1 bts rdx, rax cmp qword ptr [rcx], rdx jz @success mov byte ptr [rcx+r8], 0 @fail: mov rax, 0 ret @success: mov rax, 1 ret 

Quindi supponiamo che TryLock sia eseguito contemporaneamente in due thread:

 INT64 lock = 0; void Thread_1() { TryLock(&lock, 1); } void Thread_5() { TryLock(&lock, 5); } 

La domanda:

Il ((INT8*)lock)[1] = 1; e ((INT8*)lock)[5] = 1; i negozi non si trovano nella stessa posizione del carico di lock 64 bit. Tuttavia, sono tutti completamente contenuti in quel carico, quindi “conta” come la stessa posizione? Sembra imansible che una CPU possa farlo.

Che dire ((INT8*)lock)[0] = 1 ? L’indirizzo del negozio è quindi uguale all’indirizzo del seguente carico. Queste operazioni sono “nella stessa posizione”, anche se il caso precedente non lo era?

ps per favore nota che la domanda non riguarda il codice C / Asm, riguarda il comportamento delle CPU x86.

Può x86 riordinare un negozio ristretto con un carico più ampio che lo contiene completamente?

Sì, x86 può riordinare un negozio ristretto con un carico più ampio che lo contiene completamente.

Ecco perché il tuo algoritmo di blocco è rotto, shared_value non è uguale a 800000:

  1. GCC 6.1.0 x86_64 – collegamento al codice assemblatore: https://godbolt.org/g/ZK9Wql

  2. Clang 3.8.0 x86_64 – link al codice assemblatore: https://godbolt.org/g/qn7XuJ

Vedi sotto l’esempio corretto.


La domanda:

Il blocco ((INT8 *)) [1] = 1; e ((INT8 *) lock) [5] = 1; i negozi non si trovano nella stessa posizione del carico di blocco a 64 bit. Tuttavia, sono tutti completamente contenuti in quel carico, quindi “conta” come la stessa posizione?

No, non è così.

Il Manuale dello sviluppatore del software per le architetture Intel® 64 e IA-32 dice:

8.2.3.4 I carichi possono essere riordinati con i depositi precedenti in posizioni diverse Il modello di ordinamento della memoria Intel 64 consente di riordinare un carico con un negozio precedente in una posizione diversa. Tuttavia, i carichi non vengono riordinati con i negozi nella stessa posizione.

Questa è una regola semplificata per il caso in cui lo STORE e LOAD della stessa dimensione.

Ma una regola generale è che la scrittura nella memoria viene ritardata per un certo tempo e STORE (indirizzo + valore) accodato allo Store Buffer per attendere la cache-line in stato esclusivo (E) – quando questa linea cache sarà invalidata ( I) nella cache di altri core della CPU. Ma puoi usare l’operazione MFENCE (o qualsiasi operazione con il prefisso [LOCK] ) per forzare l’attesa fino a quando la scrittura è terminata, e tutte le seguenti istruzioni possono essere fatte solo dopo che lo Store Buffer sarà stato cancellato, e STORE sarà visibile a tutti CPU-core.

Informazioni sul riordino di due righe:

 ((volatile INT8*)lock)[threadNum] = 1; // STORE if (1LL < < 8*threadNum != *lock) // LOAD 
  • Se la dimensione STORE e LOAD è uguale, allora LOAD CPU-Core do (Store-forwarding) cerca in Store-Buffer e vede tutti i dati richiesti - è ansible ottenere tutti i dati effettivi adesso prima che STORE sia stato fatto

  • Se le dimensioni STORE e LOAD non sono uguali, STORE (1 Byte) e LOAD (8 Byte), allora anche se LOAD CPU-Core effettua la ricerca in Store-Buffer, allora vede solo 1/8 dei dati richiesti - non puoi ottenere tutti i dati effettivi adesso prima che STORE sia stato fatto. Qui potrebbero essere 2 varianti di azioni della CPU:

    1. case-1: CPU-Core carica altri dati dalla linea di cache che in stato condiviso (S) e si sovrappone a 1 byte dal buffer di archivio, ma lo STORE rimane ancora nel buffer di archivio e attende il ricevimento di uno stato esclusivo ( E) cache line per modificarlo - cioè CPU-Core legge i dati prima che STORE sia stato eseguito - nel tuo esempio è data-races (errore). STORE-LOAD riordinato a LOAD-STORE in tutto il mondo visibile. - Questo è esattamente ciò che accade su x86_64

    2. caso-2: CPU-Core attende quando lo Store-Buffer verrà svuotato, STORE ha atteso uno stato esclusivo (E) della linea cache e STORE è stato fatto, quindi CPU-Core carica tutti i dati richiesti dalla cache-line. STORE-LOAD non è riordinato a livello globale visibile. Ma questo è lo stesso come se si usasse il MFENCE .

In conclusione, devi usare MFENCE dopo STORE in ogni caso:

  1. Risolve completamente il problema nel caso-1.
  2. Non avrà alcun effetto sul comportamento e le prestazioni nel caso-2. Il MFENCE esplicito per lo Store-Buffer vuoto terminerà immediatamente.

L'esempio corretto su C e x86_64 asm:

MFENCE CPU-Core ad agire come nel caso-2 usando MFENCE , di conseguenza non c'è il riordino di StoreLoad

Nota: xchgb ha sempre il prefisso LOCK , quindi di solito non è scritto in asm o indicato tra parentesi.

Tutti gli altri compilatori possono essere selezionati manualmente sui link sopra: PowerPC, ARM, ARM64, MIPS, MIPS64, AVR.

C-code - dovrebbe usare la coerenza sequenziale per il primo STORE e il successivo LOAD:

 #ifdef __cplusplus #include  using namespace std; #else #include  #endif // lock - pointer to an aligned int64 variable // threadNum - integer in the range 0..7 // volatiles here just to show direct r/w of the memory as it was suggested in the comments int TryLock(volatile uint64_t* lock, uint64_t threadNum) { //if (0 != *lock) if (0 != atomic_load_explicit((atomic_uint_least64_t*)lock, memory_order_acquire)) return 0; // another thread already had the lock //((volatile uint8_t*)lock)[threadNum] = 1; // take the lock by setting our byte uint8_t* current_lock = ((uint8_t*)lock) + threadNum; atomic_store_explicit((atomic_uint_least8_t*)current_lock, (uint8_t)1, memory_order_seq_cst); //if (1LL < < 8*threadNum != *lock) // You already know that this flag is set and should not have to check it. if ( 0 != ( (~(1LL << 8*threadNum)) & atomic_load_explicit((atomic_uint_least64_t*)lock, memory_order_seq_cst) )) { // another thread set its byte between our 1st and 2nd check. unset ours //((volatile uint8_t*)lock)[threadNum] = 0; atomic_store_explicit((atomic_uint_least8_t*)current_lock, (uint8_t)0, memory_order_release); return 0; } return 1; } 

GCC 6.1.0 - x86_64 asm-code - dovrebbe usare MFENCE per il primo STORE:

 TryLock(unsigned long volatile*, unsigned long): movq (%rdi), %rdx xorl %eax, %eax testq %rdx, %rdx je .L7 .L1: rep ret .L7: leaq (%rdi,%rsi), %r8 leaq 0(,%rsi,8), %rcx movq $-2, %rax movb $1, (%r8) rolq %cl, %rax mfence movq (%rdi), %rdi movq %rax, %rdx movl $1, %eax testq %rdi, %rdx je .L1 movb $0, (%r8) xorl %eax, %eax ret 

Esempio completo di come funziona: http://coliru.stacked-crooked.com/a/65e3002909d8beae

 shared_value = 800000 

Cosa succederà se non usi MFENCE - Data-Races

Esiste un riordino StoreLoad come nel caso sopra descritto 1 (cioè se non si usa la coerenza sequenziale per STORE) - asm: https://godbolt.org/g/p3j9fR

Ho cambiato la barriera di memoria per STORE da memory_order_seq_cst a memory_order_release , rimuove MFENCE - e ora ci sono date-race - shared_value non è uguale a 800000.

inserisci la descrizione dell'immagine qui

Può mov byte [rcx+r8], 1 riordino con cmp qword [rcx], rdx carico cmp qword [rcx], rdx che lo segue? Questo è il lock[threadNum]=1 store e il seguente carico per assicurarsi che nessun altro abbia scritto un byte.

Il carico deve restituire i dati che includono lo store, poiché il thread in esecuzione osserva sempre le proprie azioni da eseguire nell’ordine di programma. (Questo è vero anche con gli ISA debolmente ordinati).


Si scopre che questa idea di blocco esatta è stata proposta in precedenza (per il kernel Linux), e Linus Torvalds ha spiegato che x86 permette davvero questo tipo di riordino

Nonostante il termine “errore di inoltro del negozio o stallo” , non significa che i dati devono impegnarsi in cache prima che il carico possa leggerlo. In realtà può essere letto dal buffer del negozio mentre la linea della cache è ancora nello stato S ( MESI ). (E su core Atom in ordine, non si ottiene nemmeno una stalla di inoltro del negozio).

L’hardware reale funziona in questo modo (come mostrano i test di Alex): la CPU unirà i dati da L1D con i dati dal buffer del negozio, senza commettere il negozio su L1D.

Questo di per sé non sta riordinando ancora 1 (il carico vede i dati del negozio, e sono adiacenti nell’ordine globale), ma lascia la porta aperta per il riordino. La linea della cache può essere invalidata da un altro core dopo il caricamento, ma prima che il negozio effettui il commit. Un negozio da un altro core può diventare visibile a livello globale dopo il nostro carico, ma prima del nostro negozio.

Quindi il carico include dati dal nostro negozio, ma non dall’altro negozio da un’altra CPU. L’altra CPU può vedere lo stesso effetto per il suo carico, e quindi entrambi i thread entrano nella sezione critica.


1 (Questo è il punto che stavo facendo nei commenti sulla risposta di Alex . Se x86 non ha permesso questo riordino, le CPU potrebbero ancora fare l’inoltro del negozio speculativamente prima che lo store diventi visibile a livello globale, e abbatterlo se un’altra CPU ha invalidato la cache linea prima che il negozio si impegnasse: quella parte della risposta di Alex non dimostrava che x86 funzionasse nel modo in cui funziona, solo test sperimentali e ragionamenti accurati sull’algoritmo di blocco ci hanno dato questo).

Se x86 non ha consentito questo riordino, una coppia di ricaricamento store / parzialmente sovrapposta funzionerebbe come un MFENCE: i carichi precedenti non possono diventare globalmente visibili prima del carico, e i negozi precedenti non possono diventare globalmente visibili prima del negozio. Il carico deve diventare globalmente visibile prima di qualsiasi carico o magazzino successivo e impedirebbe anche il ritardo del negozio.

Dato questo ragionamento, non è del tutto ovvio perché i negozi perfettamente sovrapposti non equivalgano a un MFENCE. Forse lo sono davvero, e x86 riesce a fare lo spill / reload o arg-passing sullo stack velocemente con un’esecuzione speculativa!


Lo schema di blocco:

Sembra che TryLock possa fallire per entrambi / tutti i chiamanti: tutti lo vedono inizialmente zero, scrivono tutti i loro byte, quindi tutti vedono almeno due byte diversi da zero ciascuno. Questo non è l’ideale per serrature pesantemente contese, rispetto all’utilizzo di un’istruzione lock ed. C’è un meccanismo di arbitraggio hardware per gestire conflitti in lock ed insns. (TODO: trovare il post sul forum di Intel in cui un ingegnere Intel ha pubblicato questo messaggio in risposta a un altro argomento di loop del ciclo di riconciliazione tra software ed istruzione, IIRC.)

La scrittura narrow / wide-read attiverà sempre uno stallo di forwarding del negozio sull’hardware x86 moderno. Penso che questo significhi solo che il risultato del carico non è pronto per diversi cicli, non quella esecuzione di altre bancarelle di istruzioni (almeno non in un progetto di OOO).

In un blocco leggermente conteso che viene usato frequentemente, il ramo sarà correttamente previsto per prendere il percorso no-conflict. L’esecuzione speculativa su quel percorso fino al completamento del carico e il ritiro del ramo non dovrebbe bloccarsi, perché le stalle di inoltro del magazzino non sono abbastanza lunghe da riempire il ROB.

  • SnB: ~ 12 cicli più lunghi rispetto a quando funziona il forwarding del negozio (~ 5c)
  • HSW: ~ 10c più lungo
  • SKL: ~ 11c più lungo di quando funziona il forwarding del negozio (4c per operandi 32 e 64 bit, che è 1c in meno delle CPU precedenti)
  • AMD K8 / K10: Agner Fog non dà un numero.
  • Famiglia AMD Bulldozer: 25-26c (Steamroller)

  • Atom: “A differenza della maggior parte degli altri processori, l’Atom può fare l’inoltro del negozio anche se l’operando letto è più grande del precedente operando di scrittura o allineato in modo diverso”, e c’è solo una latenza 1c. Non riesce solo quando si attraversa un limite della linea cache.

  • Silvermont: ~ 5c extra (base: 7c)
  • AMD Bobcat / Jaguar: 4-11c extra (base: 8c / 3c)

Quindi, se l’intero schema di blocco funziona, potrebbe andare bene per serrature leggermente contese.

Penso che potresti trasformarlo in un blocco per più lettori / scrittore singolo utilizzando il bit 1 in ogni byte per i lettori e il bit 2 per gli scrittori. TryLock_reader ignorerebbe i bit del lettore in altri byte. TryLock_writer funzionerebbe come l’originale, richiedendo uno zero in tutti i bit in altri byte.


A proposito, per la memoria che ordina roba in generale, il blog di Jeff Preshing è eccellente .