📈 #⃣ ♓️ STL、アロケータ、その共有メモリとその機能 ⭕️ 👴🏽 👵🏾

共有メモリは、プロセス間でデータを交換するための最速の方法です。ただし、ストリーミングメカニズム（パイプ、すべてのストライプのソケット、ファイルキューなど）とは異なり、ここではプログラマーは完全に自由に行動できるため、必要なものを誰が作成するかを記述します。

そのため、著者はかつて、異なるプロセスで共有メモリセグメントのアドレスが縮退している場合はどうなるのか疑問に思いました。これは実際には共有メモリプロセスがフォークしたときに何が起こるかですが、異なるプロセスはどうですか？また、すべてのシステムにフォークがあるわけではありません。

アドレスが一致しているように見えるので、何ですか？少なくとも、絶対ポインタを使用できます。これにより、多くの問題を回避できます。共有メモリから構築されたC ++文字列およびコンテナを操作できるようになります。

ちなみに、良い例です。著者がSTLを本当に気に入ったわけではありませんが、これは提案された手法のパフォーマンスに関するコンパクトで理解しやすいテストを示す機会です。（見たところ）プロセス間通信を大幅に簡素化および高速化できる手法。それが機能するかどうか、そしてあなたがどのように支払う必要があるか、私たちはさらに理解します。

前書き

共有メモリのアイデアはシンプルでエレガントです-各プロセスはシステム全体の物理に投影される独自の仮想アドレス空間で動作するため、異なるプロセスの2つのセグメントが同じ物理メモリ領域を参照できるようにしないでください。

そして、64ビットのオペレーティングシステムの急増とコヒーレントキャッシュのユビキタスな使用により、共有メモリのアイデアは第二の風を巻き起こしました。今では、それは単なる循環バッファー（「パイプ」のDIY実装）ではなく、実際の「連続トランスファンクション」（非常に神秘的で強力なデバイス）であり、その神秘性だけがそのパワーに匹敵します。

いくつかの使用例を見てみましょう。

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

.1 PostgreSQL ()

一般的に言って、どのような理想的な共有メモリが欲しいですか？これは簡単な答えです。その中のオブジェクトを、同じプロセスのスレッド間で共有されるオブジェクトであるかのように使用できるようにしたいと思います。はい、同期が必要です（とにかく必要です）が、それ以外の場合は、同期して使用するだけです！多分...それは手配することができます。

概念の証明には、最小限の意味のあるタスクが必要です。

共有メモリにstd :: map <std :: string、std :: string>の類似物があります
プロセス番号に対応するプレフィックスを持つ値を非同期的に追加/変更するN個のプロセスがあります（例：プロセス番号1の場合はkey_1_ ...）
その結果、最終結果を制御できます

最も単純なことから始めましょう-std :: stringとstd :: mapがあるので、特別なSTLアロケーターが必要です。

アロケーターSTL

malloc / freeのアナログとして共有メモリを操作するためのxalloc / xfree関数があるとします。この場合、アロケータは次のようになります。

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

これは、std :: map＆std :: stringをフックするのに十分です


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

共有メモリ上でアロケータと連携する宣言されたxalloc / xfree関数を扱う前に、共有メモリ自体を理解する価値があります。

共有メモリ

同じプロセスの異なるスレッドは同じアドレススペースにあります。つまり、任意のスレッドのすべての非thread_localポインターは同じ場所を参照します。共有メモリでは、この効果を実現するために余分な労力が必要です。

ウィンドウズ

ファイルからメモリへのマッピングを作成しましょう。共有メモリは、通常のメモリと同様に、ページングメカニズムによってカバーされます。ここでは、特に、共有ページングを使用するか、このために特別なファイルを割り当てるかが決定されます。
```
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
```
ファイル名のプレフィックス「Local \\」は、オブジェクトがセッションのローカル名前名に作成されることを意味します。

別のプロセスによってすでに作成されているマッピングに参加するには、

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

次に、完成したディスプレイを指すセグメントを作成する必要があります
```
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);                    // 
```
セグメントサイズ0は、シフトを考慮して、ディスプレイが作成されたサイズが使用されることを意味します。

ここで最も重要なことはヒントです。指定されていない場合（NULL）、システムはその裁量でアドレスを選択します。ただし、値がゼロ以外の場合は、目的のアドレスで目的のサイズのセグメントを作成しようとします。共有メモリアドレスの縮退を実現するのは、さまざまなプロセスでその値を同じものとして定義することです。32ビットモードでは、アドレス空間の大きな未割り当ての連続したチャンクを見つけるのは簡単ではありません。64ビットモードではそのような問題はなく、いつでも適切なものを見つけることができます。

Linux

ここでは基本的にすべて同じです。

共有メモリオブジェクトを作成します

  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.

ヒントに関して、その価値の制限は何ですか？実際には、さまざまな種類の制限があります。

まず、アーキテクチャ/ハードウェア。ここでは、仮想アドレスが物理アドレスにどのように変換されるかについて、いくつか説明する必要があります。TLBキャッシュミスがある場合は、ページテーブルと呼ばれるツリー構造にアクセスする必要があります。たとえば、IA-32では次のようになります。

図2ここで取り上げた4Kページの場合

ツリーへのエントリはレジスタCR3の内容であり、異なるレベルのページのインデックスは仮想アドレスのフラグメントです。この場合、32ビットは32ビットになり、すべてが公平です。

AMD64では、画像が少し異なります。

図3 AMD64、4Kページ、ここから取得

CR3は、以前の20ではなく40の有効ビットを持ち、4レベルのページのツリーでは、物理アドレスは52ビットに制限され、仮想アドレスは48ビットに制限されます。

そしてだけ（で始まる）に氷湖のマイクロアーキテクチャ（インテル）さを許可5レベルページテーブルを操作する場合57個の仮想アドレスのビット（と、まだ52物理）を使用します。

これまでのところ、Intel / AMDについてのみ説明してきました。変更のために、Aarch64アーキテクチャでは、ページテーブルを3レベルまたは4レベルにすることができ、仮想アドレスでそれぞれ39ビットまたは48ビットを使用できます（1）。

第二に、ソフトウェアの制限。特にMicrosoftは、とりわけマーケティング上の考慮事項に基づいて、さまざまなOSオプションにそれらを課しています（8.1 / Server12までの44ビット、48から始まります）。

ちなみに、48桁、つまり4GBの65000倍です。おそらく、このようなオープンスペースには、ヒントに固執できるコーナーが常にあります。

共有メモリアロケータ

まず第一に。アロケータは、割り当てられた共有メモリ上に存在し、すべての内部データをそこに配置する必要があります。

第二に。プロセス間通信ツールについて話しているので、TLSの使用に関連する最適化は関係ありません。

第三に。いくつかのプロセスが関係しているため、アロケータ自体は非常に長い間存続する可能性があり、外部メモリの断片化を減らすことが特に重要です。

第4。追加のメモリのためにOSを呼び出すことは許可されていません。したがって、たとえばdlmallocは、mmapを介して比較的大きなチャンクを直接割り当てます。はい、しきい値を上げることで離脱できますが、それでもなおです。

5番目。標準のインプロセス同期機能は適切ではなく、対応するオーバーヘッドを伴うグローバルか、スピンロックなどの共有メモリに直接配置されたものが必要です。コヒーレントキャッシュのおかげだとしましょう。posixには、この場合の名前のない共有セマフォもあります。

全体として、上記のすべてを考慮すると、手元に双子の方法によるライブアロケーターがあったため（Alexander Artyushinから提供され、わずかに改訂されました）、選択は簡単であることがわかりました。

実装の詳細の説明は、より良い時期まで残しましょう。パブリックインターフェイスが興味深いものになりました。

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

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

破壊者は取るに足らないので BuddyAllocatorは、無関係なリソースを取得しません。

最終準備

すべてが共有メモリにあるため、このメモリにはヘッダーが必要です。テストでは、このヘッダーは次のようになります。

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_は、共有メモリを作成するときに書き込まれるため、名前で接続するすべての人が実際のアドレス（ヒント）を見つけて、必要に応じて再接続できます。
このように寸法をハードコーディングするのは良くありませんが、テストには使用できます

コンストラクターは、共有メモリを作成するプロセスによって呼び出される必要があります。次のようになります。

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

共有メモリに接続するプロセスはすべての準備を整えます
これで、xalloc / xfree関数を除いて、テストに必要なものがすべて揃いました。
```
void *xalloc(size_t size)
{
	return glob_header_t::pglob_->alloc_.allocBlock(size);
}
void xfree(void* ptr)
{
	glob_header_t::pglob_->alloc_.freeBlock(ptr);
}
```

始められるようです。

実験

テスト自体は非常に簡単です。

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はプロセス/スレッド番号であり、共有メモリを作成したプロセスのcuridはゼロですが、テストには関係ありません。

Qmap、LOCK / UNLOCKは、テストごとに異なります。

いくつかのテストをしましょう

THR_MTX-マルチスレッドアプリケーション、同期はstd :: recursive_mutex、

qmap-グローバルstd :: map <std :: string、std :: string>を経由します
THR_SPNはマルチスレッドアプリケーションであり、同期はスピンロックを介して行われます。
```
std::atomic_flag slock;
..
while (slock.test_and_set(std::memory_order_acquire));  // acquire lock
…
slock.clear(std::memory_order_release);                 // release lock
```
qmap-グローバル標準::マップ<標準::文字列、標準::文字列>

PRC_SPN-いくつかの実行中のプロセス、同期はスピンロックを通過します：

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-いくつかの実行中のプロセス、同期は名前付きミューテックスを介して行われます。

qmap - glob_header_t :: pglob _-> q_map_

結果（テストタイプとプロセス/スレッドの数）：

	1	2	4	8	16
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 ''

実験は、Xeon®Gold5118 2.3GHz、Windows Server 2016を搭載したデュアルプロセッサ（48コア）コンピュータで実行されました。

合計

はい。適切に設計されていれば、さまざまなプロセスのSTLオブジェクト/コンテナ（共有メモリに割り当てられている）を使用できます。
, , PRC_SPN THR_SPN. , BuddyAllocator malloc\free MS ( ).
. — + std::mutex . lock-free , .

共有メモリは、手作業で作成された一種の「パイプ」として大きなデータストリームを転送するためによく使用されます。プロセス間のコストのかかる同期を調整する必要がある場合でも、これは優れたアイデアです。 PRC_MTXテストでは、競合がなくても1つのプロセス内で作業するとパフォーマンスが大幅に低下するため、安くはないことがわかりました。std：:( recursive_）mutex（ウィンドウの下の重要なセクション）がスピンロックのように機能する

場合、高コストの説明は簡単です。名前付きミューテックスはシステム呼び出しであり、対応するコストでカーネルモードに入ります。また、スレッド/プロセスによる実行コンテキストの損失は常に非常にコストがかかります。

しかし、プロセスの同期は避けられないので、どうすればコストを削減できますか？答えは長い間発明されてきました-バッファリング。すべてのパケットが同期されるわけではありませんが、一定量のデータ（このデータがシリアル化されるバッファー）が同期されます。バッファがパケットサイズよりも著しく大きい場合は、同期の頻度を大幅に減らす必要があります。

共有メモリ内のデータと、相対ポインタ（共有メモリの先頭から）のみがプロセス間データチャネルを介して送信されるという2つの手法を組み合わせると便利です（例：localhostを介したループ）。なぜならポインタは通常、データパケットよりも小さいため、同期を節約できます。

また、同じ仮想アドレスの異なるプロセスで共有メモリを使用できる場合は、パフォーマンスを少し向上させることができます。

送信用にデータをシリアル化しないでください。受信時に逆シリアル化しないでください。
ストリームを介して共有メモリに作成されたオブジェクトへの正直なポインタを送信します
準備ができた（ポインタ）オブジェクトを取得したら、それを使用し、通常の削除によって削除します。すべてのメモリが自動的に解放されます。これにより、リングバッファをいじる必要がなくなります。
ポインタではなく、（可能な限り最小の値-「メールがあります」という値のバイト）キューに何かがあるという事実に関する通知を送信することもできます。

最後に

共有メモリで構築されたオブジェクトの推奨事項と禁止事項。

RTTIを使用します。明らかな理由で。std :: type_infoオブジェクトは共有メモリの外部に存在し、プロセス間で使用できません。
仮想メソッドを使用します。同じ理由で。仮想関数テーブルと関数自体は、プロセス間で使用できません。
STLについて言えば、メモリを共有するプロセスのすべての実行可能ファイルは、同じ設定で1つのコンパイラによってコンパイルされる必要があり、STL自体も同じである必要があります。

PS：AlexanderArtyushinとDmitryIptyshevに感謝します（ドミトリー）この記事の準備に役立ちます。

STL、アロケータ、その共有メモリとその機能

前書き