Computer Systems Organization

CSCI-UA.0201(005), Fall 2018

Lab-4: Malloc lab

Due: 11/29

Introduction

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.

This is an individual lab.

Obtaining the lab

$ cd cso-labs
$ git fetch upstream 
$ git merge upstream/master
This creates a number of new files in subdirectory malloclab/.
Change mm.c only

The only file you should modify for this lab is mm.c.

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_checkheap as they will slow down your throughput. Style points will be given for your mm_checkheap 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

All the tracefiles can be found in the traces/ subdirectory.

You can type $./mdriver -h to see a full list of command line options.

An example naive implementation

We give you an example naive implementation in mm-naive.c. You may compile it by typing make. You can test it by typing ./mdriver-naive. It passes all but one trace due to running out of memory. The naive implementation's performance is pretty bad.

Programming Rules

Programming Advice

Programming style:

Please avoid using C Macros (like those given in the textbook). Try to define your header as structs and use regular C helper functions to access your implicit/explict list. See mm-naive.c as an example for these helper functions.

Your code should have a header comment that describes the overall design of your malloc implementation: e.g. the organization of the free list. Each function should also have a header comment that describes what the function does.

Your heap consistency checker mm_checkheap should be thorough.

As is the case with other labs, you will be graded for style and we will deduct up to 20% of total lab points for bad style based on our subjective evaluation. Please read this style guide and follow the advice.

Apart from writing code in good style, you should follow these advice:

Evaluation

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 Procedure

To handin your files, simply commit and push them to github.com
$ git commit -am "Finish lab4"
$ git push origin 
We will fetching your lab files from Github.com at the specified deadline and grade them.