Project 0

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. 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 easy 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.

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 memory deallocation function is only called with pointers that you previously returned from the allocation function. You may assume that the allocation function is called with a size that is a multiple of 4.

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. (The test harness will first run the single-thread test, then start multiple threads that exercise the allocator concurrently.)

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/prep

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:

25 points: passing the single-threaded case
 5 points: proper use of Pintos's list implementation. 
 5 points: proper use of locks for thread safety
 5 points: code quality.

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.

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.

Clarifications. These are clarifications and hints that resulted from some of the discussions in the class forum.

Q.: Can we assume the length passed to mem_init is a multiple of 4?

A.: Yes.

Q.: I'm passing your test harness even though my mem_alloc stub simply returns NULL. How come?

A.: The test harness is faulty in that it doesn't flag that case. Obviously you won't get credit for this trivial solution. In general, note that it is possible for mem_alloc to return NULL if it cannot satisfy an allocation request: either because memory is exhausted, or because there is fragmentation.

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.