20.2 — Stos i sterta

Pamięć używana przez program jest zazwyczaj podzielona na kilka różnych obszarów, zwanych segmentami:

• Segment kodu (zwany także segmentem tekstowym), w którym znajduje się skompilowany program. Segment kodu jest zazwyczaj tylko do odczytu.
• Segment bss (zwany także segmentem niezainicjowanych danych), w którym przechowywane są zmienne globalne i statyczne o wartości zerowej.
• Segment danych (zwany także zainicjalizowanym segmentem danych), w którym przechowywane są zainicjalizowane zmienne globalne i statyczne.
• Sterta, z której alokowane są dynamicznie przydzielane zmienne.
• Stos wywołań, w którym znajduje się funkcja przechowywane są parametry, zmienne lokalne i inne informacje związane z funkcjami.

W tej lekcji skupimy się przede wszystkim na stercie i stosie, ponieważ to tam dzieje się większość interesujących rzeczy.

Segment sterty

Segment sterty (znany również jako „wolny magazyn”) śledzi pamięć używaną do dynamicznej alokacji pamięci. O stercie mówiliśmy już trochę na lekcji 19.1 — Dynamiczna alokacja pamięci za pomocą operacji new i usuwania, więc będzie to podsumowanie.

W C++, gdy używasz operatora new do alokacji pamięci, pamięć ta jest alokowana w segmencie sterty aplikacji.

Zakładając, że int ma 4 bajty:

int* ptr { new int }; // new int allocates 4 bytes in the heap
int* array { new int[10] }; // new int[10] allocates 40 bytes in the heap

Adres tej pamięci jest przekazywany z powrotem przez operator new i może być następnie zapisany w wskaźnik. Nie musisz martwić się mechaniką procesu lokalizowania i przydzielania wolnej pamięci użytkownikowi. Warto jednak wiedzieć, że sekwencyjne żądania pamięci mogą nie skutkować przydzieleniem adresów pamięci sekwencyjnej!

int* ptr1 { new int };
int* ptr2 { new int };
// ptr1 and ptr2 may not have sequential addresses

Po usunięciu dynamicznie alokowanej zmiennej pamięć jest „zwracana” na stertę i może być ponownie przydzielona w miarę otrzymywania przyszłych żądań alokacji. Pamiętaj, że usunięcie wskaźnika nie powoduje usunięcia zmiennej, a jedynie zwraca pamięć pod powiązanym adresem z powrotem do systemu operacyjnego.

Sterta ma zalety i wady:

• Alokacja pamięci na stercie jest stosunkowo powolna.
• Przydzielona pamięć pozostaje przydzielona do czasu jej wyraźnego zwolnienia (uważaj na wycieki pamięci) lub zakończenia aplikacji (w tym momencie system operacyjny powinien ją wyczyścić) up).
• Dostęp do pamięci alokowanej dynamicznie musi być możliwy poprzez wskaźnik. Dereferencja wskaźnika jest wolniejsza niż bezpośredni dostęp do zmiennej.
• Ponieważ sterta to duża pula pamięci, można tu alokować duże tablice, struktury lub klasy.

Stos wywołań

Klasa stos wywołań (zwykle nazywany „stosem”) ma do odegrania znacznie bardziej interesującą rolę. Stos wywołań śledzi wszystkie aktywne funkcje (te, które zostały wywołane, ale jeszcze się nie zakończyły) od początku programu do bieżącego punktu wykonania i obsługuje alokację wszystkich parametrów funkcji i zmiennych lokalnych.

Stos wywołań jest zaimplementowany jako struktura danych stosu. Zanim więc będziemy mogli porozmawiać o tym, jak działa stos wywołań, musimy zrozumieć, czym jest struktura danych stosu.

Struktura danych stosu

A dane struktura to mechanizm programistyczny służący do organizowania danych w sposób umożliwiający ich efektywne wykorzystanie. Widziałeś już kilka typów struktur danych, takich jak tablice i struktury. Obie te struktury danych zapewniają mechanizmy przechowywania danych i efektywnego dostępu do nich. Istnieje wiele dodatkowych struktur danych, które są powszechnie używane w programowaniu, z których sporo jest zaimplementowanych w standardowej bibliotece, a stos jest jedną z nich.

Rozważmy stos talerzy w stołówce. Ponieważ każda płyta jest ciężka i są ułożone jeden na drugim, tak naprawdę możesz zrobić tylko jedną z trzech rzeczy:

1. Spójrz na powierzchnię górnej płyty
2. Zdejmij górną płytę ze stosu (odsłaniając tę ​​pod spodem, jeśli istnieje)
3. Umieść nową płytkę na wierzchu stosu (ukrywając tę ​​pod spodem, jeśli istnieje)

W programowaniu komputerowym stos jest strukturą danych pojemnika, która przechowuje wiele zmiennych (podobnie jak tablica). Jednakże, podczas gdy tablica umożliwia dostęp i modyfikowanie elementów w dowolnej kolejności (zwanej losowy dostęp), stos jest bardziej ograniczony. Operacje, które można wykonać na stosie, odpowiadają trzem rzeczom wymienionym powyżej:

1. Spójrz na najwyższy element stosu (zwykle robi się to za pomocą funkcji zwanej top(), ale czasami nazywanej peek())
2. Zdejmij najwyższy element ze stosu (wykonuje się to za pomocą funkcji zwanej pop())
3. Umieść nowy element na wierzchu stosu (wykonuje się to za pomocą funkcji zwanej push())

Stos to struktura „ostatnie weszło, pierwsze wyszło” (LIFO). Ostatni przedmiot umieszczony na stosie będzie pierwszym, który zostanie wyrzucony. Jeśli umieścisz nowy talerz na wierzchu stosu, pierwszym talerzem usuniętym ze stosu będzie ten talerz, który właśnie wsunąłeś jako ostatni. Ostatni, pierwszy. Gdy przedmioty są umieszczane na stosie, stos staje się większy - gdy przedmioty są usuwane, stos staje się mniejszy.

Na przykład, oto krótka sekwencja pokazująca, jak działa wypychanie i otwieranie stosu:

Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1

Analogia z płytą jest całkiem dobrą analogią do działania stosu wywołań, ale możemy stworzyć lepszą analogię. Rozważmy kilka skrzynek pocztowych ułożonych jedna na drugiej. Każda skrzynka pocztowa może pomieścić tylko jeden element, a wszystkie skrzynki pocztowe są początkowo puste. Ponadto każda skrzynka pocztowa jest przybijana do skrzynki znajdującej się pod nią, więc nie ma możliwości zmiany liczby skrzynek pocztowych. Jeśli nie możemy zmienić liczby skrzynek pocztowych, jak uzyskać zachowanie przypominające stos?

Najpierw używamy znacznika (np. karteczki samoprzylepnej), aby śledzić, gdzie znajduje się najniżej pusta skrzynka pocztowa. Na początku będzie to najniższa skrzynka pocztowa (na dole stosu). Kiedy wypychamy przedmiot na stos skrzynek pocztowych, umieszczamy go w zaznaczonej skrzynce pocztowej (która jest pierwszą pustą skrzynką pocztową) i przesuwamy znacznik o jedną skrzynkę w górę. Kiedy zdejmiemy przedmiot ze stosu, przesuwamy znacznik w dół o jedną skrzynkę pocztową (tak, aby wskazywał górną, niepustą skrzynkę pocztową) i usuwamy przedmiot z tej skrzynki pocztowej. Wszystko poniżej znacznika uważa się za „na stosie”. Wszystko, co znajduje się przy znaczniku lub nad nim, nie znajduje się na stosie.

Segment stosu wywołań

Segment stosu wywołań przechowuje pamięć używaną dla stosu wywołań. Po uruchomieniu aplikacji funkcja main() jest umieszczana na stosie wywołań przez system operacyjny. Następnie program rozpoczyna wykonywanie.

W przypadku napotkania wywołania funkcji, funkcja jest umieszczana na stosie wywołań. Kiedy bieżąca funkcja się kończy, jest ona usuwana ze stosu wywołań (proces ten jest czasami nazywany odwijaniem stosu). Zatem patrząc na funkcje znajdujące się obecnie na stosie wywołań, możemy zobaczyć wszystkie funkcje, które zostały wywołane, aby przejść do bieżącego punktu wykonania.

Powyższa analogia do skrzynki pocztowej jest dość analogiczna do działania stosu wywołań. Sam stos jest fragmentem adresów pamięci o stałym rozmiarze. Skrzynki pocztowe są adresami pamięci, a „elementy”, które wypychamy i umieszczamy na stosie, nazywane są ramkami stosu. Ramka stosu śledzi wszystkie dane powiązane z jednym wywołaniem funkcji. Za chwilę porozmawiamy więcej o klatkach stosowych. „Znacznik” to rejestr (mały fragment pamięci w procesorze) znany jako wskaźnik stosu (czasami w skrócie „SP”). Wskaźnik stosu śledzi, gdzie aktualnie znajduje się szczyt stosu wywołań.

Możemy dokonać jeszcze jednej optymalizacji: kiedy usuwamy element ze stosu wywołań, wystarczy przesunąć wskaźnik stosu w dół — nie musimy czyścić ani zerować pamięci używanej przez wyrzuconą ramkę stosu (co jest równoznaczne z opróżnieniem skrzynki pocztowej). Ta pamięć nie jest już uważana za znajdującą się „na stosie” (wskaźnik stosu będzie znajdował się pod tym adresem lub poniżej), więc nie będzie można uzyskać do niej dostępu. Jeśli później wepchniemy nową ramkę stosu do tej samej pamięci, zastąpi ona starą wartość, której nigdy nie wyczyściliśmy.

Stos wywołań w akcji

Przyjrzyjmy się bardziej szczegółowo, jak działa stos wywołań. Oto sekwencja kroków zachodzących po wywołaniu funkcji:

1. Program napotkał wywołanie funkcji.
2. Konstruowana jest ramka stosu i umieszczana na stosie. Ramka stosu składa się z:

• Adresu instrukcji poza wywołaniem funkcji (zwanego adresem zwrotnym). W ten sposób CPU zapamiętuje, dokąd ma wrócić po wyjściu wywołanej funkcji.
• Wszystkie argumenty funkcji.
• Pamięć dowolnych zmiennych lokalnych
• Zapisane kopie wszelkich rejestrów zmodyfikowanych przez funkcję, które muszą zostać odtworzone po powrocie funkcji

3. CPU przeskakuje do punktu początkowego funkcji.
4. Rozpoczynają się instrukcje wewnątrz funkcji wykonywanie.

Po zakończeniu funkcji mają miejsce następujące kroki:

1. Rejestry są odtwarzane ze stosu wywołań
2. Ramka stosu jest usuwana ze stosu. Spowoduje to zwolnienie pamięci na wszystkie lokalne zmienne i argumenty.
3. Zwracana wartość jest obsługiwana.
4. Procesor wznawia wykonywanie pod adresem zwrotnym.

Zwracane wartości mogą być obsługiwane na wiele różnych sposobów, w zależności od architektury komputera. Niektóre architektury zawierają wartość zwracaną jako część ramki stosu. Inni używają rejestrów procesora.

Zazwyczaj nie jest ważne, aby znać wszystkie szczegóły dotyczące działania stosu wywołań. Jednak zrozumienie, że funkcje są skutecznie wypychane na stos po ich wywołaniu i wyskakujące (rozwijane) po powrocie, daje podstawy potrzebne do zrozumienia rekurencji, a także kilka innych koncepcji przydatnych podczas debugowania.

Uwaga techniczna: w niektórych architekturach stos wywołań rośnie od adresu pamięci 0. W innych rośnie w kierunku adresu pamięci 0. W rezultacie nowo wypchnięte ramki stosu mogą mieć wyższy lub niższy adres pamięci niż poprzednie

Przykład szybkiego i brudnego stosu wywołań

Rozważmy następujące proste zastosowanie:

int foo(int x)
{
    // b
    return x;
} // foo is popped off the call stack here

int main()
{
    // a
    foo(5); // foo is pushed on the call stack here
    // c

    return 0;
}

Stos wywołań wygląda następująco w oznaczonych punktach:

a:

main()

b:

foo() (including parameter x)
main()

c:

main()

Przepełnienie stosu

Stos ma ograniczone rozmiar, w związku z czym może pomieścić jedynie ograniczoną ilość informacji. W programie Visual Studio dla systemu Windows domyślny rozmiar stosu to 1 MB. W przypadku wariantów g++/Clang dla Uniksa może on mieć rozmiar nawet 8MB. Jeśli program spróbuje umieścić zbyt dużo informacji na stosie, nastąpi przepełnienie stosu. Przepełnienie stosu ma miejsce, gdy cała pamięć na stosie zostanie przydzielona — w takim przypadku dalsze alokacje zaczynają się przepełniać do innych sekcji pamięci.

Przepełnienie stosu jest zazwyczaj wynikiem alokacji zbyt wielu zmiennych na stosie i/lub wykonania zbyt wielu zagnieżdżonych wywołań funkcji (gdzie funkcja A wywołuje funkcję B wywołuje funkcję C wywołuje funkcję D itd...) W nowoczesnych systemach operacyjnych przepełnienie stosu zazwyczaj powoduje, że system operacyjny zgłasza naruszenie zasad dostępu i kończy działanie programu.

Oto przykładowy program, który prawdopodobnie spowoduje przepełnienie stosu. Możesz uruchomić go w swoim systemie i zobaczyć, jak się zawiesza:

#include <iostream>

int main()
{
    int stack[10000000];
    std::cout << "hi" << stack[0]; // we'll use stack[0] here so the compiler won't optimize the array away

    return 0;
}

Ten program próbuje przydzielić ogromną (prawdopodobnie 40MB) tablicę na stosie. Ponieważ stos nie jest wystarczająco duży, aby obsłużyć tę tablicę, alokacja tablicy powoduje przepełnienie części pamięci, których program nie może używać.

W systemie Windows (Visual Studio) ten program generuje wynik:

HelloWorld.exe (process 15916) exited with code -1073741571.

-1073741571 to c0000005 w formacie szesnastkowym, co jest kodem systemu operacyjnego Windows oznaczającym naruszenie zasad dostępu. Należy pamiętać, że „cześć” nigdy nie jest wypisywane, ponieważ program kończy się przed tym momentem.

Oto kolejny program, który spowoduje przepełnienie stosu z innego powodu:

// h/t to reader yellowEmu for the idea of adding a counter
#include <iostream>

int g_counter{ 0 };

void eatStack()
{
    std::cout << ++g_counter << ' ';

    // We use a conditional here to avoid compiler warnings about infinite recursion
    if (g_counter > 0)
        eatStack(); // note that eatStack() calls itself

    // Needed to prevent compiler from doing tail-call optimization
    std::cout << "hi";
}

int main()
{
    eatStack();

    return 0;
}

W powyższym programie ramka stosu jest umieszczana na stosie za każdym razem, gdy wywoływana jest funkcja eatStack(). Ponieważ funkcja eatStack() wywołuje samą siebie (i nigdy nie wraca do wywołującego), w końcu w stosie zabraknie pamięci i spowoduje przepełnienie.

Stos ma zalety i wady:

• Alokacja pamięci na stosie jest stosunkowo szybka.
• Pamięć przydzielona na stosie pozostaje w zasięgu tak długo, jak długo się znajduje na stosie. Jest niszczona po zdjęciu ze stosu.
• Cała pamięć przydzielona na stosie jest znana w czasie kompilacji. W rezultacie dostęp do tej pamięci można uzyskać bezpośrednio poprzez zmienną.
• Ponieważ stos jest stosunkowo mały, generalnie nie jest dobrym pomysłem robienie czegokolwiek, co zajmuje dużo miejsca na stosie. Obejmuje to alokację lub kopiowanie dużych tablic lub innych struktur intensywnie wykorzystujących pamięć.