gc
1.0.0
gc هو تطبيق لأداة تجميع البيانات المهملة المحافظة والمحلية والعلامة والاكتساح. يوفر التنفيذ بديلاً كامل الوظائف لمكالمات POSIX malloc() و calloc() و realloc() و free() .
ينصب تركيز gc على توفير تنفيذ نظيف من الناحية النظرية لـ GC mark-and-sweep، دون الخوض في أعماق التحسين الخاص بالهندسة المعمارية (انظر على سبيل المثال Boehm GC لمثل هذا المشروع). يجب أن يكون مناسبًا بشكل خاص لأغراض التعلم ومفتوحًا لجميع أنواع التحسين (مرحبًا بممثلي العلاقات العامة!).
الدافع الأصلي لـ gc هو رغبتي في كتابة LISP الخاص بي بلغة C، بالكامل من الصفر - وهذا يتطلب جمع البيانات المهملة.
لم يكن هذا العمل ممكنًا بدون القدرة على قراءة أعمال الآخرين، وأبرزهم Boehm GC، وorangeduck's tgc (الذي يتبع أيضًا المثل العليا لكونه صغيرًا وبسيطًا)، ودليل جمع القمامة.
gc . $ git clone [email protected]:mkirchner/gc.git
$ cd gc
للتجميع باستخدام مترجم clang :
$ make test
لاستخدام مجموعة مترجمات GNU (GCC):
$ make test CC=gcc
يجب أن تكتمل الاختبارات بنجاح. لإنشاء تقرير التغطية الحالي:
$ make coverage
...
#include "gc.h"
...
void some_fun () {
...
int * my_array = gc_calloc ( & gc , 1024 , sizeof ( int ));
for ( size_t i = 0 ; i < 1024 ; ++ i ) {
my_array [ i ] = 42 ;
}
...
// look ma, no free!
}
int main ( int argc , char * argv []) {
gc_start ( & gc , & argc );
...
some_fun ();
...
gc_stop ( & gc );
return 0 ;
} يصف هذا واجهة برمجة التطبيقات الأساسية، راجع gc.h لمزيد من التفاصيل وواجهة برمجة التطبيقات ذات المستوى المنخفض.
من أجل تهيئة وبدء عملية جمع البيانات المهملة، استخدم الدالة gc_start() وقم بتمرير عنوان أسفل المكدس :
void gc_start ( GarbageCollector * gc , void * bos ); تحتاج معلمة أسفل المكدس bos إلى الإشارة إلى متغير مخصص للمكدس ووضع علامة على النهاية المنخفضة للمكدس من حيث يبدأ البحث عن الجذر (المسح).
يمكن إيقاف جمع البيانات المهملة وإيقافها مؤقتًا واستئنافها
void gc_stop ( GarbageCollector * gc );
void gc_pause ( GarbageCollector * gc );
void gc_resume ( GarbageCollector * gc );ويمكن تشغيل عملية جمع البيانات المهملة يدويًا باستخدام
size_t gc_run ( GarbageCollector * gc ); يدعم gc تخصيص الذاكرة على نمط malloc() و calloc() و realloc() . تحاكي توقيعات الوظائف المعنية وظائف POSIX (باستثناء أننا نحتاج إلى تمرير أداة تجميع البيانات المهملة كوسيطة أولى):
void * gc_malloc ( GarbageCollector * gc , size_t size );
void * gc_calloc ( GarbageCollector * gc , size_t count , size_t size );
void * gc_realloc ( GarbageCollector * gc , void * ptr , size_t size );من الممكن تمرير مؤشر إلى دالة مدمرة من خلال الواجهة الموسعة:
void * dtor ( void * obj ) {
// do some cleanup work
obj -> parent -> deregister ();
obj -> db -> disconnect ()
...
// no need to free obj
}
...
SomeObject * obj = gc_malloc_ext ( gc , sizeof ( SomeObject ), dtor );
... يدعم gc التخصيصات الثابتة التي يتم جمعها من البيانات المهملة فقط عند إيقاف تشغيل GC عبر gc_stop() . ما عليك سوى استخدام وظيفة المساعد المناسبة:
void * gc_malloc_static ( GarbageCollector * gc , size_t size , void ( * dtor )( void * )); يتوقع التخصيص الثابت مؤشرًا لوظيفة الإنهاء؛ فقط اضبط على NULL إذا لم يكن الإنهاء مطلوبًا.
لاحظ أن gc حاليًا لا يضمن ترتيبًا محددًا عندما يجمع المتغيرات الثابتة، إذا كانت هناك حاجة إلى إلغاء تخصيص المتغيرات الثابتة بترتيب معين، فيجب على المستخدم استدعاء gc_free() عليها بالتسلسل المطلوب قبل استدعاء gc_stop() ، انظر أدناه .
من الممكن أيضًا تشغيل إلغاء تخصيص الذاكرة الصريح باستخدام
void gc_free ( GarbageCollector * gc , void * ptr ); يتم ضمان استدعاء gc_free() من أجل (أ) إنهاء/تدمير الكائن المشار إليه بواسطة ptr إذا كان ذلك ممكنًا و(ب) لتحرير الذاكرة التي يشير إليها ptr بغض النظر عن الجدولة الحالية لجمع البيانات المهملة وسيعمل أيضًا إذا تم GC تم الإيقاف مؤقتًا باستخدام gc_pause() أعلاه.
يقدم gc أيضًا تطبيق strdup() الذي يُرجع نسخة مجمعة من البيانات المهملة:
char * gc_strdup ( GarbageCollector * gc , const char * s );الفكرة الأساسية وراء جمع البيانات المهملة هي أتمتة دورة تخصيص/إلغاء تخصيص الذاكرة. يتم تحقيق ذلك عن طريق تتبع كافة الذاكرة المخصصة وتفعيل إلغاء تخصيص الذاكرة التي لا تزال مخصصة ولكن لا يمكن الوصول إليها بشكل دوري.
يقوم العديد من جامعي البيانات المهملة المتقدمين أيضًا بتنفيذ أسلوبهم الخاص في تخصيص الذاكرة (أي استبدال malloc() ). وهذا يمكّنهم غالبًا من تخطيط الذاكرة بطريقة أكثر كفاءة في استخدام المساحة أو للوصول بشكل أسرع، ولكنه يأتي على حساب التطبيقات الخاصة بالهندسة المعمارية وزيادة التعقيد. يتجنب gc هذه المشكلات من خلال الرجوع إلى تطبيقات POSIX *alloc() والحفاظ على فصل إدارة الذاكرة والبيانات التعريفية لجمع البيانات المهملة. وهذا يجعل فهم gc أسهل بكثير، ولكنه بالطبع أقل كفاءة في استخدام المساحة والوقت من الأساليب الأكثر تحسينًا.
بنية البيانات الأساسية داخل gc عبارة عن خريطة تجزئة تقوم بتعيين عنوان الذاكرة المخصصة لبيانات تعريف مجموعة البيانات المهملة لتلك الذاكرة:
العناصر الموجودة في خريطة التجزئة هي تخصيصات، تم تصميمها باستخدام struct Allocation :
typedef struct Allocation {
void * ptr ; // mem pointer
size_t size ; // allocated size in bytes
char tag ; // the tag for mark-and-sweep
void ( * dtor )( void * ); // destructor
struct Allocation * next ; // separate chaining
} Allocation ; يحمل كل مثيل Allocation مؤشرًا للذاكرة المخصصة، وحجم الذاكرة المخصصة في ذلك الموقع، وعلامة للتمييز والمسح (انظر أدناه)، ومؤشر اختياري لوظيفة التدمير ومؤشر لمثيل Allocation التالي ( لتسلسل منفصل، انظر أدناه).
يتم جمع التخصيصات في AllocationMap
typedef struct AllocationMap {
size_t capacity ;
size_t min_capacity ;
double downsize_factor ;
double upsize_factor ;
double sweep_factor ;
size_t sweep_limit ;
size_t size ;
Allocation * * allocs ;
} AllocationMap ; يوفر هذا، جنبًا إلى جنب مع مجموعة من الوظائف static داخل gc.c ، دلالات خريطة التجزئة لتنفيذ واجهة برمجة التطبيقات العامة.
AllocationMap هو هيكل البيانات المركزي في بنية GarbageCollector والذي يعد جزءًا من واجهة برمجة التطبيقات العامة:
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ; مع وجود بنيات البيانات الأساسية، فإن أي طلب لتخصيص ذاكرة gc_*alloc() هو إجراء من خطوتين: أولاً، تخصيص الذاكرة من خلال وظيفة النظام (على سبيل المثال malloc() ) وثانيًا، إضافة أو تحديث بيانات التعريف المرتبطة إلى خريطة التجزئة.
بالنسبة إلى gc_free() ، استخدم المؤشر لتحديد موقع البيانات التعريفية في خريطة التجزئة، وحدد ما إذا كان إلغاء التخصيص يتطلب استدعاء مدمر، واستدعاء إذا لزم الأمر، وحرر الذاكرة المُدارة، واحذف إدخال البيانات التعريفية من خريطة التجزئة.
تتيح هياكل البيانات هذه والواجهات المرتبطة بها إدارة بيانات التعريف المطلوبة لإنشاء أداة تجميع البيانات المهملة.
يقوم gc بتشغيل التجميع في حالتين: (أ) عند فشل أي من استدعاءات تخصيص النظام (على أمل إلغاء تخصيص ذاكرة كافية لتلبية الطلب الحالي)؛ و (ب) عندما يتجاوز عدد الإدخالات في خريطة التجزئة علامة مائية عالية تم تعديلها ديناميكيًا.
في حالة حدوث أي من هاتين الحالتين، يقوم gc بإيقاف العالم ويبدأ تشغيل مجموعة البيانات المهملة ذات العلامات والمسح على كافة التخصيصات الحالية. يتم تنفيذ هذه الوظيفة في وظيفة gc_run() التي تعد جزءًا من واجهة برمجة التطبيقات العامة وتقوم بتفويض جميع الأعمال إلى وظائف gc_mark() و gc_sweep() التي تعد جزءًا من واجهة برمجة التطبيقات الخاصة.
لدى gc_mark() مهمة البحث عن الجذور ووضع علامات على جميع التخصيصات المعروفة التي يتم الرجوع إليها من جذر (أو من التخصيص الذي تتم الإشارة إليه من جذر، أي بشكل عابر) على أنها "مستخدمة". بمجرد اكتمال وضع العلامات، يتكرر gc_sweep() على جميع التخصيصات المعروفة ويلغي تخصيص جميع التخصيصات غير المستخدمة (أي غير المميزة)، ويعود إلى gc_run() ويستمر العالم في العمل.
سيحتفظ gc بتخصيصات الذاكرة التي يمكن الوصول إليها ويجمع كل شيء آخر. يعتبر التخصيص قابلاً للوصول إذا تحقق أي مما يلي:
gc_start() (أي bos هو أصغر عنوان مكدس يتم أخذه في الاعتبار أثناء مرحلة العلامة).gc_*alloc() الذي يشير إلى محتوى التخصيص.GC_TAG_ROOT .تعمل خوارزمية التحديد والمسح الساذجة على مرحلتين. أولاً، في مرحلة العلامة ، تقوم الخوارزمية بالبحث عن جميع تخصيصات الجذر وجميع التخصيصات التي يمكن الوصول إليها من الجذور ووضع علامة عليها. ثانيًا، في مرحلة المسح ، تمر الخوارزمية على جميع التخصيصات المعروفة، وتجمع كل التخصيصات التي لم يتم وضع علامة عليها وبالتالي تعتبر غير قابلة للوصول.
في بداية مرحلة العلامة ، نقوم أولاً بمسح جميع التخصيصات المعروفة والعثور على جذور واضحة باستخدام مجموعة علامات GC_TAG_ROOT . يمثل كل من هذه الجذور نقطة انطلاق لوضع العلامات العودية ذات العمق الأول.
يكتشف gc بعد ذلك جميع الجذور في المكدس (بدءًا من bos مؤشر أسفل المكدس الذي تم تمريره إلى gc_start() ) والسجلات (عن طريق تفريغها على المكدس قبل مرحلة العلامة) ويستخدمها كنقاط بداية لـ وضع العلامات كذلك.
نظرًا لتخصيص الجذر، يتكون وضع العلامات من (1) تعيين حقل tag في كائن Allocation إلى GC_TAG_MARK و(2) مسح الذاكرة المخصصة بحثًا عن مؤشرات إلى التخصيصات المعروفة، وتكرار العملية بشكل متكرر.
التنفيذ الأساسي عبارة عن بحث بسيط ومتكرر في العمق أولاً يقوم بمسح محتوى الذاكرة بالكامل للعثور على المراجع المحتملة:
void gc_mark_alloc ( GarbageCollector * gc , void * ptr )
{
Allocation * alloc = gc_allocation_map_get ( gc -> allocs , ptr );
if ( alloc && !( alloc -> tag & GC_TAG_MARK )) {
alloc -> tag |= GC_TAG_MARK ;
for ( char * p = ( char * ) alloc -> ptr ;
p < ( char * ) alloc -> ptr + alloc -> size ;
++ p ) {
gc_mark_alloc ( gc , * ( void * * ) p );
}
}
} في gc.c ، يبدأ gc_mark() عملية وضع العلامات عن طريق تحديد الجذور المعروفة على المكدس عبر استدعاء gc_mark_roots() . لتحديد الجذور نقوم بتمرير كامل عبر جميع التخصيصات المعروفة. ننتقل بعد ذلك إلى تفريغ السجلات على المكدس.
من أجل جعل محتويات تسجيل وحدة المعالجة المركزية متاحة للبحث عن الجذر، يقوم gc بتفريغها على المكدس. يتم تنفيذ ذلك بطريقة محمولة إلى حد ما باستخدام setjmp() ، الذي يخزنها في متغير jmp_buf مباشرة قبل وضع علامة على المكدس:
...
/* Dump registers onto stack and scan the stack */
void ( * volatile _mark_stack )( GarbageCollector * ) = gc_mark_stack ;
jmp_buf ctx ;
memset ( & ctx , 0 , sizeof ( jmp_buf ));
setjmp ( ctx );
_mark_stack ( gc );
... يعد التحويل باستخدام مؤشر الوظيفة volatile _mark_stack إلى وظيفة gc_mark_stack() ضروريًا لتجنب تضمين استدعاء gc_mark_stack() .
بعد وضع علامة على كل الذاكرة التي يمكن الوصول إليها وبالتالي من المحتمل أن تكون قيد الاستخدام، يصبح جمع التخصيصات التي لا يمكن الوصول إليها أمرًا تافهًا. إليك التنفيذ من gc_sweep() :
size_t gc_sweep ( GarbageCollector * gc )
{
size_t total = 0 ;
for ( size_t i = 0 ; i < gc -> allocs -> capacity ; ++ i ) {
Allocation * chunk = gc -> allocs -> allocs [ i ];
Allocation * next = NULL ;
while ( chunk ) {
if ( chunk -> tag & GC_TAG_MARK ) {
/* unmark */
chunk -> tag &= ~ GC_TAG_MARK ;
chunk = chunk -> next ;
} else {
total += chunk -> size ;
if ( chunk -> dtor ) {
chunk -> dtor ( chunk -> ptr );
}
free ( chunk -> ptr );
next = chunk -> next ;
gc_allocation_map_remove ( gc -> allocs , chunk -> ptr , false);
chunk = next ;
}
}
}
gc_allocation_map_resize_to_fit ( gc -> allocs );
return total ;
} نحن نكرر جميع التخصيصات في خريطة التجزئة (حلقة for )، ونتبع كل سلسلة (حلقة while مع chunk = chunk->next ) وإما (1) إلغاء تحديد القطعة إذا تم تحديدها؛ أو (2) استدعاء المدمر الموجود على القطعة وتحرير الذاكرة إذا لم يتم وضع علامة عليها، مع الاحتفاظ بإجمالي مقدار الذاكرة التي قمنا بتحريرها.
وبهذا تنتهي عملية العلامة والاجتياح. تم استئناف العالم المتوقف ونحن مستعدون للتشغيل التالي!
