Przepełnienie stosu
W informatyce przepełnienie stosu występuje, gdy na stosie potrzeba zbyt dużej ilości pamięci .
W wielu językach programowania stos wywołań zawiera ograniczoną ilość pamięci, zwykle ustalaną podczas uruchamiania programu. Wielkość stosu zależy od wielu czynników, w tym języka programowania, architektury maszyny, zastosowania wielowątkowości oraz dostępności pamięci w systemie. Gdy w stosie jest używane zbyt dużo pamięci , mówi się, że występuje przepełnienie i następuje awaria programu [1] . Ta klasa błędów jest zwykle spowodowana jednym z dwóch typów błędów programistycznych [2] : nieskończoną rekurencją i użyciem bardzo dużych zmiennych stosu.
Nieskończona rekurencja
Najczęstszą przyczyną przepełnienia stosu jest rekursja z nadmierną lub nieskończoną głębokością.
Języki, które implementują technikę rekurencji ogonowej , takie jak język Scheme , umożliwiają konkretną nieskończoną rekurencję, która może być wykonywana bez przepełnienia stosu. Dzieje się tak, ponieważ wywołania korzystające z rekurencji końcowej nie wymagają dodatkowego miejsca na stosie [3] .
Bardzo duże zmienne stosu
Inną główną przyczyną przepełnienia stosu jest próba przydzielenia większej ilości pamięci niż jest dostępne na stosie. Dzieje się tak, gdy tworzysz bardzo dużą tablicę zmiennych lokalnych . Z tego powodu tablice większe niż kilka kilobajtów powinny być przydzielane dynamicznie , a nie przydzielane jako zmienne lokalne [4] .
Przyczyny, które mogą zmniejszyć dostępny rozmiar stosu, a tym samym zwiększyć prawdopodobieństwo przepełnienia stosu
Przepełnienia stosu są potęgowane przez wszystko, co zmniejsza efektywny rozmiar stosu programu .
Na przykład program działający jako pojedynczy wątek może działać poprawnie, ale jeśli ten sam program działa z wieloma wątkami , następuje awaria programu , ponieważ wiele programów korzystających z wątków ma mniejszy stos dostępny dla każdego pojedynczego wątku niż program. nie używa wątków.
Podobnie osobom badającym rozwój jądra odradza się stosowanie algorytmów rekurencyjnych i bardzo dużych buforów w stosie [5] [6] .
Przykłady w języku C / C++
Nieskończona rekurencja z jedną funkcją
nieważne f () {
f ();
}
int główna ( nieważne ) {
f ();
zwróć 0 ;
}
Ten fragment kodu wywołuje funkcję f() , a funkcja f()z kolei wywołuje samą siebie, generując w ten sposób nieskończoną rekurencję.
Nieskończona rekurencja z dwiema funkcjami
nieważne f ( nieważne ); nieważne g ( nieważne );
int główna ( nieważne ) {
f ();
zwróć 0 ;
}
nieważne f ( nieważne ) {
g ();
}
nieważne g ( nieważne ) {
f (); }
Funkcja f()i funkcja g()wywołują się nawzajem w sposób ciągły, aż do wystąpienia przepełnienia stosu.
Zbyt duża zmienna w stosie
int główna ( nieważne ) {
podwójne n [ 10000000 ]; zwróć 0 ;
}
Tablica zadeklarowana w tym fragmencie kodu wymaga więcej pamięci niż jest dostępne na stosie, co powoduje przepełnienie stosu.
Notatki
- ^ James Craig Burley, Używanie i przenoszenie GNU Fortran , na sunsite.ualberta.ca , 1 czerwca 1991 (archiwum z 5 października 2012) .
- ^ Kalev Danny, Understanding Stack Overflow , devx.com , 5 września 2000 r.
- ^ Wprowadzenie do schematu i jego realizacji , na federated.com , 19 lutego 1997 (archiwum z oryginału w dniu 10 sierpnia 2007) .
- ^ Howard Feldman, Nowoczesne zarządzanie pamięcią, część 2 , na onlamp.com , 23 listopada 2005. Pobrano 10 listopada 2009 (zarchiwizowane z 20 września 2012) .
- ^ Przewodnik programowania jądra: Wskazówki dotyczące wydajności i stabilności , na stronie developer.apple.com , Apple Inc. , 7 listopada 2006 (zarchiwizowane od oryginału z 7 grudnia 2008) .
- ^ Randy Dunlap, Linux Kernel Development: Getting Started ( PDF ), na xenotime.net , 19 maja 2005 (archiwum z 27 lutego 2012) .
