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.
As soon as possible, but no later than 23.00 on Saturday, Feb. 13, you must pick a partner and notify us. One of you (only!) should complete this Catalyst web form by writing in the names and uwnetids of both partners.
We will use this information to set up a git
repository for your group on the CSE GitLab server. You must
use this repository for this assignment; you cannot use
another repository elsewhere. (And, as is true of all
assignments, your solution code should not be publicly
available on any repository where it could be accessed by
other students in the class this quarter or in the
future.)
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. If you do not have a partner by the deadline, you will be randomly assigned a partner for the assignment.
You and your partner will receive 1 point (1%) of the total credit for the assignment if you follow these instructions exactly - exactly one web form for the group filled out on time with the right information (names and uwnetids, not student id numbers).
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:
malloc
and free functions,
make, and
Please start now. Even though you are working with a partner, there is enough to do that you will be setting yourself a tremendous challenge 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).
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 submitted by your group.
The memory management package should include a header
file mem.h and C implementation files that specify and
implement the following five functions.
void* getmem(uintptr_t
size). Return a pointer to a new block of
storage with at least size 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
value size must be greater than
0. If size is not positive, or if for some
reason getmem cannot satisfy the request, it
should
return NULL. Type uintptr_t is
an unsigned integer type that can hold a pointer value
(i.e., can be converted to or from a pointer of
type void *, 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
location p to the pool of available free
storage. It should be assumed that the pointer
value p is one that was obtained as the
result of a call to getmem.
If p is NULL, then the call
to freemem has no effect and returns
immediately. If p has some value other than
one returned by getmem, or if the block it
points to has previously been released by another call
to freemem, then the operation
of freemem 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).freemem
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 to file
f showing the blocks on the free list. Each
line of output should describe one free block and begin
with two hexadecimal numbers (0xdddddddd,
where d 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.void check_heap(). Check
for possible problems with the free list data structure.
When called this function should use asserts
to verify that the free list has the following properties:
assert should fail and
cause the program to terminate at that point. Calls
to check_heap should be included in other
functions to attempt to catch errors as soon as possible.
In particular, include calls to check_heap at
the beginning and end of
functions getmem and freemem.
Include additional calls to check_heap
wherever else it makes sense.In a production memory manager 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 GitLab repository to manage the
shared files. Because of that, you should split your code into the
following set of files:
mem.h - header file containing the public
declarations of the functions (including appropriate
comments). This is the interface that clients of
your getmem/freemem package would
use.getmem.c - implementation of
function getmem.freemem.c - implementation of
function freemem.get_mem_stats.c - implementation of
function get_mem_stats.print_heap.c - implementation of
function print_heap.check_heap.c - implementation of function
check_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
file mem.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, print_heap.c,
and check_heap.c with each of you taking
responsibility for one or two of these files. You should
share responsibility for the header files as needed. Each of
you is responsible for testing the other's code.
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 Linux command
descriptions.
Synopsis: bench [ntrials [pctget [pctlarge [small_limit
[large_limit [random_seed ]]]]]]
Parameters:
ntrials: total number of getmem
plus freemem calls to randomly perform during this
test. Default 10000.pctget: percent of the
total getmem/freemem calls that should
be getmem. Default 50.pctlarge: percent of the getmem calls
that should request "large" blocks with a size greater
than small_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). Note: stdlib.h
provides rand()(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:
time.h has useful
timing functions,
like clock
for processor time.total_size quantity
from get_mem_stats, above).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.
Once your code is working without problems, you might want to
rerun bench after recompiling the code
with -DNDEBUG to turn off the assert
tests in check_heap to see how much faster the
code runs without them. However, leave
the check_heap tests on while developing and
debugging your code since this will be a big help in catching
errors.
You and your partner should share responsibility for this program and file however you wish.
Besides the software specifications above, you should meet the following requirements for this assignment.
.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.Makefile with at least the
following targets:
bench (this should be
the default target, meaning the first target). Generate
the bench executable program.test. Run
the bench test program with default
parameters. This should recompile the program first if
needed to bring it up to date.dist. Create an archive
named hw5.tar containing up-to-date
versions of all of the files that you need to turn in
(source
files, Makefile, git.log
output, and
README). This is the file you should turn
in when you are done. Note: use tar -cvf hw5.tar
FILES... to create the archiveclean. Remove
any .o files, executable, 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.make
TARGET (e.g., make dist).README file and include it in
the archive you turn in. This file should give a brief summary of:
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.git log and capture the output in a
file git.log showing the commit history in
your repository. Include this git.log file
with the other files you submit. Both you and your partner
should be regularly committing and pushing changes to your
repository and we expect the log to reflect reasonable
activity (but don't obsess about the number of
commits/pushes).clint to check for possible
style issues that may need correcting.You and your partner will be given a newly
created git repository hosted on the CSE
department's GitLab server
(https://gitlab.cs.washington.edu).
To get a new working copy of the repository if you are in
group aaronb22-vasisht, you should use the
following git command:
git clone git@gitlab.cs.washington.edu:cse374-16wi-hw5/cse374-hw5-aaronb22-vasisht.git
You will need to log on to GitLab and create an appropriate
ssh key for this command to work (and if it asks for a
password, you need to go back and fix the ssh key or create a
new one - git should not ask for a password if
everything is set up properly.)
See the course website for links to a CSE 374 GitLab Tutorial
and other reference information.
Caution: If you have trouble
getting git/GitLab to work properly, please use
office hours, the discussion board, or email to the course
staff to sort things out. Web searches for git
hints are particularly likely to lead you seriously astray,
suggesting all sorts of things that not only are not useful,
but could leave your repository in a strange, possibly
seriously damaged state that will be hard to unscramble.
The above sections describe what you need to do. This section gives some ideas about how to do it. We will talk about this 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 minimum size
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 NULL. The first
time getmem is called, it should discover that
the free list is NULL 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.
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.
Your code should work on, and we will evaluate it on, the CSE
Fedora systems (klaatu and the CSE virtual
machine). These are 64-bit machines, which means pointers and
addresses are 64-bit (8-byte) 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
(like this).
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 that's what we're testing!) 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.
As with all projects, you should start (very) small and incrementally build up the final project. Here are some ideas:
getmem
and freemem by implementing them as calls
to malloc and free. That will allow
work on the benchmark program to proceed independently of
getmem and freemem. Plus if there is a
problem later in the project, you can always substitute these stub
versions to see if the trouble is
in getmem/freemem or in the benchmark
program.getmem first by itself. Just
have freemem return without doing
anything. Get freemem working later.getmem/freemem requests.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.gdb to check that it really works as you
expect.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 your Makefile as the command for a
target with a suitable name
(e.g., test17, test42,
reallybigtest, etc.).get_mem_stats function may be useful during
debugging to see the effect on the free list of various patterns
of getmem and freemem requests. Don't
feel constrained to use it only to produce the required benchmark
program reports.check_heap() and other asserts in
your program. These can be particularly useful while you are
testing and debugging, particularly to check that pointers are
not NULL when they shouldn't be and that the heap
data structures have not been corrupted. In particular, include
calls to check_heap() at the beginning and end
of getmem and freemem to verify that
those functions don't introduce any obvious, checkable errors in
the free list. Leave the asserts
and check_heap() calls in your code even after
things seem to be working. You can always
put -DNDEBUG in a gcc command in
some Makefile target to disable asserts if you want
to run your code without them.valgrind is unlikely to be
particularly helpful for this assignment. We are
manipulating pointers in non-standard ways
and valgrind may report many spurious problems
that are not really errors.Here are a couple of things you could add to your memory manager once it's working.
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?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
was basis of the malloc/free
implementations in many C distributions.
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 committed and pushed to your GitLab 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 null statement if needed. 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 a 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.
Create a tar archive containing the source
files, a git.log file captured from the git
log command, and your Makefile and turn in
that archive file using the regular dropbox. We will look at
these files as well as the contents of your GitLab repository
to verify that everything is stored there properly.
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.