Как именно работает стек вызовов?

Я пытаюсь глубже понять, как работают низкоуровневые операции языков программирования и особенно как они взаимодействуют с ОС / ЦП. Я, наверное, читал все ответы в каждой теме, связанной со стеком / кучей, здесь, на Stack Overflow, и все они великолепны. Но есть еще одна вещь, которую я еще не полностью понял.

Рассмотрим эту функцию в псевдокоде, который, как правило, является действительным кодом Rust ;-)

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(a, b);
    doAnotherThing(c, d);
}

Вот как я предполагаю, что стек будет выглядеть в строке X:

Stack

a +-------------+
  | 1           | 
b +-------------+     
  | 2           |  
c +-------------+
  | 3           | 
d +-------------+     
  | 4           | 
  +-------------+ 

Все, что я читал о том, как работает стек, - это то, что он строго подчиняется правилам LIFO (последний пришел, первый ушел). Точно так же, как тип данных стека в .NET, Java или любом другом языке программирования.

Но если это так, то что происходит после строки X? Потому что, очевидно, следующее, что нам нужно, - это работать с aи b, но это будет означать, что ОС / ЦП (?) Должны выскочить dи cсначала вернуться к aи b. Но тогда он прострелил бы себе ногу, потому что ему нужно cи dв следующей строке.

Итак, мне интересно, что именно происходит за кулисами?

Другой связанный с этим вопрос. Предположим, мы передаем ссылку на одну из других функций следующим образом:

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(&a, &b);
    doAnotherThing(c, d);
}

Насколько я понимаю, это будет означать, что параметры в doSomethingпо существу указывают на тот же адрес памяти, что aи bв foo. Но тогда снова это означает , что не существует не всплывал стек , пока не дойдете до aиb произойдет.

Эти два случая заставляют меня думать, что я не совсем понял, как именно работает стек и как он строго следует правилам LIFO .

Стек вызовов также можно назвать стеком кадров.
По принципу LIFO складываются не локальные переменные, а целые кадры стека («вызовы») вызываемых функций . Локальные переменные вставляются и выталкиваются вместе с этими кадрами в так называемом прологе функции и эпилоге. соответственно.

Внутри фрейма порядок переменных полностью не определен; Компиляторы «переупорядочивают» позиции локальных переменных внутри кадра соответствующим образом, чтобы оптимизировать их выравнивание, чтобы процессор мог получить их как можно быстрее. Важным фактом является то, что смещение переменных относительно некоторого фиксированного адреса является постоянным на протяжении всего времени существования кадра. поэтому достаточно взять адрес привязки, скажем, адрес самого кадра, и работать со смещениями этого адреса до переменные. Такой адрес привязки фактически содержится в так называемом указателе базы или кадра.который хранится в регистре EBP. С другой стороны, смещения четко известны во время компиляции и поэтому жестко закодированы в машинный код.

Этот рисунок из Википедии показывает, как устроен типичный стек вызовов ¹ :

Добавьте смещение переменной, к которой мы хотим получить доступ, к адресу, содержащемуся в указателе кадра, и мы получим адрес нашей переменной. Короче говоря, код просто обращается к ним напрямую через постоянные смещения времени компиляции от базового указателя; Это простая арифметика с указателями.

пример

#include <iostream>

int main()
{
    char c = std::cin.get();
    std::cout << c;
}

gcc.godbolt.org дает нам

main:
    pushq   %rbp
    movq    %rsp, %rbp
    subq    $16, %rsp

    movl    std::cin, %edi
    call    std::basic_istream<char, std::char_traits<char> >::get()
    movb    %al, -1(%rbp)
    movsbl  -1(%rbp), %eax
    movl    %eax, %esi
    movl    std::cout, %edi
    call    [... the insertion operator for char, long thing... ]

    movl    $0, %eax
    leave
    ret

.. для main. Я разделил код на три подраздела. Пролог функции состоит из первых трех операций:

• Базовый указатель помещается в стек.
• Указатель стека сохраняется в базовом указателе
• Указатель стека вычитается, чтобы освободить место для локальных переменных.

Затем cinперемещается в регистр EDI ² иget вызывается; Возвращаемое значение - в EAX.

Все идет нормально. Теперь происходит интересное:

Младший байт EAX, обозначенный 8-битным регистром AL, берется и сохраняется в байте сразу после базового указателя : то есть -1(%rbp)смещение базового указателя равно -1. Этот байт - наша переменнаяc . Смещение отрицательное, потому что стек растет вниз на x86. Следующая операция сохраняет cв EAX: EAX перемещаются ESI, coutперемещаются в ЭОД , а затем оператор вставки вызываются coutи cбыть аргументы.

В заключение,

• Возвращаемое значение mainсохраняется в EAX: 0. Это из-за неявного returnоператора. Вы также можете увидеть xorl rax raxвместоmovl .
• уйти и вернуться на место вызова. leaveсокращает этот эпилог и неявно
  • Заменяет указатель стека на базовый указатель и
  • Выдвигает указатель базы.

После того, как эта операция retбыла выполнена, фрейм фактически выталкивается, хотя вызывающей стороне все равно нужно очистить аргументы, поскольку мы используем соглашение о вызовах cdecl. Другие соглашения, например stdcall, требуют от вызываемого объекта наведения порядка, например, путем передачи количества байтов в ret.

Пропуск указателя кадра

Также возможно использовать смещения не от указателя базы / кадра, а от указателя стека (ESB). Это делает регистр EBP, который в противном случае содержал бы значение указателя кадра, доступным для произвольного использования, но это может сделать невозможной отладку на некоторых машинах и будет неявно отключен для некоторых функций . Это особенно полезно при компиляции для процессоров с небольшим количеством регистров, включая x86.

Эта оптимизация известна как FPO (пропуск указателя кадра) и устанавливается -fomit-frame-pointerв GCC и -Oyв Clang; обратите внимание, что он неявно запускается при каждом уровне оптимизации> 0 тогда и только тогда, когда отладка все еще возможна, поскольку она не требует никаких дополнительных затрат. Для получения дополнительной информации см. Здесь и здесь .

¹ Как указано в комментариях, указатель кадра предположительно предназначен для указания адреса после адреса возврата.

² Обратите внимание, что регистры, начинающиеся с R, являются 64-битными аналогами регистров, которые начинаются с E. EAX обозначает четыре младших байта RAX. Для ясности я использовал названия 32-битных регистров.

Потому что, очевидно, следующее, что нам нужно, - это работать с a и b, но это будет означать, что ОС / ЦП (?) Должны сначала вывести d и c, чтобы вернуться к a и b. Но тогда он выстрелит себе в ногу, потому что ему нужны c и d в следующей строке.

Коротко:

Нет необходимости выдвигать аргументы. На аргументы, передаваемые вызывающей стороной fooфункции doSomethingи локальные переменные в, doSomething можно ссылаться как на смещение от базового указателя .
Так,

• Когда выполняется вызов функции, аргументы функции помещаются в стек. На эти аргументы далее ссылается базовый указатель.
• Когда функция возвращается к вызывающей стороне, аргументы возвращаемой функции выгружаются из стека с помощью метода LIFO.

В деталях:

Правило состоит в том, что каждый вызов функции приводит к созданию фрейма стека (минимум - адрес, на который нужно вернуться). Итак, если funcAвызовы funcBи funcBвызовы funcC, три кадра стека устанавливаются один поверх другого. Когда функция возвращается, ее фрейм становится недействительным . Нормально настроенная функция действует только на свой собственный стековый фрейм и не нарушает чужой. Другими словами, POPing выполняется в верхний фрейм стека (при возврате из функции).

Стек в вашем вопросе настраивается вызывающим абонентом foo. Когда вызываются doSomethingи doAnotherThing, они устанавливают свой собственный стек. Рисунок может помочь вам понять это:

Обратите внимание, что для доступа к аргументам тело функции должно пройти вниз (более высокие адреса) от места, где хранится адрес возврата, а для доступа к локальным переменным тело функции должно пройти вверх по стеку (более низкие адреса ) относительно места, где хранится обратный адрес. Фактически, типичный код, сгенерированный компилятором для функции, будет делать именно это. Компилятор выделяет для этого регистр EBP (базовый указатель). Другое название этого - указатель кадра. Обычно компилятор первым делом для тела функции помещает текущее значение EBP в стек и устанавливает EBP на текущий ESP. Это означает, что, как только это будет выполнено, в любой части кода функции аргумент 1 находится на расстоянии EBP + 8 (4 байта для каждого из EBP вызывающего абонента и адреса возврата), аргумент 2 - это EBP + 12 (десятичный), локальные переменные находятся на расстоянии EBP-4n.

.
.
.
[ebp - 4]  (1st local variable)
[ebp]      (old ebp value)
[ebp + 4]  (return address)
[ebp + 8]  (1st argument)
[ebp + 12] (2nd argument)
[ebp + 16] (3rd function argument) 

Взгляните на следующий код C для формирования кадра стека функции:

void MyFunction(int x, int y, int z)
{
     int a, int b, int c;
     ...
}

Когда звонящий звонит

MyFunction(10, 5, 2);  

будет сгенерирован следующий код

^
| call _MyFunction  ; Equivalent to: 
|                   ; push eip + 2
|                   ; jmp _MyFunction
| push 2            ; Push first argument  
| push 5            ; Push second argument  
| push 10           ; Push third argument  

и код сборки для функции будет (настраивается вызываемым перед возвратом)

^
| _MyFunction:
|  sub esp, 12 ; sizeof(a) + sizeof(b) + sizeof(c)
|  ;x = [ebp + 8], y = [ebp + 12], z = [ebp + 16]
|  ;a = [ebp - 4] = [esp + 8], b = [ebp - 8] = [esp + 4], c = [ebp - 12] =   [esp]
|  mov ebp, esp
|  push ebp
 

Ссылки:

• Соглашения о вызове функций и стек .
• Указатель кадра и локальные переменные .
• Дизассемблирование x86 / Функции и фреймы стека .

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

Я вставлю несколько примеров из книги Ника Парланте «Указатели и память». Я думаю, что ситуация немного проще, чем вы предполагали.

Вот код:

void X() 
{
  int a = 1;
  int b = 2;

  // T1
  Y(a);

  // T3
  Y(b);

  // T5
}

void Y(int p) 
{
  int q;
  q = p + 2;
  // T2 (first time through), T4 (second time through)
}

Точки во времени T1, T2, etc. отмечены в коде, а состояние памяти в это время показано на чертеже:

Различные процессоры и языки используют несколько разных конструкций стека. Два традиционных шаблона на 8x86 и 68000 называются соглашением о вызовах Pascal и соглашением о вызовах C; каждое соглашение обрабатывается одинаково в обоих процессорах, за исключением имен регистров. Каждый из них использует два регистра для управления стеком и соответствующими переменными, называемыми указателем стека (SP или A7) и указателем кадра (BP или A6).

При вызове подпрограммы с использованием любого соглашения, любые параметры помещаются в стек перед вызовом подпрограммы. Затем код подпрограммы помещает текущее значение указателя фрейма в стек, копирует текущее значение указателя стека в указатель фрейма и вычитает из указателя стека количество байтов, используемых локальными переменными [если есть]. Как только это будет сделано, даже если дополнительные данные помещены в стек, все локальные переменные будут сохранены в переменных с постоянным отрицательным смещением от указателя стека, и все параметры, которые были помещены в стек вызывающей стороной, могут быть доступны в постоянное положительное смещение от указателя кадра.

Разница между этими двумя соглашениями заключается в том, как они обрабатывают выход из подпрограммы. В соглашении C возвращающая функция копирует указатель кадра в указатель стека [восстанавливает его до значения, которое он имел сразу после того, как был помещен указатель старого кадра], извлекает значение указателя старого кадра и выполняет возврат. Любые параметры, которые вызывающий объект поместил в стек перед вызовом, останутся там. Согласно соглашению Паскаля, после извлечения старого указателя кадра процессор извлекает адрес возврата функции, добавляет к указателю стека количество байтов параметров, переданных вызывающей стороной, и затем переходит к извлеченному адресу возврата. На исходном 68000 необходимо было использовать последовательность из 3 инструкций для удаления параметров вызывающего абонента; Процессоры 8x86 и все 680x0 после оригинала включали "ret N"

Соглашение Pascal имеет то преимущество, что экономит немного кода на стороне вызывающей стороны, поскольку вызывающей стороне не нужно обновлять указатель стека после вызова функции. Однако для этого требуется, чтобы вызываемая функция точно знала, сколько байтов параметров вызывающая программа собирается поместить в стек. Отсутствие правильного количества параметров в стеке перед вызовом функции, использующей соглашение Паскаля, почти гарантированно приведет к сбою. Однако это компенсируется тем фактом, что небольшой дополнительный код в каждом вызываемом методе сохранит код в тех местах, где вызывается метод. По этой причине в большинстве подпрограмм исходного набора инструментов Macintosh использовалось соглашение о вызовах Pascal.

Соглашение о вызовах C имеет то преимущество, что позволяет подпрограммам принимать переменное количество параметров и быть надежным, даже если подпрограмма не использует все переданные параметры (вызывающая сторона будет знать, сколько байтов было передано параметров, и таким образом можно будет их очистить). Кроме того, нет необходимости выполнять очистку стека после каждого вызова функции. Если процедура вызывает четыре функции последовательно, каждая из которых использует четыре байта параметров, она может - вместо использования ADD SP,4после каждого вызова использовать одну ADD SP,16после последнего вызова для очистки параметров от всех четырех вызовов.

В настоящее время описанные соглашения о вызовах считаются несколько устаревшими. Поскольку компиляторы стали более эффективными при использовании регистров, обычно методы принимают несколько параметров в регистрах вместо того, чтобы требовать, чтобы все параметры помещались в стек; если метод может использовать регистры для хранения всех параметров и локальных переменных, нет необходимости использовать указатель кадра и, следовательно, нет необходимости сохранять и восстанавливать старый. Тем не менее, иногда необходимо использовать старые соглашения о вызовах при вызове библиотек, которые были связаны для их использования.

Здесь уже есть действительно хорошие ответы. Однако, если вас по-прежнему беспокоит поведение стека LIFO, считайте его стеком кадров, а не стеком переменных. Я хочу сказать, что, хотя функция может обращаться к переменным, которые не находятся на вершине стека, она по-прежнему работает только с элементом наверху стека: одним кадром стека.

Конечно, из этого есть исключения. Локальные переменные всей цепочки вызовов по-прежнему выделены и доступны. Но к ним нельзя будет получить прямой доступ. Вместо этого они передаются по ссылке (или по указателю, который на самом деле отличается только семантически). В этом случае можно получить доступ к локальной переменной кадра стека, находящегося намного ниже. Но даже в этом случае текущая выполняемая функция по-прежнему работает только со своими собственными локальными данными. Он обращается к ссылке, хранящейся в его собственном кадре стека, который может быть ссылкой на что-то в куче, в статической памяти или далее по стеку.

Это часть абстракции стека, которая делает функции вызываемыми в любом порядке и допускает рекурсию. Фрейм верхнего стека - единственный объект, к которому код напрямую обращается. Ко всему остальному осуществляется доступ косвенно (через указатель, который находится в верхнем фрейме стека).

Было бы поучительно посмотреть на сборку вашей маленькой программы, особенно если вы компилируете без оптимизации. Я думаю, вы увидите, что весь доступ к памяти в вашей функции происходит через смещение от указателя фрейма стека, и именно так код функции будет записан компилятором. В случае передачи по ссылке вы увидите инструкции непрямого доступа к памяти через указатель, который хранится с некоторым смещением от указателя кадра стека.

Стек вызовов на самом деле не является структурой данных стека. За кулисами используемые нами компьютеры являются реализациями архитектуры машин с произвольным доступом. Таким образом, можно получить прямой доступ к a и b.

За кадром машина делает:

• get "a" равно чтению значения четвертого элемента ниже вершины стека.
• get "b" равно чтению значения третьего элемента ниже вершины стека.

http://en.wikipedia.org/wiki/Random-access_machine

Вот диаграмма, которую я создал для стека вызовов C. Это более точно и современно, чем версии изображений Google

И в соответствии с точной структурой диаграммы выше, вот отладка notepad.exe x64 на Windows 7.

Младшие адреса и старшие адреса меняются местами, поэтому стек на этой диаграмме поднимается вверх. Красный обозначает рамку точно так же, как на первой диаграмме (где использовались красный и черный, но теперь черный был изменен); черный - домашнее пространство; синий - это адрес возврата, который представляет собой смещение вызывающей функции к инструкции после вызова; оранжевый - это выравнивание, а розовый - то место, куда указывает указатель инструкции сразу после вызова и перед первой инструкцией. Значение homespace + return - это наименьший допустимый фрейм в окнах, и, поскольку 16-байтовое выравнивание rsp в самом начале вызываемой функции должно поддерживаться, это всегда также включает 8-байтовое выравнивание.BaseThreadInitThunk и так далее.

Красные фреймы функций обрисовывают, что вызываемая функция логически «владеет» + читает / изменяет (она может изменять переданный в стек параметр, который был слишком большим для передачи в регистр на -Ofast). Зеленые линии ограничивают пространство, которое функция выделяет себе от начала до конца функции.