▶️ 🚫 📓 STL, Allokator, sein gemeinsamer Speicher und seine Funktionen 🈵 🌔 #⃣

Shared Memory ist der schnellste Weg, um Daten zwischen Prozessen auszutauschen. Im Gegensatz zu Streaming-Mechanismen (Pipes, Sockets aller Stripes, Datei-Warteschlangen ...) hat der Programmierer hier jedoch völlige Handlungsfreiheit, sodass er schreibt, wer das ist, was er will.

Der Autor hat sich also einmal gefragt, was wäre, wenn ... wenn die Adressen von gemeinsam genutzten Speichersegmenten in verschiedenen Prozessen degenerieren. Dies ist eigentlich der Fall, wenn sich ein Prozess mit gemeinsamem Speicher teilt, aber was ist mit verschiedenen Prozessen? Außerdem haben nicht alle Systeme eine Gabel.

Es scheint, dass die Adressen übereinstimmten, und was nun? Zumindest können Sie absolute Zeiger verwenden, was Ihnen viele Kopfschmerzen erspart. Es wird möglich sein, mit C ++ - Zeichenfolgen und Containern zu arbeiten, die aus gemeinsam genutztem Speicher erstellt wurden.

Ein hervorragendes Beispiel übrigens. Nicht dass der Autor STL wirklich geliebt hätte, aber dies ist eine Gelegenheit, einen kompakten und verständlichen Test für die Leistung der vorgeschlagenen Technik zu demonstrieren. Eine Technik, die es (wie es scheint) ermöglicht, die Kommunikation zwischen Prozessen erheblich zu vereinfachen und zu beschleunigen. Ob es funktioniert und wie Sie bezahlen müssen, werden wir weiter verstehen.

Einführung

Die Idee des gemeinsamen Speichers ist einfach und elegant - da jeder Prozess in einem eigenen virtuellen Adressraum arbeitet, der auf den systemweiten physischen Bereich projiziert wird. Warum also nicht zwei Segmenten aus verschiedenen Prozessen erlauben, denselben physischen Speicherbereich zu betrachten?

Und mit der Verbreitung von 64-Bit-Betriebssystemen und der allgegenwärtigen Verwendung von kohärentem Cache bekam die Idee des gemeinsamen Speichers einen zweiten Wind. Jetzt ist es nicht nur ein zyklischer Puffer - eine DIY-Implementierung einer „Pipe“, sondern ein echter „Continuum Transfunctioner“ - ein äußerst mysteriöses und leistungsstarkes Gerät, außerdem ist nur seine Mysteriösität gleich seiner Kraft.

Schauen wir uns einige Anwendungsbeispiele an.

“shared memory” MS SQL. (~10...15%)
Mysql Windows “shared memory”, .
Sqlite WAL-. , . (chroot).
PostgreSQL fork - . , .

.1 PostgreSQL ()

Was möchten wir im Allgemeinen für den idealen gemeinsamen Speicher sehen? Dies ist eine einfache Antwort. Wir möchten, dass die darin enthaltenen Objekte so verwendet werden, als wären sie Objekte, die von Threads desselben Prozesses gemeinsam genutzt werden. Ja, Sie brauchen eine Synchronisation (und Sie brauchen sie trotzdem), aber ansonsten nehmen Sie sie einfach und verwenden sie! Vielleicht ... kann es arrangiert werden.

Ein Proof of Concept erfordert eine minimal sinnvolle Aufgabe :

Es gibt ein Analogon von std :: map <std :: string, std :: string> im gemeinsamen Speicher
Wir haben N Prozesse, die asynchron Werte mit einem Präfix hinzufügen / ändern, das der Prozessnummer entspricht (Beispiel: key_1_ ... für Prozessnummer 1).
Dadurch können wir das Endergebnis kontrollieren

Beginnen wir mit der einfachsten Sache - da wir std :: string und std :: map haben , benötigen wir einen speziellen STL-Allokator.

Allokator STL

Angenommen, es gibt xalloc / xfree- Funktionen für die Arbeit mit gemeinsam genutztem Speicher als Analoga von malloc / free . In diesem Fall sieht der Allokator folgendermaßen aus:

template <typename T>
class stl_buddy_alloc
{
public:
	typedef T                 value_type;
	typedef value_type*       pointer;
	typedef value_type&       reference;
	typedef const value_type* const_pointer;
	typedef const value_type& const_reference;
	typedef ptrdiff_t         difference_type;
	typedef size_t            size_type;
public:
	stl_buddy_alloc() throw()
	{	// construct default allocator (do nothing)
	}
	stl_buddy_alloc(const stl_buddy_alloc<T> &) throw()
	{	// construct by copying (do nothing)
	}
	template<class _Other>
	stl_buddy_alloc(const stl_buddy_alloc<_Other> &) throw()
	{	// construct from a related allocator (do nothing)
	}

	void deallocate(pointer _Ptr, size_type)
	{	// deallocate object at _Ptr, ignore size
		xfree(_Ptr);
	}
	pointer allocate(size_type _Count)
	{	// allocate array of _Count elements
		return (pointer)xalloc(sizeof(T) * _Count);
	}
	pointer allocate(size_type _Count, const void *)
	{	// allocate array of _Count elements, ignore hint
		return (allocate(_Count));
	}
};

Dies reicht aus, um std :: map & std :: string daran zu hängen


template <typename _Kty, typename _Ty>
class q_map : 
    public std::map<
        _Kty, 
        _Ty, 
        std::less<_Kty>, 
        stl_buddy_alloc<std::pair<const _Kty, _Ty> > 
    >
{ };

typedef std::basic_string<
        char, 
        std::char_traits<char>, 
        stl_buddy_alloc<char> > q_string

Bevor Sie sich mit den deklarierten xalloc / xfree-Funktionen befassen , die mit dem Allokator über dem gemeinsam genutzten Speicher arbeiten, sollten Sie den gemeinsam genutzten Speicher selbst verstehen.

Geteilte Erinnerung

Verschiedene Threads desselben Prozesses befinden sich im selben Adressraum. Dies bedeutet, dass jeder nicht thread_local- Zeiger in einem Thread an derselben Stelle angezeigt wird . Mit Shared Memory ist ein zusätzlicher Aufwand erforderlich, um diesen Effekt zu erzielen.

Windows

Lassen Sie uns eine Zuordnung von Datei zu Speicher erstellen. Shared Memory wird wie gewöhnlicher Speicher vom Paging-Mechanismus abgedeckt. Hier wird unter anderem festgelegt, ob wir Shared Paging verwenden oder eine spezielle Datei dafür zuweisen.
```
HANDLE hMapFile = CreateFileMapping(
	INVALID_HANDLE_VALUE,     // use paging file
	NULL,                     // default security
	PAGE_READWRITE,           // read/write access
	(alloc_size >> 32)        // maximum object size (high-order DWORD)
	(alloc_size & 0xffffffff),// maximum object size (low-order DWORD)
	"Local\\SomeData");       // name of mapping object
```
Das Dateinamenpräfix "Local \\" bedeutet, dass das Objekt im lokalen Namespace der Sitzung erstellt wird.

Verwenden Sie, um einer Zuordnung beizutreten, die bereits von einem anderen Prozess erstellt wurde

HANDLE hMapFile = OpenFileMapping(
	FILE_MAP_ALL_ACCESS,      // read/write access
	FALSE,                    // do not inherit the name
	"Local\\SomeData");       // name of mapping object

Jetzt müssen Sie ein Segment erstellen, das auf die fertige Anzeige zeigt
```
void *hint = (void *)0x200000000000ll;
unsigned char *shared_ptr = (unsigned char*)MapViewOfFileEx(
	hMapFile,                 // handle to map object
	FILE_MAP_ALL_ACCESS,      // read/write permission
	0,                        // offset in map object (high-order DWORD)
	0,                        // offset in map object (low-order DWORD)
	0,                        // segment size,
	hint);                    // 
```
Segmentgröße 0 bedeutet, dass die Größe verwendet wird, mit der die Anzeige unter Berücksichtigung der Verschiebung erstellt wurde.

Das Wichtigste hier ist der Hinweis. Wenn es nicht angegeben ist (NULL), nimmt das System die Adresse nach eigenem Ermessen auf. Wenn der Wert jedoch ungleich Null ist, wird versucht, ein Segment der gewünschten Größe mit der gewünschten Adresse zu erstellen. Indem wir seinen Wert in verschiedenen Prozessen als gleich definieren, erreichen wir die Degeneration von Adressen mit gemeinsamem Speicher. Im 32-Bit-Modus ist es nicht einfach, einen großen, nicht zugewiesenen zusammenhängenden Teil des Adressraums zu finden. Im 64-Bit-Modus gibt es kein solches Problem. Sie können immer etwas Passendes finden.

Linux

Hier ist im Grunde alles gleich.

Erstellen Sie ein Shared Memory-Objekt

  int fd = shm_open(
                 “/SomeData”,               //  ,   /
                 O_CREAT | O_EXCL | O_RDWR, // flags,  open
                 S_IRUSR | S_IWUSR);        // mode,  open

  ftruncate(fd, alloc_size);

ftruncate . shm_open /dev/shm/. shmget\shmat SysV, ftok (inode ).

```
int fd = shm_open(“/SomeData”, O_RDWR, 0);
```

  void *hint = (void *)0x200000000000ll;
  unsigned char *shared_ptr = (unsigned char*) = mmap(
                   hint,                      // 
                   alloc_size,                // segment size,
                   PROT_READ | PROT_WRITE,    // protection flags
                   MAP_SHARED,                // sharing flags
                   fd,                        // handle to map object
                   0);                        // offset

hint.

Was sind die Einschränkungen in Bezug auf den Hinweis? Tatsächlich gibt es verschiedene Arten von Einschränkungen.

Erstens die Architektur / Hardware. Hier sollten einige Worte darüber gesagt werden, wie aus einer virtuellen Adresse eine physische wird. Wenn ein TLB- Cache- Fehler vorliegt , müssen Sie auf eine Baumstruktur zugreifen, die als Seitentabelle bezeichnet wird . In IA-32 sieht es beispielsweise so aus:

Abb. 2 Fall von 4K-Seiten, hier aufgenommen Der

Eintrag in den Baum ist der Inhalt des Registers CR3, die Indizes auf den Seiten verschiedener Ebenen sind Fragmente der virtuellen Adresse. In diesem Fall werden 32 Bit zu 32 Bit, alles ist fair.

In AMD64 sieht das Bild etwas anders aus.

Fig. 3 AMD64, 4K-Seiten, von hier aus genommen

CR3 hat jetzt 40 signifikante Bits anstelle von 20 zuvor, in einem Baum von 4 Seitenebenen ist die physikalische Adresse auf 52 Bit begrenzt, während die virtuelle Adresse auf 48 Bit begrenzt ist.

Und nur in (beginnend mit) Ice Lake Microarchitecture (Intel) dürfen 57 Bit der virtuellen Adresse (und immer noch 52 physische) verwendet werden, wenn mit einer 5-Ebenen-Seitentabelle gearbeitet wird.

Bisher haben wir nur über Intel / AMD gesprochen. Zur Abwechslung kann die Seitentabelle in der Aarch64- Architektur 3 oder 4 Ebenen umfassen, sodass 39 bzw. 48 Bit in der virtuellen Adresse verwendet werden können ( 1 ).

Zweitens, Softwareeinschränkungen. Microsoft, insbesondere erlegt (44 Bit bis zu 8,1 / server12, 48 ab) die auf verschiedenen OS - Optionen basierend auf, unter anderem Marketing - Überlegungen.

Übrigens, 48 Stellen, das sind 65.000 mal 4 GB, vielleicht gibt es in solchen offenen Räumen immer eine Ecke, in der Sie sich an Ihren Hinweis halten können.

Shared Memory Allocator

Erstens. Der Allokator muss auf dem zugewiesenen gemeinsam genutzten Speicher leben und alle internen Daten dort ablegen.

Zweitens. Es handelt sich um ein Interprozess-Kommunikationswerkzeug. Optimierungen im Zusammenhang mit der Verwendung von TLS sind irrelevant.

Drittens. Da mehrere Prozesse beteiligt sind, kann der Allokator selbst sehr lange leben, wobei die Reduzierung der externen Speicherfragmentierung von besonderer Bedeutung ist .

Viertens. Das Aufrufen des Betriebssystems für zusätzlichen Speicher ist nicht zulässig. So weist dlmalloc beispielsweise relativ große Blöcke direkt über mmap zu . Ja, es kann durch Anheben der Schwelle entwöhnt werden, aber trotzdem.

Fünfte. Standard-In-Process-Synchronisationstools sind nicht gut, entweder global mit dem entsprechenden Overhead oder etwas, das sich direkt im gemeinsam genutzten Speicher befindet, wie z. B. Spinlocks, ist erforderlich. Sagen wir danke dank des kohärenten Caches. In posix gibt es für diesen Fall auch unbenannte gemeinsame Semaphoren .

Insgesamt war die Wahl unter Berücksichtigung all dieser Punkte und auch, weil es einen Live-Allokator nach der Methode der Zwillinge gab (freundlicherweise von Alexander Artyushin zur Verfügung gestellt, leicht überarbeitet), nicht schwierig.

Lassen wir die Beschreibung der Implementierungsdetails bis zu besseren Zeiten, jetzt ist die öffentliche Schnittstelle interessant:

class BuddyAllocator {
public:
	BuddyAllocator(uint64_t maxCapacity, u_char * buf, uint64_t bufsize);
	~BuddyAllocator(){};

	void *allocBlock(uint64_t nbytes);
	void freeBlock(void *ptr);
...
};

Der Destruktor ist trivial, weil BuddyAllocator greift nicht auf fremde Ressourcen zu.

Letzte Vorbereitungen

Da sich alles im gemeinsam genutzten Speicher befindet, muss dieser Speicher einen Header haben. Für unseren Test sieht dieser Header folgendermaßen aus:

struct glob_header_t {
	//     magic
	uint64_t magic_;
	// hint     
	const void *own_addr_;
	//  
	BuddyAllocator alloc_;
	// 
	std::atomic_flag lock_;
	//   
	q_map<q_string, q_string> q_map_;

	static const size_t alloc_shift = 0x01000000;
	static const size_t balloc_size = 0x10000000;
	static const size_t alloc_size = balloc_size + alloc_shift;
	static glob_header_t *pglob_;
};
static_assert (
    sizeof(glob_header_t) < glob_header_t::alloc_shift, 
    "glob_header_t size mismatch");

glob_header_t *glob_header_t::pglob_ = NULL;

own_addr_ wird beim Erstellen eines gemeinsam genutzten Speichers geschrieben, damit jeder, der mit seinem Namen daran angehängt ist , die tatsächliche Adresse (Hinweis) herausfinden und bei Bedarf erneut eine Verbindung herstellen kann
Es ist nicht gut, die Abmessungen so fest zu codieren, aber es ist für Tests akzeptabel

Die Konstruktoren müssen von dem Prozess aufgerufen werden, der den gemeinsam genutzten Speicher erstellt. Es sieht folgendermaßen aus:

glob_header_t::pglob_ = (glob_header_t *)shared_ptr;

new (&glob_header_t::pglob_->alloc_)
        qz::BuddyAllocator(
                //  
                glob_header_t::balloc_size,
                //  
                shared_ptr + glob_header_t::alloc_shift,
                //   
                glob_header_t::alloc_size - glob_header_t::alloc_shift;

new (&glob_header_t::pglob_->q_map_) 
                q_map<q_string, q_string>();

glob_header_t::pglob_->lock_.clear();

Der Prozess, der eine Verbindung zum gemeinsam genutzten Speicher herstellt, bereitet alles vor
Jetzt haben wir alles, was wir für Tests benötigen, außer den xalloc / xfree-Funktionen
```
void *xalloc(size_t size)
{
	return glob_header_t::pglob_->alloc_.allocBlock(size);
}
void xfree(void* ptr)
{
	glob_header_t::pglob_->alloc_.freeBlock(ptr);
}
```

Es sieht so aus, als könnten wir anfangen.

Experiment

Der Test selbst ist sehr einfach:

for (int i = 0; i < 100000000; i++)
{
        char buf1[64];
        sprintf(buf1, "key_%d_%d", curid, (i % 100) + 1);
        char buf2[64];
        sprintf(buf2, "val_%d", i + 1);

        LOCK();

        qmap.erase(buf1); //   
        qmap[buf1] = buf2;

        UNLOCK();
}

Curid ist die Prozess- / Thread-Nummer. Der Prozess, der den gemeinsam genutzten Speicher erstellt hat, hat kein Curid, spielt jedoch für den Test keine Rolle.

Qmap , LOCK / UNLOCK sind für verschiedene Tests unterschiedlich.

Lassen Sie uns einige Tests machen

THR_MTX - eine Multithread-Anwendung, deren Synchronisation über std :: recursive_mutex ,

qmap - global std :: map <std :: string, std :: string> erfolgt
THR_SPN ist eine Multithread-Anwendung, die Synchronisation erfolgt über einen Spinlock:
```
std::atomic_flag slock;
..
while (slock.test_and_set(std::memory_order_acquire));  // acquire lock
…
slock.clear(std::memory_order_release);                 // release lock
```
qmap - global std :: map <std :: string, std :: string>

PRC_SPN - mehrere laufende Prozesse, Synchronisation durchläuft einen Spinlock:

while (glob_header_t::pglob_->lock_.test_and_set(              // acquire lock
        std::memory_order_acquire));                          
…
glob_header_t::pglob_->lock_.clear(std::memory_order_release); // release lock

qmap - glob_header_t :: pglob _-> q_map_

PRC_MTX - Mehrere laufende Prozesse, die Synchronisation durchläuft einen benannten Mutex .

qmap - glob_header_t :: pglob _-> q_map_

Ergebnisse (Testtyp vs. Anzahl der Prozesse / Threads):

	1	2	4	8	Sechszehn
THR_MTX	1'56 ''	5'41 ''	7'53 ''	51'38 ''	185'49
THR_SPN	1'26 ''	7'38 ''	25'30 ''	103'29 ''	347'04 ''
PRC_SPN	1'24 ''	7'27 ''	24'02 ''	92'34 ''	322'41 ''
PRC_MTX	4'55 ''	13'01 ''	78'14 ''	133'25 ''	357'21 ''

Das Experiment wurde auf einem Computer mit zwei Prozessoren (48 Kerne) mit Xeon® Gold 5118 2,3 GHz, Windows Server 2016, durchgeführt.

Gesamt

Ja, es möglich ist , zu verwenden STL Objekte / Container (im gemeinsam genutzten Speicher zugeordnet) aus verschiedenen Prozessen , sofern sie entsprechend gestaltet sind.
, , PRC_SPN THR_SPN. , BuddyAllocator malloc\free MS ( ).
. — + std::mutex . lock-free , .

Shared Memory wird häufig verwendet, um große Datenströme als eine Art "Pipe" von Hand zu übertragen. Dies ist eine großartige Idee, auch wenn Sie eine teure Synchronisation zwischen Prozessen veranlassen müssen. Wir haben gesehen, dass es beim PRC_MTX-Test nicht billig ist, wenn auch ohne Konkurrenz die Arbeit innerhalb eines Prozesses die Leistung erheblich beeinträchtigt.

Die Erklärung für die hohen Kosten ist einfach: Wenn std ::: recursive_) Mutex (kritischer Abschnitt unter Windows) wie ein Spinlock funktionieren kann , ist ein benannter Mutex ein Systemaufruf, der mit den entsprechenden Kosten in den Kernel-Modus wechselt. Außerdem ist der Verlust des Ausführungskontexts durch einen Thread / Prozess immer sehr teuer.

Aber wie können wir die Kosten senken, da die Synchronisierung von Prozessen unvermeidlich ist? Die Antwort ist seit langem erfunden - Pufferung. Nicht jedes einzelne Paket wird synchronisiert, sondern eine bestimmte Datenmenge - der Puffer, in den diese Daten serialisiert werden. Wenn der Puffer deutlich größer als die Paketgröße ist, müssen Sie viel seltener synchronisieren.

Es ist zweckmäßig, zwei Techniken zu mischen - Daten im gemeinsam genutzten Speicher, und nur relative Zeiger (vom Beginn des gemeinsam genutzten Speichers) werden über den Interprozessdatenkanal gesendet (z. B. Schleife durch localhost). weil Der Zeiger ist normalerweise kleiner als das Datenpaket, wodurch Synchronisation gespart wird.

Wenn verschiedene Prozesse unter derselben virtuellen Adresse auf gemeinsam genutzten Speicher zugreifen können, können Sie die Leistung etwas steigern.

Daten zum Senden nicht serialisieren, beim Empfang nicht deserialisieren
Senden Sie ehrliche Zeiger auf Objekte, die im gemeinsamen Speicher über den Stream erstellt wurden
Wenn wir ein fertiges (Zeiger-) Objekt erhalten, verwenden wir es und löschen es dann mit einem regulären Löschvorgang. Der gesamte Speicher wird automatisch freigegeben. Dies erspart uns das Durcheinander mit dem Ringpuffer.
Sie können sogar keinen Zeiger senden, sondern (so wenig wie möglich - ein Byte mit dem Wert "Sie haben E-Mail") eine Benachrichtigung darüber, dass sich etwas in der Warteschlange befindet

Schließlich

Do's and Don'ts für Objekte, die im gemeinsamen Speicher erstellt wurden.

Verwenden Sie RTTI . Aus offensichtlichen Gründen. Das Objekt std :: type_info befindet sich außerhalb des gemeinsam genutzten Speichers und ist nicht prozessübergreifend verfügbar.
Verwenden Sie virtuelle Methoden. Aus dem gleichen Grunde. Die virtuellen Funktionstabellen und die Funktionen selbst sind nicht prozessübergreifend verfügbar.
Wenn wir über STL sprechen, müssen alle ausführbaren Dateien von Prozessen, die Speicher gemeinsam nutzen, von einem Compiler mit denselben Einstellungen kompiliert werden, und die STL selbst muss dieselbe sein.

PS : Danke an Alexander Artyushin und Dmitry Iptyshev (Dmitria) für Hilfe bei der Vorbereitung dieses Artikels.

STL, Allokator, sein gemeinsamer Speicher und seine Funktionen