Устройство Стека для Intel386

Введение

Стек (от англ. 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
  movl %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

Заключение

Работа со стеком - важная часть для любого языка программирования, особенно низкоуровнего, однако полезно знать, как она устроена и для высокоуровневых языков, хотя для них она может значительно отличаться из-за самих концепций языка.

1. System V ABI Intel386

2. Документация по GNU Assembler

3. Стек, как структура данных

4. Сравнительная таблица производительности инструкций ассемблера

5. Описание операций инструкции ENTER

6. Описание операций инструкции LEAVE

7. Описание инструкции PUSH

8. Описание инструкции POP

9. Исходный код программы на GitHub

UPD1: Недолго думая на пэрроне, решил поправить перевод слова Stack на русский (Стэк Стек). @Cdracm , благодарю за замечание

UPD2: Огромное спасибо @berez за замечания по поводу указателя на вершину стека, а именно значения регистра ESP до и после push'а/pop'a чего-либо на/со стек(а), а также за поправку, насчёт регистра SS