В программном обеспечении переполнение стека происходит, если указатель стека вызовов превышает границу стека . Стек вызовов может состоять из ограниченного объема адресного пространства , часто определяемого в начале программы. Размер стека вызовов зависит от многих факторов, включая язык программирования, архитектуру машины, многопоточность и объем доступной памяти. Когда программа пытается использовать больше места, чем доступно в стеке вызовов (то есть, когда она пытается получить доступ к памяти за пределами стека вызовов, что по сути является переполнением буфера ), говорят, что стек переполняется , что обычно приводит к ошибке сбой программы . [1]
Наиболее распространенной причиной переполнения стека является чрезмерно глубокая или бесконечная рекурсия, при которой функция вызывает себя так много раз, что пространство, необходимое для хранения переменных и информации, связанной с каждым вызовом, превышает размер стека. [2]
Пример бесконечной рекурсии в C.
int foo () { return foo (); } Функция foo при ее вызове продолжает вызывать саму себя, каждый раз выделяя дополнительное пространство в стеке, пока стек не переполнится, что приведет к ошибке сегментации . [2] Однако некоторые компиляторы реализуют оптимизацию хвостовых вызовов , позволяя бесконечной рекурсии определенного вида — хвостовой рекурсии — происходить без переполнения стека. Это работает, поскольку вызовы хвостовой рекурсии не занимают дополнительного места в стеке. [3]
Некоторые параметры компилятора C позволяют эффективно оптимизировать хвостовой вызов ; например, компиляция приведенной выше простой программы с использованием gcc приведет-O1 к ошибке сегментации, но не при использовании -O2или -O3, поскольку эти уровни оптимизации подразумевают -foptimize-sibling-callsопцию компилятора. [4] Другие языки, такие как Scheme , требуют, чтобы все реализации включали хвостовую рекурсию как часть стандарта языка. [5]
Рекурсивную функцию, которая теоретически завершается, но на практике вызывает переполнение буфера стека вызовов, можно исправить, превратив рекурсию в цикл и сохранив аргументы функции в явном стеке (вместо неявного использования стека вызовов). Это всегда возможно, поскольку класс примитивно-рекурсивных функций эквивалентен классу LOOP-вычислимых функций. Рассмотрим этот пример в псевдокоде, подобном C++ :
Примитивную рекурсивную функцию, подобную той, что изображена слева, всегда можно преобразовать в цикл, подобный изображенному в правой части.
Функция, подобная приведенному выше примеру слева, не будет проблемой в среде, поддерживающей оптимизацию хвостового вызова ; однако в этих языках все еще возможно создать рекурсивную функцию, которая может привести к переполнению стека. Рассмотрим приведенный ниже пример двух простых целочисленных функций возведения в степень.
Обе pow(base, exp)приведенные выше функции вычисляют эквивалентный результат, однако функция слева склонна вызывать переполнение стека, поскольку для этой функции невозможна оптимизация хвостового вызова. Во время выполнения стек этих функций будет выглядеть так:
Обратите внимание, что функция слева должна хранить в своем стеке expчисло целых чисел, которое будет умножено, когда рекурсия завершится и функция вернет 1. Напротив, функция справа должна хранить только 3 целых числа в любой момент времени и вычисляет промежуточный результат, который передается при следующем вызове. Поскольку никакая другая информация, кроме текущего вызова функции, храниться не должна, оптимизатор хвостовой рекурсии может «отбросить» предыдущие кадры стека, исключая возможность переполнения стека.
Другая основная причина переполнения стека возникает в результате попытки выделить в стеке больше памяти, чем поместится, например, путем создания слишком больших переменных локального массива. По этой причине некоторые авторы рекомендуют выделять массивы размером более нескольких килобайт динамически, а не в виде локальной переменной. [6]
Пример очень большой переменной стека в C :
int foo () { двойной х [ 1048576 ]; } В реализации C с 8-байтовыми числами двойной точности объявленный массив потребляет 8 мегабайт данных; если это больше памяти, чем доступно в стеке (как установлено параметрами создания потока или ограничениями операционной системы), произойдет переполнение стека.
Переполнение стека усугубляется всем, что уменьшает эффективный размер стека данной программы. Например, одна и та же программа, запущенная без нескольких потоков, может работать нормально, но как только многопоточность будет включена, программа выйдет из строя. Это связано с тем, что большинство программ с потоками имеют меньше места в стеке на поток, чем программы без поддержки потоков. Поскольку ядра, как правило, являются многопоточными, людям, плохо знакомым с разработкой ядра , обычно не рекомендуется использовать рекурсивные алгоритмы или большие буферы стека. [7]