Build an Allocation, Then End Its Ownership

This module contains two distinct milestones: naive-malloc creates a new block for every request, and free-basic marks an existing block free. Reuse starts in the next module. Keeping that boundary explicit prevents a misleading expectation that adding a free flag alone makes the allocator search for it.

Fix the representation before making a request

The list stores block_header_t *; the caller receives the immediately following payload, (void *)(block + 1). Each header stores payload capacity in size, eligibility in free, the diagnostic marker in magic, and the next logical block in next.

Let H be sizeof(block_header_t) and A be _Alignof(block_header_t). Never hard-code H as 24: that is only an illustrative layout on some targets. This stage aligns headers to A. Its payloads are suitable for the byte-oriented exercises; it does not promise every alignment required of a general-purpose system malloc.

request_space(size) returns a header. my_malloc(size) returns its payload. Mixing those contracts lets the caller overwrite the list links on its first write.

Derive the reservation from the current break

A previous odd-sized payload can leave the program break unaligned. Suppose H=24, A=8, the current break is 4096, and a request asks for 5 bytes:

padding = (A - current_address % A) % A = 0
reservation = padding + H + size = 29
header  = 4096
payload = 4120, writable bytes [4120,4125)
new break = 4125

For the next request of 9 bytes, padding is 3. The new header begins at 4128, payload at 4152, and break becomes 4161. The three padding bytes belong to neither payload. Simply placing a header at 4125 would create a misaligned C object even if the processor appears to tolerate its accesses.

size still records 5 and 9 respectively; padding is not caller capacity. Headers remain immediately before their own payloads, but consecutive list nodes need not touch. List order and physical adjacency are different invariants.

Check arithmetic before publishing state

The signed argument to sbrk must be representable. Reserve room for H and the worst-case A-1 padding bytes before converting:

if size > INTPTR_MAX - H - (A-1): fail
query current break; if that fails: fail
calculate padding and total
request total; if growth fails: fail
initialize the complete new header
append it to the list
return the new header

The checked bound also keeps the additions representable on the exercise platform. my_malloc(0) returns NULL without growing or modifying the list. Direct request_space(0) also returns NULL. A failed positive request preserves the old head, successor links, capacities, flags, and live payload bytes. Do not append a candidate before successful growth, and do not confuse the (void *)-1 failure sentinel with NULL.

This sequence assumes a single-threaded teaching process with exclusive control of these break operations; another actor moving the break between the query and growth would invalidate the calculation. sbrk is a legacy platform interface, not portable ISO C. See Linux man-pages for its old-break return and signed increment behavior.

Trace the first two allocations

Starting with an empty list, my_malloc(5) creates A with (size=5, free=0, magic=BLOCK_MAGIC, next=NULL). A second call for 9 creates B and sets A.next=B; the list head remains A. Both payloads are live and disjoint. Searching for the tail must not accidentally replace the head or sever an existing successor.

The naive allocator always appends. After my_free(A_payload), a new my_malloc(3) in free-basic still appends C. Marking a block free makes future reuse possible, but this stage's allocation path does not yet search.

Free changes ownership without changing geometry

my_free(NULL) does nothing. For a non-NULL input, the caller must supply a currently live payload pointer from this allocator. Recover its immediate header by subtracting one header object, then change only its free flag to 1. Preserve capacity, magic, links, and every other live block.

Freeing an interior block cannot shrink a contiguous break region past a later live allocation. This implementation never shrinks; production allocators can release suitable regions through other mechanisms. After freeing, the caller must stop accessing the payload. Its old bytes may remain, but storage retention does not preserve ownership.

A pointer to the middle of a payload, a stack address, or an already-freed allocation violates this contract. Reading a magic value before an arbitrary pointer is not a safe validity check: deriving or dereferencing that candidate may already be invalid. A marker can diagnose corruption only after the address is known to be a readable managed header.

Complete a state and byte trace

Assume H=24 and A=8. The current break is 5001. Allocate 7 bytes, then 8 bytes. Compute both header addresses, payload addresses, and the final break. Free the first payload and predict the list changes before revealing the answer.

Reveal the trace

First padding is 7, header is 5008, payload is 5032, and break is 5039. Second padding is 1, header is 5040, payload is 5064, and final break is 5072. Freeing the first payload changes only A.free to 1. Its size remains 7 and its successor remains B. A naive allocation would still append a third block.

Implement checked growth and list append in naive-malloc, then header recovery and the NULL boundary in free-basic. Independently test odd request sizes, exact payload bounds, preserved earlier data, and rejected huge requests. Explain why a test requiring zero gap between all allocations would encode an unsafe layout rather than prove a correct allocator.