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

Question

Какой лучший способ отловить переполнение стека в C?

Более конкретно:

Программа на C содержит интерпретатор языка сценариев.

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

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

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

Есть ли лучший способ сделать это? В частности, я не ожидаю лучшего портативного решения, но если бы у меня было системное решение для Linux и другое для Windows, это было бы хорошо.

Я видел ссылки на то, что называется структурной обработкой исключений в Windows, хотя ссылки, которые я видел, были о переводе этого в механизм обработки исключений C ++; можно ли получить к нему доступ из C, и если да, то полезно ли это для этого сценария?

Я понимаю, что Linux позволяет вам поймать сигнал об ошибке сегментации; Можно ли надежно превратить это в longjmp обратно в ваш основной цикл?

Похоже, что Java поддерживает перехват исключений переполнения стека на всех платформах; как это реализовать?

Answer 1

Вдобавок ко мне, один из способов поймать чрезмерный рост стека - проверить относительную разницу в адресах стековых фреймов:

#define MAX_ROOM    (64*1024*1024UL)    // 64 MB

static char *   first_stack = NULL;

void foo(...args...)
{
    char    stack;

    // Compare addresses of stack frames
    if (first_stack == NULL)
        first_stack = &stack;
    if (first_stack > &stack  &&  first_stack - &stack > MAX_ROOM  ||
        &stack > first_stack  &&  &stack - first_stack > MAX_ROOM)
        printf("Stack is larger than %lu\n", (unsigned long)MAX_ROOM);

    ...code that recursively calls foo()...
}

Это сравнивает адрес первого фрейма стека для foo() на текущий адрес кадра стека, и если разница превышает MAX_ROOM, он пишет сообщение.

Это предполагает, что вы используете архитектуру, в которой используется линейный всегда растущий или всегда растущийСтоп, конечно.

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

Answer 2

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

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

Такие вещи, как Java, справляются с этим путем генерации машинного кода, так что это просто случай генерации кода для проверки этого при каждом переходе в стек.

Answer 3

(Я не буду беспокоить эти методы в зависимости от конкретных платформ для «лучших» решений. Они создают проблемы , ограничивая языковой дизайн и удобство использования, с небольшим выигрышем. Для ответов «просто работайте» над Linux и Windows, см. Выше.)

Прежде всего, в смысле C, вы не можете сделать это портативным способом . На самом деле, ISO C не предписывает вообще никакого «стека». Педантично даже кажется, что когда автоматическое выделение объектов завершилось неудачно, поведение буквально не определено, согласно пункту 4p2 - просто нет гарантии, что произойдет, если вызовы будут вложены слишком глубоко. Вы должны полагаться на некоторые дополнительные предположения реализации ( ISA или OS ABI ), чтобы сделать это, так что вы получите C + что-то еще, а не только C. Машинный код времени выполнения поколение также не переносимо на уровне C.

(Кстати, ISO C ++ имеет понятие разматывание стека , но только в контексте обработки исключений. И до сих пор нет гарантии переносимого поведения при переполнении стека; хотя это, кажется, не определено, не определено.)

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

Единственный переносимый способ, который я нахожу, это не полагаться на собственный стек базовой архитектуры машины. В целом это означает, что вы должны распределять кадры записи активации как часть свободного хранилища (в куче), а не как собственный стек, предоставляемый ISA. Это работает не только для интерпретируемых языковых реализаций, но и для скомпилированных, например, SML / NJ. Такой подход программного стека не всегда приводит к худшей производительности , поскольку он позволяет обеспечить абстракцию более высокого уровня на объектном языке, поэтому программы могут иметь больше возможностей для оптимизации, хотя это маловероятно для наивного интерпретатора.

У вас есть несколько вариантов для достижения этой цели. Один из способов - написать виртуальную машину . Вы можете выделить память и построить в ней стек.

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