cs24-22fa Project 03: malloc

Introduction to Computing Systems (Fall 2022)

Introduction

In this project you will be writing a general purpose dynamic storage allocator for C programs; that is, your own version of the malloc, free, realloc, and calloc functions.

You are encouraged to explore the design space creatively and implement an allocator that is correct, efficient, and fast.

In order to get the most out of this project, we strongly encourage you to start early. The total time you spend designing and debugging can easily eclipse the time you spend coding.

Bugs can be especially pernicious and difficult to track down in an allocator, and you will probably spend a significant amount of time debugging your code. Buggy code will not get any credit.

Setup

Like usual, you should register for the assignment by going to https://grinch.caltech.edu/register which will create you a repository on gitlab with the starter code. We recommend doing all testing on labradoodle.caltech.edu, because the driver is tuned to the reference solution subject to the machine characteristics.

Roadmap

In previous terms, we have noticed that students who jump directly to trying to write a performant allocator usually spend a disproportionate amount of time on the project (in debugging-land where nobody wants to be). So, this term, we’ve provided a roadmap to keep you from creating a mess of code that is impossible to debug. Specifically, we’ve laid out smaller chunks at the beginning (“implement parts of an implicit list”) followed by a larger chunk at the end (“convert your implicit list to an explicit list”). Our hope is that this gets you to the point where you understand everything that’s going on by the time you try to write your explicit list. As a result, we’ve attached points to the first few tasks which also increases the possibility of partial credit.

Provided Support Functions

The memlib.c package simulates the memory system for your dynamic memory allocator. You can invoke the following functions in memlib.c:

You are also allowed to use the following libc library functions: memcpy, memset, printf, fprintf, and sprintf. Other than these functions and the support functions, your mm-implicit.c and mm-explicit.c code may not call any externally-defined function.

Required Functions

Your dynamic storage allocators will consist of the standard functions defined in an allocator library, which are declared in mm.h and defined in both mm-implicit.c and mm-explicit.c.

Because we are running on a 64-bit machine, your allocators must be coded accordingly. Notably, your allocators must work for heaps of up to \(2^{64}\) bytes. We will check this requirement manually and deduct a significant number of points if you ignore it.

The semantics for mm_malloc, mm_realloc, mm_calloc, and mm_free match those of the corresponding libc functions.

Programming Rules

The Trace-Driven Driver Programs

The driver programs generated when you run make test your mm-implicit.c and mm-explicit.c code for correctness, space utilization, and throughput. This driver programs are controlled by a set of trace files that are included in the traces subdirectory of your repository. Each trace file contains a sequence of commands that instruct the driver to call your malloc, realloc, and free functions in some sequence. The drivers and the trace files are the same ones we will use when we grade your assignment.

When the driver programs are run, they will run each trace file multiple times: once to make sure your implementation is correct, once to determine the space utilization, and between 3 and 20 times to determine the throughput.

The tester for the implicit list is called bin/mdriver-implicit, and the tester for the explicit list is called bin/mdriver-explicit.

You can use the -h flag to get a bunch of options on both drivers. Specifically:

Implicit List (30 points)

For the first section of this project, the only file you will need to edit is mm-implicit.c in which you will write an implicit list allocator. For this part, we will guide you through doing this in several steps that we believe make up the most efficient approach. In this part of the project, we ONLY care about space utilization. We will add in throughput in the next section.

Great job! You’ve now completed a pretty reasonable implicit list implementation. Next up is to convert it to an explicit list.

Explicit List (60 points)

Assuming your explicit list passes all correctness tests, and the graders do not detect any errors in your source code, two metrics are used to evaluate performance:

The driver will report a preliminary score after running all the tests.

The score you see is not a guaranteed grade. We will re-run the driver on your code during grading. We recommend running the driver multiple times to ensure that performance is consistent. When grading, we will use the labradoodle.caltech.edu machine. So, we recommend you test there.

The gitlab tests do not test performance; so, passing those is not a gurantee of any grade.

Extra Credit (+15 points)

Learn about balanced binary search trees (either red-black trees or AVL trees) and implement a malloc that uses one of these data structures as the free list. For extra-extra credit, develop traces that demonstrate that your tree is better than either list.

Performance Index

It is not necessary to read this section, but if you are curious how the performance scores are calculated, the details are here. Observing that both memory and CPU cycles are expensive system resources, we combine these two measures into a single performance index \(P\), with \(0 \leq P \leq 100\), computed as a weighted sum of the space utilization and throughput:

\[P\left(U,T\right) = 100\,\left(w \cdot {\min}\left(1, \frac{U - U_{Y min}}{U_{Y max} - U_{Y min}}\right) + (1-w)\cdot {\min}\left(1, \frac{T - T_{Y min}}{T_{Y max} - T_{Y min}}\right)\right)\]

where \(U\) is the space utilization (averaged across the traces), and \(T\) is the throughput (averaged across the traces, but weighted by the number of operations in each trace). \(U_{Y max}\) and \(T_{Y max}\) are the estimated space utilization and throughput of a well-optimized malloc package, and \(U_{Y min}\) are \(T_{Y min}\) are minimum space utilization and throughput values, below which you will receive 0 points. The weight \(w\) defines the relative weighting of utilization versus performance in the score. We have chosen \(w = 0.60\).

The values for \(U_{Y min}\), \(U_{Y max}\), \(T_{Y min}\), and \(T_{Y max}\) are constants in the driver (0.61, 0.85, 0 Kops/s, and 40,000 Kops/s) that we chose when we configured the program. This means that once you beat 85\% utilization and 40,000 Kops/s, your performance index is perfect. We computed these values relative to the performance of reference solutions.

Acknowledgements

This project is adapted from an assignment by R. Bryant and D. O’Hallaron at CMU.