تقدير حجم المكدس

Question

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

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

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

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

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

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

Answer 1

تقييم وقت التشغيل

تتمثل الطريقة عبر الإنترنت في رسم المكدس الكامل بقيمة معينة ، مثل 0xaaaa (أو 0xaa ، مهما كان عرضك). ثم يمكنك التحقق من حجم المكدس الذي نمت في الماضي إلى حد أقصى من خلال التحقق من مقدار اللوحة التي لم يمسها.

القي نظرة على هذه رابط لتفسير مع التوضيح.

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

تقييم ثابت

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

إلقاء نظرة أيضًا على هذه سؤال.

Answer 2

يمكنك استخدام أداة تحليل ثابت مثل StackAnalyzer, ، إذا كان هدفك يناسب المتطلبات.

Answer 3

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

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

ستمنحك هذه الأنواع من التحليل تقريبًا تقريبًا لأسوأ الحالات العلوية لاستخدام المكدس وهو بالضبط ما تريد معرفته. بالطبع ، قد يشتكي النقاد (مثل الأشخاص الذين أعمل معهم) من أنك تقوم بتخصيص مساحة كبيرة جدًا ، لكنها ديناصورات لا تهتم بجودة البرمجيات الجيدة :)

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

-دجهاوس

Answer 4

ليس حرا ، ولكن تغطية هل التحليل الثابت للمكدس.

Answer 5

فحص المكدس الثابت (خارج الخط) ليس بالأمر الصعب كما يبدو. لقد قمت بتنفيذها من أجل IDE المدمج (السريع)-يعمل حاليًا لـ ARM7 (NXP LPC2XXX) و Cortex-M3 (STM32 و NXP LPC17XX) و X86 و MIPS ISA المتوافقة مع FPGA.

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

بمجرد استخدام كل وظيفة ، يكون من السهل إلى حد ما بناء شجرة مكالمة من التحليل وحساب الحد الأقصى للاستخدام لكل وظيفة. تقوم IDE بإنشاء جدولين (RTOSES الرفيعة الفعالة) لك ، لذلك نحن نعرف بالضبط الوظائف التي يتم تعيينها على أنها "مهام" والتي هي ISRs ، حتى نتمكن من معرفة أسوأ استخدام لكل منطقة مكدس.

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

لا يوجد أي منهج مثالي ، لكن الجمع بين كليهما سيمنحك صورة جيدة إلى حد ما لما سيكون عليه استخدام العالم الحقيقي.

Answer 6

كما نوقش في الجواب هذا السؤال, ، تتمثل التقنية الشائعة في تهيئة المكدس بقيمة معروفة ثم تشغيل الكود لفترة من الوقت ومعرفة أين يتوقف النمط.

Answer 7

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

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

Answer 8

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

كانت مشكلتنا الوحيدة في هذا الحل واحدة من أدوات الطرف الثالث التي أجريت على mlock على مساحة ذاكرتها بأكملها (من الناحية المثالية لتحسين الأداء). تسبب هذا في كل 2 ميغابايت من المكدس لكل مؤشر ترابطه (75-150 منها) في وضعه. فقدنا نصف مساحة ذاكرتنا حتى اكتشفناها وعلقنا على خط المخالف.

Sidenote: يخصص Linux's Virtual Memory Manager (VMM) ذاكرة الوصول العشوائي في قطع 4K. عندما يطلب مؤشر ترابط جديد 2 ميغابايت من مساحة العنوان لمكدسه ، يقوم VMM بتعيين صفحات ذاكرة وهمية للجميع باستثناء الجزء العلوي الأكثر. عندما تنمو المكدس في صفحة زائفة ، تكتشف kernel خطأ في الصفحة وتبادل صفحة وهمية مع صفحة حقيقية ، (التي تستهلك 4K آخر من ذاكرة الوصول العشوائي الفعلية). وبهذه الطريقة ، يمكن أن تنمو مكدس مؤشر الترابط إلى أي حجم يحتاجه (طالما أنه أقل من 2 ميجابايت) وسيضمن VMM فقط الحد الأدنى من الذاكرة.

Answer 9

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

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

لا لا:

void func(myMassiveStruct_t par)
{
  myMassiveStruct_t tmpVar;
}

نعم نعم:

void func (myMassiveStruct_t *par)
{
  myMassiveStruct_t *tmpVar;
  tmpVar = (myMassiveStruct_t*) malloc (sizeof(myMassicveStruct_t));
}

يبدو واضحًا جدًا ولكن في كثير من الأحيان ليس كذلك - خاصة عندما لا يمكنك استخدام Malloc ().

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

Answer 10

لست متأكدًا بنسبة 100 ٪ ، لكنني أعتقد أن هذا قد يتم أيضًا. إذا كان لديك منفذ JTAG مكشوفًا ، فيمكنك الاتصال بـ Trace32 والتحقق من الحد الأقصى لاستخدام المكدس. على الرغم من ذلك ، سيتعين عليك إعطاء حجم مكدس تعسفي أولي كبير.