heap_allocator
1.0.0
هذا هو مُخصص الكومة البسيط الذي كتبته لنظام تشغيل هواية كنت أعمل عليه. لقد كتبت هذا المُخصص من خلال القليل جدًا من البحث، وقد تم تصميمه ليكون سهل الفهم قدر الإمكان. أعتقد أن هذا المستودع يمكن أن يكون مفيدًا لأولئك الجدد في تطوير نظام التشغيل (مثلي)، أو المهتمين برؤية نسخة مبسطة من الوظائف مثل malloc والمجانية.
يوجد ملفان للرأس يحددان الكومة والقائمة المرتبطة. لتجميع هذا المستودع:
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
سيؤدي هذا إلى تشغيل عرض توضيحي للمخصص وطباعة بعض المعلومات.
من أجل تهيئة هذه الكومة، يجب توفير قسم من الذاكرة. في هذا المستودع، يتم توفير تلك الذاكرة بواسطة malloc (نعم، تخصيص كومة عبر الكومة). في إعداد نظام التشغيل، قد يلزم تعيين بعض الصفحات وتوفيرها إلى الكومة (سيناريو واحد). لاحظ أن الصناديق الموجودة في بنية heap_t تحتاج أيضًا إلى ذاكرة مخصصة لها.
عندما يتم استدعاء الوظيفة init_heap، يجب توفير عنوان بنية الكومة الفارغة (مع مؤشرات الصندوق المخصصة). ستقوم وظيفة init_heap بعد ذلك بإنشاء قطعة كبيرة واحدة برأس (بنية node_t ) وتذييلها (بنية footer_t ). لتحديد حجم هذه القطعة، تستخدم الدالة الثابت HEAP_INIT_SIZE . سيضيف هذا إلى وسيطة start لتحديد مكان انتهاء الكومة.
تحتوي كل قطعة من الذاكرة على بنية عقدة في البداية وبنية تذييل في النهاية. تحتفظ العقدة بالحجم، سواء كانت القطعة مجانية أم لا، ومؤشرين مستخدمين في القائمة المرتبطة بشكل مزدوج (التالي والسابق). تحتوي بنية التذييل ببساطة على مؤشر للرأس (يتم استخدامه أثناء تحرير الأجزاء المجاورة). القطعة الموجودة في نهاية الكومة تسمى قطعة "البرية". إنها القطعة الأكبر ويتم تحديد أحجامها الدنيا والقصوى في الكومة.h. يعد تقليص الكومة وتوسيعها أمرًا سهلاً مثل تغيير حجم قطعة الحياة البرية هذه. يتم تخزين أجزاء الذاكرة المجانية في "صناديق". كل حاوية هي في الواقع مجرد قوائم مرتبطة بشكل مزدوج من العقد ذات الأحجام المتشابهة. تحتوي بنية الكومة على عدد محدد من الصناديق ( BIN_COUNT في الكومة.h). لتحديد الحاوية التي سيتم وضع قطعة منها، يتم تعيين حجم القطعة إلى فهرس الحاوية بواسطة الدالة get_bin_index . ستضمن وظيفة التجميع المتسقة إمكانية الوصول إلى القطع وتخزينها بطريقة محددة. يتم فرز القطع عند إدراجها في الصناديق، لذا فإن إدراج القطعة ليس O(1) ولكن هذا يجعل من السهل العثور على القطع التي تتمتع بأفضل ملاءمة. لاحظ أنه يمكن تعريف وظيفة binning حسب ما يشعر به مستخدم هذه الكومة. قد يكون من المفيد تحديد وظيفة تجميع أكثر تعقيدًا للمساعدة في الاسترداد السريع للقطع.
تأخذ الدالة heap_alloc عنوان بنية الكومة للتخصيص منها وحجمها. تستخدم الدالة ببساطة get_bin_index لتحديد المكان الذي يجب أن تكون فيه قطعة بهذا الحجم، وبالطبع قد لا يكون هناك قطعة بهذا الحجم. إذا لم يتم العثور على أي قطع في الصندوق المقابل، فسيتم فحص الصندوق التالي. سيستمر هذا حتى يتم العثور على قطعة، أو الوصول إلى آخر سلة وفي هذه الحالة سيتم أخذ قطعة من الذاكرة من قطعة البرية. إذا كانت القطعة التي تم العثور عليها كبيرة بما فيه الكفاية، فسيتم تقسيمها. من أجل تحديد ما إذا كان يجب تقسيم القطعة، يتم طرح كمية البيانات الوصفية (النفقات العامة) مما لا يستخدمه تخصيصنا الحالي. إذا كان ما تبقى أكبر من أو يساوي MIN_ALLOC_SZ فهذا يعني أنه يجب علينا تقسيم هذه القطعة ووضع بقايا الطعام في الصندوق الصحيح. بمجرد أن نكون مستعدين لإعادة القطعة التي وجدناها، فإننا نأخذ عنوان الحقل next ونعيده. يتم ذلك لأن الحقول next prev غير مستخدمة أثناء تخصيص قطعة، وبالتالي يمكن لمستخدم القطعة كتابة البيانات إلى هذه الحقول دون التأثير على العمل الداخلي للكومة.
تأخذ الدالة heap_free مؤشرًا يتم إرجاعه بواسطة heap_alloc . يقوم بطرح الإزاحة الصحيحة للحصول على عنوان بنية العقدة. بدلاً من مجرد وضع القطعة في الصندوق الصحيح، يتم فحص القطع المحيطة بالقطعة المقدمة. إذا كان أي من هذه القطع مجانيًا، فيمكننا دمج القطع لإنشاء قطعة أكبر. لتجميع القطع، يتم استخدام التذييل للحصول على بنية العقدة للقطعة السابقة وبنية العقدة للقطعة التالية. على سبيل المثال، لنفترض أن لدينا قطعة تسمى to_free . للحصول على القطعة قبل هذه القطعة، نطرح sizeof(footer_t) للحصول على تذييل القطعة السابقة. يحمل التذييل مؤشرًا إلى رأس القطعة السابقة. للحصول على القطعة التالية، نحصل ببساطة على تذييل to_free ثم نضيف sizeof(footer_t) للحصول على القطعة التالية. بمجرد الانتهاء من كل هذا وإعادة حساب الأحجام، يتم وضع القطعة مرة أخرى في سلة المهملات.
ملاحظة: تم تجميع هذا الرمز في الأصل لجهاز 32 بت، وهذا يعني أنه عند استخدام هذا الرمز، كان من المقبول إرسال int إلى المؤشر نظرًا لأن كلاهما بنفس الحجم. في نظام 64 بت، سيحذرك المترجم من اختلاف الحجم. لإسكات هذه التحذيرات، استخدمت uintptr_t عند النقل من int غير الموقع إلى المؤشر. يؤدي هذا إلى تشويش إمكانية القراءة قليلاً وبعض الحسابات وحسابات المؤشر مطولة لذا ضع ذلك في الاعتبار عند قراءة الكود.
