Войти
В программном обеспечении переполнение стека происходит, если указатель стека вызовов превышает границу стека . Стек вызовов может состоять из ограниченного количества адресного пространства , часто определяется в начале программы. Размер стека вызовов зависит от многих факторов, включая язык программирования, архитектуру машины, многопоточность и объем доступной памяти. Когда программа пытается использовать больше места, чем доступно файл в стеке вызовов (то есть, когда он пытается получить доступ к памяти за пределами стека вызовов, что по сути является переполнением буфера ), стек считается переполненным, что обычно приводит к сбою программы. 108>Содержание
Наиболее частой причиной переполнения стека является чрезмерно глубокая или бесконечная рекурсия, при которой функция вызывает себя столько раз, что пространство, необходимое для хранения переменных и информации, связанной с каждый вызов больше, чем может поместиться в стеке.
Пример бесконечной рекурсии в C.
int foo () {return foo (); }Функция foo, когда она вызывается, продолжает вызывать себя, каждый раз выделяя дополнительное пространство в стеке, пока стек не переполнится, что приведет к ошибке сегментации . Однако некоторые компиляторы реализуют оптимизацию хвостового вызова, позволяющую бесконечную рекурсию определенного вида - хвостовую рекурсию - происходить без переполнения стека. Это работает, потому что вызовы хвостовой рекурсии не занимают дополнительного места в стеке.
Некоторые параметры компилятора C эффективно включают оптимизацию хвостового вызова ; например, компиляция указанной выше простой программы с использованием gcc с -O1приведет к ошибке сегментации, но не при использовании -O2или -O3, поскольку эти уровни оптимизации подразумевают параметр компилятора -foptimize-sibling-calls. Другие языки, такие как Схема, требуют, чтобы все реализации включали хвостовую рекурсию как часть языкового стандарта.
Рекурсивная функция, завершающаяся теоретически но вызывает переполнение буфера стека вызовов на практике, это может быть исправлено путем преобразования рекурсии в цикл и сохранения аргументов функции в явном стеке (а не неявном использовании стека вызовов). Это всегда возможно, потому что класс примитивных рекурсивных функций эквивалентен классу вычислимых функций LOOP. Рассмотрим этот пример в C ++ -подобном псевдокоде:
void function (argument) {if (condition) function (argument.next); } | stack.push (аргумент); а (! stack.empty ()) {аргумент = stack.pop (); if (условие) stack.push (argument.next); } |
Примитивная рекурсивная функция, подобная той, что находится слева, всегда может быть преобразована в цикл, как на правой стороне.
Функция, подобная приведенному выше примеру слева, не будет проблемой в среде, поддерживающей оптимизацию хвостового вызова ; однако по-прежнему можно создать рекурсивную функцию, которая может привести к переполнению стека на этих языках. Рассмотрим приведенный ниже пример двух простых целочисленных функций возведения в степень.
int pow (int base, int exp) {если (exp>0) return base * pow (base, exp - 1); иначе вернуть 1; } | int pow (int base, int exp) {return pow_accum (base, exp, 1);); } int pow_accum (int base, int exp, int аккумулятор) {если (exp>0) return pow_accum (base, exp - 1, аккумулятор * base); иначе вернуть аккумулятор; } |
Обе функции pow (base, exp), приведенные выше, вычисляют эквивалентный результат, однако функция слева склонна вызывать переполнение стека, поскольку оптимизация хвостового вызова для этой функции невозможна. Во время выполнения стек для этих функций будет выглядеть так:
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 |
Обратите внимание, что Функция слева должна хранить в своем стеке expколичество целых чисел, которое будет умножено, когда рекурсия завершится и функция вернет 1. Напротив, функция справа должна хранить только 3 целых числа в любой момент, и вычисляет промежуточный результат, который передается его следующему вызову. Поскольку никакая другая информация, кроме текущего вызова функции, не должна храниться, оптимизатор хвостовой рекурсии может «отбрасывать» предыдущие кадры стека, исключая возможность переполнения стека.
Другая основная причина переполнения стека возникает из-за попытки выделить в стеке больше памяти, чем может поместиться, например, путем создания слишком больших переменных локального массива. По этой причине некоторые авторы рекомендуют выделять массивы размером более нескольких килобайт динамически, а не в качестве локальной переменной.
Пример очень большой переменной стека в C :
int foo () {двойной x [1048576]; }В реализации C с 8-байтовыми числами с плавающей запятой двойной точности объявленный массив потребляет 8 мегабайт данных; если это больше памяти, чем доступно в стеке (как установлено параметрами создания потока или ограничениями операционной системы), произойдет переполнение стека.
Переполнение стека ухудшается из-за всего, что уменьшает эффективный размер стека данной программы. Например, одна и та же программа, запущенная без нескольких потоков, может работать нормально, но как только будет включена многопоточность, программа выйдет из строя. Это связано с тем, что большинство программ с потоками имеют меньше места в стеке на поток, чем программа без поддержки потоков. Поскольку ядра обычно многопоточны, людям, плохо знакомым с разработкой ядра, обычно не рекомендуется использовать рекурсивные алгоритмы или большие стековые буферы.
