Как работает callstack? - программирование
Подтвердить что ты не робот

Как работает callstack?

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

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

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, но это означало бы, что OS/CPU (?) Должен сначала выскочить 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.

4b9b3361

Ответ 1

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

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

Эта графика из Wikipedia показывает, что типичный стек вызовов структурирован как 1:

Picture of a stack

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

Пример

#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 2 и get вызывается; Возвращаемое значение находится в EAX.

Пока все хорошо. Теперь самое интересное:

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

Наконец,

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

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

Уклонение от указателя кадров

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

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


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

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

Ответ 2

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

Короче:

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

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

Подробнее:

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

enter image description here

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

enter image description here

Обратите внимание, что для доступа к аргументам тело функции должно будет проходить вниз (более высокие адреса) из места, где хранится адрес возврата, и для доступа к локальным переменным тело функции должно пройти (нижние адреса) относительно места, где хранится адрес возврата. Фактически, типичный код, сгенерированный компилятором для функции, будет делать именно это. Компилятор выделяет для этого регистр, называемый 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

Ссылки:

Ответ 3

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

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

Вот код:

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. отмечены в код и состояние памяти в это время показано на рисунке:

enter image description here

Ответ 4

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

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

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

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

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

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

Ответ 5

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

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

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

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

Ответ 6

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

За кулисами машина делает:

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

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