Стек вызовов - часть 1 - структура

Стек является фундаментальной структурой данных, а стек вызовов - одно из великих изобретений в информатике. Ведь он позволяет выполнять программу, которая написана с помощью функций, а без использования повторяющихся блоков кода невозможно написать большую программу, так как объём кода будет расти с огромной скоростью.

Как правило, память под стек вызовов выделяется операционной системой для каждого процесса.

Организация памяти процесса

Прежде, чем мы рассмотрим стек вызова, рассмотрим то, как организован процесс в памяти. Каждый процесс разделяет память на 3 сегмента: текст, данные и стек.

Сегмент текста содержит код программы как последовательность инструкций и некоторые данные только для чтения. Попытка записи в этот сегмент приведёт к ошибке сегментации (Segmentation fault).

Сегмент данных содержит инициализированные или неинициализированные данные. Например, статические переменные находятся в этом сегменте.

Стек используется для того, чтобы реализовать важную концепцию практически всех языков программирования высокого уровня - функцию (или процедуру). Казалось бы, вызов функции просто изменяет выполнение инструкций, как инструкция jump. Но отличие заключается в том, что после завершения работы функции возврат идёт в точку вызова. Именно для того, чтобы сохранить последовательности всех точек вызова и корректно к ним вернуться используется стек.

Стек как абстрактный тип данных

Стек представляет собой LIFO-структуру данных, которая аккумулирует данные, причём последний добавленный элемент будет извлечён первым. Стек имеет 2 команды для добавления и извлечения элементов: push и pop. Как правило предусмотрена возможность неразрушающего чтения данных с вершины стека. Важно понимать, что распечатывание данных на экран или просмотр элемента, не находящегося на вершине стека не предусмотрено абстрактным типом данных.

Сегмент стека

Сегмент стека - фиксированный блок памяти, в котором находятся данные. Размер самого стека внутри этого сегмента постоянно изменяется в процессе выполнения программы. У процессора есть регистр esp (sp), который указывает на вершину стека. Кроме того, как правило используется ещё и регистр ebp, который указывает на начало текущего стекового кадра.

Стековый кадр - область памяти на стеке, где находятся аргументы функций и их локальные переменные.

Адрес возврата - адрес следующей инструкции после инструкции вызова функции.

В подавляющем большинстве случаев стек организован “сверху-вниз”, то есть у низа стека адреса в памяти большие, чем у вершины стека. Такую реализацию стека используют процессоры Intel, SPARC, Motorolla и другие. Регистр esp тоже по разному используется: иногда он указывает на последний добавленный на стек элемент, а иногда он указывает на свободную область памяти после последнего стекового кадра. Для нашего примера будем рассматривать более частую реализацию - когда esp указывает на последний добавленный элемент.

Кроме регистра esp, есть ещё регистр ebp (fp), который указывает на начало текущего стекового кадра. В случаях, когда, например, в теле функции присутствует точка следования такая, что перед ней нет обращений к локальным переменным, а после неё нету инициализации новых локальных переменных, можно обойтись без этого регистра. В таких случаях адресация локальных переменных идёт через положительный отступ относительно esp. В некоторых случаях компилятор может предсказать поведение стека и корректно вычислить смещение адресов, однако данная технология используется крайне редко, поскольку вычисление этого смещения требует гораздо большего количества инструкций.

Вызов функции

Вызов функции состоит из нескольких этапов:

  1. На стек добавляются аргументы (если есть) в обратном порядке.
  2. На стек добавляется адрес возврата - текущее значение счётчика команд (IP - instruction pointer), то есть адрес следующей инструкции.
  3. На стек добавляется текущее значение регистра ebp, чтобы потом можно было адресовать локальные переменные после вложенных вызовов.
  4. Текущее значение esp (вершина стека после предыдущих добавлений) копируется в регистр ebp, поскольку, в данный момент, регистр esp содержит в себе начало следующего стекового кадра и его необходимо сохранить, чтобы адресовать новые локальные переменные.
  5. Происходит безусловный переход по адресу функции.
  6. Идёт выделение памяти для новых локальных переменных, при этом идёт вычитание из esp.

Пример

Рассмотрим пример вызова функции на Си:

void f(int arg1, int arg2, int arg3) {
    char local1[12];
    char local2[6];
}

int main() {
    f(100, 200, 300);
    return 0;
}

Если перевести данную программу в язык ассемблера, мы увидим, что f(100, 200, 300); будет переведено в:

pushl $300
pushl $200
pushl $100
call function

То есть сначала на стек добавляются аргументы, а затем идёт вызов функции инструкцией call. Этот процесс можно условно записать на ASM:

pushl $300 ; добавление аргументов на стек в обратном порядке
pushl $200
pushl $100
; добавление на стек адреса возврата
pushl %ebp ; сохраняем на стеке начало предыдущего стекового кадра
movl %esp,%ebp ; записываем в ebp начало нового стекового кадра
; переход по адресу функции
subl $20,%esp ; выделение памяти под 2 буфера

Буферы могут быть размера, кратного размеру машинного слова - 4 байта (в нашем случае). Буфер local1 будет занимать 12 байт, как и указывали, но буфер local2 будет занимать не 6 байт, а 8. Поэтому в теле функции мы вычитаем из esp 20 байт.

Возврат из функции

Возврат из функции состоит из нескольких этапов:

  1. Со стека снимаются все локальные переменные / буферы в обратном порядке.
  2. Со стека снимается регистр ebp прошлого стекового кадра и сохраняется в регистр ebp.
  3. Со стека снимается адрес возврата и по нему происходит безусловный переход.
  4. Со стека снимаются аргументы функции.

За 3 пункт отвечает инструкция ret.


Copyright © 2019 Александр Майоров. Все права защищены.