Co to jest rozwijanie stosu?

Co to jest rozwijanie stosu? Przeszukałem, ale nie mogłem znaleźć pouczającej odpowiedzi!

O rozwijaniu stosów mówi się zwykle w związku z obsługą wyjątków. Oto przykład:

void func( int x )
{
    char* pleak = new char[1024]; // might be lost => memory leak
    std::string s( "hello world" ); // will be properly destructed

    if ( x ) throw std::runtime_error( "boom" );

    delete [] pleak; // will only get here if x == 0. if x!=0, throw exception
}

int main()
{
    try
    {
        func( 10 );
    }
    catch ( const std::exception& e )
    {
        return 1;
    }

    return 0;
}

Tutaj przydzielona pamięć pleakzostanie utracona, jeśli zostanie zgłoszony wyjątek, a przydzielona pamięć szostanie odpowiednio zwolniona przez std::stringdestruktor. Obiekty przydzielone na stosie są „rozwijane” po wyjściu z zakresu (tutaj zakres jest funkcjąfunc .) Odbywa się to przez kompilator wstawiający wywołania do destruktorów zmiennych automatycznych (stosowych).

Jest to bardzo potężna koncepcja prowadząca do techniki zwanej RAII , czyli pozyskiwania zasobów to inicjalizacji , która pomaga nam zarządzać zasobami takimi jak pamięć, połączenia z bazą danych, otwarte deskryptory plików itp. W C ++.

Teraz pozwala nam to zapewnić wyjątkowe gwarancje bezpieczeństwa .

Wszystko to dotyczy C ++:

Definicja : Kiedy tworzysz obiekty statycznie (na stosie zamiast przydzielać je w pamięci stosu) i wykonujesz wywołania funkcji, są one „układane w stos”.

Po wyjściu z zakresu (wszystko ograniczone przez {i }) (przez użycie return XXX;, dotarcie do końca zakresu lub zgłoszenie wyjątku) wszystko w tym zakresie jest niszczone (wywoływane są wszystkiego, co obejmuje destruktory). Ten proces niszczenia lokalnych obiektów i wywoływania destruktorów nazywa się odwijaniem stosu.

Występują następujące problemy związane z rozwijaniem stosu:

1. unikanie wycieków pamięci (wszystko dynamicznie alokowane, które nie jest zarządzane przez obiekt lokalny i wyczyszczone w destruktorze, wycieknie) - patrz RAII, o którym mowa którego Mikołaj, oraz dokumentacja dla boost :: scoped_ptr lub ten przykład użycia boost :: mutex :: scoped_lock .

2. spójność programu: specyfikacje C ++ stwierdzają, że nigdy nie należy rzucać wyjątku, zanim nie zostanie obsłużony żaden istniejący wyjątek. Oznacza to, że proces rozwijania stosu nigdy nie powinien generować wyjątku (albo użyj tylko kodu, który gwarantuje, że nie wrzuci on destruktorów, albo otacza wszystko w destruktorach za pomocą try {i } catch(...) {}).

Jeśli jakikolwiek destruktor zgłasza wyjątek podczas odwijania stosu, trafisz do krainy nieokreślonego zachowania, które może spowodować nieoczekiwane zakończenie działania twojego programu (najczęstsze zachowanie) lub zakończenie wszechświata (teoretycznie możliwe, ale nie zostało to jeszcze zaobserwowane w praktyce).

W ogólnym sensie „odwijanie” stosu jest prawie synonimem końca wywołania funkcji i późniejszego wyskakiwania stosu.

Jednak, szczególnie w przypadku C ++, odwijanie stosu ma związek z tym, jak C ++ wywołuje destruktory dla obiektów przydzielonych od początku dowolnego bloku kodu. Obiekty utworzone w bloku są zwalniane w odwrotnej kolejności do ich alokacji.

Odwijanie stosu jest głównie koncepcją C ++, która zajmuje się tym, w jaki sposób obiekty przydzielone do stosu są niszczone po wyjściu z jego zakresu (normalnie lub w drodze wyjątku).

Załóżmy, że masz ten fragment kodu:

void hw() {
    string hello("Hello, ");
    string world("world!\n");
    cout << hello << world;
} // at this point, "world" is destroyed, followed by "hello"

Nie wiem, czy to przeczytałeś, ale artykuł Wikipedii na temat stosu wywołań zawiera dobre wyjaśnienie.

Odwijanie:

Powrót z wywoływanej funkcji spowoduje usunięcie górnej ramki ze stosu, być może pozostawiając wartość zwracaną. Bardziej ogólny akt usuwania jednej lub więcej ramek ze stosu w celu wznowienia wykonywania w innym miejscu programu nazywa się odwijaniem stosu i musi zostać wykonany, 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, dopóki nie zostanie znaleziony moduł obsługi przygotowany do obsługi (przechwycenia) typu zgłoszonego wyjątku.

Niektóre języki mają inne struktury kontrolne, które wymagają ogólnego odwijania. Pascal pozwala globalnej instrukcji goto na przeniesienie kontroli z zagnieżdżonej funkcji do wcześniej wywołanej funkcji zewnętrznej. Ta operacja wymaga rozwinięcia stosu, usuwając tyle ramek stosu, ile potrzeba, aby przywrócić właściwy kontekst i przekazać kontrolę do instrukcji docelowej w otaczającej funkcji zewnętrznej. Podobnie C ma funkcje setjmp i longjmp, które działają jako nielokalne gotos. Common Lisp pozwala kontrolować, co dzieje się, gdy stos jest rozwijany za pomocą specjalnego operatora odwijania-ochrony.

Podczas stosowania kontynuacji stos jest (logicznie) rozwijany, a następnie przewijany ze stosem kontynuacji. To nie jedyny sposób na wdrożenie kontynuacji; na przykład, używając wielu jawnych stosów, zastosowanie kontynuacji może po prostu aktywować jej stos i wyznaczyć wartość, która ma zostać przekazana. Język programowania Schematu pozwala na wykonanie dowolnych operacji w określonych punktach podczas „odwijania” lub „przewijania” stosu sterowania, gdy wywoływana jest kontynuacja.

Inspekcja [edycja]

Przeczytałem post na blogu, który pomógł mi zrozumieć.

Co to jest rozwijanie stosu?

W każdym języku obsługującym funkcje rekurencyjne (tj. Prawie wszystko oprócz Fortran 77 i Brainf * ck) środowisko wykonawcze języka przechowuje stos aktualnie wykonywanych funkcji. Odwijanie stosu jest sposobem na sprawdzenie i ewentualnie modyfikację tego stosu.

Dlaczego chcesz to zrobić?

Odpowiedź może wydawać się oczywista, ale istnieje kilka powiązanych, ale subtelnie różnych sytuacji, w których odwijanie jest przydatne lub konieczne:

1. Jako mechanizm kontroli przepływu środowiska wykonawczego (wyjątki C ++, C longjmp () itp.).
2. W debuggerze, aby pokazać użytkownikowi stos.
3. W profilerze, aby pobrać próbkę stosu.
4. Z samego programu (jak z programu obsługi awarii, aby wyświetlić stos).

Mają one nieco inne wymagania. Niektóre z nich mają kluczowe znaczenie dla wydajności, inne nie. Niektóre wymagają zdolności do rekonstrukcji rejestrów z zewnętrznej ramki, niektóre nie. Ale zajmiemy się tym za chwilę.

Pełny post można znaleźć tutaj .

Wszyscy mówili o obsłudze wyjątków w C ++. Myślę jednak, że istnieje inne skojarzenie z rozwijaniem stosu, które jest związane z debugowaniem. Debuger musi odwijać stos, ilekroć ma przejść do klatki poprzedzającej bieżącą. Jest to jednak rodzaj wirtualnego odwijania, ponieważ musi on przewinąć do tyłu, gdy wróci do bieżącej klatki. Przykładem tego mogą być polecenia góra / dół / bt w gdb.

IMO, podany poniżej schemat w tym artykule pięknie wyjaśnia efekt odwijania stosu na trasie następnej instrukcji (wykonywanej po zgłoszeniu wyjątku, który nie jest wykrywany):

Na zdjęciu:

• Pierwszym z nich jest normalne wykonanie połączenia (bez zgłaszanego wyjątku).
• Dolny jeden, gdy zostanie zgłoszony wyjątek.

W drugim przypadku, gdy wystąpi wyjątek, stos wywołań funkcji jest liniowo przeszukiwany pod kątem procedury obsługi wyjątku. Wyszukiwanie kończy się na funkcji z obsługą wyjątków, tj. main()Z załączającym try-catchblokiem, ale nie przed usunięciem wszystkich pozycji przed nią ze stosu wywołań funkcji.

Środowisko wykonawcze C ++ niszczy wszystkie zmienne automatyczne utworzone między rzutami i przechwytywaniem. W tym prostym przykładzie poniżej f1 () wyrzuca i chwyta main (), pomiędzy obiektami typu B i A są tworzone na stosie w tej kolejności. Kiedy rzuca f1 (), wywoływane są destruktory B i A.

#include <iostream>
using namespace std;

class A
{
    public:
       ~A() { cout << "A's dtor" << endl; }
};

class B
{
    public:
       ~B() { cout << "B's dtor" << endl; }
};

void f1()
{
    B b;
    throw (100);
}

void f()
{
    A a;
    f1();
}

int main()
{
    try
    {
        f();
    }
    catch (int num)
    {
        cout << "Caught exception: " << num << endl;
    }

    return 0;
}

Wyjście tego programu będzie

B's dtor
A's dtor

Wynika to z tego, że wygląda stos wywołań programu, gdy rzuca f1 ()

f1()
f()
main()

Tak więc, kiedy pojawia się f1 (), zmienna automatyczna b ulega zniszczeniu, a następnie, gdy pojawia się f (), zmienna automatyczna a ulega zniszczeniu.

Mam nadzieję, że to pomoże, szczęśliwego kodowania!

Gdy zgłoszony zostanie wyjątek i kontrola zostanie przekazana z bloku try do modułu obsługi, środowisko wykonawcze C ++ wywołuje destruktory dla wszystkich automatycznych obiektów zbudowanych od początku bloku try. Ten proces nazywa się rozwijaniem stosu. Automatyczne obiekty są niszczone w odwrotnej kolejności do ich budowy. (Obiekty automatyczne to obiekty lokalne, które zostały zadeklarowane jako automatyczne lub zarejestrowane, albo nie zostały zadeklarowane jako statyczne lub zewnętrzne. Obiekt automatyczny x jest usuwany za każdym razem, gdy program wychodzi z bloku, w którym deklarowane jest x.)

Jeśli podczas budowy obiektu składającego się z podobiektów lub elementów tablicy zostanie zgłoszony wyjątek, wywoływacze są wywoływane tylko dla tych podobiektów lub elementów tablicy pomyślnie zbudowanych przed zgłoszeniem wyjątku. Destruktor dla lokalnego obiektu statycznego zostanie wywołany tylko wtedy, gdy obiekt został pomyślnie skonstruowany.

W stosie Java odwijanie lub rozwijanie nie jest bardzo ważne (w przypadku śmieci). W wielu artykułach dotyczących obsługi wyjątków widziałem tę koncepcję (rozwijanie stosów), w szczególności pisarze zajmowali się obsługą wyjątków w C lub C ++. z try catchblokami nie powinniśmy zapominać: wolny stos od wszystkich obiektów po lokalnych blokach .