MP2: My, oh, my, oh, malloc!

CS 241

Due: Tuesday, Feb. 14, 2012 at 11:59pm

Introduction

In this MP, you will re-implement the function heap-memory function calls malloc(), calloc(), realloc(), and free() in much the same way that valgrind re-implements many C-calls to understand how your program is using memory. Just like valgrind, you will be able to use almost any existing program with your new memory functions: this includes utility programs such as "ls" text editors like "vi", or any other programs that runs on Linux.

Your first goal will be a basic correct solution. Then, you can move on to improving your allocator's speed and/or efficiency of memory use. And for fun, you'll be able to submit your malloc to a class contest.

What you must do

In this MP, you will need to make working versions of malloc(), calloc(), realloc(), and free() without using the libc defined malloc(), calloc(), realloc(), and free() calls. Instead, you will interact directly with the heap via the sbrk() function call. For the purpose of this MP, you are not allowed to use any other form of storage. You may not use files, pipes, system shared memory, mmap, a chunk of pre-defined static memory, a chunk of pre-defined stack memory, other external memory libraries found on the Internet, or any of the various other external sources of memory that exist on a modern operating system. Your re-implement of malloc() must allocate heap memory using the sbrk() call.

We provide two types of files:

mreplace.c / mcontest.c / alloc-contest.c: Don't edit these file!
These files create the system environment to ensure that calls to malloc() and related memory functions are passed on to your memory functions and not the standard libc ones. You should not edit this file, as we will replace it with a new, clean copy when we run your program.
alloc.c: Edit this file!
This file provides blank implementations of malloc(), realloc(), and free(). Since calloc() is a trivial modification of malloc(), we provide a working version of calloc() that makes use of your malloc().

That's it! You now know the requirements for this MP. Note that we haven't specified how you should implement your memory allocator. You've learned a lot of different algorithms and data structures in CS 241 for how systems can manage memory and it's up to you to choose how to do it.

But don't worry; we'll provide some guidance. In the rest of this document we supply background to help you get started, and then discuss grading and the contest.

How to get started

A bad malloc

Memory allocation might seem a bit magical. But you might be surprised to find out how easy it is to write a memory allocator which actually works in some primitive way. Let's do it now. First, malloc():

void *malloc(size_t size)
{
return sbrk(size);
}

How does that work? Malloc gets a request for size bytes of memory. It then calls sbrk(size). This is a system call that asks the operating system to increase the heap by size bytes. sbrk() returns a pointer to this new memory, and away we go. Now, how about free?

void free(void *ptr)
{
}

That's right! It's empty. In a very limited way, this is a "correct" implementation. You could write programs that use this malloc and free. So what's wrong with this implementation?

We didn't check for errors when we called sbrk(). OK, that seems straightforward to deal with.
We haven't implemented calloc or realloc. But let's not worry about that now.
The big problem, as you have surely noticed, is that freed memory is never reused! The heap will get bigger and bigger every time we call malloc(), even if we always free() the memory. Pretty soon, we'll run out of memory in the computer.

To sum up, it's actually quite easy to request new memory from the operating system. Your memory allocator's other task is harder: do the necessary "bookkeeping" to track what chunks of memory are allocated, and where the free holes are.

Towards a better malloc

So how do we do this "bookkeeping"? Let's see what information we need. When free(ptr) is called, its job is to free the block of memory starting at ptr. But how many bytes long was that block? Sadly, we are told where the memory segment starts but not how big it is. Similarly, take a look at realloc(ptr, size): it must "define a new memory segment, copy the old memory segment content to the new memory segment, free the old memory segment, and then return the new memory segment". We find that to do that, we need three pieces of information:

The old memory location
The old memory size
The new memory size

Sadly, realloc() has as arguments only the old memory location and the new memory size. So to sum up, for both free() and realloc() we must store some bookkeeping information behind the scenes when the memory is first allocated with malloc(). Specifically, we need some way to figure out the memory segment size given only the memory location ptr.

Let's define some structure to correlate the old memory location to the old memory size; that way we can look it up later:

typedef struct _mem_dictionary
{
void *addr;
size_t size;
} mem_dictionary;

...and let's use global variables to keep a count of how many records are part of this structure, as well as a pointer to the first element of the dictionary:

mem_dictionary *dictionary = NULL;
int dictionary_ct = 0;

With these data structures set up, we can make simple modifications to malloc() so it initalizes the dictionary array when it starts up and stores the (memory address)->(size) record every time malloc() is called:

void *malloc(size_t size)
{
void *return_ptr = sbrk(size);

if (dictionary == NULL)
dictionary = sbrk(1024 * sizeof(mem_dictionary)); /* Note the use of sbrk() and not malloc(), since malloc() would create an infinite loop of calling malloc(). */
dictionary[dictionary_ct].addr = return_ptr;
dictionary[dictionary_ct].size = size;
dictionary_ct++;

return return_ptr;
}

Finally, we can create a realloc() function now that we have found a way to get access to the size of an existing memory segment:

void *realloc(void *ptr, size_t size)
{
if (!size) { free(ptr); return NULL; }

void *return_ptr = malloc(size);

if (!ptr)
return return_ptr;

size_t old_size = 0;
int i;
for (i = 0; i < dictionary_ct; i++)
if (dictionary[i].addr == ptr)
old_size = dictionary[i].size;

memcpy(return_ptr, ptr, old_size);
free(ptr);

return return_ptr;
}

...and, at this point, you have something closer to a working program. One of the remaining problems is that free() still does not mark memory that was allocated to the expanding stack to be reused (eg: a program that grabs 1 MB and then frees the 1 MB will run out of memory since each 1 MB given isn't the same 1 MB, but a different 1 MB). Also, the dictionary contains a fixed number of entries that will result in a segfault if malloc() is called over 1,024 times. Also, malloc() has still done nothing to attempt to intelligently reuse memory—which is where algorithms like First Fit and Best Fit would be used. Other inefficiencies exist in the code, too, that you may want to optimize as part of the contest element of this code.

Note that we do not mean to imply that you should even begin with the dictionary-based strategy above. For example, a common trick is to integrate the bookkeeping, or metadata, with the memory segments themselves. Specifically, when you get an allocation request for size bytes you can instead reserve a few bytes more. The first part of this memory is for your metadata; malloc then returns a pointer to the memory that comes after the metadata. But when free(ptr) is called, it can figure out where the metadata is based on ptr. You can then use the metadata space to, for example, store the length of the segment and pointers for a linked list of segments.

How to test your allocation functions

To compile the launcher that we provide, along with your re-implementation of malloc, run:

make clean
make

After a successful make, you will have compiled your malloc() as a shared library object (.so) and can use the launcher to launch any Linux program using your allocation library. To do so, run:

./mreplace <Program Name> [<Program Args> ...]

For example:

./mreplace /bin/ls
./mreplace /bin/ps -aef
./mreplace anyprogram
...

You will find that valgrind will not work on this program! The ./mreplace program works in the exact same way as valgrind, so running a command like valgrind ./mreplace /bin/ls will result in ./mreplace replacing the valgrind-defined malloc() call, just like valgrind replaced toe libc malloc() call. Since you control the entire memory allocation in this MP, it doesn't even make sense to even test if you've correctly free'd all of your memory. Therefore, the grading of this MP will be based entirely on execution.

Suggested plan

Start by trying out the "bad malloc" above. Then think about the data structures and algorithms you'll use for your bookkeeping. We suggest you get a simple solution up and running first. Then for more points, you can think about how to make your solution simultaneously fast and efficient with memory use.

Grading

The grading on this MP will differ from all other MPs. Since we're using the same hooks as valgrind, you'll find that running valgrind ./mcontest someprogram will end up with some rather weird behavior in some cases. Instead, we'll use several different programs to test your MP. The breakdown of the points will be:

4 points: Correctness of your program against our provided testers (each tester will be weighted evenely).
4 points: Once your program runs completely correctly, the efficiency of your program against our provided malloc statistics.

Grading for correctness

To test the correctness of your program (4 points), we provided six testers:

tester-1: A simple program that makes a single malloc() call, stores data in the returned memory, and free()s the memory.
tester-2: A simple program that makes many, very small malloc() calls, stores data in the returned memory, ensures that the data is not overridden by future malloc() calls, and free()s the memory. This test case is the first test case that will break by using our simple "bad malloc" that we provide here.
tester-3: A simple program that makes many, somewhat large calls to to malloc(). This test case is the first test case that will require you to reuse memory that has been free()'d, rather than simply continuously adding to the stack for each malloc() request.
tester-4: A simple program that generates a tree of increasingly smaller malloc() and realloc() requests. This test case is the first test case to make calls to realloc().
tester-5: A randomly generated series of requests to malloc(), realloc(), and free(). This test case is the first to make extremely unpredictable requests, allowing significant variation in performance with various algorithms.
tester-9: The same as tester-5, but with small requests placed after each malloc() that are never free()'d.
Additionally, a few system programs will be used as testers. (We'll update them by the end of this week, we want to make sure the server can handle these programs before finalizing them.)

To run the testers to examine the expected output, simply run the testers from the command line:

% ./tester-1
Memory was allocated, used, and freed!

A correct re-implementation of the functions required in the MP should result in running the same command inside ./mreplace resulting in the same output:

% ./mreplace ./tester-1
Memory was allocated, used, and freed!

Each output that matches correctly will award you an equal amount of points - for a total of 4 points. For your programs to be considered correct, they must PASS in the contest (see the specifics below); see the results for the offical results.

Grading for efficiency

While there are a number of metrics that a system library designer must be concerned with, we have chosen to look at three of the most important metrics to measure the efficiency of your program:

Maximum heap usage
Average heap usage
Time to run program

Instead of running with ./mreplace, a second executable file has been provided for you to examine the efficiency of your program: ./mcontest. Rather than simply replacing malloc() and other calls with the ones you've programmed in alloc.c, ./mcontest monitors your program's memory usage and records interesting statistics. Using ./mcontest works just like ./mreplace, except ./mcontest will print efficiency before it exits. For example:

% ./mcontest ./tester-4
Memory was allocated, used, and freed!
[mcontest]: STATUS: OK
[mcontest]: MAX: 1359776200
[mcontest]: AVG: 2191596.819109
[mcontest]: TIME: 20.552874

As reported by ./mcontest, the program makes use of 1,359,776,200 bytes, or 1.266 GB, of heap memory at its maximum and took a little over 20 seconds to run. (This would be a bad solution, you can certainly do better than these results!)

Once your program runs correctly (you will get 0 points if you don't pass ALL the test cases), we will look at how well your program runs relative to libc. Specifically:

If you program, on average, earns an averaged percentage performance relative (last row, bold number) to libc of 200% across our test cases, you will also earn the full 4 points.
For results below 200%, we'll apply the following formula score = 4 - ((OVERALL% - 200%) / 100).

If you scored 300%, score = 4 - ((300% - 200%) / 100) = 4 - (100 / 100) = 4 - 1.0 = 3.0
If you scored 350%, score = 4 - ((350% - 200%) / 100) = 4 - (150 / 100) = 4 - 1.5 = 2.5

...remember, you can see the results on the results page.

The malloc contest

"The malloc contest" looks to pit your re-implementation of memory allocating functions against your fellow students. There are a few things to know:

If we find our test cases aren't adequate, we will add new test cases that apply only to the contest. The test cases described above will be the ones used for grading.
Your most recent SVN submission will be fetched somewhat frequently. To submit your program into the contest, you simply commit your program!
We will run all submissions across various different test cases. Some of the test cases will be the testers we provide for the grading of this MP, but some will be real-world applications.
We will assign a score to each of the three categories (max heap, average heap, and total time) based on how well your program performs memory management relative to a standard.
We will look inside your SVN at ALLOCNAME.txt. The file will be used to as your screen name to display your results on the course website each time the contest updates. Currently, everyone's name is set simply to "Anonymous". (Be nice; anything out of bounds here may get you removed from the contest entirely.)
There will be prizes!
Using any form of methods of avoiding heap allocation for memory requested by malloc() will result in your submission being removed from the results. The goal of this MP isn't to break our contest (believe me, it wouldn't be hard), but to see how well you can write a memory allocation algorithm. This includes mmap(), using files, etc, etc.
All the usual rules on cheating applies; don't copy code from the Internet or others.
Each program has 30 seconds and 2.000 GB to run; after 30 seconds or 2.000 GB alloc'd, your program will be killed.
You can view the current standings from the results page.