Что мы знаем о стеке?

Владимир Мешков

Что мы знаем о стеке?

Предпримем попытку систематизировать собственные знания о стеке и максимально подробно рассмотрим, какую роль играет стек в процедурном программировании.

Стек – это область памяти, предназначенная для временного хранения данных. Стек адресуется при помощи пары регистров SS:ESP. Регистр SS (Stack Segment) содержит селектор сегмента стека при работе процессора в защищенном режиме, ESP (Stack Pointer, указатель стека) – смещение относительно базового адреса сегмента стека. Упрощенная схема адресации данных в стеке, без привязки к какой-либо конкретной операционной системе, показана на рис. 1. Схема адресации сегментов команд и данных идентична изображенной на рисунке схеме адресации сегмента стека. При подготовке статьи использовались ОС Linux, компилятор gcc-4.1.2, отладчик gdb-6.6.

Рисунок 1. Адресация стека

Для помещения данных в стек и извлечения данных из него используются инструкции процессора push и pop. Стек работает по принципу FILO (First Input – Last Output, первым вошел – последним вышел). Каждый вызов инструкции push/pop изменяет значение регистра ESP. Инструкция push размещает данные по адресу, на который указывает ESP, и сдвигает верхушку стека в сторону младших адресов, уменьшая значение ESP. Инструкция pop поступает наоборот – снимает данные с верхушки стека и увеличивает значение ESP.

Стек играет важнейшую роль в процедурном программировании. Процедурное программирование подразумевает использование функций. Функции позволяют выделить часто используемые фрагменты кода в отдельные блоки и повторно использовать их из любой точки программы, тем самым повышая эффективность разработки. При использовании функций линейный (последовательный) ход выполнения программы нарушается – в любой момент мы можем передать управление на функцию. Для этого используется инструкция процессора call. Адрес функции передается как параметр этой команды:

call < адрес функции >

Передача параметров функции осуществляется в зависимости от используемого соглашения. В случае соглашения fastcall максимум параметров передается через регистры, что значительно ускоряет процесс вызова функции. В контексте данной статьи рассматривается соглашение stdcall/cdecl, при котором для передачи параметров используется стек. Перед вызовом функции параметры помещаются в стек при помощи инструкции push. В виде псевдокода вызов функции с двумя параметрами с использованием соглашения языка Си выглядит так (адресация показана условно, без учета размеров инструкций):

Условный адрес       Инструкция процессора

....                 ....

< N-2 >        push < параметр 2 >

< N-1 >        push < параметр 1 >

< N >                call < адрес функции >

< N+1 >        < сюда будет возвращено управление >

В языке Си первый параметр загружается в стек последним, последний параметр – первым. Получив управление, функция считывает из стека параметры вызова, и выполняет свою работу. Парметры остаются в стеке, благодаря чему их можно использовать как переменные в ходе выполнения функции. Завершается функция инструкцией ret (эту инструкцию мы обсудим ниже). После этого управление будет передано на команду, которая следует за инструкцией call. Схематически это отображено на рис. 2.

Рисунок 2. Вызов функции и передача ей параметров

Чтобы такая схема сработала, необходимо запомнить адрес возврата из функции, т.е. адрес следующей за call команды. Этот адрес сохраняет в стеке команда call. Если привязать все эти команды к изменениям стека, то получим картину как на рис. 3. Видно, как изменяют стек команды push и call. Сразу после вызова команды call в стеке будет сохранен адрес возврата – адрес следующей за call инструкции, и ESP будет указывать на этот адрес, т.е. *ESP == адрес возврата.

Рисунок 3. Изменения стека при вызове функции

Чтобы узнать, что происходит со стеком дальше, напишем небольшой тестовый пример:

Листинг 1. Файл test.c

#include <stdio.h>

#include <stdlib.h>

int foo(int a, int b)

{

return a+b;

}

int main()

{

int c, a, b;

c = 0, a = 1, b = 2;

c = foo(a, b);

return c;

}

Посмотрим на дизассемблерный листинг функции foo:

Две первые инструкции образуют пролог функции. Первая инструкция сохраняет в стеке содержимое регистра EBP, вторая присваивает регистру EBP значение ESP. Чтобы понять смысл этих манипуляций, изобразим (см. рис. 4) все изменения стека после двух этих инструкций функции.

Рисунок 4. Состояние стека после пролога функции

Что же мы все таки получили? А вот что – мы зафиксировали верхушку стека в регистре EBP и получили возможность перемещаться по стеку относительно этой точки. Другими словами, мы создали кадр стека, или стековый фрейм (stack frame). Смотрим на рис. 5.

Рисунок 5. Кадр стека

При помощи EBP мы можем адресовать параметры функции и ее локальные данные (про область локальных данных я расскажу позже). Запустим в отладчике нашу тестовую программу, установив точку останова на функцию foo:

Смотрим, какие у нас есть кадры стека:

Текущий кадр принадлежит функции foo. Получим значение регистра EBP:

Согласно рис. 5, по смещению EBP+0x4 будет находиться адрес возврата из функции foo, по смещению EBP+0x8 – первый параметр функции, EBP+0xC – второй параметр функции. Проверим это:

Адресация [EBP+0x8] в синтаксисе AT&T выглядит как 0x8(%ebp). Подробнее о различиях синтаксиса ассемблеров Intel и AT&T можно прочитать в статье http://www.ibm.com/developerworks/linux/library/l-gas-nasm.html.

С параметрами все правильно, если посмотреть на листинг 1 (a=1, b=2). Чтобы убедиться в правильности адреса возврата, дизассемблируем функцию main, потому что foo вызывается из нее:

Сравните адрес в дизассемблерном листинге и адрес, который мы при помощи отладчика извлекли из стека – они идентичны.

На что еще стоит обратить внимание в дизассемблерном листинге функции main, так это на порядок адресации локальных переменных. У main локальных переменных три: a, b и c. Также как и для любой другой функции, для main создается кадр стека, о чем красноречиво свидетельствует пролог. Прежде чем присваивать значения локальным переменным, в стеке резервируется для них место при помощи команды «sub $0x24,%esp». Эта команда сдвигает верхушку стека вниз на 36 байт. Далее следуют три команды movl, которые присваивают значения локальным переменным. Пусть вас не смущают странные значения типа 0xfffffff0, 0xfffffff4 и 0xfffffff8 – большое положительное число суть всего лишь маленькое отрицательное, просто отладчик не указывает знак числа. Всю эту тройку команд movl можно переписать так:

movl $0x0,0xfffffff0(%ebp)    ==>     movl $0x0,-16(%ebp)

movl $0x1,0xfffffff4(%ebp)    ==>     movl $0x1,-12(%ebp)

movl $0x2,0xfffffff8(%ebp)    ==>     movl $0x2,-8(%ebp

Для доказательства нашей правоты проведем проверку при помощи отладчика:

Ставим точку останова на main:

Остановились перед вызовом foo. Получаем значение регистра EBP:

Определяем значение локальных переменных, указывая положительное смещение относительно EBP:

А теперь будем задавать отрицательное смещение и сравнивать результаты:

Что еще бросается в глаза в дизассемблерном листинге функции main? Наверное, отсутствие команды push для размещения в стеке параметров функции foo, т.е. локальных переменных a и b функции main? На самом деле для размещения параметров в стеке компилятор gcc не использует push. Он использует mov. Локальная переменная b попадает в стек в результате следующей последовательности команд:

0x080483b5 <main+38>:   mov 0xfffffff8(%ebp),%eax  <-- локальная переменная b=2 в EAX

0x080483b8 <main+41>:   mov %eax,0x4(%esp)         <-- помещаем параметр b в стек

Здесь первая команда «mov 0xfffffff8(%ebp),%eax» загружает в регистр EAX локальный параметр b (согласно синтаксису ассемблера AT&T загрузка аргументов выполняется слева направо), а затем вторая команда «mov %eax,0x4(%esp)» размещает этот параметр в стеке, выполняя работу инструкции push.

Аналогично в стек попадает локальный параметр a:

0x080483bc <main+45>:   mov 0xfffffff4(%ebp),%eax  <-- локальная переменная a=1 в EAX

0x080483bf <main+48>:   mov %eax,(%esp)            <-- помещаем параметр a в стек

Первой в стеке оказывается переменная b=2, последней a=1 (см. рис. 6). Далее следует вызов call <адрес foo>, и в стеке окажется адрес возврата.

Рисунок 6. Размещение параметров в стеке перед вызовом foo

При возврате из функции main команда «add $0x24,%esp» выполняет выравнивание (балансировку) стека. Балансировка стека – это очень важная операция. Если мы перед выходом из функции не сбалансируем стек, то нас будут ждать сюрпризы, самый безобидный из которых – аварийное завершение программы по сигналу Segmentation Fault. Разберемся, почему так.

Возврат из функции выполняет инструкция ret. При помощи утилиты objdump можно установить, что в нашей программе используется инструкция ret с опкодом C3 (опкод – это код операции, operation code).

В документе [1] в описании команды RET с таким опкодом сказано, что она выполняет ближний возврат в вызывающую процедуру, near return to calling procedure (ближний, потому что команда действует в пределах текущего сегмента кода и не изменяет значение селектора сегмента).

Для возврата инструкция снимает с верхушки стека значение и заносит его в регистр EIP (EIP <-- Pop(), см. [1]). Регистр EIP содержит адрес инструкции для выполнения. Если стек сбалансирован, то в момент вызова ret регистр ESP будет указывать на адрес возврата из функции. Неверное значение ESP приведет к неправильной работе программы.

Проверим, какие значения будут находиться в регистрах ESP и EIP при выходе из функции foo.

Первую точку останова ставим на инструкцию ret:

Вторая точка останова – сразу после вызова call <адрес foo> в функции main:

Достигли первой точки останова, смотрим, что находится в ESP:

В ESP – адрес возврата из foo, при выходе из foo он должен оказаться в EIP:

Тут видно, что находится в EIP – адрес, куда будет передано управление при возврате из foo. Это уже знакомый нам 0x80483c7.

Опция gcc-компилятора fomit-frame-pointer позволяет выполнять вызовы функций без создания фиксированных кадров стека. Использование этой опции освобождает регистр EBP, и компилятор может использовать его для своих внутренних потребностей. Недостаток – затрудняется отладка, т.к. значение ESP постоянно варьируется, и нужно быть очень внимательным, чтобы отследить все его изменения.

Скомпилируем наше тестовое приложение (см. листинг 1) с использованием опции fomit-frame-pointer и посмотрим на его дизассемблерный дамп:

Видите? Ни одного намека на использование регистра EBP. Вся адресация в стеке только через ESP. Таким способом создаются «плавающие» фреймы стека, и называются они так из-за постоянного изменения значения регистра ESP.

1. Intel® 64 and IA-32 Architectures Software Developer’s Manual. Volume 2B: Instruction Set Reference, N-Z (www.intel.com).

Комментарии могут оставлять только зарегистрированные пользователи