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

Jak działa przepełnienie stosu w C++?
S7
  • Rejestracja:prawie 5 lat
  • Ostatnio:13 dni
  • Postów:354
0

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

Kopiuj
#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.


Competitive Google searcher
_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:2 miesiące
0

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


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
MarekR22
Moderator C/C++
  • Rejestracja:około 17 lat
  • Ostatnio:2 minuty
8

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.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 5x, ostatnio: MarekR22
_13th_Dragon
Zignorował? A co to takiego mov edi, 276000000
MarekR22
69 * 4 = 276 czyli to jest rozmiar potrzebny dla wektora potem masz wywołanie new int[].
stivens
https://godbolt.org/z/fb43KjTj1 a tutaj juz overflow na wywolaniach rekurencyjnych :)
S7
  • Rejestracja:prawie 5 lat
  • Ostatnio:13 dni
  • Postów:354
0

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?


Competitive Google searcher
edytowany 1x, ostatnio: Suchy702
stivens
  • Rejestracja:ponad 8 lat
  • Ostatnio:około 9 godzin
2

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


λλλ
Zobacz pozostałe 9 komentarzy
stivens
No i pojawia sie cos takiego jak garbage collector
S7
on dba o new i delete?
stivens
Mozesz myslec o tym tak, ze wszystko jest implicite new a delete bedzie wywolane jak cokolwiek przestanie wskazywac na dany obiekt EDIT: w sensie jak nic juz nie bedzie wskazywac na niego*. Tylko to dziala niederministycznie. Tj. nieosiagalny obiekt moze sobie zyc na stercie jeszcze przez jakis czas zanim zostanie wyczyszczony.
stivens
A dobra. Python uzywa reference countingu. No to moze jednak nie tak do konca niederministycznie :)
enedil
  • Rejestracja:ponad 11 lat
  • Ostatnio:2 dni
  • Postów:1027
5

@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.

Kopiuj
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

Kopiuj
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:

AK
  • Rejestracja:ponad 6 lat
  • Ostatnio:9 dni
  • Postów:3561
0

"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


Bo C to najlepszy język, każdy uczeń ci to powie
edytowany 1x, ostatnio: AnyKtokolwiek
stivens
Natura przestrzeni wirtualnej jest chyba taka, ze dostep do pamieci za stosem zawsze konczy sie SIGSEGV
stivens
Chyba ze ktos tam na sile cos zmapuje
AK
  • Rejestracja:ponad 6 lat
  • Ostatnio:9 dni
  • Postów:3561
0

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


Bo C to najlepszy język, każdy uczeń ci to powie
S7
Nie mogę już zmienić tytułu
Azarien
  • Rejestracja:ponad 21 lat
  • Ostatnio:5 minut
2
Suchy702 napisał(a):
Kopiuj
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.

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

To idzie na stos.

Kopiuj
    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.

edytowany 3x, ostatnio: Azarien
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)