مكدس الاستدعاءات

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

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

بما أن مكدس الاستدعاءات مُنظّم على شكل مكدس ، فإن مُستدعي الإجراء، أو مقدمة ذلك الإجراء، يدفع عنوان الإرجاع إلى المكدس، وعند انتهاء الإجراء الفرعي المُستدعى، يسحب عنوان الإرجاع من مكدس الاستدعاءات وينقل التحكم إلى ذلك العنوان؛ وبالمثل، تدفع مقدمة كتلة مضمنة إطار مكدس، وتسحبه خاتمة الكتلة. إذا استدعى إجراء فرعي مُستدعى إجراءً فرعيًا آخر، فسيدفع عنوان إرجاع آخر إلى مكدس الاستدعاءات، وهكذا، مع تراكم المعلومات وتفريغها حسب متطلبات البرنامج. إذا استهلك الدفع كل المساحة المُخصصة لمكدس الاستدعاءات، يحدث خطأ يُسمى تجاوز سعة المكدس ، مما يؤدي عادةً إلى تعطل البرنامج . تُسمى إضافة مدخل كتلة أو إجراء فرعي إلى مكدس الاستدعاءات أحيانًا "التفاف"، وإزالة المدخلات "فك التفاف".

عادةً ما يكون هناك مكدس استدعاء واحد فقط مرتبط ببرنامج قيد التشغيل (أو بدقة أكبر، بكل مهمة أو خيط من خيوط العملية )، على الرغم من إمكانية إنشاء مكدسات إضافية لمعالجة الإشارات أو تعدد المهام التعاوني (كما هو الحال مع setcontext ). ولأنه يوجد مكدس واحد فقط في هذا السياق المهم، يُمكن الإشارة إليه باسم المكدس (ضمنًا "مكدس المهمة")؛ ومع ذلك، في لغة برمجة فورث، يتم الوصول إلى مكدس البيانات أو مكدس المعاملات بشكل أكثر وضوحًا من مكدس الاستدعاء، ويُشار إليه عادةً باسم المكدس (انظر أدناه).

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

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

بحسب اللغة ونظام التشغيل وبيئة الجهاز، قد يخدم مكدس الاستدعاءات أغراضًا إضافية، بما في ذلك على سبيل المثال:

تخزين البيانات محليًا

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

وبالمثل، قد يخصص جزء مضمن إطار مكدس للمتغيرات المحلية. وكما هو الحال مع إطار الاستدعاء، تُفقد القيم عند انتهاء الجزء.

تمرير المعلمات

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

مجموعة التقييم

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

سياق الروتين الفرعي المحيط

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

بدلاً من الرابط الثابت، يمكن تجميع مراجع الإطارات الثابتة المحيطة في مصفوفة من المؤشرات تُعرف باسم " العرض" ، والتي يتم فهرستها لتحديد موقع الإطار المطلوب. عمق التداخل المعجمي للروتين ثابت معروف، لذا فإن حجم عرض الروتين ثابت. كذلك، عدد النطاقات الحاوية التي يجب اجتيازها معروف، وبالتالي فإن فهرس العرض ثابت أيضًا. عادةً، يقع عرض الروتين في إطار مكدس خاص به، ولكن جهاز Burroughs B6500 نفّذ مثل هذا العرض في مكونات مادية تدعم ما يصل إلى 32 مستوى من التداخل الثابت.

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

سياق الكتلة المغلقة

في بعض لغات البرمجة، مثل ALGOL 60 و PL/I ، قد يحتوي جزء من إجراء ما على متغيرات محلية خاصة به، يتم تخصيصها عند بدء الجزء وتحريرها عند انتهائه. وبالمثل، قد يحتوي الجزء على معالجات استثناءات خاصة به، يتم تعطيلها عند انتهائه.

حالة العودة الأخرى

إلى جانب عنوان الإرجاع، قد توجد في بعض البيئات حالات أخرى للجهاز أو البرنامج يجب استعادتها عند عودة روتين فرعي. قد يشمل ذلك أمورًا مثل مستوى الامتياز، ومعلومات معالجة الاستثناءات، وأنماط العمليات الحسابية، وما إلى ذلك. عند الحاجة، يمكن تخزين هذه المعلومات في مكدس الاستدعاءات تمامًا كما هو الحال مع عنوان الإرجاع.

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

يتكون مكدس الاستدعاءات من إطارات المكدس (وتُسمى أيضًا سجلات التنشيط أو إطارات التنشيط ). وهي هياكل بيانات تعتمد على الجهاز وواجهة التطبيق الثنائية (ABI)، وتحتوي على معلومات حالة الروتينات الفرعية. يتوافق كل إطار مكدس مع استدعاء روتين فرعي لم يكتمل تنفيذه بعد. ^{[ 1 ]} إطار المكدس الموجود في أعلى المكدس مخصص للروتين قيد التنفيذ حاليًا. على سبيل المثال، إذا DrawLineكان روتين فرعي باسم قيد التشغيل حاليًا، بعد استدعائه من روتين فرعي آخر DrawSquare، فقد يكون الجزء العلوي من مكدس الاستدعاءات مُرتبًا كما في الصورة المجاورة.

يمكن رسم مخطط كهذا في أي اتجاه طالما تم فهم موضع الجزء العلوي، وبالتالي اتجاه نمو المكدس. تختلف البنى فيما إذا كانت مكدسات الاستدعاء تنمو باتجاه عناوين أعلى أو باتجاه عناوين أدنى، لذا فإن منطق أي مخطط لا يعتمد على هذا الاختيار للعنونة بحكم الاصطلاح.

أثناء تنفيذه النشط، مع وجود إطاره في أعلى المكدس، يمكن للروتين الوصول إلى المعلومات الموجودة داخل إطاره حسب الحاجة. ^{[ 2 ]} يتضمن إطار المكدس عادةً العناصر التالية على الأقل (بالترتيب الذي تم دفعه به):

• الوسائط (قيم المعلمات) التي تم تمريرها إلى الروتين على مكدس الاستدعاءات (إن وجدت)؛
• عنوان الإرجاع إلى مستدعي الروتين (على سبيل المثال، في DrawLineإطار المكدس، عنوان في DrawSquareكود البرنامج)، إذا تم حفظه في مكدس الاستدعاءات بدلاً من سجل؛ و
• مساحة للمتغيرات المحلية للروتين (إن وجدت).

يمكن أحيانًا فحص مكدس الاستدعاءات أثناء تشغيل البرنامج. وبحسب طريقة كتابة البرنامج وتجميعه، يمكن استخدام المعلومات الموجودة في المكدس لتحديد القيم الوسيطة وتتبعات استدعاءات الدوال. وقد استُخدم هذا لإنشاء اختبارات آلية دقيقة ^{[ 5 ]} ، وفي حالات مثل Ruby و Smalltalk ، لتنفيذ استمرارية من الدرجة الأولى. على سبيل المثال، يُنفذ مصحح أخطاء GNU (GDB) فحصًا تفاعليًا لمكدس الاستدعاءات لبرنامج C قيد التشغيل ولكنه متوقف مؤقتًا ^{[ 6 ] .}

يمكن أن يكون أخذ عينات منتظمة من مكدس الاستدعاء مفيدًا في تحديد أداء البرامج، لأنه إذا ظهر عنوان روتين فرعي في مكدس الاستدعاء الذي يأخذ البيانات عدة مرات، فمن المحتمل أن يعمل كاختناق في التعليمات البرمجية ويجب فحصه بحثًا عن مشاكل في الأداء.

في لغة ذات مؤشرات حرة أو عمليات كتابة مصفوفة غير مدققة (كما هو الحال في لغة C)، فإن خلط بيانات تدفق التحكم التي تؤثر على تنفيذ التعليمات البرمجية (عناوين الإرجاع أو مؤشرات الإطار المحفوظة) وبيانات البرنامج البسيطة (المعلمات أو قيم الإرجاع) في مكدس الاستدعاءات يشكل خطرًا أمنيًا، ومن المحتمل استغلاله من خلال تجاوزات مخزن المكدس ، وهي النوع الأكثر شيوعًا من تجاوزات المخزن المؤقت .

تتضمن إحدى هذه الهجمات ملء مخزن مؤقت برمز تنفيذي عشوائي، ثم تجاوز سعة هذا المخزن أو مخزن مؤقت آخر للكتابة فوق عنوان إرجاع بقيمة تشير مباشرةً إلى الرمز التنفيذي. ونتيجةً لذلك، عند انتهاء الدالة، يُنفذ الحاسوب ذلك الرمز. يمكن صدّ هذا النوع من الهجمات باستخدام W^X ، ولكن قد تنجح هجمات مماثلة حتى مع تفعيل حماية W^X، بما في ذلك هجوم الإرجاع إلى مكتبة libc أو الهجمات الناتجة عن البرمجة الموجهة نحو الإرجاع . وقد اقتُرحت حلول تخفيفية متنوعة، مثل تخزين المصفوفات في موقع منفصل تمامًا عن مكدس الإرجاع، كما هو الحال في لغة برمجة فورث. ^{[ 7 ]}

• ديكسترا، إي دبليو (1960). “البرمجة العودية”. الرياضيات الرقمية . 2 (1): 312-318 . دوى : 10.1007 / BF01386232 .
• ويلسون، بي آر؛ جونستون، إم إس؛ نيلي، إم؛ بولز، دي (1995). "تخصيص التخزين الديناميكي: دراسة استقصائية ومراجعة نقدية". إدارة الذاكرة . سلسلة محاضرات في علوم الحاسوب. المجلد  986. الصفحات 1-116. CiteSeerX 10.1.1.47.275 . doi : 10.1007 / 3-540-60368-9_19 . ISBN   978-3-540-60368-9.
• "2.4. المكدس". دليل برمجة لغة التجميع MCS-4 - دليل برمجة نظام الحاسوب الصغير INTELLEC 4 (ملف PDF) (طبعة أولية  ). سانتا كلارا، كاليفورنيا، الولايات المتحدة الأمريكية: شركة إنتل . ديسمبر 1973. الصفحات 2-7 - 2-8 . MCS-030-1273-1. مؤرشف (ملف PDF) من الأصل بتاريخ 1 مارس 2020. تم الاطلاع عليه بتاريخ 2 مارس 2020 . (ملاحظة: معالج Intel 4004 ذو 4 بتات يستخدم مكدسًا داخليًا بدلاً من مكدس في الذاكرة.)

• استدعاء الدوال وعمليات مؤشر الإطار في معالج 68000 ( مؤرشف بتاريخ 24 يوليو 2010 على موقع Wayback Machine)
• مشروع libunwind - واجهة برمجة تطبيقات فك التصفح المستقلة عن النظام الأساسي