В программном обеспечении переполнение стека происходит, если указатель стека вызовов превышает границу стека . Стек вызовов может состоять из ограниченного количества адресного пространства , часто определяемого в начале программы. Размер стека вызовов зависит от многих факторов, включая язык программирования, архитектуру машины, многопоточность и объем доступной памяти. Когда программа пытается использовать больше места, чем доступно в стеке вызовов (то есть, когда она пытается получить доступ к памяти за пределами границ стека вызовов, что по сути является переполнением буфера ), говорят, что стек переполняется , что обычно приводит к сбою программы . [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]