جداول الصفحات

3. جداول الصفحات

جداول الصفحات هي أشهر آليّةٍ تمنح بها نظم التشغيل كلّ عمليّةٍ فضاء عناوينها الخاصّ وذاكرتها. فهي تحدّد ما تعنيه عناوين الذاكرة وأيّ أجزاء الذاكرة الفيزيائيّة يمكن الوصول إليها. وهي تسمح لـxv6 أن يعزل فضاءات عناوين العمليّات المختلفة وأن يضمّها في ذاكرةٍ فيزيائيّةٍ واحدة. كما توفّر جداول الصفحات مستوىً من الإحالة غير المباشرة يمكّن نظم التشغيل من أداء حِيَلٍ مفيدةٍ كثيرة. ويستفيد xv6 من بعضها: تعيين الذاكرة نفسها (صفحة الترامبولين) في عدّة فضاءات عناوين، وحماية مكدّسي النواة والمستخدم بصفحةٍ غير معيَّنةٍ، وتخصيص ذاكرة كومة المستخدم كسلًا. ويشرح باقي هذا الفصل جداول الصفحات التي يوفّرها عتاد RISC-V وكيف يستخدمها xv6.

3.1 عتاد الصفحات

وكما يُذكَّر، فإنّ تعليمات RISC-V (تعليمات المستخدم والنواة معًا) تتعامل مع عناوين افتراضيّة. أمّا ذاكرة الجهاز (RAM)، أو الذاكرة الفيزيائيّة، فتُفهرَس بعناوين فيزيائيّة. ويربط عتاد جدول صفحات RISC-V بين هذين النوعين من العناوين بتعيين كلّ عنوانٍ افتراضيٍّ إلى عنوانٍ فيزيائيّ.

الشكل 3.1: عرضٌ تجريديّ لجدول صفحاتٍ مسطّحٍ يعيّن العناوين الافتراضيّة إلى الفيزيائيّة.

يستخدم xv6 وضع Sv39، ومعناه أنّ الـ39 بتًّا الدنيا فقط من العنوان الافتراضيّ ذي الـ64 بتًّا هي المستخدمة؛ أمّا الـ25 بتًّا العلويّة فلا تُستخدم. وفي تلك الهيئة، يكون جدول الصفحات منطقيًّا مصفوفةً من $2^{27}$ (134,217,728) مدخلة جدول صفحات (PTEs)، تحتوي كلٌّ منها على رقم صفحةٍ فيزيائيّةٍ من 44 بتًّا وبعض الرايات. ويترجم عتاد الصفحات عنوانًا افتراضيًّا باستخدام الـ27 بتًّا العلويّة من الـ39 بتًّا لفهرسة جدول الصفحات بحثًا عن مدخلةٍ، وبصنع عنوانٍ فيزيائيٍّ من 56 بتًّا تأتي بتّاته الـ44 العلويّة من رقم الصفحة الفيزيائيّة في المدخلة، وتُنسَخ بتّاته الـ12 الدنيا من العنوان الافتراضيّ الأصليّ. ويُبيّن الشكل 3.1 هذه العمليّة بعرضٍ منطقيٍّ لجدول الصفحات بوصفه مصفوفةً بسيطةً من المدخلات (أمّا جدول صفحات RISC-V فشجرةٌ في الحقيقة؛ انظر الشكل 3.2 للقصة الأكمل). ويمنح جدول الصفحات نظام التشغيل تحكّمًا في ترجمات العناوين الافتراضيّة إلى الفيزيائيّة بدقّة كتلٍ محاذيةٍ من 4096 ( $2^{12}$ ) بايت، وتُسمّى الكتلة الواحدة صفحةً (page).

الشكل 3.2: تفاصيل ترجمة العناوين في RISC-V.

تترك تصميمات RISC-V مجالًا لتوسيع العناوين الافتراضيّة والفيزيائيّة على حدٍّ سواء. فإذا لزم مزيدٌ من فضاء العناوين الافتراضي، يدعم RISC-V وضع Sv48 ذا العناوين الافتراضيّة من 48 بتًّا (ووترمان وآخرون 2024). وللعناوين الفيزيائيّة أيضًا مجالٌ للنموّ: فهناك متّسعٌ في صيغة المدخلة لينمو رقم الصفحة الفيزيائيّة بعشرة بتّاتٍ أخرى. وقد اختار مصمّمو RISC-V أحجام العناوين بناءً على تنبّؤاتٍ تقنيّة. فـ$2^{48}$ بايت تساوي 262,144 غيغابايت، أيّ فضاء عناوينٍ افتراضيٍّ للمستخدم أكبر بكثيرٍ ممّا يُرجّح أن يستخدمه أيُّ تطبيقٍ اليوم. و$2^{56}$ بايت من فضاء العناوين الفيزيائيّة تساوي 65,536 تيرابايت، أيّ RAM أكثرَ بكثيرٍ مما يمكن تجهيز أيّ حاسوبٍ به اليوم.

وكما يُبيّن الشكل 3.2، يُخزَّن جدول صفحات وحدة المعالجة المركزيّة في RISC-V في الذاكرة الفيزيائيّة على هيئة شجرةٍ ثلاثيّة المستويات. وجذر الشجرة صفحة جدول صفحاتٍ من 4096 بايت تحتوي 512 مدخلةً، وهي التي تحتوي العناوين الفيزيائيّة لصفحات جداول الصفحات في المستوى التالي من الشجرة. وتحتوي كلٌّ من تلك الصفحات 512 مدخلةً للمستوى الأخير في الشجرة. ويستخدم عتاد الصفحات الـ9 بتّاتٍ العلويّة من الـ27 بتًّا لانتقاء مدخلةٍ في صفحة جدول الصفحات الجذريّة، والـ9 بتّات الوسطى لانتقاء مدخلةٍ في صفحة جدول صفحاتٍ في المستوى التالي من الشجرة، والـ9 بتّاتٍ الأدنى لانتقاء المدخلة الأخيرة. (ووضع Sv48 في RISC-V ذو أربعة مستويات لجدول الصفحات، والبتّات من 39 إلى 47 من العنوان الافتراضيّ تفهرس في المستوى الأعلى.)

فإذا كانت أيٌّ من المدخلات الثلاث اللازمة لترجمة عنوانٍ غير موجودة، يرفع عتاد الصفحات استثناءَ خطأ الصفحة، تاركًا أمر التعامل مع خطأ الصفحة للنواة (انظر الفصلين 4 و5).

إنّ البنيّة ثلاثيّة المستويات في الشكل 3.2 تتيح طريقةً موفّرةً للذاكرة في تسجيل المدخلات، مقارنةً بالتصميم أحاديّ المستوى في الشكل 3.1. ففي الحالة الشائعة التي لا توجد فيها مقابلاتٌ لمدىً كبيرٍ من العناوين الافتراضيّة، تستطيع البنيّة ثلاثيّة المستويات أن تُغفل أدلّة صفحاتٍ بأكملها. فمثلًا، إذا كان تطبيقٌ ما يستخدم بضع صفحاتٍ فقط بدءًا من العنوان صفر، فإنّ المدخلات من 1 إلى 511 في دليل الصفحات الأعلى غير صالحةٍ، ولا يلزم النواة أن تخصّص صفحاتًا لتلك الأدلّة الوسيطة الـ511. فضلًا عن ذلك، لا يلزم النواة أيضًا أن تخصّص صفحاتٍ لأدلّة الصفحات السفليّة الخاصّة بتلك الأدلّة الوسيطة الـ511. ففي هذا المثال، توفّر التصميم ثلاثيّ المستويات 511 صفحةً للأدلّة الوسيطة و$511\times512$ صفحةً لأدلّة الصفحات السفليّة.

ومع أنّ وحدة المعالجة المركزيّة تجتاز البنيّة ثلاثيّة المستويات عتاديًّا كجزءٍ من تنفيذ تعليمة تحميلٍ أو تخزينٍ، إلّا أنّ عيبًا محتملًا في المستويات الثلاثة هو أنّ على وحدة المعالجة المركزيّة أن تحمّل ثلاث مدخلاتٍ من الذاكرة لتؤدّي ترجمة العنوان الافتراضيّ في تعليمة التحميل/التخزين إلى عنوانٍ فيزيائيّ. ولكي تتجنّب كلفة تحميل المدخلات من الذاكرة الفيزيائيّة، تُخزّن وحدة المعالجة المركزيّة في RISC-V مدخلات جدول الصفحات في مخزن الترجمة الجانبيّ (Translation Look-aside Buffer)، ويُسمّى اختتصارًا TLB.

تحتوي كلّ مدخلةٍ على بتّات راياتٍ تُخبر عتاد الصفحات بكيفيّة السماح باستخدام العنوان الافتراضيّ المرتبط بها. فتشير PTE_V إلى ما إذا كانت المدخلة موجودةً: فإن لم تُضبط، سبّبت الإشارة إلى الصفحة خطأ صفحةٍ (أي أنّها غير مسموحةٍ). وتتحكّم PTE_R في السماح للتعليمات بالقراءة من الصفحة. وتتحكّم PTE_W في السماح للتعليمات بالكتابة إلى الصفحة. وتتحكّم PTE_X في قدرة وحدة المعالجة المركزيّة على تأويل محتوى الصفحة بوصفه تعليماتٍ وتنفيذه. وتتحكّم PTE_U في السماح للتعليمات في وضع المستخدم بالوصول إلى الصفحة؛ فإن لم تُضبط PTE_U، لم يمكن استخدام المدخلة إلّا في وضع المشرف. ويُبيّن الشكل 3.2 أين تقع بتّات الرايات في المدخلة. والرايات وجميع البنى الأخرى المرتبطة بعتاد الصفحات معرَّفةٌ في (riscv.h)

ولإخبار وحدة المعالجة المركزيّة باستخدام جدول صفحاتٍ، يلزم النواة أن تكتب العنوان الفيزيائيّ لصفحة جدول الصفحات الجذريّة في السجلّ satp. وستترجم وحدة المعالجة المركزيّة جميع العناوين التي تولّدها التعليمات اللاحقة باستخدام جدول الصفحات الذي يُشير إليه satp الخاصّ بها. ولكلّ وحدة معالجةٍ مركزيّةٍ satp خاصّ بها، حتّى تستطيع وحدات المعالجة المختلفة أن تُشغّل عمليّاتٍ مختلفة، لكلٍّ منها فضاء عناوينٍ خاصٌّ تصفه جدول صفحاتها الخاصّ.

ومن وجهة نظر النواة، جدول الصفحات بياناتٌ مخزَّنةٌ في الذاكرة، وتُنشئ النواة جداول الصفحات وتعدّلها بشيفرةٍ تشبه كثيرًا ما قد تراه لأيّ بنية بياناتٍ على هيئة شجرة.

وبضع ملاحظاتٍ حول المصطلحات المستخدمة في هذا الكتاب. فتشير الذاكرة الفيزيائيّة إلى خلايا التخزين في RAM. ولكلّ بايتٍ من الذاكرة الفيزيائيّة عنوانٌ يُسمّى العنوان الفيزيائيّ. والتعليمات التي تفسّر العناوين (مثل التحميل والتخزين والقفزات ونداءات الدوالّ) لا تستخدم إلّا عناوين افتراضيّة، يترجمها عتاد الصفحات إلى عناوين فيزيائيّة، ثمّ يرسلها إلى عتاد RAM لقراءة خلية التخزين أو الكتابة فيها. وفضاء العناوين هو مجموعة العناوين الافتراضيّة الصالحة في جدول صفحاتٍ معيَّن؛ ولكلّ عمليّة xv6 فضاء عناوين مستخدمٍ منفصل، ولنواة xv6 فضاء عناوينها الخاصّ هي أيضًا. وتشير ذاكرة المستخدم إلى فضاء عناوين مستخدم العمليّة مضافًا إليه الذاكرة الفيزيائيّة التي يسمح جدول الصفحات للعمليّة بالوصول إليها. وتشير الذاكرة الافتراضيّة (virtual memory) إلى الأفكار والتقنيّات المرتبطة بإدارة جداول الصفحات واستخدامها لتحقيق أهدافٍ كالعزل.

الشكل 3.3: على اليسار، فضاء العناوين الافتراضيّ لنواة xv6. وتشير RWX إلى أذونات القراءة والكتابة والتنفيذ في PTE. وعلى اليمين، فضاء العناوين الفيزيائيّة في RISC-V الذي تتوقّع xv6 رؤيته.

3.2 فضاء عناوين النواة

عند بدء تشغيلها، تُنشئ xv6 جدول صفحاتٍ وحيدًا يصف فضاء عناوين النواة. وتضبط النواة هيئة فضاء عناوينها لتمنح نفسها وصولًا إلى الذاكرة الفيزيائيّة وإلى موارد عتاديّة مختلفة عند عناوين افتراضيّةٍ متوقَّعةٍ. ويُبيّن الشكل 3.3 كيف تعيّن هذه الهيئة عناوين النواة الافتراضيّة إلى عناوين فيزيائيّة. ويُعلن الملفّ kernel/memlayout.h الثوابت الخاصّة بهيئة ذاكرة النواة في xv6.

يحاكي QEMU حاسوبًا يضمّ ذاكرة عشوائيّة (RAM) تبدأ عند العنوان الفيزيائيّ 0x80000000 وتمتدّ إلى 0x88000000 على الأقلّ، وهو ما تُسمّيه xv6 PHYSTOP. وتضمّ محاكاة QEMU أيضًا أجهزة إدخال/إخراج، كواجهة القرص. ويعرض QEMU واجهات الأجهزة على البرمجيّات في صورة مسجّلات تحكّمٍ معيَّنةٍ في الذاكرة (memory-mapped) واقعةٍ دون 0x80000000 في فضاء العناوين الفيزيائيّة. وتستطيع النواة التفاعل مع الأجهزة بقراءة تلك العناوين الفيزيائيّة الخاصّة والكتابة إليها؛ وهذه القراءات والكتابات تتواصل مع عتاد الجهاز لا مع الذاكرة العشوائيّة. ويشرح الفصل 4 كيف تتفاعل xv6 مع الأجهزة.

تعيّن النواة جميع صفحات الذاكرة العشوائيّة وسجلات الأجهزة عند عناوين افتراضيّةٍ مساويةٍ للعناوين الفيزيائيّة. ويُسمّى هذا «التعيين المباشر»، وهو يسمح للنواة بقراءة العنوان الفيزيائيّ $x$ أو الكتابة إليه ببساطةٍ بتحميل العنوان الافتراضيّ $x$ أو التخزين فيه. أمّا شيفرة النواة نفسها فموجودةٌ في KERNBASE=0x80000000 في فضاء العناوين الافتراضيّ وفي الذاكرة الفيزيائيّة معًا. وحين يخصّص kfork ذاكرة مستخدمٍ للعمليّة الابن، يُعيد المخصّص العنوان الفيزيائيّ لتلك الذاكرة؛ ويستخدم kfork ذلك العنوان مباشرةً بوصفه عنوانًا افتراضيًّا حين ينسخ ذاكرة مستخدم الأب إلى الابن.

وهناك عنوانان افتراضيّان خاصّان بالنواة غير معيَّنين مباشرةً:

• صفحة الترامبولين. فهي معيَّنةٌ في أعلى فضاء العناوين الافتراضيّ؛ وجداول صفحات المستخدم لها التعيين نفسه. ويناقش الفصل 4 دور صفحة الترامبولين، لكنّنا نرى هنا حالة استخدامٍ مثيرّةٍ للاهتمام لجداول الصفحات؛ فصفحةٌ فيزيائيّةٌ (تحتوي شيفرة الترامبولين) معيَّنةٌ مرّتين في فضاء العناوين الافتراضيّ للنواة: مرّةً في أعلى فضاء العناوين الافتراضيّ ومرّةً بتعيينٍ مباشر.
• صفحات مكدّس النواة. لكلّ عمليّةٍ مكدّس نواتها الخاصّ، وهو معيَّنٌ في عنوان افتراضيّ نواويّ عالٍ حتّى تستطيع xv6 أن تُخلي تحته صفحة حراسةٍ (guard page) غير معيَّنةٍ. فمدخلة جدول صفحات صفحة الحراسة غير صالحةٍ (أي أنّ PTE_V غير مضمومة)، حتّى إذا فاض مكدّس نواةٍ، فمن المرجّح أنّ ذلك يُسبّب خطأ صفحةٍ وأنّ النواة تُعلن هلعًا (panic). وبدون صفحة حراسةٍ، كان المكدّس الفائض سيدوّن فوق ذاكرة نواةٍ أخرى، فيؤدّي ذلك إلى تشغيلٍ غير صحيح. والانهيار بالهلع أفضل.

وبينما تستخدم النواة مكدّساتها عبر التعيينات في الذاكرة العليا، فإنّ كلّ مكدّسٍ متاحٌ للنواة أيضًا عبر عنوانٍ معيَّنٍ مباشرةً. وقد يقتصر تصميمٌ بديلٌ على التعيين المباشر وحده، ويستخدم المكدّسات عند العنوان المعيَّن مباشرةً. لكن في ذلك الترتيب، سيستلزم توفير صفحات الحراسة إلغاء تعيين عناوين افتراضيّةٍ كانت ستُشير إلى ذاكرةٍ فيزيائيّةٍ لولا ذلك، وهو ما سيصعب استخدامه بعدئذٍ.

وتعيّن النواة صفحات الترامبولين ونصّ النواة بالأذونات PTE_R وPTE_X، لا PTE_W. وتعيّن النواة الصفحات الأخرى بالأذونات PTE_R وPTE_W، لا PTE_X. والتعيينات الخاصّة بصفحات الحراسة غير صالحةٍ. والغرض من هذه الأذونات المقيَّدة هو المساعدة على كشف عُلَل النواة التي تصل إلى الصفحات بطرائق غير متوقَّعة، مثلًا إذا حاولت شيفرة النواة دون قصدٍ أن تدوّن فوق تعليمات النواة.

وتُنشئ النواة جدول صفحات نواةً وحيدًا، تستخدمه جميع وحدات المعالجة المركزيّة حين تنفّذ في النواة. ولا يعدّل xv6 جدول صفحات النواة بعد إنشائه ابتداءً.

3.3 الشيفرة: إنشاء فضاء عناوين

يُرجى قراءة kernel/vm.c حتّى نهاية mappages() قبل المضي.

وتقيم معظم شيفرة xv6 الخاصّة بالتلاعب بفضاءات العناوين وجداول الصفحات في vm.c. وبنية البيانات المركزيّة هي pagetable_t، وهي في الحقيقة مؤشّرٌ إلى صفحة جدول الصفحات الجذريّة في RISC-V؛ وقد تكون pagetable_t إمّا جدول صفحات النواة أو أحد جداول صفحات كلّ عمليّةٍ. والدوالّ المركزيّة هي walk، التي تجد المدخلة الخاصّة بعنوانٍ افتراضيّ، وmappages، التي تُثبّت المدخلات للمقابلات الجديدة. والدوالّ التي تبدأ بـkvm تتلاعب بجدول صفحات النواة؛ والدوالّ التي تبدأ بـuvm تتلاعب بجدول صفحات مستخدم؛ وغيرها يُستخدم لكليهما. وcopyout وcopyin تنسخان البيانات من وإلى عناوين المستخدم الافتراضيّة الممرَّرة كمعطيات نداء نظام؛ وهما في vm.c لأنّهما يلزمهما ترجمة تلك العناوين ترجمةً صريحةً للعثور على الذاكرة الفيزيائيّة المقابلة.

في وقتٍ مبكّرٍ من تسلسل الإقلاع، تنادي main الدالّة kvminit لإنشاء جدول صفحات النواة باستخدام kvmmake. ويقع هذا النداء قبل أن تُفعّل xv6 الصفحات في RISC-V، لذا تُشير العناوين إلى الذاكرة الفيزيائيّة مباشرةً. وتخصّص kvmmake أوّلًا صفحةً من الذاكرة الفيزيائيّة لتحمل صفحة جدول الصفحات الجذريّة. ثمّ تنادي kvmmap لتُثبّت الترجمات التي تحتاجها النواة. وتتضمّن تلك الترجمات تعليمات النواة وبياناتها، والذاكرة الفيزيائيّة حتّى PHYSTOP، ومدىً من الذاكرة هي في الحقيقة أجهزة. وتخصّص proc_mapstacks مكدّس نواةٍ لكلّ عمليّةٍ. وهي تنادي kvmmap لتعيين كلّ مكدّسٍ عند العنوان الافتراضيّ الذي يولّده KSTACK، وهو ما يُخلي مجالًا لصفحات حماية المكدّس غير الصالحة.

وتنادي kvmmap الدالّة mappages، التي تُثبّت مقابلاتٍ في جدول صفحاتٍ لمدىً من العناوين الافتراضيّة إلى مدىً مقابلٍ من العناوين الفيزيائيّة. وهي تفعل ذلك لكلّ عنوانٍ افتراضيٍّ في المدى على حدة، بفواصل الصفحات. ولكلّ عنوانٍ افتراضيٍّ يُعيَّن، تنادي mappages الدالّة walk للعثور على عنوان المدخلة الخاصّة بذلك العنوان. ثمّ تُهيّئ المدخلة لتحمل رقم الصفحة الفيزيائيّة المعنيّة، والأذونات المطلوبة (PTE_W وPTE_X و/أو PTE_R)، وPTE_V للإشارة إلى أنّ المدخلة صالحةٌ (vm.c:168).

وتحاكي walk عتاد الصفحات في RISC-V وهو يبحث عن المدخلة الخاصّة بعنوانٍ افتراضيّ (انظر الشكل 3.2). فتنزل walk في شجرة جدول الصفحات مستوىً واحدًا في كلّ مرّةٍ، مستعينةً بالـ9 بتّاتٍ من العنوان الافتراضيّ لكلّ مستوىٍ للفهرسة في صفحة دليل الصفحات المعنيّة. وفي كلّ مستوىٍ تجد إمّا مدخلة صفحة دليل الصفحات الخاصّة بالمستوى التالي، أو مدخلة الصفحة الأخيرة (vm.c:105). فإن لم تكن مدخلةٌ في صفحة دليل صفحات المستوى الأوّل أو الثاني صالحةً، فإنّ صفحة الدليل المطلوبة لم تُخصَّص بعد؛ فإذا ضُبط المعطى alloc، خصّصت walk صفحة جدول صفحاتٍ جديدةً ووضعت عنوانها الفيزيائيّ في المدخلة. وهي تُعيد عنوان المدخلة في الطبقة الأدنى في الشجرة (vm.c:115).

وتعتمد الشيفرة أعلاه على أنّ الذاكرة الفيزيائيّة معيَّنةٌ مباشرةً في فضاء العناوين الافتراضيّ للنواة. فمثلًا، بينما تنزل walk في مستويات جدول الصفحات، تجلب عنوان (فيزيائيّ) جدول صفحات المستوى الأدنى التالي من مدخلةٍ (vm.c:107)، ثمّ تستخدم ذلك العنوان بوصفه عنوانًا افتراضيًّا لإحضار المدخلة في المستوى الأدنى التالي (vm.c:105).

وفي كلّ وحدة معالجةٍ مركزيّة، تنادي main الدالّة kvminithart لتُثبّت جدول صفحات النواة، واضعةً العنوان الفيزيائيّ لصفحة جدول الصفحات الجذريّة في السجلّ satp الخاصّ بوحدة المعالجة المركزيّة. وبعد ذلك تترجم وحدة المعالجة المركزيّة العناوين باستخدام جدول صفحات النواة. وتستمرّ النواة في التنفيذ صحيحةً لأنّ جدول صفحات النواة معيَّنٌ مباشرةً، حتّى تُشير العناوين إلى المواضع نفسها في RAM قبل هذا التغيير وبعده.

وتُخزّن كلّ وحدة معالجةٍ مركزيّةٍ في RISC-V مدخلات جدول الصفحات في مخزن الترجمة الجانبيّ (TLB)، وحين يعدّل xv6 جدول صفحاتٍ، يلزمه أن يأمر وحدة المعالجة المركزيّة بإبطال مدخلات TLB المخزَّنة المقابلة. فلو لم يفعل ذلك، لربما استخدم TLB في وقتٍ لاحقٍ مقابلةً مخزَّنةً قديمةً تُشير إلى صفحةٍ فيزيائيّةٍ خُصّصت في هذه الأثناء لعمليّةٍ أخرى، ونتيجةً لذلك، قد تستطيع عمليّةٌ ما أن تخرب ذاكرة عمليّةٍ أخرى. ولدى RISC-V تعليمةٌ sfence.vma تُفرِّغ TLB وحدة المعالجة المركزيّة الحاليّة. وينفّذ xv6 التعليمة sfence.vma في kvminithart بعد إعادة تحميل السجلّ satp، وفي شيفرة الترامبولين الخاصّة بـuservec وuserret.

ومن الضروريّ أيضًا إصدار التعليمة sfence.vma قبل تغيير satp، وذلك لانتظار إتمام جميع عمليّات التحميل والتخزين المعلَّقة. وهذا الانتظار يضمن أنّ تحديثات جدول الصفحات السابقة قد أُتمّت، ويضمن أنّ عمليّات التحميل والتخزين السابقة تستخدم جدول الصفحات القديم لا الجديد.

3.4 تخصيص الذاكرة الفيزيائيّة

يلزم النواة أن تخصّص ذاكرةً فيزيائيّةً وتحرّرها زمن التشغيل من أجل جداول الصفحات، وذاكرة المستخدم، ومكدّسات النواة، ومخازن الأنابيب.

يستخدم xv6 الذاكرة الفيزيائيّة الواقعة بين نهاية النواة وPHYSTOP للتخصيص زمن التشغيل. وهو يخصّص ويحرّر صفحات كاملةً من 4096 بايت في كلّ مرّةٍ. وهو يتابع الصفحات الحرّة بخيط قائمةٍ مترابطةٍ تمرّ بالصفحات نفسها. فالتخصيص هو إزالة صفحةٍ من القائمة المترابطة؛ والتحرير هو إضافة الصفحة المحرَّرة إلى القائمة.

يُرجى قراءة kernel/kalloc.c.

3.5 الشيفرة: مخصّص الذاكرة الفيزيائيّة

ويقيم المخصّص في kalloc.c. وبنية بيانات المخصّص هي قائمة حرّة (free list) من صفحات الذاكرة الفيزيائيّة المتوفّرة للتخصيص. ومؤشّر «التالي» الخاصّ بكلّ صفحةٍ حرّةٍ يقيم في struct run. ويخزّن المخصّص بنية run الخاصّة بكلّ صفحةٍ حرّةٍ في الصفحة الحرّة نفسها، إذ لا شيء آخر مخزَّنٌ هناك ما دامت الصفحة حرّة. والقائمة الحرّة محميّةٌ بقفل تدويرٍ (kalloc.c:21-24). والقائمة والقفل ملفوفتان في بنية struct لِتَجَليّة أنّ القفل يحمي حقول البنية. وفي هذه الأثناء، تجاهل القفل ونداءَي acquire وrelease؛ وسيفحص الفصل 7 الأقفال بتفصيلٍ أكبر.

وتنادي الدالّة main الدالّة kinit لتهيئة المخصّص (kalloc.c:27). وتُهيّئ kinit القائمة الحرّة لتحمل كلّ صفحةٍ من الذاكرة العشوائيّة (RAM) الواقعة بين نهاية النواة وPHYSTOP. وكان على xv6 أن يحدّد مقدار الذاكرة الفيزيائيّة المتوفّرة بتحليل معلومات الضبط التي يوفّرها العتاد. لكنّه يفترض بدلًا من ذلك أنّ الجهاز يملك 128 ميغابايت من RAM. وتنادي kinit الدالّة freerange لإضافة ذاكرةٍ إلى القائمة الحرّة عبر نداءات kfree لكلّ صفحةٍ. ولا تستطيع المدخلة أن تُشير إلّا إلى عنوانٍ فيزيائيٍّ محاذٍ على حدّ 4096 بايت (أي مضاعفٍ لـ 4096)، لذا تستخدم freerange الدالّة PGROUNDUP لضمان تحرير عناوين فيزيائيّةٍ محاذاةٍ فقط. ويبدأ المخصّص بلا ذاكرةٍ؛ وهذه النداءات إلى kfree تمنحه شيئًا منها لإدارته.

ويتعامل المخصّص مع العناوين أحيانًا بوصفها أعدادًا صحيحةً لأداء حسابٍ عليها (مثلًا، اجتياز جميع الصفحات في freerange)، ويستخدمها أحيانًا أخرى كمؤشّراتٍ لقراءة الذاكرة والكتابة إليها (مثلًا، التلاعب ببنية run المخزّنة في كلّ صفحةٍ)؛ وهذا الاستخدام المزدوج للعناوين هو السبب الرئيسيّ في أنّ شيفرة المخصّص مملوءةٌ بتحويلات الأنواع في C.

تبدأ الدالّة kfree بضبط كلّ بايتٍ في الذاكرة التي تُحرَّر على القيمة 1. وهذا سيُسبّب قراءة الشيفرة التي تستخدم الذاكرة بعد تحريرها (أي التي تستخدم «مراجع معلّقة» (dangling references)) قمامةً بدلًا من المحتوى الصحيح القديم؛ ونأمل أن يجعل ذلك هذه الشيفرة تنكسر أسرع. ثمّ تُضيف kfree الصفحة إلى مقدّمة القائمة الحرّة: فهي تحوّل pa إلى مؤشّرٍ إلى struct run، وتسجّل بداية القائمة الحرّة القديمة في r->next، وتجعل القائمة الحرّة مساويةً لـr. وتُزيل kalloc أوّل عنصرٍ في القائمة الحرّة وتُعيده.

3.6 فضاء عناوين العمليّة

لكلّ عمليّةٍ جدول صفحاتها الخاصّ، وحين تبدّل xv6 بين العمليّات، فإنّها تُغيّر جداول الصفحات أيضًا. ويُظهر الشكل 3.4 فضاء عناوين عمليّةٍ بتفصيلٍ أكبر من الشكل 2.3. ويبدأ فضاء عناوين مستخدم العمليّة من الصفر وينتهي مبدئيًّا عند MAXVA (0x4000000000) (riscv.h:417)، وإنّه ليس في التطبيق إلّا جزءٌ صغيرٌ منه معيَّنٌ في ذاكرةٍ فيزيائيّة.

ويتألّف فضاء عناوين العمليّة من صفحاتٍ تحتوي نصّ البرنامج (وتعيّنه xv6 بالأذونات PTE_R، وPTE_X، وPTE_U)، وصفحاتٍ تحتوي بيانات البرنامج المهيّأة مسبقًا، وصفحةٍ للمكدّس، وصفحاتٍ للكومة. وتُعيّن xv6 البيانات والمكدّس والكومة بالأذونات PTE_R، وPTE_W، وPTE_U.

واستخدام الأذونات داخل فضاء عناوين المستخدم تقنيّةٌ شائعةٌ لتحصين عمليّة مستخدم. فلو عُيِّن النصّ بـPTE_W، لَكان في وسع عمليّةٍ ما أن تُعدّل برنامجها دون قصدٍ؛ فمثلًا، قد يُسبّب خطأٌ برمجيٌّ كتابة البرنامج إلى مؤشّرٍ معدومٍ، فيُعدّل التعليمات عند العنوان 0، ثمّ يواصل التشغيل، فلعلّه يُحدث فوضى أكبر. ولكشف هذه الأخطاء فورًا، تعيّن xv6 النصّ بغير PTE_W؛ فإذا حاول برنامجٌ دون قصدٍ أن يخزّن إلى العنوان 0، سيرفض العتاد تنفيذ التخزين وسيرفع خطأ صفحةٍ (انظر الفصل 4). ثمّ تقتل النواة العمليّة وتطبع رسالةً مُفيدةً حتّى يستطيع المطوّر تتبّع المشكلة.

وبالمثل، بتعيين البيانات بغير PTE_X، لا يستطيع برنامج مستخدمٍ أن يقفز دون قصدٍ إلى عنوانٍ في بيانات البرنامج ويبدأ التنفيذ عند ذلك العنوان.

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

والمكدّس صفحةٌ واحدة، ويُعرَض بمحتواه الأوّليّ كما أنشأه نداء النظام exec. فالنصوص التي تحتوي معطيات سطر الأوامر، وكذلك مصفوفة المؤشّرات إليها، تقع في أعلى المكدّس تمامًا. وتحتها مباشرةً قيمٌ تسمح لبرنامجٍ بالبدء عند main كأنّ الدالّة main(argc، argv) قد نُوديت للتوّ.

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

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

الشكل 3.4: فضاء عناوين مستخدم عمليّةٍ، مع مكدّسه الأوّليّ.

3.7 الشيفرة: exec

يُرجى قراءة kernel/exec.c وkernel/vm.c بدءًا من uvmcreate().

exec نداء نظامٍ يستبدل فضاء عناوين مستخدم العمليّة ببياناتٍ تُقرَأ من ملفٍّ يُسمّى ملفًّا ثنائيًّا أو تنفيذيًّا. والملفّ الثنائيّ هو عادةً مخرج المصرِّف والرابط، ويحتوي تعليمات الآلة وبيانات البرنامج. وkexec، وهو التنفيذ الداخليّ في النواة لـexec، يفتح الملفّ الثنائيّ المسمّى path باستخدام namei، الذي يُشرَح في الفصل 10. ثمّ يقرأ ترويسة ELF. والملفّات الثنائيّة في xv6 منسّقةٌ بصيغة ELF الشائعة الاستخدام، المعرَّفة في (elf.h). ويتألّف الملفّ الثنائيّ ELF من ترويسة ELF، struct elfhdr، يتبعها تسلسلٌ من ترويسات أقسام البرنامج، struct proghdr. وتصف كلّ proghdr قسمًا من التطبيق يلزم تحميله في الذاكرة؛ وبرامج xv6 لها ترويستا قسم برنامج: واحدةٌ للتعليمات وأخرى للبيانات.

والخطوة الأولى هي تحقّقٌ سريع من أنّ الملفّ يحوي على الأرجح ملفًّا ثنائيًّا ELF. ويبدأ الملفّ الثنائيّ ELF بـ«الرقم السحريّ» ذي البايتات الأربعة 0x7F، E'`، L'، ``F'، أو ELF_MAGIC. فإذا كان لترويسة ELF الرقم السحريّ الصحيح، تفترض kexec أنّ الملفّ الثنائيّ حسن التكوين.

يخصّص kexec جدول صفحاتٍ جديدًا بلا مقابلات مستخدمٍ باستخدام proc_pagetable، ويخصّص ذاكرةً لكلّ مقطع ELF باستخدام uvmalloc، ويحمّل كلّ مقطعٍ في الذاكرة باستخدام loadseg. ويستخدم loadseg الدالّة walkaddr للعثور على العنوان الفيزيائيّ للذاكرة المخصّصة التي تُكتب فيها كلّ صفحةٍ من مقطع ELF، والدالّة readi للقراءة من الملفّ.

وتبدو ترويسة قسم البرنامج الخاصّة بـ/init، أوّل برنامج مستخدمٍ يُنشَأ بـkexec، هكذا:

# objdump -p user/_init

user/_init:     file format elf64-little

Program Header:
0x70000003 off    0x0000000000006bb0 vaddr 0x0000000000000000
                                       paddr 0x0000000000000000 align 2**0
         filesz 0x000000000000004a memsz 0x0000000000000000 flags r--
    LOAD off    0x0000000000001000 vaddr 0x0000000000000000
                                       paddr 0x0000000000000000 align 2**12
         filesz 0x0000000000001000 memsz 0x0000000000001000 flags r-x
    LOAD off    0x0000000000002000 vaddr 0x0000000000001000
                                       paddr 0x0000000000001000 align 2**12
         filesz 0x0000000000000010 memsz 0x0000000000000030 flags rw-
   STACK off    0x0000000000000000 vaddr 0x0000000000000000
                                       paddr 0x0000000000000000 align 2**4
         filesz 0x0000000000000000 memsz 0x0000000000000000 flags rw-

ونرى أنّ مقطع النصّ يلزم تحميله في الذاكرة عند العنوان الافتراضيّ 0x0 (بلا أذونات كتابةٍ) من محتوى يقع عند الإزاحة 0x1000 في الملفّ. ونرى أيضًا أنّ البيانات يلزم تحميلها عند العنوان 0x1000، الواقع على حدّ صفحةٍ، وبلا أذونات تنفيذٍ.

وقد يكون filesz في ترويسة قسم البرنامج أقلّ من memsz، وهو ما يدلّ على أنّ الفراغ بينهما يلزم أن يُملأ أصفارًا (خاصّةً بالمتغيّرات العامّة في C) لا أن يُقرَأ من الملفّ. فبالنسبة إلى /init، filesz البيانات هو 0x10 بايت وmemsz هو 0x30 بايت، وبذلك تخصّص uvmalloc ذاكرةً فيزيائيّةً تكفي لاحتواء 0x30 بايت، لكنّها لا تقرأ من الملفّ /init إلّا 0x10 بايت.

والآن يخصّص kexec مكدّس المستخدم ويُهيّئه. وهو لا يخصّص إلّا صفحة مكدّسٍ واحدة. وينسخ kexec نصوص المعطيات إلى أعلى المكدّس واحدةً تلو الأخرى، مسجّلًا المؤشّرات إليها في ustack. ويضع مؤشّرًا معدومًا في نهاية ما سيصبح قائمة argv الممرَّرة إلى main. أمّا قيمتا argc وargv فتُمرَّران إلى main عبر مسار عودة نداء النظام: argc يُمرَّر عبر قيمة عودة نداء النظام، التي تذهب في a0، وargv يُمرَّر عبر مدخلة a1 في إطار المصيدة الخاصّ بالعمليّة.

يضع kexec صفحةً لا يمكن الوصول إليها تحت صفحة المكدّس مباشرةً، حتّى تفشل البرامج التي تحاول استخدام أكثر من صفحةٍ واحدة. وتسمح هذه الصفحة غير القابلة للوصول لـkexec أيضًا بالتعامل مع المعطيات الكبيرة أكثر من اللزوم؛ ففي تلك الحالة، ستلاحظ الدالّة copyout التي يستخدمها kexec لنسخ المعطيات إلى المكدّس أنّ صفحة الوجهة غير قابلةٍ للوصول، وستُعيد -1.

وأثناء تهيئة صورة الذاكرة الجديدة، إذا كشف kexec خطأً كَمقطع برنامجٍ غير صالحٍ، فإنّه يقفز إلى البطاقة bad، ويحرّر الصورة الجديدة، ويُعيد -1. وينبغي أن ينتظر kexec تحرير الصورة القديمة حتّى يتأكّد من أنّ نداء النظام سينجح: فإذا كانت الصورة القديمة قد أُزيلت، فلن يستطيع نداء النظام إعادة -1 إليها. وحالات الخطأ الوحيدة في kexec تقع أثناء إنشاء الصورة. وما أن تكتمل الصورة حتّى يستطيع kexec الالتزام بجدول الصفحات الجديد (exec.c:134) وتحرير القديم (exec.c:138).

يحمّل نداء النظام exec بايتات من الملفّ ELF إلى الذاكرة عند عناوين يحدّدها الملفّ نفسه. ويستطيع المستخدمون أو العمليّات أن يضعوا في ملفّ ELF أيّ عناوين يشاؤون. ولذلك فإنّ exec أمرٌ خطر، لأنّ العناوين في الملفّ قد تُشير إلى النواة، سهوًا أو بقصدٍ. وأمّا النتائج على نواةٍ غير حذرةٍ فقد تتراوح بين الانهيار وخرقٍ خبيثٍ لآليّات عزل النواة (أي استغلالٍ أمنيّ). ويُجرِي xv6 عدّة تحقّقاتٍ لتجنّب هذه المخاطر. فمثلًا، يتحقّق if(ph.vaddr + ph.memsz < ph.vaddr) من أنّ المجموع لا يفيض عددًا صحيحًا من 64 بتًّا. والخطر هو أنّ مستخدمًا ما قد يبني ملفًّا ثنائيًّا بـph.vaddr يُشير إلى عنوانٍ يختاره هو، وبـph.memsz كبيرٍ بما يكفي لأن يفيض المجموع إلى 0x1000، وهو ما سيبدو قيمةً صالحةً. وفي إصدارٍ أقدم كانت فضاءات عناوين المستخدم تحتوي النواة هي أيضًا (لكن دون إمكانيّة القراءة/الكتابة في وضع المستخدم)، فكان في وسع المستخدم أن يختار عنوانًا يقابل ذاكرة النواة فينسخ بذلك بيانات من الملفّ الثنائيّ إلى النواة. أمّا في إصدار xv6 الخاصّ بـRISC-V فلا يمكن أن يحدث ذلك، لأنّ للنواة جدول صفحاتها المنفصل؛ فـloadseg يحمّل في جدول صفحات العمليّة لا في جدول صفحات النواة.

ومن السهل على مطوّر نواةٍ أن يغفل تحقّقًا حاسمًا، وللأنوية في العالم الحقيقيّ تاريخٌ طويلٌ من التحقّقات الناقصة التي يمكن لبرامج المستخدم استغلال غيابها لنيل صلاحيّات النواة. ومن المرجّح أنّ xv6 لا يؤدّي عملًا كاملًا في التحقّق من بيانات مستوى المستخدم المُمرَّرة إلى النواة، وهو ما قد يستطيع برنامج مستخدمٍ خبيثٌ استغلاله للتحايل على عزل xv6.

3.8 عالم الواقع

ومعظم نظم التشغيل، مثلها في ذلك مثل xv6، تستخدم عتاد الصفحات لحماية الذاكرة وتعيينها. غير أنّ معظم نظم التشغيل تستخدم الصفحات استخدامًا أرقى بكثيرٍ ممّا يفعل xv6، بجمعها بين الصفحات واستثناءات أخطاء الصفحات، وهي التي سنناقشها في الفصل 4.

ويبسُط xv6َ استخدام النواة خريطةً مباشرةً بين العناوين الافتراضيّة والفيزيائيّة، وافتراضها وجود RAM فيزيائيّة عند العنوان 0x80000000، حيث تتوقّع النواة أن تُحمَّل. وهذا ينفع مع QEMU، لكنّه اتّضح أنّه فكرةٌ سيّئةٌ على العتاد الحقيقيّ؛ فالعتاد الحقيقيّ يضع RAM والأجهزة عند عناوين فيزيائيّةٍ غير متوقَّعةٍ، حتّى إنّه (مثلًا) قد لا تكون هناك RAM عند 0x80000000، حيث تتوقّع xv6 أن تتمكّن من تخزين النواة. وتستثمر تصاميم الأنوية الأجدّ جدول الصفحات لتحويل هيئات ذاكرة العتاد الفيزيائيّة التعسّفيّة إلى هيئات عناوين افتراضيّةٍ متوقَّعةٍ للنواة.

ويدعم RISC-V الحماية على مستوى العناوين الفيزيائيّة، لكنّ xv6 لا يستخدم تلك الميزة.

وعلى الآلات ذات الذاكرة الكثيرة، قد يكون من المنطقيّ الاستعانة بدعم RISC-V لـ«الصفحات الضخمة (super pages)». فالصفحات الصغيرة مناسبةٌ حين تكون الذاكرة الفيزيائيّة ضئيلة، لأنّها تسمح بالتخصيص وبالإخراج إلى القرص بدقّةٍ ناعمةٍ. فمثلًا، إذا كان برنامجٌ ما يستخدم 8 كيلوبايت فقط من الذاكرة، فمنحه صفحةً ضخمةً كاملةً من الذاكرة الفيزيائيّة سعةً 4 ميغابايت مضيعةٌ. والصفحات الأكبر مناسبةٌ على الآلات ذات RAM الكثيرة، وقد تُخفّض أعباء التلاعب بجدول الصفحات.

ولتجنّب الاضطرار إلى إفراغ TLB كاملًا عند تغيير جداول الصفحات، قد تدعم وحدات المعالجة المركزيّة في RISC-V معرّفات فضاءات العناوين (ASIDs) (ووترمان وآخرون 2024). وعندها تستطيع النواة أن تُفرّغ مدخلات TLB الخاصّة بفضاء عناوين معيَّنٍ فحسب. ولا يستخدم xv6 هذه الميزة.

وافتقار نواة xv6 إلى مخصّصٍ على شاكلة malloc يستطيع توفير ذاكرةٍ للأجسام الصغيرة يمنع النواة من استخدام بنيات بياناتٍ متطوّرةٍ تلزم تخصيصًا ديناميكيًّا. وكانت نواةٌ أكثر تفصيلًا لتُخصّص أحجامًا مختلفةً كثيرةً من الكتل الصغيرة، بدلًا من (كما في xv6) كتل 4096 بايت فقط؛ ومخصّص نواةٍ حقيقيّ يلزمه أن يتعامل مع التخصيصات الصغيرة والكبيرة معًا.

وتخصيص الذاكرة موضوعٌ دائم الحدّة، وأهمّ مشكلاته استخدامٌ كفؤٌ لذاكرةٍ محدودةٍ والاستعداد لطلباتٍ مستقبليّةٍ مجهولةٍ (كنوث 1997). والناس اليوم يهتمّون بالسرعة أكثر من اهتمامهم بكفاءة المساحة.