Lab 5: Writing a Dynamic Memory Allocator
Assigned | Monday, May 21 |
---|---|
Due Date | Friday June 1 |
Files | lab5.tar |
Videos | You may find the following videos helpful for getting started with the lab: |
Submissions | Submit your files via the Canvas assignments page (go to the Labs section, not the Homeworks section). Be sure to follow the detailed instructions at the bottom of this page. |
Learning Objectives and Overview
- Implement a memory allocator using an explicit free list.
- Examine how algorithm choice impacts tradeoffs between utilization and throughput.
- Read and modify a substantial C program.
- Improve your C programming skills including gaining more experience with structs, pointers, macros, and debugging.
In this lab, you will be writing a dynamic storage allocator for C
programs, i.e., your own version of the malloc
and free
routines. This is a classic implementation
problem with many interesting algorithms and opportunities to put
several of the skills you have learned in this course to good use. It
is quite involved.
Start early!
Code for this lab
- Browser (click to download): lab5.tar
- Terminal:
wget https://courses.cs.washington.edu/courses/cse351/18sp/labs/lab5.tar
Running tar xvf lab5.tar
from the terminal will extract the lab files to a directory called lab5
.
Instructions
The only file you will modify and turn in is mm.c
(unless you decide to do extra credit). You may find the
short README
file useful to read.
(In the following instructions, we will assume that you are
executing programs on the CSE VM or in your local directory
on attu
. For this lab, you can work anywhere there's a C
compiler and make
.)
Your dynamic storage allocator will consist of the following three
functions (and several helper functions), which are declared
in mm.h
and defined in mm.c
:
int mm_init(void);
void* mm_malloc(size_t size);
void mm_free(void* ptr);
The mm.c
file we have given you partially implements
an allocator using an explicit free list. Your job is to complete this
implementation by filling out mm_malloc
and mm_free
. The three main memory management functions
should work as follows:
-
mm_init
(provided): Before callingmm_malloc
ormm_free
, the application program (i.e., the trace-driven driver program that you will use to evaluate your implementation) callsmm_init
to perform any necessary initializations, such as allocating the initial heap area. The return value is -1 if there was a problem in performing the initialization, 0 otherwise. -
mm_malloc
: Themm_malloc
routine returns a pointer to an allocated block payload of at leastsize
bytes. (size_t
is a type for describing sizes; it is an unsigned integer that can represent a size spanning all of memory, so on x86_64 it is a 64-bit unsigned value.) The entire allocated block should lie within the heap region and should not overlap with any other allocated block. -
mm_free
: Themm_free
routine frees the block pointed to byptr
. It returns nothing. This routine is guaranteed to work only when the passed pointer (ptr
) was returned by an earlier call tomm_malloc
and has not yet been freed. These semantics match the semantics of the corresponding malloc and free routines in libc. Typeman malloc
in the shell for complete documentation.
We will compare your implementation to the version of malloc supplied in the standard C library (libc). Since the libc malloc always returns payload pointers that are aligned to 8 bytes, your malloc implementation should do likewise and always return 8-byte aligned pointers.
Provided Code for the Allocator
We define a BlockInfo
struct designed to be used as a
node in a doubly-linked explicit free list, and the following
functions for manipulating free lists:
BlockInfo* searchFreeList(size_t reqSize)
: returns a block of at least the requested size if one exists (andNULL
otherwise)void insertFreeBlock(BlockInfo* blockInfo)
: inserts the given block in the free list in a LIFO mannervoid removeFreeBlock(BlockInfo* blockInfo)
: removes the given block from the free list
In addition, we implement mm_init
and provide two helper
functions implementing important parts of the allocator:
void requestMoreSpace(size_t incr)
: enlarges the heap byincr
bytes (if enough memory is available on the machine to do so)void coalesceFreeBlock(BlockInfo* oldBlock)
: coalesces any other free blocks adjacent in memory tooldBlock
into a single new large block and updates the free list accordingly
Finally, we use a number of C Preprocessor macros to extract common
pieces of code (constants, annoying casts/pointer manipulation) that
might be prone to error. Each is documented in the code. You are
welcome to create your own macros as well, though the ones already included
in mm.c
are the only ones we used in our sample solution,
so it is possible without more. For more info on macros, check
the GCC
manual and/or two of the videos posted at the top of this page.
FREE_LIST_HEAD
: returns a pointer to the first block in the free list (the head of the free list)UNSCALED_POINTER_ADD
andUNSCALED_POINTER_SUB
: useful for calculating pointers without worrying about the size ofstruct BlockInfo
- Other short utilities for extracting the size field and determining block size
Additionally, for debugging purposes, you may want to print the contents
of the heap. This can be accomplished with the provided examine_heap()
function.
Provided Code for the Underlying Memory System
The memlib.c
package simulates the memory system for your
dynamic memory allocator. In your allocator, you can call the
following functions (if you use the provided code for an explicit free
list, most uses of the memory system calls are already covered).
-
void* mem_sbrk(int incr)
: Expands the heap byincr
bytes, whereincr
is a positive nonzero integer and returns a pointer to the first byte of the newly allocated heap area. The semantics are identical to the Unixsbrk
function, except thatmem_sbrk
accepts only a positive nonzero integer argument. (Runman sbrk
if you want to learn more about what this does in Unix.) -
void* mem_heap_lo()
: Returns a pointer to the first byte in the heap -
void* mem_heap_hi()
: Returns a pointer to the last byte in the heap. -
size_t mem_heapsize()
: Returns the current size of the heap in bytes. size_t mem_pagesize()
: Returns the system's page size in bytes (4K on Linux systems).
Provided Code for a Trace-Driven Driver Program
The driver program mdriver.c
tests
your mm.c
package for correctness, space utilization, and
throughput. Use the command make
to generate the driver
code and run it with the command ./mdriver -V
(the -V
flag displays helpful summary information as
described below).
The driver program is controlled by a set of trace files
that it will expect to find in a subdirectory
called traces
. The .tar. file provided to you should
unpack into a directory structure that places
the traces
subdirectory in the correct location
relative to the driver. (If you want to move the trace files around,
you can update the TRACEDIR path in config.h
). Each
trace file contains a sequence of allocate and free directions that
instruct the driver to call your mm_malloc
and
mm_free
routines in some sequence. The driver and the trace
files are the same ones we will use when we grade your
submitted mm.c
file.
The mdriver
executable accepts the following command
line arguments:
-
-t <tracedir>
: Look for the default trace files in directorytracedir
instead of the default directory defined inconfig.h
. -
-f <tracefile>
: Use one particulartracefile
for testing instead of the default set of tracefiles. -
-h
: Print a summary of the command line arguments. -
-l
: Run and measurelibc
malloc in addition to the student's malloc package. -
-v
: Verbose output. Print a performance breakdown for each tracefile in a compact table. -
-V
: More verbose output. Prints additional diagnostic information as each trace file is processed. Useful during debugging for determining which trace file is causing your malloc package to fail.
Programming Rules
- You should not change any of the interfaces in
mm.c
(e.g. names of functions, number and type of parameters, etc.). -
You should not invoke any memory-management related library calls
or system calls. This means you cannot use
malloc
,calloc
,free
,realloc
,sbrk
,brk
or any variants of these calls in your code. (You may use all the functions inmemlib.c
, of course.) - You are not allowed to define any global or
static
compound data structures such as arrays, structs, trees, or lists in yourmm.c
program. You are allowed to declare global scalar variables such as integers, floats, and pointers inmm.c
, but try to keep these to a minimum. (It is possible to complete the implementation of the explicit free list without adding any global variables.) -
For consistency with the
malloc
implementation inlibc
, which returns blocks aligned on 8-byte boundaries, your allocator must always return pointers that are aligned to 8-byte boundaries. The driver will enforce this requirement for you.
Collaboration
This is all a reminder, but an important one: In general we encourage students to discuss ideas from the labs and homeworks. But the code you submit must be your own. You must not refer to solutions from previous quarters or from a similar course at another university -- that is cheating. You must not consult a fellow student's solution -- that is also cheating.
We encourage you to start early and ask questions as needed. The course staff is here to help you succeed. But even if you do end up struggling and not completing the assignment to your full satisfaction, submitting a partial solution is much better than cheating.
Evaluation
Your grade will be calculated (as a percentage) out of a total of 64 points as follows:
- Correctness (45 points). You will receive 5 points for each test performed by the driver program that your solution passes. (9 tests)
- Style (10 points).
- Your code should use as few global variables as possible (ideally none!).
- Your code should be as clear and concise as possible.
- You should use provided macros whenever they do what is needed and make your code more readable. You will lose points if you reimplement code or use “magic numbers” where you should have used a macro instead.
- Since some of the unstructured pointer manipulation inherent to allocators can be confusing, we expect to see short inline comments on steps of the allocation algorithms. (These will also help us give you partial credit if you have a partially working implementation.)
- Each function should have a header comment that describes what it does and how it does it.
- Performance (5 points). Performance represents a small
portion of your grade. We are most concerned about the correctness
of your implementation. For the most part, a correct implementation
will yield reasonable performance. Two performance metrics will be
used to evaluate your solution:
- Space utilization: The peak ratio between the aggregate
amount of memory used by the driver (i.e., allocated via
mm_malloc
but not yet freed viamm_free
) and the size of the heap used by your allocator. The optimal ratio is 1, although in practice we will not be able to achieve that ratio. You should find good policies to minimize fragmentation in order to make this ratio as close as possible to the optimal. - Throughput: The average number of operations completed per second.
where U is your space utilization, T is your throughput, and Tlibc is the estimated throughput ofP = 0.6U + 0.4 min (1, T/Tlibc)
libc
malloc on your system on the default traces. The performance index favors space utilization over throughput. You will receive 5(P+ 0.1) points, rounded up to the closest whole point. For example, a solution with a performance index of 0.63 or 63% will receive 4 performance points. Our complete version of the explicit free list allocator has a performance index between just over 0.7 and 0.8; it would receive a full 5 points. Thus if you have a performance index GREATER THAN 0.7 (mdriver prints this as "70/100") then you will get the full 5 points for Performance. Observing that both memory and CPU cycles are expensive system resources, we adopt this formula to encourage balanced optimization of both memory utilization and throughput. Ideally, the performance index will reach P = 1 or 100% . To receive a good performance score, you must achieve a balance between utilization and throughput. - Space utilization: The peak ratio between the aggregate
amount of memory used by the driver (i.e., allocated via
- Reflection (4 points).
Hints
Getting Started
- Read these instructions.
- Read over the provided code.
- Take notes while doing the above.
- Draw some diagrams of what the data structures should look like before and after various operations.
- Understand every line of the malloc implementation in the textbook. The textbook has a detailed example of a simple allocator based on an implicit free list. Use this as a point of departure. Don't start working on your allocator until you understand everything about the simple implicit list allocator.
Debugging
- Use the
mdriver
-f
option. During initial development, using tiny trace files will simplify debugging and testing. We have included two such trace files (short1-bal.rep
andshort2-bal.rep
) that you can use for initial debugging. - Use the
mdriver
-v
and-V
options. The-v
option will give you a detailed summary for each trace file. The-V
will also indicate when each trace file is read, which will help you isolate errors. - Compile with
gcc -g
and usegdb
. The-g
flag tellsgcc
to include debugging symbols, sogdb
can follow the source code as it steps through the executable. TheMakefile
should already be set up to do this. A debugger will help you isolate and identify out of bounds memory references. You can specify any command line arguments formdriver
after therun
command ingdb
e.g.run -f short1-bal.rep
. - Write a function that treats the heap as an implicit list, and
prints all header information from all the blocks in the heap. Using
fprintf
to print tostderr
is helpful here because standard error is not buffered so you will get output from your print statements even if the next statement crashes your program. - Encapsulate your pointer arithmetic in C preprocessor
macros. Pointer arithmetic in memory managers is confusing and
error-prone because of all the casting that is necessary. We have
supplied maros that do this: see
UNSCALED_POINTER_ADD
andUNSCALED_POINTER_SUB
. - Use a profiler. You may find the
gprof
tool helpful for optimizing performance. (man gprof
or searching online forgprof
documentation will get you the basics.) If you usegprof
, see the hint about debugging above for how to pass extra arguments to GCC in theMakefile
. - Start early! It is possible to write an efficient malloc package with a few pages of code. However, it will be some of the most difficult and sophisticated code you have written so far in your career. So start early, and good luck!
Heap Consistency Checker
This is an optional, but recommended, addition that will help you check to see if your allocator is doing what it should (or figure out what it's doing wrong if not). Dynamic memory allocators are notoriously tricky beasts to program correctly and efficiently. They are difficult to program correctly because they involve a lot of untyped pointer manipulation. In addition to the usual debugging techniques, you may find it helpful to write a heap checker that scans the heap and checks it for consistency.
Some examples of what a heap checker might check are:
- Is every block in the free list marked as free?
- Are there any contiguous free blocks that somehow escaped coalescing?
- Is every free block actually in the free list?
- Do the pointers in the free list point to valid free blocks?
- Do any allocated blocks overlap?
- Do the pointers in a heap block point to valid heap addresses?
Your heap checker will consist of the function int
mm_check(void)
in mm.c
. Feel free to rename it,
break it into several functions, and call it wherever you want. It
should check any invariants or consistency conditions you consider
prudent. It returns a nonzero value if and only if your heap is
consistent. This is not required, but may prove useful. When you
submit mm.c
, make sure to remove any calls
to mm_check
as they will slow down your throughput.
Extra Credit
As optional extra credit, implement a final memory allocation-related
function: mm_realloc
. Write your implementation in
mm-realloc.c
.
The signature for this function, which
you will find in your mm.h
file, is:
extern void* mm_realloc(void* ptr, size_t size);
Similarly, you should find the following in
your mm-realloc.c
file:
void* mm_realloc(void* ptr, size_t size) {
// ... implementation here ...
}
To receive credit, you should follow the contract of the C
library's
realloc
exactly (pretending that malloc
and
free
are mm_malloc
and mm_free
, etc.).
The man page entry for realloc
says:
The realloc() function changes the size of the memory block pointed to by ptr to size bytes. The contents will be unchanged in the range from the start of the region up to the minimum of the old and new sizes. If the new size is larger than the old size, the added memory will not be initialized. If ptr is NULL, then the call is equivalent to malloc(size), for all values of size; if size is equal to zero, and ptr is not NULL, then the call is equivalent to free(ptr). Unless ptr is NULL, it must have been returned by an earlier call to malloc(), calloc() or realloc(). If the area pointed to was moved, a free(ptr) is done.
A good test would be to compare the behavior of
your mm_realloc
to that of realloc
, checking
each of the above cases. Your implementation
of mm_realloc
should also be performant. Avoid copying
memory if possible, making use of nearby free blocks. You should not
use memcpy
to copy memory; instead, copy
WORD_SIZE
bytes at a time to the new destination while
iterating over the existing data.
To run tracefiles that test mm_realloc
, compile using
make mdriver-realloc
. Then, run mmdriver-realloc
with the -f
flag to specify a tracefile, or first edit
config.h
to include additional realloc tracefiles
(realloc-bal.rep
and realloc2-bal.rep
) in the
default list.
Don't forget to submit your finished mm-realloc.c
along with mm.c
.
Extra Extra Credit
Do NOT spend time on this part until you have finished and turned in the core assignment.
In this extra credit portion, you will implement a basic mark and
sweep garbage collector. Write your implementation
in mm-gc.c
.
Some additional notes:
- To test the current garbage collector, use
make mdriver-garbage
which generates an executable calledmdriver-garbage
. - The driver assumes that you have a correctly working
mm_malloc
andmm_free
implementation. - The tester checks that all of the blocks that should have been freed are freed and that all of the others remain allocated. On success it prints "Success! The garbage collector passed all of the tests". You can look in
GarbageCollectorDriver.c
to see what the test code does. - This implementation assumes that the alignment is 8 bytes because the third bit of
sizeAndTags
is used as the mark bit to mark the block. - The function
is_pointer
only looks for pointers that point to the beginning of a payload (like Java), and will return false if it points to a free block. - Pointers will always be word aligned in the data block.
Don't forget to submit your finished mm-gc.c
along with mm.c
.
Lab 5 Reflection
Compile this code on attu or the CSE VM by saving it to, for example,lab5reflect.c
and compiling it with
gcc -Wall lab5reflect.c -o hmm
.
#include <stdlib.h> #include <stdio.h> // Assume called with one argument that is a positive number int main(int argc, char**argv) { int *p, *q; p = (int*)malloc(sizeof(int)); *p = 42; free(p); q = (int*)malloc(atoi(argv[1])*sizeof(int)); *q = 43; *p = 44; printf("%d\n",*q); free(q); }
- This program has a bug. Explain what it is. [1pt]
- If you run this buggy program with argument 2 (i.e.,
./hmm 2
), what happens? Give a plausible description of whatmalloc
andfree
might be doing that leads to this behavior. [1pt] - If you run this buggy program with argument 20 (i.e.,
./hmm 20
), what happens? Give a plausible description of whatmalloc
andfree
might be doing that leads to this behavior. [1pt] - If you run this buggy program with argument 40 (i.e.,
./hmm 40
), what happens? Give a plausible description of whatmalloc
andfree
might be doing that leads to this behavior. [1pt]
Submission Instructions
Submit the following files:
mm.c
mm-realloc.c
[if you did the extra credit]mm-gc.c
[if you did the extra extra credit]lab5reflect.txt
Once you're satisfied with your solutions, submit them via Canvas (link is at the top of this page).