Jak działa stos w języku asemblera?

Obecnie próbuję zrozumieć, jak działa stos, więc postanowiłem nauczyć się języka asemblera , używam tej książki:

http://savannah.nongnu.org/projects/pgubook/

Używam Gas i tworzę program na Linux Mint .

Jestem trochę zdezorientowany:

O ile wiedziałem, stos to po prostu struktura danych. Więc założyłem, że jeśli będę kodował w asemblerze, będę musiał sam zaimplementować stos. Jednak wydaje się, że tak nie jest, ponieważ istnieją takie polecenia

pushl
popl

Zatem podczas kodowania w asemblerze dla architektury x86 i przy użyciu składni Gas: czy stos jest tylko strukturą danych, która jest już zaimplementowana? A może faktycznie jest zaimplementowany na poziomie sprzętu? A może to coś innego? Czy też większość języków asemblera dla innych zestawów układów miałaby już zaimplementowany stos?

Wiem, że to trochę głupie pytanie, ale tak naprawdę jestem tym zdezorientowany.

Myślę, że przede wszystkim mylisz się między a program's stacka any old stack.

Stos

To abstrakcyjna struktura danych, która składa się z informacji w systemie Last In First Out. Umieszczasz dowolne przedmioty na stosie, a następnie zdejmujesz je ponownie, podobnie jak taca wejściowa / wyjściowa, górny przedmiot jest zawsze zdejmowany i zawsze kładziesz go na wierzchu.

Stos programów

Jest to stos, to sekcja pamięci, która jest używana podczas wykonywania, zwykle ma statyczny rozmiar na program i często jest używana do przechowywania parametrów funkcji. Parametry umieszczasz na stosie, gdy wywołujesz funkcję, a funkcja albo bezpośrednio adresuje stos, albo zdejmuje zmienne ze stosu.

Stos programów nie jest generalnie sprzętem (chociaż jest przechowywany w pamięci, więc można go argumentować), ale wskaźnik stosu, który wskazuje na bieżący obszar stosu, jest na ogół rejestrem procesora. To sprawia, że ​​jest nieco bardziej elastyczny niż stos LIFO, ponieważ można zmienić punkt, w którym stos jest adresowany.

Powinieneś przeczytać i upewnić się, że rozumiesz artykuł na Wikipedii, ponieważ zawiera dobry opis stosu sprzętu, z którym masz do czynienia.

Istnieje również ten samouczek, który wyjaśnia stos w kontekście starych 16-bitowych rejestrów, ale może być pomocny, oraz inny, dotyczący stosu.

Od Nilsa Pipenbrincka:

Warto zauważyć, że niektóre procesory nie implementują wszystkich instrukcji dostępu i manipulowania stosem (push, pop, wskaźnik stosu itp.), Ale x86 robi to ze względu na częstotliwość używania. W takich sytuacjach, jeśli chciałbyś mieć stos, musiałbyś go zaimplementować samodzielnie (niektóre MIPS i niektóre procesory ARM są tworzone bez stosów).

Na przykład w MIPach instrukcja push byłaby zaimplementowana w następujący sposób:

addi $sp, $sp, -4  # Decrement stack pointer by 4  
sw   $t0, ($sp)   # Save $t0 to stack  

a instrukcja Pop wyglądałaby następująco:

lw   $t0, ($sp)   # Copy from stack to $t0  
addi $sp, $sp, 4   # Increment stack pointer by 4  

(Zrobiłem podsumowanie całego kodu w tej odpowiedzi na wypadek, gdybyś chciał się nim bawić)

Podczas mojego kursu CS101 w 2003 roku robiłem tylko najbardziej podstawowe rzeczy w asm. I nigdy tak naprawdę nie rozumiałem, jak działają asm i stos, dopóki nie zdałem sobie sprawy, że wszystko to w zasadzie przypomina programowanie w C lub C ++ ... ale bez lokalnych zmiennych, parametrów i funkcji. Prawdopodobnie nie brzmi to jeszcze łatwo :) Pozwól, że ci pokażę (dla asm x86 ze składnią Intela ).

1. Co to jest stos

Stos to zwykle ciągły fragment pamięci przydzielony dla każdego wątku przed ich uruchomieniem. Możesz tam przechowywać co tylko zechcesz. W terminach C ++ ( fragment kodu 1 ):

const int STACK_CAPACITY = 1000;
thread_local int stack[STACK_CAPACITY];

2. Góra i dół stosu

W zasadzie możesz przechowywać wartości w losowych komórkach stacktablicy ( fragment # 2.1 ):

stack[333] = 123;
stack[517] = 456;
stack[555] = stack[333] + stack[517];

Ale wyobraź sobie, jak trudno byłoby zapamiętać, które komórki stacksą już w użyciu, a które są „wolne”. Dlatego przechowujemy nowe wartości na stosie obok siebie.

Jedną dziwną rzeczą związaną ze stosem (x86) asm jest to, że dodajesz tam rzeczy zaczynając od ostatniego indeksu i przechodzisz do niższych indeksów: stos [999], następnie stos [998] i tak dalej ( fragment # 2.2 ):

stack[999] = 123;
stack[998] = 456;
stack[997] = stack[999] + stack[998];

I nadal (uwaga, teraz będziesz zdezorientowany) „oficjalna” nazwa stack[999]znajduje się na dole stosu .
Ostatnia używana komórka ( stack[997]w powyższym przykładzie) jest nazywana szczytem stosu (zobacz Gdzie wierzchołek stosu znajduje się na x86 ).

3. Wskaźnik stosu (SP)

Na potrzeby tego omówienia załóżmy, że rejestry procesora są reprezentowane jako zmienne globalne (patrz Rejestry ogólnego przeznaczenia ).

int AX, BX, SP, BP, ...;
int main(){...}

Istnieje specjalny rejestr procesora (SP), który śledzi szczyt stosu. SP jest wskaźnikiem (przechowuje adres pamięci, taki jak 0xAAAABBCC). Ale na potrzeby tego postu użyję go jako indeksu tablicy (0, 1, 2, ...).

Po uruchomieniu wątku SP == STACK_CAPACITYprogram i system operacyjny modyfikują go w razie potrzeby. Zasada jest taka, że ​​nie można zapisywać na stosie komórek poza wierzchołkiem stosu, a każdy indeks mniejszy niż SP jest nieprawidłowy i niebezpieczny (z powodu przerwań systemowych ), więc najpierw zmniejszamy SP, a następnie zapisujemy wartość do nowo przydzielonej komórki.

Jeśli chcesz umieścić kilka wartości na stosie w rzędzie, możesz zarezerwować miejsce na wszystkie z nich z góry ( fragment 3 ):

SP -= 3;
stack[999] = 12;
stack[998] = 34;
stack[997] = stack[999] + stack[998];

Uwaga. Teraz możesz zobaczyć, dlaczego alokacja na stosie jest tak szybka - to tylko jeden dekrement rejestru.

4. Zmienne lokalne

Przyjrzyjmy się tej uproszczonej funkcji ( fragment nr 4.1 ):

int triple(int a) {
    int result = a * 3;
    return result;
}

i przepisz go bez użycia zmiennej lokalnej ( fragment # 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];
}

i zobacz, jak to się nazywa ( fragment # 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

Dodanie nowego elementu na szczycie stosu jest tak częsta operacja, że procesory mają specjalną dyspozycję, że push. Zaimplementujemy to w ten sposób ( fragment 5.1 ):

void push(int value) {
    --SP;
    stack[SP] = value;
}

Podobnie, biorąc górny element stosu ( fragment 5.2 ):

void pop(int& result) {
    result = stack[SP];
    ++SP; // note that `pop` decreases stack's size
}

Typowy wzorzec użycia push / pop tymczasowo oszczędza pewną wartość. Powiedzmy, że mamy coś pożytecznego w zmiennej myVariz jakiegoś powodu musimy wykonać obliczenia, które ją nadpiszą ( fragment 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. Parametry funkcji

Teraz przekażmy parametry za pomocą stosu ( fragment # 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. returnoświadczenie

Zwróćmy wartość w rejestrze AX ( fragment nr 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. Wskaźnik podstawy stosu (BP) (znany również jako wskaźnik ramki ) i ramka stosu

Weźmy bardziej „zaawansowaną” funkcję i przepiszmy ją w naszym C ++ podobnym do asm ( fragment # 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);
}

Teraz wyobraź sobie, że zdecydowaliśmy się wprowadzić nową zmienną lokalną, aby przechowywać tam wynik przed zwróceniem, tak jak robimy to w tripple(snippet # 4.1). Treść funkcji będzie wyglądać następująco ( fragment # 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;

Widzisz, musieliśmy zaktualizować każde odwołanie do parametrów funkcji i zmiennych lokalnych. Aby tego uniknąć, potrzebujemy indeksu kotwicy, który nie zmienia się, gdy stos rośnie.

Utworzymy kotwicę zaraz po wejściu do funkcji (zanim przydzielimy miejsce dla lokalnych), zapisując bieżącą górę (wartość SP) do rejestru BP. Fragment nr 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
}

Kawałek stosu, który należy do funkcji i ma pełną kontrolę nad nią, nazywany jest ramką stosu funkcji . Np. myAlgo_noLPR_withAnchorRamka stosu to stack[996 .. 994](obie idexy włącznie).
Ramka zaczyna się od BP funkcji (po zaktualizowaniu jej wewnątrz funkcji) i trwa do następnej ramki stosu. Zatem parametry na stosie są częścią ramki stosu wywołującego (patrz uwaga 8a).

Uwagi:
8a. Wikipedia mówi inaczej o parametrach, ale tutaj trzymam się instrukcji programisty Intela , patrz t. 1, część 6.2.4.1 Wskaźnik podstawy stosu ramki i rysunek 6-2 w sekcji 6.3.2 Dalsza operacja wywołania i RET . Parametry funkcji i ramka stosu są częścią rekordu aktywacji funkcji (zobacz Generowanie dziennika funkcji ).
8b. dodatnie przesunięcia od punktu BP do parametrów funkcji, a ujemne przesunięcia wskazują na zmienne lokalne. Jest to bardzo przydatne do debugowania
8c. stack[BP]przechowuje adres poprzedniej ramki stosu,stack[stack[BP]]przechowuje poprzednią ramkę stosu i tak dalej. Podążając za tym łańcuchem, możesz odkryć ramki wszystkich funkcji w programie, które jeszcze nie wróciły. W ten sposób debugery pokazują wywołanie stosu
8d. pierwsze 3 instrukcje myAlgo_noLPR_withAnchor, w których ustawiamy ramkę (zapisz stary BP, zaktualizuj BP, zarezerwuj miejsce dla lokalnych), nazywają się prologiem funkcji

9. Konwencje przywoławcze

We fragmencie 8.1 przesunęliśmy parametry myAlgood prawej do lewej i zwróciliśmy wynik w postaci AX. Równie dobrze moglibyśmy przekazać parametry od lewej do prawej i wrócić BX. Lub przekaż parametry w BX i CX i wróć w AX. Oczywiście caller ( main()) i wywoływana funkcja muszą zgadzać się gdzie i w jakiej kolejności wszystkie te rzeczy są przechowywane.

Konwencja wywoływania to zestaw reguł dotyczących przekazywania parametrów i zwracania wyniku.

W powyższym kodzie użyliśmy konwencji wywoływania cdecl :

• Parametry są przekazywane na stosie, przy czym pierwszy argument znajduje się na najniższym adresie stosu w momencie wywołania (odłożony ostatni <...>). Obiekt wywołujący jest odpowiedzialny za zdejmowanie parametrów ze stosu po wywołaniu.
• zwracana wartość jest umieszczana w AX
• EBP i ESP muszą być zachowane przez wywoływanego ( myAlgo_noLPR_withAnchorfunkcję w naszym przypadku), tak aby wywołujący ( mainfunkcja) mógł polegać na tych rejestrach, które nie zostały zmienione przez wywołanie.
• Wszystkie inne rejestry (EAX, <...>) mogą być dowolnie modyfikowane przez odbiorcę; jeśli wywołujący chce zachować wartość przed i po wywołaniu funkcji, musi zapisać wartość w innym miejscu (robimy to z AX)

^{(Źródło: przykład „32-bit cdecl” ze Stack Overflow Documentation; prawa autorskie 2016 icktoofay i Peter Cordes ; licencja na licencji CC BY-SA 3.0. Archiwum pełnej zawartości dokumentacji Stack Overflow można znaleźć na archive.org, w której ten przykład jest indeksowany według ID tematu 3261 i ID przykładu 11196).}

10. Wywołania funkcji

Teraz najciekawsza część. Podobnie jak dane, kod wykonywalny jest również przechowywany w pamięci (całkowicie niezwiązany z pamięcią stosu), a każda instrukcja ma adres.
Jeśli nie wydano innego polecenia, CPU wykonuje instrukcje jedna po drugiej, w kolejności, w jakiej są one przechowywane w pamięci. Ale możemy nakazać procesorowi „przeskoczyć” do innego miejsca w pamięci i wykonać instrukcje z tego miejsca. W asm może to być dowolny adres, aw bardziej zaawansowanych językach, takich jak C ++, można przeskakiwać tylko do adresów oznaczonych etykietami ( istnieją obejścia, ale nie są one co najmniej ładne).

Weźmy tę funkcję ( fragment nr 10.1 ):

int myAlgo_withCalls(int a, int b) {
    int t1 = triple(a);
    int t2 = triple(b);
    return t1 - t2;
}

Zamiast wywoływać trippleC ++ w sposób, wykonaj następujące czynności:

1. skopiuj tripplekod na początek myAlgotreści
2. przy myAlgowejściu przeskocz tripplekod za pomocągoto
3. kiedy musimy wykonać tripplekod, zapisz na stosie adres linii kodu zaraz po tripplewywołaniu, abyśmy mogli wrócić tutaj później i kontynuować wykonywanie ( PUSH_ADDRESSmakro poniżej)
4. przeskocz na adres pierwszej linii ( tripplefunkcji) i wykonaj go do końca (3. i 4. razem to CALLmakro)
5. na końcu tripple(po wyczyszczeniu lokalnych), weź adres zwrotny z góry stosu i wskocz tam ( RETmakro)

Ponieważ w C ++ nie ma łatwego sposobu, aby przejść do konkretnego adresu kodowego, będziemy używać etykiet do oznaczania miejsc skoków. Nie będę szczegółowo opisywać, jak działają poniższe makra, po prostu uwierz mi, że robią to, co mówię ( fragment # 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);
}

Uwagi:
10a. ponieważ adres zwrotny jest przechowywany na stosie, w zasadzie możemy go zmienić. Tak działa atak niszczący stosy
10b. ostatnie 3 instrukcje na „końcu” triple_label(czyszczenie miejscowych, przywracanie starego BP, powrót) nazywane są epilogiem funkcji

11. Montaż

Teraz spójrzmy na prawdziwy asm dla myAlgo_withCalls. Aby to zrobić w programie Visual Studio:

• ustaw platformę kompilacji na x86 ( nie x86_64)
• typ kompilacji: Debug
• ustaw punkt przerwania gdzieś w myAlgo_withCalls
• uruchom, a gdy wykonanie zatrzyma się w punkcie przerwania, naciśnij Ctrl + Alt + D

Jedyną różnicą w porównaniu z naszym C ++ podobnym do asm jest to, że stos asm działa na bajtach zamiast na liczbach int. Aby zarezerwować miejsce na jeden int, SP zostanie zmniejszone o 4 bajty.
Zaczynamy ( fragment nr 11.1 , numery wierszy w komentarzach pochodzą z sedna ):

;   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  

A asm dla tripple( fragment # 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  

Mam nadzieję, że po przeczytaniu tego posta montaż nie wygląda tak tajemniczo jak wcześniej :)

Oto linki z treści posta i dalsze lektury:

• Eli Bendersky , gdzie szczyt stosu jest na x86 - góra / dół, push / pop, SP, ramka stosu, konwencje wywoływania
• Eli Bendersky , Układ ramki stosu na x86-64 - argumenty przekazywane na x64, ramka stosu, czerwona strefa
• University of Mariland, Understanding the Stack - naprawdę dobrze napisane wprowadzenie do koncepcji stosu. (Dotyczy MIPS (nie x86) i składni GAS, ale nie ma to znaczenia dla tematu). Jeśli jesteś zainteresowany, zobacz inne uwagi na temat programowania MIPS ISA .
• x86 Asm wikibook, Rejestry ogólnego przeznaczenia
• x86 Demontaż wikibook, The Stack
• x86 Demontaż wikibook, Funkcje i ramki stosu
• Podręczniki programisty Intela - spodziewałem się, że będzie naprawdę hardkorowe, ale, co zaskakujące, jest dość łatwe do przeczytania (choć ilość informacji jest przytłaczająca)
• Jonathan de Boyne Pollard, Perilogues gen na temat funkcji - prolog / epilog, ramka stosu / rekord aktywacji, czerwona strefa

Jeśli chodzi o to, czy stos jest zaimplementowany w sprzęcie, może pomóc ten artykuł w Wikipedii .

Niektóre rodziny procesorów, takie jak x86, mają specjalne instrukcje dotyczące manipulowania stosem aktualnie wykonywanego wątku. Inne rodziny procesorów, w tym PowerPC i MIPS, nie mają wyraźnej obsługi stosu, ale zamiast tego opierają się na konwencji i delegują zarządzanie stosem do interfejsu binarnego aplikacji (ABI) systemu operacyjnego.

Ten artykuł i inne, do których prowadzi, mogą być przydatne do zrozumienia wykorzystania stosu w procesorach.

Koncepcja

Najpierw pomyśl o całej sprawie tak, jakbyś był osobą, która ją wymyśliła. Lubię to:

Najpierw pomyśl o tablicy i sposobie jej implementacji na niskim poziomie -> jest to po prostu zbiór sąsiadujących ze sobą lokalizacji pamięci (miejsc pamięci, które są obok siebie). Teraz, gdy masz ten mentalny obraz w swojej głowie, pomyśl o fakcie, że możesz uzyskać dostęp do DOWOLNEGO z tych miejsc pamięci i usunąć je według własnego uznania, gdy usuwasz lub dodasz dane do swojej tablicy. Pomyśl teraz o tej samej macierzy, ale zamiast możliwości usunięcia dowolnej lokalizacji zdecydujesz, że usuniesz tylko OSTATNĄ lokalizację, gdy usuniesz lub dodasz dane do swojej tablicy. Teraz twój nowy pomysł na manipulowanie danymi w tej tablicy w ten sposób nazywa się LIFO, co oznacza Last In First Out. Twój pomysł jest bardzo dobry, ponieważ ułatwia śledzenie zawartości tej tablicy bez konieczności używania algorytmu sortowania za każdym razem, gdy coś z niej usuwasz. Również, aby zawsze wiedzieć, jaki jest adres ostatniego obiektu w tablicy, przeznaczasz jeden rejestr w procesorze, aby go śledzić. Sposób, w jaki rejestr to śledzi, polega na tym, że za każdym razem, gdy usuwasz lub dodajesz coś do swojej tablicy, zmniejszasz lub zwiększasz wartość adresu w rejestrze o liczbę obiektów, które usunąłeś lub dodałeś z tablicy (o ilość zajmowanej przestrzeni adresowej). Chcesz również upewnić się, że wielkość, o którą zmniejszasz lub zwiększasz ten rejestr, jest ustalona na jedną wartość (np. 4 lokalizacje pamięci, tj. 4 bajty) na obiekt, ponownie, aby ułatwić śledzenie, a także umożliwić używać tego rejestru z niektórymi konstrukcjami pętli, ponieważ pętle używają stałego przyrostu na iterację (np. aby zapętlić tablicę za pomocą pętli, konstruujesz pętlę, aby zwiększyć swój rejestr o 4 w każdej iteracji, co nie byłoby możliwe, gdyby tablica zawierała obiekty o różnych rozmiarach). Na koniec wybierasz nazwanie tej nowej struktury danych „Stosem”, ponieważ przypomina ci ona stos talerzy w restauracji, gdzie zawsze usuwają lub dodają talerz na wierzchu tego stosu.

Implementacja

Jak widać, stos to nic innego jak tablica ciągłych lokalizacji pamięci, w których zdecydowałeś, jak nim manipulować. Z tego powodu widzisz, że nie musisz nawet używać specjalnych instrukcji i rejestrów do sterowania stosem. Możesz zaimplementować to samodzielnie za pomocą podstawowych instrukcji mov, add i sub oraz używając rejestrów ogólnego przeznaczenia zamiast ESP i EBP w następujący sposób:

mov edx, 0FFFFFFFFh

; -> to będzie adres początkowy twojego stosu, najdalej od twojego kodu i danych, posłuży również jako rejestr, który śledzi ostatni obiekt na stosie, który wyjaśniłem wcześniej. Nazywasz to „wskaźnikiem stosu”, więc wybierasz rejestr EDX, do którego zwykle używa się ESP.

sub edx, 4

mov [edx], dword ptr [someVar]

; -> te dwie instrukcje zmniejszą twój wskaźnik stosu o 4 lokalizacje pamięci i skopiują 4 bajty zaczynając od [someVar] lokalizacji pamięci do lokalizacji pamięci, na którą teraz wskazuje EDX, tak jak instrukcja PUSH zmniejsza ESP, tylko tutaj zrobiłeś to ręcznie i użyłeś EDX. Więc instrukcja PUSH jest po prostu krótszym kodem operacyjnym, który faktycznie robi to z ESP.

mov eax, dword ptr [edx]

dodaj edx, 4

; -> i tutaj robimy odwrotnie, najpierw kopiujemy 4 bajty zaczynając od lokalizacji pamięci, na którą wskazuje teraz EDX, do rejestru EAX (dowolnie wybrany tutaj, mogliśmy go skopiować gdziekolwiek chcieliśmy). Następnie zwiększamy nasz wskaźnik stosu EDX o 4 lokalizacje pamięci. To właśnie robi instrukcja POP.

Teraz możesz zobaczyć, że instrukcje PUSH i POP oraz rejestry ESP i EBP zostały właśnie dodane przez Intel, aby uczynić powyższą koncepcję struktury danych „stosu” łatwiejszą do zapisu i odczytu. Wciąż istnieje kilka procesorów RISC (zredukowany zestaw instrukcji), które nie mają instrukcji PUSH i POP oraz rejestrów dedykowanych do manipulacji stosem, a podczas pisania programów asemblerowych dla tych procesorów musisz sam zaimplementować stos, tak jak pokazałem ci.

Mylisz abstrakcyjny stos ze stosem zaimplementowanym sprzętowo. Ten ostatni jest już zaimplementowany.

Myślę, że główna odpowiedź, której szukasz, została już zasugerowana.

Podczas uruchamiania komputera x86 stos nie jest konfigurowany. Programista musi jawnie skonfigurować go podczas uruchamiania. Jeśli jednak korzystasz już z systemu operacyjnego, zostało to załatwione. Poniżej znajduje się przykładowy kod z prostego programu ładującego.

Najpierw ustawiane są rejestry danych i segmentów stosu, a następnie wskaźnik stosu jest ustawiany na 0x4000 poza to.

    movw    $BOOT_SEGMENT, %ax
    movw    %ax, %ds
    movw    %ax, %ss
    movw    $0x4000, %ax
    movw    %ax, %sp

Po tym kodzie można użyć stosu. Teraz jestem pewien, że można to zrobić na wiele różnych sposobów, ale myślę, że to powinno zilustrować ten pomysł.

Stos to tylko sposób, w jaki programy i funkcje wykorzystują pamięć.

Stos zawsze mnie mylił, więc zrobiłem ilustrację:

( tutaj wersja svg )

Stos już istnieje, więc możesz założyć, że pisząc swój kod. Stos zawiera adresy zwrotne funkcji, zmienne lokalne i zmienne przekazywane między funkcjami. Istnieją również wbudowane rejestry stosu, takie jak BP, SP (wskaźnik stosu), których możesz użyć, stąd wbudowane polecenia, o których wspomniałeś. Jeśli stos nie był jeszcze zaimplementowany, funkcje nie mogły działać, a przepływ kodu nie działał.

Stos jest „implementowany” za pomocą wskaźnika stosu, który (zakładając tutaj architekturę x86) wskazuje na segment stosu . Za każdym razem, gdy coś jest umieszczane na stosie (za pomocą pushl, wywołania lub podobnego kodu operacji stosu), jest zapisywane na adres, na który wskazuje wskaźnik stosu, a wskaźnik stosu jest zmniejszany (stos rośnie w dół , tj. Mniejsze adresy) . Kiedy zdejmujesz coś ze stosu (popl, ret), wskaźnik stosu jest zwiększany, a wartość odczytywana ze stosu.

W aplikacji w przestrzeni użytkownika stos jest już skonfigurowany podczas uruchamiania aplikacji. W środowisku przestrzeni jądra musisz najpierw ustawić segment stosu i wskaźnik stosu ...

Nie widziałem konkretnie asemblera Gas, ale ogólnie stos jest „implementowany” poprzez utrzymywanie odniesienia do lokalizacji w pamięci, w której znajduje się wierzchołek stosu. Lokalizacja pamięci jest przechowywana w rejestrze, który ma różne nazwy dla różnych architektur, ale może być traktowany jako rejestr wskaźnika stosu.

Polecenia pop i push są zaimplementowane w większości architektur w oparciu o mikro instrukcje. Jednak niektóre „Architektury Edukacyjne” wymagają samodzielnego ich wdrożenia. Funkcjonalnie wypychanie byłoby zaimplementowane mniej więcej w ten sposób:

   load the address in the stack pointer register to a gen. purpose register x
   store data y at the location x
   increment stack pointer register by size of y

Ponadto niektóre architektury przechowują ostatnio używany adres pamięci jako wskaźnik stosu. Niektóre przechowują następny dostępny adres.

Co to jest stos? Stos to rodzaj struktury danych - sposób przechowywania informacji w komputerze. Gdy nowy obiekt jest umieszczany w stosie, umieszczany jest na wierzchu wszystkich wcześniej wprowadzonych obiektów. Innymi słowy, struktura danych stosu jest podobna do stosu kart, papierów, korespondencji z kartami kredytowymi lub wszelkich innych obiektów ze świata rzeczywistego, o których możesz pomyśleć. Podczas usuwania obiektu ze stosu, ten na górze jest usuwany jako pierwszy. Ta metoda jest określana jako LIFO (ostatnie weszło, pierwsze wyszło).

Termin „stos” może również oznaczać stos protokołów sieciowych. W sieci połączenia między komputerami są realizowane poprzez serię mniejszych połączeń. Te połączenia lub warstwy zachowują się jak struktura danych stosu, ponieważ są budowane i usuwane w ten sam sposób.

Masz rację, że stos jest strukturą danych. Często struktury danych (w tym stosy), z którymi pracujesz, są abstrakcyjne i istnieją jako reprezentacja w pamięci.

Stos, z którym pracujesz w tym przypadku, ma bardziej materialne istnienie - mapuje bezpośrednio do rzeczywistych rejestrów fizycznych w procesorze. Jako struktura danych stosy są strukturami typu FILO (pierwszy wchodzi, ostatni wychodzi), które zapewniają usuwanie danych w kolejności odwrotnej do ich wprowadzenia. Zobacz logo StackOverflow, aby uzyskać wizualizację! ;)

Pracujesz ze stosem instrukcji . To jest stos rzeczywistych instrukcji podawanych do procesora.

Stos wywołań jest implementowany przez zestaw instrukcji x86 i system operacyjny.

Instrukcje, takie jak push i pop, dostosowują wskaźnik stosu, podczas gdy system operacyjny dba o alokację pamięci w miarę wzrostu stosu dla każdego wątku.

Fakt, że stos x86 „rośnie” z wyższych na niższe adresy, czyni tę architekturę bardziej podatną na atak przepełnienia bufora.

Masz rację, że stos to „tylko” struktura danych. Tutaj jednak odnosi się do stosu zaimplementowanego sprzętowo, używanego w specjalnym celu - „Stos”.

Wiele osób wypowiadało się na temat stosu zaimplementowanego sprzętowo w porównaniu ze strukturą danych stosu (programowego). Chciałbym dodać, że istnieją trzy główne typy struktury stosu -

1. Stos wywołań - o który pytasz! Przechowuje parametry funkcji, adres zwrotny itp. Przeczytaj rozdział 4 (wszystko o 4. stronie, tj. Str. 53) funkcji tej książki. Jest dobre wytłumaczenie.
2. Ogólny stos, którego możesz użyć w swoim programie, aby zrobić coś specjalnego ...
3. Ogólny stos sprzętowy
   Nie jestem tego pewien, ale pamiętam, że czytałem gdzieś, że w niektórych architekturach dostępny jest stos sprzętowy ogólnego przeznaczenia. Jeśli ktoś wie, czy to prawda, proszę o komentarz.

Pierwszą rzeczą, którą należy wiedzieć, jest architektura, dla której programujesz, którą wyjaśnia książka (właśnie ją sprawdziłem - link). Aby naprawdę zrozumieć rzeczy, sugeruję, abyś nauczył się pamięci, adresowania, rejestrów i architektury x86 (zakładam, że tego się uczysz - z książki).

Funkcje wywoływania, które wymagają zapisywania i przywracania stanu lokalnego w stylu LIFO (w przeciwieństwie do uogólnionego podejścia współrutynowego), okazują się tak niewiarygodnie powszechną potrzebą, że języki asemblera i architektury procesorów w zasadzie budują tę funkcjonalność. można by prawdopodobnie powiedzieć o pojęciach wątków, ochrony pamięci, poziomów bezpieczeństwa, itp. Teoretycznie możesz zaimplementować swój własny stos, konwencje wywołań itp., ale zakładam, że niektóre kody operacyjne i większość istniejących środowisk wykonawczych opiera się na tej natywnej koncepcji „stosu” .

stackjest częścią pamięci. używa dla inputi outputod functions. służy również do zapamiętywania powrotu funkcji.

esp register pamięta adres stosu.

stacki espsą wdrażane sprzętowo. również możesz to zaimplementować samodzielnie. spowolni to twój program.

przykład:

nop // esp= 0012ffc4

push 0 // esp= 0012ffc0, Dword [0012ffc0] = 00000000

zadzwoń proc01 // esp= 0012ffbc, Dword [0012ffbc] = eip, eip= adrr [proc01]

pop eax// eax= Dword [ esp], esp= esp+ 4

Szukałem tego, jak działa stos pod względem funkcji i stwierdziłem, że ten blog jest niesamowity i wyjaśnia od zera koncepcję stosu i jak stos przechowuje wartość w stosie.

Teraz twoja odpowiedź. Wyjaśnię za pomocą Pythona, ale dowiesz się, jak działa stos w dowolnym języku.

To jest program:

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(3)

Źródło: Cryptroix

niektóre z jego tematów, które porusza na blogu:

How Function work ?
Calling a Function
 Functions In a Stack
 What is Return Address
 Stack
Stack Frame
Call Stack
Frame Pointer (FP) or Base Pointer (BP)
Stack Pointer (SP)
Allocation stack and deallocation of stack
StackoverFlow
What is Heap?

Ale wyjaśnij to w języku Python, więc jeśli chcesz, możesz rzucić okiem.