In this assignment you will work with a partner to develop and benchmark a memory management package. You should 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).
As soon as possible, but no later than before class on Nov. 12, you should pick a partner. One of you should send a note to the instructor (perkins at cs), with your names and your CSENetIDs. Please put 303 partners in the email subject heading. We will use this information to assign you and your partner to a Unix project group and set up a project directory where you should create the code repository and any other files you need for this assignment.
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,
Please get started early. Even if you are working with a partner, there is enough to do that you will be in (big) trouble if you wait to begin until the weekend before this assignment is due. To encourage this, 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. Both people in 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.
The memory management package should include a header file mem.h and
a C implementation that specify and implement the following
four functions.
void* getmem(int 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 8-byte boundary (i.e., its address
should be a multiple of
8). 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 a NULL pointer.void freemem(void* p). Return the block of storage
at location p to the pool of available free storage. The pointer
value p must be 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
a 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(int* total_size, int* total_free, int* n_free_blocks).
Store statistics about the current state of the memory manager in the three
given variables.
The information returned 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 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 on the line about the free block,
but each free block should be described on a single output line that begins
with the block's address and length.In a production system, there would likely be a single implementation 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 definitions 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.mem_impl.h - header file with declarations of internal implementation
details shared by more than one of the above files. In particular,
this is where the declarations of the free list data structure(s) should
reside. This is the information required in more than one of the implementation
files, but that is not part of the public
interface.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.
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 orders. This program
should allow the user to specify parameters that control the test. The available
parameters, and their default values are given below. Trailing parameters can
be omitted, in which case default values are used (square brackets [] mean
optional, as is the usual convention for Unix commands).
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: low-order 32 bits of the system time-of-day clock (or
4 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 type them repeatedly.)
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 requests for
small blocks of storage interspersed with some larger ones. 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_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 - one line for each set of output
should be enough.
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.
attu)
and use it 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.) This repository
must be in the lab file system, not on a separate machine of your own.Makefile with at least the following targets:
bench (this should be the default 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,
and README).
You should turn in this file 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 unrelated files in the directory.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.The above section describes 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 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 int that gives its size, and a pointer to the next block on
the free list. To help keep data stored in dynamically allocated blocks properly
aligned, we require that all of the blocks be a multiple of 8 bytes in size,
and that their addresses also be a multiple of 8.
When a block is requested by 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 the 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 in 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 4K or 8K 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 block of 20K of storage, 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 guarantees that
the storage it returns is allocated on 8-byte, 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
executed, 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, then return 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 worry about this
possibility.
One other wrinkle: If getmem always starts
scanning the free list from the beginning when it is looking for a block of
suitable size, it is likely to leave lots of little fragments of unused 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.
Don't implement this at first, but once your code is running, you might experiment
with this idea to see if, or how much it helps.
Here are a few ideas that you might find useful. Feel free to use or ignore them as you wish.
The command line may 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 library getopt 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 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 4 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. On some 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.
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.
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. Later get freemem to work.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.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, etc.).get_mem_stats function may be useful during debugging
to see the effect on the free list is of various patterns of getmem and freemem requests.
Don't feel constrained to use it only to report the situation when required
in the benchmark program.asserts in your program,
they can be particularly useful while you are testing and debugging, particularly
to check that pointers are not NULL when they shouldn't be.
Use them liberally and add targets to your Makefile to generate debugging
versions of your code.A small amount of extra credit, way less that it is worth in proportion to the amount of extra work and learning involved, will be awarded for the following extension. 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. 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 immediately preceding and following storage 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.
DO NOT ATTEMPT 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 part of many distributions.
To help organize the implementation, you should turn in the project in two phases.
Part 1: Header files. 15% 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. The header files should be essentially complete;
the skeleton (stub) implementations (the .c files)
can contain functions with either empty implementations or a default return
statement. These files should be complete enough to compile
without errors when the files are unpacked in a directory on attu and
a make command
is executed there. The implementations may be more complete than this, but
they only need to compile cleanly; they don't need to work yet. These files
should also include a skeleton of the benchmark program with #includes for
the necessary headers and a skeleton main program. All files must contain
appropriate comments, particularly heading comments on functions and interfaces.
Part 2: Final code. This contains the complete project, including
the README file and everything else requested above.