CSE 374 - Homework 6
Memory Management
Due in three parts:
Part 0 (1%): Pick a partner and send info by Saturday, Feb. 23 at 11:59 pm
Part 1 (14%): Repository, header files, and function prototypes/skeletons
by Thursday, Fe.b 28 at
11 pm
(NO LATE ASSIGNMENTS for this part)
Part 2 (85%): Final Code by Thursday, Mar. 7 at 11 pm
Synopsis
In this assignment you will develop and benchmark a memory management package. You are required to work with a partner on this project. You and your partner should turn in a single assignment, and both partners will receive the same grade on the project. Be sure to have both of your names on the assignment, but only turn in a single copy under one of your names (and turn in the project under the same name for both parts, please). Also remember that if you wish to use a late day or two for the final part of the project, both you and your partner must have those late days available.
Step 0 - Pick a partner. Now!
As soon as possible, but no later than 11:59 pm on Saturday, Feb. 23,
you must pick a partner and notify us. One of you (only!) should send a note to the instructor
(perkins at cs). The email subject must be exactly 374
partners, and please cc your partner so
that a reply-all will reach both of you. The email must contain both your name, your partner's name, and both of your uwnetids. We
will use this information to assign you and your partner to group and set
up a svn
repository you can use for this assignment.
You must work with a partner on this assignment; you cannot work alone. Part of the point of the assignment is to gain experience handling source code when more than one person is working on a project.
You and your partner will receive 1 point (1%) of the total credit for the assignment if you follow these instructions exactly (exactly one email message sent on time to the right address with the right subject heading, correct cc to partner, correct contents (names and uwnetids) ).
Assignment goals
This assignment continues our exploration of procedural programming, memory management, and software tools, as well as software development and working in groups. In particular, in this assignment you will:
- Implement and test a memory management package that has the same functionality
as the standard library
malloc
andfree
functions, - Gain experience using source-code management systems, in particular subversion,
- Gain further experience with software development tools like
make
, and - Gain experience working in groups.
Please start now. Even though you are working with a partner, there is enough to do that you will be in (big) trouble if you wait until the weekend before it is due to begin. To encourage you to get started now you are required to turn in skeleton files for your code fairly early in the project (details at the end of this writeup).
Requirements
The project consists of two main technical pieces: a memory management package, and a program to exercise it and report statistics. The members of your group will be in charge of different parts of the assignment, as described below. Ultimately, however, both of you are responsible for, and should understand and be able to explain, all of the code.
Memory Management
The memory management package should include a header file mem.h
and
C implementation files that specify and implement the following
four functions.
void* getmem(uintptr_t size)
. Return a pointer to a new block of storage with at leastsize
bytes of memory. The pointer to the returned block should be aligned on an 16-byte boundary (i.e., its address should be a multiple of 16). The block may be somewhat larger than the size requested, if that is convenient for the memory allocation routines, but should not be significantly larger, which would waste space. The valuesize
must be greater than 0. Ifsize
is not positive, or if for some reasongetmem
cannot satisfy the request, it should returnNULL
. Typeuintptr_t
is an unsigned integer type that can hold a pointer value (i.e., can be converted to or from a pointer of typevoid *
, or other pointer type, exactly). It is defined in header<inttypes.h>
(and also<stdint.h>
). See discussion below.void freemem(void* p)
. Return the block of storage at locationp
to the pool of available free storage. The pointer valuep
must be one that was obtained as the result of a call togetmem
. Ifp
isNULL
, then the call tofreemem
has no effect and returns immediately. Ifp
has some value other than one returned bygetmem
, or if the block it points to has previously been released by another call tofreemem
, then the operation offreemem
is undefined (i.e.,freemem
may behave in any manner it chooses, possibly causing the program to crash either immediately or later; it is under no obligation to detect or report such errors).
One additional implementation requirement: Whenfreemem
returns a block of storage to the pool, if the block is physically located in memory adjacent to one or more other free blocks, then the free blocks involved should be combined into a single larger block, rather than adding the small blocks to the free list individually.void get_mem_stats(uintptr_t* total_size, uintptr_t* total_free, uintptr_t* n_free_blocks)
. Store statistics about the current state of the memory manager in the three integer variables whose addresses are given as arguments. The information stored should be as follows:total_size
: total amount of storage in bytes acquired by the memory manager so far to use in satisfying allocation requests. (In other words, the total amount requested from the underlying system.)total_free
: the total amount of storage in bytes that is currently stored on the free list, including any space occupied by header information or links in the free blocks.n_free_blocks
: the total number of individual blocks currently stored on the free list.
void print_heap(FILE * f)
. Print a formatted listing on filef
showing the blocks on the free list. Each line of output should describe one free block and begin with two hexadecimal numbers (0xdddddddd
, whered
is a hexadecimal digit) giving the address and length of that block. You may include any additional information you wish on the line describing the free block, but each free block should be described on a single output line that begins with the block's address and length.
Dividing the Work
In a production implementation there would likely be a single .c
file
containing all of the above functions. One person would be responsible for
the implementation of that file, while the other person would test it. But
for this class, we want to divide the work so that you and your partner both
work on the details and use a svn
repository to manage the shared
files. Because of that, you should split your code into the following half-dozen
files:
mem.h
- header file containing the public declarations of the functions (including appropriate comments). This is the interface that clients of yourgetmem
/freemem
package would use.getmem.c
- implementation of functiongetmem
.freemem.c
- implementation of functionfreemem
.get_mem_stats.c
- implementation of functionget_mem_stats
.print_heap.c
- implementation of functionprint_heap
.mem_impl.h
- header file with declarations of internal implementation details shared by more than one of the above files. This is information required in more than one of the implementation files, but that is not part of the public interface, which is declared in filemem.h
. In particular, this is where the declarations of the free list data structure(s) should reside.
One person in your group should be the primary implementor in charge of getmem.c
;
the other person is in charge of freemem.c
. Similarly, you should
divide get_mem_stats.c
and print_heap.c
, with each
of you taking responsibility for one of these files. You should share responsibility
for the header files as needed. Each of you is responsible for testing the
other's code.
Test and Benchmark
You should implement a program named bench
, whose source code
is stored in a file bench.c
. When this program is run, it should
execute a large number of calls to functions getmem
and freemem
to
allocate and free blocks of random sizes and in random order. This program
should allow the user to specify parameters that control the test. The
command-line parameters, and their default values are given below. Trailing
parameters can
be omitted, in which case default values should be used. Square brackets []
mean
optional, as is the usual convention for Unix command descriptions.
Synopsis: bench [ntrials [pctget [pctlarge [small_limit
[large_limit [random_seed ]]]]]]
Parameters:
ntrials
: total number ofgetmem
plusfreemem
calls to randomly perform during this test. Default 10000.pctget
: percent of the totalgetmem
/freemem
calls that should begetmem
. Default 50.pctlarge
: percent of thegetmem
calls that should request "large" blocks with a size greater thansmall_limit
. Default 10.small_limit
: largest size in bytes of a "small" block. Default 200.large_limit
: largest size in bytes of a "large" block. Default 20000.random_seed
: initial seed value for the random number generator. Default: some more-or-less random number such as the the system time-of-day clock (or bytes read from/dev/urandom
if you're feeling adventurous).
(The parameter list is, admittedly, complex, but the intent is that this program
will be executed by various commands in your Makefile
(s), so you
will not have
to repeatedly type long command lines to run it.)
When bench
is executed, it should perform ntrials
memory
operations. On each operation, it should randomly decide either to allocate
a block using
getmem
or free a previously acquired block using freemem
.
It should make this choice by picking a random
number with a pctget
chance of picking getmem
instead
of freemem
.
If the choice is to free a block and all
previously allocated blocks have already been freed, then there is nothing
to do, but this choice should be counted against the ntrials
total
and execution should continue.
If the choice is to free a block, one of the previously allocated blocks should be picked randomly to be freed. The bench program must pick this block and update any associated data structures used to keep track of allocated blocks in amortized constant (O(1)) time so that the implementation of the bench program does not have unpredictable effects on the processor time needed for the test.
The next three parameters are used to control the size of the blocks
that are allocated. In typical use, memory managers receive many more requests for
small blocks of storage than large ones, and the order of requests is often unpredictable. To model this
behavior, each time a new block is allocated, it should be a large block with
probability pctlarge
; otherwise it should be a small block (use
a random number generator to make this decision with the requested
probability). If the decision is to allocate a small block, request a block
whose size is a
random
number between
1 and small_limit
.
If the decision is to allocate a large block, request a block whose size is
is a random number between small_limit
and large_limit
.
While the test is running, the benchmark program should print the following
statistics to stdout
:
- Total CPU time used by the benchmark test so far in seconds (show enough fractional digits to provide useful information if possible, although the granularity of the system clock may be too large for this to be meaningful for short tests).
- Total amount of storage acquired from the underlying system by the memory
manager during the test so far (e.g., the
total_size
quantity fromget_mem_stats
, above). - Total number of blocks on the free storage list at this point in the test.
- Average number of bytes in the free storage blocks at this point in the test.
The program should print this 10 times during execution, evenly spaced during
the test. In other words, the first report should appear after 10% of the total
getmem
/freemem
calls have executed, then after 20%,
30%, etc., and finally after the entire test has run. You may format this information
however you wish, but please keep it brief and understandable - one line for
each set of output numbers should be enough.
You and your partner should share responsibility for this program and file however you wish.
Additional Requirements
Besides the software specifications above, you should meet the following requirements for this assignment.
- You and your partner must use a subversion repository to store all of
the code and other files associated with the project. (But
don't
store
things
like
.o
files and executable programs that don't belong in a repository.) You must use the repository that we provide even if you have separate machines or accounts of your own that you use for other projects. - You should create a
Makefile
with at least the following targets:bench
(this should be the default target). Generate thebench
executable program.test
. Run thebench
test program with default parameters. This should recompile the program first if needed to bring it up to date.dist
. Create an archive namedhw6.tar
containing up-to-date versions of all of the files that you need to turn in (source files,Makefile
,svn.log
file, andREADME
). This is the file you should turn in when you are done.clean
. Remove any.o
files, executables, emacs backup files (*~
), and any other files generated as part of making the program, leaving only the original source files and any other files in the directory unrelated to the project.
- You should create a
README
file and include it in the archive you turn in. This file should give a brief summary of:- Who was responsible for which part of the project, and how the work was divided.
- A brief description of how your heap (free list) data structure is organized and the algorithms used to manage it.
- A summary of any additional features or improvements in your memory manager or benchmark code. If you did any extra credit parts of the assignment, be sure to describe that. If you experimented with various quantities such as the minimum size of a block fragment to keep on the free list, describe your experiments and results obtained.
- A summary of the results you observed on several runs of your
bench
program. This does not need to be exhaustive (or exhausting), but it should give the reader an idea of how your code worked, how fast it was, and how efficient it was in its use of memory. - A summary of any resources you consulted for information about memory management algorithms. Your code, of course, must be your own, but feel free to research and explore memory management topics.
- When you are ready to hand in your project, run the command
svn log
and capture the output in a filesvn.log
showing the change commit history in your repository. Include thissvn.log
file with the other files you submit. - Finally, your code should be of the usual high quality, with clean layout, good comments, and so forth. In particular, the comments describing the free list data structures should contain a complete but succinct description of this data so that someone can read these definitions and understand them without tracing the code that uses them.
Repository Notes
You and your partner will be given a newly created Subversion repository on
the machine cubist.cs.washington.edu
. The full repository name
to be used in svn
commands is https://cubist.cs.washington.edu/repos/cse374_13wi_
xx,
where xx is the one- or two-letter id for your group's repository.
For example, to get a new working copy of a repository if you are in group qz
,
you would use the following svn
command:
svn checkout https://cubist.cs.washington.edu/repos/cse374_13wi_qz
The first time you access a repository or create a working copy you will need
to enter your password and possibly your user id. These are different accounts
from
your
normal UW accounts and have a different password. If you are accessing the
repository from an account that has a different user name than the uw netid
that you gave us when we set up the group, you can specify the netid for the repository in the
svn
command, after which you will be prompted for the password. For example,
if your netid is xyzzy
and you are creating a working directory
on a machine from an account with a different user name, you could check out the files from your repository with
svn checkout --username xyzzy https://cubist.cs.washington.edu/repos/cse374_13wi_qz
Once you've created a working copy of a repository, the url
, your user id, and your password are stored locally in the
working copy and you shouldn't have to enter them again on subsequent svn
commands.
Memory Management
The above sections describe what you need to do. This section gives some ideas about how to do it. We will talk about this further in class, and you should take advantage of the online class discussion list to trade questions, ideas, and suggestions.
The basic idea behind the memory manager is fairly simple. At the core, the
getmem
and freemem
functions share a single data
structure, the free list,
which is just a linked-list of free memory blocks that are available
to satisfy memory allocation requests. Each block on the free list starts with
an uintptr_t
integer that gives its size followed by a pointer to the next block on
the free list. To help keep data in dynamically allocated blocks properly
aligned, we require that all of the blocks be a multiple of 16 bytes in size,
and that their addresses also be a multiple of 16.
When a block is requested from getmem
,
it should scan the free list looking for a block of storage that is at least
as large as the amount requested, delete that block from the free list, and
return a pointer to it to the caller. When freemem
is called,
it should return the given block to the free list, combining it with
any adjacent free blocks if possible to create a single, larger block instead
of several smaller ones.
The actual implementation needs to be a bit more clever than this.
In particular, if getmem
finds a block on the free list that is
substantially larger than the storage requested, it should divide that block
and return a
pointer to a portion that is large enough to satisfy the request, leaving
the remainder on the free list. But if the block is only a little bit larger
than the requested size, then it doesn't make sense to split it and leave a
tiny chunk on the free list that is unlikely to be useful in satisfying future
requests. You can experiment with this threshold and see what number is
large enough
to prevent excessive fragmentation, without
wasting too much space that could have been used to satisfy small requests.
The actual number should be a symbolic constant given by a #define
in
your code.
What if no block on the free list is large enough to satisfy a getmem
request?
In that case, getmem
needs to acquire a good-sized block of storage
from the underlying system, add it to the free list, then split it up, yielding
a block that will satisfy the request, and leaving the remainder on the free
list. Since requests to the underlying system are (normally) relatively expensive,
they should yield a reasonably large chunk of storage, say at least 4K or 8K
or more, that is likely to be useful in satisfying several future getmem
requests.
Normally the same amount is acquired each time it is necessary to go to the
underlying system for more memory. But watch out for really big getmem
requests.
If getmem
is asked for, say, a 200K block, it
needs to get at least that much in
a single chunk, since the underlying system cannot be relied on to return adjacent
blocks of storage on successive calls.
So what is "the underlying system"? For our purposes, it is the
standard malloc
function!
Your memory manager should acquire large blocks of storage from malloc
when
it needs to add blocks to its free list. malloc
normally guarantees that
the storage it returns is allocated on 16-byte or larger boundaries
on
modern systems, so we don't need to worry about whether the block we get from
malloc
is properly aligned.
Notice that a request for a large block will happen the very first time getmem
is
called(!). When a program that uses getmem
and freemem
begins
execution, the free list should be initially empty. The first time getmem
is
called, it should discover that the (empty) free list does not contain a
block large enough for the request,
so it will have to call the underlying system to acquire some storage to work
with.
What about freemem
? When it is called, it is passed a pointer
to a block of storage and it needs to add this storage to the free list, combining
it with any immediately adjacent blocks that are already on the list. What
freemem
isn't told is how big the block is(!). In order
for this to work, freemem
somehow has to be able to find the
size of the block. The usual way this is done is to have getmem
actually
allocate a
block of memory that is a bit larger than the user's request,
store the block size at the beginning of the block, and return to the caller
a pointer that actually points a few bytes beyond the real start
of the block. Then
when
freemem
is called, it can take the pointer it is given, subtract
the appropriate number of bytes to get the real start address of the
block,
and find
the size of the block there.
How is freemem
going to find nearby blocks and decide whether
it can combine a newly freed block with one(s) adjacent to it? There are various
ways to do this (as usual), but a good basic strategy is for getmem
and freemem
to
keep the blocks on the free list sorted in order of ascending memory address.
The block addresses plus the sizes stored in the blocks can be used to
determine
where a new block should be placed in the free list and whether it is, in fact,
adjacent to another one.
It could happen that a request to freemem
would result in one
of the underlying blocks obtained from the system becoming totally free, making
it possible to return that block to the system. But this is difficult to detect
and not worth the trouble in normal use, so you shouldn't deal with this
possibility in your code.
Implementation Suggestions
Here are a few ideas that you might find useful. Feel free to use or ignore them as you wish, although you do want to use the 64-bit pointer types correctly.
64-bit Pointers and ints
Your code should work on, and we will evaluate it on, the CSE Fedora 17 systems (klaatu
and the CSE virtual machine). These are 64-bit machines, which means pointers and addresses are 64-bit quantities. Your code will probably work on other 64-bit machines, and, if you're careful, will probably work on 32-bit machines if it is recompiled, although we won't test that.
One thing that is needed in several places is to treat pointer values as unsigned integers so we can do arithmetic to compute memory block addresses and sizes. We need to be able to cast 64-bit values between integer and pointer types without losing any information. Fortunately the library <inttypes.h>
contains a number of types and macros that make the job easier (and fairly portable!). The main type we want to use is uintptr_t
, which is a type that is guaranteed to be the right size to hold a pointer value so we can treat it as an unsigned integer. A pointer value (void*
or any other pointer type) can be cast to uintptr_t
to create an integer value for arithmetic, and uintptr_t
values can be cast to pointers if they hold integers that we want to treat as addresses. (There is also an intptr_t
type that is a signed integer type of the right size to hold a pointer, but for our project it would be best to stick with unsigned values.)
You can print pointers and uintptr_t
values with printf
. Use format %p
to print a pointer value, e.g., printf("%p\n", ptr);
. For uintptr_t
values, since these are stored as long, unsigned integers on our 64-bit systems, they can be printed as decimal numbers using the %lu
format specifier: printf("%lu\n",uintvalue);
. It turns out that <inttypes.h>
defines string macros that make it possible to print values without knowing the actual size of the underlying type. The magic incantation to print an uintptr_t
value ui
is printf("%" PRIuPTR "\n", ui);
. There are other formatting macros to do things like print signed integer pointer values as decimal numbers (PRIdPTR
) or in hex (PRIxPTR
). See a good C reference for details.
The Benchmark Program
The command line can contain several integer parameters. These need to
be converted from character strings ("500") to binary int
values.
There are various library functions that are useful: look at atoi
and
related ones. Take advantage of the Linux getopt
library function
if it helps.
The benchmark program relies heavily on random numbers. The standard library
function rand
can be used to generate sequences of pseudo-random
numbers. Given a particular starting number (the seed), rand
(or
any pseudo-random number generator) will always generate the same sequence
of numbers on successive calls. This can be very helpful during testing (i.e.,
things
are basically random, but the sequence is reproducible). If you want to generate
a different sequence of numbers each time the program is executed, you can
set the seed to some quantity that is different on each run - the system time-of-day
clock is a frequent choice, and should be the default if no seed is given on
the
benchmark program command line. Alternatively, modern Linux systems provide
a special file /dev/urandom
that returns random bytes whenever
it is read, and you can read bytes from here to get a random starting value.
One of the benchmark quantities that should be printed is the processor time
used. The clock
library function can be used to measure this.
Store the time right before starting the tests, then subtract this beginning
time from
the
current clock time whenever you need to get the elapsed time. Unfortunately,
on many Linux systems clock
is updated infrequently. If your test
is fast enough that
clock
has the same value before and after the test, don't worry
about it. Alternatively you can explore whether there are better timing functions
available. If you use one of these please be sure it is available on the CSE
Linux machines so the program will work when we run it.
Finally, the benchmark program needs to keep track of all of the pointers
returned by getmem
but not yet freed, and randomly pick one of
these to free when the "coin flip" says to free some storage. The
obvious way to handle this is to allocate a "big enough" array using malloc
(not using getmem
! Why?) and store the pointers there. When a pointer is
picked randomly to be freed, you can move another pointer from the end of the
list to
the spot occupied by the freed pointer and reduce the size of the list by 1.
That way, picking the pointer and updating the list can be done in O(1)
(constant) time, so the order in which the pointers are picked won't affect
the time needed
by the
benchmark
program
itself
to
run the tests.
Developing and Testing
As with all projects, you should start (very) small and incrementally build up the final project. Here are some ideas:
- You can create initial versions of
getmem
andfreemem
by implementing them as calls tomalloc
andfree
(!). That will allow work on the benchmark program to proceed independently ofgetmem
andfreemem
. Plus if there is a problem later in the project, you can always substitute these stub versions to see if the trouble is ingetmem
/freemem
or in the benchmark program. - You can implement
getmem
first by itself. Just havefreemem
return without doing anything. Getfreemem
working later. - Start small with tests involving very few
getmem
/freemem
requests. - The
print_heap
function can be very helpful during debugging. Get it working early. Also,gdb
can be very helpful in exploring the free list and examining the operation of your code. - Write several small test programs whose effect on the heap you can predict by hand,
then use the free list printout (above) and/or
gdb
to check that it really works as you expect. - Don't be shy about adding lots of targets to your
Makefile
to compile and run small test programs, or run the benchmark program with various argument values. If you find yourself typing the same command more than a few times to run a test, add it to yourMakefile
as the command for a target with a suitable name (e.g.,test17
,test42
,reallybigtest
, etc.). - The
get_mem_stats
function may be useful during debugging to see the effect on the free list of various patterns ofgetmem
andfreemem
requests. Don't feel constrained to use it only to produce the required benchmark program reports. - While you are not required to use
assert
s in your program, they can be particularly useful while you are testing and debugging, particularly to check that pointers are notNULL
when they shouldn't be. Use them liberally and add targets to yourMakefile
to generate debugging versions of your code.
Extra Credit
Here are a couple of things you could add to your memory manager once it's working.
- (easy) If
getmem
always starts scanning the free list from the beginning when it is looking for a block of suitable size, it is likely that eventually there will be lots of little fragments of free space at the beginning of the list. We can reduce fragmentation, and speed things up, if each subsequent search starts from where the previous search left off, wrapping around to the front of the free list if the end is reached before finding a suitable block. How does the output of your benchmark program change if you do this?
- (harder) Modify the free list and memory allocation routines so that blocks can be added to the free list and combined with adjacent blocks in constant time. One way to do this is the following, known as the boundary tag method. In addition to the header information at the beginning of each block containing its size, every block, both allocated and on the free list, should contain an extra few bytes at the end with length information and/or extra pointers and/or "free/allocated" bits. The idea is that when a block is being freed, we can look at the adjacent storage in the heap to find the end and beginning of the previous and next blocks, and from there we can determine whether they are free or allocated and how big they are without having to search the free list.
DO NOT ATTEMPT ANY OF THIS until you have completed the basic assignment and turned it in.
For more information, in addition to Google and Wikipedia, an authoritative
discussion is in Sec. 2.5, Dynamic Storage Allocation, in The Art of Computer
Programming, Vol. I: Fundamental Algorithms, by Donald Knuth. Doug Lea's
web site (http://g.oswego.edu/dl/html/malloc.html)
has good information about the allocator that he wrote that is basis of the malloc
/free
implementations in many
C distributions.
What to Turn In (and When)
To help organize the project, and to stay on schedule, you should turn in this assignment in two phases.
Part 1: Header files and repository. 14% of the total credit
for the entire assignment will be awarded for turning in a complete set of
header
files
and
skeleton implementations of everything required for the assignment, including
the basic Makefile
, and having these properly checked in to your svn
repository.
The header files should be essentially complete; the skeleton (stub) implementations
(the .c
files)
can contain functions with either empty implementations or a dummy return
statement
as appropriate. These files should be complete enough to compile without errors
when the files are unpacked in a directory on klaatu
or the 64-bit CSE Linux VM and
a make
command
is executed there. The implementations may be more complete than this, but
they only need to compile cleanly at this point; nothing needs to work yet. These files
should also include a skeleton of the benchmark program which #includes
the necessary headers and contains skeleton main function (return 0;
is
perfectly fine). All files must contain appropriate comments, particularly
heading comments
on functions
and
interfaces, and information in each file to identify you and the project.
You should also run the command svn list -v
showing the contents
of your repository
and capture the output in a file named svn.list
.
Create
a tar
archive containing the source files and the svn.list
file
and turn in that archive file using the regular dropbox.
Part 2: Final code. This contains the complete project, including
the README
file and everything else requested above. Use the make
dist
target in your Makefile
to create an archive containing all of the requested
files and turn that in.
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX