Как обнаруживается исключение StackOverflowException?

TL; TR
Когда я задал вопрос, я предположил StackOverflowException - Это механизм предотвращения бесконечного запуска приложений. Это неправда.
A StackOverflowException не обнаруживается.
Он бросается, когда стек не имеет возможности выделить больше памяти.

[исходный вопрос:]

это общий вопрос, который может иметь разные ответы на язык программирования.
Я не уверен, как языки, отличные от C#, обрабатывают a переполнение стека.

Я сегодня переживал исключения и продолжал думать о том, как A StackOverflowException можно обнаружить. Я считаю, что невозможно сказать f.e. если стек имеет глубину 1000 вызовов, то бросьте исключение. Потому что, возможно, в некоторых случаях правильная логика будет настолько глубокой.

какова логика обнаружения бесконечного цикла в моей программе?

StackOverflowException class:
https://msdn.microsoft.com/de-de/library/system.stackoverflowexception%28v=vs.110%29.aspx

Перекрестная ссылка, упомянутая в StackOverflowException класс documentation:
https://msdn.microsoft.com/de-de/library/system.reflection.emit.opcodes.localloc(v=vs. 110).aspx

Я только что добавил stack-overflow тег к этому вопросу, и описание говорит, что он выбрасывается, когда стек вызовов потребляет слишком много памяти. Сделать это означает, что стек вызовов - это какой-то путь к текущей позиции выполнения моей программы, и если он не может хранить больше путь, то исключение выбрасывается?

6 66
c# stack-overflow infinite-loop

6 ответов:

переполнение стека

Я сделаю это легко для вас; но это на самом деле довольно сложно... Обратите внимание, что я буду обобщать совсем немного здесь.

как вы знаете, большинство языков используют стек для хранения информации о вызовах. Смотрите также:https://msdn.microsoft.com/en-us/library/zkwh89ks.aspx Для того, как работает cdecl. Если вы вызываете метод, вы нажимаете материал в стеке; если вы возвращаетесь, вы вытаскиваете материал из стека.

обратите внимание, что рекурсия обычно не является "встроенной". (Примечание: Я явно говорю "рекурсия" здесь, а не "хвостовая рекурсия"; последний работает как "goto" и не увеличивает стек).

самый простой способ обнаружить переполнение стека-проверить текущую глубину стека (например, используемые байты) - и если он попадает в границу, дайте ошибку. Чтобы уточнить об этой "проверке границ": способ выполнения этих проверок обычно используется с помощью защитных страниц; это означает, что проверки границ обычно не выполняются, как если бы-то-еще проверки (хотя некоторые реализации существуют...).

в большинстве языков, каждый поток имеет свой собственный стек.

обнаружение бесконечных петель

Ну, вот вопрос, который я не слышал некоторое время. : -)

в основном обнаружение всех бесконечных циклов требует от вас решения Остановить. Который, кстати, является неразрешимые проблемы. Это определенно не делается компиляторами.

этот это не значит, что вы не можете сделать никакого анализа; на самом деле, вы можете сделать совсем немного анализа. Однако также обратите внимание, что иногда вы хотите, чтобы вещи запускались бесконечно (например, основной цикл на веб-сервере).

другие языки

тоже интересно... Функциональные языки используют рекурсию, поэтому они в основном связаны стека. (Тем не менее, функциональные языки также имеют тенденцию использовать хвостовую рекурсию, которая работает более или менее как "goto" и не растет стек.)

а еще есть логические языки.. Ну теперь, я не уверен, как петля навсегда в этом - вы, вероятно, в конечном итоге с чем-то, что не будет оценивать вообще (никакое решение не может быть найдено). (Хотя, это, вероятно, зависит от языка... )

уступая, асинхронные, продолжения

интересная концепция, о которой вы могли бы подумать, называется продолжения. Я слышал от Microsoft, что когда yield впервые была реализована, в качестве реализации рассматривались реальные продолжения. Продолжения в основном позволяют вам "сохранить" стек, продолжить где-то еще и "восстановить" стек обратно в более поздний момент... (Опять же, детали намного сложнее, чем это; это только основная идея).

к сожалению, Microsoft не пошла на эту идею (хотя я могу себе представить, почему), но реализовала ее с помощью вспомогательного класса. Выход и асинхронность в C# работают путем добавления временного класса и интернирования всех локальных переменные внутри класса. Если вы вызываете метод, который выполняет "выход" или "асинхронность", вы фактически создаете вспомогательный класс (из вызываемого метода и нажимаете на стек), который нажимается на кучу. Класс, который помещается в кучу, имеет функциональность (например, для yield это реализация перебора). Это делается с помощью переменной состояния, которая хранит местоположение (например, некоторый идентификатор состояния), где программа должна продолжаться, когда MoveNext называется. Ветвь (переключатель) с помощью этот идентификатор позаботится об остальном. Обратите внимание, что этот механизм не делает ничего "особенного" с тем, как работает сам стек; вы можете реализовать то же самое самостоятельно, используя классы и методы (это просто включает в себя больше ввода :-)).

решение переполнения стека с помощью ручного стека

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

public void FloodFill(int x, int y, int color)
{
    // Wait for the crash to happen...
    if (Valid(x,y))
    {
        SetPixel(x, y, color);
        FloodFill(x - 1, y, color);
        FloodFill(x + 1, y, color);
        FloodFill(x, y - 1, color);
        FloodFill(x, y + 1, color);
    }
}

в этом нет ничего плохого однако этот код. Он делает всю работу, но наш стек мешает. Наличие ручного стека решает эту проблему, хотя реализация в основном одинакова:

public void FloodFill(int x, int y, int color)
{
    Stack<Tuple<int, int>> stack = new Stack<Tuple<int, int>>();
    stack.Push(new Tuple<int, int>(x, y));
    while (stack.Count > 0)
    {
        var current = stack.Pop();

        int x2 = current.Item1;
        int y2 = current.Item2;

        // "Recurse"
        if (Valid(x2, y2))
        {
            SetPixel(x2, y2, color);
            stack.Push(new Tuple<int, int>(x2-1, y2));
            stack.Push(new Tuple<int, int>(x2+1, y2));
            stack.Push(new Tuple<int, int>(x2, y2-1));
            stack.Push(new Tuple<int, int>(x2, y2+1));
        }
    }
}
41

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

Я не уверен, как языки, отличные от C#, обрабатывают переполнение стека.

Ваш вопрос "Как обнаружить переполнение стека?"Ваш вопрос о том, как он обнаруживается в C# или на каком-то другом языке? Если у вас есть вопрос о другом языке, я рекомендую создать новый вопрос.

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

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

какова логика обнаружения бесконечного цикла в моей программе?

вы имеете в виду неограниченная рекурсия, а не бесконечный цикл.

Я опишу это ниже.

Я только что добавил тег Stack-overflow к этому вопросу, и в описании говорится, что он выбрасывается, когда стек вызовов потребляет слишком много памяти. Означает ли это, что стек вызовов является некоторым вид пути к текущей позиции выполнения моей программы, и если он не может хранить больше информации о пути, то возникает исключение?

короткий ответ: да.

больше ответ: стек вызовов используется для двух целей.

во-первых, представлять информация об активации. То есть, значения локальных переменных и временных значений, время жизни которых равно или короче, чем текущая активация ("вызов") метода.

во-вторых, представлять информация о продолжении. То есть, когда я закончу с этим методом, что мне нужно сделать дальше? обратите внимание, что стек делает не представляют "откуда я пришел?". Стек представляет куда я иду дальше и так получилось, что обычно когда метод возвращается, вы возвращаетесь туда, откуда вы пришли.

стек также хранит информацию для неместных продолжение - то есть обработка исключений. Когда метод бросает вызов, стек вызовов содержит данные, которые помогают среде выполнения определить, какой код, если таковой имеется, содержит соответствующий блок catch. Этот блок catch затем становится продолжение -- "что мне делать дальше" -- метода.

теперь, прежде чем я продолжу, я отмечаю, что стек вызовов-это структура данных, которая используется для два цели, нарушающие принцип единой ответственности. Нет требование что существует один стек, используемый для двух целей, и на самом деле есть некоторые экзотические архитектуры, в которых есть два стека, один для фреймов активации и один для обратных адресов (которые являются воплощением продолжения.) Такие архитектуры менее уязвимы для атак" разбивания стека", которые могут происходить на таких языках, как C.

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

более подробно, как Windows делает из обнаружения стека?

Я написал логику обнаружения вне стека для 32-разрядных версий Windows VBScript и JScript в 1990-х годах; среда CLR использует те же методы, что и я, но если вы хотите узнать подробности, связанные с CLR, вам придется проконсультироваться с экспертом на CLR.

давайте рассмотрим только 32-битные окна; 64-битные окна работают аналогично.

Windows использует виртуальную память, конечно, если вы не понимаете, как работает виртуальная память, сейчас было бы хорошее время, чтобы изучить, прежде чем читать дальше. Каждому процессу предоставляется 32-битное плоское адресное пространство, половина которого зарезервирована для операционной системы, а половина-для пользовательского кода. Каждому потоку по умолчанию предоставляется зарезервированный непрерывный блок из одного мегабайта адресного пространства. (Примечание: это один причина, по которой нити тяжеловесны. Миллион байтов непрерывной памяти-это много, когда у вас есть только два миллиарда байтов в первую очередь.)

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

хорошо, поэтому у нас есть, скажем, миллион байтов памяти, разделенных в 250 страниц по 4 КБ каждый. Но программа, когда она впервые запускается, понадобится только несколько КБ стека. Вот как это работает. Текущая страница стека-это совершенно хорошая выделенная страница; это просто нормальная память. Страница дальше это помечено как страничка охраны. А то последние страница в нашем миллионном стеке байтов отмечена как очень специальная страница охраны.

предположим, что мы пытаемся написать байт стековой памяти за пределами нашей хорошей страницы стека. Эта страница охраняется, поэтому происходит ошибка страницы. Операционная система обрабатывает ошибку, делая эту страницу стека хорошей, а далее страница становится новой страницей guard.

, если последние страничка guard поражена - очень особенная - затем Windows запускает исключение из стека, и Windows сбрасывает страницу guard, чтобы означать "если эта страница снова поражена, завершите процесс". Если это произойдет, то Windows завершает процесс тут. Ни одно исключение. Нет кода очистки. Нет диалогового окна. Если вы когда-либо видели, что приложение для Windows просто внезапно исчезает полностью, вероятно, что произошло, кто-то ударил страницу guard в конце стека для второй времени.

хорошо, теперь, когда мы понимаем механизмы-и снова, я замалчиваю здесь многие детали-вы, вероятно, можете увидеть, как писать код, который делает исключения из стека. Вежливый способ - это то, что я сделал VBScript и JScript -- это сделать запрос виртуальной памяти в стеке и спросить, где находится последняя страница guard. Затем периодически смотрите на текущий указатель стека, и если он попадает в течение нескольких страниц, просто создайте ошибку VBScript или бросьте исключение JavaScript прямо тогда и там, а не позволяйте операционной системе делать это за вас.

Если вы не хотите делать это зондирование себя, то вы можете справиться с первый шанс исключение, операционная система дает вам, когда последняя страница защиты поражена, превратите это в исключение переполнения стека, которое понимает C#, и будьте очень осторожны чтобы не попасть на страничку охранника во второй раз.

33

стек-это просто блок памяти фиксированного размера, которая выделяется при создании потока. Существует также "указатель стека", способ отслеживания того, сколько стека в настоящее время используется. В рамках создания нового кадра стека (при вызове метода, свойства, конструктор и т. д.) он перемещает указатель стека вверх на сумму, которая понадобится новому кадру. В это время он будет проверять, если переместил указатель стека в конец стека, и если да, то киньте ГОСПРЕДПРИЯТИЕ.

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

13

внимание: это имеет много делать с механикой под капотом, в том числе как сам CLR должен работать. Это будет иметь смысл только в том случае, если вы начнете изучать программирование на уровне сборки.

под капотом вызовы методов выполняются путем передачи управления на сайт другого метода. Для передачи аргументов и возвращений они загружаются в стек. Для того, чтобы знать, как возвращение управление вызывающим методом, среда CLR также должна реализовать стек вызовов, который нажимается при вызове метода и выскакивает из него, когда метод возвращается. Этот стек сообщает методу возврата здесь для возврата управления.

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

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

добавление: причина, по которой я упоминаю рекурсивные циклы-это потому, что исключение произойдет только в том случае, если вы переполните стек, что обычно означает, что вы вызываете методы, которые в конечном итоге возвращаются в тот же метод и увеличивают стек вызовов. Если у вас есть что-то логически бесконечное, но не рекурсивный, вы обычно не увидите а StackOverflowException

6

проблема с переполнением стека не в том, что они могут вытекать из бесконечного вычисления. Проблема заключается в исчерпании стековой памяти, которая является конечным ресурсом в современных операционных системах и языках.

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

4

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

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

обнаружение переполнения стека с помощью кода использовался еще в те дни, когда ПК работали в 16-битном реальные режим и оборудование были слабыми. Он больше не используется, но об этом стоит упомянуть. В этом сценарии мы указываем переключатель компилятора, который просит компилятор выдавать специальный скрытый фрагмент кода проверки стека в начале каждой функции, которую мы пишем. Этот код просто считывает значение регистра указателя стека и проверяет, не слишком ли он близок к концу стека; если это так, он останавливает нашу программу. Стек на архитектуре x86 увеличивается вниз, поэтому если диапазон адресов от 0x80000 до 0x90000 был обозначен как стек нашей программы, то указатель стека первоначально указывает на 0x90000, и по мере того, как вы продолжаете вызывать вложенные функции, он опускается к 0x80000. Итак, если код проверки стека видит, что указатель стека слишком близок к 0x80000, (скажем, при 0x80010 или ниже), то он прекращения.

все это имеет недостаток: а) добавление накладных расходов к каждому вызову функции, который мы делаем, и Б) невозможность обнаружить переполнение стека во время вызовов внешнего кода, который не был скомпилирован с помощью этого специального переключателя компилятора и поэтому не выполняет никакой проверки переполнения стека. Еще в те времена StackOverflow исключение было неслыханной роскошью: ваша программа либо завершится очень лаконично (можно было бы почти сказать грубо) сообщение об ошибке , или произойдет сбой системы, требующий перезагрузки.

обнаружение переполнения стека с помощью аппаратного в основном делегирует задание процессору. Современные процессоры имеют сложную систему для разделения памяти на страницы (обычно длиной 4 КБ каждая) и выполнения различных трюков с каждой страницей, включая возможность автоматического прерывания (в некоторых архитектурах называемого "ловушкой") при доступе к определенной странице. Итак, операционная система настраивает Процессор таким образом, что прерывание будет выдано, если вы попытаетесь получить доступ к адресу стековой памяти ниже назначенного минимума. Когда это прерывание происходит, оно принимается средой выполнения вашего языка (в случае C#, среда выполнения .Net), и оно переводится в StackOverflow исключения.

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

3