From: Bob <ubob@mail.ru.>
Newsgroups: email
Date: Mon, 16 Mar 2009 17:02:14 +0000 (UTC)
Subject: Использование стека на примере разбора кода, сгенерированного GCC
В данной статье предпринята попытка систематизировать собственные знания
о стеке и подробно рассмотреть, какую роль играет стек в процедурном программировании.
Статья была опубликована в журнале "Системный администратор", ноябрь 2007 г.
1. Общие понятия о стеке
Стек - это область памяти, предназначенная для временного хранения
данных. Стек адресуется при помощи пары регистров SS:ESP. Регистр SS
(Stack Selector) содержит селектор сегмента стека при работе процессора
в защищенном режиме, ESP (Stack Pointer, указатель стека) - смещение
относительно базового адреса сегмента стека.
Упрощенная схема адресации данных в стеке, без привязки к какой-либо
конкретной операционной системе, показана на рис.1.
Схема адресации сегментов команд и данных идентична изображенной на
рисунке схеме адресации сегмента стека.
Для помещения данных в стек и извлечения данных из него используются
инструкции процессора push и pop. Стек работает по принципу FILO (First
Input - Last Output, первым вошел - последним вышел). Каждый вызов
инструкции push/pop изменяет значение регистра ESP. Инструкция push
размещает данные по адресу, на который указывает ESP, и сдвигает
верхушку стека в сторону младших адресов, уменьшая значение ESP.
Инструкция pop поступает наоборот - снимает данные с верхушки стека и
увеличивает значение ESP.
2. Использование стека в процедурном программировании
Стек играет важнейшую роль в процедурном программировании. Процедурное
программирование подразумевает использование функций. Функции позволяют
выделить часто используемые фрагменты кода в отдельные блоки и повторно
использовать их из любой точки программы, тем самым повышая
эффективность разработки. При использовании функций линейный
(последовательный) ход выполнения программы нарушается - в любой момент
мы можем передать управление на функцию. Для этого используется
инструкция процессора call. Адрес функции передается как параметр этой
команды:
call < адрес функции >
Передача параметров функции осуществляется в зависимости от
используемого соглашения. В случае соглашения fastcall максимум
параметров передается через регистры, что значительно ускоряет процесс
вызова функции. В контексте данной статьи рассматривается соглашение
stdcall/cdecl, при котором для передачи параметров используется стек.
Перед вызовом функции параметры помещаются в стек при помощи инструкции
push. В виде псевдокода вызов функции с двумя параметрами с
использованием соглашения языка Си выглядит так (адресация показана
условно, без учета размеров инструкций):
Условный адрес Инструкция процессора
.... ....
< N-2 > push < параметр 2 >
< N-1 > push < параметр 1 >
< N > call < адрес функции >
< N+1 > < сюда будет возвращено управление >
В языке Си первый параметр загружается в стек последним, последний
параметр - первым. Получив управление, функция считывает из стека
параметры вызова, и выполняет свою работу. Парметры остаются в стеке,
благодаря чему их можно использовать как переменные в ходе выполнения
функции. Завершается функция инструкцией ret (эту инструкцию мы обсудим
ниже). После этого управление будет передано на команду, которая следует
за инструкцией call.
Схематически это отображено на рис.2.
Условный Инструкция
адрес процессора
| | |
+---------------+--------------------------------------+
| N - 2 | push < параметр 2 > |
+---------------+--------------------------------------+
| N - 1 | push < параметр 1 > | +------------+
+---------------+--------------------------------------+ | |
| N | call < адрес функции > |------>| |
+---------------+--------------------------------------+ | Функция |
| N + 1 | < адрес, на который будет возвращено | | |
| | управление > |<------| |
+---------------+--------------------------------------+ | |
| N + 2 | . . . . . . . . | +------------+
Возврат из ф-ии после
команды ret. Управление
передается на инструкцию,
которая следует за call
Рис.2. Вызов функции и передача ей параметров
Чтобы такая схема сработала, необходимо запомнить адрес возврата из
функции, т.е. адрес следующей за call команды.
Этот адрес сохраняет в стеке команда call. Если привязать все эти
команды к изменениям стека, то получим картину как на рис.3:
На рисунке 3 видно, как изменяют стек команды push и call. Сразу после
вызова команды call в стеке будет сохранен адрес возврата - адрес
следующей за call инструкции, и ESP будет указывать на этот адрес, т.е.
*ESP == адрес возврата.
2.1 Кадры стека
Чтобы узнать, что происходит со стеком дальше, напишем небольшой
тестовый пример:
Листинг 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:
bash-3.1# gcc -Wall -g -o test test.c
bash-3.1# gdb -q ./test
Using host libthread_db library "/lib/tls/libthread_db.so.1".
(gdb) disas foo
Dump of assembler code for function foo:
0x08048384 <foo+0>: push %ebp
0x08048385 <foo+1>: mov %esp,%ebp
0x08048387 <foo+3>: mov 0xc(%ebp),%eax
0x0804838a <foo+6>: add 0x8(%ebp),%eax
0x0804838d <foo+9>: pop %ebp
0x0804838e <foo+10>: ret
End of assembler dump.
Две первые инструкции образуют пролог функции. Первая инструкция
сохраняет в стеке содержимое регистра EBP, вторая присваивает регистру
EBP значение ESP. Чтобы понять смысл этих манипуляций, изобразим на
рис.4 все изменения стека после двух этих инструкций функции:
Что же мы все-таки получили? А вот что - мы зафиксировали верхушку стека
в регистре EBP и получили возможность перемещаться по стеку относительно
этой точки. Другими словами, мы создали кадр стека, или стековый фрейм
(stack frame).
Текущий кадр принадлежит функции foo. Получим значение регистра EBP:
(gdb) info reg ebp
ebp 0xbf92f588 0xbf92f588
Согласно рис.5, по смещению EBP+0x4 будет находиться адрес возврата из
функции foo, по смещению EBP+0x8 - первый параметр функции, EBP+0xC -
второй параметр функции. Проверим это:
(gdb) x/w 0xbf92f588+4
0xbf92f58c: 0x080483c7 <--- адрес возврата из foo
(gdb) x/w 0xbf92f588+8
0xbf92f590: 0x00000001 <--- первый параметр (a=1)
(gdb) x/w 0xbf92f588+0xC
0xbf92f594: 0x00000002 <--- второй параметр (b=2)
Адресация [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 вызывается из нее:
(gdb) disas main
Dump of assembler code for function main:
0x0804838f <main+0>: lea 0x4(%esp),%ecx
0x08048393 <main+4>: and $0xfffffff0,%esp
0x08048396 <main+7>: pushl 0xfffffffc(%ecx)
0x08048399 <main+10>: push %ebp
0x0804839a <main+11>: mov %esp,%ebp
0x0804839c <main+13>: push %ecx
0x0804839d <main+14>: sub $0x24,%esp <--- резерв места для лок.перем.
0x080483a0 <main+17>: movl $0x0,0xfffffff0(%ebp) <--- лок.перем. c = 0
0x080483a7 <main+24>: movl $0x1,0xfffffff4(%ebp) <--- лок.перем. a = 1
0x080483ae <main+31>: movl $0x2,0xfffffff8(%ebp) <--- лок.перем. b = 2
0x080483b5 <main+38>: mov 0xfffffff8(%ebp),%eax
0x080483b8 <main+41>: mov %eax,0x4(%esp)
0x080483bc <main+45>: mov 0xfffffff4(%ebp),%eax
0x080483bf <main+48>: mov %eax,(%esp)
0x080483c2 <main+51>: call 0x8048384 <foo> <--- вызов функции foo
0x080483c7 <main+56>: mov %eax,0xfffffff0(%ebp) <--- сюда вернемся из foo
0x080483ca <main+59>: mov 0xfffffff0(%ebp),%eax
0x080483cd <main+62>: mov %eax,0x4(%esp)
0x080483d1 <main+66>: movl $0x8048504,(%esp)
0x080483d8 <main+73>: call 0x80482b8 <printf@plt.>
0x080483dd <main+78>: mov 0xfffffff0(%ebp),%eax
0x080483e0 <main+81>: add $0x24,%esp
0x080483e3 <main+84>: pop %ecx
0x080483e4 <main+85>: pop %ebp
0x080483e5 <main+86>: lea 0xfffffffc(%ecx),%esp
0x080483e8 <main+89>: ret
End of assembler dump.
(gdb)
Сравните адрес в дизассемблерном листинге и адрес, который мы при помощи
отладчика извлекли из стека - они идентичны.
2.2 Адресация локальных переменных
На что еще стоит обратить внимание в дизассемблерном листинге функции
main, так это на порядок адресации локальных переменных.
У main локальных переменных три: a, b и c. Также как и для любой другой
функции, для main создается кадр стека, о чем красноречиво
свидетельствует пролог. Прежде чем присваивать значения локальным
переменным, в стеке резервируется для них место при помощи команды sub
$0x24,%esp. Эта команда сдвигает верхушку стека вниз на 36 байт. Далее
следуют три команды movl, которые присваивают значения локальным
переменным. Пусть вас не смущают странные значения типа 0xfffffff0,
0xfffffff4 и 0xfffffff8 - большое положительное число суть всего лишь
маленькое отрицательное, просто отладчик не указывает знак числа. Всю
эту тройку команд movl можно переписать так:
Что еще бросается в глаза в дизассемблерном листинге функции 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>, и в стеке окажется адрес возврата.
| |
Первоначальное | |
значение ESP -->+----------------+
/| |
/ | |
/ | |
/ | |
Место в стеке | |
зарезервировано | |
+----------------+ mov %eax, 0x4(%esp)
| Параметр b=2 |<-- в EAX - значение параметра b=2
+----------------+
| Параметр a=1 |<-- mov %eax, (%esp)
Значение ESP после ->+----------------+ в EAX - значение параметра a=1
после команды | |
sub $0x24, %esp
(новая верхушка стека)
Рис.6. Размещение параметров в стеке перед вызовом foo
2.4 Балансировка стека
При возврате из функции 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.
bash-3.1# gdb -q test
Using host libthread_db library "/lib/tls/libthread_db.so.1".
(gdb) disas foo
Dump of assembler code for function foo:
0x08048384 <foo+0>: push %ebp
0x08048385 <foo+1>: mov %esp,%ebp
0x08048387 <foo+3>: mov 0xc(%ebp),%eax
0x0804838a <foo+6>: add 0x8(%ebp),%eax
0x0804838d <foo+9>: pop %ebp
0x0804838e <foo+10>: ret
End of assembler dump.
Первую точку останова ставим на инструкцию ret:
(gdb) b *0x0804838e
Breakpoint 1 at 0x804838e: file test.c, line 7.
Вторая точка останова - сразу после вызова call <адрес foo> в функции main:
(gdb) b *0x080483c7
Breakpoint 2 at 0x80483c7: file test.c, line 16.
(gdb) r
Starting program: ~TEST/STACK/test
Breakpoint 1, 0x0804838e in foo (a=0, b=-1209000736) at test.c:7
7 }
Достигли первой точки останова, смотрим что находится в ESP:
(gdb) info reg esp
esp 0xbff583ac 0xbff583ac
(gdb) x/xw 0xbff583ac
0xbff583ac: 0x080483c7
(gdb) s
В ESP - адрес возврата из foo, при выходе из foo он должен оказаться в EIP:
Breakpoint 2, 0x080483c7 in main () at test.c:16
16 c = foo(a, b);
(gdb) info reg eip
eip 0x80483c7 0x80483c7 <main+56>
(gdb)
Тут ясно видно, что находится в EIP - адрес, куда будет передано
управление при возврате из foo. Это уже знакомый нам 0x80483c7.
2.5 "Плавающие" кадры стека
Опция fomit-frame-pointer компилятора gcc позволяет выполнять вызовы
функций без создания фиксированных кадров стека.
Использование этой опции освобождает регистр EBP, и компилятор может
использовать его для своих внутренних потребностей.
Скомпилируем наше тестовое приложение (см. листинг 1) с использованием
опции fomit-frame-pointer и посмотрим на его дизассемблерный дамп:
bash-3.1$ gcc -Wall -g -fomit-frame-pointer -o test test.c
bash-3.1$ gdb -q ./test
Using host libthread_db library "/lib/tls/libthread_db.so.1".
(gdb) disas main
Dump of assembler code for function main:
0x0804838d <main+0>: lea 0x4(%esp),%ecx
0x08048391 <main+4>: and $0xfffffff0,%esp
0x08048394 <main+7>: pushl 0xfffffffc(%ecx)
0x08048397 <main+10>: push %ecx
0x08048398 <main+11>: sub $0x18,%esp
0x0804839b <main+14>: movl $0x3,0xc(%esp)
0x080483a3 <main+22>: movl $0x1,0x10(%esp)
0x080483ab <main+30>: movl $0x2,0x14(%esp)
0x080483b3 <main+38>: mov 0x14(%esp),%eax
0x080483b7 <main+42>: mov %eax,0x4(%esp)
0x080483bb <main+46>: mov 0x10(%esp),%eax
0x080483bf <main+50>: mov %eax,(%esp)
0x080483c2 <main+53>: call 0x8048384 <foo>
0x080483c7 <main+58>: mov %eax,0xc(%esp)
0x080483cb <main+62>: mov 0xc(%esp),%eax
0x080483cf <main+66>: mov %eax,0x4(%esp)
0x080483d3 <main+70>: movl $0x8048504,(%esp)
0x080483da <main+77>: call 0x80482b8 <printf@plt.>
0x080483df <main+82>: mov 0xc(%esp),%eax
0x080483e3 <main+86>: add $0x18,%esp
0x080483e6 <main+89>: pop %ecx
0x080483e7 <main+90>: lea 0xfffffffc(%ecx),%esp
0x080483ea <main+93>: ret
End of assembler dump.
(gdb) disas foo
Dump of assembler code for function foo:
0x08048384 <foo+0>: mov 0x8(%esp),%eax
0x08048388 <foo+4>: add 0x4(%esp),%eax
0x0804838c <foo+8>: ret
End of assembler dump.
Видите? Ни одного намека на использование регистра EBP. Вся адресация в
стеке только через ESP. Таким способом создаются "плавающие" фреймы
стека, и называются они так из-за отсутствия какой-либо фиксированной
точки, относительно которой можно перемещаться по стеку, как это было в
случае c регистром EBP.
2.6 Соглашение fastcall
Как было упомянуто в начале статьи, существует соглашение fastcall, при
котором максимум параметров функции передается через регистры общего
назначения. Модифицируем вызов функции foo из Листинга 1 и посмотрим,
что из себя представляет ее ассемблерный дамп:
int __attribute__ ((fastcall)) foo(int a, int b)
{
return a+b;
}
bash-3.1$ gdb -q ./test
Using host libthread_db library "/lib/libthread_db.so.1".
(gdb) disas foo
Dump of assembler code for function foo:
0x08048354 <foo+0>: push %ebp
0x08048355 <foo+1>: mov %esp,%ebp
0x08048357 <foo+3>: sub $0x8,%esp
0x0804835a <foo+6>: mov %ecx,0xfffffffc(%ebp)
0x0804835d <foo+9>: mov %edx,0xfffffff8(%ebp)
0x08048360 <foo+12>: mov 0xfffffff8(%ebp),%eax
0x08048363 <foo+15>: add 0xfffffffc(%ebp),%eax
0x08048366 <foo+18>: leave
0x08048367 <foo+19>: ret
End of assembler dump.
Явно видно, как что-то грузится в область локальных данных функции из
регистров ECX и EDX. В этих регистрах, согласно документации, будут
находится оба параметра функции. Это нетрудно проверить:
(gdb) info reg ecx
ecx 0x1 1
(gdb) info reg edx
edx 0x2 2
При подготовке статьи использовались ОС Linux, компилятор gcc-4.1.2,
отладчик gdb-6.6.
Литература.
1. Intel. 64 and IA-32 Architectures Software Developer's
Manual. Volume 2B: Instruction Set Reference, N-Z (www.intel.com)
Vova
