W jaki sposób zmienne są przechowywane i pobierane ze stosu programu?

Z góry przepraszamy za naiwność tego pytania. Jestem 50-letnim artystą, który po raz pierwszy próbuje właściwie zrozumieć komputery. No i proszę.

Próbowałem zrozumieć, w jaki sposób typy danych i zmienne są obsługiwane przez kompilator (w bardzo ogólnym sensie wiem, że jest w tym wiele). Brakuje czegoś w moim rozumieniu związku między pamięcią w „stosie” i typami wartości, a pamięcią w „stercie” i typami referencyjnymi (cudzysłowy mają oznaczać, że rozumiem, że te terminy są abstrakcjami, a nie zbyt dosłownie w tak uproszczonym kontekście, jak sposób sformułowania tego pytania). W każdym razie, moim uproszczonym pomysłem jest to, że typy takie jak liczby logiczne i liczby całkowite przechodzą na „stos”, ponieważ mogą, ponieważ są znanymi jednostkami pod względem przestrzeni dyskowej, a ich zasięg jest odpowiednio kontrolowany.

Ale nie rozumiem, w jaki sposób zmienne na stosie są następnie odczytywane przez aplikację - jeśli deklaruję i przypisuję xjako liczbę całkowitą, powiedzmy x = 3, a pamięć jest zarezerwowana na stosie, a następnie 3jest przechowywana tam jego wartość , a następnie w tę samą funkcję, którą deklaruję i przypisuję yjako, powiedzmy 4, a następnie używam xw innym wyrażeniu (powiedzmy z = 5 + x) jak program może czytać x, aby ocenić, zkiedy jest poniżejyna stosie? Wyraźnie czegoś mi brakuje. Czy to dlatego, że położenie na stosie dotyczy tylko czasu życia / zakresu zmiennej i że cały stos jest faktycznie dostępny dla programu przez cały czas? Jeśli tak, to czy oznacza to, że istnieje jakiś inny indeks, który przechowuje tylko adresy zmiennych na stosie, aby umożliwić pobieranie wartości? Ale potem pomyślałem, że cały sens stosu polegał na tym, że wartości były przechowywane w tym samym miejscu co adres zmiennej? W moim kiepskim umyśle wydaje się, że jeśli istnieje ten inny indeks, to mówimy o czymś więcej jak kupie? Jestem wyraźnie zdezorientowany i mam tylko nadzieję, że istnieje prosta odpowiedź na moje uproszczone pytanie.

Dzięki za przeczytanie do tej pory.

Przechowywanie zmiennych lokalnych na stosie jest szczegółem implementacji - w zasadzie optymalizacją. Możesz myśleć o tym w ten sposób. Przy wprowadzaniu funkcji gdzieś przydzielane jest miejsce na wszystkie zmienne lokalne. Następnie możesz uzyskać dostęp do wszystkich zmiennych, ponieważ w jakiś sposób znasz ich lokalizację (jest to część procesu przydzielania). Po opuszczeniu funkcji spacja zostaje zwolniona (zwolniona).

Stos jest jednym ze sposobów implementacji tego procesu - można go traktować jako rodzaj „szybkiej sterty”, która ma ograniczony rozmiar i dlatego jest odpowiednia tylko dla małych zmiennych. Jako dodatkową optymalizację wszystkie zmienne lokalne są przechowywane w jednym bloku. Ponieważ każda zmienna lokalna ma znany rozmiar, znasz przesunięcie każdej zmiennej w bloku i w ten sposób uzyskujesz do niej dostęp. Kontrastuje to ze zmiennymi przydzielonymi na stercie, których adresy same są przechowywane w innych zmiennych.

Możesz myśleć o stosie jako bardzo podobnym do klasycznej struktury danych stosu, z jedną zasadniczą różnicą: możesz uzyskać dostęp do elementów poniżej górnej krawędzi stosu. Rzeczywiście, możesz uzyskać dostęp do tego przedmiotu od góry. W ten sposób możesz uzyskać dostęp do wszystkich lokalnych zmiennych za pomocą wypychania i poppingu. Jedyne popychanie jest wykonywane po wejściu do funkcji, a jedyne wyskakiwanie po wyjściu z funkcji.$k$

Na koniec chciałbym wspomnieć, że w praktyce niektóre zmienne lokalne są przechowywane w rejestrach. Wynika to z faktu, że dostęp do rejestrów jest szybszy niż dostęp do stosu. Jest to kolejny sposób implementacji przestrzeni dla zmiennych lokalnych. Po raz kolejny wiemy dokładnie, gdzie przechowywana jest zmienna (tym razem nie poprzez przesunięcie, ale poprzez nazwę rejestru), i ten rodzaj przechowywania jest odpowiedni tylko dla małych danych.

Posiadanie yna stosie fizycznie nie uniemożliwia xdostępu, co, jak wskazałeś, powoduje, że stosy komputerów różnią się od innych stosów.

Podczas kompilacji programu pozycje zmiennych na stosie są również z góry określone (w kontekście funkcji). W twoim przykładzie, jeśli stos zawiera xznak y„na górze”, to program z góry wie, że xbędzie 1 element poniżej stosu, gdy będzie wewnątrz funkcji. Ponieważ sprzęt komputerowy może jawnie poprosić o 1 element poniżej górnej części stosu, komputer może uzyskać, xmimo że yrównież istnieje.

Czy to dlatego, że położenie na stosie dotyczy tylko czasu życia / zakresu zmiennej i że cały stos jest faktycznie dostępny dla programu przez cały czas?

Tak. Po wyjściu z funkcji wskaźnik stosu przesuwa się z powrotem do poprzedniej pozycji, skutecznie usuwając xi y, ale technicznie nadal będzie tam, dopóki pamięć nie zostanie wykorzystana na coś innego. Dodatkowo, jeśli twoja funkcja wywołuje inną funkcję, xi ynadal tam będzie i można uzyskać do niej dostęp, celowo schodząc zbyt daleko w stosie.

Aby podać konkretny przykład sposobu, w jaki kompilator zarządza stosem i sposobu uzyskiwania dostępu do wartości na stosie, możemy spojrzeć na obrazy oraz kod wygenerowany przez GCCśrodowisko Linux z i386 jako architekturą docelową.

1. Układaj ramki

Jak wiadomo, stos jest lokalizacją w przestrzeni adresowej uruchomionego procesu, która jest używana przez funkcje lub procedury , w tym sensie, że przestrzeń jest przydzielana na stos dla zmiennych deklarowanych lokalnie, a także argumentów przekazywanych do funkcji ( miejsce na zmienne zadeklarowane poza jakąkolwiek funkcją (tj. zmienne globalne) jest przydzielone w innym regionie w pamięci wirtualnej). Miejsce przydzielone na wszystkie dane funkcji odnosi się do ramki stosu . Oto wizualne przedstawienie wielu ramek stosu (z Computer Systems: A Programmer's Perspective ):

2. Zarządzanie ramkami stosu i lokalizacja zmiennych

Aby wartości zapisane na stosie w ramach konkretnej ramki stosu były zarządzane przez kompilator i odczytywane przez program, musi istnieć pewna metoda obliczania pozycji tych wartości i odzyskiwania ich adresu pamięci. Pomagają w tym rejestry w CPU nazywane wskaźnikiem stosu i wskaźnikiem bazowym.

Wskaźnik bazowy, ebpzgodnie z konwencją, zawiera adres pamięci dna lub podstawy stosu. Pozycje wszystkich wartości w ramce stosu można obliczyć za pomocą adresu we wskaźniku podstawowym jako odniesienia. Jest to pokazane na powyższym obrazku: %ebp + 4jest to adres pamięci zapisany na przykład we wskaźniku podstawowym plus 4.

3. Kod generowany przez kompilator

Ale nie rozumiem, w jaki sposób zmienne na stosie są następnie odczytywane przez aplikację - jeśli zadeklaruję i przypiszę x jako liczbę całkowitą, powiedzmy x = 3, a pamięć jest zarezerwowana na stosie, a następnie przechowywana jest jej wartość 3 tam, a następnie w tej samej funkcji deklaruję i przypisuję y jako, powiedzmy 4, a następnie używam x w innym wyrażeniu, (powiedzmy z = 5 + x) w jaki sposób program może odczytać x w celu oceny z, kiedy jest na stosie poniżej y?

Użyjmy prostego przykładowego programu napisanego w C, aby zobaczyć, jak to działa:

int main(void)
{
        int x = 3;
        int y = 4;
        int z = 5 + x;

        return 0;
}

Przeanalizujmy tekst asemblera wygenerowany przez GCC dla tego tekstu źródłowego w języku C (dla uproszczenia wyczyściłem go trochę):

main:
    pushl   %ebp              # save previous frame's base address on stack
    movl    %esp, %ebp        # use current address of stack pointer as new frame base address
    subl    $16, %esp         # allocate 16 bytes of space on stack for function data
    movl    $3, -12(%ebp)     # variable x at address %ebp - 12
    movl    $4, -8(%ebp)      # variable y at address %ebp - 8
    movl    -12(%ebp), %eax   # write x to register %eax
    addl    $5, %eax          # x + 5 = 9
    movl    %eax, -4(%ebp)    # write 9 to address %ebp - 4 - this is z
    movl    $0, %eax
    leave

Co możemy zaobserwować, że zmienne X, Y i Z znajdują się pod adresami %ebp - 12, %ebp -8i %ebp - 4, odpowiednio. Innymi słowy, lokalizacje zmiennych w ramce stosu main()są obliczane przy użyciu adresu pamięci zapisanego w rejestrze CPU %ebp.

4. Dane w pamięci poza wskaźnikiem stosu są poza zakresem

Wyraźnie czegoś mi brakuje. Czy to dlatego, że położenie na stosie dotyczy tylko czasu życia / zakresu zmiennej i że cały stos jest faktycznie dostępny dla programu przez cały czas? Jeśli tak, to czy oznacza to, że istnieje jakiś inny indeks, który przechowuje tylko adresy zmiennych na stosie, aby umożliwić pobieranie wartości? Ale potem pomyślałem, że cały sens stosu polegał na tym, że wartości były przechowywane w tym samym miejscu co adres zmiennej?

Stos to region w pamięci wirtualnej, którego użyciem zarządza kompilator. Kompilator generuje kod w taki sposób, że wartości poza wskaźnikiem stosu (wartości poza górną krawędzią stosu) nigdy nie są przywoływane. Po wywołaniu funkcji pozycja wskaźnika stosu zmienia się, aby utworzyć miejsce na stosie, który można powiedzieć, że nie jest „poza granicami”.

Gdy funkcje są wywoływane i zwracane, wskaźnik stosu jest zmniejszany i zwiększany. Dane zapisane na stosie nie znikają, gdy są poza zakresem, ale kompilator nie generuje instrukcji odwołujących się do tych danych, ponieważ nie ma możliwości, aby kompilator obliczył adresy tych danych za pomocą %ebplub %esp.

5. Podsumowanie

Kod, który może być bezpośrednio wykonany przez CPU, jest generowany przez kompilator. Kompilator zarządza stosem, ramkami stosu dla funkcji i rejestrami procesora. Jedną strategią stosowaną przez GCC do śledzenia lokalizacji zmiennych w ramkach stosu w kodzie przeznaczonym do wykonania w architekturze i386 jest użycie adresu pamięci w podstawowym wskaźniku ramki stosu %ebp, jako odniesienia i zapisanie wartości zmiennych do lokalizacji w ramkach stosu w przesunięciach do adresu w %ebp.

Istnieją dwa specjalne rejestry: ESP (wskaźnik stosu) i EBP (wskaźnik bazowy). Po wywołaniu procedury zwykle wykonywane są pierwsze dwie operacje

push        ebp  
mov         ebp,esp 

Pierwsza operacja zapisuje wartość EBP na stosie, a druga operacja ładuje wartość wskaźnika stosu do wskaźnika bazowego (aby uzyskać dostęp do zmiennych lokalnych). Tak więc EBP wskazuje tę samą lokalizację, co ESP.

Asembler tłumaczy nazwy zmiennych na przesunięcia EBP. Na przykład, jeśli masz dwie zmienne lokalne x,yi masz coś podobnego

  x = 1;
  y = 2;
  return x + y;

to może być przetłumaczone na coś podobnego

   push        ebp  
   mov         ebp,esp
   mov  DWORD PTR [ ebp + 6],  1   ;x = 1
   mov  DWORD PTR [ ebp + 14], 2   ;y = 2
   mov  eax, [ ebp + 6 ]
   add  [ ebp + 14 ], eax          ; x + y 
   mov  eax, [ ebp + 14 ] 
   ...  

Wartości przesunięcia 6 i 14 są obliczane w czasie kompilacji.

Z grubsza tak to działa. Szczegółowe informacje można znaleźć w książce kompilatora.

Jesteś zdezorientowany, ponieważ do lokalnych zmiennych przechowywanych w stosie nie można uzyskać dostępu z regułą dostępu stosu: First In Last Out lub po prostu FILO .

Chodzi o to, że reguła FILO ma zastosowanie do sekwencji wywołań funkcji i ramek stosu , a nie do zmiennych lokalnych.

Co to jest rama stosu?

Kiedy wchodzisz do funkcji, otrzymuje ona pewną ilość pamięci na stosie, zwaną ramką stosu. Zmienne lokalne funkcji są przechowywane w ramce stosu. Można sobie wyobrazić, że rozmiar ramki stosu różni się w zależności od funkcji, ponieważ każda funkcja ma inną liczbę i wielkość zmiennych lokalnych.

Sposób przechowywania zmiennych lokalnych w ramce stosu nie ma nic wspólnego z FILO. (Nawet kolejność pojawiania się zmiennych lokalnych w kodzie źródłowym nie gwarantuje, że zmienne lokalne będą przechowywane w tej kolejności.) Jak prawidłowo wywnioskowałeś w swoim pytaniu: „istnieje jakiś inny indeks, który przechowuje tylko adresy zmiennych na stosie, aby umożliwić pobranie wartości ". Adresy zmiennych lokalnych są zazwyczaj obliczane na podstawie adresu podstawowego , takiego jak adres granicy ramki stosu i wartości przesunięcia specyficzne dla każdej zmiennej lokalnej.

Kiedy więc pojawia się to zachowanie FILO?

Co się stanie, jeśli wywołasz inną funkcję? Funkcja callee musi mieć własną ramkę stosu i to ta rama stosu jest wpychana do stosu . Oznacza to, że ramka stosu funkcji odbierającej jest umieszczona na ramce stosu funkcji wywołującej. A jeśli ta funkcja wywołań wywoła inną funkcję, wówczas ramka stosu zostanie ponownie przesunięta na wierzch stosu.

Co się stanie, jeśli funkcja zwróci? Gdy funkcja odbierającego powróci do funkcji wywołującej, ramka stosu funkcji odbierającej jest wysuwana ze stosu, uwalniając miejsce do wykorzystania w przyszłości.

Więc z twojego pytania:

Czy to dlatego, że położenie na stosie dotyczy tylko czasu życia / zakresu zmiennej i że cały stos jest faktycznie dostępny dla programu przez cały czas?

masz tu całkowitą rację, ponieważ wartości zmiennych lokalnych w ramce stosu nie są tak naprawdę kasowane, gdy funkcja powraca. Wartość po prostu tam pozostaje, chociaż lokalizacja pamięci, w której jest przechowywana, nie należy do ramki stosu żadnej funkcji. Wartość jest usuwana, gdy jakaś inna funkcja zyskuje ramkę stosu, która zawiera lokalizację i zapisuje jakąś inną wartość do tej lokalizacji pamięci.

Co zatem odróżnia stos od stosu?

Stos i stos są takie same w tym sensie, że oba są nazwami, które odnoszą się do pewnego miejsca w pamięci. Ponieważ możemy uzyskać dostęp do dowolnej lokalizacji w pamięci za pomocą jej adresu, możesz uzyskać dostęp do dowolnej lokalizacji na stosie lub stosie.

Różnica wynika z obietnicy złożonej przez system komputerowy na temat sposobu ich wykorzystania. Jak już powiedziałeś, sterta ma charakter referencyjny. Ponieważ wartości w stercie nie mają związku z żadną konkretną ramką stosu, zakres wartości nie jest powiązany z żadną funkcją. Zmienna lokalna jest jednak objęta zakresem funkcji i chociaż można uzyskać dostęp do dowolnej wartości zmiennej lokalnej, która znajduje się poza ramką stosu bieżącej funkcji, system spróbuje upewnić się, że takie zachowanie się nie zdarzy, za pomocą układać ramki. To daje nam złudzenie, że zmienna lokalna ma zakres do określonej funkcji.

Istnieje wiele sposobów implementacji zmiennych lokalnych przez system wykonawczy języka. Korzystanie ze stosu jest często skutecznym rozwiązaniem, stosowanym w wielu praktycznych przypadkach.

Intuicyjnie wskaźnik stosu spjest utrzymywany w czasie wykonywania (pod stałym adresem lub w rejestrze - to naprawdę ma znaczenie). Załóżmy, że każde „push” zwiększa wskaźnik stosu.

W czasie kompilacji kompilator określa adres każdej zmiennej, ponieważ sp - Kgdzie Kjest stałą, która zależy tylko od zakresu zmiennej (stąd można ją obliczyć w czasie kompilacji).

Zauważ, że używamy tutaj słowa „stos” w luźnym tego słowa znaczeniu. Do tego stosu nie można uzyskać dostępu tylko poprzez operacje push / pop / top, ale można również uzyskać dostęp za pomocą sp - K.

Weźmy na przykład ten pseudokod:

procedure f(int x, int y) {
  print(x,y);    // (1)
  if (...) {
    int z=x+y; // (2)
    print(x,y,z);  // (3)
  }
  print(x,y); // (4)
  return;
}

Po wywołaniu procedury x,yna stosie można przekazać argumenty . Dla uproszczenia załóżmy, że konwencja polega na tym, że dzwoniący xnajpierw naciska y.

Następnie kompilator w punkcie (1) może znaleźć xw sp - 2i yw sp - 1.

W punkcie 2 wprowadzono nową zmienną. Kompilator generuje kod sumujący x+y, tzn. Wskazany przez sp - 2i sp - 1, i wypycha wynik sumy na stos.

W punkcie (3) zjest drukowany. Kompilator wie, że jest to ostatnia zmienna w zakresie, więc wskazuje na to sp - 1. To już nie jest y, ponieważ zostało spzmienione. Mimo to, aby wydrukować ykompilator wie, że może go znaleźć, w tym zakresie, pod adresem sp - 2. Podobnie xznajduje się teraz w sp - 3.

W punkcie (4) wychodzimy z zakresu. zpojawia się, ypojawia się ponownie pod adresem sp - 1i xjest pod adresem sp - 2.

Kiedy wracamy, albo fdzwoniący wyskakuje x,yze stosu.

Tak więc obliczenia Kdla kompilatora polegają na z grubsza policzeniu, ile zmiennych ma zakres. W rzeczywistości jest to bardziej złożone, ponieważ nie wszystkie zmienne mają ten sam rozmiar, więc obliczenia Ksą nieco bardziej złożone. Czasami stos zawiera również adres zwrotny f, dlatego też Knależy go pominąć. Ale to są szczegóły techniczne.

Zauważ, że w niektórych językach programowania rzeczy mogą stać się jeszcze bardziej złożone, jeśli trzeba będzie obsługiwać bardziej złożone funkcje. Np. Procedury zagnieżdżone wymagają bardzo starannej analizy, ponieważ Kteraz muszą „pomijać” wiele adresów zwrotnych, szczególnie jeśli procedura zagnieżdżona jest rekurencyjna. Funkcje zamknięcia / lambdas / anonimowe również wymagają pewnej ostrożności przy obsłudze „przechwyconych” zmiennych. Powyższy przykład powinien jednak ilustrować podstawowy pomysł.

Najłatwiej jest pomyśleć o zmiennych jako o poprawnych nazwach adresów w pamięci. Rzeczywiście, niektóre asemblery wyświetlają w ten sposób kod maszynowy („przechowuj wartość 5 w adresie i”, gdzie ijest nazwą zmiennej).

Niektóre z tych adresów są „bezwzględne”, jak zmienne globalne, niektóre są „względne”, jak zmienne lokalne. Zmienne (tj. Adresy) w funkcjach odnoszą się do pewnego miejsca na „stosie”, które jest inne dla każdego wywołania funkcji; w ten sposób ta sama nazwa może odnosić się do różnych rzeczywistych obiektów, a cykliczne wywołania tej samej funkcji są niezależnymi wywołaniami działającymi na niezależnej pamięci.

Elementy danych, które mogą przejść na stos, są umieszczane na stosie - Tak! Jest to przestrzeń premium. Ponadto, kiedy już wepchnęliśmy xna stos, a następnie wepchnęliśmy yna stos, idealnie nie możemy uzyskać dostępu, xdopóki ysię nie pojawi. Musimy pop, yaby uzyskać dostęp x. Poprawiłeś je.

Stos nie składa się ze zmiennych, ale z frames

To, co źle zrozumiałeś, dotyczy samego stosu. Na stosie nie są bezpośrednio przesyłane elementy danych. Zamiast tego na stosie stack-framewypychane jest coś zwanego . Ta ramka stosu zawiera elementy danych. Chociaż nie możesz uzyskać dostępu do ramek głęboko w stosie, możesz uzyskać dostęp do górnej ramki i wszystkich zawartych w niej elementów danych.

Powiedzmy, że mamy nasze elementy danych w pakiecie w dwóch ramkach stosu frame-xi frame-y. Pchaliśmy je jeden po drugim. Teraz, dopóki frame-ysiedzi na górze frame-x, idealnie nie możesz uzyskać dostępu do żadnego elementu danych w środku frame-x. Tylko frame-yjest widoczne. ALE biorąc pod uwagę, że frame-yjest widoczny, możesz uzyskać dostęp do wszystkich zawartych w nim elementów danych. Widoczna jest cała ramka, odsłaniając wszystkie zawarte w niej elementy danych.

Koniec odpowiedzi. Więcej (rant) na tych ramkach

Podczas kompilacji tworzona jest lista wszystkich funkcji programu. Następnie dla każdej funkcji tworzona jest lista elementów danych, które można ustawiać jeden na drugim . Następnie dla każdej funkcji stack-frame-templatetworzony jest a . Ten szablon jest strukturą danych, która zawiera wszystkie wybrane zmienne, miejsce na dane wejściowe funkcji, dane wyjściowe itp. Teraz w czasie wykonywania, za każdym razem, gdy wywoływana jest funkcja, jej kopia templatejest umieszczana na stosie - wraz ze wszystkimi zmiennymi wejściowymi i pośrednimi . Kiedy ta funkcja wywołuje jakąś inną funkcję, wówczas nowa kopia tej funkcji stack-framejest umieszczana na stosie. Teraz, dopóki ta funkcja działa, elementy danych tej funkcji są zachowywane. Po zakończeniu tej funkcji ramka stosu jest wysuwana. Terazta ramka stosu jest aktywna i ta funkcja może uzyskać dostęp do wszystkich swoich zmiennych.

Należy pamiętać, że struktura i skład ramki stosu różni się w zależności od języka programowania i języka programowania. Nawet w języku mogą występować subtelne różnice w różnych implementacjach.

Dziękujemy za rozważenie CS. Jestem programistą i teraz biorę lekcje gry na pianinie :)