CSCI 380 -- Lab 2a

Your First Memory Allocator

The purpose of this assignment is to become more familiar with the concepts of dynamic storage allocators. You’ll do this by writing your very own versions of malloc, free, and realloc routines!

I have a handout which you should use to get started: lab2-handout.tar

Logistics

Handout Instructions

Copy and extract the handout code:

$ cd ~/cs380/
$ cp ~wkillian/Public/380/lab2-handout.tar .
$ tar xf lab2-handout.tar
$ cd lab2-handout

You will only be modifying the mm.c source code file. All other files should be left unchanged.

Working 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);

void* mm_realloc (void* ptr, size_t size);

I am providing you with an empty skeleton — it currently does not function as an allocator. Each of the functions have the following semantics:

  1. mm_init
    • Before calling mm_malloc, mm_realloc, or mm_free, the application program will call mm_init to perform any necessary initializations, such as allocating initial heap area or default-initializing any global variables
    • The return value should be -1 if there was some problem or 0 otherwise
  2. mm_malloc:
    • The mm_malloc routine returns a pointer to an allocated block payload of at least size bytes.
    • The entire allocated block must lie within the heap region and may not overlap with any other allocated chunk.
    • Your submission will be compared to the standard C library (libc) implementation. libc malloc always returns a payload pointer which is aligned to 16B (double-word), so your malloc implementation should do the same.
  3. mm_free
    • The mm_free routine frees the block pointed to by ptr
    • It will not return anything, however, this routine is only guaranteed to work when the passed pointer was returned by a prior call to mm_malloc or mm_realloc
  4. mm_realloc
    • The mm_realloc routine returns a pointer to an allocated region of at least size bytes with the following constraints:
      • If ptr is NULL, the call is equivalent to mm_malloc (size)
      • If size is 0, the call is equivalent to mm_free (ptr)
      • If ptr is not NULL, it must have been returned by an earlier call to mm_malloc or mm_realloc. The call to mm_realloc changes the size of the memory pointed to by ptr (the old block) to size bytes and returns the address of the new block. This means the address of the new block may be the same as the old block — or it might be different — depending on your implementation, the amount of internal fragmentation in the old block, and the size of the realloc request
      • The contents of the new block are the same as those of the old ptr block, up to the minimum of the old and new sizes. Everything else will be uninitialized. In other words, the first min (oldSize, newSize) will be identical
    • The semantics of these four functions match libc’s malloc, realloc, and free routines. You can type in man malloc within a terminal to read complete documentation on these functions

Checking Your Heap

Dynamic memory allocators are notoriously tricky beasts to program correctly and efficiently. This is hard. They are difficult to program correctly because they involve a lot of untyped pointer manipulation. You will find it extremely useful to write a heap checker that scans the heap and checks it for consistency.

Some examples of what a heap checker might check are:

You are also tasked with writing a heap checker. It will consist of a single function located in mm.c

int  mm_check(void);

The heap checker should check for any invariants or consistency conditions you consider prudent. It will return a non-zero value IFF your heap is consistent. You are not limited to the listed suggestions nor are you required to check all of them; however, you will be graded based on the quality of heap checker you choose to submit. Please note: it will also help reduced debugging time by iteratively writing it and adding error messages within mm_check if it does fail.

This consistency checker is for your own debugging during development. When you submit mm.c, be sure to remove any calls to mm_check as they will slow down your throughput score.

Support Routines

I cannot expect anyone to use sbrk() directly, so I’ve included a memory library which simulates the memory system for your dynamic memory allocator. You are welcome to use any of the following functions defined in memlib.h:

/* expands the heap by {incr} bytes.
 *   - {incr} must be positive, non-zero
 *   - returns a generic pointer to the first byte of the newly allocated heap area
 *   - semantically similar to the UNIX sbrk function
 */
void* mem_sbrk (int incr);

/*
 * returns a generic pointer to the first byte in the heap
 */
void* mem_heap_lo (void);

/*
 * returns a generic pointer to the last byte in the heap
 */
void* mem_heap_hi (void);

/*
 * returns the current size of the heap in bytes
 */
uint32_t mem_heapsize (void);

/*
 * returns the system's page size in bytes
 *   note: useful for optimizations
 */
uint32_t mem_pagesize (void);

The Trace-Driven Driver Program

I provide a nifty little tool called mdriver which is capable of measuring your implementation for correctness, space utilization, and throughput. The driver program is controlled by a set of trace files which are located in my public directory. Each trace contains a sequence of allocation, reallocation, and free directions that instruct the driver to call your mm_malloc, mm_realloc, and mm_free routines, respectively. Two “short” traces are provided as part of the handout tarball.

The driver driver accepts the following command line arguments:

Programming Rules

Evaluation

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

\[ P = wU + (1-w) min(1, \frac{T}{T_{libc}}) \]

Submission

Upload/submit mm.c to autolab

Hints