Optimize the Layout Without Breaking Ownership

This module's four exercises add alignment, splitting, coalescing, and diagnostics. Each improves a different property. Work from byte addresses and capacities; a block-list link alone is not proof that two blocks are physically adjacent.

Alignment comes before splitting

An address is N-byte aligned when its value is divisible by N. For a power-of-two N, round an address upward using (address + N - 1) & ~(N - 1), after checking that the addition cannot overflow. For example, rounding address 0x1029 to 16 gives 0x1030, seven bytes later. Ordinary C allocation provides fundamental alignment; over-aligned data may need a separate API. SIMD requirements depend on the instruction, and not every misaligned access traps or crosses a cache line.

The custom aligned-allocation exercise reserves payload plus alignment-1 bytes of possible padding plus room for an original-pointer slot. Round upward after leaving room for that slot, store the raw pointer immediately before the returned aligned address, and retrieve it in the paired free. Passing the interior aligned address directly to ordinary free is invalid. Check each size addition before allocating; a valid power of two alone does not prevent overflow.

Work aligned allocation first. Its custom API promotes a positive power-of-two alignment smaller than sizeof(void*) to the pointer size, rejects zero-sized requests, and permits sizes not divisible by alignment. Those are exercise rules, not a substitute for the standard C API. The standard's fundamental-alignment contract is described in the C11 committee draft, §7.22.3.

Trace a raw allocation beginning at invented decimal address 1000. With an eight-byte pointer, alignment 64, and payload size 20, reserve 20+63+8=91 bytes. The first possible payload address is 1008. Its remainder modulo 64 is 48, so add 16 bytes of padding and return 1024. Store the raw pointer 1000 in [1016,1024); the user's bytes occupy [1024,1044). The 64-byte alignment does not mean the user owns 64 bytes. The saved pointer is metadata and must not overlap those 20 writable bytes.

There are two arithmetic boundaries: the reservation and the underlying heap extension. Check padding and pointer-slot additions, then ensure the supplied allocator's rounded payload plus header fits the signed sbrk increment. For a toy SIZE_MAX=255, size 240, alignment 16, and pointer size 8, padding alone gives 255, but adding the slot would give 263. Reject before allocation. Checking only that 16 is a power of two would allow a wrapped, undersized block.

Complete a fresh trace: raw address 2008, pointer size 8, alignment 32, size 9. Find the reserved byte count, returned address, and saved-pointer range.

Check the address trace

Reserve 9+31+8=48 bytes. Start at 2016, already divisible by 32, so return 2016 with the saved pointer in [2008,2016) and payload in [2016,2025). No alignment padding is needed after the pointer slot in this case.

Before continuing, change the raw address to 2016 and reconstruct the layout without reopening the answer. Then explain why an arithmetic rejection must leave an already-free block free and every live allocation unchanged. Splitting next changes capacities; it must preserve this same ownership boundary.

Derive a split from capacities

Suppose header size H=24, alignment 8, and a free block's payload capacity is 120. A request for 33 rounds to R=40. A split leaves 120-40-24=56 bytes of payload in the remainder. The new header begins at old_header + H + R, and both headers remain aligned.

If the minimum useful remainder payload is 16, split only when capacity-R >= H+16. Check R <= capacity before subtracting, or unsigned underflow can turn an oversized request into an apparently enormous remainder. At equality a split is allowed: capacity 80 and request 40 leave exactly one 24-byte header and 16-byte payload. Preserve the old successor by assigning remainder.next = old.next before old.next = remainder.

The original header is still overhead; the second header comes out of the original payload capacity. Writing remainder = capacity-R without subtracting H counts the same bytes as both metadata and usable payload.

Merge only physical neighbors

For headers A and B, adjacency means address(A)+H+A.capacity == address(B). Both must be free. Then A can absorb B with A.capacity += H+B.capacity, and skip B in the list. Two adjacent free payloads of 40 and 56 with H=24 become capacity 120, reversing the split. Two 40-byte blocks separated by a live block cannot become one allocation merely because their free-list links are consecutive.

A scan can find a preceding physical block in a singly linked list. A doubly linked list speeds up predecessor lookup only if its order reflects physical layout; boundary tags encode physical-neighbor information at a space cost. To merge a longer free run, repeat forward merging or maintain an invariant that no adjacent free blocks remain after each free. A single pairwise merge is not a universal full-run algorithm.

Diagnostics require trustworthy bounds

Check live ownership, metadata consistency, and payload boundaries. A sentinel can detect a write that crosses a checked boundary, but a matching magic value does not prove an arbitrary pointer is safe to dereference. The diagnostic exercise has its own limited managed-heap rules; it is not a universal invalid-pointer detector. A debugger watchpoint can stop on a specific metadata write, helping distinguish corruption from the later traversal that discovers it.

The allocator exercises are single-threaded. A global lock must protect the entire search-and-claim operation, including list updates and coordinated heap growth. Thread-local arenas need cross-thread free and memory-retention policies. An atomic list head does not make the allocator correct, and lock-free data structures additionally need safe reclamation; no strategy is inherently fastest for every workload.

Capacity is not production readiness

Mapping large requests separately can make individual release possible, but page rounding and address-space fragmentation still exist. Thresholds are allocator policies, not universal constants. These exercises deliberately use limited my_* interfaces; exporting them as libc symbols or injecting them into arbitrary processes requires a complete ABI, alignment, threading, and bootstrap design. Passing a local test suite does not establish those properties.

Check yourself: a capacity-72 block, H=24, alignment 8, minimum payload 16, and request 35 rounds to 40. Do not split: only 32 bytes remain, less than the 40 required. The unsplit allocation retains capacity 72; the extra capacity is internal fragmentation.