Implement an Aligned malloc and Matching free in C

Implement `aligned_malloc` in C: it allocates at least `size` bytes and returns a pointer whose address is a multiple of `alignment`. Memory obtained this way must also be released, so implement the matching `aligned_free` as well. The report gives only "implement aligned malloc in C"; the signatures and the rules below follow the usual form of this question and are stated as assumptions. ```c void *aligned_malloc(size_t size, size_t alignment); void aligned_free(void *ptr); ``` - Build on the standard `malloc` and `free` only: do not call `posix_memalign`, `aligned_alloc` or any platform-specific aligned allocator. - `aligned_malloc` returns `NULL` if the memory cannot be allocated. - `aligned_free(ptr)` must release everything `aligned_malloc` allocated for `ptr`, and `aligned_free(NULL)` does nothing. For example, with `alignment = 64`, every pointer `p` returned satisfies `(uintptr_t)p % 64 == 0`, and all `size` bytes starting at `p` may be written. ```hint Room to move Asking malloc for more than size bytes gives you a choice of where the caller's block starts. Work out the worst-case distance from the address malloc returns to an address you could hand back. ``` ```hint What free needs free must receive exactly the address malloc returned, but the caller hands aligned_free a different address. Decide how aligned_free can recover the original address in constant time. ``` ### Constraints and Clarifications - Assume `alignment` is a power of two unless the interviewer says otherwise. - Do pointer arithmetic through `uintptr_t`, an unsigned integer type wide enough to hold a pointer. ### Clarifying Questions - Is `alignment` always a power of two? What should happen when it is not, when it is zero, or when it is smaller than a pointer? - What should `aligned_malloc(0, alignment)` return? - Is wasting up to about `alignment` bytes per allocation acceptable, or does the overhead matter for large alignments such as a page? - Must memory from `aligned_malloc` be released only with `aligned_free`, or should plain `free` work too? ### What a Strong Answer Covers - How much extra memory to request, and why that amount is always enough - Correct integer arithmetic for rounding an address up, using an unsigned pointer-sized type - How `aligned_free` finds the original pointer in constant time, and the alignment of whatever is stored for that purpose - Validation and failure handling: a non-power-of-two alignment, overflow in the size computation, `malloc` returning `NULL`, and `NULL` passed to `aligned_free` - Tests across alignments and sizes, and the per-allocation memory overhead ### Follow-up Questions - Implement `aligned_realloc`. Why can you not simply call `realloc` on the original block? - For a page-sized alignment, this approach can waste nearly a page per allocation. How would you avoid that? - Can `aligned_free` detect a pointer that did not come from `aligned_malloc`? - How would you extend the stored bookkeeping so that a debug build catches double frees and writes past the end of a block?