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++

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

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ż

• przepełnienie bufora

Przypisy