Reference no: EM132785039

Goals

Learn about how Malloc works under the hood

Get used to systems programming environment

Introduction

As you no doubt know by now, a major part of C programming is the management of memory. You have used malloc() and its kin before, but now it is time to delve into how malloc() works.

In this lab, you will implement a memory allocator, which allows users to malloc() and free() memory as needed.

Your allocator will request large chunks of memory from the OS, and manage all the bookkeeping and memory efficiently.

The allocator you will implement is inspired by the DLMalloc allocator designed by Doug Lea. Also inspired by the DLMalloc allocator is the PTMalloc allocator, which is currently used by GLibC. Our allocator is a simplified version, but if you look through the approach taken by DLMalloc you will notice many similarities.

Task 1: Allocation

1. Calculate the required block size (actual request size) by adding the size of the required metadata and rounding the allocation size up to the next 8-byte modulo. The actual request size is either the size calculated in this step or the size of the header struct, whichever is larger.
2. Find the appropriate free list to look for a block to allocate (recall that the block size per each list is based on the rounded request size, not including the metadata)
1. As long as there are no blocks in the current list, check the next list until there is a block, which can satisfy the request
2. When checking the final list, instead of just checking if the list is empty, iterate over all blocks and check if any is large enough to satisfy the request.
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.
1. When splitting, the size and left_size fields maintained in the neighboring blocks will need to be updated.
4. When allocating a block, update its allocation status to ALLOCATED
5. Finally, return to the user a pointer to the data field of the header.

Task 2: 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 header of the block being freed we must calculate the locations of its right and left neighbors, also 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 with one or both of the neighboring blocks

Task 3: Managing Additional Chunks
Above we don't specify how to handle the case where the user's request cannot be fulfilled by any of the available blocks.
1. If no available block can satisfy an allocation request then we must allocate more memory from the OS. To do this we must call sbrk() again.
2. Two consecutive calls to sbrk() should allocate contiguous regions in memory, therefore when we allocate another chunk we can coalesce it with the most recently allocated chunk. Unfortunately, the user of our library could have called sbrk() between our calls and thus we must check that our two chunks are in fact contiguous in memory.

3. There are a few cases for managing adding a new chunk to the free lists:
1. If the new chunk is not adjacent to the previous chunk, then it can simply be inserted into the appropriate free list like any other block.
2. If the new chunk is adjacent to the previous chunk, then the fence posts between the two chunks should be removed and the chunk should be coalesced with any unallocated memory at the end of the previous chunk.

4. This process may need to be repeated multiple times to get enough memory to satisfy a user's requests.

1. Example: Say a user makes a malloc request for 1000 bytes of memory, but our arena size is 400 bytes. To satisfy the request, we must make 2 consecutive calls to sbrk, leaving us with a total of 1200 bytes in a single contiguous block, from which we can then allocate the necessary 1000 bytes. All new chunks must be the arena size. It is important for you to manage additional chunks this way, as this is how the tests expect you to handle new chunks

Attachment:- Systems Programming.rar