#eye #eye

Custom Malloc



This is a 64-bit struct-based segregated list memory allocator and is robust enough to replace C’s built in malloc. This implementation makes use of explicit lists (with footerless blocks), mini blocks, and a custom 'closeEnoughFit' free block search algorithm that is a mix of first fit and best fit. The segregated list have size bounds, and is each an explicit list for a given size range. We can traverse the free segregated lists using next and prev pointers within our free blocks. For our mini blocks, we only have room for a next pointer so we make do with a singly linked list in the mini block case. I found this to be a good balance to achieve good throughput while minimizing both internal and external fragmentation.


Please contact me in the case that you would like to see the full implementation and please do not share this private page. This is due to CMU’s academic integrity policy.

Duration:
2.5 Weeks
Language and Tools:
Written in C, GDB, cGDB, Valgrind, a lot of Redbull 

Standard free blocks contain a header + next and prev pointers to traverse our free segregated lists 

Mini free blocks contain a header + next pointer to traverse our singly linked mini block list 

Our allocated blocks (of both varieties) contain a header and payload 

Our headers contain the size of our block, an allocated flag bit, a prevBlockAllocated flag bit, and a prevBlockMini flag bit. Anytime a block is changed or written, we update these bits and tell the next block of our allocation or ministatus.