Przepełnienie stosu - Stack overflow
W oprogramowaniu przepełnienie stosu występuje, gdy wskaźnik stosu wywołań przekracza granicę stosu . Stos wywołań może składać się z ograniczonej ilości przestrzeni adresowej , często określanej na początku programu. Rozmiar stosu wywołań zależy od wielu czynników, w tym języka programowania, architektury maszyny, wielowątkowości i ilości dostępnej pamięci. Gdy program próbuje wykorzystać więcej miejsca niż jest dostępne na stosie wywołań (to znaczy, gdy próbuje uzyskać dostęp do pamięci poza granicami stosu wywołań, co jest zasadniczo przepełnieniem buforu ), mówi się, że stos przepełnia się , co zwykle skutkuje awaria programu.
Powoduje
Nieskończona rekurencja
Najczęstszą przyczyną przepełnienia stosu jest nadmiernie głęboka lub nieskończona rekurencja, w której funkcja wywołuje samą siebie tyle razy, że przestrzeń potrzebna do przechowywania zmiennych i informacji związanych z każdym wywołaniem jest większa niż może zmieścić się na stosie.
Przykład nieskończonej rekurencji w C .
int foo()
{
return foo();
}
Funkcja foo , gdy jest wywoływana, kontynuuje wywoływanie samej siebie, za każdym razem przydzielając dodatkowe miejsce na stosie, aż do przepełnienia stosu, co spowoduje błąd segmentacji . Jednak niektóre kompilatory implementują optymalizację wywołania ogona , umożliwiając nieskończoną rekurencję określonego rodzaju — rekurencję ogona — bez przepełnienia stosu. Działa to, ponieważ wywołania rekurencji ogonowej nie zajmują dodatkowego miejsca na stosie.
Niektóre opcje kompilatora C skutecznie umożliwią optymalizację wywołania końcowego ; na przykład kompilacja powyższego prostego programu przy użyciu gcc z -O1spowoduje błąd segmentacji, ale nie przy użyciu -O2lub -O3, ponieważ te poziomy optymalizacji implikują -foptimize-sibling-callsopcję kompilatora. Inne języki, takie jak Scheme , wymagają, aby wszystkie implementacje zawierały rekursję ogonową jako część standardu językowego.
Bardzo głęboka rekurencja
Funkcja rekurencyjna, która teoretycznie kończy się, ale w praktyce powoduje przepełnienie bufora stosu wywołań, można naprawić, przekształcając rekurencję w pętlę i przechowując argumenty funkcji w jawnym stosie (zamiast niejawnego użycia stosu wywołań). Jest to zawsze możliwe, ponieważ klasa prymitywnych funkcji rekurencyjnych jest równoważna klasie funkcji obliczalnych LOOP. Rozważmy ten przykład w pseudokodzie podobnym do C++ :
void function (argument)
{
if (condition)
function (argument.next);
}
|
stack.push(argument);
while (!stack.empty())
{
argument = stack.pop();
if (condition)
stack.push(argument.next);
}
|
Prymitywną funkcję rekurencyjną, taką jak ta po lewej stronie, zawsze można przekształcić w pętlę, jak po prawej stronie.
Funkcja taka jak w powyższym przykładzie po lewej stronie nie stanowiłaby problemu w środowisku obsługującym optymalizację wywołania końcowego ; jednak nadal można utworzyć funkcję rekurencyjną, która może spowodować przepełnienie stosu w tych językach. Rozważmy poniższy przykład dwóch prostych funkcji potęgowania liczb całkowitych.
int pow(int base, int exp) {
if (exp > 0)
return base * pow(base, exp - 1);
else
return 1;
}
|
int pow(int base, int exp) {
return pow_accum(base, exp, 1);
}
int pow_accum(int base, int exp, int accum) {
if (exp > 0)
return pow_accum(base, exp - 1, accum * base);
else
return accum;
}
|
Obie pow(base, exp)powyższe funkcje obliczają równoważny wynik, jednak ten po lewej stronie może powodować przepełnienie stosu, ponieważ optymalizacja wywołania końcowego nie jest możliwa dla tej funkcji. Podczas wykonywania stos dla tych funkcji będzie wyglądał tak:
pow(5, 4)
5 * pow(5, 3)
5 * (5 * pow(5, 2))
5 * (5 * (5 * pow(5, 1)))
5 * (5 * (5 * (5 * pow(5, 0))))
5 * (5 * (5 * (5 * 1)))
625
|
pow(5, 4)
pow_accum(5, 4, 1)
pow_accum(5, 3, 5)
pow_accum(5, 2, 25)
pow_accum(5, 1, 125)
pow_accum(5, 0, 625)
625
|
Zauważ, że funkcja po lewej musi przechowywać na stosie expliczbę liczb całkowitych, które zostaną pomnożone, gdy rekursja zakończy się i funkcja zwróci 1. W przeciwieństwie do tego, funkcja po prawej musi przechowywać tylko 3 liczby całkowite w dowolnym momencie i oblicza wynik pośredni, który jest przekazywany do kolejnego wywołania. Ponieważ żadne inne informacje poza bieżącym wywołaniem funkcji nie muszą być przechowywane, optymalizator rekurencji ogonowej może „porzucić” poprzednie ramki stosu, eliminując możliwość przepełnienia stosu.
Bardzo duże zmienne stosu
Inna główna przyczyna przepełnienia stosu wynika z próby przydzielenia większej ilości pamięci na stosie, niż się zmieści, na przykład przez utworzenie zbyt dużych lokalnych zmiennych tablicowych. Z tego powodu niektórzy autorzy zalecają, aby tablice większe niż kilka kilobajtów były przydzielane dynamicznie zamiast jako zmienna lokalna.
Przykład bardzo dużej zmiennej stosu w C :
int foo()
{
double x[1048576];
}
W implementacji języka C z 8-bajtowymi pływakami o podwójnej precyzji zadeklarowana tablica zużywa 8 megabajtów danych; jeśli jest to więcej pamięci niż jest dostępne na stosie (zgodnie z parametrami tworzenia wątków lub ograniczeniami systemu operacyjnego), nastąpi przepełnienie stosu.
Przepełnienie stosu jest pogarszane przez wszystko, co zmniejsza efektywny rozmiar stosu danego programu. Na przykład ten sam program uruchamiany bez wielu wątków może działać poprawnie, ale po włączeniu wielowątkowości program ulegnie awarii. Dzieje się tak, ponieważ większość programów z wątkami ma mniej miejsca na stosie na wątek niż program bez obsługi wątków. Ponieważ jądra są generalnie wielowątkowe, osoby początkujące w rozwoju jądra są zwykle zniechęcane do używania algorytmów rekurencyjnych lub dużych buforów stosu.