Assignment 6: Memory Manager

Due Sunday, March 30, before midnight

The goals for this assignment are:

  • Write your own memory manager

  • Work with blocks of memory using advanced pointers

We will use new starter code: Start Code Link

Memory Manager

Assignment by Dianna Xu

In this project, you will implement a memory allocator for the heap of a user-level process. In other words, you will build your own version of malloc() and free(). You will implement this as a dynamically linked library.

Memory allocators have two distinct tasks.

  • First, the memory allocator asks the operating system to expand the heap portion of the process’s address space by calling either sbrk() or mmap().

  • Second, the memory allocator doles out this memory to the calling process. This involves managing the free list of memory and finding a contiguous chunk of memory that is large enough for the user’s request; when the user later frees memory, it is added back to this list.

The memory allocator is usually provided as part of a standard library and is not part of the OS.

To be clear, the memory allocator operates entirely within the virtual address space of a single process and knows nothing about which physical pages have been allocated to this process or the mapping from logical addresses to physical addresses. Although only a small subset of what the OS does in terms of memory management, this project should still provide good insights into memory allocation.

Requesting Memory

Although a real memory allocator requests more memory from the OS whenever it cannot satisfy a request from the user (for example, typical implementation of malloc calls sbrk repeatedly and manages each chunk returned by sbrk), we simplify the implementation by asking that your memory allocator call mmap() only one time in Mem_Init

Interface

An interface to the memory allocation library has been created for you. You will write your own implementation of this interface.

int Mem_Init(long sizeOfRegion)

Mem_Init is called one time by a process using your routines. sizeOfRegion is the number of bytes you should request from the OS using mmap.

Note that you may need to round this amount so that you request memory in units of the page size (see the man page for getpagesize). Note also that you need to use this allocated memory for your own data structures as well; that is, your infrastructure for tracking the mapping from addresses to memory objects has to be placed in this region.

Return value: Upon success (when the call to mmap is succesful), Mem_Init returns 0. Upon failure, Mem_Init should return −1 and set m_error to E_BAD_ARGS. Along with mmap failing, there are a few other cases where Mem_Init should return a failure: Along with mmap failing, there are a few other cases where Mem_Init should return a failure: Mem_Init is called more than once; sizeOfRegion is less than or equal to 0, etc.

void *Mem_Alloc(long size)

Mem_Alloc takes as input the size in bytes of the object to be allocated and returns a pointer to the start of that object.

Your allocator should use a Worst Fit (WF) policy to decide which chunk of free space to hand out; WF simply looks through your free list and finds the free space that is largest in size and returns the requested size to the user, keeping the rest of the chunk in its free list.

For performance reasons, Mem_Alloc should return 8-byte aligned chunks of memory. For example, if a user allocates 1 byte of memory, your Mem_Alloc implementation should return 8 bytes of memory so that the next free block will be 8-byte aligned, too. To figure out whether you return 8-byte aligned pointers, you should print the pointer out with printf("%p", ptr) The last digit should be a multiple of 8 (i.e., 0 or 8).

Return value: Upon success, Mem_Alloc returns a pointer to the start of the object. The function returns NULL if there is not enough contiguous free space within sizeOfRegion allocated by Mem_Init to satisfy this request (and sets m_error to E_NO_SPACE).

int Mem_Free(void *ptr, int coalesce)

Mem_Free frees the memory object that ptr points to. Just like the standard free(), if ptr is NULL, then no operation is performed. The coalesce flag determines whether the Mem_Free routine should coalesce the freed space back into the bigger pool. Note that in the case of Mem_Free(NULL,1), you should still coalesce, even though you have not freed any memory.

Coalescing: Coalescing rejoins neighboring freed blocks into one bigger free chunk, thus ensuring that big chunks remain free for subsequent calls to Mem_Alloc. When coalesce is non-zero, Mem_Free will coalesce free space; specifically, when coalesce is 1, coalesce the entire list and coalesce wherever possible; when coalesce is 2, coalesce a local neighberhood whose size is upto you. If the coalesce flag is 0, no such coalescing should be done; this makes Mem_Free faster, but leaves small fragments in the free space. Note that in this setup, 0 is the fastest, 1 is the slowest, and 2 is inbetween, depending on how you optimize.

Return value: Upon success, Mem_Free should return 0; on failure, it should return −1.

void Mem_Dump()

This is a debugging routine for your own use. Have it print the regions of free memory to the screen. For those of you who know how to generate PPM images, you can also visualize used vs. empty memory with an image.

Design

Make sure you spend time pondering the design of your memory allocator. In other words:

  1. What are you putting into those 32-byte headers?

  2. Where are you putting the headers and how are you going to organize those headers (note that the important thing is you are limited to 32 bytes per block. You are not limited to the “header” name. In other words, you can put it before, after (which makes them footers), as well as before AND after (you will have to split the 32 bytes then, of course)) . How are your data structures embedded and organized through the headers?

  3. How many lists? Singly or doubly or something else?

Of course, the answers to the above questions are intertwined because what you wish to keep in the headers will depend on how you wish to organize them and through them, your lists.

Once you think you have a design, I strongly advice you to do some drawings to better under- stand what is going on. Which bytes need to be updated when merging two blocks, three blocks, more blocks? What happens when a block is split (on allocation)?

Testing

You need to provide tests to demonstrate that your memory allocator works.

  1. check for 8-byte

  2. simple 8-byte allocation

  3. a few aligned allocations

  4. several odd-sized allocations

  5. bad args to Mem_Init()

  6. worstfit allocation

  7. coalesce of free space

  8. simple allocation and free

  9. aligned allocation and free

  10. odd-sized allocation and free

  11. initialize with size of 1 page

  12. initialize and round up to 1 page

  13. no space left to allocate

  14. try to free a NULL pointer

  15. check that memory can be written to after allocation

You are heavily enouraged to test beyond this!

Other requirements

  • You are not allowed to use malloc() or any related function in any of your routines!

  • You’ll need a header per allocated block; the maximum size of such a header is 32 bytes.

  • You should not allocate any global arrays. You may allocate a few global variables (e.g., a pointer to the head of your free list).

Grading Rubric

Assignment rubrics

Grades are out of 4 points.

  • (4 points) Memory Manager

    • (1.5 points) Memory API, valgrind

    • (0.5 points) Coalesce

    • (1.0 points) Performance

    • (0.7 points) Test Suite

    • (0.3 points) style and header comment

Code rubrics

For full credit, your C programs must be feature-complete, robust (e.g. run without memory errors or crashing) and have good style.

  • Some credit lost for missing features or bugs, depending on severity of error

  • -12.5% for style errors. See the class coding style here.

  • -50% for memory errors

  • -100% for failure to check in work to Github

  • -100% for failure to compile on linux using make

Resubmission

Your memory manager program (A06) is eligible for resubmission at the end of the term. Students can submit up to two times:

  • The first time for up to 3.7 credit

  • The second time for up to 3.0 credit

Resubmissions cannot be made for missed work. I reserve the right to judge whether an earnest effort has been made on the initial submission, but as a guideline, students must have received at least a C (2.0), for example, corresponding to a submission that has some features working but with memory errors.