For this lab, you will write a simple implementation of the malloc and free functions.
This simple memory allocation library will give you a much deeper understanding of pointers and memory management.
Building an allocator can be a bit painful: odds are your favorite C functions call a memory allocator, which means you can’t use them inside your allocator or you’ll end up with never-ending recursion.
But this is also a fun challenge;
building software in a limited environment to provide services to other programs is the essence of operating system implementation, and will help you fully appreciate the challenge and importance of careful system building.
Please read the following instructions carefully. There are quite a few important details in the implementation of this lab, and getting them wrong can lead to some very difficult-to-diagnose errors.
Download the starter code archive, malloc.tar.gz.
The starter code includes a simple, somewhat-functional heap implementation in allocator.c, along with a wrapper that allows you to replace the default allocator with your custom allocator when you run a program.
The “somewhat-functional” heap uses the mmap system call to request memory from the operating system every time malloc is called.
This is a terrible allocator!
The mmap system call returns pages of memory to the program, meaning we’re requesting at least 4096 bytes of memory for every allocation, even if we only allocate an int.
In addition to wasting an enormous amount of memory, free is not implemented so we never actually reclaim this space.
While the starter code implements a very bad allocator, it does work for some programs.
Most notably, it does not work for programs that call malloc often enough that the operating system runs out of space.
You can run some simple utities like ls or editors like vim if you don’t open a large file.
To run a program with your allocator instead of the default allocator, you will need to use the LD_PRELOAD environment variable.
This is a special environment variable that ld, the dynamic linker (linker dynamic?), looks at before starting a program.
Any libraries listed in this environment variable will be loaded before system libraries.
That means any functions you implement in a preloaded library will replace the default implementation.
There are some tricks to doing this correctly with a memory allocator (for one, the dynamic linker allocates memory, which creates some odd circular dependencies) so I have included a wrapper from a system called heap layers that takes care of most of this for you.
You just need to implement functions called xxmalloc, xxfree, and xxmalloc_usable_size in allocator.c.
Leave the files wrapper.h and gnuwrapper.cpp alone!
To run a program with your custom allocator, use a command line like the following (omit the dollar sign. This is how I show the shell prompt):
$ LD_PRELOAD=./myallocator.so ls
This assumes you’re running the command from the root of your project directory.
Everything should run as it usually does.
To make sure your allocator is actually running, you should break something.
Go to the xxmalloc function inside allocator.c and add a line return (void*)-1; to the beginning of the function.
After running make, test your allocator again.
This time, the ls command should fail, most likely with a segmentation fault.
Remove this intentional error now so it doesn’t cause problems later!
You can also run more complex programs like vim:
$ LD_PRELOAD=./myallocator.so vim
The program will probably start up okay, but if you open a large file you’ll probably run out of memory and vim will crash.
We’ll fix that later.
Speaking of crashes, you may find it useful to run programs with your allocator inside a debugger.
To do this, you have to start things a little differently.
This session starts the program ls with your custom allocator inside of gdb.
$ gdb ls
...
Lots of gdb startup messages will appear here
...
> set environment LD_PRELOAD=./myallocator.so
> run
If you want to start the program with command line options, they go immediately after the run command (on the same line).
Starting with our very bad allocator, you will implement what is often called a BiBoP allocator. BiBoP, short for “Big Bag of Pages”, is an old and well-known technique for allocating memory that uses a size-segregated heap. The job of a memory allocator is to request large blocks of memory from the OS, then parcel out smaller pieces of that memory to programs that request it. You could imagine an allocator that cleverly splits large blocks into smaller pieces, called allocated objects, when needed. A clever allocator could then coalesce adjacent freed objects into larger free objects so they can be used to satisfy larger requests in the future. While this approach has its place, it’s complicated, and has some significant downsides.
A size-segregated heap designates each large block of memory to hold objects of a single size. If you need to allocate objects of a different size you have to get them from a different block. This simplifies the allocator, and actually has some nice performance advantages as well. For one, we can store the size of allocated objects once per block instead of next to every object, so there is less wasted space for metadata.
It’s easiest to describe the structure of a BiBoP allocator by explaining how it handles requests.
Our allocator enters the picture when the main program calls malloc(27).
This call is directed to our allocator library, which passes the call along to xxmalloc(27).
We’re supposed to find a 27 byte space in memory and return it to the program.
Because our allocator dedicates an entire block to one size of object, we don’t want to keep blocks around for every unique object size.
Instead, the allocator will need to round this size up to one of the size classes our allocator uses.
There are some requirements for memory returned from malloc, which will influence our choice of size classes.
The most important requirement for our allocator is alignment;
Any pointer returned from malloc must be aligned to a 16-byte boundary on some systems, while others require eight-byte alignment.
To make our allocator more portable, we’ll use 16-byte alignment.
That means we have to make sure every small piece of memory we return occurs at an address that is a multiple of sixteen.
Note that an address aligned to a multiple of 16 will have zeros in its four rightmost bits.
Alignment constrains have an effect on our choice of size classes. Since we will align each object to a 16-byte boundary, we should use 16 bytes as our smallest size class. That means any smaller allocation will be rounded up to 16 bytes. Requests for more than 16 bytes of memory must also return 16-byte aligned addresses, so we need to choose size classes that make this alignment possible. The easiest choice is to use powers of two as our size classes. Consider the following example calls:
malloc(5) should be rounded up to a request for 16 bytesmalloc(16) should allocate 16 bytesmalloc(17) should be rounded up to a request for 32 bytesmalloc(48) should be rounded up to a request for 64 bytesmalloc(64) should allocate 64 bytesSince our example request was for 27 bytes, the allocator will need to round that up to 32 bytes. Now that we know which size class we are looking for, we need to find some memory to return to the program. There are two places we can get this memory: from the operating system, or from a freelist. We’ll look at the freelist first.
The freelist is a linked list of free memory locations, all of which must be the same size.
Your allocator will have a freelist for each size class, from 16 up to 2048 (we’ll talk about larger objects later).
The allocator only looks at the freelist for the size of the current request;
a call to malloc(27) should look in the freelist for 32-byte objects, but not other freelists.
If there is at least one free 32-byte object on the freelist, the allocator should remove it from the front of the list and return it to the program.
The freelist is a linked list, but you may recall from earlier assignments and labs that linked lists require allocating memory.
We’re writing an allocator, so calling malloc and free inside the allocator is likely to lead to infinite recursion.
The key insight from our reading for this lab is that the freelist is used to track free memory, so we can use the actual free memory itself to store our linked list nodes.
This technique, known as an embedded freelist, can be a bit difficult to grasp;
we’ll spend some time in class discussing this technique.
The basic ideas is that the address of the free memory itself is the value we are storing, and in that memory we can store a pointer to the next free object of the same size, or NULL if this is the last object in the freelist.
Returning to our example request for 27 bytes, what should the allocator do if it looks in the 32-byte freelist and finds that there are no free objects?
The only alternate source of memory is the OS.
In this case, the allocator will call mmap to request a larger block of memory.
For we will use a block size of one page to simplify things a bit.
Use the constant PAGE_SIZE, which is 4096.
Given this block of memory, the allocator must do two things: initialize the block with a header, and divide the block into free objects that should be added to the freelist.
When an object is passed to free, our allocator will need to make sure this is a valid pointer to a heap object, and determine the size of the object being freed.
We will do this using a header at the beginning of each block.
The header will have two fields: a magic number, and the size of the objects on this block.
The magic number should be some value you can check to verify that you are looking at a real block from the heap.
The size is just that; an integer that reports the size of the objects on the block.
Both fields should go at the beginning of the block, and must be written immediately after requesting a block of memory from the OS.
After placing the header at the front of the block, the allocator can divide the remaining memory up into free objects.
You will need to skip over the first free object, since it overlaps the block header.
The remaining space on the block is still usable, so you can walk through the block and add each object to the appropriate freelist.
If you are dividing a block for 32-byte objects, those objects should begin 32, 64, 96, 128, … bytes from the start of the block.
For a block that holds 128-byte objects, the objects should start at 128, 256, 384, 512, … bytes from the start of the block.
Aligning objects to multiples of the object size is a requirement for this lab, and makes it much easier to implement free later.
Once the allocator has divide the block into free objects and added them to the freelist, we are done with the block;
don’t free it, but you do not need to track its address.
Now that you’ve added some free objects to the freelist you can satisfy the call to malloc(27) by returning a 32-byte object from the 32-byte freelist.
At some point later, the program calls free(p).
The code in gnuwrapper.cpp does some boilerplate again and calls along to xxfree(p).
All we have at this point is a pointer to somewhere inside the object.
We don’t know the size of the object, and we don’t know if the pointer is at the beginning of the object or somewhere in the middle.
The first step is to find the size of the object.
You will need to know an object’s size to free it, but you’ll also have to implement xxmalloc_usable_size for the allocator to work properly.
You can call xxmalloc_usable_size from inside xxfree, so you might as well start out implementing this helper function.
Recall that every block begins with a header, and that header stores the size of all objects in the block.
Every block will begin at a multiple of PAGE_SIZE (4096 bytes), so you can simply round the pointer p down to the next lowest multiple of PAGE_SIZE.
This rounded-down address is a pointer to the block header.
Now you can check the magic number you wrote in the header to verify that this is a valid block from the heap, and then return the size from the header.
If free is called with a pointer that does not fall within a block (meaining you can’t find the magic number in your block header) you can just return without freeing memory.
You’ll need to handle free(NULL) specially, since looking for a block header here would cause a segmentation fault.
Now that we know the size of the object being freed, we need to figure out where it starts (the program may be freeing from an interior pointer). Because you carefully pareceled out free objects aligned to the object size (you did do that, right?) this just requires rounding down to the next multiple of the object size.
Finally, you know the size of the object being freed, and you have a pointer to the start of that object. Now you can add it to the appropriate freelist. It’s usually best to reuse freed memory as soon as possible, so add the freed object to the front of the freelist.
Before writing any code in your memory allocator, you should implement the computations to round object sizes to the next power of two and select the appropriate freelist.
This code is difficult to test inside of your allocator because you cannot call functions like printf when you are inside of xxmalloc.
The only POSIX functions you are allowed to call are the async signal safe functions listed on this page.
As a workaround, you can call snprintf to prepare a string to print, then write that string to stderr with the puts function;
this isn’t 100% guaranteed to work, but should be safe on MathLAN machines.
Becasue debugging inside your allocator is difficult, I recommend implementing your rounding code in a separate test program to make sure it works, then move it into your allocator once you trust it.
Warning: Rounding sizes is the number one cause of errors on this lab. Make sure your rounding code works correctly before moving on.
Implement xxmalloc for objects up to 2048 bytes.
You will need the code from part A to choose the appropriate freelist, along with new code to take an object off of a freelist, allocate new blocks, initialize the new block’s header, and add free objects from the block to the freelist.
We don’t have any code to compute the size of an allocated object yet, but you can assume that any allocated memory is at least 16 bytes.
Update xxmalloc_usable_size so it always returns 16 (unless it is given a NULL pointer, in which case it should return zero).
The gnuwrapper.cpp file defines realloc, which calls xxmalloc_usable_size to check if an object can be resized.
Once you’ve updated xxmalloc_usable_size to return the conservative lower bound of 16 you should still be able to run some simple programs, even though freeing does not work yet.
If you test a program and it crashes, check to see if xxmalloc is being asked to allocate more than 2048 bytes at a time (gdb breakpoints will be helpful here).
If so, you may have to skip ahead to part D before you can test your allocator;
many large object allocations happen as part of program startup and can be difficult to avoid.
Now that you can allocate objects, it’s time to support freeing them.
You will need to complete a full implementation of xxmalloc_usable_size to get the size of a freed object, then round to the start of the object and add it to the appropriate freelist.
Warning: Some programs will call free(NULL). In this case, your allocator should just return without doing anything.
Accessing a block header for NULL will result in a segmentation fault, so you have to check for this case.
We don’t want to deal with large objects using our BiBoP structure, so we’ll just fall back to mmap.
For any object larger than 2048 bytes, we’ll use mmap to satisfy the request instead of our heap structure.
You will need to round these allocations up to the next multiple of PAGE_SIZE.
One difficult issue with large objects is in the free implementation.
Your allocator will not find a block header at the beginning of a large object, so free will do nothing.
You don’t need to do anything else for this lab—you can just leak large objects.
if you would like an extra challenge, implement support for freeing large objects. You will need to devise a scheme to keep track of where allocated large objects are, and to find their beginning pointers and sizes given a pointer that may be in the middle of a large object. I’m happy to discuss strategies for implementing this if you have an idea you’d like to try.
Your final submitted allocator should work on simple command line utilities, as well as with gcc, vim, top, and the lynx command line web browser.
In addition to testing your allocator with some simple programs, you can use the same testing script I will use to assign a portion of your grade on this lab.
To get the test program, download and extract malloc-test.tar.gz.
The test program enforces some properties that are specific to this allocator design, so even the standard libc malloc will not receive full credit on this lab. The requirements for your allocator are:
malloc(24) should return a pointer to 32 bytes of memory that is aligned at an address that is a multiple of 32.If you find that you are failing some of these tests, make sure your implementation of xxmalloc_usable_size is working correctly.
This function is an important part of the testing process, so an incorrect implementation can cause many other tests to fail.