Due Dates

This assignment is due in 3 (three) parts:

Objectives

This assignment continues our exploration of procedural programming, memory management, and software tools, as well as software development and working in teams. In particular, in this assignment you will:

Assignment

This portion of the page is divided into subsections for your convenience:

Synopsis

In this assignment you (together with your teammate(s)) will develop and benchmark a memory management package. Your team will turn in a single assignment, and all members will receive the same grade on the project.

Please start now. Even though you are working with a team, 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 (Part 2) fairly early in the project.

Technical Requirements (the "What")

The project consists of two main technical pieces: a memory management package, and a benchmark and testing program to exercise it and report statistics. The members of your team will be in charge of different parts of the assignment (suggestions for dividing the work are given below). Ultimately, however, all of you are responsible for, and should understand and be able to explain, all of the code (hint, concepts may show up on the final).

Memory Management Package

The memory management package should include a header file mem.h and C implementation files that specify and implement the following four functions:

  1. 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 a 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 about pointers and ints below.

  2. 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 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).

    One additional implementation requirement: When 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.

  3. 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: See the discussion below outlining the implementation of the memory manager for more details about these quantities.

  4. 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.

Benchmark and Testing Program

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.

Usage
bench [ntrials [pctget [pctlarge [small_limit [large_limit [random_seed ]]]]]]

Parameters

(Hint: 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.)

Behavior

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:

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.

Additional Requirements

Besides the Technical Requirements above, you should meet the following additional requirements for this assignment:

Working with a Team

You are required to work with a team of 2-3 persons on this project.

Your team should turn in a single assignment, and all members will receive the same grade on the project. Be sure to have all 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 all parts, please). Also remember that if you wish to use a late day or two for the final part of the project, all members must have those late days available.

You must work with your teammate(s) on this assignment; you cannot work alone. Part of the purpose of the assignment is for you to gain experience handling source code when more than one person is working on a project.

Dividing the Work

In a production implementation there would likely be a single .c file containing all of the Memory Management Package functions described above. One person would be responsible for the implementation of that file, while another person would test it. But for this class, we want to divide the work so that you and your teammate(s) work on the details and use a svn repository to manage the shared files. Because of that, you should split your Memory Management Package code into the following half-dozen files:

One person in your team should be the primary implementor in charge of getmem.c; another person is in charge of freemem.c. Similarly, you should divide responsibility for get_mem_stats.c, print_heap.c, the source files for the Benchmark and Testing Program, and Makefile. You should share responsibility for the header files as needed. Each of you is responsible for testing code produced by your teammate(s).

SVN Repository Notes

You and your teammate(s) will be given a newly created Subversion (SVN) 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_14wi_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_14wi_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_14wi_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.

Implementation Hints (the "How")

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.

Developing and Testing

As with all projects, you should start (very) small and incrementally build up the final project. Here are some ideas:

64-bit Pointers and ints

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 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.

Memory Management Package

The Technical Requirements 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 online class discussion board 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.

Benchmark and Testing 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.

Extra Credit

Here are a couple of things you could add to your memory manager once it's working.

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.

Assessment

Your solutions should:

Identifying information including:

should appear as comments at the top of each of your files.

Turn-in Instructions

You are responsible for making sure all the correct files get turned in to the Dropbox. You can download what you have submitted to verify that all files are present, the contents are what you intended, and they are not corrupted.

To help organize the project, and to stay on schedule, you should turn in this assignment in three phases:

Part 1 (1%): Email to instructor about teammate(s)

Due

Form a 2-3 person team. Now!

As soon as possible, but no later than you must pick your teammate(s) and notify us. One of you (only!) should send a note to the instructor (campbell[at]cs). The email subject must be exactly 374 team, and please CC your teammate(s) so that a reply-all will reach all of you. The email body must contain

We will use this information to assign your team to a Unix group and set up an svn repository you can use for this assignment.

Your team 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, correct contents (names and uwnetids) ).

Part 2 (14%): Header files and repository

Due

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 3 (85%): Final code

Due

(85%) 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.