**Assignment 06: Dynamic Memory** For this assignment you will build an implicit, list-based dynamic memory allocator for C programs (essentially, your own version of the `malloc` and `free` functions). You may choose your partner for this assignment. # Learning Goals - Learn about dynamic memory. - Implement a heap-based memory allocator. # Grading Walk-Throughs This assignment will be graded as "Nailed It" / "Not Yet" by a TA. To pass ("Nailed It") the assignment, you must 1. Complete the assignment and submit your work to gradescope. + You should start this assignment in class on the day shown on the calendar. + *Complete the assignment as early as possible*. 1. Schedule a time to meet with a TA. You can meet with them after the submission deadline. + You must book a time to meet with a TA + Sign-up on the Google Sheet *with at least 36 hours of notice*. + Contact your TA on Slack after signing up. + All partners must meet with the TA. If you cannot all make it at the same time, then each of you needs to schedule a time to meet with the TAs. 1. Walk the TA through your solutions prior to the deadline. + Walk-throughs should take no more than 20 minutes. + You should be well prepared to walk a TA through your answers. + You may not make any significant corrections during the walk-through. You should plan on making corrections afterward and scheduling a new walk-through time. Mistakes are expected---nobody is perfect. + You must be prepared to explain your answers and justify your assumptions. TAs do not need to lead you to the correct answer during a walk-through---this is best left to a mentor session. 1. The TA will then either + mark your assignment as "Nailed It" on gradescope, or + mark your assignment as "Not Yet" and inform you that you have some corrections to make. 1. If corrections are needed, then you will need to complete them and then schedule a new time to meet with the TA. + You will ideally complete any needed revisions by the end of the day the following Monday. If you have concerns about the grading walk-through, you can meet with me after you have first met with a TA. # Overview You should open gradescope now and see what you need to submit. **Quite a few of your answers should be completed prior to making any code changes.** Materials for the assignment are on the course VM in the `/data` directory. ~~~bash cd ~/cs105/assignments tar xvf /data/A06-DynamicMemory.tar ~~~ Although the archive includes a number of files, you will only modify `mm.c`. The second most important file is `mdriver.c`, which is a driver program that enables you to evaluate the performance of your allocator; this is the file you will run. Near the top of the file `mm.c` is a C structure `team` into which you should insert the requested identifying information about the team members (if you have a third team member, then you should write both team-members two and three in the space provided for two). *Do this right away so you don't forget. The test code won't work reliably until you do.* Now make and run the driver like so: ~~~bash cd ~/cs105/assignments/A06-DynamicMemory make ./mdriver -V ~~~ The `-V` flag displays helpful summary information. This code evaluates the dynamic memory allocator in terms of both utilization and throughput. Make a note of the total utilization score (in percent), the total throughput score (Kops/sec, labeled Kops), and the overall performance index (out of 100). As you complete this assignment, you will make changes to the dynamic memory allocator to improve these metrics. You will submit your assignment answers and code on gradescope. # The Dynamic Storage Allocator The starter code consists of three key functions, which are declared in `mm.h` and implemented in `mm.c`. 1. `int mm_init(void);` 2. `void* mm_malloc(size_t size);` 3. `void mm_free(void* ptr);` The `mm.c` file implements a simple but functionally correct dynamic memory allocation package. You will modify the functions in the file and perhaps declare other private `static` functions as you find useful. Your functions must obey the following conditions. - `mm_init`: Before calling `mm_malloc` or `mm_free`, the `driver` program calls `mm_init` to allocate and initialize the initial heap area. The return value of `mm_init` is $-1$ if there was a problem in performing the initialization and $0$ otherwise. - `mm_malloc`: `mm_malloc` returns a pointer to an allocated block payload of at least `size` bytes (the input parameter). The starter code uses an implicit-list approach with a first-fit strategy for finding an available block. If necessary, `mm_malloc` will extend the heap using the function `void * mem_sbrk(int incr)` which is implemented in the `memlib.c` package and simulates the system call `sbrk()`. Like the version of `malloc` supplied in the standard C library, this implementation of `malloc` always returns payload pointers that are aligned to 8 bytes. - `mm_free`: `mm_free` frees the block pointed to by `ptr`. It returns nothing. This routine is only guaranteed to work when the passed pointer (`ptr`) was returned by an earlier call to `mm_malloc` and has not yet been freed. The starter code uses an implicit-list approach with no coalescing. # The Testing Suite The driver program `mdriver.c` tests your `mm.c` code for correctness, space utilization, and throughput. The driver program is controlled by a set of *trace files* that are included in the tar file. Each trace file contains a sequence of allocate, reallocate, and free directions that instruct the driver to call your `mm_malloc`, and `mm_free` routines in some sequence. The driver `mdriver.c` accepts the following command line arguments: - `-t `: Look for the default trace files in directory `tracedir` instead of the default directory defined in `config.h`. - `-f `: Use the specified tracefile for testing instead of the default set of tracefiles. - `-h`: Print a summary of the command line arguments. - `-l`: Run and measure the `libc` version of `malloc` in addition to your code. - `-v`: Verbose output. Print a performance breakdown for each tracefile in a compact table. - `-V`: More verbose output. Prints additional diagnostic information as each trace file is processed. Useful during debugging for determining which trace file is causing your malloc package to fail. The driver program computes two metrics to evaluate the dynamic memory functions. - *Space utilization,* $U$, is the peak ratio between the aggregate amount of memory used by the driver (i.e., allocated via `mm_malloc` or `mm_realloc` but not yet freed via `mm_free`) and the size of the heap used by your allocator. The optimal ratio is 1. You should find good policies to minimize fragmentation in order to make this ratio as close as possible to the optimal. - *Throughput*, $T$, is the average number of operations completed per second. The driver program summarizes the performance of your allocator by computing a *performance index*, $P$, which is a weighted sum of the space utilization and throughput $$P = w{U} + (1-w) \min\left(1, \frac{T}{T_{\mathtt{libc}}}\right),$$ where $w$ is a weighting factor of $0.6$ and $T_{\mathtt{libc}}$ is $600K$ operations per second, an estimate of the performance of the native `libc` routines. Both memory and CPU cycles are expensive system resources. The test framework generates an overall performance score out of 100 based on a balanced between memory utilization and throughput. # Your Tasks To complete this homework, you need to complete two tasks. 1. **Coalescing:** Modify the `mm_free` function to implement coalescing. After this is done, re-run the driver code and make a note of how the utilization and throughput (and overall performance index) have changed. Make sure you take out the debugger flag (if you are using it) and re-compile your code before evaluating the performance! You might find this [Book chapter (look for "Splitting and Coalescing")](https://pages.cs.wisc.edu/~remzi/OSTEP/vm-freespace.pdf) helpful. 2. **Next Fit:** Implement the function `next_fit` to select the next available block that fits the desired size payload and modify the `mm_alloc` function to call this function instead of the `first_fit` function. After this is done, re-run the driver code and make a note of how the utilization and throughput (and overall performance index) have changed. Make sure you take out the debugger flag (if you are using it) and re-compile your code before evaluating the performance! This is covered by the video from Wednesday. **Hint:** You will need to modify your coalescing code when you implement next fit. Why? # Coding Rules Your code must obey the following rules. - You must not change any of the interfaces in `mm.c`. - You may not invoke any memory-management related library calls or system calls. This excludes the use of `malloc`, `calloc`, `free`, `realloc`, `sbrk`, `brk`, or any variants of these calls in your code. - You are not allowed to define any global or `static` compound data structures such as arrays, structs, trees, or lists in your `mm.c` program. However, you *may* use the existing global scalar values declared in `mm.c` (`top`, `base`, and `search`). - For consistency with the `libc` `malloc` package, which returns blocks aligned on 8-byte boundaries, your allocator must always return pointers that are aligned to 8-byte boundaries. The driver will enforce this requirement. # Hints and Suggestions ## Some General points - Use `mdriver -f`. During initial development, using tiny trace files will simplify debugging and testing. We have included two such trace files, `short1-bal.rep` and `short2-bal.rep`, that you can use for initial debugging. - Use `mdriver -v` and `mdrive -V`. The `-v` option will give you a detailed summary for each trace file. The `-V` will also indicate when each trace file is read, which will help you isolate errors. - Compile with `gcc -g` and use a debugger. A debugger will help you isolate and identify out of bounds memory references. - Understand every line of the starter code. I've tried to comment it thoroughly, but I strongly recommend you make sure you understand it before you start making changes. ## Heap Consistency Checker Dynamic memory allocators can be difficult to program correctly because they involve a lot of untyped pointer manipulation. I've provided a basic heap checker called `mm_check` that checks that the header and footer match for each block, that there are not adjacent free blocks, and that the end of the heap corresponds to the end of the last block. You are welcome to make changes to this function if you think of other checks that might be useful. This consistency checker is for your own debugging during development. Make sure to remove any calls to `mm_check` when evaluating your program as they will slow down your throughput. # Improving the allocator Although both of your tasks should improve the performance of the dynamic memory allocator, there is still a lot of room for improvement. These will all affect utilization and throughput in different ways. Collectively, a well-optimized allocator can have significantly better performance than the one implemented in this homework. (For reference, Prof. Birrell can achieve a performance index of 95/100.) If you have time and would like a challenge, you could think about how to further improve your allocator and/or try implementing some of those improvements. **Note:** This is not required, and it will not affect your grade. But I am happy to discuss your ideas. # Submitting Your Assignment You will submit your code and/or responses on gradescope. **Only one partner should submit.** The submitter will add the other partner through the gradescope interface. Additional details for using gradescope can be found here: - [Submitting an Assignment](https://help.gradescope.com/article/ccbpppziu9-student-submit-work) - [Adding Group Members](https://help.gradescope.com/article/m5qz2xsnjy-student-add-group-members) - [gradescope Student Help Center](https://help.gradescope.com/category/cyk4ij2dwi-student-workflow)