È possibile memorizzare puntatori nella memoria condivisa senza utilizzare offset?

Question

Quando si utilizza la memoria condivisa, ciascun processo può eseguire la divisione della regione condivisa in un'area diversa del rispettivo spazio indirizzo. Ciò significa che quando si memorizzano i puntatori all'interno della regione condivisa, è necessario store them as offsets dell'avvio dell'area condivisa. Sfortunatamente, questo complica l'uso di istruzioni atomiche (ad esempio se stai cercando di scrivere un lock free algorithm). Ad esempio, supponiamo di avere un gruppo di nodi con riferimenti di riferimento nella memoria condivisa, creati da un singolo autore. Periodicamente, lo scrittore aggiorna periodicamente un puntatore "p" per puntare a un nodo valido con conteggio di riferimento positivo. I lettori vogliono scrivere atomicamente su "p" perché punta all'inizio di un nodo (una struttura) il cui primo elemento è un conteggio di riferimento. Poiché p punta sempre a un nodo valido, l'incremento del conteggio ref è sicuro e rende sicuro il dereferenziamento "p" e l'accesso ad altri membri. Tuttavia, tutto funziona solo quando tutto è nello stesso spazio degli indirizzi. Se i nodi e il puntatore 'p' sono memorizzati nella memoria condivisa, quindi i clienti soffrono una condizione di competizione:

1. x = leggere p
2. y = x + offset
3. Incremento refcount ay

Durante il passaggio 2, p potrebbe cambiare e x potrebbe non puntare più a un nodo valido. L'unica soluzione a cui riesco a pensare è in qualche modo forzare tutti i processi a concordare su dove mappare la memoria condivisa, in modo che i riferimenti reali anziché gli offset possano essere memorizzati nella regione mmap'd. C'è un modo per farlo? Vedo MAP_FIXED nella documentazione di mmap, ma non so come potrei scegliere un indirizzo che sarebbe sicuro.

Modifica: utilizzando l'assembly inline e il prefisso 'lock' su x86, forse è possibile creare un "incremento ptr X con offset Y per valore Z"? Opzioni equivalenti su altre architetture? Non ho scritto molto assemblaggio, non so se esistono le istruzioni necessarie.

Answer 1

a basso livello 86 inctruction atomico può fare tutto questo passi albero contemporaneamente:

1. x = leggere p
2. y = x + compensato Incremento
3. refcount ay

// 
     mov edi, Destination 
     mov edx, DataOffset 
     mov ecx, NewData 
@Repeat: 
     mov eax, [edi + edx] //load OldData 
//Here you can also increment eax and save to [edi + edx]   
     lock cmpxchg dword ptr [edi + edx], ecx 
     jnz @Repeat 
// 

Answer 2

Abbiamo codice simile alla descrizione del problema. Utilizziamo un file mappato in memoria, offset e blocco dei file. Non abbiamo trovato un'alternativa.

Answer 3

Questo è banale su un Sistema UNIX; basta usare le funzioni della memoria condivisa:

shgmet, shmat, shmctl, shmdt

void * shmat (int shmid, const void * shmaddr, int shmflg);

shmat() attribuisce la memoria condivisa segmento individuato dal shmid allo spazio indirizzo del processo chiamante. L'indirizzo fissaggio è specificato da shmaddr con uno dei seguenti criteri :

Se shmaddr è NULL, il sistema sceglie un opportuno indirizzo (inutilizzato) in cui per fissare il segmento.

Basta specificare il proprio indirizzo qui; per esempio. 0x20000000000

Se shmget() utilizzando la stessa chiave e le dimensioni in ogni processo, si otterrà lo stesso segmento di memoria condivisa. Se si shmat() allo stesso indirizzo, gli indirizzi virtuali saranno gli stessi in tutti i processi. Il kernel non si cura di quale intervallo di indirizzi si utilizza, purché non sia in conflitto con qualunque sia il luogo in cui normalmente assegna le cose. (Se si omette l'indirizzo, è possibile vedere la regione generale a cui piace mettere le cose, inoltre, controllare gli indirizzi nello stack e restituiti da malloc()/new [].)

Su Linux, assicurarsi che root imposta SHMMAX in/proc/sys/kernel/shmmax su un numero abbastanza grande da contenere i segmenti di memoria condivisa (il valore predefinito è 32 MB).

Per quanto riguarda le operazioni atomiche, è possibile ottenerle tutte dal codice sorgente del kernel Linux, ad es.

include/asm-x86/atomic_64.h

/* 
* Make sure gcc doesn't try to be clever and move things around 
* on us. We need to use _exactly_ the address the user gave us, 
* not some alias that contains the same information. 
*/ 
typedef struct { 
     int counter; 
} atomic_t; 

/** 
* atomic_read - read atomic variable 
* @v: pointer of type atomic_t 
* 
* Atomically reads the value of @v. 
*/ 
#define atomic_read(v)   ((v)->counter) 

/** 
* atomic_set - set atomic variable 
* @v: pointer of type atomic_t 
* @i: required value 
* 
* Atomically sets the value of @v to @i. 
*/ 
#define atomic_set(v, i)    (((v)->counter) = (i)) 


/** 
* atomic_add - add integer to atomic variable 
* @i: integer value to add 
* @v: pointer of type atomic_t 
* 
* Atomically adds @i to @v. 
*/ 
static inline void atomic_add(int i, atomic_t *v) 
{ 
     asm volatile(LOCK_PREFIX "addl %1,%0" 
        : "=m" (v->counter) 
        : "ir" (i), "m" (v->counter)); 
} 

versione a 64 bit:

typedef struct { 
     long counter; 
} atomic64_t; 

/** 
* atomic64_add - add integer to atomic64 variable 
* @i: integer value to add 
* @v: pointer to type atomic64_t 
* 
* Atomically adds @i to @v. 
*/ 
static inline void atomic64_add(long i, atomic64_t *v) 
{ 
     asm volatile(LOCK_PREFIX "addq %1,%0" 
        : "=m" (v->counter) 
        : "er" (i), "m" (v->counter)); 
} 

Answer 4

Non si deve aver paura di fare un indirizzo a caso, perché il kernel rifiuterà solo gli indirizzi che non gli piacciono (quelli che sono in conflitto). Vedere la mia risposta shmat() sopra, usando 0x20000000000

Con mmap:

void * mmap (void * addr, lunghezza size_t, int Prot, int flag, int fd, off_t offset);

Se addr non è NULL, il kernel lo prende come suggerimento su dove collocare la mappatura su ; su Linux, la mappatura verrà creata al prossimo limite superiore della pagina . L'indirizzo di la nuova mappatura viene restituita come risultato della chiamata .

L'argomento flags determina se aggiornamenti alla mappatura sono visibili ad altri processi mappatura stessa regione, e se gli aggiornamenti sono trasportati attraverso il file di sottostante. Questo comportamento è determinato dalla includendo esattamente uno dei seguenti valori in bandiere:

MAP_SHARED Condividi questa mappatura. Gli aggiornamenti alla mappatura sono visibili a altri processi che associano questo file e vengono trasferiti al file sottostante .Il file potrebbe non essere aggiornato finché non viene chiamato msync (2) o munmap().

ERRORI

EINVAL Non ci piace addr, lunghezza o offset (per esempio, sono troppo grandi, o non allineate su un limite di pagina).

Answer 5

Aggiungere l'offset al puntatore non crea il potenziale per una gara, esiste già. Poiché almeno né ARM né x86 possono leggere atomicamente un puntatore quindi accedere alla memoria a cui si riferisce è necessario proteggere l'accesso del puntatore con un blocco indipendentemente dal fatto che si aggiunga un offset.