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

CS 241

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


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:

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?

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:

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


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:

Grading for correctness

To test the correctness of your program (4 points), we provided six testers: 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: 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: ...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: