Constrained-Resource Programming

1Why malloc is banned

MISRA C, JPL's flight rules, and most automotive and medical standards forbid dynamic allocation after initialization. Four reasons, all of which week 19's desktop allocator gets away with and an embedded one does not.

Fragmentation is the decisive one. A long-running device allocating and freeing different sizes eventually has plenty of free memory in pieces too small to use. On a desktop the process restarts; a device in the field does not.

The replacement is to allocate everything at startup and never release it — or to use fixed-size pools, where fragmentation is impossible by construction.

2Static allocation and pools

Static

#define MAX_SENSORS 8
static Sensor sensors[MAX_SENSORS];     /* .bss: exists from power-on */
static size_t sensor_count = 0;

Simple, provably bounded, and visible in the size output of week 52. The limit becomes a compile-time constant you can reason about, which is exactly the property the standards require.

A fixed-block pool

When objects come and go, a pool gives you allocation without fragmentation: every block is the same size, so any free block satisfies any request.

typedef struct Block { struct Block *next; } Block;

static uint8_t  pool_storage[POOL_BLOCKS * POOL_BLOCK_SIZE];
static Block   *free_list = NULL;

void pool_init(void)
{
    free_list = NULL;
    for (size_t i = 0; i < POOL_BLOCKS; i++) {
        Block *b = (Block *)&pool_storage[i * POOL_BLOCK_SIZE];
        b->next = free_list;                 /* push onto the free list */
        free_list = b;
    }
}

void *pool_alloc(void)                       /* O(1), always */
{
    if (free_list == NULL) return NULL;
    Block *b = free_list;
    free_list = b->next;
    return b;
}

void pool_free(void *p)                      /* O(1), always */
{
    Block *b = p;
    b->next = free_list;
    free_list = b;
}

The free list lives inside the free blocks — a block is either in use or holding a next pointer, never both. That costs no extra memory and is the standard trick.

Both operations are a handful of instructions with no loop, so the timing is identical every call. That determinism is worth as much as the absence of fragmentation.

If an interrupt can allocate, the list manipulation needs week 51's critical section — it is a read-modify-write on a shared pointer.

The ring buffer

For streams rather than objects, a ring buffer allocates nothing at all. Week 51 used one between an ISR and the main loop; it is the general answer for bounded queues on a device.

3Fixed-point arithmetic

Many microcontrollers have no floating-point unit, so a single float multiplication becomes a library call of hundreds of cycles and several kilobytes of linked code.

Fixed point represents a fraction as an integer with an implied binary point. Q16.16 uses 32 bits: 16 for the integer part, 16 for the fraction.

typedef int32_t q16_t;

#define Q16_SHIFT 16
#define Q16_ONE   (1 << Q16_SHIFT)

#define INT_TO_Q16(n)   ((q16_t)((n) * Q16_ONE))
#define Q16_TO_INT(q)   ((int32_t)((q) >> Q16_SHIFT))
#define FLOAT_TO_Q16(f) ((q16_t)((f) * Q16_ONE))     /* compile time only */

static inline q16_t q16_add(q16_t a, q16_t b) { return a + b; }

static inline q16_t q16_mul(q16_t a, q16_t b)
{
    return (q16_t)(((int64_t)a * b) >> Q16_SHIFT);   /* 64-bit intermediate */
}

static inline q16_t q16_div(q16_t a, q16_t b)
{
    return (q16_t)((((int64_t)a) << Q16_SHIFT) / b);
}

Addition and subtraction are plain integer operations. Multiplication needs the 64-bit intermediate: two Q16.16 values multiply to Q32.32, and the shift brings it back. Omit the cast and the product overflows 32 bits for any operands above about 128.

Use fixed point when the range of your values is known — sensor readings, percentages, PID coefficients — and floating point when it is not. The uniform precision is often an advantage: a Q16.16 value has the same absolute resolution at 1000 as at 0.001, which a float does not.

4Code size

-Os                      # optimize for size instead of speed
-ffunction-sections -fdata-sections
-Wl,--gc-sections        # discard anything unreferenced
-flto                    # link-time optimization, across files

The section flags matter more than they look: without them the linker's unit of granularity is the whole object file, so one used function drags in every other function in that file.

Trading flash for RAM and cycles is the characteristic embedded move: a 256-entry sine table costs 512 bytes of flash and turns a library call into an array index.

Measure rather than guess — week 52's map file and nm --size-sort will usually show one or two symbols dominating.

5Surviving failure

Low power

for (;;) {
    if (work_pending) { do_work(); }
    else              { __asm__ volatile ("wfi"); }   /* wait for interrupt */
}

wfi halts the core until an interrupt arrives. On a battery device this is the difference between weeks and years — a busy-wait loop draws full current doing nothing. Week 51's interrupt-driven design is what makes it possible.

The watchdog

A hardware timer that resets the device unless the software periodically tells it not to. If the program hangs, the watchdog restarts it.

watchdog_enable(2000);              /* reset if not fed within 2 s */

for (;;) {
    do_work();
    watchdog_feed();                /* only on the healthy path */
}

Fault handlers

Week 49's default handler was an infinite loop. On a real product it should record what happened, because a device in the field cannot be attached to a debugger.

void hard_fault_handler(void)
{
    /* The processor stacked eight registers; recover the PC. */
    uint32_t *frame;
    __asm__ volatile ("mrs %0, msp" : "=r"(frame));

    crash_log.magic    = CRASH_MAGIC;
    crash_log.pc       = frame[6];      /* where it faulted */
    crash_log.lr       = frame[5];      /* who called it */
    crash_log.psr      = frame[7];
    crash_log.count++;

    system_reset();
}

Place crash_log in a region the linker script marks NOLOAD and the startup code does not clear, and it survives the reset. On the next boot the program can report the faulting address — often enough to identify the bug from the map file alone.

6Worked example: pool, fixed point, and measurement

/* constrained.c */
#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>

/* ---------- UART (weeks 50, 52) ---------- */
#define UART0_DR (*(volatile uint32_t *)0x4000C000u)
#define UART0_FR (*(volatile uint32_t *)0x4000C018u)

static void putc_raw(char c)
{
    while (UART0_FR & (1u << 5)) { }
    UART0_DR = (uint32_t)(unsigned char)c;
}
static void puts_raw(const char *s)
{
    for (; *s; s++) { if (*s == '\n') putc_raw('\r'); putc_raw(*s); }
}
static void put_int(int32_t v)
{
    char t[12]; int i = 0;
    if (v < 0) { putc_raw('-'); v = -v; }
    if (!v) { putc_raw('0'); return; }
    while (v) { t[i++] = (char)('0' + v % 10); v /= 10; }
    while (i) putc_raw(t[--i]);
}

/* ---------- fixed point, Q16.16 ---------- */

typedef int32_t q16_t;
#define Q16_SHIFT 16
#define Q16_ONE   (1 << Q16_SHIFT)
#define INT_TO_Q16(n) ((q16_t)((n) * Q16_ONE))

static inline q16_t q16_mul(q16_t a, q16_t b)
{
    return (q16_t)(((int64_t)a * b) >> Q16_SHIFT);
}
static inline q16_t q16_div(q16_t a, q16_t b)
{
    return (q16_t)((((int64_t)a) << Q16_SHIFT) / b);
}

/* Print a Q16.16 with three decimal places, no floating point. */
static void put_q16(q16_t q)
{
    if (q < 0) { putc_raw('-'); q = -q; }
    put_int(q >> Q16_SHIFT);
    putc_raw('.');
    uint32_t frac = (uint32_t)(q & 0xFFFFu);
    frac = (frac * 1000u) >> Q16_SHIFT;          /* to thousandths */
    if (frac < 100) putc_raw('0');
    if (frac < 10)  putc_raw('0');
    put_int((int32_t)frac);
}

/* ---------- a fixed-block pool ---------- */

#define POOL_BLOCKS     8
#define POOL_BLOCK_SIZE 32

typedef struct Block { struct Block *next; } Block;

static uint8_t pool_storage[POOL_BLOCKS * POOL_BLOCK_SIZE];
static Block  *free_list;
static uint32_t pool_in_use;
static uint32_t pool_peak;

static void pool_init(void)
{
    free_list = NULL;
    for (size_t i = 0; i < POOL_BLOCKS; i++) {
        Block *b = (Block *)(void *)&pool_storage[i * POOL_BLOCK_SIZE];
        b->next = free_list;
        free_list = b;
    }
    pool_in_use = pool_peak = 0;
}

static void *pool_alloc(void)
{
    if (free_list == NULL) return NULL;        /* exhausted, not undefined */
    Block *b = free_list;
    free_list = b->next;
    pool_in_use++;
    if (pool_in_use > pool_peak) pool_peak = pool_in_use;
    return b;
}

static void pool_free(void *p)
{
    if (p == NULL) return;
    Block *b = p;
    b->next = free_list;
    free_list = b;
    pool_in_use--;
}

/* ---------- a ring buffer: no allocation at all ---------- */

#define RING_SIZE 16
typedef struct {
    uint8_t data[RING_SIZE];
    uint8_t head, tail;
} Ring;

static bool ring_push(Ring *r, uint8_t v)
{
    uint8_t next = (uint8_t)((r->head + 1u) % RING_SIZE);
    if (next == r->tail) return false;          /* full: refuse, not grow */
    r->data[r->head] = v;
    r->head = next;
    return true;
}

static bool ring_pop(Ring *r, uint8_t *out)
{
    if (r->tail == r->head) return false;
    *out = r->data[r->tail];
    r->tail = (uint8_t)((r->tail + 1u) % RING_SIZE);
    return true;
}

/* ---------- a lookup table, in flash ---------- */

/* sin(x) scaled to Q16.16, 16 entries over a quarter turn.
   const keeps it in .rodata — week 52. */
static const q16_t sine_table[17] = {
        0,  6423, 12785, 19024, 25079, 30893, 36409, 41575,
    46340, 50660, 54491, 57797, 60547, 62714, 64276, 65220, 65536
};

static q16_t q16_sin_quarter(uint8_t index)     /* 0..16 */
{
    return sine_table[index > 16 ? 16 : index];
}

/* ---------- a PID step, entirely in fixed point ---------- */

typedef struct {
    q16_t kp, ki, kd;
    q16_t integral, previous;
} Pid;

static q16_t pid_step(Pid *p, q16_t setpoint, q16_t measured)
{
    q16_t error = setpoint - measured;
    p->integral += error;

    q16_t derivative = error - p->previous;
    p->previous = error;

    return q16_mul(p->kp, error)
         + q16_mul(p->ki, p->integral)
         + q16_mul(p->kd, derivative);
}

int main(void)
{
    puts_raw("\n=== constrained resources ===\n");

    /* --- pool --- */
    puts_raw("\nfixed-block pool: ");
    put_int(POOL_BLOCKS); puts_raw(" blocks of ");
    put_int(POOL_BLOCK_SIZE); puts_raw(" bytes\n");

    pool_init();
    void *held[POOL_BLOCKS + 2];
    size_t got = 0;

    for (size_t i = 0; i < POOL_BLOCKS + 2; i++) {
        held[i] = pool_alloc();
        puts_raw("  alloc "); put_int((int32_t)i);
        puts_raw(held[i] ? " -> ok\n" : " -> refused (pool exhausted)\n");
        if (held[i]) got++;
    }

    puts_raw("  succeeded: "); put_int((int32_t)got);
    puts_raw(", peak in use: "); put_int((int32_t)pool_peak); puts_raw("\n");

    for (size_t i = 0; i < POOL_BLOCKS + 2; i++) pool_free(held[i]);
    puts_raw("  after freeing all, in use: ");
    put_int((int32_t)pool_in_use); puts_raw("\n");

    puts_raw("  allocation is O(1) every time — no search, no coalescing,\n");
    puts_raw("  and fragmentation is impossible: every block is the same size\n");

    /* --- ring buffer --- */
    puts_raw("\nring buffer of ");
    put_int(RING_SIZE); puts_raw(" bytes, allocating nothing\n");

    Ring r = { .head = 0, .tail = 0 };
    int pushed = 0;
    for (uint8_t v = 1; v <= 20; v++) {
        if (ring_push(&r, v)) pushed++;
    }
    puts_raw("  pushed "); put_int(pushed);
    puts_raw(" of 20; the rest were refused\n  drained: ");
    uint8_t v;
    while (ring_pop(&r, &v)) { put_int(v); putc_raw(' '); }
    puts_raw("\n");

    /* --- fixed point --- */
    puts_raw("\nfixed point, Q16.16\n");

    q16_t a = INT_TO_Q16(3);
    q16_t b = q16_div(INT_TO_Q16(1), INT_TO_Q16(4));    /* 0.25 */

    puts_raw("  a        = "); put_q16(a); puts_raw("\n");
    puts_raw("  b        = "); put_q16(b); puts_raw("\n");
    puts_raw("  a * b    = "); put_q16(q16_mul(a, b)); puts_raw("\n");
    puts_raw("  a / b    = "); put_q16(q16_div(a, b)); puts_raw("\n");
    puts_raw("  a + b    = "); put_q16(a + b); puts_raw("\n");
    puts_raw("  resolution is 1/65536 everywhere, unlike a float\n");

    /* --- lookup table --- */
    puts_raw("\nsine from a flash table (no library call)\n");
    for (uint8_t i = 0; i <= 16; i += 4) {
        puts_raw("  sin("); put_int(i * 90 / 16); puts_raw(" deg) = ");
        put_q16(q16_sin_quarter(i));
        puts_raw("\n");
    }
    puts_raw("  17 entries = 68 bytes of flash, zero RAM\n");

    /* --- PID --- */
    puts_raw("\na PID controller in fixed point\n");
    Pid pid = {
        .kp = INT_TO_Q16(1),
        .ki = q16_div(INT_TO_Q16(1), INT_TO_Q16(10)),
        .kd = q16_div(INT_TO_Q16(1), INT_TO_Q16(20)),
        .integral = 0, .previous = 0
    };
    q16_t setpoint = INT_TO_Q16(100);
    q16_t measured = 0;

    for (int step = 0; step < 6; step++) {
        q16_t out = pid_step(&pid, setpoint, measured);
        measured += q16_div(out, INT_TO_Q16(10));      /* crude plant model */
        puts_raw("  step "); put_int(step);
        puts_raw(": output "); put_q16(out);
        puts_raw(", measured "); put_q16(measured);
        puts_raw("\n");
    }
    puts_raw("  no FPU, no soft-float library, constant timing\n");

    for (;;) {
        __asm__ volatile ("wfi");        /* sleep until an interrupt */
    }
}

arm-none-eabi-gcc -mcpu=cortex-m3 -mthumb \
    -ffreestanding -nostdlib -Os -Wall -Wextra -g \
    -ffunction-sections -fdata-sections -Wl,--gc-sections \
    -T firmware.ld -Wl,-Map=firmware.map \
    -o firmware.elf startup.c constrained.c

arm-none-eabi-size firmware.elf
qemu-system-arm -M lm3s6965evb -nographic -kernel firmware.elf

Measure what each choice costs

Fixed point against float. Replace the Q16.16 arithmetic with float and rebuild:

arm-none-eabi-size firmware.elf
arm-none-eabi-nm --size-sort -S firmware.elf | tail -15

The image typically grows by two to six kilobytes, and the largest new symbols are __aeabi_fmul, __aeabi_fdiv, and friends — the soft-float library, linked in because the Cortex-M3 has no FPU. On a part with 32 KB of flash that is a fifth of the budget for arithmetic you did not need.

Optimization level.

for opt in -O0 -O1 -O2 -O3 -Os; do
    arm-none-eabi-gcc -mcpu=cortex-m3 -mthumb -ffreestanding -nostdlib \
        $opt -ffunction-sections -fdata-sections -Wl,--gc-sections \
        -T firmware.ld -o /tmp/f.elf startup.c constrained.c
    printf "%-4s " $opt; arm-none-eabi-size /tmp/f.elf | tail -1
done

-Os is usually smallest and -O3 largest, sometimes by a factor of two. On a desktop the difference is irrelevant; here it decides whether the firmware fits.

Section garbage collection. Drop -ffunction-sections -fdata-sections -Wl,--gc-sections and compare. Unused functions that were previously discarded now remain, because the linker's granularity fell back to whole object files.

Exhaust the pool deliberately

The program requests ten blocks from a pool of eight. The ninth and tenth are refused — a NULL return the caller must handle, exactly as malloc would, but with a bound you can state at compile time. Raising POOL_BLOCKS changes a number in .bss that size will report; there is no scenario in which the device runs out unexpectedly.

Check the fixed-point overflow

q16_t big = INT_TO_Q16(200);
puts_raw("200 * 200 = "); put_q16(q16_mul(big, big));

40 000 does not fit in the 16-bit integer part, so the result is wrong. Fixed point has a fixed range and overflows silently — the price of its speed. Know your value range before choosing the format, and consider Q8.24 or Q24.8 when the balance differs.

Then remove the (int64_t) cast from q16_mul and try 3 * 0.25 again: the 32-bit product overflows before the shift, and the answer is nonsense for operands far smaller than the format's stated range.

7Common mistakes

9Where this leads

Week 54 introduces an RTOS, which offers tasks, queues, and semaphores — the general versions of this week's pool and ring buffer — and asks when the superloop you have been writing should be replaced by a scheduler.