Базовый CS с нуля
Стек вызовов
Ты знаешь, что инструкция CALL сохраняет адрес возврата и переходит к функции. Но
куда она его сохраняет? И что происходит, когда эта функция сама вызывает другую
функцию — адреса возврата где-то накапливаются? Где живут локальные переменные, пока
функция выполняется?
Ответ — стек вызовов: область памяти, которую рантайм использует как структуру «последним вошёл — первым вышел». Каждый вызов кладёт блок данных, называемый кадром стека, на стек; каждый возврат снимает верхний кадр обратно. Кадры накапливаются по мере вложения вызовов и разматываются в обратном порядке по мере возврата функций. После этого урока ты сможешь держать точное состояние стека в голове в любой момент выполнения программы.
После этого урока ты сможешь описать, что содержит кадр стека (адрес возврата и локальные переменные), объяснить, что значит «положить кадр» и «снять кадр», трассировать состояние стека через последовательность вложенных вызовов и возвратов, и объяснить, почему стек вызовов — LIFO.
Стек вызовов — это область стека в адресном пространстве (введена в Блоке 02, уроке 04). Напомним: область стека растёт и сжимается автоматически по мере выполнения функций. Каждый раз, когда вызывается функция, рантайм резервирует блок ячеек для этой функции — этот блок называется кадром стека (или записью активации). Кадр хранит:
- Адрес возврата — куда должен перейти счётчик команд, когда эта функция вернётся.
- Локальные переменные функции — каждая переменная, объявленная внутри тела функции.
«Положить кадр» означает, что рантайм помещает новый кадр на вершину стека (указатель стека сдвигается, резервируя новое место). «Снять кадр» означает, что рантайм удаляет верхний кадр (указатель стека возвращается назад), освобождая эти ячейки для повторного использования.
Стек вызовов — LIFO: функция, вызванная последней, всегда завершается первой. Её кадр лежит сверху и снимается первым. Кадр под ним принадлежит вызывающей стороне, которая возобновляет выполнение после снятия. Этот порядок LIFO обусловлен тем, как функции вкладываются: последняя вызванная функция должна завершиться, прежде чем её вызывающая сторона сможет продолжить.
Программа для трассировки ниже содержит три функции: main вызывает outer, которая
вызывает inner. Все три кадра появятся на стеке одновременно, прежде чем начнётся
разматывание.
1
function inner(): void {
2
let c = 3; // единственная локальная переменная inner
3
}
4
5
function outer(): void {
6
let b = 2; // единственная локальная переменная outer
7
inner(); // вызов inner — кладёт кадр inner
8
}
9
10
function main(): void {
11
let a = 1; // единственная локальная переменная main
12
outer(); // вызов outer — кладёт кадр outer
13
}
14
15
main(); // точка входа — кладёт кадр main
- L2 c живёт в кадре стека inner — не существует до вызова inner
- L6 b живёт в кадре стека outer
- L7 CALL inner: сохраняет адрес возврата (строка 8), кладёт кадр inner
- L11 a живёт в кадре стека main
- L12 CALL outer: сохраняет адрес возврата (строка 13), кладёт кадр outer
- L15 CALL main: запускает всю цепочку — кладёт кадр main
Пройди вызов main() шаг за шагом. Каждая ячейка представляет один кадр стека. Кадры
показаны снизу вверх (старейший слева, новейший справа).
1
function inner(): void {
2
let c = 3;
3
}
4
5
function outer(): void {
6
let b = 2;
7
inner();
8
}
9
10
function main(): void {
11
let a = 1;
12
outer();
13
}
14
15
main();
Граничные случаи
Переполнение стека. Область стека имеет конечный размер (обычно 1–8 МБ в современных системах). Если вызовы вложены достаточно глубоко — чаще всего из-за безграничной рекурсии — стек заканчивается. Когда указатель стека должен выйти за пределы области стека, ОС посылает сигнал, завершающий программу с ошибкой «переполнение стека» (stack overflow). Это не логическая ошибка в алгоритме; это физическое ограничение зарезервированного диапазона адресов. В уроке 05 ты увидишь, как это происходит при рекурсии.
main вызывает outer; outer вызывает inner. Пока inner выполняется, сколько кадров стека находится на стеке?
inner возвращается. Сколько кадров стека теперь на стеке?
Кадр стека хранит адрес возврата и локальные переменные функции. Функция f объявляет 3 локальные переменные. Сколько минимум единиц данных хранит кадр f (адрес возврата + локальные)?
Стек вызовов — LIFO. Если main вызвал outer, который вызвал inner, чей кадр удаляется первым при возврате функций?
outer вызывает inner. Адрес возврата inner указывает на инструкцию сразу после вызова inner() в outer. Если эта инструкция на строке 8, на какую строку переходит счётчик команд при возврате inner?
Что содержит кадр стека и когда он кладётся и снимается?
Стек вызовов — это область стека в адресном пространстве, управляемая в порядке LIFO. Когда вызывается функция, рантайм кладёт кадр стека на стек: блок ячеек, хранящий адрес возврата и все локальные переменные функции. Когда функция возвращается, рантайм снимает этот кадр — эти ячейки немедленно освобождаются. В любой момент выполнения стек хранит ровно кадры всех текущих активных функций: от самого внешнего вызывающего внизу до последней вызванной функции вверху. Кадры добавляются и удаляются в строгом порядке «последним вошёл — первым вышел», потому что последняя вызванная функция должна завершиться, прежде чем её вызывающая сторона сможет продолжить. Если вызовы вложены слишком глубоко, область стека заканчивается, и программа аварийно завершается с ошибкой переполнения стека.