72. Debugging and dynamic data structures

Two topics that look different on a computer and on a chip.

Debugging. On a computer you have a debugger, sanitizers, gigabytes for logs. On a chip — a two-wire debugger and a serial port. The techniques are the same, but you have to use them more sparingly.

Dynamic structures are lists, queues and trees that grow as the program runs. On a computer they are built on malloc. In a Keil project the heap is half a kilobyte by default, and the main question of this section is what to replace it with. All sizes are taken from real images, and the memory errors were caught by a tool.

Terms used in the documentation

Term	Meaning
tracing, logging	printing what happens, a record of events
breakpoint, watchpoint	a stop at code, a stop on a data access
heap, dynamic allocation	the heap, taking memory at run time
memory leak	memory that is never returned
use-after-free, double free	access after release, releasing twice
buffer overflow	going past the end of a buffer
sanitizer	a tool that checks the program while it runs
stack (LIFO), queue (FIFO)	stack, queue
linked list, node	linked list, node
memory pool, free list	memory pool, list of free blocks
binary search tree	binary search tree
traversal (pre-, in-, post-order)	visiting every node of a tree

72.1 Debugging: three ways

Tracing is printing what is going on. The oldest and most reliable technique: print the value of a variable and see whether it matches what you expected. On a chip the printing goes to a serial port (section 16.6) or to the SWO debug output (section 21). SWO needs one pin — PB3 on the F1 and F4 — and hardly slows the program down. The Cortex-M0 and M0+ have no such channel.

Debug printing is conveniently done with a macro that disappears in the release build (section 71.10):

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

A log is the same printing, but with severity levels and into a separate stream. On a computer error messages are written to stderr, and they can be separated from normal output: prog 2> errors.txt. On a chip the log is often written to a ring buffer in RAM (section 32) and dumped on request — that way it does not slow the work down, and the latest events are kept.

A debugger stops the program at the right place, shows variables and memory, and executes step by step. On a chip it works through the debug interface, and it has something printing does not: it sees the state at the moment of a processor fault. How to read a fault and watch the stack — sections 35.2 and 35.4.

72.2 Dynamic memory

The heap is a memory area from which the program takes blocks while it runs:

Four rules without which you cannot work with the heap:

• check the result for NULL — memory can run out;
• on failure realloc returns NULL and keeps the old block. Writing p = realloc(p, n) loses the last pointer to the block on failure. The right way is through a temporary variable;
• after free, set the pointer to null: free(p); p = NULL;. Otherwise it is dangling (section 67.10);
• every malloc gets exactly one free.

72.3 Four errors and how they are caught

None of them is visible at compile time, and all of them show up somewhere other than where they were made. On a computer they are caught by AddressSanitizer — the option -fsanitize=address in GCC and clang. Each of the four errors in a short example is caught by it with an exact diagnosis: heap-use-after-free, heap-buffer-overflow, attempting double-free, and a leak report "Direct leak of 100 bytes" naming the line where the block was allocated.

There is no sanitizer on the chip. Hence a practical technique: logic that does not depend on the hardware — protocol parsing, filters, data structures — is debugged on a computer, with the sanitizer, and code that has already been checked is moved to the chip. How to set this up is described in section 79.5.

72.4 The heap on a microcontroller

How much heap does the chip have? It depends on the environment. In a Keil project — as much as is set in the startup file. In the F103 and F407 startup files from the Keil pack:

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

Half a kilobyte. A program that allocated memory by the megabyte on a computer will run out on the chip at its very first list. The size is changed right here — but first it is worth deciding whether you need a heap at all.

A CubeIDE project is different. _Min_Heap_Size = 0x200 in the linker script is only a minimum check, and _sbrk from sysmem.c gives malloc all the memory from the end of .bss up to the space reserved for the stack (section 4б.5). There malloc runs out later, but the heap grows right up to the stack without warning.

The cost in code. An image with the real F103 startup file:

The reduced microlib library is almost three times cheaper, but it can also do less.

And a curious detail: if the allocated block never leaves the function, the compiler removes malloc and free altogether — a function that allocated an array came down to returning one. It is allowed to do this: the result does not change.

But the main thing is not the size, it is the behaviour. The heap fragments: after many allocations and releases the free memory is broken into pieces, and a large block cannot be allocated although there is enough space in total. The time of malloc is unpredictable. And there is usually nowhere to handle an allocation failure in the middle of the device's work. So the rule for the chip (sections 11.4 and 25): allocate memory once at startup and never free it, and for things that come and go, use pools. One more thing: malloc and free from the standard library must not be called from an interrupt, and from several tasks only under protection: the heap is shared, and two simultaneous calls will corrupt it. An RTOS has its own allocation functions for this (section 25). The same goes for the pool from 72.8: if nodes are taken by both an interrupt and the program, run pool_get and pool_put with interrupts disabled.

72.5 Stack and queue

The two most common structures:

• a stack (LIFO) — last in, first out: put in 1…5, took out 5 4 3 2 1;
• a queue (FIFO) — first in, first out: 1 2 3 4 5.

A stack on a linked list — adding and removing at the head, both operations are instant:

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

The pointer to a pointer is needed here so that the function can change the top pointer itself (section 67.7).

For a queue one detail matters. If you keep only the head, every addition walks the whole list to the end: a thousand additions take 498501 steps. With a separate tail pointer an addition is instant, zero steps. A data structure is not only the nodes but also which pointers to them you keep.

On a chip a stack and a queue are almost always built on a fixed-size array: a queue as a ring buffer (section 32), a queue between tasks with RTOS facilities (section 27).

72.6 Dynamic array

An array that grows as needed is kept with spare room and, when it fills up, is doubled:

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

A hundred elements, starting from a capacity of 16, needed only three reallocations: 16 → 32 → 64 → 128. Doubling, rather than adding one at a time, makes growth cheap: copying is rarely needed.

72.7 Linked list

Each node stores data and a pointer to the next one; the last one points to NULL:

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

Adding at the head is instant; finding an element means walking the list. Removal requires remembering the previous node. To avoid handling an empty list separately, a header node without data is sometimes kept: then the pointer to the start of the list never changes.

A list is freed one node at a time, saving next before free:

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

72.8 A node pool instead of malloc

How do you get a list without a heap? Allocate an array of nodes in advance and keep the free ones in a free list:

#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;
}

A pool of 8 nodes hands out exactly 8, returns NULL on the ninth request, and hands out a returned node again. Taking and returning a node is a few instructions, the time is always the same, there is no fragmentation, and the amount of memory is visible already at link time. This is exactly how static object creation works in an RTOS (section 26.8).

72.9 Binary search tree

Each node has a key and two pointers: on the left — smaller keys, on the right — larger ones. Every search step discards half:

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

The keys 50, 30, 70, 20, 40, 60, 80 give a tree of height 3: any key is found in at most three comparisons, 60 in exactly three, and the absence of 65 is also established in three.

But the same keys inserted in order give a tree that has degenerated into a list — of height 7, and finding the largest key, 80, takes seven steps. All the advantage of the tree is gone. So in serious applications trees are balanced, and how to evaluate such things is covered in section 76.

Traversals of a tree — root 1, on the left 2 with children 3 and 4, on the right 5:

An in-order traversal of a search tree yields the keys in ascending order — this is a way to sort. And post-order is convenient for freeing: a node is deleted after its children.

All tree operations are naturally written with recursion — and on a chip this raises the question of stack depth (section 66.7). For a degenerate tree the recursion depth equals the number of nodes.

72.10 Pitfalls

malloc on the chip returned NULL almost immediately. The heap in a Keil project is 512 bytes; the size is set in the startup file.

The program ran for months and then started failing. A leak or heap fragmentation.

p = realloc(p, n) lost the data. On failure realloc returned NULL, and the old pointer was overwritten.

Data "goes bad" some time after being freed. Access through a dangling pointer: it was not set to null after free.

The heap "broke" at a random place. A write past the end of a block or a double free. On a computer — AddressSanitizer.

Freeing a list crashes. Accessing head->next after free(head).

The queue slows down on large volumes. There is no tail pointer: every addition walks the whole list.

The search tree is slow. The keys came in order, and the tree degenerated into a list.

A recursive tree traversal overflowed the stack. The recursion depth is the height of the tree; for a degenerate one, the number of nodes.

The firmware grew by half a kilobyte from a single malloc. The heap functions from the standard library; microlib is almost three times cheaper.

72.11 Summary

• Three ways to debug: tracing, a log, a debugger. On a chip printing goes to a port or a debug channel, the log to a ring buffer.
• malloc, calloc, realloc, free: check the result for NULL, use realloc through a temporary variable, set the pointer to null after free.
• The four memory errors — access after free, writing past the end, double free, a leak — are caught on a computer by AddressSanitizer; debug the logic there and move checked code to the chip.
• The heap in the Keil startup files for the F103 and F407 is 512 bytes, the stack 1024; in a CubeIDE project malloc takes all free RAM up to the stack reserve.
• malloc and free add 576 bytes of code with the standard library and 200 with microlib; if the block does not leave the function, the compiler removes them altogether.
• On a chip memory is allocated at startup, and for objects that come and go there are pools: constant time, no fragmentation.
• A queue needs a tail pointer: without it 1000 additions take 498501 steps.
• A dynamic array is doubled: 100 elements starting from 16 take three reallocations.
• A search tree of 7 keys has height 3; the same keys in order give a list of height 7.

Next: section 73 "Measuring time and performance".