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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Function Виклик і вказівник кадра в 68000