Objective

Write a two-function allocator over a 4096-byte static pool: heap_alloc hands out 8-aligned blocks from a free list, heap_free gives one back and merges it with a free neighbour.

Steps

• Write heap_alloc.c. It defines void *heap_alloc(size_t n) and void heap_free(void *p). Nothing else is available to you: no malloc, no sbrk, not one library call.
• All the memory you hand out comes from a single static array of exactly 4096 bytes that you declare in that file.
• heap_alloc(n) returns a pointer to at least n writable bytes inside the pool, aligned on 8. An array of char carries no alignment guarantee at all, so declare the pool as an array of a type at least 8 bytes wide.
• Two live blocks never share a byte. A block stays valid until it is passed to heap_free.
• heap_alloc(0) returns NULL.
• A request the pool cannot serve returns NULL. n can be SIZE_MAX, so compare n against the pool size before you add the size of your header to it. Add first and the sum wraps to a small number, and the request sails through.
• heap_free(NULL) returns without touching anything.
• heap_free(p) puts a block back. When the returned block sits next to a free block, the two become one block. This merge is the point of the exercise: without it, a pool that has been filled and then emptied is a chain of small holes, and a later request bigger than any single hole fails while the room is sitting right there.
• One test fills the pool with 256-byte blocks, frees two neighbours, then asks for 400 bytes. Neither hole alone can serve that. Two more empty a full pool completely, one from the highest address down and one every other block followed by the rest, then ask for 1024 bytes.
• The header layout, the rounding and the shape of the free list are yours. Keep the bookkeeping down to a header: the pool is expected to hold at least eight 256-byte blocks at once.
• The largest single request in the tests is 2048 bytes, out of a fully released pool. A request that must be refused for its size alone asks for more than 4096 bytes.
• Passing heap_free a pointer that heap_alloc never returned, or freeing the same block twice, is undefined. Grademe does neither.
• Nothing about your internals is printed, since two correct allocators disagree on all of it. Each test prints tokens computed from the pointers you returned, and a check that does not hold prints the same tag with another value: align:bad, overlap:found, inpool:out, or <tag>:bad.
• alloc:ok a request that had to succeed came back non-NULL. null it came back NULL.
• align:ok every live block starts on an 8-byte boundary. overlap:none no two live blocks share a byte. inpool:ok every live block fits inside one 4096-byte window.
• split:ok many small blocks were served, so the one big free block was really cut up. data:ok bytes written into a block read back unchanged, in that block and in every other live block.
• reuse:ok a block freed out of a full pool served the next request of the same size. coalesce:ok freed neighbours became one block again and served a request larger than any of them. exhaust:ok the pool ran out and said so instead of handing out memory it does not own.
• Every test shares the same pool and releases everything it took before the next one starts. An allocator that splits but never merges gets through the first tests, then stops being able to serve anything bigger than a single hole.

Objective

Write a two-function allocator over a 4096-byte static pool: heap_alloc hands out 8-aligned blocks from a free list, heap_free gives one back and merges it with a free neighbour.

Steps

• Write heap_alloc.c. It defines void *heap_alloc(size_t n) and void heap_free(void *p). Nothing else is available to you: no malloc, no sbrk, not one library call.
• All the memory you hand out comes from a single static array of exactly 4096 bytes that you declare in that file.
• heap_alloc(n) returns a pointer to at least n writable bytes inside the pool, aligned on 8. An array of char carries no alignment guarantee at all, so declare the pool as an array of a type at least 8 bytes wide.
• Two live blocks never share a byte. A block stays valid until it is passed to heap_free.
• heap_alloc(0) returns NULL.
• A request the pool cannot serve returns NULL. n can be SIZE_MAX, so compare n against the pool size before you add the size of your header to it. Add first and the sum wraps to a small number, and the request sails through.
• heap_free(NULL) returns without touching anything.
• heap_free(p) puts a block back. When the returned block sits next to a free block, the two become one block. This merge is the point of the exercise: without it, a pool that has been filled and then emptied is a chain of small holes, and a later request bigger than any single hole fails while the room is sitting right there.
• One test fills the pool with 256-byte blocks, frees two neighbours, then asks for 400 bytes. Neither hole alone can serve that. Two more empty a full pool completely, one from the highest address down and one every other block followed by the rest, then ask for 1024 bytes.
• The header layout, the rounding and the shape of the free list are yours. Keep the bookkeeping down to a header: the pool is expected to hold at least eight 256-byte blocks at once.
• The largest single request in the tests is 2048 bytes, out of a fully released pool. A request that must be refused for its size alone asks for more than 4096 bytes.
• Passing heap_free a pointer that heap_alloc never returned, or freeing the same block twice, is undefined. Grademe does neither.
• Nothing about your internals is printed, since two correct allocators disagree on all of it. Each test prints tokens computed from the pointers you returned, and a check that does not hold prints the same tag with another value: align:bad, overlap:found, inpool:out, or <tag>:bad.
• alloc:ok a request that had to succeed came back non-NULL. null it came back NULL.
• align:ok every live block starts on an 8-byte boundary. overlap:none no two live blocks share a byte. inpool:ok every live block fits inside one 4096-byte window.
• split:ok many small blocks were served, so the one big free block was really cut up. data:ok bytes written into a block read back unchanged, in that block and in every other live block.
• reuse:ok a block freed out of a full pool served the next request of the same size. coalesce:ok freed neighbours became one block again and served a request larger than any of them. exhaust:ok the pool ran out and said so instead of handing out memory it does not own.
• Every test shares the same pool and releases everything it took before the next one starts. An allocator that splits but never merges gets through the first tests, then stops being able to serve anything bigger than a single hole.