May 9, 2022
mm.c file to Lab
4 on MoodleIn this lab you will be writing a dynamic storage allocator for C
programs, i.e., your own version of the malloc,
free, and (for extra credit) realloc routines.
You are encouraged to explore the design space creatively and implement
an allocator that is correct, efficient and fast.
The goals of this lab are
You can do this assignment individually or with a partner. You must fill out the partner survey regardless of whether you will be working with a partner. The survey gives you the option of requesting to be matched with a partner. Being matched is not guaranteed, as an odd number of people may request a partner. Late days may be used on this lab only if both partners have them remaining.
wget http://cs.carleton.edu/faculty/awb/cs208/s22/handouts/lab4-handout.tar tar xvf lab4-handout.tarThis will create a directory called lab4-handout that
contains a number of files. The only file you will be modifying and
handing in is mm.c. The mdriver.c program is a
driver program that allows you to evaluate the performance of your
solution. Use the command make to generate the driver code
and run it with the command ./mdriver -V. (The
-V flag displays helpful summary information.) The command
make test will provide nicely formatted information about
your overall lab grade. Detailed usage information for the
mdriver testing executable is described later.
The extracted directory contains the following:
Makefile – recipes for compilingmdriver.c – testing drivermemlib.h – memory/heap interfacemm.c – memory allocator implementationmm.h – memory allocator interfacetraces/ – several trace files (.rep) used
for simulated testingWhen you have completed the lab, you will hand in only one file
(mm.c), which contains your solution. The allocator you
build might work on similar platforms (no guarantees!), but it must work
on Linux for grading. Compile the allocator and test driver with make to
produce an executable called mdriver.
This assignment requires careful bit-level manipulation of memory using many of C’s unsafe pointer casting features without much structure. Your allocator code will not be enormous, but it will be subtle. Take planning seriously and work methodically. Ignoring this advice could cost hours or days. Also keep in mind that performance is a component of the grading for this assignment.
We recommend this path for preparation and development of a successful allocator:
You will modify mm.c to implement a memory allocator
with the interface declared in mm.h and the functionality
described below.
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);The provided mm.c file partially implements an allocator
based on an implicit free list. It provides skeletons of several helper
functions beyond the interface above and an implementation of
mm_malloc that uses these helper functions. Your job is to
complete the helper functions (and possibly add more of your own) as
well as mm_free to implement a memory allocator with good
balance of memory utilization and throughput. You may use any
implementation strategy that works (subject to programming rules), but
performance of your memory allocator is a large component of the grade.
There are many opportunities for extensions, whether in increasingly
sophisticated allocator implementations for better performance or in
analysis and error-checking tools.
Grading considers design, documentation, style, correctness, and performance.
The remainder of this document includes:
As you read this document, complete these exercises to familiarize yourself with heap layout, block layout, and the provided starter code. These exercises will help you design your allocator implementation before diving into messy implementation details. Good planning is key when developing low-level systems software. Feel free to discuss these exercises with your classmates. You can find solutions to these exercises on Moodle.
These exercises will help you plan your allocator implementation and avoid wasting time writing C code before you understand what you are doing. Tips:
Read mm.c to learn about the block layout. Assume words
are 8 bytes. Pay special attention to the early comments about block and
heap layout, as well as the code in mm_init.
#define a constant for this value.For the following questions, draw memory as an array of words (but
not to scale when using big numbers). Use the block layout rules from
mm.c and especially the heap setup code in
mm_init. Follow the style of heap drawings used in the
CSAPP book (Figures 9.36-9.38), but remember that block details will
vary. Always draw the heap header word, the heap footer word, and the
headers (and footers as needed) for all blocks in the heap.
Simulate the starter allocator code by hand starting from an heap
generated by a call to mm_init. Update a drawing of the
heap as you go, following the drawing guidelines from part A. Show
exactly what this starter allocator does, not your idea of what an
allocator should do. This will force you to read and understand the
provided code carefully in detail. Add comments as you go if it helps
you to keep notes in addition to the provided comments.
Starting from a fresh initial heap, simulate the following requests and update your drawing based on what the starter code allocator does:
p0 = mm_malloc(12);
p1 = mm_malloc(16);
p2 = mm_malloc(16);
mm_free(p0);
mm_free(p1);
p3 = mm_malloc(24);Starting from fresh initial heaps, simulate the traces
short1-bal.rep and short2-bal.rep from the
traces directory in the starter code. The format of trace files is
described here.
bp, write an expression using the
provided helper macros to return the allocation status of the block
preceding bp in memory order.find_fit employ?extend_heap coalesce its newly added space?
Consider that extend_heap is typically called only if no
existing free block is large enough to satisfy the current allocation
request.For each of the following features, add the feature by sketching
pseudocode comments within mm.c. Then, before working on
the next feature, simulate the allocator with this feature on the sample
traces from the previous part, drawing heap state as you go.
mm_free as
comments in the body of mm_free.place as comments in the body of place.coalesce as
comments in the body of coalesce.Write pseudocode at a sufficient level of detail that you can simulate clearly, but do not get tangled up in C-level pointer work. Well-written comments at this stage can remain as documentation when you move on to implementation in C.
The three main memory management functions should work as follows:
mm_init(), provided: Initialize the
heap. Before calling mm_malloc or mm_free, the
application program (i.e., the trace-driven driver program that you will
use to evaluate your implementation) calls mm_init to
perform any necessary initializations, such as allocating the initial
heap area. The return value should be -1 if there was a problem in
performing the initialization, 0 otherwise.mm_malloc(size_t size): allocate and return a pointer
to an allocated block payload of at least size contiguous
bytes or return NULL if the requested allocation could not
be completed.
size_t is a type for describing sizes; it is an
unsigned integer large enough to represent any size within the address
space.mm_free(void *ptr): free the block whose payload is
pointed to by ptr. It returns nothing. Assume that payload
was returned by an earlier call to mm_malloc and has not
been passed to mm_free since its most recent return from
mm_malloc.These semantics match the the semantics of the corresponding C
library malloc and free routines. Run
man malloc in the terminal for complete documentation.
The memlib.c package simulates the memory system for
your dynamic memory allocator. You can invoke the following functions in
memlib.c:
void *mem_sbrk(int incr): Expands the heap by
incr bytes, where incr is a positive non-zero
integer and returns a pointer to the first byte of the newly allocated
heap area. The semantics are identical to the Unix sbrk
function, except that mem_sbrk accepts only a positive
non-zero integer argument.void *mem_heap_lo(void): Returns a pointer to the first
byte in the heap.void *mem_heap_hi(void): Returns a pointer to the last
byte in the heap.size_t mem_heapsize(void): Returns the current size of
the heap in bytes.size_t mem_pagesize(void): Returns the system’s page
size in bytes (4K on Linux systems).mm_ function types in
mm.c or mm.h. You may add, remove, or change
helper functions in mm.c as you wish. Declare all helper
functions (other than the interface above) as static
(visible only within the file).malloc, calloc,
free, etc. You may use all functions in
memlib.c, but if you use the provided starter code, you
likely will not need additional uses of the memlib.c
functions.mm_malloc, mm_free, find_fit,
place, and coalesce) to describe what the
function does, what policy it follows (if applicable), and what it
assumes. Use inline comments to describe details as needed.You may take any approach to implementing the specified allocator behavior above. Your implementation will be evaluated based on correctness, performance, documentation, and style. This section suggests an incremental implementation strategy that allows you to choose what balance of implementation sophistication and performance you prefer.
Start with an implicit free list allocator implementation. If you wish to improve the performance of your allocator once you have implemented and tested an implicit free list approach, consider an explicit free list or other search, coalescing, and splitting strategies as next steps.
Convert your pseudocode feature implementations to C code one at a time, testing each before starting C code for the next feature.
mm_free.place.coalesce.Run tests on individual traces for [debugging] and on all traces for general testing and performance evaluation.
short1-bal.rep and
short2-bal.rep should work from the beginning, but they are
suitable only as small debugging samples.check_heap
to sanity-check each feature before implementing the next or to help
debug when things go wrong.Explicit free-list allocators must distinguish memory order from list order. Memory order refers to the order of blocks as arranged in the memory address space. We use the terms adjacent, preceding, predecessor, following, and successor to refer to memory order. List order refers to the order of blocks in the explicit free list. We use the terms next and previous to refer to list order. Confusing these orders will lead to tricky bugs.
The best way to develop an explicit free list allocator is to first develop a working implicit free list allocator and extend it to use explicit free lists. Save a copy of your implicit free list allocator before you start working on improving it, so you have a working allocator as a reference (and a fallback).
Some suggestions as you implement explicit free lists:
mm_free
while you complete initial development of the explicit free list.mm_init, find_fit,
place, and extend_heap to use your explicit
free list. Test.mm_free, splitting, and
coalescing for the explicit free list.A clean and efficient working explicit free list allocator should achieve a respectable performance index. To achieve even better performance, you could consider implementing deferred coalescing, the boundary tag optimization described in the textbook, alternative ways of splitting, or alternative search strategies. Segregated free lists (CSPP section 9.9.14) or approaches using self-balancing trees can very extremely efficient, but correspondingly tricky to get right. If you embark on this path, weigh difficulty of implementation against likely effect on performance index.
The mdriver program tests your mm.c
implementation for correctness, space utilization, and throughput. Build
mdriver with make and run it with the command
./mdriver -V. (The -V flag displays helpful
summary information as described below).
mdriver uses trace files to
simulate memory management workloads using your mm.c
implementation. A trace is a sequence of allocate and
free events. mdriver simulates a trace by calling
mm_malloc and mm_free for each corresponding
event in the trace in order.
The mdriver executable accepts the following command
line arguments:
-t TRACEDIR: Look for the default trace files in
directory TRACEDIR instead of the default directory defined
in config.h.-f TRACEFILE: Use one particular TRACEFILE
for testing instead of the default set of tracefiles.-h: Print a summary of the command line arguments.-l: Run and measure libc malloc in
addition to your mm.c implementation.-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 mm.c
implementation to fail.mdriver on individual traces for debugging:
./mdriver -V -f traces/your-favorite-trace.repmdriver on all traces for correctness testing and
performance evaluation: ./mdriver -Vtraces directory will cause your
allocator to run out of memory until you have completed all three
implicit allocator features.short1-bal.rep and
short2-bal.rep should work from the beginning. You may find
it useful to write additional traces for debugging.When learning about the starter code, you will simulate small traces. When testing and debugging, you may find it useful to write and test your own small traces.
Traces used by mdriver summarize the execution of a
program as a sequence of mm_malloc and mm_free
calls in a simple format.
A trace file contains 4 header lines:
Remaining lines after the header give a sequence of memory management events, one per line. Each event is either an allocate event or a free event:
a I SIZE indicates the Ith call to
malloc in the trace, requesting payload SIZE.
The ID I uniquely identifies the malloc call
and the allocation it makes, starting at 0 for the first allocation in
the trace.f I indicates a call to mm_free with
the pointer that was returned by the Ith
malloc call in the trace.The following example C code would generate the corresponding trace below it.
C code:
p0 = malloc(12);
p1 = malloc(16);
p2 = malloc(16);
free(p0);
free(p1);
p3 = malloc(24);128
4
6
1
a 0 12
a 1 16
a 2 16
f 0
f 1
a 3 24check_heap that scans the heap and checks it for
consistency. Make sure to remove all calls to
check_heap before submitting your code. It will definitely
affect performance evaluation. check_heap takes a
line number as a parameter, so that any error messages can be tagged
with the line where check_heap was called. You can do this
with
check_heap(__LINE__);The compiler will automatically fill in __LINE__ with
the correct line number.
A print_heap function is also provided that prints out
the current state of the implicit free list.
You may also find it helpful to extend the check_heap
function to check more detailed consistency properties. This becomes
most interesting when considering an explicit free list (or more
sophisticated) allocator. check_heap should return a
nonzero value if and only if your heap is consistent according to the
conditions you check.
Example checks to add:
Feel free to rename or split check_heap into multiple
static helper functions. When you submit mm.c, make sure to
disable any calls to check_heap as they will impact
performance.
mdriver.opt for performance evaluation.
The mdriver.opt executable is a second version of
mdriver that is compiled with aggressive compiler
optimizations enabled and assertions disabled. Run
make mdriver.opt to create it. Use mdriver.opt
for performance evaluation, but use the normal mdriver
during testing and debugging. Enabling optimizations and disabling
assertions may be necessary to reach the highest levels of performance,
but they can make debugging more difficult.
For the most part, a correct implementation based on our provided code will yield passable performance. Two performance metrics will be used to evaluate your solution:
mm_malloc but not yet freed via mm_free) and
the size of the heap used by your allocator. The optimal ratio equals to
1. You should find good policies to minimize fragmentation in order to
make this ratio as close as possible to the optimal.The driver program summarizes the performance of your allocator by
computing a performance index, \(P\), which is a weighted sum of the space
utilization and throughput \[ P = 0.6\times
U_{mm.c} + 0.4\times \min\left(1, \frac{T_{mm.c}}{T_{libc}}\right)
\] where \(U_{mm.c}\) is your
space utilization, \(T_{mm.c}\) is your
throughput, and \(T_{libc}\) is the
estimated throughput of libc malloc on your system on the
default traces.2 The performance index values both
good space utilization and good throughput, with slight preference
toward space efficiency.
Your allocator must balance utilization and throughput. A performance index of 70-80 or above (out of 100) is pretty good. For reference, an implicit free list with splitting and coalescing should achieve an index in the 50s.
Low-level unguarded memory manipulation code like this allocator is prone to subtle and frustrating bugs. There’s a reason you often use higher-level languages with more protections! The following strategies help to work effectively and responsibly to avoid frustration and confusion.
Review allocator concepts, complete the preparatory exercises, and read the provided code carefully. Never write code until you have a good idea of what you are doing and what is already there.
Expect things to go wrong. Anywhere your code relies on an assumption, check it explicitly. Explain to your partner why your code should work. Write error-prone code once carefully and reuse it.
GET,
PUT) and pointer arithmetic (PADD and
PSUB). This helps avoid pointer manipulation errors or at
least catch them early.Implement and test one feature (or sub-feature!) at a time, testing each before you start implementing the next. This will make it much easier to understand what code is involved in a bug.
gdb, check_heap, and especially
print_heap functions are the tools of choice. Here are some
strategies and other tips.
gdb to run the code until it crashes, then find the
line that crashed (and the context in which it executed) with
bt, backtrace, or where.gdb, inspect the arguments shown in the backtrace
or print variables to determine what ill-formed pointer was
dereferenced to cause a segmentation fault or what illegal values failed
an assertion.backtrace to see where the current function was
called. (Don’t just assume you know which function called this one. Get
the truth.)up and down in gdb to
step up and down the call stack, then print what you want
to see.mm_malloc and
mm_free are called many times during a single execution.
They depend on their arguments, but also the entire contents of the heap
as it exists when they are called, so changes made by earlier calls to
mm_malloc and mm_free affect data used by this
one.
check_heap function to scan the heap and
print_heap to print it.gdb with
call check_heap(0) or call print_heap() (these
functions will need to be called at least once in your code for this to
work).mm_malloc or
mm_free call.print_heap to be the most effective debugging
toolprintf at the beginning of each function with
the function name and the value of its arguments is often helpful.
Disable any printing in final version.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 and
short2-bal.rep) that you can use for initial debugging. You
can also write your own for targeted debugging/testing.mdriver -V option. The -V will
option will give a detailed summary for each trace file and indicate
when each trace file is read, which will help you isolate errors.check_heap and print_heap. Printing
the full contents of the heap on every memory management event costs
orders of magnitude more than the allocations or frees themselves.Before submitting, remove calls to check_heap,
print_heap, and any diagnostic printing that you added
outside of these functions.
Submit your mm.c file to Lab
4 on Moodle. You do not need to turn in anything else. If you are
working with a partner, only one person needs to submit (make sure both
of your names are in the top comment).
Your grade will be calculated from 100 points as follows:
mdriver tests (split evenly among the 11 provided
traces).mdriver performance index).You may use any implementation strategy that works (subject to programming rules). Allocator performance is a significant component of the grade for this lab. Do the arithmetic: a high-quality implicit free list allocator can achieve a reasonable grade.
reallocImplement a final memory allocation-related function:
mm_realloc. The signature for this function, which you will
find in your mm.h file, is:
extern void* mm_realloc(void* ptr, size_t size);The mm_realloc function returns a pointer to an
allocated region of at least size bytes with the following
constraints.
if ptr is NULL, the call is equivalent
to mm_malloc(size)
if size is equal to zero, the call is equivalent to
mm_free(ptr)
if ptr is not NULL, it must have been
returned by an earlier call to mm_malloc or
mm_realloc. The call to mm_realloc changes the
size of the memory block pointed to by ptr (the old
block) to size bytes and returns the address of the
new block. Notice that the address of the new block might be the same as
the old block, or it might be different, depending on your
implementation, the mount of internal fragmentation in the old block,
and the size of the realloc request.
The contents of the new block are the same as those of the old
ptr block, up to the minimum of the old and new sizes.
Everything else is uninitialized. For example, if the old block is 8
bytes and the new block is 12 bytes, then the first 8 bytes of the new
block are identical to the first 8 bytes of the old block and the last 4
bytes are uninitialized. Similarly, if the old block is 8 bytes and the
new block is 4 bytes, then the contents of the new block are identical
to the first 4 bytes of the old block.
To run tests with mm_realloc, switch out
mdriver.c with mdriver-realloc.c (to do this
rename mdriver-realloc.c to mdriver.c, and
delete or rename the original). To run mm_realloc
tracefiles, run the driver with the -f flag to specify a
tracefile, or first edit config.h to include additional
realloc tracefiles in the default list. The
realloc traces will not be evaluated for performance, only
correctness. Each of the two test cases is worth 3 points of extra
credit if it passes.
This lab is adapted from the Malloc Lab developed for Computer Systems: A Programmer’s Perspective by Randal E. Bryant and David R. O’Hallaron, Carnegie Mellon University, available here.↩︎
The value for \(T_{libc}\) is a constant in the driver
(6000 Kops/s) that was established by testing the throughput of
malloc and free on mantis.↩︎