Custom Memory Allocator
In this project I implemented malloc, free, and realloc in C with 16-byte alignment, using three size segregated free lists anchored by dummy heads. I handled allocation using a first-fit policy, and newly freed blocks are placed at the front of the lists. To increase efficiency, blocks are split when beneficial, adjacent free blocks are coalesced, and footer optimization is applied to avoid storing unneeded footers inside allocated payloads. The heap then grows when needed, and a heap check routine walks through headers/footers and the free lists to verify invariants during development.
In this custom memory allocator, I use 16-byte alignment and per-block metadata. Free space is organized into three size-segregated lists. Each list has a dummy node at the beginning to simplify inserting new nodes and account for edge cases. Allocation uses a first-fit policy. If no blocks fit, a new block is created at the beginning of the list. If a block fits but is too big, it is split into two blocks, the correctly sized block is allocated, and the rest becomes a new free block. When a free request is received, the block is freed, then if two consecutive blocks are freed, they are coalesced. One of the most important policies I implemented was footer optimization, which requires headers to carry more information (previous blocks' location), allowing for footers to be overwritten when allocating blocks. This has a big effect because it allows for more space utilization in the heap, increasing efficiency by almost 60%.
My malloc function receives malloc requests and filters them to the correct size-segregated list. The list is then checked to find a free block; if no free block is found, then the heap is extended. My free function handles the coalescing when neighbors can be freed. This is done by checking if any of the following cases apply to the current block: the block before and after are free, only one of the blocks before or after is free, or both the block before and after are allocated. Re-alloc is a function that allows the user to edit a malloc request they previously gave by making it bigger or smaller. Lastly, a checkheap function passes through all the lists and blocks and validates that all headers/footers are in bounds, lists contain only free blocks, and no coalescing opportunities are missed. This allows issues to be caught early and targets them for debugging.
This project strengthened my organization and programming skills. Tackling a big project can be challenging, but because of this project, I was able to plan well, then execute on those plans. This especially helped when bugs and errors would arise because I would be able to diagnose and fix them very quickly. Something else that helped with that was writing organized and clean code, which allowed me to be able to look through my code with no stress and plenty of freedom to make changes. I also learned low-level programming techniques like bit manipulation and pointer arithmetic. This allowed me to not only learn, but also get hands-on experience with a very challenging area in programming. Lastly and most importantly, this project taught me to debug more than anything I have done before. Due to the massive amount of information moving around through the memory, bit manipulation, and pointer arithmetic, I had to be clinical with my debugging to find the needle in a haystack. Now I am confident I can debug any code I face.