In this lab you will be writing a dynamic storage allocator for C programs, i.e., your own version of the malloc, free and realloc routines. You are encouraged to explore the design space creatively and implement an allocator that is correct, efficient and fast.

For this lab, you may work in a group of one or two people.

Obtaining the lab

$ cd cso-labs/
$ git commit -am "commits for previous lab"
$ git pull
This creates a number of new files in subdirectory malloclab/. Note that:

Working on the Lab

In mm.c, you should implement the following five functions (which are declared in mm.h)
int    mm_init(void);
void*  mm_malloc(size_t size);
void   mm_free(void *ptr);
void*  mm_realloc(void *ptr, size_t size);
void   mm_checkheap(int verbose);
The existing code in mm.c implements the simplest but still functionally correct malloc package that we could think of. Using this as a starting place, modify these functions (and possibly define others), so that they obey the following semantics:

The malloc,free, realloc semantics match the the semantics of the C standard library's malloc, realloc, and free routines. Type man malloc for the complete documentation.

When implementing mm_init, mm_free, mm_mallocmm_realloc functions, you need to invoke the following functions which simulate the the memory system for your dynamic memory allocator. They are defined in memlib.c:

Checking Heap Consistency

Dynamic memory allocators are notoriously tricky beasts to program correctly and efficiently. They are difficult to program correctly because they involve a lot of untyped pointer manipulation. We ask you to write mm_checkheap to scan the heap and checks it for consistency. Some examples of what a heap checker might check are: Your heap checker will consists of the function void mm_heapcheck(int verbose), to be implemented in mm.c. It will check any invariants or consistency conditions you consider prudent. It returns a nonzero value if and only if your heap is consistent. You are not limited to the listed suggestions nor are you required to check all of them. This consistency checker is for your own debugging during development. When you submit mm.c, make sure to remove any calls to mm_check as they will slow down your throughput. Style points will be given for your mm_check function.

Testing for correctness and performance

We provide you with a tester program mdriver.c that tests your mm.c for correctness, space utilization, and throughput.

The tester mdriver reads a set of trace files, each of which contains a sequence of allocate, reallocate, and free events corresponding to some example application workload. It then calls your mm_malloc, mm_realloc, and mm_free routines according to the sequence of events.

To run the tester, type:

$ ./mdriver -V

The -V turns on verbose printing in the tester.

To run the tester on one specific tracefile instead of all of the default tracefiles, type:

$./mdriver -V -f tracefile
This is helpful when debugging failure with a particular tracefile. Type $./mdriver -h to see a full list of command line options.

Programming Rules

Programming Advice


You will receive zero points if you break any of the rules or your code is buggy and crashes the tester. Otherwise, your grade will be calculated as follows:

Handin instruction

To handin your files, type:
$ make handin
This creates a file called lab4.tar.gz. Submit it here