Как определить максимальное использование стека?
Какие методы доступны для определения оптимального размера стека для встроенной системы / системы с ограниченным объемом памяти? Если он слишком большой, то память тратится впустую, что может быть использовано в другом месте. Однако, если он слишком мал, мы получаем тезку этого сайта...
Чтобы попытаться начать все сначала: Джек Гэнсл в "Искусстве проектирования встраиваемых систем " заявляет, что "с опытом можно научиться стандартному, научному способу вычисления правильного размера стека: выбирайте размер наугад и надейтесь". Кто-нибудь может сделать лучше, чем это?
Был запрошен более конкретный пример. Итак, как насчет программы на C, предназначенной для микроконтроллера MSP430 с 2 КБ ОЗУ с использованием набора инструментов IAR Embedded Workbench без операционной системы? Эта IDE может отображать содержимое стека и использование при использовании отладчика JTAG.
5 ответов
Наиболее распространенный способ определить использование самого глубокого стека - инициализировать память стека с некоторым известным, но необычным значением, а затем периодически (или в конце большого теста) видеть, где останавливается этот шаблон.
Именно так IAR IDE определяет объем используемого стека.
Вы пометили свой вопрос статическим анализом, но эту проблему сложно решить с помощью статического анализа. Использование стека зависит от профиля времени выполнения программы, особенно если вы используете рекурсию или alloca. Учитывая, что это встроенная платформа, я думаю, что также сложно запустить что-то вроде ps или top и посмотреть, сколько стека использует ваше приложение.
Интересный подход заключается в использовании адреса текущего стекового фрейма, чтобы определить, какой объем стека используется. Вы можете сделать это, взяв адрес аргумента функции или локальной переменной. Сделайте это для основной функции и функций, которые, по вашему мнению, используют больше всего стека. Разница покажет вам, сколько стека требует ваше приложение. Вот пример (при условии обычного роста стека от высокого до низкого).
char *stack_top, stack_bottom;
int
main(int argc, char *argv[])
{
stack_top = (char *)&argc;
// ...
printf("Stack usage: %d\n", stack_top - stack_bottom);
}
void
deeply_nested_function(void)
{
int a;
stack_bottom = (char *)&a;
// ...
}
Если ваш компилятор позволяет вам указывать пролог пользовательской функции (многие делают это, чтобы разрешить профилирование программ на основе графа), вы можете даже организовать для всех функций вызов такого кода измерения. Тогда ваша функция измерения становится примерно такой
void
stack_measurement_function(void)
{
int a;
stack_bottom = min(stack_bottom, (char *)&a);
// ...
}
Я использовал подход, аналогичный тому, который я описал, для создания этих диаграмм.
С хорошим инструментом статического анализа исходного кода вы можете создать график вызовов для вашего приложения. Учитывая это, и оценки количества локальных / временных файлов, произведенных вашим компилятором, вы можете напрямую вычислить консервативную оценку потребности в стеке.
Под "хорошим" инструментом анализа я имею в виду тот, который может считывать все задействованные блоки компиляции, может определять прямые вызовы функций, может определять косвенные указатели, в блоке компиляции, может вычислять консервативные точки для анализа по всей системе, может построить граф вызовов с учетом анализа точек. Это устраняет множество инструментов, поэтому каждый видит специальные методы, такие как "заполнить стек во время выполнения и посмотреть, что произойдет". Вам также нужны оценки стека, требующие места компилятора в стеке; Вы можете аппроксимировать многое из этого, просто зная, насколько велики требования к хранилищу для всех типов, что, как правило, довольно просто определить для программ на C встроенных систем. Наконец, вы должны верить, что в вашем приложении нет рекурсивных вызовов или что инструмент имеет представление о самой глубокой рекурсии (возможно, вы сказали об этом).
Набор инструментов для реинжиниринга программного обеспечения DMS отвечает всем этим требованиям для программ на Си. См. http://www.semanticdesigns.com/Products/DMS/DMSToolkit.html Вам все еще необходимо настроить его для вычисления потребности в стеке путем сканирования графа вызовов и использования различных оценок размера.
Если вам нужен быстрый ответ, используйте трюк с заполнением стека. Если вам нужен ответ, который вы можете пересчитать после каждого изменения исходного кода, вам потребуется метод статического анализа.
Я работаю над этой проблемой прямо сейчас - то есть аналитическое вычисление размера стека. Очевидно, это будет очень рекурсивный кусок кода, потому что вызов функции может иметь индексированный массив в качестве одного или нескольких своих аргументов, а один или несколько индексов массива могут включать вызовы функций!!
Тем не менее, пара реализаций позволяет немного облегчить сложность:
(1) При использовании высокоуровневого языкового компилятора указатель стека в конце выполнения каждого оператора / строки кода должен быть в том же месте, что и в начале. (По крайней мере, это было бы хорошим правилом для наблюдения, иначе у вас будут проблемы!)
(2) Указатель стека после возврата из каждого вызова функции или подпрограммы должен быть таким же, как и до вызова. Следовательно, максимальный размер стека - это максимальный размер всех стеков в программе для максимального значения стека, достигнутого в каждом операторе. (По крайней мере, это было бы хорошим правилом для наблюдения, иначе у вас будут проблемы!)
Конечно, оператор может включать в себя рекурсивные проблемы, о которых я упоминал выше, но, по крайней мере, проблема определения максимального размера стека для всей программы сводится к тому, чтобы найти максимальное требование стека для каждого оператора, а затем выбрать максимальное из них.
Это не может быть завершено, пока все вызываемые функции также не будут скомпилированы. Поэтому я генерирую файл для каждого скомпилированного модуля, в котором записывается количество стеков для каждого оператора (в основном это пиковое значение перед каждым вызовом функции и значение непосредственно перед каждым вызовом функции (исключая любые пока неизвестные дополнения к стековому размеру, вызванные функцией). вызов) и задействованные имена функций. Затем я ретроспективно обрабатываю эти файлы с помощью рекурсивной процедуры, после того как все функции скомпилированы, для определения максимального размера стека.
К счастью, кроме рекурсивных процедур, максимально возможное требование к размеру стека не зависит от потока программы, хотя в типичном потоке (который зависит от данных) этот максимально возможный размер стека может никогда не быть достигнут.
Пример: Предположим, что функция 1 вызывает функцию 2, и поток программы обоих зависит от значения данных X. Предположим, существует диапазон X, который заставляет функцию 1 выполнить ее худший оператор, который включает в себя вызов функции 2, которая не выполняется его наихудший случай для того же диапазона X. Поскольку мы вычислили максимально возможный размер стека, используя наихудшие случаи для функции 1 и функции 2 одновременно, мы могли переоценить размер стека. По крайней мере, мы допустили ошибку.
Мне нравится давать подпрограммам прерывания свое собственное стековое пространство в стеке ОС, если они им нужны, чтобы они не добавляли требований к программному стеку, кроме адреса возврата из прерывания
- Никогда не используйте рекурсивные или рекурсивные алгоритмы. (Остерегайтесь библиотек регулярных выражений)
- Не используйте массивы, всегда используйте malloc().
- Не используйте alloca(), некоторые компиляторы даже содержат ошибки в этой функции.
Затем вручную изучите часть кода и найдите, где использование стека, вероятно, является самым высоким (помните, я сказал, что нет массивов)
- Проверьте использование стека на предполагаемой высшей точке в самом коде, войдите в интерфейс отладчика.
- Поместите крышку на основе предполагаемого использования стека с этой крышкой на месте. например, ограничить количество подключений к серверу.