COMP2310 : Malloc | Systems, Networks, and Concurrency Report Writing

Your task is to implement malloc (memory allocator) and include in your implementation the various requirements and optimizations discussed above. Broadly, your coding tasks are three-fold.

 Allocation

1. Calculate the required block size.
2. Find the appropriate free list to look for a block to allocate.
3. Depending on the size of the block, either allocate the full block or split the block and allocate the right (higher in memory) portion to the user.
4. When allocating a block, update its allocation status.
5. Finally, return the user a pointer to the data field of the header.

 Deallocation (Freeing)

1. Free is called on the same pointer that malloc returned, which means we must calculate the location of the header by pointer arithmetic.
2. Once we have the block’s header freed, we must calculate the locations of its right and left neighbors, using pointer arithmetic and the block’s size fields.
3. Based on the allocation status of the neighboring blocks, we must either insert the block or coalesce it with one or both of the neighboring blocks.

 Report

You must submit a report (maximum of two pages) along with your malloc implementation. The report consists of the following sections.

• Describe your implementation of explicit free list, fence posts, and constant time coalescing. Briefly mention key data structures and function names.
• Describe the optimizations you have attempted in your implementation of malloc.
• If you have done quantitatively analyzed the placement policies, include any graphs and tables.
• Discuss two implementation challenges you encountered in your implementation of malloc.
• Discuss two key observations from testing and benchmarking your malloc implementation. Did something break? Did you end up fixing some stuff after testing and benchmarking? What did not work?