Block Metadata: Turn Bytes Into a Navigable Layout

The previous module obtained a region. Now make its layout explicit. Implement block-header-design: conversions between a known header and its payload, initialization, a diagnostic marker, and a bounded calculation of the next physical header. No allocation policy is needed yet.

Read the header as a contract

The exercise supplies this exact type:

typedef struct block_header {
    size_t size;                 // payload capacity in bytes
    int free;                   // 1 = reusable, 0 = allocated
    unsigned int magic;         // BLOCK_MAGIC after initialization
    struct block_header *next;  // logical list successor
} block_header_t;

Let H = sizeof(block_header_t). The layout is [H header bytes][size payload bytes]. size excludes the header; it describes capacity, not the last client's requested length. On the course's usual 64-bit target H is 24, but calculate with sizeof, because field sizes and padding depend on the target.

block_init sets all four fields: capacity, supplied free flag, BLOCK_MAGIC, and next = NULL. A reused memory region can contain old bytes in any field. Initialization establishes a state; it does not verify where the pointer came from.

Work one block by byte offsets

Use a hypothetical aligned arena with a header at byte address 4096, H=24, and capacity 40:

4096                       4120                               4160
| header: 24 bytes         | payload: 40 bytes                 |
^ header                   ^ user pointer                     ^ next boundary

The total extent is 64 bytes. The payload starts at 4120; its last byte is 4159. Recovering the header subtracts 24 bytes from the payload address.

Typed pointer arithmetic scales by its pointed-to type: block + 1 advances one whole header. In this supplied immediate-header layout, ((block_header_t *)payload) - 1 reverses that conversion for a payload obtained from a valid block. By contrast, block + sizeof(block_header_t) advances H headers, H×H bytes. Use unsigned char * when expressing a byte offset; ISO C does not define arithmetic on void *.

These expressions require the managed storage and alignment described in the task. They are not permission to subtract from NULL, a stack variable, or an arbitrary user's address. C pointer arithmetic and conversions have object-boundary and alignment rules. C11 committee draft, §§6.3.2.3 and 6.5.6

Physical next and logical next

The physical candidate starts at header address + H + capacity. The logical successor is the value stored in next. The two can differ: a list can be reordered or link blocks from separate regions. block_next_in_memory computes from byte geometry and never follows next.

Suppose an arena starts at offset 0, H=24, and its exclusive end is offset 160. A header at offset 0 with capacity 40 ends at 64. There are 96 bytes remaining, enough for another header, so return the candidate at 64. If the arena instead ends at 80, only 16 bytes remain after that block. Return NULL: a candidate's first byte being inside the arena is insufficient to hold a complete 24-byte header.

Check the extent before constructing an out-of-range pointer. Given a trusted current header and an exclusive end in the same arena, let remaining = end - start. The task guarantees at least H bytes remain and that the difference fits ptrdiff_t.

• If capacity exceeds remaining - H, return NULL; the claimed current extent crosses the boundary.
• Otherwise consume H + capacity, a now-bounded amount.
• If fewer than H bytes remain after it, return NULL.
• Otherwise return the candidate; the task guarantees its header alignment.

This helper establishes room for a header, not that a new header has already been initialized. When constructing a chain in a fresh arena, initialize the returned location before reading its fields.

Three alignment questions

Ask separately whether the current header, payload, and next header have suitable alignment. H=24 and a base divisible by 16 yield a payload at base+24: divisible by 8 but not by 16. Even if a header needs only 8-byte alignment, that does not meet every possible payload requirement. An odd payload capacity can also misalign the following header.

For this exercise, the caller provides aligned header storage and, when physically walking blocks, capacities whose extents keep candidates aligned. Later exercises round capacities according to their stated allocator model. A general C allocator must meet the applicable allocation alignment contract; a hard-coded 8-byte teaching policy is not universal. C11 committee draft, §§6.2.8 and 7.22.3

What a magic check can establish

block_is_valid checks whether the readable, trusted header's magic equals BLOCK_MAGIC. It can detect some accidental overwrites. It cannot establish ownership, catch every corruption, or safely validate an arbitrary address. An overwritten size with the magic untouched still passes this check.

In particular, reading payload - H before deciding whether an arbitrary payload belongs to the allocator may already access invalid storage. The precondition must come first. Later free operations in this course accept only their stated owned pointers, plus any explicitly supported NULL case. A hardened diagnostic would need trusted region/ownership information before reading candidate metadata.

Finish the layout yourself

H=24, arena end=256, current header offset=64, capacity=48. Compute payload offset, block end, and remaining bytes after the block. Decide whether a next header fits. Then suppose the stored logical next points to offset 200: does it change the physical result?

Check the completed layout

Payload=88; end=64+24+48=136; remaining=256−136=120. A header fits at 136. The stored next is unrelated to that physical calculation. Do not treat the example's logical pointer as permission to dereference offset 200 unless it names a valid initialized header.

For independent practice, take H=32, header offset=96, capacity=64. Compare arena ends 224 and 208: calculate the candidate offset and whether the complete candidate header fits in each case. Explain the equality boundary in your own words.

Build and explain

Implement initialization and total size first, then the two inverse payload conversions. Test the round trip payload_to_block(block_to_payload(block)) == block. Finally implement the bounded physical-next calculation. Use suitably aligned test storage, and test exact end, a short trailing fragment, and an oversized claimed capacity.

Before the quiz, explain which functions have trusted-pointer preconditions, why list order is separate from byte order, and why a correct magic value does not make an arbitrary pointer safe. Those distinctions will prevent errors when the next module begins tracking reusable blocks.