что такое переполнение стека
Как происходит «переполнение стека» и как его предотвратить?
Как происходит переполнение стека и как лучше всего этого избежать или как предотвратить его, особенно на веб-серверах, но были бы интересны и другие примеры?
Когда вы вызываете функцию в своем коде, следующая инструкция после вызова функции сохраняется в стеке и любое пространство памяти, которое может быть перезаписано вызовом функции. Вызываемая функция может использовать больше стека для собственных локальных переменных. Когда это будет сделано, он освобождает используемое пространство стека локальной переменной, а затем возвращается к предыдущей функции.
Переполнение стека
Многие программисты делают эту ошибку, вызывая функцию A, которая затем вызывает функцию B, которая затем вызывает функцию C, которая затем вызывает функцию A. Она может работать большую часть времени, но только один раз неправильный ввод заставит ее навсегда войти в этот круг. пока компьютер не обнаружит, что стек слишком раздут.
Рекурсивные функции также являются причиной этого, но если вы пишете рекурсивно (т. Е. Ваша функция вызывает сама себя), вам необходимо знать об этом и использовать статические / глобальные переменные для предотвращения бесконечной рекурсии.
Обычно операционная система и язык программирования, который вы используете, управляют стеком, и это вне ваших рук. Вы должны посмотреть на свой граф вызовов (древовидную структуру, которая показывает из вашего main, что вызывает каждая функция), чтобы увидеть, насколько глубоко заходят ваши вызовы функций, и чтобы обнаружить циклы и рекурсию, которые не предназначены. Преднамеренные циклы и рекурсия необходимо искусственно проверять, чтобы исключить ошибки, если они вызывают друг друга слишком много раз.
Помимо хороших практик программирования, статического и динамического тестирования, на этих высокоуровневых системах мало что можно сделать.
Встроенные системы
Во встраиваемом мире, особенно в коде высокой надежности (автомобильный, авиационный, космический), вы выполняете обширный анализ и проверку кода, но вы также делаете следующее:
Языки и системы высокого уровня
Но на языках высокого уровня, работающих в операционных системах:
Веб-серверы
Что такое стек
И почему так страшен стек-оверфлоу.
Постепенно осваиваем способы организации и хранения данных. Уже было про деревья, попробуем про стеки. Это для тех, кто хочет в будущем серьёзно работать в ИТ: одна из фундаментальных концепций, которая влияет на качество вашего кода, но не касается какого-то конкретного языка программирования.
👉 Стек — это одна из структур данных. Структура данных — это то, как хранятся данные: например, связанные списки, деревья, очереди, множества, хеш-таблицы, карты и даже кучи (heap).
Как устроен стек
Стек хранит последовательность данных. Связаны данные так: каждый элемент указывает на тот, который нужно использовать следующим. Это линейная связь — данные идут друг за другом и нужно брать их по очереди. Из середины стека брать нельзя.
👉 Главный принцип работы стека — данные, которые попали в стек недавно, используются первыми. Чем раньше попал — тем позже используется. После использования элемент стека исчезает, и верхним становится следующий элемент.
Классический способ объяснения принципов стека звучит так: представьте, что вы моете посуду и складываете одинаковые чистые тарелки стопкой друг на друга. Каждая новая тарелка — это элемент стека, а вы просто добавляете их по одной в стек.
Когда кому-то понадобится тарелка, он не будет брать её снизу или из середины — он возьмёт первую сверху, потом следующую и так далее.
🤔 Есть структура данных, похожая на стек, — называется очередь, или queue. Если в стеке кто последний пришёл, того первым заберут, то в очереди наоборот: кто раньше пришёл, тот раньше ушёл. Можно представить очередь в магазине: кто раньше её занял, тот первый дошёл до кассы. Очередь — это тоже линейный набор данных, но обрабатывается по-другому.
Стек вызовов
В программировании есть два вида стека — стек вызовов и стек данных.
Когда в программе есть подпрограммы — процедуры и функции, — то компьютеру нужно помнить, где он прервался в основном коде, чтобы выполнить подпрограмму. После выполнения он должен вернуться обратно и продолжить выполнять основной код. При этом если подпрограмма возвращает какие-то данные, то их тоже нужно запомнить и передать в основной код.
Чтобы это реализовать, компьютер использует стек вызовов — специальную область памяти, где хранит данные о точках перехода между фрагментами кода.
Допустим, у нас есть программа, внутри которой есть три функции, причём одна из них внутри вызывает другую. Нарисуем, чтобы было понятнее:
Программа запускается, потом идёт вызов синей функции. Она выполняется, и программа продолжает с того места, где остановилась. Потом выполняется зелёная функция, которая вызывает красную. Пока красная не закончит работу, все остальные ждут. Как только красная закончилась — продолжается зелёная, а после её окончания программа продолжает свою работу с того же места.
А вот как стек помогает это реализовать на практике:
Программа дошла до синей функции, сохранила точку, куда ей вернуться после того, как закончится функция, и если функция вернёт какие-то данные, то программа тоже их получит. Когда синяя функция закончится и программа получит верхний элемент стека, он автоматически исчезнет. Стек снова пустой.
С зелёной функцией всё то же самое — в стек заносится точка возврата, и программа начинает выполнять зелёную функцию. Но внутри неё мы вызываем красную, и вот что происходит:
При вызове красной функции в стек помещается новый элемент с информацией о данных, точке возврата и указанием на следующий элемент. Это значит, что когда красная функция закончит работу, то компьютер возьмёт из стека адрес возврата и вернёт управление снова зелёной функции, а красный элемент исчезнет. Когда и зелёная закончит работу, то компьютер из стека возьмёт новый адрес возврата и продолжит работу со старого места.
Переполнение стека
Почти всегда стек вызовов хранится в оперативной памяти и имеет определённый размер. Если у вас будет много вложенных вызовов или рекурсия с очень большой глубиной вложенности, то может случиться такая ситуация:
Переполнение — это плохо: данные могут залезать в чужую область памяти и записывать себя вместо прежних данных. Это может привести к сбою в работе других программ или самого компьютера. Ещё таким образом можно внедрить в оперативную память вредоносный код: если программа плохо работает со стеком, можно специально вызвать переполнение и записать в память что-нибудь вредоносное.
Стек данных
Стек данных очень похож на стек вызовов: по сути, это одна большая переменная, похожая на список или массив. Его чаще всего используют для работы с другими сложными типами данных: например, быстрого обхода деревьев, поиска всех возможных маршрутов по графу, — и для анализа разветвлённых однотипных данных.
Стек данных работает по такому же принципу, как и стек вызовов — элемент, который добавили последним, должен использоваться первым.
Что дальше
А дальше поговорим про тип данных под названием «куча». Да, такой есть, и с ним тоже можно эффективно работать. Стей тюнед.
Как происходит «переполнение стека» и как его предотвратить?
Как происходит переполнение стека и каковы наилучшие способы убедиться, что этого не происходит, или способы предотвратить это, особенно на веб-серверах, но другие примеры также были бы интересны?
9 ответов
при вызове функции в коде следующая инструкция после вызова функции сохраняется на стек и любое пространство хранения, которое может быть перезаписано вызовом функции. Вызываемая функция может использовать больше стека для собственных локальных переменных. Когда это сделано, он освобождает пространство стека локальной переменной, которое он использовал, а затем возвращается к предыдущей функции.
переполнение стека
многие программисты делают эту ошибку, вызывая функцию A, которая затем вызывает функцию B, которая затем вызывает функцию C, которая затем вызывает функцию A. Это может работать большую часть времени, но только один раз неправильный ввод заставит его идти по этому кругу навсегда, пока компьютер не распознает, что стек раздут.
рекурсивные функции также являются причиной этого, но если вы пишете рекурсивно (т. е. ваша функция вызывает себя), вам нужно знать об этом и использовать статические/глобальные переменные для предотвращения бесконечной рекурсии.
Как правило, ОС и язык программирования, который вы используете, управляют стеком, и это не в ваших руках. Вы должны посмотреть на ваш звонок graph (древовидная структура, которая показывает из вашего main, что вызывает каждая функция), чтобы увидеть, как глубоко ваши вызовы функций идут, и обнаружить циклы и рекурсию, которые не предназначены. Преднамеренные циклы и рекурсия должны быть искусственно проверены на ошибку, если они вызывают друг друга слишком много раз.
помимо хороших методов программирования, статического и динамического тестирования, вы мало что можете сделать в этих системах высокого уровня.
встраиваемых систем
во встроенном мир, особенно в коде высокой надежности (автомобильный, самолет, космос) Вы делаете обширные обзоры кода и проверку, но вы также делаете следующее:
языки и системы высокого уровня
но в языках высокого уровня, работающих в операционных системах:
веб-сервера
переполнение стека в реальном коде происходит очень редко. Большинство ситуаций, в которых это происходит, являются рекурсиями, в которых завершение было забыто. Однако это может редко происходить в сильно вложенных структурах, например, особенно больших XML-документах. Единственная реальная помощь здесь-рефакторинг кода для использования явного объекта стека вместо стека вызовов.
некоторые опции в этом случае:
обычно переполнение стека является результатом бесконечного рекурсивного вызова (учитывая обычный объем памяти в настоящее время для обычных компьютеров).
при вызове метода, функции или процедуры «стандартный» способ или вызов состоит в следующем:
таким образом, обычно это занимает несколько байтов, уменьшающих количество и тип параметров, а также архитектуру машины.
вы увидите, что если вы начнете делать рекурсивные вызовы, стек начнет расти. Сейчас, стек обычно резервируется в памяти таким образом, что он растет в противоположном направлении к куче, поэтому при большом количестве вызовов без «возврата» стек начинает заполняться.
теперь, в старые времена переполнение стека может произойти просто потому, что вы exausted всю доступную память, просто так. С моделью виртуальной памяти (до 4 ГБ в системе X86), которая была вне области, поэтому обычно, если вы получаете ошибку переполнения стека, ищите бесконечный рекурсивный вызов.
переполнение стека происходит, когда Джефф и Джоэл хотите дать миру лучшее место, чтобы получить ответы на технические вопросы. Слишком поздно предотвращать переполнение стека. Этот «другой сайт» мог бы предотвратить это, не будучи scuzzy. 😉
Помимо формы переполнения стека, которую вы получаете от прямой рекурсии (например, Fibonacci(1000000) ), более тонкой формой этого, которую я испытывал много раз, является косвенная рекурсия, где функция вызывает другую функцию, которая вызывает другую, а затем одна из этих функций снова вызывает первую.
это обычно может происходить в функциях, которые вызываются в ответ на события, но которые сами могут генерировать новые события, например:
в этом случае вызов ResizeWindow может привести к WindowSizeChanged() обратный вызов должен быть запущен снова, который вызывает ResizeWindow снова, пока у вас не закончится стек. В таких ситуациях вам часто нужно отложить ответ на событие до тех пор, пока не вернется кадр стека, например, отправив сообщение.
что? Никто не любит тех, кого окружает бесконечная петля?
Урок №105. Стек и Куча
На этом уроке мы рассмотрим стек и кучу в языке C++.
Сегменты
Память, которую используют программы, состоит из нескольких частей — сегментов:
Сегмент кода (или «текстовый сегмент»), где находится скомпилированная программа. Обычно доступен только для чтения.
Сегмент bss (или «неинициализированный сегмент данных»), где хранятся глобальные и статические переменные, инициализированные нулем.
Сегмент данных (или «сегмент инициализированных данных»), где хранятся инициализированные глобальные и статические переменные.
Куча, откуда выделяются динамические переменные.
Стек вызовов, где хранятся параметры функции, локальные переменные и другая информация, связанная с функциями.
Сегмент кучи (или просто «куча») отслеживает память, используемую для динамического выделения. Мы уже немного поговорили о куче на уроке о динамическом выделении памяти в языке С++.
В языке C++ при использовании оператора new динамическая память выделяется из сегмента кучи самой программы:
Адрес выделяемой памяти передается обратно оператором new и затем он может быть сохранен в указателе. О механизме хранения и выделения свободной памяти нам сейчас беспокоиться незачем. Однако стоит знать, что последовательные запросы памяти не всегда приводят к выделению последовательных адресов памяти!
При удалении динамически выделенной переменной, память возвращается обратно в кучу и затем может быть переназначена (исходя из последующих запросов). Помните, что удаление указателя не удаляет переменную, а просто приводит к возврату памяти по этому адресу обратно в операционную систему.
Куча имеет свои преимущества и недостатки:
Выделение памяти в куче сравнительно медленное.
Выделенная память остается выделенной до тех пор, пока не будет освобождена (остерегайтесь утечек памяти) или пока программа не завершит свое выполнение.
Доступ к динамически выделенной памяти осуществляется только через указатель. Разыменование указателя происходит медленнее, чем доступ к переменной напрямую.
Поскольку куча представляет собой большой резервуар памяти, то именно она используется для выделения больших массивов, структур или классов.
Стек вызовов
Стек вызовов (или просто «стек») отслеживает все активные функции (те, которые были вызваны, но еще не завершены) от начала программы и до текущей точки выполнения, и обрабатывает выделение всех параметров функции и локальных переменных.
Стек вызовов реализуется как структура данных «Стек». Поэтому, прежде чем мы поговорим о том, как работает стек вызовов, нам нужно понять, что такое стек как структура данных.
Стек как структура данных
Структура данных в программировании — это механизм организации данных для их эффективного использования. Вы уже видели несколько типов структур данных, например, массивы или структуры. Существует множество других структур данных, которые используются в программировании. Некоторые из них реализованы в Стандартной библиотеке C++, и стек как раз является одним из таковых.
Например, рассмотрим стопку (аналогия стеку) тарелок на столе. Поскольку каждая тарелка тяжелая, а они еще и сложены друг на друге, то вы можете сделать лишь что-то одно из следующего:
Посмотреть на поверхность первой тарелки (которая находится на самом верху).
Взять верхнюю тарелку из стопки (обнажая таким образом следующую тарелку, которая находится под верхней, если она вообще существует).
Положить новую тарелку поверх стопки (спрятав под ней самую верхнюю тарелку, если она вообще была).
В компьютерном программировании стек представляет собой контейнер (как структуру данных), который содержит несколько переменных (подобно массиву). Однако, в то время как массив позволяет получить доступ и изменять элементы в любом порядке (так называемый «произвольный доступ»), стек более ограничен.
В стеке вы можете:
Посмотреть на верхний элемент стека (используя функцию top() или peek() ).
Вытянуть верхний элемент стека (используя функцию pop() ).
Добавить новый элемент поверх стека (используя функцию push() ).
Стек — это структура данных типа LIFO (англ. «Last In, First Out» = «Последним пришел, первым ушел»). Последний элемент, который находится на вершине стека, первым и уйдет из него. Если положить новую тарелку поверх других тарелок, то именно эту тарелку вы первой и возьмете. По мере того, как элементы помещаются в стек — стек растет, по мере того, как элементы удаляются из стека — стек уменьшается.
Например, рассмотрим короткую последовательность, показывающую, как работает добавление и удаление в стеке:
Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Push 4
Stack: 1 2 3 4
Pop
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1
Стопка тарелок довольно-таки хорошая аналогия работы стека, но есть лучшая аналогия. Например, рассмотрим несколько почтовых ящиков, которые расположены друг на друге. Каждый почтовый ящик может содержать только один элемент, и все почтовые ящики изначально пустые. Кроме того, каждый почтовый ящик прибивается гвоздем к почтовому ящику снизу, поэтому количество почтовых ящиков не может быть изменено. Если мы не можем изменить количество почтовых ящиков, то как мы получим поведение, подобное стеку?
Во-первых, мы используем наклейку для обозначения того, где находится самый нижний пустой почтовый ящик. Вначале это будет первый почтовый ящик, который находится на полу. Когда мы добавим элемент в наш стек почтовых ящиков, то мы поместим этот элемент в почтовый ящик, на котором будет наклейка (т.е. в самый первый пустой почтовый ящик на полу), а затем переместим наклейку на один почтовый ящик выше. Когда мы вытаскиваем элемент из стека, то мы перемещаем наклейку на один почтовый ящик ниже и удаляем элемент из почтового ящика. Всё, что находится ниже наклейки — находится в стеке. Всё, что находится в ящике с наклейкой и выше — находится вне стека.
Сегмент стека вызовов
Сегмент стека вызовов содержит память, используемую для стека вызовов. При запуске программы, функция main() помещается в стек вызовов операционной системой. Затем программа начинает свое выполнение.
Когда программа встречает вызов функции, то эта функция помещается в стек вызовов. При завершении выполнения функции, она удаляется из стека вызовов. Таким образом, просматривая функции, добавленные в стек, мы можем видеть все функции, которые были вызваны до текущей точки выполнения.
Наша аналогия с почтовыми ящиками — это действительно то, как работает стек вызовов. Стек вызовов имеет фиксированное количество адресов памяти (фиксированный размер). Почтовые ящики являются адресами памяти, а «элементы», которые мы добавляем или вытягиваем из стека, называются фреймами (или «кадрами») стека. Кадр стека отслеживает все данные, связанные с одним вызовом функции. «Наклейка» — это регистр (небольшая часть памяти в ЦП), который является указателем стека. Указатель стека отслеживает вершину стека вызовов.
Единственное отличие фактического стека вызовов от нашего гипотетического стека почтовых ящиков заключается в том, что, когда мы вытягиваем элемент из стека вызовов, нам не нужно очищать память (т.е. вынимать всё содержимое из почтового ящика). Мы можем просто оставить эту память для следующего элемента, который и перезапишет её. Поскольку указатель стека будет ниже этого адреса памяти, то, как мы уже знаем, эта ячейка памяти не будет находиться в стеке.
Стек вызовов на практике
Давайте рассмотрим детально, как работает стек вызовов. Ниже приведена последовательность шагов, выполняемых при вызове функции:
Программа сталкивается с вызовом функции.
Создается фрейм стека, который помещается в стек. Он состоит из:
адреса инструкции, который находится за вызовом функции (так называемый «обратный адрес»). Так процессор запоминает, куда ему возвращаться после выполнения функции;
памяти для локальных переменных;
сохраненных копий всех регистров, модифицированных функцией, которые необходимо будет восстановить после того, как функция завершит свое выполнение.
Процессор переходит к точке начала выполнения функции.
Инструкции внутри функции начинают выполняться.
После завершения функции, выполняются следующие шаги:
Регистры восстанавливаются из стека вызовов.
Фрейм стека вытягивается из стека. Освобождается память, которая была выделена для всех локальных переменных и аргументов.
Обрабатывается возвращаемое значение.
ЦП возобновляет выполнение кода (исходя из обратного адреса).
Возвращаемые значения могут обрабатываться разными способами, в зависимости от архитектуры компьютера. Некоторые архитектуры считают возвращаемое значение частью фрейма стека, другие используют регистры процессора.
Знать все детали работы стека вызовов не так уж и важно. Однако понимание того, что функции при вызове добавляются в стек, а при завершении выполнения — удаляются из стека, дает основы, необходимые для понимания рекурсии, а также некоторых других концепций, которые полезны при отладке программ.
How to eliminate stack overflow error even after allocating a large stack size?
Unhandled exception at 0x00AA9379 in A.exe: 0xC00000FD: Stack overflow (parameters: 0x00000000, 0x00802000).
I am facing a stack overflow error. I’m using VS15 as my IDE. I tried to allocate more memory for the stack. For that I used Project >> Properties >> Linker >> System >> Stack allocation and allocated 4GB for the stack. But the error continues to stop at chkstk.asm at this line
But the problem isn’t solved. How do I know in advance that how much stack size would I need? I’ve used dynamic memory allocation for all of the large variables. But cannot solve the problem. Here is a verifiable example.
2 Answers 2
The default stack size on Windows using MS compilers is 1 MiB. You put on the stack several arrays that hold millions of integers and doubles.
You said you increased stack size to 4GB. In that case, the following becomes relevant:
The reserved memory size represents the total stack allocation in virtual memory. As such, the reserved size is limited to the virtual address range. The initially committed pages do not utilize physical memory until they are referenced; however, they do remove pages from the system total commit limit, which is the size of the page file plus the size of the physical memory. The system commits additional pages from the reserved stack memory as they are needed, until either the stack reaches the reserved size minus one page (which is used as a guard page to prevent stack overflow) or the system is so low on memory that the operation fails. (emphasis mine)
Given these definitions, the following lists the limits on 32-bit and 64-bit variants of Windows:
32-bit
64-bit
Note that the limit on static and stack data is the same in both 32-bit and 64-bit variants. This is due to the format of the Windows Portable Executable (PE) file type, which is used to describe EXEs and DLLs as laid out by the linker. It has 32-bit fields for image section offsets and lengths and was not extended for 64-bit variants of Windows. As on 32-bit Windows, static data and stack share the same first 2GB of address space. (emphasis mine)
Finally, look closely at the instruction in the beginning of your post:
But the error continues to stop at chkstk.asm at this line
To look more closely at this, I wrote a small program which would generate the same effect as yours (it only «worked» with a 32-bit build—I am not sure what needs to be done to cause a 64-bit executable to crash):
I set the stack size in the linker options to 4294967296 and then ran the program under the debugger. It crashed with a stack overflow, and broke at the same instruction you observed. Scrolling up in the stack checking code, I noted the following comments:
As far as I can figure out, the routine is trying to move the top-of-stack down by PAGESIZE at a time to reserve the applicable stack size.
Indeed, looking at the hexdump of an executable built with /STACK:1000000000 and comparing it to one built with /STACK:4294967296 highlights the problem:
While setting a stack size to larger but still unsupported sizes does result in a positive value being set in the executable header, e.g.:
the resulting executable cannot be run:
However even though setting the stack to a smaller but still large size may enable your program to run, relying on a huge stack is not necessarily a good idea. The immediate alternative is to allocate those arrays on the heap using malloc and remembering to free them.
That is, instead of
you need declare int *Enod and then allocate memory for the array using
Answers to this question discuss why the stack is much more constrained.
In addition, your code would benefit from replacing arbitrary looking numbers with meaningful mnemonics using defines.