Введение
Стэк (от англ. Stack) - специально отведённое место в памяти для хранения временных данных. Он подчиняется следующим правилам
LIFO (Last In First Out), который подразумевает, что элемент, который был помещён на стэк последним, будет первым оттуда удалён
Стэк растёт в сторону начала адресного пространства (ещё говорят, что стэк растёт вниз)
Минимальная единица, которая может быть удалена\помещена со\на стэк(а) - 16 бит (2 байта)
Максимальная единица, которая может быть удалена\помещена со\на стэк(а) - 32 бита (4 байта)
Устройство Стэка
Как видно из Рисунка 1, при помещении чего-либо на стэк, он увеличивается вниз. Указатель стэка (ESP - Stack Pointer) указывает на последний элемент стэка, который был туда помещён, эту часть стэка также называют вершиной стэка (от англ. TOS - Top Of Stack)
Когда что-то помещается на стэке, процессор декрементирует значение в регистре ESP и записывает записывает помещаемое значение на вершину стэка. В случае, когда необходимо что-то удалить со стэка, процессор сначала копирует удаляемое значение с вершины стэка, а затем уже инкрементирует значение в регистре ESP.
Чтобы процессор смог понять, что ему нужно сохранить на стэк, используется инструкция push
в ассемблерном коде, в случае удаления - pop
Инструкция push
Её синтаксис может разнится от одного языка ассемблера к другому, однако суть её остаётся неизменной - помещение какого-либо значения на стэк
PUSH r/m16
PUSH r/m32
PUSH r16
PUSH r32
PUSH imm8
PUSH imm16
PUSH imm32
Префикс
r/m
(от англ. register/memory) означает, что значение, которое необходимо поместить на стэк находится в памяти, которая в свою очередь находится в регистре, например, в регистре лежит значение0x87654321
- адрес памяти, по которому хранится значение0x11223344
, соответственно на стэк будет помещено значение0x11223344
Префикс
r
(от англ. register) означает, что значение, которое необходимо поместить на стэк, находится в регистреПрефикс
imm
(от англ. immediate), т.е. значение, которое непосредственно передаётся инструкции в качестве параметраПостфиксы 8, 16, 32 означают сколько бит содержит, передаваемое инструкции, значение, которое в свою очередь, обычно называют операндом
На данный момент может возникнуть вопрос от том, что, как писалось выше, минимальная единица, которая может быть помещена на стэк - 16 бит, но в синтаксисе инструкции push
есть imm8
, говорящее о том, что операндом инструкции может быть 8-битное значение. На самом деле, 8-битные значения дополняются до 16-битных, т.к. стэк выровнен по 16 бит, однако это имеет значение и для знаковых типов, которые используют 2-ое дополнение.
Инструкция pop
Синтаксис инструкции pop аналогичен тому, который используется в инструкции push
, за исключением того, что значение удаляется со стэка и помещается в операнд инструкции
POP r/m16
POP r/m32
POP r16
POP r32
А также, по очевидным причинам, операндом инструкции pop
не может быть immediate value, т.к. мы не можем сохранить что-либо туда
Регистры для управления стэком
Уже был упомянут один из регистров, который повзволяет управлять стэком - ESP (Stack Pointer), пожалуй, это самый важный регистр, который хранит, указатель на вершину стэка, однако есть ещё несколько регистров, связанных со стэком
SS (Stack Segment) - регистр, указывающий на определённый сегмент памяти, в котором находится текущий фрейм, только одним фреймом можно манипулировать в конкретный момент времени, этот регистр задействуется процессором для всех операций, связанных со стэком
EBP (Base Pointer) - регистр, указывающий на текущий фрейм, т.е. на начало стэка для конкретной процедуры\функции, обычно используется для адресации локальных переменных и аргументов процедуры\функции
Соглашение о вызовах функций в System V Intel386
В System V Intel386 (далее System V) существует несколько правил для вызова функций и соответственно передачи им аргументов, эти правила распространяются исключительно на глобальные функции, локальные функции могут не следовать этим правилам (однако это считается не лучшим выбором)
Аргументы вызываемой функции помещаются на стэк в обратном порядке по отношению к вызывающей функции, т.е. вызывающая функция (от англ. caller) сначала должна поместить на стэк последний аргумент, затем предпоследний и т.д. до первого, затем вызываемая функция (от англ. callee) может забрать со стэка аргументы в привычном для неё порядке
Регистры EBP, EBX, EDI, ESI и ESP могут изменяться вызываемой функцией, соответственно, если вызывающая функция хранит какое-либо значение в одном из этих регистров - она сначала должна поместить значения этих регистров на стэке, а после восстановить их, исключение составляет регистр EBP, которые не изменяется при вызове функции и продолжает указывать на предыдущий фрейм (на фрейм вызывающей функции), поэтому он помещается на стэк вызываемой функцией в начале её выполнения и восстанавливается по завершении, то же каксается и регистра ESP
При осуществлении вызова функции используется инструкция
call
в ассемблере, которая сохраняет на стэке адрес, следующей за ней [call] инструкции, который обычно называют return addressЕсли функция возвращает какое-либо значение - она должна поместить его в регистр EAX, в ином случае она не должна ничего сохранять в какой-либо регистр (восстановить все регистры по завершении)
Таким образом, после вызова функции (после выполнения инструкции call
), стэк будет выглядеть следующим образом
Как показано на Рисунке 2, первое, что есть на текущем фрейме - адрес следующей после call
инструкции, далее идёт сохранённое значение регистра EBP, указывающее на предыдущий фрейм, а затем идут локальные переменные относящиеся к конкретной функции
Всё, что выше return address относится к предыдущему фрейму, включая аргументы, переданные вызываемой функции,следовательно, первый аргумент будет в EBP + 8, второй в EBP + 12, и т.д., за исключением случаев, когда аргументом является 16-битное значение
Пример работы со стэком на GNU Assembler x86
В качестве примера работы со стэком будет рассматриваться вывод аргументов командной строки, которые будут индексироватся с помощью локальной переменной, а также вывод переменных окружения
В примере будет использоваться GNU Assembler (GAS), который использует синтаксис AT&T, для сборки используется GCC
Начнём с того, как будет выглядеть стэк для функции main
:
Stack
envp <-- EBP + 16
argv <-- EBP + 12
argc <-- EBP + 8
return address <-- EBP + 4
saved EBP <-- EBP
local argv index <-- EBP - 4
В качестве аргументов были переданы argc, argv и envp и находятся они, соответственно, в EBP + 8, EBP + 12 и EBP + 16, return address - как уже упоминалось - адрес, следующий за инструкцией call
, local argv index - локальная переменная для красивого вывода (ну почти) массива argv
Для начала в секции .rodata (Read-Only Data) создадим 3 переменные, которые будут форматированными строками, для вывода argc, argv и envp
.section .rodata
argc_str:
.string "argc = %d\n\n"
argv_str:
.string "argv[%d] = %s\n"
envp_str:
.string "%s\n"
Затем объявим в секции .text функцию main, где собственно, и будет код программы, и пометим её, как глобальную
.section .text
.globl main
main:
В самом начале функции помещаем регистр EBP на стэк и делаем его локальным указателем на текущий фрейм
pushl %ebp
pushl %esp, %ebp
Помещаем argc и указатель на массив argv в EDI и ESI соответственно, а также аллоцируем на стэке 4 байта для локальной перменной и инициализируем её значением нулём
/* move argc into edi */
movl 8(%ebp), %edi
/* move argv base address into esi */
movl 12(%ebp), %esi
/* allocate 4 bytes on the stack */
subl $4, %esp
/* initialize local variable by 0 */
movl $0, -4(%ebp)
Теперь можно заняться выводом argc, для этого необходимо в обратном порядке поместить все аргументы функции (в данном случае используется printf
), а после вызова очистить стэк, т.к. в System V очисткой стэка занимается вызывающая сторона
Аргументами функции будут форматированная сторка и значение argc, которое хранится в регистре EDI
pushl %edi
pushl $argc_str
call printf
addl $4, %esp
popl %edi
Стоит заметить, что на стэк мы помещаем не значение, которое хранится в argc_str
, а её адрес, т.к. printf
ожидает именно указатель на форматированную строку
Следующим шагом будет вывод массива argv, который будет осуществляться в цикле, однако перед этим необходимо понимать, что argv содержит адрес памяти, по которому лежит массив символов (необходимая нам строка), поэтому первым аргументом будет адрес, лежащий в argv, вторым аргументом будет адрес, лежащий в argv + 4, и т.д., здесь мы прибавляем по 4 байта, т.к. адрес - это 32-битное (4-байтовое) число
_pr_args:
cmpl -4(%ebp), %edi /* if index == argc: */
je _pr_args_out /* goto pr_args_out */
pushl (%esi) /* element in argv */
pushl -4(%ebp) /* index */
pushl $argv_str /* format string */
call printf
addl $4, %esp
popl -4(%ebp)
popl (%esi)
incl -4(%ebp) /* increment index */
/* point to the next arg */
addl $4, %esi
jmp _pr_args
_pr_args_out:
Первым делом, в цикле проверяется значение индекса и argc, в случае если они равны (напоминаю, что индексация массива в данном случае идёт с нуля, поэтому последний элемент в массиве argv будет argv + (argc - 1)
), то мы просто выходим из цикла, иначе же вызываем функцию printf (регистр ESI содержит адрес argv), чистим стэк, увеличиваем индекс на единицу, перемещаем указатель на следующий элемент в массиве argv и возвращаемся в начало цикла
После чего, чтобы отделить масив argv от массива envp, сделаем перенос строки (символ переноса строки - \n
, который в десятичном представлении имеет значение 10, а в шестнадцатеричном, соответственно, 0xA), для этого используем функцию putchar
pushl $0xA
call putchar
addl $4, %esp
Далее мы будем импользовать тот же регистр ESI для хранения указателей на переменные окружения в массиве envp, как и в случае с argv
movl 16(%ebp), %esi
Теперь, т.к. у нас нет индекса для массива envp, а также мы не знаем заранее, сколько там будет элементов, необходимо вспомнить, что массив envp - это нуль-терминированный массив, поэтому, чтобы узнать, что больше элементов нет - достаточно проверить равен ли нулю элемент (он будет следовать за последним)
_pr_envp:
cmpl $0, (%esi)
je _out
pushl (%esi) /* environment variable */
pushl $envp_str /* format string */
call printf
addl $4, %esp
popl (%esi)
/* point to the next element in envp */
addl $4, %esi
jmp _pr_envp
_out:
Цикл вывода переменных окружения не сильно отличается от того, что использовался для вывода массива аргументов командной строки, за исключением проверки выхода из цикла и отсутствием индекса
Ну и в самом конце необходимо установить возвращаемое значение функции в ноль, а также произвести очистку стэка
/* set up return value */
movl $0, %eax
popl %ebp
movl %ebp, %esp
ret
Очистка стэка производится путём восстановления регистра EBP и ESP в их исходные значения, следовательно всё, что было в этой функции может быть перезаписано и использовано другими функциями\процедурами, инструкция ret
устанавливает в EIP (Instruction Pointer) значение return address, таким образом управление возрвращается вызывающей стороне
Важно упомянуть, что существует более удобная инструкцию для очистки стэка - leave
, она выполняет именно эти две вещи - восстановление регистров EBP и ESP, соответственно последняя часть кода может быть переписана следующим образом
/* set up return value */
movl $0, %eax
leave
ret
Однако у этой инструкции есть менее привлекателный компаньон - инструкция enter
, у неё два операнда, первый отвечает за количество байт, которое необходимо аллоцировать на стэке, а второй за уровень вложенности, из-за чего реализация подобной инструкции достаточно сложна и не ограничивается этими тремя инструкциями
pushl %ebp
movl %esp, %ebp
subl $N, %esp
Поэтому выполняется в разы медленнее, из-за чего большинство компиляторов стараются её избегать, однако, для демонстрации, те три строчки можно заменить одной
enter $4, $0
Теперь подошло время проверить работу программы, для этого используем gcc
, чтобы скомпилировать и слинковать ассемблерный код
$ gcc -o args args.S
Или, в случае, если хостом является x64
$ gcc -m32 -o args args.S
И, наконец, можно запустить программу
$ ./args
Заключение
Работа со стэком - важная часть для любого языка программирования, особенно низкоуровнего, однако полезно знать, как она устроена и для высокоуровневых языков, однако для них она может значительно отличаться из-за самих концепций языка
System V ABI Intel386
Документация по GNU Assembler
Стэк, как структура данных
Сравнительная таблица производительности инструкций ассемблера
Описание операций инструкции ENTER
Описание операций инструкции LEAVE
Описание инструкции PUSH
Описание инструкции POP
Исходный код программы на GitHub