مخصص قالب C ++ مع مخزن مؤقت دائري آمن للخيط

إليك نموذج C ++ بسيط لمخصص مع مخزن مؤقت دائري آمن للخيط.



كل التنفيذ في ملف .h واحد: [fast_mem_pool.h]



رقائق ، لماذا هذا المخصص أفضل من المئات من تلك المماثلة - تحت القص.



هذه هي الطريقة التي تعمل بها دراجتي.



1) في بنية الإصدار ، لا توجد كائنات كائنات ولا دورات انتظار لـ atomic - ولكن المخصص دوري ، ويجدد الموارد باستمرار حيث يتم تحريرها بواسطة سلاسل الرسائل. كيف يفعل ذلك؟



كل تخصيص من ذاكرة الوصول العشوائي (RAM) يقدمه FastMemPool عبر fmalloc هو في الواقع أكثر للرأس:

  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 signature_size) خلال أوراق مصفوفة Lea_array ، وإذا كان كل شيء مشغولاً في كل مكان ، فشرط تمكين علامة Do_OS_malloc ، فسيأخذ ذاكرة من نظام التشغيل أكبر من الحجم المطلوب حسب sizeof (AllocHeader) - خارج يتم أخذ الذاكرة من المخزن المؤقت الدائري الداخلي أو من نظام التشغيل ، يقوم المُخصص دائمًا بإنشاء رأس مع معلومات الخدمة. إذا نفد المخصص من الذاكرة وعلامة Do_OS_malloc == false ، فسيعيد fmalloc القيمة nullptr - هذا السلوك مفيد للتحكم في الحمل (على سبيل المثال ، تخطي الإطارات من كاميرا الفيديو عندما لا تواكب وحدات معالجة الإطار مع FPS للكاميرا).

كيف يتم تنفيذ ركوب الدراجات

تم تصميم المخصصات الدورية للمهام الدورية - يجب ألا تستمر المهام إلى الأبد. على سبيل المثال ، يمكن أن يكون:

• المخصصات لجلسات المستخدم
• معالجة إطار دفق الفيديو لتحليلات الفيديو
• حياة الوحدات القتالية في اللعبة

نظرًا لأنه يمكن أن يكون هناك أي عدد من أوراق الذاكرة في مصفوفة Lea_array ، فمن الممكن في حدود الحد الأقصى إنشاء صفحة للعدد الممكن نظريًا للوحدات القتالية في اللعبة ، بحيث نضمن الحصول على ورقة ذاكرة مجانية مع حالة انسحاب الوحدات. من الناحية العملية ، بالنسبة لتحليلات الفيديو ، عادةً ما تكون 16 ورقة كبيرة كافية بالنسبة لي ، ويتم التبرع بالأوراق القليلة الأولى منها لعمليات تخصيص طويلة غير دورية عند تهيئة الكاشف.

كيف يتم تنفيذ سلامة الخيط

تعمل مصفوفة من أوراق التخصيص بدون كائنات كيميائية ... الحماية ضد أخطاء مثل "سباق البيانات" تتم على النحو التالي:

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

تحتوي كل ورقة ذاكرة



على عدادين : - متاح ، مهيأ حسب حجم Leaf_Size_Bytes. مع كل تخصيص ، يقل هذا العداد ، ويعمل نفس العداد كإزاحة بالنسبة لبداية ورقة الذاكرة == يتم تخصيص الذاكرة من نهاية المخزن المؤقت:

result_ptr  =  leaf_array[leaf_id].buf + available_after;

- تتم تهيئة إلغاء التخصيص {0} إلى الصفر ، ومع كل إلغاء تخصيص في هذه الورقة (أتعلم من AllocHeader على أي ورقة أو نظام تشغيل يتم التعامل مع الصفقة) ، يتم زيادة العداد حسب الحجم الصادر:

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

بمجرد تطابق العدادات مثل هذه (تم إلغاء تخصيصها == (Leaf_Size_Bytes - متاح)) ، فهذا يعني أن كل ما تم تخصيصه قد تم تحريره الآن ويمكنك إعادة تعيين الورقة إلى حالتها الأصلية ، ولكن هذه نقطة دقيقة: ماذا سيحدث إذا بعد قرار إعادة تعيين الورقة بالعودة إلى الأصل ، يقوم شخص ما بتخصيص جزء صغير آخر من الذاكرة من الورقة ... لاستبعاد ذلك ، استخدم check_exchange_strong check:

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) يوفر التجميع 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;

نظرًا لأن السرعة ليست مهمة جدًا في التصحيح ، فقد تم استخدام كائن المزامنة (mutex) لحماية خريطة std :: القياسية. تؤثر معلمة القالب (bool Raise_Exeptions = DEF_Raise_Exeptions) على ما إذا كان سيتم طرح استثناء على الخطأ.



بالنسبة لأولئك الذين يريدون أقصى قدر من الراحة في بنية الإصدار ، يمكنك تعيين علامة DEF_Auto_deallocate ، ثم سيتم كتابة جميع تخصيصات نظام التشغيل malloc (بالفعل ضمن كائن المزامنة في std :: set <>) وإصدارها في FastMemPool destruction (يستخدم كمتعقب للتخصيص).



3)لتجنب أخطاء مثل "تجاوز سعة المخزن المؤقت" ، أوصي باستخدام FastMemPool :: check_access check قبل البدء في العمل بالذاكرة المخصصة. بينما لا يشتكي نظام التشغيل إلا عند دخولك إلى ذاكرة الوصول العشوائي الخاصة بشخص آخر ، فإن وظيفة 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();
  }

بمعرفة مؤشر التخصيص الأولي ، يمكنك دائمًا الحصول على الرأس ، من الرأس نكتشف حجم التخصيص ، ثم نحسب ما إذا كان العنصر الهدف سيكون ضمن التخصيص الأولي. يكفي التحقق مرة واحدة قبل بدء دورة المعالجة بأقصى وصول ممكن نظريًا. قد يكون من الجيد جدًا أن القيم المحددة ستخترق حدود التخصيص (على سبيل المثال ، في الحسابات يُفترض أن بعض المتغيرات يمكن أن تسير في نطاق معين فقط بسبب فيزياء العملية ، وبالتالي لا تتحقق من كسر حدود التخصيص).



من الأفضل التحقق مرة واحدة بدلاً من القتل بعد أسبوع للبحث عن شخص يقوم أحيانًا بكتابة بيانات عشوائية إلى الهياكل الخاصة بك ...



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) من أجل التمكن من استخدام المُخصص في حاويات STL في نفس الملف .h ، يتم تنفيذ إمكانات std :: المخصص جزئيًا في قالب 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) في بعض الأحيان في مشروع كبير ، تقوم بعمل نوع من الوحدات ، واختبار كل شيء بدقة - إنها تعمل مثل ساعة سويسرية. يتم تضمين الوحدة النمطية الخاصة بك في الكاشف ، وخوض معركة - وفي بعض الأحيان ، مرة واحدة في اليوم ، تبدأ المكتبة في الوقوع في مكب نفايات. بعد تشغيل التفريغ على مصحح الأخطاء ، تجد أنه في إحدى حلقات اجتياز المؤشرات ، بدلاً من 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 -).

في شركتنا ، يتطلب تركيب التحليل الهندسي ثلاثي الأبعاد للصفائح المعدنية معالجة فيديو متعددة الخيوط (50 إطارًا في الثانية). تمر الأوراق أسفل الكاميرا وأنا أقوم ببناء خريطة ثلاثية الأبعاد للورقة من انعكاس الليزر. تم استخدام FastMemPool لضمان أقصى سرعة للعمل مع الذاكرة والأمان. إذا لم تستطع التدفقات التعامل مع الإطارات الواردة ، فإن حفظ الإطارات للمعالجة المستقبلية بالطريقة المعتادة يؤدي إلى استهلاك غير متحكم فيه لذاكرة الوصول العشوائي. مع FastMemPool ، في حالة تجاوز السعة ، سيتم إرجاع nullptr ببساطة أثناء التخصيص وسيتم تخطي الإطار - في الصورة ثلاثية الأبعاد النهائية ، يوضح هذا العيب في شكل قفزة في خطوة أنه من الضروري إضافة مؤشرات ترابط CPU إلى المعالجة.



جعلت عملية الخيوط الخالية من المزامنة مع مخصص ذاكرة دائرية ومكدس المهام من الممكن معالجة الإطارات الواردة بسرعة كبيرة ، دون فقدان الإطار ودون تجاوز ذاكرة الوصول العشوائي. يعمل هذا الرمز الآن في 16 مؤشر ترابط على وحدة المعالجة المركزية AMD Ryzen 9 3950X ، ولم يتم تحديد أي أعطال في فئة FastMemPool.



يمكن رؤية مثال - مخطط مبسط لعملية تحليل الفيديو مع التحكم في تجاوز ذاكرة الوصول العشوائي في كود المصدر 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 .