Przepełnienie stosu
Przepełnienie stosu (ang. stack overflow) – rodzaj błędu w oprogramowaniu komputerowym, który występuje, gdy rozmiar stosu przekroczy ilość pamięci zarezerwowanej dla niego. Maksymalny rozmiar stosu jest zwykle ograniczony i ustalany na początku działania programu i zależy od języka programowania, architektury systemu, ustawionego trybu pracy i ilości dostępnej pamięci, najczęściej jest rzędu 1 MB (w systemach 16-bitowych maksymalna wielkość stosu była ograniczona do 64 kB). W wielu językach programowania można określić początkową wielkość stosu, na jakim będzie pracował program. Skutkiem przepełnienia stosu, gdy nie przygotowano programu na tę okoliczność jest nagłe przerwanie jego działania.
Do przepełnienia stosu dochodzi zazwyczaj, gdy:
- wywoływanych jest kaskadowo zbyt wiele funkcji (każda funkcja wywołuje kolejną);
- obszerne parametry do funkcji są przekazywane bezpośrednio (np. tablice jako wartości), a nie przez wskaźniki;
- w funkcji deklarowane są zmienne lokalne o dużej objętości (np. tablice wielowymiarowe).
Najczęstszą przyczyną przepełniania stosu jest nieskończona rekurencja. Gdy przeprowadzona jest optymalizacja rekurencji ogonowej nieskończona rekurencja może zaistnieć bez przepełnienia stosu, bo kolejne wywołania tej funkcji nie zajmują dodatkowego miejsca na stosie – co w rezultacie prowadzi do pętli nieskończonej. Gdy język nie wspiera rekurencji ogonowej można stosować trampolinę, aby nie zużywać stosu i nie doprowadzić do przepełnienia stosu[1].
Przykłady w C++
[edytuj | edytuj kod]- Nieskończona rekurencja
void foo()
{
bar();
}
void bar()
{
foo();
}
foo()
wywołuje bar()
, który z kolei wywołuje foo()
i tak dalej. W końcu dochodzi do przepełnienia stosu.
- Alokacja dużej tablicy na stosie
int main()
{
int n[10000000]; // tablica jest zbyt duża
int j =0; // j nie mieści się już na stosie, błąd
}
Przykład w Visual Basic
[edytuj | edytuj kod]Sub bar()
foo
End Sub
Sub foo()
bar
End Sub
Tutaj najpierw wywoływana jest funkcja foo(), po której bezpośrednio jest wykonywana funkcja bar(). Dochodzi do wzajemnej aktywacji wcześniej wspomnianych funkcji kończącej się brakiem miejsca w stosie dla którejś funkcji.
Zobacz też
[edytuj | edytuj kod]Przypisy
[edytuj | edytuj kod]- ↑ Jakub T. Jankiewicz: Trampolina czyli rekurencja bez stosu. Głównie JavaScript, 2018-01-09. [dostęp 2021-11-14].