スレッドセーフな循環バッファを備えたC ++テンプレートアロケータ

これは、スレッドセーフな循環バッファーを備えたアロケーター用の単純なC ++テンプレートです。



1つのヘッダー.hファイルでのすべての実装：[fast_mem_pool.h]



チップ、なぜこのアロケーターが何百もの同様のアロケーターよりも優れているのか-カットの下で。



これが私のバイクの仕組みです。



1）リリースビルドでは、ミューテックスやアトミックの待機サイクルはありませんが、アロケーターは循環的であり、スレッドによってリリースされるときにリソースを継続的に再生成します。彼はどうやってそれをしますか？



FastMemPoolがfmallocを介して提供するRAMの各割り当ては、実際にはヘッダー用です。

  struct AllocHeader {
//    : tag_this = this + leaf_id
    uint64_t  tag_this  {  2020071700  };  
//  :
    int  size;  
//     :
    int  leaf_id  {  -2020071708  };  
  };

このヘッダーは、ポインター（res_ptr）から巻き戻すことにより、ユーザーが所有するポインターから常に取得できます。sizeof（AllocHeader）：







AllocHeaderヘッダーの内容により、ffree（void * ptr）メソッドはその割り当てを認識し、循環バッファーメモリのどのシートが返されるかを検出します。 ：

  void  ffree(void  *ptr)
  {
    char  *to_free  =  static_cast<char  *>(ptr)  
         -  sizeof(AllocHeader);
    AllocHeader  *head  =  reinterpret_cast<AllocHeader  *>(to_free);

アロケータがメモリを割り当てるように求められると、シートの配列の現在のシートを調べて、必要なサイズ+ヘッダーサイズのサイズ（AllocHeader）を切り取ることができるかどうかを確認します。



アロケータでは、Leaf_Cntメモリシートが事前に予約されており、各シートのサイズはLeaf_Size_Bytesです（ここではすべてが従来型です）。割り当ての機会を探すために、fmalloc（std :: size_t layout_size）メソッドはleaf_array配列のリーフを一周し、すべてがビジー状態の場合、Do_OS_mallocフラグが有効になっていると、オペレーティングシステムからsizeof（AllocHeader）で必要なサイズよりも大きいメモリを取得します-外部メモリは内部循環バッファまたはOSから取得され、アロケータは常にサービス情報を含むヘッダーを作成します。アロケータのメモリが不足し、Do_OS_malloc == falseフラグが設定されている場合、fmallocはnullptrを返します。この動作は負荷を制御するのに役立ちます（たとえば、フレーム処理モジュールがカメラのFPSに追いついていない場合、ビデオカメラからフレームをスキップします）。

サイクリングの実装方法

循環アロケータは循環タスク用に設計されています-タスクは永遠に続くべきではありません。たとえば、次のようになります。

• ユーザーセッションの割り当て
• ビデオ分析のためのビデオストリームフレーム処理
• ゲーム内の戦闘ユニットの寿命

leaf_array配列には任意の数のメモリシートが存在する可能性があるため、制限内でゲーム内の理論的に可能な戦闘ユニット数のページを作成できます。これにより、ユニットが脱落した状態で、空きメモリシートを確実に取得できます。実際には、ビデオ分析の場合、通常は16枚の大きなシートで十分であり、そのうち最初の数枚は、検出器の初期化時に長期の非周期的割り当てに寄付されます。

スレッドの安全性の実装方法

割り当てシートの配列はミューテックスなしで機能します...「データ競合」などのエラーに対する保護は次のように行われます。

      char  *buf;
      // available == offset 
      std::atomic<int>  available  {  Leaf_Size_Bytes  };
      // allocated ==  
      std::atomic<int>  deallocated  {  0  };

各メモリシートには2つのカウンタがあります。



-Leaf_Size_Bytesのサイズで初期化して使用できます。割り当てごとに、このカウンターは減少し、同じカウンターがメモリシートの先頭に対するオフセットとして機能します==メモリはバッファの末尾から割り当てられます。

result_ptr  =  leaf_array[leaf_id].buf + available_after;

-割り当て解除は{0}からゼロに初期化され、このシートの割り当て解除ごとに（取引が処理されているシートまたはOSのAllocHeaderから学習します）、リリースされたボリュームによってカウンターが増加します。

const int  deallocated  =  leaf_array[head->leaf_id].deallocated.fetch_add(real_size, std::memory_order_acq_rel)  +  real_size;

このようなカウンター（deallocated ==（Leaf_Size_Bytes-available））が一致するとすぐに、これは割り当てられたすべてが解放され、リーフを元の状態にリセットできることを意味しますが、ここに微妙なポイントがあります：リーフをリセットする決定後にどうなるか元に戻すと、誰かがシートから別の小さなメモリを割り当てます...これを除外するには、compare_exchange_strongチェックを使用します。

if (deallocated  == (Leaf_Size_Bytes - available))
{  //      ,
  // , ,  Leaf
  if (leaf_array[head->leaf_id].available
      .compare_exchange_strong(available,  Leaf_Size_Bytes))
  {
    leaf_array[head->leaf_id].deallocated  -=  deallocated;
  }
}

メモリーシートは、リセット時に使用可能なカウンターの状態が決定時と同じままである場合にのみ、元の状態にリセットされます。タダー!!!



素晴らしいボーナスは、各割り当てのAllocHeaderヘッダーを使用して次のバグをキャッチできることです。

• 再割り当て
• 他人の記憶の割り当て解除
• バッファオーバーフロー
• 他人のメモリ領域へのアクセス

2番目の機能は、これらの機会に実装されます。



2） Debugコンパイルは、再割り当て中に以前の割り当て解除が行われた正確な情報（ファイル名、コード行番号、メソッド名）を提供します。これは、基本メソッド（fmallocd、ffreed、check_accessd-メソッドのデバッグバージョンの最後にdが付いています）の周りにデコレータの形式で実装されます。

/**
 * @brief FFREE  -      free
 * @param iFastMemPool  -   FastMemPool    
 * @param ptr  -      fmaloc
 */
#if defined(Debug)
#define FFREE(iFastMemPool, ptr) \
   (iFastMemPool)->ffreed (__FILE__, __LINE__, __FUNCTION__, ptr)
#else
#define FFREE(iFastMemPool, ptr) \
   (iFastMemPool)->ffree (ptr)
#endif

プリプロセッサマクロが使用されます。

• __FILE __- c ++ソースファイル
• __LINE __- c ++ソースファイルの行番号
• __FUNCTION __-これが発生した関数の名前

この情報は、割り当てポインタと割り当て情報の間の対応としてメディエータに保存されます。

  struct AllocInfo {
//   : ,   ,   :
    std::string  who;  
//  true - ,  false - :
    bool  allocated  {  false  };  
  };
  std::map<void *,  AllocInfo>  map_alloc_info;
  std::mutex  mut_map_alloc_info;

デバッグでは速度はそれほど重要ではないため、標準のstd ::マップを保護するためにミューテックスが使用されました。テンプレートパラメータ（bool Raise_Exeptions = DEF_Raise_Exeptions）は、エラー時に例外をスローするかどうかに影響します。



リリースビルドで最大限の快適さを望む場合は、DEF_Auto_deallocateフラグを設定すると、すべてのOS malloc割り当てが書き込まれ（すでにstd :: set <>のミューテックスの下にあります）、FastMemPoolデストラクタ（割り当てトラッカーとして使用）でリリースされます。



3）「バッファオーバーフロー」などのエラーを回避するには、割り当てられたメモリの操作を開始する前に、FastMemPool :: check_accessチェックを使用することをお勧めします。オペレーティングシステムは、他の誰かのRAMにアクセスしたときにのみ文句を言いますが、check_access関数（またはFCHECK_ACCESSマクロ）は、AllocHeaderヘッダーによって、指定された割り当てのオーバーランがあるかどうかを計算します。

  /**
   * @brief check_access  -        
   * @param base_alloc_ptr -      FastMemPool
   * @param target_ptr  -     
   * @param target_size  -   ,    
   * @return - true         FastMemPool
   */
  bool  check_access(void  *base_alloc_ptr,  void  *target_ptr,  std::size_t  target_size)

//  :
  if (FCHECK_ACCESS(fastMemPool, elem.array, 
      &elem.array[elem.array_size - 1], sizeof (int))) 
  {
    elem.array[elem.array_size - 1] = rand();
  }

初期割り当てのポインタがわかれば、いつでもヘッダーを取得できます。ヘッダーから割り当てのサイズを確認し、ターゲット要素が初期割り当て内にあるかどうかを計算します。理論的に可能な最大アクセス数で処理サイクルを開始する前に、一度チェックするだけで十分です。制限値が割り当ての境界を突破する可能性が非常に高いです（たとえば、計算では、プロセスの物理的性質により、一部の変数は特定の範囲内でしか歩くことができないと想定されているため、割り当ての境界を破るためのチェックは行いません）。



1週間後に殺して、構造にランダムなデータをときどき書き込む人を探すよりも、一度チェックする方がよいでしょう...



4） CMakeを介してコンパイル時にデフォルトのテンプレートコードを設定します。



CmakeLists.txtには、構成可能なパラメーターが含まれています。次に例を示します。

set(DEF_Leaf_Size_Bytes "65536" CACHE PATH "Size of each memory pool leaf")
message("DEF_Leaf_Size_Bytes: ${DEF_Leaf_Size_Bytes}")
set(DEF_Leaf_Cnt "16" CACHE PATH "Memory pool leaf count")
message("DEF_Leaf_Cnt: ${DEF_Leaf_Cnt}")

これにより、QtCreator：







またはCMake GUIでパラメータを編集するのが非常に便利になります。







次に、コンパイル中に次のようにパラメータがコードに渡されます。

set(SPEC_DEFINITIONS
      ${CMAKE_SYSTEM_NAME}
      ${CMAKE_BUILD_TYPE}
      ${SPEC_BUILD}
      SPEC_VERSION="${Proj_VERSION}"
      DEF_Leaf_Size_Bytes=${DEF_Leaf_Size_Bytes}
      DEF_Leaf_Cnt=${DEF_Leaf_Cnt}
      DEF_Average_Allocation=${DEF_Average_Allocation}
      DEF_Need_Registry=${DEF_Need_Registry}
  )
#
target_compile_definitions(${TARGET} PUBLIC ${TARGET_DEFINITIONS})

コードでは、デフォルトのテンプレート値をオーバーライドします：

#ifndef DEF_Leaf_Size_Bytes
  #define DEF_Leaf_Size_Bytes  65535
#endif


template<int Leaf_Size_Bytes = DEF_Leaf_Size_Bytes, 
    int Leaf_Cnt = DEF_Leaf_Cnt,
    int Average_Allocation = DEF_Average_Allocation,
    bool Do_OS_malloc = DEF_Do_OS_malloc,
    bool Need_Registry = DEF_Need_Registry, 
    bool Raise_Exeptions = DEF_Raise_Exeptions>
class FastMemPool
{
// ..
};

そのため、CMakeパラメータのチェックボックスをオン/オフにすることで、アロケータテンプレートをマウスで快適に調整できます。



5）同じ.hファイル内のSTLコンテナーでアロケーターを使用できるようにするために、std :: allocatorの機能は、FastMemPoolAllocatorテンプレートに部分的に実装されています。

//    compile time  :
std::unordered_map<int,  int, std::hash<int>,
  std::equal_to<int>,
  FastMemPoolAllocator<std::pair<const int,  int>> >   umap1;

//    runtime  :
std::unordered_map<int,  int>  umap2(
   1024, std::hash<int>(),
   std::equal_to<int>(),
   FastMemPoolAllocator<std::pair<const int,  int>>());

使用例は、test_allocator1.cppおよびtest_stl_allocator2.cppにあります。



たとえば、割り当てに関するコンストラクタとデストラクタの作業：

bool test_Strategy()
{
  /*
   *     Runtime
   *  (     )
 */
  using MyAllocatorType = FastMemPool<333, 33>;
// instance of:
  MyAllocatorType  fastMemPool;  
// inject instance:
  FastMemPoolAllocator<std::string,
     MyAllocatorType > myAllocator(&fastMemPool); 
  //     3 :
  std::string* str = myAllocator.allocate(3);
  //     : 
  myAllocator.construct(str, "Mother ");
  myAllocator.construct(str + 1, " washed ");
  myAllocator.construct(str + 2, "the frame");

//- 
  std::cout << str[0] << str[1] << str[2]; 

  //  :
  myAllocator.destroy(str);
  myAllocator.destroy(str + 1);
  myAllocator.destroy(str + 2);
  //  :
  myAllocator.deallocate(str, 3);
  return  true;
}

6）大規模なプロジェクトでは、ある種のモジュールを作成し、すべてを徹底的にテストすることがあります。これはスイスの時計のように機能します。モジュールはDetectorに含まれており、戦闘に参加します。1日に1回、ライブラリがダンプに陥り始めることがあります。デバッガーでダンプを実行した後、ポインターのループトラバーサルの1つで、nullptrの代わりに、誰かが8という数字をポインターに書き込んだことがわかります。このポインターに移動すると、当然、オペレーティングシステムが怒りました。



考えられる原因の範囲をどのように絞り込むことができますか？容疑者からあなたの構造を除外することは非常に簡単です-それらはRAMに別の場所（妨害者が爆撃しない場所）に移動する必要があります：







FastMemPoolを使用してこれを簡単に行うにはどうすればよいですか？それは非常に簡単です：FastMemPoolでは、割り当てはメモリのページの終わりから噛み砕くことによって行われます-作業に必要な以上のメモリのページを要求することによって、メモリのページの始まりがバグのある爆撃のテストの場のままであることを保証します。例えば：

FastMemPool<100000000, 1, 1024, true, true>  bulletproof_mempool;
void *ptr = bulletproof_mempool.fmalloc(1234567);
// ..
//  -    c ptr
// ..
bulletproof_mempool.ffree(ptr);

新しい場所で誰かがあなたの建造物を爆撃している



場合、おそらくあなた自身です...そうでなければ、図書館が安定した場合、チームは一度にいくつかの贈り物を受け取ります：

• あなたのアルゴリズムは再びスイスの時計のように機能します
• バグのあるコーダーは、空のメモリ領域を安全に爆撃できるようになりました（誰もがそれを探している間）、ライブラリは安定しています。
• 爆撃範囲を監視してメモリを変更することができます-バグのあるエンコーダにトラップを設定します。

---

全体として、この特定のバイクの利点は何ですか？

• ( / )
• , Debug ,
• , /
• , ( nullptr), — , ( FPS , FastMemPool -).

当社では、金属板の3D形状解析のインストールには、マルチスレッドビデオ処理（50FPS）が必要でした。シートはカメラの下を通過し、レーザーの反射でシートの3Dマップを作成します。 FastMemPoolは、メモリと安全性を操作する最大速度を確保するために使用されました。ストリームが着信フレームに対応できない場合、通常の方法で将来の処理のためにフレームを保存すると、RAMが制御不能に消費されます。 FastMemPoolを使用すると、オーバーフローが発生した場合、割り当て中にnullptrが返され、フレームがスキップされます。最終的な3Dイメージでは、ステップのジャンプという形の欠陥は、CPUスレッドを処理に追加する必要があることを示しています。



循環メモリアロケータとタスクスタックを使用したスレッドのミューテックスフリー操作により、フレーム損失やRAMのオーバーフローなしに、着信フレームを非常に迅速に処理できました。現在、このコードはAMD Ryzen 9 3950X CPUの16スレッドで実行され、FastMemPoolクラスの障害は確認されていません。



簡略化された例-RAMオーバーフロー制御を使用したビデオ分析プロセスの図は、ソースコードtest_memcontrol1.cppにあります。



そしてデザートの場合：同じスキーム例では、非ミューテックススタックが使用されます：

using  TWorkStack = SpecSafeStack<VideoFrame>;
//..
  // Video frames exchanger:
TWorkStack  work_stack;
//..
work_staff->work_stack.push(frame);
//..
VideoFrame * frame = work_staff->work_stack.pop();

すべてのソースを備えた実用的なデモスタンドは、gihubにあります。