Как происходит “переполнение стека” и как Вы предотвращаете его?
Во-первых, я настоятельно рекомендую сделать тип subObjects не факультативным. В редких случаях для факультативных массивов нет причин. Действительно ли вам нужно различать «no array» и «empty array?»? Это очень редко. Если вы сделаете subObjects просто массивом, вы можете написать то, что вы описываете как простую рекурсивную функцию:
func flattenMyObjects(myObjects: [MyObject]) -> [MyObject] {
return myObjects.flatMap { (myObject) -> [MyObject] in
var result = [myObject]
result.appendContentsOf(flattenMyObjects(myObject.subObjects))
return result
}
}
Если вам нужно, чтобы это было необязательным, изменения были незначительными (вы " вам нужно добавить if-let или что-то подобное).
8 ответов
Стек
стопка А, в этом контексте, является методом "последним пришел - первым вышел", буферизуют Вас данные места в то время как Ваши прогоны программы. Метод "последним пришел - первым вышел" (LIFO) означает, что последней вещью, которую Вы вставляете, всегда является первая вещь, которую Вы возвращаете - при продвижении 2 объектов на стеке, и затем 'B', тогда первой вещью, которую Вы выталкиваете от стека, будет 'B', и следующей вещью является 'A'.
, Когда Вы вызываете функцию в своем коде, следующая инструкция после того, как вызов функции хранится на стеке и любом пространстве памяти, которое могло бы быть перезаписано вызовом функции. Функция, которую Вы вызываете, могла бы израсходовать больше стека для своих собственных локальных переменных. Когда это сделано, это освобождает стековое пространство локальной переменной, которое это использовало, затем возвращает предыдущей функции.
Переполнение стека
переполнение стека А состоит в том при израсходовании большей памяти для стека, чем программа, как предполагалось, использовала. Во встроенных системах у Вас могло бы только быть 256 байтов для стека, и если каждая функция поднимает 32 байта тогда, у Вас могут только быть вызовы функции 8 глубоких - функция 1 функция вызовов 2, кто вызывает функцию 3, кто вызывает функцию 4...., кто вызывает функцию 8, кто вызывает функцию 9, но функцию 9 памятей перезаписей вне стека. Это могло бы перезаписать память, код, и т.д.
, Многие программисты делают эту ошибку путем вызывания функции, который тогда вызывает функцию B, который тогда вызывает функцию C, который тогда вызывает функцию A. Это могло бы работать большую часть времени, но только как только неправильный вход заставит его входить в тот круг навсегда, пока компьютер не распознает, что стек раздут.
Рекурсивные функции являются также причиной для этого, но если Вы пишете рекурсивно (т.е., Ваши вызовы функции самого) тогда, необходимо знать об этом и использовать статические / глобальные переменные для предотвращения бесконечной рекурсии.
Обычно ОС и язык программирования, который Вы используете, управляют стеком, и это вне Ваших рук. Необходимо посмотреть граф вызовов (древовидная структура, которая показывает от основного, что каждый вызовы функции), чтобы видеть, как глубоко вызовы функции идут, и обнаружить циклы и рекурсию, которые не предназначаются. Намеренные циклы и рекурсия должны быть искусственно проверены на ошибку, если они называют друг друга слишком много раз.
Вне хороших практик программирования, статического испытания и динамического тестирования, нет очень, можно сделать в этих системах высокого уровня.
Встроенные системы
Во встроенном мире, особенно в высоком коде надежности (автомобильный, самолет, пространство) Вы делаете обширные обзоры кода и проверку, но Вы также делаете следующее:
- Запрещают рекурсию, и циклы - осуществленный политикой и тестированием
- Сохраняют код и складывают далеко друг от друга (код во флэш-памяти, стек в RAM, и никогда двойка не должна встречаться)
- защитные полосы Места вокруг стека - пустая область памяти, которую Вы заполняете магическим числом (обычно инструкция по программному прерыванию, но существует много опций здесь), и сотни или тысячи времен в секунду, Вы смотрите на защитные полосы, чтобы удостовериться, что они не были перезаписаны.
- защита памяти Использования (т.е., нет выполнитесь на стеке, никаком чтении или записи недалеко от стека)
- , Прерывания не вызывают вторичные функции - они устанавливают флаги, копируют данные и позволяют приложению заботиться об обработке его (иначе, Вы могли бы получить 8 глубоко в Вашем дереве вызова функции, иметь прерывание, и затем выйти другой немного функций в прерывании, вызвав выброс). У Вас есть несколько деревьев вызова - один для основных процессов, и один для каждого прерывания. Если Ваши прерывания могут прервать друг друга... хорошо, существуют драконы...
Высокоуровневые языки и системы
, Но на высокоуровневых языках работают на операционных системах:
- Уменьшают Ваше устройство хранения данных локальной переменной (локальные переменные хранятся на стеке - хотя компиляторы довольно умны об этом и будут иногда помещать крупных местных жителей на "кучу", если Ваше дерево вызова мелко)
- , Избегают или строго ограничивают рекурсию
- , не разбивают Ваши программы слишком далеко в меньшие и меньшие функции - даже, не считая локальные переменные, каждый вызов функции использует целых 64 байта на стеке (процессор на 32 бита, сохраняя половину регистров ЦП, флагов, и т.д.)
- Сохраняют Ваше дерево вызова мелким (подобный вышеупомянутому оператору)
веб-серверы
, Это зависит от 'песочницы', которую Вы имеете, можно ли управлять или даже видеть стек. Возможности хороши, можно рассматривать веб-серверы, поскольку Вы были бы любой другой высокоуровневый язык и операционная система - это в основном вне Ваших рук, но проверьте язык и стопку сервера, которую Вы используете. возможно унести стек на Вашем SQL-сервере, например.
-Adam
Переполнение стека в реальном коде происходит очень редко. Большинство ситуаций, в которых это происходит, является рекурсиями, где о завершении забыли. Это могло бы однако редко происходить в высоко вложенных структурах, например, особенно больших XML-документах. Единственная реальная справка здесь должна осуществить рефакторинг код для использования явного объекта стека вместо стека вызовов.
Большинство людей скажет Вам, что переполнение стека происходит с рекурсией без пути выхода - в то время как главным образом верный, если Вы будете работать с достаточно большими структурами данных, даже надлежащий путь выхода рекурсии не поможет Вам.
опции Some в этом случае:
- Поиск в ширину
- Хвостовая рекурсия .Net-определенное великое сообщение в блоге (жаль, 32-разрядный.Net)
Бесконечная рекурсия является распространенным способом получить ошибку переполнения стека. Для предотвращения - всегда удостоверяются, что существует путь выхода, который будет быть пораженным.:-)
Другой способ получить переполнение стека (в C/C++, по крайней мере) состоит в том, чтобы объявить некоторую огромную переменную на стеке.
char hugeArray[100000000];
Это сделает это.
Переполнение стека происходит, когда Jeff и Joel хотят дать миру лучшее место для получения ответов на технические вопросы. Слишком поздно для предотвращения этого переполнения стека. То, что "другой сайт", возможно, предотвратил его, не будучи занюханным.;)
Обычно переполнение стека является результатом бесконечного рекурсивного вызова (учитывая обычный объем памяти в стандартных компьютерах в наше время).
, Когда Вы звоните методу, функции или процедуре, "стандартный" путь или совершение звонка состоят на:
- Требование у направления возврата для вызова в стек (это - следующее предложение после вызова)
- Обычно пространство для возвращаемого значения резервируется в стек
- Продвижение каждого параметра в стек (порядок отличается и зависит от каждого компилятора, также некоторые из них иногда хранятся на регистрах ЦП для повышений производительности)
- Совершение фактического звонка.
Так, обычно это берет несколько байтов depeding на числе и типе параметров, а также архитектуры машины.
Вы будете видеть тогда, что, если Вы начинаете выполнять рекурсивные вызовы, стек начнет расти. Теперь, стек обычно резервируется в памяти таким способом, которым это растет в противоположном направлении до "кучи" так, учитывая большое количество вызовов, не "возвращаясь", стек начинает становиться полным.
Теперь, на более старом переполнении стека времен мог произойти просто потому что Вы exausted вся доступная память, точно так же, как это. С моделью виртуальной памяти (до 4 ГБ в системе X86), который был вне объема так обычно, если Вы получаете ошибку переполнения стека, ищут бесконечный рекурсивный вызов.
Что? Ни у кого нет любви к тем, случился бесконечным циклом?
do
{
JeffAtwood.WritesCode();
} while(StackOverflow.MakingMadBank.Equals(false));
Рассмотрение этого было отмечено со "взламыванием", я подозреваю "переполнение стека", к которому он обращается, переполнение стека вызовов, а не высокоуровневое переполнение стека, такое как те, на которых ссылаются в большинстве других ответов здесь. Это действительно не относится ни к каким управляемым или интерпретируемым средам, таким как.NET, Java, Python, Perl, PHP, и т.д., в котором обычно пишутся веб-приложения, таким образом, Ваш единственный риск является самим веб-сервером, который, вероятно, записан в C или C++.
Выезд этот поток:
https://stackoverflow.com/questions/7308/what-is-a-good-starting-point-for-learning-buffer-overflow