Переполнение стека
В программном обеспечении переполнение стека (англ. stack overflow) возникает, когда в стеке вызовов хранится больше информации, чем он может вместить. Обычно ёмкость стека задаётся при старте программы/потока. Когда указатель стека выходит за границы, программа аварийно завершает работу.[1]
Эта ошибка случается по трём причинам.[2]
Бесконечная рекурсия
Простейший пример бесконечной рекурсии на Си:
int foo() {
return foo();
}
Функция будет вызывать сама себя, расходуя пространство в стеке, пока стек не переполнится и не случится ошибка сегментации.[3]
Это рафинированный пример, и в реальном коде бесконечная рекурсия может появиться по двум причинам:
Ошибки в намеренной рекурсии
Рекурсия требует очень аккуратного программирования, не зря рекурсивные переборы любили в спортивном программировании в 1990-е, пока защищённый режим (а значит, большие массивы) и стандартные библиотеки алгоритмов вроде STL не расширили ассортимент задач, которые реально запрограммировать за несколько часов. Вот несколько ошибок.
Ошибка в условии окончания рекурсии:
int factorial (int n)
{
if (n == 1) // глубокая (4 млрд) рекурсия при n⩽0
return 1;
return n * factorial(n - 1);
}
Ошибка в рекурсивном спуске:
int factorial (int n)
{
if (n <= 1) // условие верное…
return 1;
return n * factorial(n); // …а спуск неверный, надо (n - 1)
}
Многие компиляторы делают оптимизацию, именуемую «хвостовая рекурсия». Рекурсия, находящаяся в конце функции, превращается в цикл и не расходует стека[4]. Если такая оптимизация сработает, вместо переполнения стека будет зацикливание.
Программист написал рекурсию, не осознавая того
Программист может написать рекурсию и ненамеренно — например, когда одну и ту же функциональность выполняют несколько перегруженных функций, и одна вызывает другую.
int Obj::getData(int index, bool& isChangeable)
{
isChangeable = true;
return getData(index);
}
int Obj::getData(int index)
{
bool noMatter;
return getData(index, noMatter);
}
См. также Порочный круг, Сепульки.
Другой вариант — программист взял не ту перегрузку.
int Obj::getData(int index, bool& isChangeable) { ... }
int Obj::getData(int index)
{
return getData(index); // случайно вызвал себя же
}
В интерфейсных фреймворках наподобие Qt и VCL рекурсия может случиться, если в обработчике, например, изменения поля программист сам же это поле и изменит.
Очень глубокая рекурсия
Уничтожить односвязный список можно таким кодом:
void destroyList(struct Item* it)
{
if (it == NULL)
return;
destroyList(it->next);
free(it);
}
Этот алгоритм, если список не испорчен, теоретически выполнится за конечное время, затребовав при этом O(n) стека. Разумеется, при длинном списке программа откажет. Возможные решения:
- Найти нерекурсивный алгоритм (работает в данном примере).
- Перенести рекурсию из аппаратного стека в динамически выделяемый (например, при обходе разного рода сетей[5]).
- Если рекурсия зашла глубоко, применять другой метод. Например, быстрая сортировка — чрезвычайно эффективный метод сортировки, который в крайних случаях может задействовать немалый объём стека. Поэтому реализации сортировки в языках программирования ограничивают глубину рекурсии, а если «упёрлись» в предел, используют более медленные методы наподобие пирамидальной. Так работает, например, Introsort.
Большие переменные в стеке
Третья большая причина переполнения стека — одноразовое выделение огромного количества памяти крупными локальными переменными. Многие авторы рекомендуют выделять память, превышающую несколько килобайт, в «куче», а не на стеке.[6]
Пример на Си:
int foo() {
double x[1000000];
}
Массив занимает 8 мегабайт памяти; если в стеке нет такого количества памяти, случится переполнение.
Всё, что уменьшает эффективный размер стека, увеличивает риск переполнения. Потоки обычно берут стека меньше, чем основная программа — поэтому программа может работать в однопоточном режиме и отказывать в многопоточном. Работающие в режиме ядра подпрограммы часто пользуются чужим стеком, поэтому при программировании в режиме ядра стараются не применять рекурсию и большие локальные переменные.[7][8]
См. также
Примечания
- ↑ Burley, James Craig Using and Porting GNU Fortran (1 июня 1991). Дата обращения: 30 марта 2012. Архивировано из оригинала 5 октября 2012 года.
- ↑ Danny, Kalev Understanding Stack Overflow (5 сентября 2000). Дата обращения: 30 марта 2012. Архивировано 27 сентября 2020 года.
- ↑ What is the difference between a segmentation fault and a stack overflow? Архивная копия от 9 марта 2012 на Wayback Machine at StackOverflow
- ↑ An Introduction to Scheme and its Implementation (19 февраля 1997). Дата обращения: 30 марта 2012. Архивировано из оригинала 23 августа 2000 года.
- ↑ Пример ошибки (Архивная копия от 13 ноября 2020 на Wayback Machine) в poly2tri, известной библиотеке для построения ограниченной триангуляции Делоне многоугольника; ошибку исправили динамическим стеком STL.
- ↑ Feldman, Howard Modern Memory Management, Part 2 (23 ноября 2005). Дата обращения: 30 марта 2012. Архивировано 5 октября 2012 года.
- ↑ Kernel Programming Guide: Performance and Stability Tips . Apple Inc. (7 ноября 2006). Дата обращения: 30 сентября 2017. Архивировано 7 декабря 2008 года.
- ↑ Dunlap, Randy Linux Kernel Development: Getting Started (19 мая 2005). Дата обращения: 30 марта 2012. Архивировано из оригинала 5 октября 2012 года.