Jak dokładnie działa stos wywołań?

Staram się uzyskać głębsze zrozumienie tego, jak działają operacje niskiego poziomu języków programowania, a zwłaszcza jak współdziałają z systemem operacyjnym / procesorem. Prawdopodobnie przeczytałem każdą odpowiedź w każdym wątku związanym ze stosem / stertą w Stack Overflow i wszystkie są genialne. Ale jest jeszcze jedna rzecz, której jeszcze nie w pełni zrozumiałem.

Rozważ tę funkcję w pseudokodzie, który wydaje się być prawidłowym kodem Rusta ;-)

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

    // line X

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

Oto jak zakładam, że stos będzie wyglądał w linii X:

Stack

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

Teraz wszystko, co przeczytałem o tym, jak działa stos, to to, że ściśle przestrzega reguł LIFO (ostatni wchodzi, pierwszy wychodzi). Podobnie jak typ danych stosu w .NET, Javie lub dowolnym innym języku programowania.

Ale jeśli tak jest, to co dzieje się po linii X? Ponieważ oczywiście następną rzeczą, której potrzebujemy, jest praca z ai b, ale to oznaczałoby, że system operacyjny / procesor (?) Musi wyskoczyć di cnajpierw wrócić do aib . Ale wtedy strzelałby sobie w stopę, bo tego potrzebuje ciw dnastępnej linii.

Więc zastanawiam się co dokładnie dzieje się za kulisami?

Kolejne powiązane pytanie. Rozważ, że przekazujemy odniesienie do jednej z pozostałych funkcji, takich jak ta:

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

    // line X

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

Od jak rozumiem rzeczy, oznaczałoby to, że parametry doSomethingsą zasadniczo wskazując tym samym adresem pamięci jak ai bin foo. Ale z drugiej strony oznacza to, że stos nie wyskakuje, dopóki nie dojdziemy do tegoa ib dzieje.

Te dwa przypadki sprawiają, że myślę, że nie do końca zrozumiałem, jak dokładnie działa stos i jak ściśle przestrzega reguł LIFO .

Stos wywołań można również nazwać stosem ramek.
Rzeczy, które są układane w stos po zasadzie LIFO, nie są zmiennymi lokalnymi, ale całymi ramkami stosu („wywołaniami”) wywoływanych funkcji . Zmienne lokalne są wypychane i wstawiane razem z tymi klatkami w tak zwanym prologu funkcji i epilogu .

Wewnątrz ramki kolejność zmiennych jest zupełnie nieokreślona; Kompilatory odpowiednio „zmieniają kolejność” pozycji zmiennych lokalnych wewnątrz ramki, aby zoptymalizować ich wyrównanie, tak aby procesor mógł je pobrać tak szybko, jak to możliwe. Kluczowym faktem jest to, że przesunięcie zmiennych względem jakiegoś ustalonego adresu jest stałe przez cały okres życia ramki - więc wystarczy wziąć adres zakotwiczenia, powiedzmy, adres samej ramki i pracować z przesunięciami tego adresu do zmienne. Taki adres zakotwiczenia jest faktycznie zawarty w tak zwanym wskaźniku bazowym lub ramcektóry jest przechowywany w rejestrze EBP. Z drugiej strony przesunięcia są wyraźnie znane w czasie kompilacji i dlatego są na stałe zakodowane w kodzie maszynowym.

Ta grafika z Wikipedii pokazuje strukturę typowego stosu wywołań ¹ :

Dodaj przesunięcie zmiennej, do której chcemy uzyskać dostęp, do adresu zawartego we wskaźniku ramki i otrzymamy adres naszej zmiennej. Krótko mówiąc, kod po prostu uzyskuje do nich dostęp bezpośrednio poprzez stałe przesunięcia czasu kompilacji od wskaźnika podstawowego; To prosta arytmetyka wskaźników.

Przykład

#include <iostream>

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

gcc.godbolt.org daje nam

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

.. dla main. Kod podzieliłem na trzy podrozdziały. Prolog funkcji składa się z pierwszych trzech operacji:

• Podstawowy wskaźnik jest umieszczany na stosie.
• Wskaźnik stosu jest zapisywany we wskaźniku podstawowym
• Wskaźnik stosu jest odejmowany, aby zrobić miejsce na zmienne lokalne.

Następnie cinjest przenoszony do rejestru EDI ² iget wywoływany; Wartość zwracana jest w EAX.

Na razie w porządku. Teraz dzieje się interesująca rzecz:

Najniższy bajt EAX, oznaczony przez 8-bitowy rejestr AL, jest pobierany i zapisywany w bajcie tuż za wskaźnikiem podstawowym : to znaczy -1(%rbp), przesunięcie wskaźnika podstawowego wynosi -1. Ten bajt jest naszą zmiennąc . Przesunięcie jest ujemne, ponieważ stos rośnie w dół na x86. Następna operacja jest przechowywana cw EAX: EAX jest przenoszony do ESI, coutprzenoszony do EDI, a następnie wywoływany jest operator wstawiania z argumentami couti cbędący argumentami.

Wreszcie,

• Zwracana wartość mainjest przechowywana w EAX: 0. Wynika to z niejawnej returninstrukcji. Możesz także zobaczyć xorl rax raxzamiast movl.
• wyjdź i wróć do strony wezwania. leaveskraca ten epilog i niejawnie
  • Zastępuje wskaźnik stosu wskaźnikiem podstawowym i
  • Zdejmuje wskaźnik bazowy.

Po wykonaniu tej operacji i retwykonaniu tej operacji ramka została skutecznie usunięta, chociaż wywołujący nadal musi wyczyścić argumenty, ponieważ używamy konwencji wywoływania cdecl. Inne konwencje, np. Stdcall, wymagają od wywoływanego uporządkowania, np. Poprzez przekazanie ilości bajtów do ret.

Pominięcie wskaźnika ramki

Można również nie używać przesunięć ze wskaźnika podstawy / ramki, ale zamiast tego ze wskaźnika stosu (ESB). To sprawia, że ​​rejestr EBP, który w przeciwnym razie zawierałby wartość wskaźnika ramki, jest dostępny do dowolnego użytku - ale może uniemożliwić debugowanie na niektórych maszynach i zostanie domyślnie wyłączony dla niektórych funkcji . Jest to szczególnie przydatne podczas kompilacji dla procesorów z tylko kilkoma rejestrami, w tym x86.

Ta optymalizacja jest znana jako FPO (pominięcie wskaźnika ramki) i jest ustawiana przez -fomit-frame-pointerGCC i -OyClang; zwróć uwagę, że jest on niejawnie wyzwalany przez każdy poziom optymalizacji> 0 wtedy i tylko wtedy, gdy debugowanie jest nadal możliwe, ponieważ nie ma żadnych dodatkowych kosztów. Więcej informacji można znaleźć tutaj i tutaj .

¹ Jak wskazano w komentarzach, wskaźnik ramki przypuszczalnie ma wskazywać na adres za adresem zwrotnym.

² Zauważ, że rejestry zaczynające się od R są 64-bitowymi odpowiednikami tych, które zaczynają się od E. EAX wyznacza cztery bajty RAX o najniższej kolejności. Dla jasności użyłem nazw rejestrów 32-bitowych.

Ponieważ oczywiście następną rzeczą, której potrzebujemy, jest praca z a i b, ale oznaczałoby to, że system operacyjny / procesor (?) Musi najpierw wyskoczyć d i c, aby wrócić do aib. Ale wtedy strzeliłby sobie w stopę, ponieważ potrzebuje cid w następnej linii.

W skrócie:

Nie ma potrzeby przerywania argumentów. Argumenty przekazane przez obiekt wywołujący foodo funkcji doSomethingi zmienne lokalne w doSomething mogą być przywoływane jako przesunięcie względem wskaźnika podstawowego .
Więc,

• Kiedy wywoływana jest funkcja, jej argumenty są PUSHOWANE na stosie. Te argumenty są dalej przywoływane przez wskaźnik bazowy.
• Kiedy funkcja powraca do swojego wywołującego, argumenty funkcji zwracającej są wyrzucane ze stosu przy użyciu metody LIFO.

Szczegółowo:

Zasada jest taka, że każde wywołanie funkcji powoduje utworzenie ramki stosu (minimum to adres do powrotu). Tak więc, jeśli funcAwywołania funcBi funcBwywołania funcC, ustawiane są trzy ramki stosu jedna na drugiej. Kiedy funkcja zwraca, jej ramka staje się nieprawidłowa . Dobrze działająca funkcja działa tylko na własnej ramce stosu i nie narusza innej ramki. Innymi słowy, POPing jest wykonywany do ramki stosu na górze (przy powrocie z funkcji).

Stos w Twoim pytaniu jest konfigurowany przez dzwoniącego foo. Kiedy doSomethingi doAnotherThingzostaną sprawdzeni, ustawiają swój własny stos. Rysunek może pomóc ci to zrozumieć:

Zwróć uwagę, że aby uzyskać dostęp do argumentów, treść funkcji będzie musiała przejść w dół (wyższe adresy) od lokalizacji, w której przechowywany jest adres zwrotny, a aby uzyskać dostęp do zmiennych lokalnych, treść funkcji będzie musiała przejść w górę stosu (niższe adresy ) względem lokalizacji, w której przechowywany jest adres zwrotny. W rzeczywistości typowy kod funkcji wygenerowany przez kompilator będzie dokładnie to robił. Kompilator dedykuje do tego rejestr o nazwie EBP (wskaźnik podstawowy). Inną nazwą tego samego jest wskaźnik ramki. Kompilator zazwyczaj, jako pierwsza rzecz dla treści funkcji, wypycha bieżącą wartość EBP na stos i ustawia EBP na bieżącą ESP. Oznacza to, że po wykonaniu tej czynności w dowolnej części kodu funkcji argument 1 to EBP + 8 dalej (4 bajty na każdy EBP dzwoniącego i adres zwrotny), argument 2 to EBP + 12 (dziesiętnie) dalej, zmienne lokalne są EBP-4n daleko.

.
.
.
[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) 

Spójrz na poniższy kod w C służący do tworzenia ramki stosu funkcji:

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

Kiedy dzwoniący dzwoni

MyFunction(10, 5, 2);  

zostanie wygenerowany następujący kod

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

a kod asemblera funkcji będzie (ustawiony przez wywoływanego przed powrotem)

^
| _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
 

Bibliografia:

• Konwencje wywołań funkcji i stos .
• Wskaźnik ramki i zmienne lokalne .
• Demontaż / funkcje x86 i ramki stosu .

Jak zauważyli inni, nie ma potrzeby zdejmowania parametrów, dopóki nie wyjdą poza zakres.

Wkleję przykład z „Pointers and Memory” Nicka Parlante. Myślę, że sytuacja jest nieco prostsza, niż sobie wyobrażałeś.

Oto kod:

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)
}

Punkty w czasie T1, T2, etc. są zaznaczone w kodzie, a stan pamięci w tamtym czasie przedstawia rysunek:

Różne procesory i języki używają kilku różnych projektów stosów. Dwa tradycyjne wzorce w 8x86 i 68000 nazywane są konwencją wywoływania Pascala i konwencją wywoływania C; każda konwencja jest obsługiwana w ten sam sposób w obu procesorach, z wyjątkiem nazw rejestrów. Każdy używa dwóch rejestrów do zarządzania stosem i powiązanymi zmiennymi, zwanymi wskaźnikiem stosu (SP lub A7) i wskaźnikiem ramki (BP lub A6).

Podczas wywoływania podprogramu przy użyciu którejkolwiek z konwencji wszelkie parametry są umieszczane na stosie przed wywołaniem procedury. Następnie kod procedury wypycha bieżącą wartość wskaźnika ramki na stos, kopiuje bieżącą wartość wskaźnika stosu do wskaźnika ramki i odejmuje od wskaźnika stosu liczbę bajtów używanych przez zmienne lokalne [jeśli istnieją]. Gdy to zrobisz, nawet jeśli dodatkowe dane zostaną umieszczone na stosie, wszystkie zmienne lokalne będą przechowywane jako zmienne ze stałym ujemnym przesunięciem ze wskaźnika stosu, a wszystkie parametry, które zostały umieszczone na stosie przez wywołującego, będą dostępne w stałe dodatnie przesunięcie od wskaźnika ramki.

Różnica między tymi dwiema konwencjami polega na sposobie, w jaki obsługują one wyjście z podprogramu. W konwencji C funkcja zwracająca kopiuje wskaźnik ramki do wskaźnika stosu [przywracając go do wartości, którą miał tuż po przesunięciu wskaźnika starej ramki], zdejmuje wartość wskaźnika starej ramki i zwraca wartość. Wszelkie parametry, które wywołujący umieścił na stosie przed wywołaniem, pozostaną tam. W konwencji Pascala, po zdejmowaniu wskaźnika starej ramki, procesor pobiera adres powrotu funkcji, dodaje do wskaźnika stosu liczbę bajtów parametrów przekazanych przez wywołującego, a następnie przechodzi do pobranego adresu zwrotnego. W oryginalnym 68000 konieczne było użycie sekwencji 3 instrukcji, aby usunąć parametry wywołującego; procesory 8x86 i wszystkie 680x0 po oryginale zawierały „ret N”

Konwencja Pascala ma tę zaletę, że zachowuje trochę kodu po stronie wywołującego, ponieważ wywołujący nie musi aktualizować wskaźnika stosu po wywołaniu funkcji. Wymaga jednak, aby wywoływana funkcja dokładnie wiedziała, ile bajtów wartości parametrów ma zostać umieszczony przez wywołującego na stosie. Niewypełnienie odpowiedniej liczby parametrów na stos przed wywołaniem funkcji używającej konwencji Pascala jest prawie gwarantowane, że spowoduje awarię. Jest to jednak równoważone faktem, że niewielki dodatkowy kod w każdej wywołanej metodzie zapisze kod w miejscach, w których metoda jest wywoływana. Z tego powodu większość procedur z oryginalnego zestawu narzędzi Macintosha korzystała z konwencji wywoływania Pascal.

Konwencja wywoływania języka C ma tę zaletę, że pozwala procedurom akceptować zmienną liczbę parametrów i jest niezawodna, nawet jeśli procedura nie używa wszystkich przekazanych parametrów (wywołujący będzie wiedział, ile bajtów wartości parametrów wypchnęła i dzięki temu będzie mógł je wyczyścić). Ponadto nie jest konieczne czyszczenie stosu po każdym wywołaniu funkcji. Jeśli procedura wywołuje kolejno cztery funkcje, z których każda wykorzystywała cztery bajty parametrów, może - zamiast używać ADD SP,4po każdym wywołaniu, użyć jednej ADD SP,16po ostatnim wywołaniu, aby oczyścić parametry ze wszystkich czterech wywołań.

Obecnie opisane konwencje wywoływania uważane są za nieco przestarzałe. Ponieważ kompilatory stały się bardziej wydajne w korzystaniu z rejestrów, często metody akceptują kilka parametrów w rejestrach, zamiast wymagać umieszczenia wszystkich parametrów na stosie; jeśli metoda może używać rejestrów do przechowywania wszystkich parametrów i zmiennych lokalnych, nie ma potrzeby używania wskaźnika ramki, a zatem nie ma potrzeby zapisywania i przywracania starego. Mimo to czasami konieczne jest użycie starszych konwencji wywoływania podczas wywoływania bibliotek, które zostały połączone, aby ich używać.

Są już tutaj naprawdę dobre odpowiedzi. Jeśli jednak nadal martwisz się zachowaniem stosu LIFO, potraktuj go jako stos ramek, a nie stos zmiennych. Chcę zasugerować, że chociaż funkcja może uzyskiwać dostęp do zmiennych, które nie znajdują się na szczycie stosu, nadal działa tylko na elemencie na szczycie stosu: pojedynczej ramce stosu.

Oczywiście są od tego wyjątki. Zmienne lokalne całego łańcucha połączeń są nadal przydzielane i dostępne. Ale nie będą dostępne bezpośrednio. Zamiast tego są przekazywane przez odniesienie (lub przez wskaźnik, który w rzeczywistości różni się tylko semantycznie). W tym przypadku można uzyskać dostęp do zmiennej lokalnej ramki stosu znajdującej się znacznie niżej. Ale nawet w tym przypadku aktualnie wykonywana funkcja nadal działa tylko na własnych danych lokalnych. Uzyskuje dostęp do odniesienia przechowywanego we własnej ramce stosu, które może być odniesieniem do czegoś na stercie, w pamięci statycznej lub dalej w stosie.

Jest to część abstrakcji stosu, która umożliwia wywoływanie funkcji w dowolnej kolejności i umożliwia rekursję. Górna ramka stosu jest jedynym obiektem, do którego kod ma bezpośredni dostęp. Cokolwiek innego jest dostępne pośrednio (przez wskaźnik znajdujący się w górnej ramce stosu).

Pouczające może być przyjrzenie się montażowi twojego małego programu, szczególnie jeśli kompilujesz bez optymalizacji. Myślę, że zobaczysz, że cały dostęp do pamięci w twojej funkcji odbywa się poprzez przesunięcie wskaźnika ramki stosu, czyli sposób, w jaki kod funkcji zostanie zapisany przez kompilator. W przypadku przejścia przez odniesienie, zobaczysz instrukcje pośredniego dostępu do pamięci przez wskaźnik, który jest przechowywany z pewnym przesunięciem od wskaźnika ramki stosu.

Stos wywołań nie jest w rzeczywistości strukturą danych stosu. Za kulisami używane przez nas komputery to implementacje architektury maszyn o dostępie swobodnym. Zatem a i b mogą być dostępne bezpośrednio.

Za kulisami maszyna:

• get "a" oznacza odczytanie wartości czwartego elementu poniżej szczytu stosu.
• get "b" oznacza odczytanie wartości trzeciego elementu poniżej szczytu stosu.

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

Oto diagram, który utworzyłem dla stosu wywołań C. Jest dokładniejszy i bardziej nowoczesny niż wersje obrazów Google

Zgodnie z dokładną strukturą powyższego diagramu, tutaj jest debugowanie programu notepad.exe x64 w systemie Windows 7.

Niskie adresy i wysokie adresy są zamieniane, więc stos rośnie w górę na tym diagramie. Kolor czerwony oznacza ramkę dokładnie tak, jak na pierwszym schemacie (który używał czerwonego i czarnego, ale czarny został teraz zmieniony); czarny to przestrzeń domowa; niebieski to adres zwrotny, który jest przesunięciem funkcji wywołującej do instrukcji po wywołaniu; Pomarańczowy to wyrównanie, a różowy to miejsce, w którym wskaźnik instrukcji wskazuje zaraz po wywołaniu i przed pierwszą instrukcją. Przestrzeń główna + zwracana wartość to najmniejsza dozwolona ramka w oknach, a ponieważ 16-bajtowe wyrównanie rsp na początku wywoływanej funkcji musi być zachowane, zawsze obejmuje to również wyrównanie do 8 bajtów.BaseThreadInitThunk i tak dalej.

Czerwone ramki funkcji określają, co funkcja wywoływana logicznie „posiada” + odczytuje / modyfikuje (może modyfikować parametr przekazywany na stosie, który był zbyt duży, aby można go było przekazać w rejestrze przy opcji -Ofast). Zielone linie wyznaczają przestrzeń, którą funkcja sama przydziela od początku do końca funkcji.