Ist es möglich, Zeiger im Shared Memory zu speichern, ohne Offsets zu verwenden?

Question

Bei Verwendung von gemeinsam genutztem Speicher kann jeder Prozess den freigegebenen Bereich in einen anderen Bereich des entsprechenden Adressraums kopieren. Dies bedeutet, dass beim Speichern von Zeigern innerhalb der gemeinsamen Region der Start der gemeinsamen Region store them as offsets sein muss. Leider erschwert dies die Verwendung von atomaren Anweisungen (z. B. wenn Sie versuchen, eine lock free algorithm schreiben). Angenommen, Sie haben eine Reihe von Referenzzählknoten im gemeinsam genutzten Speicher, die von einem einzelnen Schreiber erstellt wurden. Der Schreiber aktualisiert periodisch automatisch einen Zeiger "p", um auf einen gültigen Knoten mit einer positiven Referenzzahl zu zeigen. Leser möchten atomar auf 'p' schreiben, da sie auf den Anfang eines Knotens (einer Struktur) zeigt, dessen erstes Element eine Referenzzahl ist. Da p immer auf einen gültigen Knoten zeigt, ist das Erhöhen der Ref-Zählung sicher und macht die Dereferenzierung von "p" und den Zugriff auf andere Mitglieder sicher. Dies funktioniert jedoch nur, wenn sich alles im selben Adressraum befindet. Wenn die Knoten und der Zeiger 'p' im gemeinsam genutzten Speicher gespeichert sind, dann leiden Clients eine Race-Bedingung:

1. x = read p
2. y = x + Offset
3. Increment refcount bei y

Während Schritt 2 kann sich p ändern und X kann nicht mehr auf einen gültigen Knoten zeigen. Die einzige Problemumgehung, die ich mir vorstellen kann, ist, alle Prozesse dazu zu zwingen, sich darauf zu einigen, wo der geteilte Speicher zugeordnet werden soll, so dass reale Zeiger statt Offsets in der mmap-Region gespeichert werden können. Gibt es eine Möglichkeit, das zu tun? Ich sehe MAP_FIXED in der mmap-Dokumentation, aber ich weiß nicht, wie ich eine Adresse auswählen könnte, die sicher wäre.

Edit: Mit Inline-Assembly und der 'Sperre' Präfix auf x86 ist es vielleicht möglich, ein "Inkrement Ptr X mit Offset Y von Wert Z" zu bauen? Gleichwertige Optionen auf anderen Architekturen? Habe nicht viel Assembler geschrieben, weiß nicht ob die benötigten Instruktionen existieren.

Answer 1

auf niedriges Niveau des x86-Atom inctruction kann auf einmal diesen Baum Schritte tun:

1. x = lesen p
2. y = x + Offset Increment
3. refcount bei y

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

Wir haben einen Code, der Ihrer Problembeschreibung ähnelt. Wir verwenden eine Speicherabbilddatei, Offsets und Dateisperren. Wir haben keine Alternative gefunden.

Answer 3

Dies ist trivial auf a UNIX-System; nur die Speicherfunktionen Mitbenützung:

shgmet, shmat, shmctl, shmdt

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

shmat() legt den gemeinsam genutzten Speicher Segment durch shmid zum Raum des rufenden Prozess Adresse identifiziert. Die Befestigung Adresse wird durch shmaddr mit einem der folgenden Kriterien angegeben :

Wenn shmaddr NULL ist, wählt das System eine geeignete (nicht verwendet) Adresse, an die das Segment zu befestigen.

Geben Sie hier einfach Ihre eigene Adresse an; z.B. 0x20000000000

Wenn Sie() mit dem gleichen Schlüssel und Größe in jedem Prozess shmget, erhalten Sie das gleiche Shared-Memory-Segment erhalten. Wenn Sie shmat() an der gleichen Adresse senden, sind die virtuellen Adressen in allen Prozessen identisch. Dem Kernel ist es egal, welchen Adressbereich Sie verwenden, solange er nicht in Konflikt mit den normalerweise zugewiesenen Adressen steht. (Wenn Sie die Adresse weglassen, können Sie die allgemeine Region sehen, in der sie gerne Dinge ablegt; Adressen auf dem Stapel überprüfen und von malloc()/new [] zurückgeben.)

Unter Linux stellen Sie root sicher setzt SHMMAX in/proc/sys/kernel/shmax auf eine Größe, die groß genug ist, um Ihre gemeinsamen Speichersegmente unterzubringen (Standard ist 32 MB).

Wie für atomare Operationen, können Sie sie alle von der Linux-Kernel-Quelle, z.

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)); 
} 

64-Bit-Version:

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

Sie sollten keine Angst haben, eine Adresse nach dem Zufallsprinzip zu bilden, weil der Kernel nur Adressen ablehnt, die er nicht mag (Konflikte). Siehe meine shmat() Antwort oben, mit 0x20000000000

Mit mmap:

void * mmap (void * addr, size_t Länge, int Prot, int flags, int fd, off_t Offset);

Wenn addr nicht NULL ist, dann nimmt der Kernel es als Hinweis, wo zu Platzieren Sie die Zuordnung; Unter Linux wird das Mapping bei der nächsten höheren Seitengrenze erstellt. Die Adresse der neuen Zuordnung wird als Ergebnis des Aufrufs zurückgegeben.

Das Argument flags legt fest, ob Updates für die Zuordnung zu anderen Prozessen Mapping die gleiche Region sichtbar ist, und ob Updates durch bis zur darunter liegenden Datei. Dieses Verhalten wird durch einschließlich genau eine der folgenden Werte in den Flaggen bestimmt:

MAP_SHARED Teilen Sie diese Zuordnung. Aktualisierungen des Mappings sind für andere Prozesse sichtbar, die diese -Datei zuordnen und an die zugrunde liegende Datei weitergeleitet werden.Die Datei darf nicht tatsächlich aktualisiert werden, bis msync (2) oder munmap() aufgerufen wird.

ERRORS

EINVAL Wir möchten nicht addr, Länge oder Offset (beispielsweise sind sie zu groß ist, oder nicht auf einer Seitengrenze ausgerichtet).

Answer 5

Das Hinzufügen des Versatzes zum Zeiger erzeugt nicht das Potenzial für eine Rasse, es existiert bereits. Da weder ARM noch x86 einen Zeiger lesen können und dann auf den Speicher zugreifen, auf den er sich bezieht, müssen Sie den Zeigerzugriff mit einer Sperre schützen, unabhängig davon, ob Sie einen Offset hinzufügen.