Assigned: Tuesday, Feb 16, 2016
Due: Monday, Feb 22, 2016 at 10:30pm
Collaboration: Work with your assigned partner for this lab. You may use your classmates and their code as a resource, but please cite them. Sharing of complete or nearly-complete answers is not permitted.
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.
The starter code for this lab includes an implementation of a bump pointer allocator with non-functional free. This allocator allocates large chunks of memory (1MB) by calling mmap to request additional memory from the OS, then parcels this chunk out by “bumping” a pointer up through the chunk as memory is requested through calls to malloc, calloc, or realloc. This implementation should work for most simple programs, but it won’t work very well because you can’t actually free memory! Your job for this lab is to implement what is called an embedded freelist: a linked list of freed memory that malloc will use to satisfy memory allocations whenever possible. The trick here is that you can’t call malloc to create space for your linked list nodes: you will need to use the freed memory to store the linked list that tracks the freed memory. And before you ask, yes, I also find that a little mind-bending.
This allocator implementation is usable using what is called the LD_PRELOAD trick. 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. You can leave the files allocator/wrapper.h and allocator/gnuwrapper.cpp alone.
To run a program with your custom allocator, use a command line like the following:
LD_PRELOAD=allocator/myallocator.so vim allocator/allocator.c
This assumes you’re running the command from the root of your project directory. And yes, you’d be editing your allocator source code with vim while using your allocator.
You may find it useful to run programs with your allocator inside a debugger, which could help you track down bugs. To do this, you have to start things a little differently:
$ gdb my_test_program
Lots of gdb startup messages go here
> set environment LD_PRELOAD=allocator/myallocator.so
> run
If you’d like to learn how to use gdb, the cprogramming.com guide appears to cover the essentials.
Instead of just discarding memory when it is free, we would like our allocator to reuse this memory to satisfy requests from future calls to malloc.
One standard technique for implemention this behavior is to write a freelist.
A freelist is just a linked list that keeps track of all the freed objects.
The trick is that you can’t actually call malloc to create linked list nodes;
you will need to use the freed memory itself to store the linked list nodes.
Implement a single global freelist for your allocator.
When memory is freed, add it to the beginning of the freelist.
Whenever malloc is called, check through the freelist for the first free object that is large enough to satisfy the memory allocation request.
You should only get memory from the current chunk when there are no free objects that are large enough to return.
One other case to consider is when your current chunk is not large enough to satisfy the current memory allocation request. In this case, you should request a new chunk and handle the allocation from that chunk. You should also take the remaining memory in the old chunk and add it to the freelist; this is usable free memory that you do not want to waste!
Look at the example test in the tests directory, and use this as a template to write tests that thoroughly exercise your allocator’s functionality.
You should cover the basic behavior of malloc, free, calloc, and realloc.
These additional allocation functions are implemented in the wrapper code, which will call your xxmalloc, xxfree, and xxmalloc_usable_size implementations.
You should test specific functionality to try to track down bugs in your allocator. When your allocator has bugs, real programs will typically just crash when you use it.
To create a new test program, copy the entire tests/example directory to a new directory under tests. Add the name of that directory to the DIRS variable in tests/Makefile (separated by whitespace). Finally, you may want to edit the name of the executable by changing the TARGETS variable in your new test directory’s makefile. If you do so, you will need ot edit the test:: target in that makefile a well.
You can run all of the test targets from the root of your project by typing make test. If you have any failing tests, make will return that the build target failed; be sure to look above this message to see the assertion that failed.
Returning the first free chunk of memory that is large enough can be very inefficient.
For one, you could end up allocating 1MB to a malloc call that requested 1 byte.
Another issue is that you have to scan past tiny objects when handling a large request, which makes the allocator take quite a bit longer to return memory.
One solution is to use size classes and size segregated freelists to reduce wasted space. The idea here is that you round every allocation request up to the next power of two (or some other number like 48, 96, etc.). You then keep a separate freelist for each size class. When an object is freed, use its size to determine which freelist to add it to.
Update your allocator to use at least eight different powers of two, starting at 32 bytes. For objects that are too large to fit in the eight size class, you should use a fallback freelist that holds all large objects and satisfies allocation requests using the procedure from part A.