72. Отладка и динамические структуры данных

Две темы, которые на компьютере и на камне выглядят по-разному.

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

Динамические структуры — списки, очереди, деревья, которые растут по мере работы. На компьютере их строят на malloc. В проекте Keil куча по умолчанию — полкилобайта, и главный вопрос раздела — чем её заменить. Все размеры сняты с настоящих образов, а ошибки работы с памятью — пойманы инструментом.

Как это называется в документации

Оригинал	Перевод
tracing, logging	трассировка, журнал
breakpoint, watchpoint	точка останова, точка наблюдения
heap, dynamic allocation	куча, динамическое выделение памяти
memory leak	утечка памяти
use-after-free, double free	обращение после освобождения, двойное освобождение
buffer overflow	выход за границу буфера
sanitizer	санитайзер, инструмент проверки во время работы
stack (LIFO), queue (FIFO)	стек, очередь
linked list, node	связный список, узел
memory pool, free list	пул памяти, список свободных
binary search tree	двоичное дерево поиска
traversal (pre-, in-, post-order)	обход дерева

72.1 Отладка: три способа

Трассировка — печать того, что происходит. Самый старый и самый надёжный приём: вывести значение переменной и посмотреть, совпало ли оно с ожидаемым. На камне печать идёт в последовательный порт (раздел 16.6) или в отладочный вывод SWO (раздел 21). Ему нужен один вывод — PB3 у F1 и F4, — и программу он почти не тормозит. У Cortex-M0 и M0+ такого канала нет.

Отладочную печать удобно делать макросом, который исчезает в рабочей сборке (раздел 71.10):

#ifdef DEBUG
#define TRACE(...) printf(__VA_ARGS__)
#else
#define TRACE(...) ((void)0)
#endif

Журнал — та же печать, но с уровнями важности и в отдельный поток. На компьютере сообщения об ошибках пишут в stderr, и их можно отделить от обычного вывода: prog 2> errors.txt. На камне журнал часто пишут в кольцевой буфер в ОЗУ (раздел 32) и выгружают по запросу — так он не тормозит работу, а последние события сохраняются.

Отладчик — остановка программы в нужном месте, просмотр переменных и памяти, пошаговое выполнение. На камне он работает через отладочный интерфейс, и у него есть то, чего нет у печати: он видит состояние в момент отказа процессора. Как читать отказ и следить за стеком — разделы 35.2 и 35.4.

72.2 Динамическая память

Куча — область памяти, из которой программа берёт блоки во время работы:

Четыре правила, без которых работать с кучей нельзя:

• результат проверяют на NULL — память может кончиться;
• realloc при неудаче возвращает NULL, а старый блок сохраняет. Запись p = realloc(p, n) при неудаче теряет последний указатель на блок. Правильно — через временную переменную;
• после free указатель обнуляют: free(p); p = NULL;. Иначе он висячий (раздел 67.10);
• каждому malloc — ровно один free.

72.3 Четыре ошибки и как их ловят

Ни одна из них не видна при компиляции, и все проявляются не там, где сделаны. На компьютере их ловит AddressSanitizer — ключ -fsanitize=address у GCC и clang. Каждая из четырёх ошибок в коротком примере поймана им с точным диагнозом: heap-use-after-free, heap-buffer-overflow, attempting double-free и отчёт об утечке «Direct leak of 100 bytes» с указанием строки, где блок был выделен.

На камне санитайзера нет. Отсюда практический приём: логику, не зависящую от железа, — разбор протокола, фильтры, структуры данных — отлаживают на компьютере, с санитайзером, а на камень переносят уже проверенный код. О том, как это устроить, — раздел 79.5.

72.4 Куча на микроконтроллере

Сколько кучи есть на камне? Зависит от среды. В проекте Keil — столько, сколько указано в стартовом файле. В стартовых файлах F103 и F407 из пака Keil:

Stack_Size      EQU     0x00000400     ; 1024 байта стека
Heap_Size       EQU     0x00000200     ; 512 байт кучи

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

В проекте CubeIDE иначе. _Min_Heap_Size = 0x200 в скрипте компоновки — только проверка минимума, а _sbrk из sysmem.c отдаёт malloc всю память от конца .bss до резерва под стек (раздел 4б.5). Там malloc кончается позже, зато куча без предупреждения подходит вплотную к стеку.

Цена в коде. Образ с настоящим стартовым файлом F103:

Урезанная библиотека microlib обходится почти втрое дешевле, но и умеет меньше.

И любопытная деталь: если выделенный блок никуда не уходит из функции, компилятор выбрасывает malloc и free совсем — функция, выделявшая массив, свелась к возврату единицы. Он вправе так делать: результат от этого не меняется.

Главное же — не размер, а поведение. Куча фрагментируется: после множества выделений и освобождений свободная память разбита на куски, и большой блок не выделяется, хотя в сумме места хватает. Время malloc непредсказуемо. А обработать отказ в выделении посреди работы устройства обычно негде. Поэтому правило для камня (разделы 11.4 и 25): выделять память один раз при старте и не освобождать, а для того, что появляется и исчезает, — пулы. И ещё: malloc и free стандартной библиотеки нельзя вызывать из прерывания, а из нескольких задач — только под защитой: куча общая, и два одновременных вызова её разрушат. В ОСРВ для этого есть свои функции выделения (раздел 25). С пулом из 72.8 то же: если узлы берут и прерывание, и программа, pool_get и pool_put выполняют с запрещёнными прерываниями.

72.5 Стек и очередь

Две самые частые структуры:

• стек (LIFO) — последним положили, первым взяли: положили 1…5, забрали 5 4 3 2 1;
• очередь (FIFO) — первым положили, первым взяли: 1 2 3 4 5.

Стек на связном списке — добавление и изъятие с головы, обе операции мгновенны:

typedef struct node { int value; struct node *next; } node;

void push(node **top, int v)
{
    node *n = malloc(sizeof *n);
    n->value = v;
    n->next = *top;
    *top = n;
}

Указатель на указатель здесь нужен, чтобы функция могла изменить сам указатель на вершину (раздел 67.7).

Для очереди важна деталь. Если хранить только голову, каждое добавление идёт в конец по всему списку: тысяча добавлений — это 498 501 шаг. С отдельным указателем на хвост добавление мгновенно, шагов ноль. Структура данных — это не только узлы, но и то, какие указатели на них держать.

На камне стек и очередь почти всегда делают на массиве фиксированного размера: очередь — кольцевым буфером (раздел 32), очередь между задачами — средствами ОСРВ (раздел 27).

72.6 Динамический массив

Массив, который растёт по мере надобности, держат с запасом и при заполнении удваивают:

if (n == cap) {
    int *bigger = realloc(arr, 2 * cap * sizeof *arr);
    if (!bigger)
        return -1;              /* arr цел; новый элемент не добавлен */
    arr = bigger;
    cap *= 2;
}
arr[n++] = value;

Сто элементов, начиная с ёмкости 16, потребовали всего трёх перевыделений: 16 → 32 → 64 → 128. Удвоение, а не прибавление по одному, делает рост дешёвым: копировать приходится редко.

72.7 Связный список

Каждый узел хранит данные и указатель на следующий; последний указывает на NULL:

for (node *p = head; p != NULL; p = p->next)
    printf("%d ", p->value);

Добавить в начало — мгновенно, найти элемент — пройти список. Удаление требует помнить предыдущий узел. Чтобы не обрабатывать отдельно пустой список, иногда держат заглавный узел без данных: тогда указатель на начало списка не меняется никогда.

Освобождают список по одному узлу, сохраняя next до free:

while (head) {
    node *next = head->next;
    free(head);
    head = next;                 /* а не head = head->next после free */
}

72.8 Пул узлов вместо malloc

Как получить список без кучи? Заранее выделить массив узлов и держать свободные в списке свободных:

#define POOL 8
static node pool[POOL];
static node *free_list;

void pool_init(void)
{
    for (int i = 0; i < POOL; i++) {
        pool[i].next = free_list;
        free_list = &pool[i];
    }
}

node *pool_get(void)
{
    node *n = free_list;
    if (n) free_list = n->next;
    return n;                        /* NULL, если пул пуст */
}

void pool_put(node *n)
{
    n->next = free_list;
    free_list = n;
}

Пул на 8 узлов выдаёт ровно 8, на девятый запрос возвращает NULL, а возвращённый узел выдаёт снова. Выделение и возврат — несколько команд, время всегда одинаковое, фрагментации нет, а объём памяти виден ещё при компоновке. Именно так устроено статическое создание объектов в ОСРВ (раздел 26.8).

72.9 Двоичное дерево поиска

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

while (t) {
    if (key == t->key) return t;
    t = key < t->key ? t->left : t->right;
}

Ключи 50, 30, 70, 20, 40, 60, 80 дают дерево высотой 3: любой ключ находится не больше чем за три сравнения, 60 — ровно за три, а отсутствие 65 выясняется тоже за три.

Но те же ключи, вставленные по порядку, дают дерево, выродившееся в список, — высотой 7, и поиск наибольшего ключа, 80, занимает семь шагов. Всё преимущество дерева исчезло. Поэтому в серьёзных применениях деревья балансируют, а о том, как оценивать такие вещи, — раздел 76.

Обходы дерева — корень 1, слева 2 с детьми 3 и 4, справа 5:

Симметричный обход дерева поиска выдаёт ключи по возрастанию — это способ отсортировать. А обратный удобен для освобождения: узел удаляется после своих детей.

Все операции с деревом естественно пишутся рекурсией — и на камне это значит вопрос о глубине стека (раздел 66.7). Для выродившегося дерева глубина рекурсии равна числу узлов.

72.10 Грабли

malloc на камне вернул NULL почти сразу. Куча в проекте Keil — 512 байт; размер задан в стартовом файле.

Программа месяцами работала и начала отказывать. Утечка или фрагментация кучи.

p = realloc(p, n) потерял данные. При неудаче realloc вернул NULL, а старый указатель перезаписан.

Данные «портятся» через некоторое время после освобождения. Обращение по висячему указателю: после free его не обнулили.

Куча «сломалась» в случайном месте. Запись за границу блока или двойной free. На компьютере — AddressSanitizer.

Освобождение списка падает. Обращение к head->next после free(head).

Очередь тормозит на больших объёмах. Нет указателя на хвост: каждое добавление идёт через весь список.

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

Рекурсивный обход дерева переполнил стек. Глубина рекурсии — высота дерева; у выродившегося — число узлов.

Прошивка выросла на полкилобайта от одного malloc. Функции кучи из стандартной библиотеки; microlib обходится почти втрое дешевле.

72.11 Итоги

• Три способа отладки: трассировка, журнал, отладчик. На камне печать идёт в порт или отладочный канал, журнал — в кольцевой буфер.
• malloc, calloc, realloc, free: результат проверяют на NULL, realloc — через временную переменную, после free указатель обнуляют.
• Четыре ошибки с памятью — обращение после free, выход за границу, двойной free, утечка — на компьютере ловит AddressSanitizer; логику отлаживают там, а на камень переносят проверенный код.
• Куча в стартовых файлах Keil для F103 и F407 — 512 байт, стек — 1024; в проекте CubeIDE malloc берёт всё свободное ОЗУ до резерва стека.
• malloc и free добавляют 576 байт кода со стандартной библиотекой и 200 с microlib; если блок не уходит из функции, компилятор выбрасывает их совсем.
• На камне память выделяют при старте, а для переменных объектов — пулы: время постоянное, фрагментации нет.
• Очереди нужен указатель на хвост: без него 1000 добавлений — 498 501 шаг.
• Динамический массив удваивают: 100 элементов с 16 — за три перевыделения.
• Дерево поиска из 7 ключей — высота 3; из тех же ключей по порядку — список высотой 7.

Дальше: раздел 73 «Измерение времени и производительности».