Figure 1: Used/free lists for first-fit address-ordered allocator
Introduction. Pintos, despite being a state-of-the-art OS in most respects, currently lacks a user-level memory allocator. Programs running on Pintos cannot make use of malloc() and free() (the C equivalents of C++'s new and delete), which obviously is a sad state of affairs.
In this project, you will implement a user-level memory allocator for Pintos. Along the way, you will learn about user-level memory allocation strategies, you'll learn how to use some of Pintos's code, and you'll gain your first bit of exposure to concurrent programming practices.
A memory allocator divvys up a large, continuous piece of memory into smaller pieces, called blocks. Blocks can be of different sizes. To allocate memory, an allocator needs to find a free block of sufficient size. If memory is deallocated (freed), the block in which the memory was contained is returned to the pool of free memory.
Using Lists. You should use two lists to keep track of the blocks that are in use and those that are free. The lists should be sorted by address. Initially, all available memory is kept in a single, large block that is added to the free list. The used list starts out empty.
You should use Pintos's list implementation in lib/kernel/list.c|h for this project. You should read these two files to familiarize yourself with the API. In particular, pay attention to the functions it provides to maintain sorted lists. You will use these lists in all future Pintos projects.
Figure 1: Used/free lists for first-fit address-ordered allocator
Allocation and First-Fit. Your allocator should use a "first-fit" strategy. If a request is made to allocate a certain number of bytes, your allocator should look for the first available block that has a size large enough to accommodate the request. If the block is larger than the memory that is requested, it must be split into two blocks: the first portion will contain the requested memory and is moved to the used list, the second portion will be added to the free list. A block is not split if the portion that would remain is too small to be kept on the free list.
Be sure to keep free and used lists always in order of increasing addresses. Your allocator should return a pointer to the beginning of the usable memory inside the allocated block. Your allocator should return NULL if it cannot satisfy an allocation request.
Even though first-fit may seem like a strategy too simple to be useful, it is actually a pretty good one. Other strategies include "best-fit" and "next-fit". A next-fit allocator picks the next available block like first-fit, but doesn't start over when a new request arrives. Next-fit generally does worse than first-fit. A "best-fit" strategy looks for the block that fits best, leaving the smallest remainder or none. This can have the unfortunate consequence that a lot of small memory blocks are returned to the free list. Eventually, there are many small blocks on the free list, which creates fragmentation. Fragmentation makes it impossible to satisfy a request for memory, even though the total amount of free memory is still larger than the requested amount. Different allocation strategies cause different amounts of fragmentation. Unfortunately, there is no universal best solution - for any strategy, you can construct a sequence of allocations and deallocations that creates fragmentation. In practice, for many types of workloads, best-fit and first-fit perform roughly the same, so the added overhead of best-fit does not always pay off.
Deallocation and Coalescing. If memory is freed, you must find the block of memory that contains the address of the pointer passed to the free routine. That block of memory must be removed from the used list, and it must be added to the free list. In addition, you'll have to coalesce the free list: if the blocks to its left or right are also free, they must be merged into a single block.
If the address that is passed to mem_free() does not correspond to a previously allocated block, mem_free() should return false. Otherwise, it should return true.
You should implement functions that report on the status of the used and free lists. Two functions that return their size, and two functions to dump the lists. We will call the size functions; the dump functions are for your own debugging use.
Assumptions. You may assume that the allocation function is called with a size that is a multiple of 4.
You may assume that mem_init() is called with a size that is a multiple of 4 and that is greater or equal to 16.
Our test harness will invoke your memory allocator and execute a series of allocation and deallocation requests. Finally, it will deallocate all allocated memory and check that you properly coalesced the free memory into a single, large block.
Thread Safety. Your memory allocator should be thread-safe. That is, it should be able to handle being invoked by multiple threads concurrently. To accomplish this, you must protect its data structures so that only one thread can access them at any given point in time. In the Pintos kernel, you would use lock_acquire()/lock_release() for this purpose. For now, we will use the POSIX thread API which is provided by Linux. You need to use the functions pthread_mutex_lock() and pthread_mutex_unlock(). You will also need to initialize the mutex or mutexes you will be using. To see how to do that, read the man pages for pthread_mutex_lock(P) and pthread_mutex_init(P). These are the only pthread functions you will need to use. We recommend that you first develop and test your allocator with one thread, and then add the necessary protection to pass the multi-threaded part of the test harness. (Tests 1, 2, and 4 are run by a single thread, only Test 3 exercises the allocator concurrently by multiple threads.)
Instructions. You will work in the pintos/src/prep directory for this assignment. Copy the pintos source tree into a directory of your choice; read-protect the directory:
cp -R ~cs3204/pintos/pintos pintos-project0 chmod go-rwx pintos-project0 cd pintos-project0/src/prepYou must add a file called memalloc.c to that directory that implements the memory allocator's interface, described in memalloc.h. Please read this file for specifics. memalloc.h also contains a struct memory_block definition you may use to represent blocks of memory.
You build the test harness using "make". This will build the test_mem executable. ./test_mem will run it.
Grading. This assignment will count for 40 points. Unlike for future projects, you are not required to submit a design document with this project. The points break down as follows:
10 points: passing Test 1. 10 points: passing Test 1 and 2. 5 points: passing Test 1, 2, and 3 - (includes proper use of locks for thread safety) 5 points: passing Test 1, 2, 3, and 4. 5 points: proper use of Pintos's list implementation. 5 points: adherence to coding standards outlined in Pintos project documentation.
Submission. You will submit your project using Curator. Instructions for that are here.
FAQ.
Q.: A production version of first-fit wouldn't use a simple doubly-linked list, would it?
A.: No, it would probably use a more scalable data structure. But a linear list is acceptable for this project.
Q.: What extra credit is there?
A.: For extra credit, implement best fit and compare the fragmentation produced by first-fit to the fragmentation produced by best-fit for the test harness's workload. Produce a report that outlines your results in a concise manner.
Q.: Can we make changes to test_mem.c?
A.: No. We will use the test_mem.c that we provided. Your implementation should be in memalloc.c which you'll write. You may make changes to memalloc.h if you deem them necessary.
Q.: Given the void* pointer passed to mem_free, how do I get a pointer to the surrounding memory block?
A.: Consider using the offsetof macro, which is explained here. Other options exists as well, but make sure your code compiles without warnings.