M3 Projects

Two deliverables. Both go on your GitHub with a clean README. Both must be reproducible — clone, make, make test, everything passes on a clean machine. The point is to prove to your future self (and any study partner) that you not only understand memory in C, you can build things that don’t leak.

Project 1: arena — A Bump-Arena Allocator

~200 LOC of C. Zero leaks under ASan. Full test suite.

Scope

Build an arena/bump allocator based on Chris Wellons’ 2023 pattern, with:

  • arena_init(Arena *a, void *buf, size_t cap) — initialize from a caller-provided buffer.

  • arena_alloc(Arena *a, size_t size, size_t align) — aligned bump allocation, returns NULL when out of room.

  • arena_new(a, T) and arena_new_n(a, T, n) — typed macros using _Alignof(T).

  • arena_reset(Arena *a) — free everything at once (bump offset to zero).

  • arena_save(Arena *a) / arena_restore(Arena *a, ArenaMark) — scratch-arena / checkpoint pattern.

  • Optional: arena_grow(Arena *a, size_t new_cap) that mmap-reserves a large virtual range up front and commits pages lazily. This is Wellons’ “gigabytes of address space” trick.

Test Suite Requirements

  1. Alignment: alloc a char, then a double, verify the double’s address is 8-byte aligned.

  2. Capacity: fill the arena, verify next alloc returns NULL, verify existing pointers still valid.

  3. Reset: alloc N objects, reset, alloc N objects, verify addresses match.

  4. Save/restore: alloc A, save mark M, alloc B, restore M, alloc C, verify C’s address equals B’s.

  5. Zero-size alloc: arena_alloc(a, 0, 1) returns non-NULL and doesn’t advance offset (or returns NULL by policy; document your choice).

  6. Overalignment: request 64-byte-aligned block, verify address is 64-byte aligned.

All tests run under -fsanitize=address,undefined. Zero errors, zero leaks. make asan should print PASS on every test.

Stretch

  • Benchmark against malloc/free for a workload of 100k random small allocations. You should see 5-20x speedup. Include the benchmark output in the README.

  • Implement arena_alloc_zeroed (like calloc for the arena).

  • Thread-local scratch arena a la Wellons: arena_scratch() returns a per-thread arena you can use for short-lived allocations.

Repository Layout

arena/
  README.md          # what, why, how, benchmark numbers
  Makefile           # release, debug, asan, test, bench targets
  arena.h            # 8126311 lines
  arena.c            # ~8126311 lines
  test/test_arena.c  # ~<phone_number_or_numberic_id_or_random_id_31> lines
  bench/bench.c      # ~<phone_number_or_numberic_id_or_random_id_32> lines

README Must Explain

  • Why an arena (link Wellons’ post and Fleury’s).

  • The API and its ownership contract (“the arena owns everything until reset”).

  • The single rule (“never store a pointer past arena_reset”).

  • Benchmark numbers on your machine, honest, including the case where malloc wins (large allocations from an empty state).

Project 2: linked-list-annotated — Ownership Docs In Every Signature

A working doubly-linked list library where every function’s ownership role is explicit and enforced by tests.

Scope

A generic (void*-payload) doubly-linked list with:

  • List *list_new(void (*elem_free)(void*)) — [owned] returns new list; if elem_free != NULL, list will call it on remaining elements at destroy.

  • void list_destroy(List *l) — [sink] frees list and (if elem_free set) all elements.

  • int list_push_back(List *l, void *elem) — [sink] on elem iff elem_free was set at construction. Otherwise [borrow].

  • void *list_front(const List *l) — [borrow] returns pointer; caller must not free.

  • void *list_pop_front(List *l) — [owned] transfers ownership of the popped element back to caller; caller is now responsible.

  • void list_for_each(const List *l, void (*fn)(void *elem, void *ctx), void *ctx) — [borrow] iteration.

  • size_t list_len(const List *l).

The Convention

Every header entry starts with an annotation comment:

/* [owned]  Returns new list; caller must call list_destroy().
 *          elem_free: destructor for elements, or NULL if list borrows. */
List *list_new(void (*elem_free)(void*));

/* [borrow] Reads list; does not modify structure or elements. */
size_t list_len(const List *l);

/* [sink]   Takes ownership of elem iff list was created with elem_free != NULL.
 *          Otherwise elem is borrowed; caller must keep it alive. */
int list_push_back(List *l, void *elem);

/* [owned]  Removes and returns front element. Caller now owns it. */
void *list_pop_front(List *l);

Every header file starts with a two-paragraph explanation of the ownership model and how to read the annotations.

Test Suite Requirements

  1. Owning list: create with elem_free = free, push heap-allocated strings, destroy — zero leaks under ASan.

  2. Borrowing list: create with elem_free = NULL, push stack-allocated strings, destroy — no crashes, no leaks.

  3. Pop transfers: pop element, hold pointer past destroy — verify pointer still valid (it should be; the caller now owns it).

  4. Mixed ownership — a test that documents what happens if you break the convention (push heap ptrs into a borrowing list, don’t free them, destroy list): should be a leak, and the test asserts ASan reports it. This test compiles only with -DNEGATIVE_TESTS and is skipped by make test.

  5. Iteration under list_for_each — assert the callback receives elements in insertion order.

Stretch

  • Implement list_splice(List *dst, List *src) with explicit [sink] on src — the classic ownership-transfer operation.

  • Sanitizer CI: a GitHub Actions workflow that builds with clang, GCC, and MSVC-clang on Windows, running the ASan test suite on each.

  • A one-page “lessons learned” document in the repo describing what the annotation exercise changed about how you think about C APIs.

Why This Matters

Every study loop for a systems role will eventually ask you a variant of “who owns this pointer?” This library is your rehearsed answer. When you point at a repo where you’ve made ownership a first-class citizen of the API, you’ve done something 90% of C programmers never bother with. That’s the deliverable that beats a NeetCode-in-C repo on merit.

Time Budget

Project

Estimated hours

Project 1 (arena)

12-16 h

Project 2 (annotated linked list)

8-12 h

Reading (Wellons + Fleury)

3-4 h

Total

25-32 h

At 10-15 h/week over M3, that’s tight but doable. Skip the stretch goals on your first pass; ship the core and come back.

Done Definition

  • Both repos public on GitHub, license file, README.md explains what/why/how.

  • make asan test prints PASS with zero AddressSanitizer errors.

  • make valgrind prints “definitely lost: 0 bytes in 0 blocks.”

  • Your ownership annotation convention is documented in one place and applied everywhere in both repos.

  • You can, in one sitting, sketch the arena implementation on a whiteboard from memory.

Return to README.md