This assignment has two parts with the following due dates.

• Part 1: due Nov. 28, 11:59 pm

• Part 2: due Dec. 5, 11:59 pm

1    Introduction

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

2    Hand Out Instructions

Start by copying lab5-handout .tar .gz to your home directory on lcs-vc-cis341 .syr .edu machine. Then untar the tarball file to unpack the assignment in the directory.

unix>  cd  ˜/

unix>  cp  /home/cis341-proj/lab5-handout .tar .gz   .

unix>  tar  -xvf  lab5-handout .tar .gz

This will create a directory malloclab-handout with the necessary files for the project. The only file you will be modifying is mm .c. The mdriver p1 .c and mdriver p2 .c program is a driver program that allows you to evaluate the performance of your solution.  Use the command make to generate the driver code and run it with the command  . /mdriver_p1 or  . /mdriver_p2, for part 1 and part 2, respectively.

When you have completed the lab, you will hand in only one file (mm .c), renamed to mm p1 .c and mm p2 .c, for each part.

3    How to Work on the Lab

Your dynamic storage allocator will consist of the following four functions, which are declared in mm .h and defined in mm .c.

int      mm_init(void);

void  *mm_malloc(size_t  size);

void    mm_free(void  *ptr);

static  void  mm_coalesce(void  *ptr);

The initial mm .c file we have given you implements the simplest and partially correct malloc package that we could think of. Using this as a starting place, modify these functions (and possibly define other private static functions), so that they obey the following semantics:

• mm init: Before calling mm malloc or mm free, the application program (i.e., the trace-driven driver program that you will use to evaluate your implementation) calls mm init to perform any necessary initializations, such as allocating the initial heap area. The return value should be -1 if there was a problem in performing the initialization, 0 otherwise.

• mm malloc: The mm malloc routine returns a pointer to an allocated block payload of at least size bytes. The entire allocated block should lie within the heap region and should not overlap with any other allocated chunk.

We will compare your implementation to the version of malloc supplied in the standard C library (libc). While the libc malloc returns payload pointers that are aligned to 8 bytes, your malloc implementation must always return 16-byte aligned pointers.

• mm free: The mm free routine frees the block pointed to by ptr. It returns nothing. This rou- tine 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.

• mm coalesce: The mm coalesce routine combines multiple contiguous small blocks into one large block. The input is a pointer to one of these blocks, and the routine should check its adjacent blocks for coalescing.

You may create supporting functions within mm .c: in such a case, make sure you declare their prototype and definitions mm .c.

4    Support Routines

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

• void  *mem sbrk(int  incr):  Expands the heap by incr bytes, where incr is a positive non-zero integer and returns a generic pointer to the first byte of the newly allocated heap area. The semantics are identical to the Unix sbrk function, except that mem sbrk accepts only a positive non-zero integer argument.

• void  *mem heap lo(void): Returns a generic pointer to the first byte in the heap.

• void  *mem heap hi(void): Returns a generic pointer to the last byte in the heap.

•  size t  mem heapsize(void): Returns the current size of the heap in bytes.

•  size t  mem pagesize(void): Returns the system’s page size in bytes (4K on Linux systems).

• void  mem heap print(void): Prints the allocation status and boundary of blocks starting from the start of the heap.

5    The Trace-driven Driver Program

The driver program mdriver p1 .c and mdriver p2 .c test your mm .c package for correctness, space            utilization, and throughput.  The driver programs are controlled by a set of trace files that are located in            /home/cis341-proj/malloclab/traces. The difference between mdriver p1 .c and mdriver p2 .c is the set of trace files they use for testing.  mdriver p1 .c uses four relatively small traces, while            mdriver p2 .c includes a wider range of nine traces.  Each trace file contains a sequence of allocate            and free directions that instruct the drivers to call your mm malloc and mm free routines in some se-

quence. The drivers and the trace files are the same ones we will use when we grade your handin mm .c file.

The drivers mdriver p1 .c and mdriver p2 .c accept the following command line arguments:

•  -t  <tracedir>: Look for the default trace files in directory tracedir instead of the default directory defined in config .h.

•  -f  <tracefile>: Use one particular tracefile for testing instead of the default set of trace- files.

•  -h: Print a summary of the command line arguments.

•  -l: Run and measure libc malloc in addition to the student’s malloc package.

•  -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.

Running mdriver p1 with the initial, handout version of mm .c will output results similar to the follow- ing.

unix>   . /mdriver_p1  -v

Results  for  mm  malloc:

Perf  index  =  22   (util)  +  30   (thru)  =  52/100

The util column computes the memory utilization for each trace and their average. The Kops columns computes the throughput, based on data measured from ops and secs.  The Trace column shows the corresponding trace file that produced the result for each row, and the trace file is located in

/home/cis341-proj/malloclab/traces. The Perf  index represents the performance score for the implementation, using the average util and Kops. More details on the performance score will be

explained later in this handout.

On the other hand, running mdriver p2 using the initial, handout version of mm .c will output the follow- ing.

unix>   . /mdriver_p2  -v

Results  for  mm  malloc:

Terminated  with  3  errors .

This mm .c fails to correctly handle three traces:  coalescing-bal .rep, random-bal .rep, and random2-bal .rep. These failures are due to mem sbrk running out of memory, as this mm .c does not re-use freed space.

6    Programming Rules

• You will receive extra credit if you implement lazy coalescing. This means that mm free or any of its subroutines would not coalesce adjacent free blocks into one.  Instead, coalescing should occur during mm malloc. If you implement eager coalescing, you will not receive extra points.

• You should not change any of the interfaces in mm .c.

• You should not invoke any memory management-related library calls or system calls. This excludes the use of malloc, calloc, free, 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 are allowed to declare global scalar variables such as integers, floats, and pointers in mm .c.

• The libc malloc package returns blocks aligned on 8-byte boundaries.  However, your alloca- tor must always return pointers that are aligned to 16-byte boundaries. The driver will enforce this requirement for you.

7    Evaluation

Part 1 is worth 20 points in total (8 for correctness, 12 for performance), and part 2 is worth 30 points in total (18 for correctness, 12 for performance). There is an additional 5 point bonus that you may receive for part 2. You will receive zero points if you break any of the rules or your code is buggy and crashes the driver. Otherwise, your grade will be calculated as follows:

• Correctness (8 + 18 = 26 points). You will receive full points if your solution passes the correctness tests performed by the driver program. You will receive partial credit for each correct trace. Of the 20 points, 8 points are allocated for part 1, and 18 points for part 2.

• Bonus (5 points).  You will receive a 5 point bonus for part 2 if (1) you implement lazy coalescing (coalescing is not called during free or its subroutine), and (2) your implementation is correct across all nine traces.

• Performance (12 + 12 = 24 points).  The performance score is given only if the implementation is correct (i.e. passes all the traces). Two performance metrics will be used to evaluate your solution:

–  Space utilization: The peak ratio between the aggregate amount of memory used by the driver (i.e., allocated via mm malloc but not yet freed via mm free) and the size of the heap used by your allocator. The optimal ratio equals 1. You should find good policies to minimize fragmen- tation in order to make this ratio as close as possible to the optimal.

–  Throughput: 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 × min ( 1, ) + (1 − w) × min ( 1, )

where U is your space utilization, T is your throughput, and Tlibc is the estimated throughput of libc malloc on your system on the default traces.1  The performance index favors space utilization over throughput, with w = 0.7.

Observing that both memory and CPU cycles are expensive system resources, we adopt this formula to encourage balanced optimization of both memory utilization and throughput. Ideally, the performance index will reach P = w + (1 − w) = 1 or 100%. Since each metric will contribute at most w and 1 − w to the performance index, respectively, you should not go to extremes to optimize either the memory utilization or the throughput only.  To receive a good score, you must achieve a balance between utilization and throughput.

The initial, handout version of mm .c will correctly pass the four traces and achieve a performance score of ∼50 for part 1. This results in ∼ 14 (8 + 12 × 0.5) points for part 1. For part 2, however, the unmodified version will only pass six out of the nine traces, and not achieve any performance score. Thus, this will result in 12 points for part 2. Turning in the unmodified mm .c will thus achieve ∼26 out of the total 50 points.

You should make your implementation both correct (so that it works across all nine traces) and efficient (so that you receive more performance points). However, keep in mind that part 1 is evaluated on a subset of traces where the unmodified default version already passes all four traces.