equivalente x86 per LWARX e STWCX

Question

Sto cercando un equivalente di LWARX e STWCX (come trovato sui processori PowerPC) o un modo per implementare funzionalità simili sulla piattaforma x86. Inoltre, dove sarebbe il posto migliore per scoprire cose del genere (vale a dire buoni articoli/siti web/forum per la programmazione di lock/wait-free).

---

Modifica
penso di aver bisogno di dare maggiori dettagli come viene ipotizzato che sto solo cercando un CAS (confrontare e swap) il funzionamento. Quello che sto cercando di fare è implementare un sistema di conteggio dei riferimenti senza vincoli con puntatori intelligenti a cui è possibile accedere e modificare da più thread. Fondamentalmente ho bisogno di un modo per implementare la seguente funzione su un processore x86.

int* IncrementAndRetrieve(int **ptr) 
{ 
    int val; 
    int *pval; 
    do 
    { 
    // fetch the pointer to the value 
    pval = *ptr; 

    // if its NULL, then just return NULL, the smart pointer 
    // will then become NULL as well 
    if(pval == NULL) 
     return NULL; 

    // Grab the reference count 
    val = lwarx(pval); 

    // make sure the pointer we grabbed the value from 
    // is still the same one referred to by 'ptr' 
    if(pval != *ptr) 
     continue; 

    // Increment the reference count via 'stwcx' if any other threads 
    // have done anything that could potentially break then it should 
    // fail and try again 
    } while(!stwcx(pval, val + 1)); 
    return pval; 
} 

ho davvero bisogno di qualcosa che imita LWARX e STWCX abbastanza accuratamente per tirare fuori questo (non riesco a trovare un modo per fare questo con l'CompareExchange, di scambio o di aggiungere funzioni che ho finora trovato per la x 86).

Grazie

Answer 1

Come ha detto Michael, quello che probabilmente stai cercando è l'istruzione cmpxchg.

È importante sottolineare che il metodo PPC per ottenere questo risultato è noto come Load Link/Store Conditional (LL/SC), mentre l'architettura x86 utilizza Compare And Swap (CAS). LL/SC ha una semantica più forte di CAS in quanto qualsiasi modifica al valore sull'indirizzo condizionato causerà il fallimento dell'archivio, anche se l'altra modifica sostituisce il valore con lo stesso valore su cui è stato condizionato il carico. CAS, d'altra parte, riuscirebbe in questo caso. Questo è noto come problema ABA (vedi il link CAS per maggiori informazioni).

Se avete bisogno la semantica più forte sul architettura x86, è possibile approssimare esso utilizzando il x86s istruzioni cmpxchg8b, o cmpxchg16b sotto x86_64 doppia larghezza confrontare-e-swap (DWCAS). Ciò consente di scambiare atomicamente due parole consecutivi "di dimensioni naturali" contemporaneamente, anziché solo quelle usuali. L'idea di base è che una delle due parole contiene il valore di interesse e l'altra contiene un "conteggio delle mutazioni" sempre crescente. Sebbene ciò non elimini tecnicamente il problema, la probabilità che il contatore delle mutazioni si sposti tra un tentativo e l'altro è talmente bassa che è un ragionevole sostituto per la maggior parte degli scopi.

Answer 2

x86 non supporta direttamente "concorrenza ottimistica", come PPC fa - piuttosto, il supporto di x86 per la concorrenza si basa su un "prefisso di blocco", vedi here. (Alcune cosiddette istruzioni "atomiche" come XCHG ottengono effettivamente la loro atomicità affermando intrinsecamente il prefisso LOCK, indipendentemente dal fatto che il programmatore del codice assembly abbia effettivamente codificato o meno). Non è esattamente "a prova di bomba", per dirla diplomaticamente (anzi, è piuttosto incline agli incidenti, direi ;-).

Answer 3

Probabilmente stai cercando la famiglia di istruzioni di cmpxchg.

È necessario precedere questi con un'istruzione di blocco per ottenere un comportamento equivalente.

Dai uno sguardo allo here per una rapida panoramica di ciò che è disponibile.

È probabile che finisce con qualcosa di simile a questo:

mov ecx,dword ptr [esp+4] 
mov edx,dword ptr [esp+8] 
mov eax,dword ptr [esp+12] 
lock cmpxchg dword ptr [ecx],edx 
ret 12 

si dovrebbe leggere this paper ...

Modifica

In risposta alla domanda aggiornato, sei cercando di fare qualcosa come il Boost shared_ptr? Se è così, dai un'occhiata a quel codice e ai file in quella directory: ti aiuteranno sicuramente a iniziare.

Answer 4

Quello che stai cercando di fare non funzionerà come ti aspetti. Quello che hai implementato sopra può essere fatto con la funzione InterlockedIncrement (funzione Win32; assembly: XADD).

Il motivo per cui il codice non esegue ciò che si pensa che faccia è che un altro thread può ancora modificare il valore tra la seconda lettura di * ptr e stwcx senza invalidare lo stwcx.

Answer 5

se si è su 64 bit e si limita a dire 1 TB di heap, è possibile impacchettare il contatore nei 24 bit inutilizzati. se hai puntatori allineati a parole sono disponibili anche i 5 bit inferiori.

int* IncrementAndRetrieve(int **ptr) 
{ 
    int val; 
    int *unpacked; 
    do 
    { 
    val = *ptr; 
    unpacked = unpack(val); 

    if(unpacked == NULL) 
     return NULL; 
    // pointer is on the bottom 
    } while(!cas(unpacked, val, val + 1)); 
    return unpacked; 
} 

Answer 6

Non so se LWARX e STWCX invalidare l'intera linea di cache, CAS e DCAS fanno. Il che significa che, a meno che non sia disposto a buttare via molta memoria (64 byte per ogni puntatore "bloccabile" indipendente) non si vedranno molti miglioramenti se si sta davvero spingendo il software in stress. I risultati migliori che ho visto fino ad ora sono stati quando le persone hanno consapevolmente archiviato 64b, pianificato le loro strutture attorno ad esso (imballando cose che non saranno oggetto di contesa), hanno mantenuto tutto allocato sui confini 64b e utilizzato barriere esplicite di lettura e scrittura dei dati. L'invalidazione della linea cache può costare circa da 20 a 100 cicli, rendendola un vero problema di perf perfection, quindi bloccare l'evitamento.

Inoltre, è necessario pianificare una diversa strategia di allocazione della memoria per gestire la perdita controllata (se è possibile partizionare il codice in "elaborazione richiesta" logica - una richiesta "perdite" e quindi rilasciare tutta la memoria alla rinfusa alla fine) o gestione di allocazione dati in modo che una struttura in conflitto non riceva mai la memoria realizzata da elementi della stessa struttura/raccolta (per impedire ABA). Alcuni di questi possono essere molto contro-intuitivi, ma è o quello o il prezzo per GC.