(я набрал гист всего кода в этом ответе на случай, если вы захотите поиграть с ним)
Я только когда-либо делал самые простые вещи в asm во время моего курса CS101 в 2003 году. И я никогда не понимал, как работают asm и стек
пока я не понял, что все это по сути как программирование на C или C ++ ... но без локальных переменных, параметров и функций.
Наверное, пока не так просто :) Позвольте мне показать вам (для x86 asm с Intel синтаксис ).
1. Что такое стек
Стек - это непрерывный кусок памяти, выделяемый каждому потоку при его запуске. Вы можете хранить там все, что хотите. На языке C ++ ( фрагмент кода # 1 ):
const int STACK_CAPACITY = 1000;
thread_local int stack[STACK_CAPACITY];
2. Верх и низ стека
В принципе, вы можете хранить значения в случайных ячейках массива stack ( snippet # 2.1 ):
cin >> stack[333];
cin >> stack[517];
stack[555] = stack[333] + stack[517];
Но представьте, как трудно было бы вспомнить, какие ячейки stack уже используются, а какие "свободны". Вот почему мы храним новые значения в стеке рядом друг с другом.
Одна странная вещь в стеке (x86) asm заключается в том, что вы добавляете туда вещи, начиная с последнего индекса, и переходите к нижним индексам: stack [999], затем stack [998] и т. Д. ( snippet # 2.2 ):
cin >> stack[999];
cin >> stack[998];
stack[997] = stack[999] + stack[998];
И все же (осторожно, вы сейчас запутаетесь) "официальное" имя для stack[999] - это нижняя часть стека .
Последняя использованная ячейка (stack[997] в приведенном выше примере) называется вершина стека (см. Где вершина стека находится на x86 ).
3. Указатель стека (SP)
Стек - не единственная вещь, видимая повсюду в вашем коде asm. Вы также можете управлять регистрами ЦП (см. Регистры общего назначения ). Они действительно похожи на глобальные переменные:
int AX, BX, SP, BP, ...;
int main(){...}
Существует специальный регистр ЦП (SP) для отслеживания последнего элемента, добавленного в стек.
Как следует из названия, это, ну, указатель (содержит адрес памяти, такой как 0xAAAABBCC). Но для целей этого поста я буду использовать его в качестве индекса.
В начале потока SP == STACK_CAPACITY и затем вы уменьшаете его по мере необходимости. Правило состоит в том, что вы не можете записывать в ячейки стека за вершину стека, и любой индекс меньше SP недопустим, поэтому вы
сначала уменьшить SP и затем записать значение во вновь выделенную ячейку.
Когда вы знаете, что вы добавите несколько значений в стек подряд, вы можете зарезервировать место для всех них заранее ( фрагмент # 3 ):
SP -= 3;
cin >> stack[999];
cin >> stack[998];
stack[997] = stack[999] + stack[998];
Примечание. Теперь вы можете видеть, почему «распределение» в стеке происходит так быстро. Вы на самом деле ничего не выделяете (как в new ключевом слове или malloc), это всего лишь одно целочисленное уменьшение.
4. Избавление от локальных переменных
Давайте возьмем эту упрощенную функцию ( фрагмент # 4.1 ):
int triple(int a) {
int result = a * 3;
return result;
}
и переписать его без локальной переменной ( фрагмент # 4.2 ):
int triple_noLocals(int a) {
SP -= 1; // move pointer to unused cell, where we can store what we need
stack[SP] = a * 3;
return stack[SP];
}
использование ( фрагмент # 4.3 ):
// SP == 1000
someVar = triple_noLocals(11);
// now SP == 999, but we don't need the value at stack[999] anymore
// and we will move the stack index back, so we can reuse this cell later
SP += 1; // SP == 1000 again
5. Push / pop
Добавление нового элемента на вершину стека является настолько частой операцией, что процессоры имеют специальную инструкцию для этого, push.
Мы реализуем это следующим образом ( фрагмент 5.1 ):
void push(int value) {
--SP;
stack[SP] = value;
}
Аналогично, берется верхний элемент стека ( фрагмент 5.2 ):
void pop(int& result) {
result = stack[SP];
++SP; // note that `pop` decreases stack's size
}
Распространенная схема использования push / pop - это временное сохранение некоторого значения. Скажем, у нас есть кое-что полезное в переменной myVar, и по какой-то причине нам нужно выполнить вычисления, которые перезапишут это ( фрагмент 5.3 ):
int myVar = ...;
push(myVar); // SP == 999
myVar += 10;
... // do something with new value in myVar
pop(myVar); // restore original value, SP == 1000
6. Избавление от параметров
Теперь давайте передадим параметры, используя стек ( фрагмент # 6 ):
int triple_noL_noParams() { // `a` is at index 999, SP == 999
SP -= 1; // SP == 998, stack[SP + 1] == a
stack[SP] = stack[SP + 1] * 3;
return stack[SP];
}
int main(){
push(11); // SP == 999
assert(triple(11) == triple_noL_noParams());
SP += 2; // cleanup 1 local and 1 parameter
}
7. Избавление от return операторов
Давайте вернем значение в регистре AX ( фрагмент # 7 ):
void triple_noL_noP_noReturn() { // `a` at 998, SP == 998
SP -= 1; // SP == 997
stack[SP] = stack[SP + 1] * 3;
AX = stack[SP];
SP += 1; // finally we can cleanup locals right in the function body, SP == 998
}
void main(){
... // some code
push(AX); // save AX in case there is something useful there, SP == 999
push(11); // SP == 998
triple_noL_noP_noReturn();
assert(triple(11) == AX);
SP += 1; // cleanup param
// locals were cleaned up in the function body, so we don't need to do it here
pop(AX); // restore AX
...
}
8. Базовый указатель стека (BP) (также известный как указатель кадра ) и кадр стека
Давайте возьмем более «продвинутую» функцию и перепишем ее в нашем asm-подобном C ++ ( snippet # 8.1 ):
int myAlgo(int a, int b) {
int t1 = a * 3;
int t2 = b * 3;
return t1 - t2;
}
void myAlgo_noLPR() { // `a` at 997, `b` at 998, old AX at 999, SP == 997
SP -= 2; // SP == 995
stack[SP + 1] = stack[SP + 2] * 3;
stack[SP] = stack[SP + 3] * 3;
AX = stack[SP + 1] - stack[SP];
SP += 2; // cleanup locals, SP == 997
}
int main(){
push(AX); // SP == 999
push(22); // SP == 998
push(11); // SP == 997
myAlgo_noLPR();
assert(myAlgo(11, 22) == AX);
SP += 2;
pop(AX);
}
Теперь представьте, что мы решили ввести новую локальную переменную для хранения результатов перед возвратом, как мы это делаем в tripple (фрагмент # 4.1). Тело функции будет ( фрагмент # 8.2 ):
SP -= 3; // SP == 994
stack[SP + 2] = stack[SP + 3] * 3;
stack[SP + 1] = stack[SP + 4] * 3;
stack[SP] = stack[SP + 2] - stack[SP + 1];
AX = stack[SP];
SP += 3;
Видите ли, нам приходилось обновлять каждую ссылку на параметры функции и локальные переменные. Чтобы избежать этого, нам нужен индекс привязки, который не изменяется при увеличении стека.
Мы создадим якорь сразу после входа в функцию (перед тем, как выделять место для местных жителей), сохранив текущую вершину (значение SP) в регистре BP. Фрагмент # 8.3 :
void myAlgo_noLPR_withAnchor() { // `a` at 997, `b` at 998, SP == 997
push(BP); // save old BP, SP == 996
BP = SP; // create anchor, stack[BP] == old value of BP, now BP == 996
SP -= 2; // SP == 994
stack[BP - 1] = stack[BP + 1] * 3;
stack[BP - 2] = stack[BP + 2] * 3;
AX = stack[BP - 1] - stack[BP - 2];
SP = BP; // cleanup locals, SP == 996
pop(BP); // SP == 997
}
Срез стека, которому принадлежит функция и которая полностью контролирует функцию, называется кадр стека функции . Например. Кадр стека myAlgo_noLPR_withAnchor равен stack[996 .. 994] (оба идекса включительно).
Кадр начинается с BP функции (после того, как мы обновили его внутри функции) и продолжается до следующего кадра стека. Таким образом, параметры в стеке являются частью стекового фрейма вызывающей стороны (см. Примечание 8a).
Примечания:
8a. Википедия говорит иначе о параметрах , но здесь я придерживаюсь Руководство разработчика программного обеспечения Intel , см. Вып. 1, раздел 6.2.4.1 Базовый указатель стековой рамки и Рисунок 6-2 в разделе 6.3.2 Дальний вызов и RET . Параметры функции и кадр стека являются частью записи активации функции (см. Общие сведения о функциях ).
8b. положительные смещения от точки ВР к параметрам функции и отрицательные смещения указывают на локальные переменные. Это очень удобно для отладки
8c. stack[BP] хранит адрес предыдущего кадра стека, stack[stack[BP]] сохраняет предыдущий кадр стека и так далее. Следуя этой цепочке, вы можете обнаружить кадры всех функций в программе, которые еще не вернулись. Вот как отладчики показывают вам стек вызовов
8d. первые 3 инструкции myAlgo_noLPR_withAnchor, где мы настраиваем фрейм (сохранить старый БП, обновить БП, зарезервировать место для местных жителей), называются Пролог функции
9. Соглашения о вызовах
В фрагменте 8.1 мы поместили параметры для myAlgo справа налево и вернули результат в AX.
Мы могли бы также передать параметры слева направо и вернуться в BX. Или передайте параметры в BX и CX и верните в AX. Очевидно, что вызывающий абонент (main()) и
вызываемая функция должна согласовать, где и в каком порядке хранится весь этот материал.
Соглашение о вызовах - это набор правил о том, как передаются параметры и возвращается результат.
В приведенном выше коде мы использовали соглашение о вызовах cdecl :
- Параметры передаются в стеке с первым аргументом по наименьшему адресу в стеке во время вызова (помещается последним <...>). Вызывающая сторона отвечает за возврат параметров из стека после вызова.
- возвращаемое значение помещается в AX
- EBP и ESP должны сохраняться вызываемым абонентом (в нашем случае это функция
myAlgo_noLPR_withAnchor), чтобы вызывающий абонент (функция main) мог полагаться на те регистры, которые не были изменены вызовом.
- Все остальные регистры (EAX, <...>) могут быть свободно изменены вызываемым пользователем; если вызывающая сторона желает сохранить значение до и после вызова функции, она должна сохранить значение в другом месте (мы делаем это с AX)
(Источник: пример "32-битного cdecl" из документации по переполнению стека; авторские права 2016 icktoofay и Peter Cordes ; лицензированы по CC BY-SA 3.0. архив полного содержимого документации по переполнению стека можно найти на archive.org, где этот пример проиндексирован по идентификатору темы 3261 и примеру 11196.)
10. Избавление от вызовов функций
Теперь самая интересная часть. Как и данные, исполняемый код также хранится в памяти (полностью не связан с памятью для стека), и каждая инструкция имеет адрес.
Если не указано иное, CPU выполняет инструкции одну за другой в порядке их сохранения в памяти. Но мы можем дать команду CPU «перепрыгнуть» в другое место в памяти и выполнить оттуда инструкции.
В asm это может быть любой адрес, а в более высокоуровневых языках, таких как C ++, вы можете переходить только к адресам, отмеченным метками ( есть обходные пути , но они не очень приятные, если не сказать больше).
Давайте возьмем эту функцию ( фрагмент # 10.1 ):
int myAlgo_withCalls(int a, int b) {
int t1 = triple(a);
int t2 = triple(b);
return t1 - t2;
}
И вместо того, чтобы вызывать tripple C ++ way, сделайте следующее:
- копия всего тела
tripple внутри myAlgo
- в
myAlgo запись перепрыгивает через tripple код с goto
- когда нам нужно выполнить код
tripple, сохраните адрес стека строки кода сразу после вызова tripple, чтобы мы могли вернуться сюда позже и продолжить выполнение (макрос PUSH_ADDRESS ниже)
- перейти к адресу функции
tripple и выполнить его до конца (3. и 4. вместе - макрос CALL)
- в конце
tripple (после того, как мы очистили локальных), взять адрес возврата с вершины стека и прыгнуть туда (RET макрос)
Поскольку в C ++ нет простого способа перехода к определенному адресу кода, мы будем использовать метки для обозначения мест перехода.
Я не буду вдаваться в подробности, как работают макросы ниже, просто поверьте мне, они делают то, что я говорю, они делают ( сниппет # 10.2 ):
// pushes the address of the code at label's location on the stack
// NOTE1: this gonna work only with 32-bit compiler (so that pointer is 32-bit and fits in int)
// NOTE2: __asm block is specific for Visual C++. In GCC use https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
#define PUSH_ADDRESS(labelName) { \
void* tmpPointer; \
__asm{ mov [tmpPointer], offset labelName } \
push(reinterpret_cast<int>(tmpPointer)); \
}
// why we need indirection, read https://stackoverflow.com/a/13301627/264047
#define TOKENPASTE(x, y) x ## y
#define TOKENPASTE2(x, y) TOKENPASTE(x, y)
// generates token (not a string) we will use as label name.
// Example: LABEL_NAME(155) will generate token `lbl_155`
#define LABEL_NAME(num) TOKENPASTE2(lbl_, num)
#define CALL_IMPL(funcLabelName, callId) \
PUSH_ADDRESS(LABEL_NAME(callId)); \
goto funcLabelName; \
LABEL_NAME(callId) :
// saves return address on the stack and jumps to label `funcLabelName`
#define CALL(funcLabelName) CALL_IMPL(funcLabelName, __LINE__)
// takes address at the top of stack and jump there
#define RET() { \
int tmpInt; \
pop(tmpInt); \
void* tmpPointer = reinterpret_cast<void*>(tmpInt); \
__asm{ jmp tmpPointer } \
}
void myAlgo_asm() {
goto my_algo_start;
triple_label:
push(BP);
BP = SP;
SP -= 1;
// stack[BP] == old BP, stack[BP + 1] == return address
stack[BP - 1] = stack[BP + 2] * 3;
AX = stack[BP - 1];
SP = BP;
pop(BP);
RET();
my_algo_start:
push(BP); // SP == 995
BP = SP; // BP == 995; stack[BP] == old BP,
// stack[BP + 1] == dummy return address,
// `a` at [BP + 2], `b` at [BP + 3]
SP -= 2; // SP == 993
push(AX);
push(stack[BP + 2]);
CALL(triple_label);
stack[BP - 1] = AX;
SP -= 1;
pop(AX);
push(AX);
push(stack[BP + 3]);
CALL(triple_label);
stack[BP - 2] = AX;
SP -= 1;
pop(AX);
AX = stack[BP - 1] - stack[BP - 2];
SP = BP; // cleanup locals, SP == 997
pop(BP);
}
int main() {
push(AX);
push(22);
push(11);
push(7777); // dummy value, so that offsets inside function are like we've pushed return address
myAlgo_asm();
assert(myAlgo_withCalls(11, 22) == AX);
SP += 1; // pop dummy "return address"
SP += 2;
pop(AX);
}
Примечания:
10a. , поскольку адрес возврата хранится в стеке, в принципе мы можем его изменить. Вот как атака с разбиванием стека работает
10b. последние 3 инструкции в "конце" triple_label (очистка локальных объектов, восстановление старого BP, возврат) называются эпилогом функции
11. Монтаж
Теперь давайте посмотрим на настоящий asm для myAlgo_withCalls. Для этого в Visual Studio:
- установить платформу сборки на x86
- тип сборки: отладка
- установить точку останова где-нибудь внутри myAlgo_withCalls
- запустить, и когда выполнение остановится в точке останова, нажмите Ctrl + Alt + D
Одно отличие от нашего asm-подобного C ++ состоит в том, что стек asm работает с байтами, а не с целыми числами. Таким образом, чтобы зарезервировать место для одного int, SP будет уменьшен на 4 байта.
Здесь мы идем ( фрагмент # 11.1 , номера строк в комментариях взяты из gist ):
; 114: int myAlgo_withCalls(int a, int b) {
push ebp ; create stack frame
mov ebp,esp
; return address at (ebp + 4), `a` at (ebp + 8), `b` at (ebp + 12)
sub esp,0D8h ; reserve space for locals. Compiler can reserve more bytes then needed. 0D8h is hexadecimal == 216 decimal
push ebx ; cdecl requires to save all these registers
push esi
push edi
; fill all the space for local variables (from (ebp-0D8h) to (ebp)) with value 0CCCCCCCCh repeated 36h times (36h * 4 == 0D8h)
; see https://stackoverflow.com/q/3818856/264047
; I guess that's for ease of debugging, so that stack is filled with recognizable values
; 0CCCCCCCCh in binary is 110011001100...
lea edi,[ebp-0D8h]
mov ecx,36h
mov eax,0CCCCCCCCh
rep stos dword ptr es:[edi]
; 115: int t1 = triple(a);
mov eax,dword ptr [ebp+8] ; push parameter `a` on the stack
push eax
call triple (01A13E8h)
add esp,4 ; clean up param
mov dword ptr [ebp-8],eax ; copy result from eax to `t1`
; 116: int t2 = triple(b);
mov eax,dword ptr [ebp+0Ch] ; push `b` (0Ch == 12)
push eax
call triple (01A13E8h)
add esp,4
mov dword ptr [ebp-14h],eax ; t2 = eax
mov eax,dword ptr [ebp-8] ; calculate and store result in eax
sub eax,dword ptr [ebp-14h]
pop edi ; restore registers
pop esi
pop ebx
add esp,0D8h ; check we didn't mess up esp or ebp. this is only for debug builds
cmp ebp,esp
call __RTC_CheckEsp (01A116Dh)
mov esp,ebp ; destroy frame
pop ebp
ret
И asm для tripple ( фрагмент # 11.2 ):
push ebp
mov ebp,esp
sub esp,0CCh
push ebx
push esi
push edi
lea edi,[ebp-0CCh]
mov ecx,33h
mov eax,0CCCCCCCCh
rep stos dword ptr es:[edi]
imul eax,dword ptr [ebp+8],3
mov dword ptr [ebp-8],eax
mov eax,dword ptr [ebp-8]
pop edi
pop esi
pop ebx
mov esp,ebp
pop ebp
ret
Надеюсь, после прочтения этого поста сборка выглядит не так загадочно, как раньше :)
Вот ссылки из тела поста и некоторые дальнейшие чтения:
- Эли Бендерский, Там, где вершина стека находится на x86 - верх / низ, push / pop, SP, кадр стека, соглашения о вызовах
- Eli Bendersky, Расположение кадра стека на x86-64 - передача аргументов на x64, кадр стека, красная зона
- Университет Мариленда, Понимание стека - действительно хорошо написанное введение в концепции стеков. (Это для MIPS (не x86) и в синтаксисе GAS, но для темы это несущественно). См. Другие примечания по MIPS ISA Programming , если интересно.
- x86 Asm wikibook, Регистры общего назначения
- x86 Разборка викибук, Стек
- x86 Разборка викибук, Функции и рамки стека
- Руководства разработчика программного обеспечения Intel - Я ожидал, что он будет действительно хардкорным, но удивительно, что его довольно легко прочитать (хотя объем информации огромен)
- Джонатан де Бойн Поллард, Общая информация о перилогах функций - пролог / эпилог, кадр стека / запись активации, красная зона