Стек викликів

В інформатиці, стек викликів (англ. call stack) це структура даних у вигляді стека, яка зберігає інформацію про активні підпрограми комп'ютерної програми. Такий тип стека також відомий під назвами стек виконання, стек управління або рантайм стек, часто скорочується до просто "стек". Хоча підтримка функціонування стека викликів дуже важлива для будь-якої програми, деталі роботи зі стеком зазвичай приховані під час роботи з високорівневими мовами програмування.

Стек викликів використовується для декількох пов'язаних цілей, але головне його призначення - відслідковувати точку повернення з кожної активної підпрограми, тобто адресу інструкції, куди має бути повернуте виконання після завершення підпрограми. (Активними підпрограмами вважаються такі, що були викликані, але ще не завершили виконання поверненням.) Якщо, наприклад, підпрограма DrawSquare викликає підпрограму DrawLine з чотирьох різних місць, тоді код DrawLine має знати куди йому повертати виконання. Це зазвичай робиться кодом для кожного виклику підпрограми всередині DrawSquare, він записує адресу інструкції, наступної після конкретного виклику (адреси повернення) на верхівку стека викликів. Алгоритм повторюється для кожного наступного вкладеного виклику. При поверненні з підпрограми, адреса повернення знімається зі стека і керування передається наступній інструкції у призупиненій підпрограмі.

Опис

У зв'язку з тим, що стек викликів влаштований як стек, підпрограма, що викликає, заштовхує адресу повернення на верхівку стека, а підпрограма яку викликають, після завершення своєї роботи, виштовхує адресу повернення зі стека і повертає керування інструкції за цією адресою. Якщо підпрограма, яку викликали, викликає іншу підпрограму або рекурсивно саму себе, тоді вона заштовхує наступну адресу повернення на верхівку стека, і т.д. Якщо розмір стека поглинає увесь виділений під стек простір, тоді виникає помилка переповнення стека, яка зазвичай призводить до краху програми. Додавання запису про підпрограму іноді називається намотування (англ. winding); відповідно, видалення запису - розмотування (англ. unwinding).

Зазвичай з програмою пов'язують лише один стек викликів (або більш точно, з кожною ниттю процесу), хоча додатковий стек може бути створений з метою обробки сигналів. Через таку унікальність даного поняття в конкретному контексті, можна вживати просто термін стек.

В високорівневих мовах програмування специфіка стека викликів зазвичай прихована від програміста, який оперує набором функцій, а не прямо пам'яттю стека. З іншого боку, більшість асемблерних мов залучають програміста до маніпулювання стеком. Подробиці маніпулювання стеком в певній мові програмування залежать від компілятора, операційної системи і доступного набору інструкцій.

Призначення стека викликів

Як зауважено вище, головним призначенням стека викликів є:

• Збереження адреси повернення – Коли підпрограма викликається, виникає потреба у збереженні місцезнаходження інструкції на яку має повернутися виконання. Використання саме стека для збереження цієї адреси має важливі переваги відносно інших способів. Одна з них полягає в тому, що кожне завдання має свій окремий стек викликів, таким чином підпрограма може бути повторновикористана різними завданнями (нитями). Іншою перевагою є автоматична підтримка рекурсії. Коли функція викликає себе рекурсивно, адреса повернення щоразу має бути збережена. Ця можливість автоматизується стеком.

Стек викликів може мати додаткові призначення, залежно від мови програмуання і архітектури комп'ютера. Серед них можуть бути:

• Локальне сховище даних – Підпрограма часто потребує пам'ять для збереження значень локальних змінних, змінних значення яких відомі тільки під час виконання підпрограми і не зберігаються по виході з неї. Часто буває зручно виділяти для таких змінних місце просто рухаючи верхівку стека достатньо, щоб забезпечити необхідний простір. Це дуже швидке рішення у порівнянні з розташуванням в купі. Зауважимо, що кожна окрема підпрограма має свій окремий простір у стеку для локальних змінних.

• Передача параметрів – Підпрогами часто вимагають від коду, що їх викликає параметри, і розташування значень цих параметрів у стеку не є незвичним рішенням. Якщо параметрів всього декілька і їхній розмір малий, тоді для передачі їх в підпрограму можна використати регістри процесора, але якщо розмір парамерів не дозволяє зужиткувати цей спосіб передачі, буде необхідний простір в пам'яті. Стек добре працює для передачі таких параметрів, особливо через те, що з кожним викликом наступної підпрограми значення параметрів змінюються, щоразу для них виділяється окреме місце.

• Стек обчислення – Операнди арифметичних або логічних операцій зазвичай розташовують в регістрах і тоді провадять над ними певні дій. Однак, в деяких ситуаціях операнди можуть накопичуватися до довільної глибини, тоді постає питання використання чогось відмінного від регістрів. Стек подібних операндів, скоріше схожий на RPN калькулятор, називається стеком обчислення, і може розташовуватися у стеку викликів.

• Вказівник на поточний об'єкт - Деякі об’єктозорієнтовані мови програмування (наприклад, C++),при виклику функції зберігають вказівник this разом з аргументами функції у стеку. Вказівник this вказує на об'єкт пов'язаний з методом, що викликається.

• Охоплювальне середовище підпрограми - Деякі мови (наприклад, Pascal та Ada) підтримують вкладені підпрограми, які дозволять внутрішній підпрограмі мати доступ до даних охоплюючої підпрограми, тобто параметрів і змінних із власного середовища охоплюючої підпрограми. Таке статичне вкладення може повторюватися - функція об'явлена в функції об'ялевній в наступній функції... Реалізація має забезпечити спосіб у який функція на будь-якому статичному рівні вкладення могла б посилатися на дані з кожного рівня вкладеності охоплювального середовища. Зазвичай це здійснюється через використання вказівника на оточуючий кадр, він зветься (англ. downstack link) або (англ. static link), для того, щоб розрізняти з (англ. dynamic link), що посилається на того хто викликає (необов'язково статичного предка). Наприклад, мови які дозволяють підпрограмам викликати себе рекурсивно, з можливістю утворення в результаті багатьох кадрів виклику для внутрішньої підпрограми, але всі ці статичні посилання вказують на один і те саме середовище охоплюючої підпрограми. Замість статичних посилань, посилання на оточуючі статичні кадри можуть бути реалізовані у вигляді масиву вказівників.

• Інші стани повернення – Окрім адреси повернення, в деяких середовищах в яких присутні інші машинниі аьо програмні стани, що повинні бути відновлені після повернення з підпрограми. Це може бути рівень привілеїв, інформація стосовно обробки винятків, арифметичні режими і так далі. При потребі ці дані можуть бути збережені у стеку так само як і адреса повернення.

Зазвичай стек викликів використовується для адреси повернення, локальних параметрів і параметрів відомих як «кадр виклику». В різних середовищах різні обов'язки покладаються на стек викликів. В мові програмування Forth, наприклад, тільки адреса повернення і локальні змінні зберігаються у стеку викликів (тут він відомй як стек повернення); параметри зберігаються в окремому стеку даних.

Структура

Стек викликів складається з стекових кадрів (іноді активаційних записів). Це залежні від архітектури структури, що містять інформацію про стан підпрограми. Кожний стековий кадр відповідає підпрограмі, яка була викликана і ще не завершилась. Наприклад, якщо підпрогама DrawLine зараз виконується і була викликана підпрограмою DrawSquare, верхня частина стека має виглядати подібним чином:

Стековий кадр на горі стека відповідає поточній підпрограмі. В найзагальнішому варіанті стековий кадр включає:

• простір для локальних змінних підпрограми,
• адреси повернення і
• значення параметрів переданих в підпрограму.

Адреса верхівки стека міститься в регістрі, який називають вказівник стеку. Також доступ до пам'яті всередині кадру можна отримати через окремий регістр, часто згадуваний як вказівник кадру, зазвичай він вказує на фіксовану точку в структурі кадру, таку як розташування адреси повернення.

Стекові кадри мають різний розмір. Різні підпрограми мають різну кількість параметрів, тож ця частина може мати різний розмір для різних підпрограм. Насправді, деякі мови програмування підтримують динамічне виділення пам'яті для локальних змінних у стеку, в такому випадку розмір цієї частину кадру може змінюватись під час виконання підпрограми, і бути невідомим під час компілювання. В останньому випадку, доступ через вказівник кадру, швидший ніж через вказівник стеку, зазвичай необхідний через неможливість передбачити зміщення від верхівки стека до таких значень як адреса повернення.

В багатьох системах, вказівник кадру містить поле для збереження попереднього значення регістра вказівника кадру, тобто значення яке він мав під час виконання підпрограми, що викликала. Наприклад, на передуючий діаграмі, стековий кадр DrawLine буде мати комірку пам'яті відведену під збереження значення вказівника кадру, котрий використовує DrawSquare. Це значення зберігається на вході в підпрограму і відновлюється для повернення. Наявність такого поля в стековому фреймі дозволяє коду мати доступ до кожного кадру знизу поточної підпрограми.

мови програмування, які підтримують вкладені підпрограми в стековому кадрі мають поле, що містить вказівник на стековий фрейм охоплюючої підпрограми, яка й викликала цю внутрішню (вкладену) підпрограму. Це іноді називається дисплей. Цей вказівник забезпечує внутрішній підпрограмі можливість доступу, до локальних змінних і параметрів охоплюючої підпрограми з якої вона була викликана.

Для деяких цілей стекові кадри викликової та викликаної підпрограм можуть перетинатися. Перетин складається з пам'яті для параметрів. В деяких середовищах, викликова підпрограма заштовхує кожен з аргументів на верхівку стека, розширюючи таким чином свій стековий кадр, і потому робить виклик. В інших середовищах, викликова підпрограма заздалегідь отримує виділене місце на горі стекового кадра, для збереження аргументів, які вона передає викликаній підпрограмі. Це місце іноді називають ділянка вихідних аргументів або викликова ділянка. В цьому випадку, ромір такої ділянки обчислюється компілятором так, щоб забезпечити всі можливі виклики підпрограм.

Використання

Обробка місця виклику

Зазвичай найменші дії над стеком викликів потрібні саме в місці виклику підпрограми (і це є добре, бо може бути багато місць виклику кожної підпрограми). Значення актуальних аргументів обчислюються на місці виклику, через їх особливість для кожного виклику, і заштовхуються в стек або записуються в регістри, в залежності від угоди про виклики, що використовується. Потому виконується інструкція, наприклад BAL (перехід і зв'язування, англ. Branch and Link), для передачі керування коду цільової підпрограми.

Обробка в викликаній підпрограмі

В викликаній підпрограмі, перший виконаний код зазвичай зветься пролог підпрограми, він виконує необхідну господарську роботу перед початком роботи логічного коду підпрограми.

Код пролога зазвичай зберігає адресу повернення залишену інструкцією виклику в регістрі, заштовхуючи її в стек. Схожим чином, поточний вказівник стеку та/або вказівник кадра може бути збережений. Як варіант, деякі архітектури автоматично забезпечують подібну функціональність, і тоді код пролога не має виконувати ці операції.

Якщо використовується вказівник кадра, типовий вступ встановлює нове значення регістра вказівника стека з поточного значення цього вказівника. Простір для локальних змінних може бути виділений покроковою зміною адреси верхівки стека.

Мова програмування Forth дозволяє явне намотування стека викликів (це називається «стек повернення»).

Обробка повернень

Коли підпрограма готова повернути керування, вона виконує епілог який відкочує кроки пролога. Типово це відновлення значень регістрів (таких як значення вказівника кадра) зі стекового кадра, цілком виштовхує стековий кадр зміною значення вказівника стека, і насамкінець передає виконання інструкції за адресою повернення. В багатьох погодженнях викликів серед елементів виштовхнутих зі стека епілогом присутні початкові значення аргументів, в такому випадку викликова програма зазвичай не має необхідності маніпулювати стеком після повернення в неї. Однак, в деяких угодах про виклик це завдання покладається на викликову підпрограму.

Розмотування

Повернення з викликаної підпрограми виштовхне верхній кадр зі стека, можливо залишивши значення, яке повертає викликана підпрограма.

Деякі мови програмування, такі як Паскаль, дозволяють глобальні goto переходи для передачі керування назовні з вкладеної підпрограми і в попередньо викликану охоплюючу функцію. Така дія потребує розмотки стека через стільки кадрів, скільки необхідно, щоб відновити середовище зовнішньої підпрограми в якій знаходиться адреса інструкції повернення. Зазвичай таке використовують тільки для обробки помилок.

Інші мови, такі як Object Pascal, забезпечують обробку винятків, яка також потребує розмотування стека. Стековий кадр підпрограми може містити один або більше записів, що визначають обробку винятків. У випадку виникнення виняткової ситуації, стек розмотується доти, доки не буде знайдений обробник готовий прийняти (зловити) даний тип винятку. Common Lisp дозволяє проконтролювати, що відбудеться при розмотуванні стека через використання спеціального unwind-protect оператора.

При застосуванні продовження, стек (логічно) розмотується і знов намотується зі стеком продовження.

Стек викликів і тестування програмного забезпечення

Нещодавно заявлений підхід використовує стек викликів в дуже відмінний спосіб від описаних. Він використовує його для зменшення набору тестів,. Коротко, зменшення набору тестів шукає можливості для зменшення кількості тестових прикладів в наборі тестів одночасно зберігаючі високий відсоток ефективності виявлення помилок. Два тестових приклади вважаються тотожними якщо вони утворюють однаковий набір стеків виклику під час виконання. По подробиці дивись .

Аналіз продуктивності

Перегляд стека виклику в довільний момент виконання програми може бути дуже корисним для покращення продуктивності програм. Якщо інструкція виклику підпрограми з'являться через певні проміжки часу, можливе покращення через видалення виликів. Дивись «Аналіз продуктивності» та «Глибинне вибирання».

Безпека

Змішування даних потоку керування впливаючих на виконання коду (адреса повернення, збережені вказівникі кадрів) і простих даних програми (параметри, значення до повернення, локальні змінні) у стеку викликів породжує ризики безпеки, можливість експлойтування через переповнення буферів.

Див. також

• Переповнення стекового буфера

Примітки

1. c2:AlternativeMicroprocessorDesign
2. “Call Stack Coverage for GUI Test-Suite Reduction” by Scott McMaster and Atif M. Memon. In Proceedings of the 17th IEEE International Symposium on Software Reliability Engineering (ISSRE 2006), Nov. 2006.
3. “Call-Stack Coverage for GUI Test-Suite Reduction” by Scott McMaster and Atif M. Memon. IEEE Trans. Softw. Eng., 2008, IEEE Press.

Зовнішні посилання

• Function Виклик і вказівник кадра в 68000 [ 24 липня 2010 у Wayback Machine.]