مرحبا يا هبر! أقدم لكم ترجمة المقال "مؤشرات معقدة ، أو: ما في البايت؟" تأليف رالف يونغ.
أعمل هذا الصيف في Rust بدوام كامل مرة أخرى ، وسأعمل مجددًا (من بين أشياء أخرى) على "نموذج ذاكرة" لنظام Rust / MIR. ومع ذلك ، قبل أن أتحدث عن أفكاري ، يجب أخيرًا تبديد الأسطورة القائلة بأن "المؤشرات بسيطة: إنها مجرد أرقام". كلا الجزأين من هذا البيان خاطئان ، على الأقل في اللغات ذات الميزات غير الآمنة ، مثل Rust أو C: لا يمكن تسمية المؤشرات إما بالأرقام الأولية أو (العادية).
أود أيضًا مناقشة جزء نموذج الذاكرة الذي يجب معالجته قبل أن نتحدث عن الأجزاء الأكثر تعقيدًا: في أي شكل يتم تخزين البيانات في الذاكرة؟ تتكون الذاكرة من وحدات البايت ، والحد الأدنى من الوحدات القابلة للعنونة وأصغر العناصر التي يمكن الوصول إليها (على الأقل في معظم الأنظمة الأساسية) ، ولكن ما هي قيم البايت المحتملة؟ مرة أخرى ، اتضح أن "إنه مجرد رقم 8 بت" غير مناسب كإجابة.
آمل أنه بعد قراءة هذا المنشور ، سوف تتفق معي بشأن كلا البيانين.
المؤشرات معقدة
ما هي المشكلة مع "المؤشرات هي أرقام منتظمة"؟ لنلقِ نظرة على المثال التالي: (أستخدم C ++ هنا ، لأن كتابة التعليمات البرمجية غير الآمنة في C ++ أسهل من الكتابة في Rust ، والكود غير الآمن هو فقط المكان الذي تظهر فيه المشكلات. تعاني Insecure Rust و C من نفس المشاكل التي و C ++).
int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; int i = ; auto x_ptr = &x[i]; *x_ptr = 23; return y[0]; }
يعد تحسين القراءة الأخيرة لـ y [0] بعودة 42 مفيدًا دائمًا. الأساس المنطقي لهذا التحسين هو أن تغيير x_ptr الذي يشير إلى x لا يمكن تغيير ذ.
ومع ذلك ، عند التعامل مع لغات منخفضة المستوى مثل C ++ ، يمكننا انتهاك هذا الافتراض بتعيين i yx value. نظرًا لأن & x [i] هي نفس x + i ، نكتب 23 في & y [0].
بالطبع ، هذا لا يمنع مترجمين C ++ من القيام بهذه التحسينات. لحل هذه المشكلة ، يشير المعيار إلى أن الكود الخاص بنا يحتوي على UB .
أولاً ، لا يُسمح بإجراء عمليات حسابية على المؤشرات (كما في حالة & x [i]) ، إذا تجاوز المؤشر في هذه الحالة أي من حدود المصفوفة . ينتهك برنامجنا هذه القاعدة: x [i] يتجاوز x ، لذلك هو UB. بمعنى آخر ، حتى حساب قيمة x_ptr هو UB ، لذلك نحن لا نصل إلى المكان الذي نريد استخدام هذا المؤشر فيه.
(اتضح أن i = yx هي UB أيضًا ، حيث إن المؤشرات التي تشير إلى نفس تخصيص الذاكرة فقط هي المسموح بطرحها . ومع ذلك ، يمكننا كتابة i = ((size_t) y - (size_t) x) / sizeof (int) لتجاوز هذا هو القيد.)
لكننا لم ننته بعد: هذه القاعدة لديها الاستثناء الوحيد الذي يمكننا استخدامه لمصلحتنا. إذا كانت العملية الحسابية تحسب قيمة المؤشر إلى العنوان بعد نهاية المصفوفة تمامًا ، فسيتم ترتيب كل شيء. (هذا الاستثناء مطلوب لحساب vec.end () للحلقات الأكثر شيوعًا في C ++ 98.)
دعنا نغير المثال قليلا:
int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; auto x_ptr = x+8;
الآن تخيل أنه تم تخصيص x و y واحدة تلو الأخرى ، مع أن y لها عنوان أكبر. ثم تشير x_ptr إلى بداية y! ثم الشرط صحيح وتحدث المهمة. في الوقت نفسه ، لا يوجد أي UB بسبب خروج المؤشر في الخارج.
يبدو أن هذا لن يسمح بالتحسين. ومع ذلك ، يحتوي المعيار C ++ على غلاف آخر لمساعدة منشئي برنامج التحويل البرمجي: في الواقع ، لا يسمح لنا باستخدام x_ptr. وفقًا لما يقوله المعيار حول إضافة الأرقام إلى المؤشرات ، يشير x_ptr إلى العنوان بعد العنصر الأخير للصفيف. لا يشير إلى عنصر محدد لكائن آخر ، حتى إذا كان لديهم نفس العنوان . (على الأقل هذا تفسير شائع للمعيار استنادًا إلى قيام LLVM بتحسين هذا الرمز .)
وعلى الرغم من أن x_ptr و & y [0] يشيران إلى العنوان نفسه ، فإن هذا لا يجعلهما المؤشر نفسه ، أي أنه لا يمكن استخدامها بالتبادل: & y [0] يشير إلى العنصر الأول من y؛ يشير x_ptr إلى العنوان بعد x. إذا استبدلنا * x_ptr = 23 بالسلسلة * & y [0] = 0 ، فسنغير قيمة البرنامج ، على الرغم من أن المؤشرين قد تم التحقق منهما من أجل المساواة.
هذا يستحق التكرار:
فقط لأن مؤشرين يشيران إلى نفس العنوان لا يعنيان أنهما متساويان ويمكن استخدامهما بالتبادل.
نعم ، هذا الاختلاف بعيد المنال. في الواقع ، لا يزال هذا يسبب اختلافات في البرامج المترجمة باستخدام LLVM و GCC.
لاحظ أيضًا أن هذه القاعدة الواحدة ليست هي المكان الوحيد في C / C ++ حيث يمكننا ملاحظة مثل هذا التأثير. مثال آخر هو تقييد الكلمات الرئيسية في C ، والتي يمكن استخدامها للتعبير عن عدم تداخل المؤشرات (ليست متساوية):
int foo(int *restrict x, int *restrict y) { *x = 42; if (x == y) { *y = 23; } return *x; } int test() { int x; return foo(&x, &x); }
استدعاء الاختبار () يستدعي UB ، حيث لا يجب أن يحدث وصولان للذاكرة في foo في نفس العنوان. استبدال * y بـ * x في foo ، سنقوم بتغيير قيمة البرنامج ، ولن ندعو UB بعد الآن. مرة أخرى: على الرغم من أن x و y لهما نفس العنوان ، إلا أنهما لا يمكن استخدامهما بالتبادل.
المؤشرات هي بالتأكيد ليست مجرد أرقام.
نموذج مؤشر بسيط
إذن ما هو المؤشر؟ أنا لا أعرف الجواب الكامل. في الواقع ، هذا مجال مفتوح للبحث.
نقطة واحدة مهمة: هنا نحن ننظر إلى نموذج مؤشر مجردة . بالطبع ، على جهاز كمبيوتر حقيقي ، المؤشرات هي أرقام. لكن الكمبيوتر الحقيقي لا ينفذ التحسينات التي يقوم بها مترجمو C ++ الحديثة. إذا كتبنا البرامج المذكورة أعلاه في المجمع ، فلن يكون هناك أي UB ، لا تحسينات. تتخذ C ++ و Rust مقاربة أكثر "مستوى أعلى" للذاكرة والمؤشرات ، مما يحد المبرمج من المترجم. عندما يكون من الضروري وصف ما يمكن للمبرمج القيام به ولا يمكنه فعله بهذه اللغات ، يتم تحطيم نموذج المؤشرات كأرقام ، لذلك نحن بحاجة إلى العثور على شيء آخر. هذا مثال آخر على استخدام "جهاز افتراضي" يختلف عن جهاز كمبيوتر حقيقي لأغراض المواصفات - فكرة كتبت عنها سابقًا .
فيما يلي جملة بسيطة (في الواقع ، يتم استخدام هذا النموذج من المؤشرات بواسطة CompCert وعملي من قبل RustBelt ، وكذلك الطريقة التي ينفذ بها مترجم miri المؤشرات ): المؤشر عبارة عن زوج من بعض المعرفات يحدد منطقة ذاكرة بشكل فريد (التخصيص) ، والإزاحة بالنسبة إلى هذه المنطقة. إذا كتبت هذا في Rust:
struct Pointer { alloc_id: usize, offset: isize, }
تؤثر عمليات إضافة (طرح) رقم إلى مؤشر (من مؤشر) على الإزاحة فقط ، وبالتالي لا يمكن للمؤشر مغادرة منطقة الذاكرة أبدًا. يكون طرح مؤشرات ممكنًا فقط إذا كانت تنتمي إلى نفس مساحة الذاكرة (وفقًا لـ C ++ ).
(كما نرى ، يطبق معيار C ++ هذه القواعد على المصفوفات ، وليس مناطق الذاكرة. ومع ذلك ، فإن LLVM يطبقها على مستوى المنطقة .)
اتضح (ويظهر ميري الشيء نفسه) أن هذا النموذج يمكن أن يخدمنا بشكل جيد. نتذكر دائمًا منطقة الذاكرة التي ينتمي إليها المؤشر ، حتى نتمكن من تمييز المؤشر الواحد تلو الآخر من منطقة الذاكرة من المؤشر إلى بداية منطقة أخرى. وهكذا قد تجد ميري أن المثال الثاني (مع & x [8]) له UB.
نموذجنا ينهار
في نموذجنا ، المؤشرات ، على الرغم من أنها ليست أرقام ، فهي بسيطة على الأقل. ومع ذلك ، سيبدأ هذا النموذج في الانهيار أمام أعيننا ، بمجرد أن تتذكر تحويل المؤشرات إلى أرقام. في miri ، لا يؤدي إطلاق مؤشر إلى رقم إلى شيء في الواقع ، فنحن فقط نحصل على متغير رقمي (على سبيل المثال ، يشير نوعه إلى أنه رقم) تكون قيمته عبارة عن مؤشر (على سبيل المثال ، زوج من مساحة الذاكرة والإزاحة). ومع ذلك ، يؤدي ضرب هذا الرقم في 2 إلى حدوث خطأ ، لأنه من غير الواضح تمامًا ما يعنيه "ضرب مثل هذا المؤشر المجرد في 2".
يجب أن أوضح: هذا ليس حلاً جيدًا عندما يتعلق الأمر بتعريف دلالات اللغة. ومع ذلك ، هذا يعمل بشكل جيد للمترجم. هذا هو النهج الأبسط ، وقد اخترناه لأنه ليس من الواضح كيف يمكن القيام به بطريقة أخرى (باستثناء عدم دعم مثل هذه التخفيضات على الإطلاق - ولكن مع دعمهم يمكن أن تقوم ميري بتشغيل المزيد من البرامج): في جهازنا المجرد لا توجد "مساحة عنوان" واحدة ، حيث سيتم تحديد كافة مناطق الذاكرة المخصصة ، وتم تعيين كافة المؤشرات لأرقام مختلفة محددة. يتم تعريف كل منطقة الذاكرة بمعرف (مخفي). الآن يمكننا البدء في إضافة بيانات إضافية إلى نموذجنا ، مثل العنوان الأساسي لكل منطقة ذاكرة ، واستخدامه بطريقة ما لإعادة الرقم إلى المؤشر ... وفي هذه المرحلة تصبح العملية معقدة للغاية ، وعلى أي حال ، مناقشة لهذا النماذج ليست غرض كتابة منشور. والغرض منه هو مناقشة الحاجة إلى مثل هذا النموذج. إذا كنت مهتمًا ، أوصي بأن تقرأ هذا المستند ، والذي يلقي نظرة فاحصة على الفكرة المذكورة أعلاه المتمثلة في إضافة عنوان أساسي.
باختصار ، إن أشكال المؤشرات والأرقام لبعضها البعض مربكة ويصعب تحديدها بشكل رسمي ، بالنظر إلى التحسينات التي تمت مناقشتها أعلاه. يوجد تعارض بين النهج رفيع المستوى اللازم للتحسينات والنهج المنخفض المستوى المطلوب لوصف مؤشرات الصب على الأرقام والعكس. بالنسبة للجزء الأكبر ، نحن ببساطة نتجاهل هذه المشكلة في ميري ونحاول ، كلما كان ذلك ممكنًا ، القيام بأكبر قدر ممكن باستخدام النموذج البسيط الذي نتعامل معه. بالطبع ، لا يمكن أن يذهب التعريف الكامل للغات مثل C ++ أو Rust ، بطريقة بسيطة ، بل يجب أن يوضح ما يحدث بالفعل. على حد علمي ، لا يوجد حل مناسب ، لكن البحث الأكاديمي يقترب من الحقيقة .
هذا هو السبب في أن المؤشرات ليست بسيطة أيضًا.
من المؤشرات إلى البايت
آمل أن يكون لدي حجة مقنعة مفادها أن الأرقام ليست هي نوع البيانات الوحيد الذي يجب مراعاته إذا كنا نريد وصف اللغات ذات المستوى المنخفض رسميًا مثل C ++ أو الجزء (غير الآمن) من Rust. ومع ذلك ، هذا يعني أن العملية البسيطة مثل قراءة بايت من الذاكرة لا يمكنها فقط إرجاع u8. تخيل أننا نطبق memcpy من خلال قراءة كل بايت من المصدر بدوره إلى بعض المتغيرات المحلية v ، ثم تخزين هذه القيمة في الموقع المستهدف. ولكن ماذا لو كانت هذه البايتة جزءًا من مؤشر؟ إذا كان المؤشر عبارة عن زوج من معرف منطقة الذاكرة وإزاحة ، فما هو البايت الأول؟ نحتاج أن نقول ما قيمة v تساوي ، لذلك سيكون علينا الإجابة على هذا السؤال بطريقة أو بأخرى. (وهذه مشكلة مختلفة تمامًا عن مشكلة الضرب ، والتي كانت في القسم السابق. نفترض فقط أن هناك نوعًا مجردة من Ponter.)
لا يمكننا تمثيل بايت المؤشر كقيمة للنطاق 0..256 (ملاحظة: فيما يلي 0 ، لم يتم تشغيل 256). بشكل عام ، إذا استخدمنا نموذج تمثيل ساذج للذاكرة ، فسيتم فقد الجزء "المخفي" الإضافي من المؤشر (الذي يجعله أكثر من مجرد رقم) عند كتابة المؤشر على الذاكرة وإعادة قراءته منه. سيتعين علينا إصلاح هذا الأمر ، ولهذا يتعين علينا توسيع مفهوم "البايت" لتمثيل هذه الحالة الإضافية. وبالتالي ، أصبحت البايت الآن إما قيمة النطاق 0..256 ("البتات الأولية") ، أو البايتة التاسعة في بعض المؤشرات المجردة. إذا اضطررنا إلى تطبيق نموذج ذاكرتنا في Rust ، فقد يبدو الأمر كما يلي:
enum ByteV1 { Bits(u8), PtrFragment(Pointer, u8), }
على سبيل المثال ، PtrFragment (ptr ، 0) يمثل البايت الأول من مؤشر ptr. وبالتالي ، يمكن لـ memcpy "تقسيم" المؤشر إلى وحدات بايت منفصلة تمثل هذا المؤشر في الذاكرة ، ونسخها بشكل فردي. على بنية 32 بت ، سيحتوي تمثيل ptr الكامل على 4 بايت:
[PtrFragment(ptr, 0), PtrFragment(ptr, 1), PtrFragment(ptr, 2), PtrFragment(ptr, 3)]
يدعم هذا التمثيل جميع عمليات نقل البيانات عبر المؤشرات على مستوى البايت ، وهو ما يكفي تمامًا للبطاقة. العمليات الحسابية أو عمليات البت غير مدعومة بالكامل ؛ كما ذكر أعلاه ، فإن هذا يتطلب تمثيل أكثر تعقيدًا للمؤشرات.
ذاكرة غير مهيأة
ومع ذلك ، لم ننته من تعريفنا لـ "البايت". لوصف سلوك البرنامج بشكل كامل ، نحتاج إلى التفكير في خيار آخر: البايت في الذاكرة يمكن أن يكون غير مهيأ . سيبدو تعريف البايت الأخير بهذا الشكل (لنفترض أن لدينا نوع مؤشر للمؤشرات):
enum Byte { Bits(u8), PtrFragment(Pointer, u8), Uninit, }
نستخدم قيمة Uninit لجميع وحدات البايت في الذاكرة المخصصة التي لم نكتب فيها أي قيمة بعد. من الممكن قراءة ذاكرة غير مهيأة دون مشاكل ، ولكن أي إجراءات أخرى باستخدام هذه البايتات (على سبيل المثال ، حساب رقمي) تؤدي إلى UB.
هذا يشبه إلى حد كبير قواعد LLVM فيما يتعلق بقيمة السم الخاصة. لاحظ أن LLVM لها أيضًا قيمة غير معزولة ، والتي تُستخدم للذاكرة غير المهيأة وتعمل بشكل مختلف قليلاً. ومع ذلك ، فإن تجميع Uninit to unef الخاص بك هو الصحيح (undef هو "أضعف" في بعض النواحي) ، وهناك اقتراحات لإزالة undef من LLVM واستخدام السم بدلاً من ذلك .
قد تتساءل لماذا لدينا قيمة Uninit خاصة على الإطلاق. لماذا لا تختار بعض التعسفي b: u8 لكل بايت جديد ، ثم استخدم Bits (b) كقيمة أولية؟ هذا هو حقا خيار واحد. ومع ذلك ، بادئ ذي بدء ، جاءت جميع المجمعين إلى النهج باستخدام قيمة خاصة للذاكرة غير مهيأ. لا يعني اتباع هذا النهج ليس فقط التسبب في مشاكل الترجمة من خلال LLVM ، ولكن أيضًا مراجعة جميع التحسينات والتأكد من أنها تعمل بشكل صحيح مع هذا النموذج المعدل. النقطة الأساسية هنا: يمكنك دائمًا استبدال Uninit بأمان بأي قيمة أخرى: أي عملية تلقي هذه القيمة ستؤدي في أي حال إلى UB.
على سبيل المثال ، يعد تحسين كود C أسهل مع Uninit:
int test() { int x; if (condA()) x = 1;
مع Uninit ، يمكننا أن نقول بسهولة أن x له إما قيمة Uninit أو قيمة 1 ، ومنذ استبدال Uninit بـ 1 أعمال ، يمكن شرح التحسين بسهولة. بدون Uninit ، x إما "نوع من أنواع البت التعسفي" أو 1 ، ويصعب شرح التحسين الأمثل.
(يمكننا القول إنه يمكننا مبادلة العمليات عندما نتخذ قرارًا غير حاسم ، ولكن بعد ذلك نحتاج إلى إثبات أن الشفرة التي يصعب تحليلها لا تستخدم x بأي شكل من الأشكال. Uninit يتجنب هذه المشكلة بأدلة غير ضرورية.)
أخيرًا ، Uninit هو الخيار الأفضل للمترجمين الفوريين مثل miri. يواجه هؤلاء المترجمون الفوريون مشاكل في عمليات مثل "مجرد اختيار أي من هذه القيم" (أي ، العمليات غير القطعية) ، حيث يميلون إلى متابعة جميع المسارات الممكنة لتنفيذ البرنامج ، مما يعني أنهم بحاجة إلى تجربة كل القيم الممكنة. استخدام Uninit بدلاً من نمط بت تعسفي يعني أنه يمكن لـ miri إخبارك بعد تشغيل أحد البرامج ما إذا كان البرنامج يستخدم قيمًا غير مهيأة بشكل غير صحيح.
استنتاج
لقد رأينا أنه في لغات مثل C ++ و Rust (على عكس أجهزة الكمبيوتر الحقيقية) ، يمكن أن تكون المؤشرات مختلفة حتى لو كانت تشير إلى نفس العنوان ، وأن البايت أكثر من مجرد رقم في النطاق 0..256. لذلك ، إذا كانت اللغة C في عام 1978 يمكن أن تكون "مجمّع متنقل" ، فهي الآن عبارة خاطئة بشكل لا يصدق.