Когда стек действительно переполняется?

Question

Является ли бесконечная рекурсия единственным случаем или это может произойти по другим причинам? Разве размер стека не увеличивается так же, как и размер кучи?

Извините, если этот вопрос был задан ранее, буду признателен за ссылки на них, если это так.

Answer 1

Я не могу говорить для всех платформ, но, как это происходит, я просто потратил некоторое время на работу с файлами .exe Windows (я имею в виду, фактически изучая их двоичный формат - я знаю, в некотором смысле, все мы здесь работают с исполняемыми файлами;)). Готов поспорить, что большинство других платформ имеют аналогичные возможности, но я не знаком с ними сразу.

Часть самого формата файла включает в себя два значения, относящиеся к текущему обсуждению:

typedef struct _IMAGE_OPTIONAL_HEADER {
    ...
    DWORD   SizeOfStackReserve;
    DWORD   SizeOfStackCommit;
    ...
} IMAGE_OPTIONAL_HEADER32, *PIMAGE_OPTIONAL_HEADER32;

Из MSDN:

SizeOfStackReserve

Количество байтов, резервируемых для стек. Только память, указанная член SizeOfStackCommit является совершено во время загрузки; остальное сделал доступной одну страницу за раз пока этот резервный размер не будет достигнут.

SizeOfStackCommit

Количество байтов для фиксации для стек.

Другими словами, компоновщик определяет максимальный размер стека программы. Если вы достигнете максимального размера, вы переполнитесь - независимо от того, как вы достигли максимального размера. Вы можете написать простую программу, чтобы сделать это в одной строке кода, просто выделив одну переменную стека (скажем, массив), которая больше максимального размера стека. Или вы можете сделать это с помощью бесконечной (или конечной, но очень глубокой) рекурсии или просто выделив слишком много переменных стека.

Компоновщик Microsoft по умолчанию устанавливает это значение в 1 МБ на платформах X86 (4 МБ в системах Itanium). На первый взгляд это кажется малым для современной системы. Однако более современные версии Windows интерпретируют эти значения немного по-разному. Вместо того, чтобы полностью ограничивать стек, он ограничивает физическую память, которую будет использовать стек. Если ваш стек выходит за рамки этого, задействуется виртуальная память, поэтому вы все равно должны быть в порядке ... при условии, что у вас достаточно виртуальной памяти.

Помните, что позволяет исчерпать память даже в современных системах с огромным объемом оперативной памяти и большим количеством виртуальной памяти на диске. Вам просто нужно выделить действительно большие объемы данных.

Итак, короче говоря: возможно ли переполнить стек без бесконечной рекурсии? Определенно. Это вероятно? Не совсем, если только вы не размещаете действительно огромные объекты.

Answer 2

Стек переполняется, когда указатель стека выталкивается из блока памяти, выделенного операционной системой для стека. Некоторые операционные системы изменяют размер стека по мере его роста (IIRC Linux делает это), в то время как в других размер стека устанавливается в начале процесса или потока (IIRC Windows делает это).

Возможные причины переполнения стека:

• Неограниченное количество кадров стека (например, из неограниченной рекурсии)
• Попытка выделить большие блоки из стека
• Переполнения буфера для буферов, выделенных в стеке

Возможно, есть и другие причины, о которых я не могу вспомнить, если не считать головы.

Answer 3

Этот вопрос не определяет, какой стек является "стеком". Итак, вот несколько ответов:

стек вызовов

Стек вызовов переполняется всякий раз, когда количество вызовов в стеке превышает объем памяти, который у него есть. Наиболее распространенным способом является бесконечная рекурсия, но вполне возможно иметь рекурсию, которая чрезмерна, но не бесконечна. Например, вычисление функции Аккермана наивно облагает налогом любой компьютер.

Языки

Языки на основе стека

Некоторые языки, такие как Postscript и Forth, и некоторые виртуальные машины, такие как виртуальная машина Java, основаны на стеке. На этих языках возможно сделать выражения настолько сложными, что они переполняют стек.

Контекстно-свободные языки

Неконтекстные языки часто реализуются с использованием стека. Если строки для кода этих языков становятся слишком сложными, возможно переполнение стека.

Answer 4

На ноутбуке или настольном компьютере может быть необычно переполнять стек без бесконечной (или очень глубоко вложенной) рекурсии при запуске из основного потока ... однако переполнения стека не редкость для:

• Потоковый код, в котором потоку выделен небольшой стек фиксированного размера.
• Код обработки сигналов, в котором контекст обработки сигналов имеет небольшой стек фиксированного размера.
• Код выполняется на встроенных устройствах, где памяти, как правило, недостаточно.

Например, если вы зарегистрируете обработчик сигнала, используя sigaction , если обработчик сигнала выполняет какие-либо сложные (т. Е. Глубоко вложенные) операции, очень легко получить переполнение стека в ряде операционных систем. , поскольку обработчикам сигналов обычно выделяется небольшой стек фиксированного размера. Аналогично, если вы порождаете поток с помощью pthread_create , но вы указываете небольшой размер стека с помощью pthread_attr_setstacksize , тогда очень легко достичь переполнения стека. На устройствах с очень ограниченным объемом памяти, таких как беспроводные датчики, можно избежать переполнения стека.

Answer 5

Моя повседневная работа включает в себя большую работу с LotusScript в Lotus Notes, который имеет фиксированные ограничения стека для различных областей. Например. большинство переменных в процедуре / функции должны помещаться в стек размером 32 КБ, за исключением того, что содержимое переменных класса хранится в куче.
Если переменные фиксированного размера превышают размер стека, код не будет компилироваться.
Переполнение стека во время выполнения может произойти с рекурсией. Этого легко добиться в LotusScript, поскольку он ограничивает рекурсию любой отдельной функции стеком 32 КБ. Из-за этого я отказался от использования рекурсивной быстрой сортировки несколько лет назад.

Answer 6

Если ваша программа превышает выделенное пространство стека без какой-либо бесконечной рекурсии, значит, вы делаете что-то не так.

Хотя это может произойти, если вы пропустите несколько звездочек и попытаетесь передать несколько огромных буферов по значению.

Объем памяти, выделяемой для стека, обычно увеличивается по мере необходимости в разумных пределах - я не уверен, каков верхний предел для различных систем.