Embedded C and C++ Programming Questions

Decision Memo — object pool vs optimized dynamic allocator

Evaluation criteria

• Functional: peak allocation rate, typical object lifetimes, fragmentation risk
• Non‑functional: memory footprint, latency/jitter (worst‑case alloc/free), predictability for real‑time deadlines
• Risk & schedule: implementation time, test coverage required, debugging complexity
• Long‑term: maintainability, portability, extensibility (new object types), tooling/support

Preferred choice (short deadline)

• Choose object pools (fixed-size preallocated) as default.
• Reasons: deterministic worst‑case latency, minimal fragmentation, simpler to implement/test in C on constrained MCUs, low runtime overhead. Under tight schedule predictability and safety outweigh memory efficiency gains from a complex allocator.

Migration path

1. Start with per-type pools implemented as arrays + free‑list (O(1) alloc/free). Provide unified API (pool_alloc(pool_id), pool_free(ptr)).
2. Instrument usage: counters, high‑water marks, allocation sites logging.
3. After stability, if memory exhausted or many sizes needed, prototype an optimized dynamic allocator (segregated free lists or TLSF) in a separate module.
4. Swap via the unified API and run stress/soak tests; compare traces and latencies before cutover.

Mitigate long‑term maintainability risks

• Encapsulate allocation behind an allocator interface; keep pool implementation modular.
• Add automated unit + fault injection tests (double free, use‑after‑free).
• Document allocation budgets per feature and enforce code review rules for heap use.
• Monitor runtime metrics (heap/pool usage) in-field; keep fallback safe mode (reject new allocations) to preserve stability.

Example: implement pool as struct { void *blocks; uint16_t free_head; uint16_t block_size; uint16_t count; } with compile‑time asserts to avoid alignment issues.

Estimate (assumptions first)

• 32-bit embedded target: pointer = 4 bytes.
• sizeof(Node) = 4 (char*) + 1 (uint8_t) + 3 (padding) = 8 bytes.
• strdup allocates name bytes = length + 1 (NUL). average = 20 + 1 = 21 bytes.
• Per-malloc heap metadata/fragmentation overhead ≈ 16 bytes (simple allocator; adjust to your runtime).

Calculations for n = 100:

• Node array: 100 * 8 = 800 bytes
• Name payload: 100 * 21 = 2,100 bytes
• Per-name malloc overhead: 100 * 16 = 1,600 bytes
  Total ≈ 800 + 2,100 + 1,600 = 4,500 bytes (plus any allocator rounding/fragmentation).

Why overhead is high

• 100 separate strdup calls => 100 heap metadata blocks and alignment padding cause significant overhead and fragmentation.

Concrete changes (retain functionality: each Node has null-terminated name string and flags)

1. Single contiguous name slab (recommended)

• Allocate one big buffer for all names, copy names into it, store pointers into Node.
• Reduces per-name malloc overhead to one allocation.

Example:

// allocate nodes
Node *list = malloc(n * sizeof(Node));
// allocate slab
size_t slab_size = n * (max_name_len + 1); // or compute exact sum
char *slab = malloc(slab_size);
// fill names
char *p = slab;
for (i=0;i<n;i++) {
    strcpy(p, input_name[i]);
    list[i].name = p;
    p += strlen(p) + 1;
    list[i].flags = ...
}

Estimated memory: 800 (nodes) + 2,100 (names) + 16 (one slab malloc overhead) ≈ 2,916 bytes.

2. Inline/flexible-array per-node (if names vary and you want per-node allocation without strdup)

• Define struct with flexible array member and allocate one malloc per node sized to exact name length; removes separate strdup but still has per-node malloc overhead, so only slightly better than strdup.

3. Use a pool/arena allocator

• Implement a small arena that hands out name space with no per-string metadata; good for embedded determinism.

Trade-offs

• Single slab: fast, low overhead, but harder to free individual names; OK if lifetime is same.
• Flexible-array per-node: easier per-node free but still per-malloc overhead.
• Pool: middle ground for partial lifetime control and low overhead.

Recommendation: use single contiguous slab or arena for embedded targets to minimize heap metadata and fragmentation while keeping API unchanged.

Approach (brief)
Use boundary tags: each block has a header (size + used bit) and footer (size) only for free blocks to minimize overhead. Maintain a simple explicit free list (doubly-linked) stored in payload of free blocks to speed coalescing and reduce fragmentation. 8-byte alignment. Per-block overhead: 8 bytes header + 8 bytes footer only for free blocks; allocated blocks omit footer to save space (uses header only), but coalescing requires footer so we write footer when freeing.

Data layout

• Header: 8 bytes (size | used_bit)
• Footer (free blocks only): 8 bytes (size)
• Free-block payload start: prev/next pointers (8+8 bytes on 64-bit; for embedded use 4-byte pointers adapt)

Code (C-style pseudocode):

typedef uint32_t word; // adapt to 32/64-bit
#define ALIGN 8
#define USED 1
#define SIZE_MASK (~(word)0x7)

word read_header(void *p) { return *(word*)p; }
void write_header(void *p, word v) { *(word*)p = v; }
void write_footer(void *p, word v) { *(word*)((char*)p + v - sizeof(word)) = v; }

void *heap_start, *heap_end;
void *free_list_head;

void *find_fit(size_t asize){
  for(void *b = free_list_head; b; b = *(void**)((char*)b + sizeof(void*))) {
    word h = read_header(b);
    size_t sz = h & SIZE_MASK;
    if(sz >= asize) return b;
  }
  return NULL;
}

void *malloc(size_t size){
  if(size==0) return NULL;
  size_t asize = ((size + sizeof(word) + (ALIGN-1)) & ~(ALIGN-1)); // header + aligned payload
  void *b = find_fit(asize);
  if(!b) return NULL; // no sbrk in constrained environment
  word h = read_header(b);
  size_t sz = h & SIZE_MASK;
  remove_from_free_list(b);
  if(sz - asize >= (sizeof(word)*2 + ALIGN)) { // split
    write_header(b, asize | USED);
    void *next = (char*)b + asize;
    write_header(next, (sz - asize) | 0);
    write_footer(next, (sz - asize));
    insert_into_free_list(next);
  } else {
    write_header(b, sz | USED);
  }
  return (char*)b + sizeof(word);
}

void free(void *ptr){
  if(!ptr) return;
  void *b = (char*)ptr - sizeof(word);
  word h = read_header(b);
  size_t sz = h & SIZE_MASK;
  // mark free and write footer
  write_header(b, sz | 0);
  write_footer(b, sz);
  // coalesce with prev if free (use footer of prev)
  void *prev_footer = (char*)b - sizeof(word);
  if(prev_footer >= heap_start){
    word prev_size = *(word*)prev_footer;
    if((*(word*)((char*)b - prev_size) & USED)==0){
      void *prev_block = (char*)b - prev_size;
      remove_from_free_list(prev_block);
      sz += prev_size;
      b = prev_block;
      write_header(b, sz | 0);
      write_footer(b, sz);
    }
  }
  // coalesce with next
  void *next = (char*)b + sz;
  if(next < heap_end){
    word nh = read_header(next);
    if((nh & USED)==0){
      size_t nsz = nh & SIZE_MASK;
      remove_from_free_list(next);
      sz += nsz;
      write_header(b, sz | 0);
      write_footer(b, sz);
    }
  }
  insert_into_free_list(b);
}

Notes, trade-offs, edge cases

• Explicit free list reduces traversal time vs single list. Overhead tuned for embedded: use 4-byte pointers when 32-bit.
• Allocated blocks omit footer to save 8 bytes; requires care on coalescing (footers exist only for free neighbors).
• Alignment: ensure asize includes header and rounds to ALIGN.
• Consider splitting threshold, minimum block size, and thread-safety (locks) for RTOS.

Plan overview

• Prevent via static analysis, detect in host/unit tests with heavy instrumentation, and run lightweight diagnostics on target devices with limited RAM/CPU.

Static analysis (host CI)

• Tools: clang-tidy + clang-analyzer, Cppcheck, Coverity/PRQA for MISRA checks.
• Rules: enable null-deref, use-after-free heuristics, uninitialized reads, pointer lifetime, stack depth checks. Fail CI on new warnings.

Host/runtime instrumentation + unit tests

• Use AddressSanitizer and UBSan in host/QEMU builds to detect leaks, UAF, double-free, stack overflow.
• Run Valgrind/memcheck and ASAN-enabled unit tests in CI matrix (gcc/clang).
• Fuzz memory APIs with libFuzzer/AFL for buffer and allocator edge cases.
• Example lightweight malloc tracer (wraps malloc/free to record backtraces and refcounts):

// simple malloc tracer (compile only for host/unit tests)
#include <stdlib.h>
#include <stdio.h>
#include <execinfo.h>

void *tracked_malloc(size_t s){
  void *p = malloc(s);
  if(p){
    void *bt[8]; int n = backtrace(bt, 8);
    fprintf(stderr, "MALLOC %p size=%zu bt=%d\n", p, s, n);
  }
  return p;
}
void tracked_free(void *p){
  free(p);
  fprintf(stderr, "FREE %p\n", p);
}

On-target diagnostics for low-memory devices

• Build a "diagnostic firmware" with: malloc/free tracking (lightweight hash table), allocation counters, peak usage, and configurable sampling to limit overhead.
• Enable MPU/stack canaries and compile with -fstack-protector-strong.
• Put minimal heap integrity checks into allocator: magic headers, checksum on free, double-free detection.
• If MPU present, use guard regions for critical stacks/tasks; else store per-task high-water marks and check at context switch.
• Expose telemetry via serial/Syslog: allocation failures, leak summaries, stack high-water marks, and earliest fault backtrace (store compressed call chains on failure).
• Remote-triggered health dump: on OOM or crash, dump recent allocation events from circular buffer.

CI & process

• Gate merges: require no new static warnings and passing ASAN unit tests.
• Nightly: run heavy Valgrind/fuzz on host and occasional QEMU ASAN builds.
• Training: enforce allocator review, require unit tests for all new dynamic memory paths.

Trade-offs

• ASan not for tiny targets — use sampled on-target tracing + strict code review and static tools.
• Balance telemetry vs RAM; prefer circular logs and sampling for production.

Results: early detection on host, reproducible unit tests, and focused, low-overhead on-target telemetry to catch residual issues in constrained devices.

Answer (formal, assumptions, and instrumentation)

Assumptions

• Heap total bytes = H.
• Largest single allocation request size = M.
• Allocator obeys contiguity: an allocation of size s needs a contiguous free block >= s.
• We measure external fragmentation as free bytes that cannot satisfy a future allocation request of size up to M (i.e., unusable for any request ≤ M).

Formal worst-case bound

• At any instant you can place at most floor(H / M) disjoint blocks of size M into H. The remaining bytes R = H - floor(H / M) * M are strictly < M.
• Therefore in the worst case all free space could be distributed so no contiguous free block ≥ M, so unusable (wasted for requests of size M) ≤ R < M.
• Bound: worst-case wasted memory < M (equivalently ≤ M - 1 when working in integer bytes).

Reasoning (why this holds)

• If any contiguous region ≥ M exists then a request of size M could be satisfied, so maximum unavoidable unusable remainder is the mod remainder after packing M-sized chunks into H.
• This is agnostic to allocation pattern or fragmentation strategy because it’s a packing upper bound.

Extensions / caveats

• If you must support requests up to variable maxima or alignment/metadata overhead a, replace M with M + a (or with allocation quantum Q): bound becomes < Q.
• If fragmentation is measured relative to arbitrary smaller requests, worst-case wasted can be larger (many small holes each < required s), so the bound applies only w.r.t. the specified maximum request size.

Instrumentation in the field (embedded-friendly)

• Track free-list summary counters rather than full dumps: total_free_bytes, largest_free_block, free_block_count.
• Periodically log or expose via telemetry:
  • external_waste_for_M = total_free_bytes if largest_free_block < M else total_free_bytes - largest_contiguous_allocatable_bytes_for_M (or simply R = H - floor(H/M)*M as theoretical reference).
  • fragmentation_metric = 1 - (largest_free_block / total_free_bytes) or wasted_fraction = (total_free_bytes - usable_for_M) / H.
• Lightweight implementation: on each free/alloc update:
  • maintain max_free_block (update on coalesce/split),
  • maintain total_free,
  • sample free-list to compute usable_for_M = sum_{blocks b with size ≥ M} floor(size_b / M) * M.
• Report trends and alarms (largest_free_block < M or wasted_fraction > threshold).

Example short check (C-style pseudo):

size_t total_free, largest_free;
void update_on_change(block b) { total_free += b.size_change; largest_free = max(largest_free, b.size); }
bool alarm = (largest_free < M && total_free >= M); // indicates fragmentation preventing M-sized allocation

This gives a provable worst-case bound (< M wasted) for requests of size ≤ M and pragmatic telemetry to detect and quantify fragmentation in embedded systems.