MP7: My, oh, my, oh, malloc!

CS 241, Spring 2010

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" or text editors "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 and a bit of profit, you'll be able to submit your malloc to a class contest.

What you must do

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

mem_dictionary *dictionary = NULL;
int dictionary_ct = 0;

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;
}

void *realloc(void *ptr, size_t size)
{
  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;
}

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

make clean
make

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

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

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 extra points, you can think about how to make your solution simultaneously fast and efficient with memory use.

Grading

• 3 points: Correctness of your program against our provided testers.
• 2 points: Efficiency of your program against our provided base statistics.
• 1 point: Rank of your program against other students in CS 241.

Grading for correctness

• 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-1
Memory was allocated, used, and freed!
%

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

Grading for efficiency

• Maximum heap usage
• Average heap usage
• Time to run program

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