Как определить максимальное использование стека?

Question

Какие методы доступны для определения оптимального размера стека для встроенной/ограниченной памяти системы? Если он слишком велик, память пропадает, что можно использовать в другом месте. Однако, если он слишком мал, то мы получим тезку этого веб-сайта ...

Чтобы попытаться перепрыгнуть начать вещи: Джек Ganssle говорится в The Art of Designing Embedded Systems что «С опытом, один учится стандарт, научный способ вычисления правильный размер для стека: выберите размер случайным образом и надейтесь ». Может ли кто-нибудь сделать лучше?

Был запрошен более конкретный пример. Итак, как насчет программы C, нацеленной на MSP430 MCU с 2 КБ ОЗУ с использованием IAR Embedded Workbench toolchain без операционной системы? Эта IDE может отображать содержимое стека и использование при использовании отладчика JTAG.

Answer 1

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

Это как раз то, как IAR IDE определяет количество используемого стека.

Answer 2

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

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

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; 
    // ... 
} 

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

void 
stack_measurement_function(void) 
{ 
    int a; 
    stack_bottom = min(stack_bottom, (char *)&a); 
    // ... 
} 

я использовал подход, аналогичный тому, что я описал для создания these charts.

Answer 3

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

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

Набор инструментов DMS Software Reengineering Toolkit отвечает всем этим требованиям для программ на C. См. http://www.semanticdesigns.com/Products/DMS/DMSToolkit.html Вам по-прежнему приходится настраивать его для вычисления потребности в стеке путем обхода графика вызовов и использования различных оценок размера.

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

Answer 4

• Не использовать рекурсию или рекурсивные алгоритмы когда-либо. (beware regex libraries)
• Не используйте массивы, всегда используйте malloc().
• Не используйте alloca(), некоторые компиляторы даже имеют ошибки в этой функции.

Затем осмотрите вручную ту часть кода, ищет, где использование стека, вероятно, самый высокий (помните, я сказал, не массивы)

• Проверьте использование стека на подозреваемыхвысокой точка в самом коде, войдите в интерфейс отладчика.
• Установите колпачок на основе предполагаемого использования стека с этой крышкой на месте. например ограничить соединения с сервером.

Answer 5

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

Однако несколько реализаций позволяют некоторое облегчение от сложности:

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

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

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

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

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

Пример: предположим, функция 1 вызывает функцию 2, и программный поток обоих зависит от значения данных X. Предположим, что существует диапазон X, который заставляет функцию 1 выполнять свой худший оператор, который включает в себя вызов функции 2, которая не выполняет его наихудший случай для того же диапазона X. Поскольку мы вычислили максимально возможный стекиз, используя одновременно наихудшие случаи как для функции 1, так и для функции 2, мы, возможно, переоценили стекизацию. По крайней мере, мы допустили ошибку.

Я хотел бы дать прерывание Подпрограммы свои собственные stackspace на стек ОС, если они нуждаются в каких-либо, поэтому они не добавляют требования стеки программы, кроме возврата из прерывания адреса