Stos wywołań — Call stack

W informatyce , A stos wywołań jest stos struktura danych , która przechowuje informacje o aktywnych podprogramów danego programu komputerowego . Ten rodzaj stosu jest również znany jako stosie wykonania , programem stosie , kontroli stosu , run-time stosie lub maszynowego stosie , często skracane do tylko „ stos ”. Chociaż utrzymanie stosu wywołań jest ważne dla prawidłowego funkcjonowania większości oprogramowania , szczegóły są zwykle ukryte i automatyczne w językach programowania wysokiego poziomu . Wiele zestawów instrukcji komputerowych zawiera specjalne instrukcje dotyczące manipulowania stosami.

Stos wywołań jest używany do kilku powiązanych celów, ale głównym powodem jego posiadania jest śledzenie punktu, do którego każdy aktywny podprogram powinien zwracać kontrolę po zakończeniu wykonywania. Aktywny podprogram to taki, który został wywołany, ale nie został jeszcze wykonany, po czym kontrola powinna zostać przekazana z powrotem do punktu wywołania. Takie aktywacje podprogramów mogą być zagnieżdżone na dowolnym poziomie (szczególnie rekurencyjne), stąd struktura stosu. Na przykład, jeśli podprogram DrawSquarewywołuje podprogram DrawLinez czterech różnych miejsc, DrawLinemusi wiedzieć, dokąd wrócić, gdy jego wykonanie się zakończy. Aby to osiągnąć, adres następujący po instrukcji, która przeskakuje do DrawLine, adres zwrotny , jest umieszczany na szczycie stosu wywołań przy każdym wywołaniu.

Opis

Ponieważ stos wywołań jest zorganizowany jako stos , osoba wywołująca wstawia adres zwrotny na stos, a wywoływana podprocedura po jej zakończeniu pobiera lub zdejmuje adres zwrotny ze stosu wywołań i przekazuje kontrolę na ten adres. Jeśli wywołany podprogram wywołuje jeszcze inny podprogram, wstawia inny adres powrotny na stos wywołań i tak dalej, a informacje są układane i rozkładane w stosie, zgodnie z poleceniem programu. Jeśli wypychanie zużywa całą przestrzeń przydzieloną dla stosu wywołań, pojawia się błąd zwany przepełnieniem stosu , co zwykle powoduje awarię programu . Dodanie wpisu podprogramu do stosu wywołań jest czasami nazywane „nawijaniem”; odwrotnie, usuwanie wpisów jest "rozwijaniem".

Zwykle jest dokładnie jeden stos wywołań związane z uruchomionego programu (lub dokładniej, z każdego zadania lub wątku z procesu ), choć dodatkowe stosy mogą być tworzone dla sygnału manipulacyjnych lub spółdzielczego wielozadaniowej (jak setcontext ). Ponieważ jest tylko jeden w tym ważnym kontekście, może być dalej w stosie (domyślnie, „zadania”); jednakże w języku programowania Forth stos dane lub parametr stos jest dostępne bardziej wyraźnie niż stos wywołań i jest powszechnie nazywany w stosie (patrz niżej).

W językach programowania wysokiego poziomu specyfika stosu wywołań jest zwykle ukryta przed programistą. Mają dostęp tylko do zestawu funkcji, a nie do pamięci na samym stosie. To jest przykład abstrakcji . Z drugiej strony większość języków asemblerowych wymaga od programistów zaangażowania w manipulowanie stosem. Rzeczywiste szczegóły stosu w języku programowania zależą od kompilatora , systemu operacyjnego i dostępnego zestawu instrukcji .

Funkcje stosu wywołań

Jak wspomniano powyżej, głównym celem stosu wywołań jest przechowywanie adresów zwrotnych . Kiedy podprogram jest wywoływany, lokalizacja (adres) instrukcji, w której procedura wywołująca może później zostać wznowiona, musi być gdzieś zapisana. Użycie stosu do zapisania adresu zwrotnego ma istotne zalety w porównaniu z alternatywnymi konwencjami wywoływania . Jednym z nich jest to, że każde zadanie może mieć swój własny stos, a zatem podprogram może być bezpieczny wątkowo , to znaczy może być aktywny jednocześnie dla różnych zadań wykonujących różne rzeczy. Inną korzyścią jest to, że poprzez zapewnienie ponowne wejścia , rekurencja jest automatycznie obsługiwane. Gdy funkcja wywołuje się rekursywnie, adres powrotu musi być przechowywany dla każdej aktywacji funkcji, aby później mógł zostać użyty do powrotu z aktywacji funkcji. Struktury stosu zapewniają tę możliwość automatycznie.

W zależności od języka, systemu operacyjnego i środowiska maszyny, stos wywołań może służyć dodatkowym celom, w tym na przykład:

Lokalne przechowywanie danych
Zobacz też: Alokacja pamięci na podstawie stosu
Podprogram często potrzebuje miejsca w pamięci do przechowywania wartości zmiennych lokalnych , zmiennych , które są znane tylko w ramach aktywnego podprogramu i nie zachowują wartości po jego powrocie. Często wygodnie jest przydzielić miejsce do tego zastosowania, po prostu przesuwając górę stosu na tyle, aby zapewnić miejsce. Jest to bardzo szybkie w porównaniu z dynamiczną alokacją pamięci , która wykorzystuje przestrzeń sterty . Zwróć uwagę, że każda oddzielna aktywacja podprogramu ma swoje osobne miejsce w stosie dla lokalnych.
Przekazywanie parametrów
Podprogramy często wymagają, aby wartości parametrów były dostarczane przez kod, który je wywołuje, i często zdarza się, że miejsce na te parametry może być umieszczone w stosie wywołań. Generalnie, jeśli jest tylko kilka małych parametrów, do przekazania wartości zostaną użyte rejestry procesora , ale jeśli jest więcej parametrów, niż można w ten sposób obsłużyć, potrzebna będzie przestrzeń pamięci. Stos wywołań dobrze sprawdza się jako miejsce na te parametry, zwłaszcza, że ​​każde wywołanie podprogramu, który będzie miał różne wartości parametrów, otrzyma osobne miejsce na stosie wywołań dla tych wartości.
Stos ewaluacyjny
Argumenty operacji arytmetycznych lub logicznych są najczęściej umieszczane w rejestrach i tam operowane. Jednak w niektórych sytuacjach operandy mogą być spiętrzone do dowolnej głębokości, co oznacza, że ​​trzeba użyć czegoś więcej niż rejestrów (tak jest w przypadku rozlewania się rejestrów ). Stos takich operandów, podobnie jak w kalkulatorze RPN , nazywany jest stosem oceny i może zajmować miejsce w stosie wywołań.
Wskaźnik do bieżącej instancji
Niektóre języki obiektowe (np. C++ ) przechowują wskaźnik this wraz z argumentami funkcji na stosie wywołań podczas wywoływania metod. Wskaźnik this wskazuje na instancję obiektu skojarzoną z metodą, która ma zostać wywołana.
Załączenie kontekstu podprogramu
Niektóre języki programowania (np. Pascal i Ada ) obsługują deklaracje zagnieżdżonych podprogramów , które mają dostęp do kontekstu ich procedur obejmujących, tj. parametrów i zmiennych lokalnych w zakresie procedur zewnętrznych. Takie statyczne zagnieżdżenie może się powtarzać — funkcja zadeklarowana w funkcji zadeklarowanej w funkcji... Implementacja musi zapewniać środki, dzięki którym wywoływana funkcja na dowolnym poziomie zagnieżdżenia statycznego może odwoływać się do otaczającej ramki na każdym obejmującym poziomie zagnieżdżenia. Zwykle to odniesienie jest implementowane przez wskaźnik do ramki ostatnio aktywowanej instancji funkcji otaczającej, zwanego „łączem w dół” lub „łączem statycznym”, aby odróżnić go od „łącza dynamicznego”, który odnosi się do bezpośredniego wywołującego ( które nie muszą być statyczną funkcją nadrzędną).

Zamiast łącza statycznego, odniesienia do otaczających ramek statycznych mogą być gromadzone w tablicy wskaźników znanej jako wyświetlacz, która jest indeksowana w celu zlokalizowania pożądanej ramki. Głębokość zagnieżdżenia leksykalnego procedury jest znaną stałą, więc rozmiar wyświetlania procedury jest stały. Znana jest również liczba zakresów zawierających do przebycia, indeks do wyświetlania jest również stały. Zazwyczaj wyświetlacz procedury znajduje się we własnej ramce stosu, ale Burroughs B6500 zaimplementował taki wyświetlacz w sprzęcie, który obsługuje do 32 poziomów statycznego zagnieżdżania.
Wpisy wyświetlacza oznaczające zakresy są uzyskiwane z odpowiedniego prefiksu wyświetlacza wywołującego. Wewnętrzna procedura, która rekursywnie tworzy oddzielne ramki wywołań dla każdego wywołania. W tym przypadku wszystkie statyczne linki procedury wewnętrznej wskazują na ten sam kontekst procedury zewnętrznej.
Inny stan zwrotu
Oprócz adresu zwrotnego, w niektórych środowiskach mogą występować inne stany maszyny lub oprogramowania, które muszą zostać przywrócone po powrocie podprogramu. Może to obejmować takie rzeczy, jak poziom uprawnień, informacje o obsłudze wyjątków, tryby arytmetyczne i tak dalej. W razie potrzeby może to być przechowywane w stosie wywołań, tak jak adres zwrotny.

Typowy stos wywołań jest używany dla adresu zwrotnego, wartości lokalnych i parametrów (znanych jako ramka wywołania ). W niektórych środowiskach do stosu wywołań może być przypisanych więcej lub mniej funkcji. W języku programowania Forth , na przykład, zwykle tylko adres powrotu, zliczone parametry pętli i indeksy oraz ewentualnie zmienne lokalne są przechowywane na stosie wywołań (który w tym środowisku nazywa się stosem powrotów ), chociaż dowolne dane mogą być tymczasowo umieszczane tam za pomocą specjalnego kodu obsługującego stos zwrotów, o ile spełnione są potrzeby połączeń i zwrotów; parametry są zwykle przechowywane na osobnym stosie danych lub parametrów stosie , zazwyczaj nazywany stos w terminologii Forth chociaż nie jest stos wywołań, ponieważ jest zwykle dostępny w bardziej wyraźny sposób. Niektóre Forthy mają również trzeci stos dla parametrów zmiennoprzecinkowych .

Struktura

Układ stosu wywołań dla rosnących stosów

Wezwanie stos składa się z ramek stosu (zwanych również rekordy aktywacji lub ramek aktywacji ). Są to struktury danych zależne od komputera i zależne od ABI , zawierające informacje o stanie podprogramu. Każda ramka stosu odpowiada wywołaniu podprogramu, który nie został jeszcze zakończony zwrotem. Na przykład, jeśli podprogram nazwany DrawLinejest aktualnie uruchomiony i został wywołany przez podprogram DrawSquare, górna część stosu wywołań może być ułożona tak, jak na sąsiednim obrazku.

Taki schemat można narysować w dowolnym kierunku, o ile rozumie się położenie wierzchołka, a tym samym kierunek wzrostu stosu. Ponadto, niezależnie od tego, architektury różnią się tym, czy stosy wywołań rosną w kierunku wyższych adresów, czy w kierunku niższych adresów. Logika diagramu jest niezależna od wyboru adresowania.

Ramka stosu na szczycie stosu jest przeznaczona dla aktualnie wykonywanej procedury. Ramka stosu zazwyczaj zawiera co najmniej następujące elementy (w kolejności push):

  • argumenty (wartości parametrów) przekazane do procedury (jeśli istnieją);
  • adres powrotu z powrotem do wołającego podprogram (np. w DrawLineramce stosu, adres w DrawSquarekodzie ); i
  • miejsce na lokalne zmienne procedury (jeśli istnieją).

Wskaźniki stosu i ramki

Gdy rozmiary ramek stosu mogą się różnić, na przykład między różnymi funkcjami lub między wywołaniami określonej funkcji, zdjęcie ramki ze stosu nie stanowi stałego zmniejszenia wskaźnika stosu . Podczas powrotu funkcji wskaźnik stosu jest przywracany do wskaźnika ramki , wartości wskaźnika stosu tuż przed wywołaniem funkcji. Każda ramka stosu zawiera wskaźnik stosu do góry ramki bezpośrednio poniżej. Wskaźnik stosu jest zmiennym rejestrem współdzielonym między wszystkimi wywołaniami. Wskaźnik ramki danego wywołania funkcji jest kopią wskaźnika stosu, jaki był przed wywołaniem funkcji.

Lokalizacje wszystkich innych pól w ramce można zdefiniować albo względem góry ramki, jako ujemne przesunięcia wskaźnika stosu, albo względem górnej części ramki poniżej, jako dodatnie przesunięcia wskaźnika ramki. Sama lokalizacja wskaźnika ramki musi być z natury zdefiniowana jako ujemne przesunięcie wskaźnika stosu.

Zapisywanie adresu do ramki dzwoniącego

W większości systemów ramka stosu ma pole, które zawiera poprzednią wartość rejestru wskaźnika ramki, wartość, jaką miała podczas wykonywania funkcji wywołującej. Na przykład ramka stosu DrawLinemiałaby miejsce w pamięci zawierające wartość wskaźnika ramki, która DrawSquareużywa (nie pokazano na powyższym schemacie). Wartość jest zapisywana po wejściu do podprogramu i przywracana po powrocie. Posiadanie takiego pola w znanej lokalizacji w ramce stosu umożliwia kodowi dostęp do każdej ramki kolejno pod ramką aktualnie wykonywanej procedury, a także pozwala procedurze na łatwe przywrócenie wskaźnika ramki do ramki wywołującego , tuż przed jego powrotem.

Zagnieżdżone leksykalnie procedury

Dalsze informacje: Funkcja zagnieżdżona i zmienna nielokalna

Języki programowania, które obsługują zagnieżdżone podprogramy, mają również pole w ramce wywołania, które wskazuje na ramkę stosu ostatniej aktywacji procedury, która najdokładniej hermetyzuje wywoływanego, tj. bezpośredni zasięg wywoływanego. Nazywa się to łączem dostępu lub łączem statycznym (ponieważ śledzi statyczne zagnieżdżanie podczas wywołań dynamicznych i rekurencyjnych) i zapewnia procedurze (jak również innym podprogramom, które może wywołać) dostęp do lokalnych danych jego procedur enkapsulacji przy każdym zagnieżdżaniu poziom. Niektóre architektury, kompilatory lub przypadki optymalizacji przechowują jedno łącze dla każdego poziomu otaczającego (nie tylko bezpośrednio otaczającego), tak że głęboko zagnieżdżone procedury, które uzyskują dostęp do płytkich danych, nie muszą przechodzić przez kilka łączy; strategia ta jest często nazywana „wyświetlaniem”.

Łącza dostępu można zoptymalizować, gdy funkcja wewnętrzna nie uzyskuje dostępu do żadnych (niestałych) danych lokalnych w enkapsulacji, tak jak ma to miejsce w przypadku czystych funkcji komunikujących się tylko za pomocą argumentów i wartości zwracanych. Niektóre historyczne komputery, takie jak duże systemy Burroughs , miały specjalne „rejestry wyświetlania” do obsługi zagnieżdżonych funkcji, podczas gdy kompilatory dla większości nowoczesnych maszyn (takich jak wszechobecny x86) po prostu rezerwują na stosie kilka słów na wskaźniki, w razie potrzeby.

Zakładka

Dla niektórych celów, ramka stosu podprogramu i jego wywołującego można uznać za nakładające się, nakładanie składające się z obszaru, w którym parametry są przekazywane od wywołującego do wywoływanego. W niektórych środowiskach wywołujący wkłada każdy argument na stos, rozszerzając w ten sposób swoją ramkę stosu, a następnie wywołuje wywoływanego. W innych środowiskach wywołujący ma wstępnie przydzielony obszar na górze swojej ramki stosu do przechowywania argumentów, które dostarcza do innych podprogramów, które wywołuje. Ten obszar jest czasami nazywany obszarem argumentów wychodzących lub obszarem objaśnień . W tym podejściu kompilator oblicza wielkość obszaru jako największą potrzebną dowolnej nazwie podprogramu.

Posługiwać się

Zadzwoń do przetwarzania witryny

Zwykle manipulacja stosem wywołań potrzebna w miejscu wywołania podprogramu jest minimalna (co jest dobre, ponieważ może być wiele witryn wywołań dla każdego podprogramu, który ma zostać wywołany). Wartości rzeczywistych argumentów są oceniane w witrynie wywołania, ponieważ są one specyficzne dla konkretnego wywołania i albo są odkładane na stos, albo umieszczane w rejestrach, zgodnie z użytą konwencją wywołania . Rzeczywista instrukcja wywołania, taka jak „gałąź i łącze”, jest następnie zwykle wykonywana w celu przekazania sterowania do kodu podprogramu docelowego.

Przetwarzanie wpisów podprogramów

W wywoływanej podprogramie pierwszy wykonywany kod jest zwykle nazywany prologiem podprogramu , ponieważ wykonuje niezbędne porządki przed rozpoczęciem kodu dla instrukcji procedury.

W przypadku architektur zestawów instrukcji, w których instrukcja używana do wywoływania podprogramu umieszcza adres powrotu do rejestru, zamiast wpychać go na stos, prolog zwykle zapisuje adres powrotu, wkładając wartość na stos wywołań, chociaż jeśli wywołany podprogram nie wywołuje żadnych innych podprogramów, może pozostawić wartość w rejestrze. Podobnie można przesunąć bieżące wartości wskaźnika stosu i/lub wskaźnika ramki.

Jeśli używane są wskaźniki ramki, prolog zazwyczaj ustawia nową wartość rejestru wskaźnika ramki ze wskaźnika stosu. Przestrzeń na stosie dla zmiennych lokalnych może być następnie przydzielona poprzez przyrostową zmianę wskaźnika stosu.

Język programowania Forth umożliwia jawne zwijanie stosu wywołań (zwanego tam „stosem zwrotnym”).

Przetwarzanie zwrotu

Kiedy podprogram jest gotowy do powrotu, wykonuje epilog, który cofa kroki prologu. Zwykle przywróci to zapisane wartości rejestru (takie jak wartość wskaźnika ramki) z ramki stosu, zdejmie całą ramkę stosu ze stosu przez zmianę wartości wskaźnika stosu, a na koniec rozgałęzi się do instrukcji pod adresem powrotu. Zgodnie z wieloma konwencjami wywoływania elementy zdejmowane ze stosu przez epilog zawierają oryginalne wartości argumentów, w takim przypadku zwykle nie ma dalszych manipulacji stosu, które muszą być wykonane przez wywołującego. Jednak w przypadku niektórych konwencji wywoływania obowiązkiem wywołującego jest usunięcie argumentów ze stosu po powrocie.

Rozwijanie

Powrót z wywołanej funkcji usunie górną ramkę ze stosu, być może pozostawiając wartość zwracaną. Bardziej ogólna czynność zdejmowania jednej lub więcej ramek ze stosu w celu wznowienia wykonywania w innym miejscu w programie nazywana jest rozwijaniem stosu i musi być wykonywana, gdy używane są nielokalne struktury sterujące, takie jak te używane do obsługi wyjątków . W takim przypadku ramka stosu funkcji zawiera jeden lub więcej wpisów określających procedury obsługi wyjątków. Po zgłoszeniu wyjątku stos jest rozwijany do momentu znalezienia programu obsługi, który jest przygotowany do obsługi (przechwycenia) typu zgłaszanego wyjątku.

Niektóre języki mają inne struktury kontrolne, które wymagają ogólnego rozwinięcia. Pascal umożliwia globalnej instrukcji goto przekazanie kontroli z funkcji zagnieżdżonej do wcześniej wywołanej funkcji zewnętrznej. Ta operacja wymaga rozwinięcia stosu, usunięcia tylu ramek stosu, ile jest to konieczne, aby przywrócić właściwy kontekst w celu przeniesienia kontroli do instrukcji docelowej w otaczającej funkcji zewnętrznej. Podobnie C ma funkcje setjmpi,longjmp które działają jako nielokalne goto. Common Lisp pozwala kontrolować, co się dzieje, gdy stos jest rozwijany, za pomocą unwind-protectspecjalnego operatora.

Podczas stosowania kontynuacji stos jest (logicznie) rozwijany, a następnie przewijany ze stosem kontynuacji. To nie jedyny sposób na zaimplementowanie kontynuacji; na przykład, używając wielu jawnych stosów, zastosowanie kontynuacji może po prostu aktywować jego stos i zwinąć wartość do przekazania. Język programowania Scheme pozwala na wykonanie dowolnych fragmentów w określonych punktach podczas "odwijania" lub "przewijania" stosu kontrolnego, gdy wywoływana jest kontynuacja.

Kontrola

Zobacz też: Profilowanie (programowanie komputerowe)

Stos wywołań może być czasami sprawdzany podczas działania programu. W zależności od tego, jak program jest napisany i skompilowany, informacje na stosie można wykorzystać do określenia wartości pośrednich i śladów wywołań funkcji. Zostało to wykorzystane do generowania drobnoziarnistych testów automatycznych, a w przypadkach takich jak Ruby i Smalltalk do implementacji kontynuacji pierwszej klasy. Jako przykład, GNU Debugger (GDB) implementuje interaktywną inspekcję stosu wywołań uruchomionego, ale wstrzymanego programu C.

Pobieranie próbek stosu wywołań w czasie regularnym może być przydatne w profilowaniu wydajności programów, ponieważ jeśli wskaźnik podprogramu pojawia się wiele razy na danych próbkowania stosu wywołań, prawdopodobnie jest to wąskie gardło kodu i należy go sprawdzać pod kątem problemów z wydajnością.

Bezpieczeństwo

Główny artykuł: Przepełnienie bufora stosu

W języku z wolnymi wskaźnikami lub niesprawdzonymi zapisami w tablicy (tak jak w C), mieszanie danych przepływu sterowania, które wpływają na wykonanie kodu (adresy powrotne lub wskaźniki zapisanej ramki) i proste dane programu (parametry lub wartości zwracane ) w stosie wywołań jest zagrożeniem bezpieczeństwa, które może być wykorzystane przez przepełnienie bufora stosu jako najczęstszy typ przepełnienia bufora .

Jeden z takich ataków polega na wypełnieniu jednego bufora dowolnym kodem wykonywalnym, a następnie przepełnieniu tego samego lub innego bufora w celu nadpisania adresu zwrotnego wartością, która wskazuje bezpośrednio na kod wykonywalny. W rezultacie, gdy funkcja zwraca, komputer wykonuje ten kod. Ten rodzaj ataku można łatwo zablokować za pomocą W^X . Podobne ataki mogą odnieść sukces nawet przy włączonej ochronie W^X, w tym atak powrotu do libc lub ataki pochodzące z programowania zorientowanego na powrót . Zaproponowano różne środki zaradcze, takie jak przechowywanie tablic w całkowicie oddzielnej lokalizacji od stosu powrotnego, jak ma to miejsce w języku programowania Forth.

Zobacz też

Bibliografia

Dalsza lektura

Linki zewnętrzne