Code Katas

Focused, repeatable C exercises for this module. Complete each multiple times until it is automatic.

Format for every kata:

• Time limit: as stated per kata
• Build command: always start with gcc -Wall -Wextra -O1 -g -std=c11 plus any sanitizer flags listed
• Tests: write at least three test cases before coding, including one edge case
• Reflect: after coding, add a two-line comment: one about the pointer invariant, one about the memory-safety argument

Kata 1: Linked List from Scratch

Time limit: 30 minutes Goal: Implement a singly linked list of int with push_front, pop_front, length, free_all. Setup: One .c file plus a small main driver.

Use typedef struct Node { int v; struct Node *next; } Node;. Write a memory diagram of the list after three push_front operations before you code. Make free_all walk to the end and free each node; do not leak.

Build: gcc -Wall -Wextra -O1 -g -fsanitize=address,undefined -o ll ll.c. Run your tests.

Repeat until: ASan reports no leaks and the code compiles with -Werror and you can write it in under 15 minutes without reference.

Kata 2: Small malloc (Bump + Free-List)

Time limit: 60 minutes Goal: Implement my_malloc and my_free against a fixed-size static arena with explicit free-list coalescing. Setup: A 1 MB unsigned char arena[1 << 20]; with 16-byte alignment.

Step 1: bump allocator. my_malloc returns the next aligned offset; my_free is a no-op. Verify alignment using assert(((uintptr_t)p & 0xF) == 0);.

Step 2: free list. Each block has a header: struct Hdr { size_t size; struct Hdr *next_free; int is_free; };. my_malloc finds the first fitting free block, splits if much larger, returns payload. my_free flips the flag and coalesces with left and right free neighbors.

Tests: random sequence of 10 000 malloc / free calls with sizes in [1, 1024]; verify the free list is well-formed after every step; total "in-use" size never exceeds arena.

Repeat until: ASan + UBSan clean, and you can sketch the free-list diagram by hand.

Kata 3: Stack-Frame Tracer

Time limit: 30 minutes Goal: Print each stack frame's local address to show stack direction and frame size. Setup: A recursive function that calls itself with depth printed.

Implement:

void trace(int depth) {
    int marker = depth;
    printf("depth=%d  addr=%p\n", depth, (void *)&marker);
    if (depth > 0) trace(depth - 1);
}

Tasks:

1. From two consecutive addresses, compute the frame size in bytes.
2. Run with and without -O2. Explain the difference.
3. Use backtrace(3) from <execinfo.h> at the deepest point to print a symbolic stack trace.

Repeat until: you can predict the stack-direction result on x86-64 (downward) and can read a backtrace output fluently.

Kata 4: Struct-Packing Analyzer

Time limit: 25 minutes Goal: Given a struct definition, predict sizeof and each field's offset, then verify. Setup: Any three structs of your own design.

Print every field's offsetof plus sizeof for each struct. Then reorder fields to minimize total size. Use _Static_assert(sizeof(S) == expected, "layout"); to freeze your result.

Example starting point:

struct Big {
    char a;
    int  b;
    char c;
    double d;
    short e;
};

Compute the size with default alignment on x86-64 before running. Reorder to minimize size. Compare with -Wpadded warnings.

Repeat until: you can size four out-of-order structs in under 5 minutes and your reorder matches -Wpadded's recommendation.

Kata 5: Endianness Converter

Time limit: 30 minutes Goal: Serialize and deserialize uint32_t and IEEE 754 double across a canonical byte order. Setup: A tiny encode(buf, value) / decode(buf) pair for each type.

Implement explicit shift-and-mask without htonl:

void put_u32_be(uint8_t *buf, uint32_t v) {
    buf[0] = (uint8_t)(v >> 24);
    buf[1] = (uint8_t)(v >> 16);
    buf[2] = (uint8_t)(v >>  8);
    buf[3] = (uint8_t)(v      );
}
uint32_t get_u32_be(const uint8_t *buf) {
    return ((uint32_t)buf[0] << 24)
         | ((uint32_t)buf[1] << 16)
         | ((uint32_t)buf[2] <<  8)
         | ((uint32_t)buf[3]      );
}

For double, memcpy through uint64_t and byte-swap the integer.

Tests: round-trip 0, 1, -1, 0x12345678, 3.14, -Inf, NaN. Every round trip must be identity.

Repeat until: round-trip works for all 16 test values and the code is endianness-independent (works the same on little- and big-endian hosts).

Completion Standard

• All five katas completed at least once
• Katas 1, 4, 5 completed three or more times, within time limit, from scratch
• All katas run clean under -fsanitize=address,undefined
• Memory diagrams drawn for Katas 1 and 2 before coding
• You can recite the core invariant (ownership / alignment / byte order / frame layout) for every kata without reference