git pull on cse374-materials to get the updated starter code (in HW6)This assignment continues our exploration of procedural
programming, memory management, and software tools. In particular in this
assignment you will: implement and test a memory management package that
has the same functionality as the standard library malloc
and free functions. You will develop and use a benchmarking
program to exercise your memory management code. You will exercise your
skills in pointer management, as well as use a test framework and Makefile.
Requirements
Memory management design
Suggestions
Turn-in instructions
In this assignment you will develop and benchmark a memory management package. Starter code will be provided for you to use, and is available through the CSE374-materials git repository. This is a large assignment and is worth a total of 75 points. You will be graded on the correctness of your memory management as well as your use of the benchmarking and Makefile to build your project.
You may work in a team for this assignment. If you wish to work with a team mate you must submit a request via Canvas by Wednesday Nov., 23. We will create a shared gitlab repository for your team to use. Please notice that each participating team member will recieve the same grade at the completion of this project. In order to be considered a participating team member you must have commits on the gitlab repository.
You should use your git repository on the CSE GitLab server 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.)
The project consists of two main technical pieces: a memory management package, and a program to exercise it and report statistics. While starter code is provided to give you a jump on development, you are ultimately responsible for both portions of the code and for making them work together.
The code provided implements the headers (and therefore defines a datatype) as well as some of the functions described below. You will need to look through the code to determine what remains to be completed, and how to make it work with the existing functions. You may modify any of the supplied code, and at the minimum Makefile, bench.c, getmem.c freemem.c.
The memory management package should include a header
file mem.h and C implementation files that specify and
implement the following four functions.
| Function | Description |
|---|---|
void* getmem(uintptr_t size) |
Return a pointer to a new block of storage with at least |
void freemem(void* p) |
Return the block of storage
at location |
void get_mem_stats( |
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:
|
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 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.
|
In addition, there should be a separate header file mem_impl.h
and C implementation file for the following function,
which is used internally in the memory manager implementation,
but is not intended to be used by client code.
| Function | Description |
|---|---|
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 this assignment we will break the memory system into three files: mem_utils.c contains the functions for evaluating the memory manager. getmem.c will implement getmem, and freemem.c will implement freemem. Helper functions should be placed in the module where they are used, or in mem_utils.c if they are used by both getmem and freemem. The memory system is declared
in two header files: mem.h defines the user facing functions and can be included in the bench program. mem_impl.h defines the utility functions and is the 'back-end'. There is one final file which is bench.c which contains the benchmarking code.
Note: In a production memory system the entire module may contain one header (mem.h), and one implementation function (memory.c). The second header (mem_impl.h) would be unecessary because those declarations could be in memory.c. The code is divided up for convenience in assignment distribution. Your primary job will be to implement the memory functions, and add functionality to bench and Makefile. Please read the comments in the provided code carefully.
In addition to completing getmem and freemem, 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).(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 allocate a block, then, if
the pointer returned by getmem is not
NULL, the bench program
should store the value 0xFE in each of
the first 16 bytes of the allocated block starting at the pointer
address returned by getmem. If the requested block size is
smaller than 16 bytes, all of the requested bytes should be initialized
to 0xFE.
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 specified 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 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.
Besides the software specifications above, you must meet the following requirements for this assignment.
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.clean. 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.Readme file to accompany your work
This file should give a brief summary of:
bench program. This does not need to be
exhaustive (and should not be 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.cpplint to check for possible
style issues that may need correcting. (Note: cpplint may flag rand
and ask you to use the multi-threaded version. For this reason we have
included a version of cpplint in the hw6 folder that removes this flag.)You have a repository on gitlab you may use for this assignment on the CSE gitlab (https://gitlab.cs.washington.edu). If you are working with in a team a new repository will be created for which you will share access. You should use your experience with gitlab to access this resource.
The above sections describe what you need to do. This section gives some ideas about how to do it. We discuss 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. As each of these values
requires 8 bytes, we require that all blocks be a multiple of 16 bytes
in size, with all addresses multiples of 16 bytes. This helps ensure that
dynamically allocated blocks are properly aligned.
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.
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, and no block currently on the free list is that large,
it needs to get at least that much in a single request
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, we'll
use 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 aligned on
16-byte or larger boundaries on modern systems, so we won't
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. If implemented cleanly, this will not be an
additional "special case" in the code -- it's just the normal
action taken by getmem when it needs to get new
blocks for the free list!
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 to the storage that the caller can use, but which 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. Our list nodes are set up to hold this size.
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 (i.e., from
malloc) 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.
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.
Here are a few ideas that you might find useful. Feel free to use or ignore them as you wish, although you do need to use the 64-bit pointer types correctly.
Your code should work on, and we will evaluate it on, the CSE
Linux systems (cancun 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, might 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 that 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 when 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 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 a different value for each execution
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.
(This has been a problem in the past when people developed the code using other
systems only to have their entire project fail to compile because
they were using a timing function or header that was not portable and not found on
the CSE machines.)
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 toss"
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:
bench first and then tackling getmem and
freemem has been a good strategy. You can use stub versions
of the memory manager functions to get bench working, and then
it is available to help test the memory manager routines as you work on them.
You should definitely consider doing this.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
when you are first testing the memory manager routines.print_heap function can be very helpful during
debugging. Get it working early. Also, gdb can be
very useful for exploring the free list (expecially gdb's
x command) and for 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, especially 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 will probably report many spurious problems
that are not really errors given what the code needs to do.cpplint.py is provided. You should use this version early to check your code for styles issues.For this assignment, you will turn in the code via Gradescope as usual. You should be able to submit it directly from Gitlab (but this is untested functionality!). If you are working as a team we will double check your gitlab commits to ensure that each team member is active.
You should submit Readme, Makefile, bench.c, getmem.c, and freemem.c. If you modified any of mem.h, mem_impl.h, mem_utils.c you should additionally submit those files. For testing we will use your Makefile to compile and run the code. We will also use our source files to test different functions independently, so you should retain the interface specifications laid out in the sample code and assignment.