Memory Fundamentals: Reserve Bytes Before Building an Allocator

You are building a sequence of small components: request raw bytes, describe a block, link blocks, then allocate and reuse them. In this first module, implement sbrk-basics. It tracks a growing region; it does not yet promise aligned objects, block reuse, or free.

Check your starting point

You should be able to distinguish an address from the bytes at that address, explain size_t, and move a byte pointer by an offset. Predict this before continuing: if a region begins at address 4096 and contains 24 bytes, its last byte is 4119 and its exclusive end is 4120. An end pointer names a boundary; it is not a byte you may write.

The region model

For this Linux teaching exercise, imagine one managed region [base, break). Growing its endpoint supplies bytes to the process. Other parts of its virtual address space include code, stacks, libraries, and mappings. There is no universal C diagram in which every heap allocation belongs to this one region: for example, glibc can obtain allocations through both the program break and separate mappings. Linux malloc documentation

Separate three responsibilities:

Layer	Question answered	Work in this course
Region growth	Where can we obtain more bytes?	sbrk-basics
Allocator metadata	Which bytes belong to which block?	block-header-design
Allocation policy	Which free block can satisfy a request?	free-list-operations, then allocation and reuse

Consecutive successful growth calls are adjacent only while no other code moves the break between them. The exercise runs sequentially and assumes exclusive control of this region. Do not install these helpers as replacements for the C library allocator or mix independent allocators managing the same break.

Follow a successful request

On the supported platform, sbrk(increment) returns the old break on success; sbrk(0) queries it. Failure is (void *)-1, which is different from NULL. sbrk is a legacy interface, outside ISO C and current POSIX. Linux brk/sbrk documentation

Addresses below are invented decimal byte addresses. A successful initialization observes break 4096:

Operation	Returned value	Break afterward	Successful requested bytes	Growth attempts
heap_init()	no value	4096	0	0
heap_request(24)	4096	4120	24	1
heap_request(8)	4120	4128	32	2
heap_request(0)	NULL	4128	32	2
heap_current_break()	4128	4128	32	2

The first request owns [4096, 4120) and the second [4120, 4128). Returning the new break would point just beyond the new storage. Queries are not growth attempts, and zero is rejected before calling sbrk.

heap_init() resets accounting and records the current boundary. It does not lower the break or release earlier storage. Consequently, the requested-byte counter is a total since initialization, not the size of every region in the process.

Make failure a state transition

A request is a transaction: validate, attempt growth, then publish successful accounting.

1. Reject zero. Reject a value larger than INTPTR_MAX before converting size_t to the signed intptr_t increment.
2. Reject an accounting overflow using size > SIZE_MAX - total_requested. Check before addition.
3. Attempt sbrk once and increment the attempt counter, even if that attempt fails.
4. If the result is (void *)-1, return NULL with successful bytes unchanged.
5. Only on success, add the requested size and return the old break.

The task bounds the number of attempts below INT_MAX. Include <stdint.h> for the integer limits. A cast is not a range check: on the usual platform, converting the largest unsigned value to a signed increment can produce a negative value and request a shrink instead of growth.

For example, after the table above, suppose heap_request(64) fails. The break stays 4128, successful bytes stay 32, and attempts become 3. A subsequent successful request for 16 returns 4128, moves the break to 4144, and gives totals 48 and 4. Counting failed bytes would claim ownership of storage that was never obtained.

Complete a trace before coding

Start at break 8192 with reset counters. Request 10 successfully, request 6 successfully, reject zero, then attempt 20 and receive (void *)-1. Fill the missing row:

Checkpoint	Break	Successful bytes	Attempts
After 10	8202	10	1
After 6	8208	16	2
After zero and failed 20	?	?	?

Check your reasoning after completing the row

The row is 8208, 16, 3. Zero makes no call; the failed positive request makes one call but acquires no bytes. If heap_init() is called next, the break stays 8208 while both counters become zero.

Now predict a separate trace without the table: reset at 1000; successfully request 7, reject a size greater than INTPTR_MAX, then successfully request 9. Record both returned addresses, final break, total bytes, and attempts. Explain which branch prevents a signed conversion from changing the meaning of the request.

From raw storage to blocks

These helpers return byte storage of exactly the requested length. Two requests of 1 byte need not both start at an address suitable for a struct. The next module introduces headers; later allocation exercises define an alignment policy and checked rounding. Do not infer a general malloc alignment guarantee from successful region growth.

Likewise, freeing an interior block does not imply that its bytes can be returned by lowering the break. With live A, free B, live C in address order, lowering the endpoint through B would remove C. The allocator will track B for reuse instead.

Build and explain

Implement sbrk-basics with the failure branches above. Check initialization, two contiguous successful requests, zero, an unrepresentable increment, an injected growth failure, and reset-without-shrink. The tests include simulated failures so correctness does not depend on exhausting real memory.

Before taking the quiz, explain why the old boundary is the returned allocation, why attempts and successful bytes differ, and why these functions alone cannot implement free. After a wrong answer, revisit the linked section and retrace a different sequence before retrying.