Jak działa przepełnienie stosu w C++?

Cześć!
Co zadeklarowane przeze mnie ląduje na stosie a co nie?

#include <bits/stdc++.h>

using namespace std;

const int MILION = 1e6;

void rec(int i){
    if (i == 0)
        return;
    int niecenzuralne_slowo = 420 * 2137;
    return rec(i-1);
}

int main(){
    int n[MILION * 3];                      // powoduje przepelnienie
    rec(MILION);                            // powoduje przepelnienie
    int a[MILION], b[MILION], c[MILION];    // nie powoduje przepelnienia
    vector<int> vec(MILION * 69);           // nie powoduje przepelnienia
    int m;
    return 0;
}

Ten stos jest w trakcie programu zwalniany? Mógłby ktoś napisać coś o tym, albo podesłać jakiś link bo nie rozumiem jak to działa.

Najprościej skompiluj z opcją produkcji asemblera i sam zobacz.

C++ jako standard nie definiuje tego.
To czy i w jakich okolicznościach następuje przepełnienie stosu, decyduje: platforma, kompilator i jego ustawienia.

Przykładowo twoja funkcja rec nic nie robi. Sprytny kompilator, z właściwymi ustawieniami optymalizacji po prostu usunie tą funkcję, albo zamieni rekursję na zwykłą pętlę i przepełnienia stosu nie będzie.

Tak samo kompilator widząc, że te twoje tablice nie są używane może je zignorować i znowu przepełnienia stosu nie będzie.

Przykład tutaj kompilator zostawił tylko std::vector resztę zignorował. rec wygenerował jako puste a i tak go nie używa.

A tutaj po dodaniu czegoś, by rec cokolwiek robiło, rekursja została zamieniona na pętlę i znowu przepełnienia stosu nie będzie.

A co gdy program np. zużywa 100MB pamięci, na pewno przepełniłby stos ale jednak nie powoduje błędu. Gdzie ta pamięc jest przechowywana?

Po pierwsze nie na pewno no bo rozmiar stosu sobie mozesz dostosowac a po drugie masz jeszcze sterte.

@Suchy702:
masz mniej więcej 3 typy przestrzeni na zmienne
1 - na stosie
2 - na heapie
3 - zmienne globalne

Kiedy jest alokacja na stosie? Jak robisz zmienne automatyczne, tzn np.

int main() {
    int tab[200];
}

wtedy, (zakładając, że nie będzie to wyoptymalizowane), tablica tab wyląduje na stosie, i zajmie sizeof(int)*200 bajtów.

Zazwyczaj też, aby umożliwić return w funkcjach, kompilator przy wejściu do funkcji odkłada na stos adres powrotu. Efektywnie to jest coś w stylu

void g() {
// cośtam
    void* x;
    void** adres_powrotu = &x - 1;
    goto *adres_powrotu;
}
void f() {
    void* adres_powrotu = &ret_here; // wiem, że to składniowo nie jest poprawne
    g();
    ret_here:
}

wtedy nieskończona rekurecja (czy też odpowiednio głęboka po prostu), może spowodować (słynne) stack overflow - każde wywołanie zwiększa wielkość stosu o ileś bajtów - dlatego też rozmiar stosu jest tak rygorystycznie ograniczany - bardzo prosto by było zrobić błędnie działające programy które przypadkiem są nieefektywne.

Alokacja na heapie:
wszystko co używa malloc/new, np. new int[2137], ale też np. wektor, czy wszystkie chyba kontenery STL z wyjątkiem std::array. Możesz się na tym poznać, patrząc, że na typowej implementacji, sizeof(vector) == 24. Jest to rozmiar stały, niezależnie od ilości elementów. Implementowane jest to tak, że siedzi tam w środku wskaźnik na tablicę zaalokowaną za pomocą new.

Zmienne globalne - one mają jeszcze osobne miejsce w pamięci - informacja o zmiennych globalnych jest zawarta bezpośrednio w pliku wykonywalnym (a jeśli np. jest to nieinicjalizowana zmienna globalna, to szczęśliwie jest tam umieszczana tylko informacja o tym jak dużo tych zer trzeba umieścić). Takie zmienne nie mogą rosnąć w sposób niekontrolowany, więc też ograniczenia na ich rozmiar są znacznie bardziej zrelaksowane.

Trochę szczegółowiej mówi o tym Gynvael na jednym ze streamów, o tutaj:

"Jak działa przepełnienie stosu w C++?"
obok kompetentnych odpowiedzi Kolegów, podkreślę mocno jedno:

@Suchy702
Odmiennie niż w Javie, Pythonie, C# (wymień jeszcze kilka języków - natychmiast leci wyrazisty wyjątek z opisem co, jak i z jakiego miejsca), to naruszenia zasad, granic w C/C++ przejawiają się odmiennie:
nie ma jakiegoś jednego modelu zachowania. Tu wszystko jest UB Undefined Behaviour, czyli np pewne wystąpienia błędów mogą nie dawać widocznych przejawów, mogą dawać efek z opóźnieniem nawet minut (gdy ulegają zniszczeniu jakieś struktury systemowe), uszkadzać jakieś dane, problem być może się ujawni przy ich użyciu.
Podobieństwa mogą mieć języki un-safe generujące kod maszynowy, Delphi (choć tam np granice tablic mogą być bronione przez kompilator)

Oczywiście, w rękach doświadczonego programisty mgiełka UB nabiera częściowej powtarzalności, jak się widziało jedno, drugie, trzecie przejechanie granic

Widzę @Suchy702 że temat pytania jest odmienny od treści, bo w teści pytasz już nie przepełnienie, ale o realia zmiennych różnych -> modeli pamięci

Suchy702 napisał(a):

void rec(int i){
    if (i == 0)
        return;
    int niecenzuralne_slowo = 420 * 2137;
    return rec(i-1);

Zazwyczaj każde wywołanie funkcji odkłada na stos adres powrotu (czyli wskaźnik na kod zaraz za wywołaniem funkcji) dzięki czemu procesor wie gdzie wrócić w momencie wyjścia z funkcji. Szczegóły zależą od platformy, kompilatora, jego ustawień, ale generalnie musimy pamiętać że zbyt głębokie wywołanie (rekurencyjne bądź nie) może spowodować przepełnienie stosu.

int main(){
    int n[MILION * 3];                      // powoduje przepelnienie

To idzie na stos.

    rec(MILION);                            // powoduje przepelnienie

Z powodu o którym napisałem wyżej - odkładasz na stos milion razy adres powrotu.

int a[MILION], b[MILION], c[MILION];    // nie powoduje przepelnienia

To też idzie na stos.

vector<int> vec(MILION * 69);           // nie powoduje przepelnienia

Tu na stos idzie tylko niewielki obiekt typu vector<int>. Same dane są przechowywane na stercie.

int m;

To też idzie na stos (teoretycznie; kompilator taką zmienną zapewne wyoptymalizuje).

Ten stos jest w trakcie programu zwalniany? Mógłby ktoś napisać coś o tym, albo podesłać jakiś link bo nie rozumiem jak to działa.

Wyjście zmiennej z zakresu, czyli wyjście z bloku { } w którym była zmienna zadeklarowana zwalnia fragment stosu zaalokowany w tym bloku.