CSCI 380 -- Lab 2b

Malloc Redux

This lab will leverage the same handout as before. You can also use your code from the prior lab as your starting point.

Logistics

Handout "Update" Instructions

Edit the Makefile and change the following two lines

#Part 1
CPPFLAGS += -DMALLOC_LAB_IMPLICIT
#Part 2
#CPPFLAGS += -DMALLOC_LAB_EXPLICIT

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

Working on the Lab

This should be functionally equivalent to your last lab; however, you must now change your implicit list to an explicit free list.

We must now manage next and free pointers which logically represent a doubly-linked list of free blocks. These pointers consume part of the payload of a free block. When a block is allocated, it will NOT have these pointers.

Here's a picture of how your heap may look after mm_init.

                  root                            base
                    |                               |
                    v                               v
    +---+---+---+---+---+---+---+---+---+---+---+---+
    |   |   |   | 4 |nextPtr|prevPtr|       | 4 | 0 |
    +---+---+---+---+---+---+---+---+---+---+---+---+
    0       1       2       3       4       5       6

Helper Code


typedef uint32_t tag;
typedef uint64_t word;
typedef uint8_t byte;
typedef byte* address;

#define ALIGNMENT (2 * sizeof (word))
#define WORD_SIZE sizeof(word)
#define OVERHEAD (2 * sizeof (tag))
#define MIN_BLOCK_SIZE 4


static inline uint32_t sizeOf (tag* base) {
  return *base & (uint32_t)-2;
}

static inline bool isAllocated (tag* base) {
  return *base & (uint32_t)1;
}

static inline tag* header (address base) {
  return (tag*)base - 1;
}

static inline tag* footer (address base) {
  return (tag*)(base + sizeOf (header (base)) * sizeof (word) - 2 * sizeof (tag));
}

static inline address nextBlock (address base) {
  return base + sizeOf (header(base)) * sizeof (word);
}

static inline tag* prevFooter (address base) {
  return header(base) - 1;
}

static inline tag* nextHeader (address base) {
  return footer(base) + 1;
}

static inline address prevBlock (address base) {
  return base - sizeOf (prevFooter (base)) * sizeof(word);
}

static inline address* nextPtr (address base) {
  return (address*)base;
}

static inline address* prevPtr (address base) {
  return (address*)base + 1;
}

Reminders

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.

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}}) \]

To earn full credit on this lab, you must achieve a minimum utilization of 75% and throughput of 600Kops on autolab.

Submission

Upload/submit mm.c to autolab

Hints