CSE Homework 6 100 points Solved

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 will turn in a single assignment, and both partners will receive the same grade on the project. Be sure to have both of your names in the assignment files. 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, and both of you will be charged for any late days used.
Part 0: Pick a partner NOW!
As soon as possible, but no later than 11:00 pm on Monday, May 7, you must pick a partner and notify us. One of you (only!) must complete this Google form by writing in the names and uwnetids of both partners. We will create a discussion on the Canvas discussion board for students to find partners whose schedule might be compatible.
You must work in PAIRS. You cannot work alone and you cannot have a group of three or more.
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, random email addresses, or other information).
Part 1: Header files and repository (due 5/15/18, 11pm)
See the turnin section for details about what is required for Part 1. Turnin will be through GitLab. NO LATE SUBMISSIONS.
Part 2: Final code (due 5/24/18, 11pm)
See the turnin section for final turnin instructions through GitLab.
Assignment goals
This assignment continues our exploration of procedural programming, memory management, and software tools, as well as software development and working in groups. In particular, in this assignment you will:
    • Implement and test a memory management package that has the same functionality as the standard library malloc and free functions,
    • Gain experience using source-code management systems, in particular git,
    • Gain further experience with software development tools like make, and
    • Gain experience working in groups.
Please start now. Even though you are working with a partner, there is enough to do that you will be in (big) trouble if you wait until the weekend before it is due to begin. To encourage you to get started now you are required to turn in skeleton files for your code fairly early in the project (details later in this writeup).
Requirements
The project consists of two main technical pieces: a memory management package, and a program to exercise it and report statistics. The members of your group will be in charge of different parts of the assignment, as described below. Ultimately, however, both of you are responsible for, and should understand and be able to explain, all of the code submitted by your group.
Memory Management
The memory management package should include a header file mem.h and C implementation files that specify and implement the following four functions.
Function
Description
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. 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).
An 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.
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.
See the discussion below outlining the implementation of the memory manager for more details about these quantities.
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:
    • Blocks are ordered with strictly increasing memory addresses
    • Block sizes are positive numbers and no smaller than whatever minimum size you are using in your implementation
    • Blocks do not overlap (the start + length of a block is not an address in the middle of a later block on the list)
    • Blocks are not touching (the start + length of a block should not be the same address as the next block on the list since in that case the two blocks should have been combined into a single, larger block.)
If no errors are detected, this function should return silently after performing these tests. If an error is detected, then an 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.
Dividing the Work
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:
File
Description
mem.h
Header file containing declarations of the public functions in the memory manager (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_utils.c
Implementation of function check_heap. This is also a good place to put any other shared code or functions that are used internally by other parts of the implementation but are not intended to be part of the public interface.
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, as well as the declaration of function check_heap.
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 mem_utils.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.
Test and Benchmark
You should implement a program named bench, whose source code is stored in a file bench.c. When this program is run, it should execute a large number of calls to functions getmem and freemem to allocate and free blocks of random sizes and in random order. This program should allow the user to specify parameters that control the test. The command-line parameters, and their default values are given below. Trailing parameters can be omitted, in which case default values should be used. Square brackets [] mean optional, as is the usual convention for 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 CPU time used by the benchmark test so far in seconds (show enough fractional digits to provide useful information if possible, although the granularity of the system clock may be too large for this to be meaningful for short tests).
    • Total amount of storage acquired from the underlying system by the memory manager during the test so far (e.g., the total_size quantity from get_mem_stats, above).
    • Total number of blocks on the free storage list at this point in the test.
    • Average number of bytes in the free storage blocks at this point in the test.
The program should print this 10 times during execution, evenly spaced during the test. In other words, the first report should appear after 10% of the total getmem/freemem calls have executed, then after 20%, 30%, etc., and finally after the entire test has run. You may format this information however you wish, but please keep it brief and understandable - one line for each set of output numbers should be enough.
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.
Additional Requirements
Besides the software specifications above, you must meet the following requirements for this assignment.
    • You and your partner must use a CSE GitLab repository to store all of the code and other files associated with the project. (But don't store things like .o files and executable programs that don't belong in a repository.) You must use the repository that we provide even if you have separate machines or accounts of your own that you use for other projects. Both you and your partner should be regularly committing and pushing changes to your repository and we expect the git log to reflect reasonable activity by both members of the group. Don't obsess about the number of commits/pushes done by each person, however the git log must show commit activity by both partners for both parts of the project.
    • You should create a 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.
You may add any additional targets that you wish for your convenience. There are some ideas for useful targets in the Implementation Suggestions section, below.
    • You should create a README file at the top level of your repository. This file should give a brief summary of:
        ◦ Both of your names, and your group identifier (2 letters).
        ◦ Who was responsible for which part of the project, and how the work was divided.
        ◦ A brief description of how your heap (free list) data structure is organized and the algorithms used to manage it.
        ◦ A summary of any additional features or improvements in your memory manager or benchmark code. If you did any extra credit parts of the assignment, be sure to describe that. If you experimented with various quantities such as the minimum size of a block fragment to keep on the free list, describe your experiments and results obtained.
        ◦ A summary of the results you observed on several runs of your bench program. This does not need to be exhaustive (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.
        ◦ A summary of any resources you consulted for information about memory management algorithms. Your code, of course, must be your own, but feel free to research and explore memory management topics.
    • Finally, your code should be of the usual high quality, with clean layout, good comments, and so forth. In particular, the comments describing the free list data structures should contain a complete but succinct description of this data so that someone can read these definitions and understand them without tracing the code that uses them. Use clint to check for possible style issues that may need correcting.
Repository Notes
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 xy, you should use the following git command:
    git clone git@gitlab.cs.washington.edu:cse374-18sp-students/cse374-18sp-xy.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 promptly. 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.
Memory Management
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. 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, 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.
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.
Implementation Suggestions
Here are a few ideas that you might find useful. Feel free to use or ignore them as you wish, although you do need to use the 64-bit pointer types correctly.
64-bit Pointers and ints
Your code should work on, and we will evaluate it on, the CSE Linux 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, 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 Benchmark Program
The command line can contain several integer parameters. These need to be converted from character strings ("500") to binary int values. There are various library functions that are useful: look at atoi and related ones. Take advantage of the Linux getopt library function if it helps.
The benchmark program relies heavily on random numbers. The standard library function rand can be used to generate sequences of pseudo-random numbers. Given a particular starting number (the seed), rand (or any pseudo-random number generator) will always generate the same sequence of numbers on successive calls. This can be very helpful during testing (i.e., things are basically random, but the sequence is reproducible). If you want to generate a different sequence of numbers each time the program is executed, you can set the seed to some quantity that is different on each run -- the system time-of-day clock is a frequent choice -- and 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.
Developing and Testing
As with all projects, you should start (very) small and incrementally build up the final project. Here are some ideas:
    • In the past, many successful teams have found that implementing 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.
    • You can create initial versions of 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.
    • You can implement getmem first by itself. Just have freemem return without doing anything. Get freemem working later.
    • Use small tests involving very few getmem/freemem requests when you are first testing the memory manager routines.
    • The 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.
    • Write several small test programs whose effect on the heap you can predict by hand, then use the free list printout (above) and/or gdb to check that it really works as you expect.
    • Don't be shy about adding lots of targets to your Makefile to compile and run small test programs, or run the benchmark program with various argument values. If you find yourself typing the same command more than a few times to run a test, add it to your Makefile as the command for a target with a suitable name (e.g., test17, test42, reallybigtest, etc.).
    • The get_mem_stats function may be useful during debugging to see the effect on the free list of various patterns of getmem and freemem requests. Don't feel constrained to use it only to produce the required benchmark program reports.
    • Use 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.
    • Note that 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.
    • Be sure to commit and push code to your Gitlab repository regularly. That ensures that you have backup copies of your files, and also makes it easy (or possible!) to revert to previous versions of the code if needed.
Extra Credit
Here are a couple of things you could add to your memory manager once it's working.
    • (easy) If getmem always starts scanning the free list from the beginning when it is looking for a block of suitable size, it is likely that eventually there will be lots of little fragments of free space at the beginning of the list. We can reduce fragmentation, and speed things up, if each subsequent search starts from where the previous search left off, wrapping around to the front of the free list if the end is reached before finding a suitable block. How does the output of your benchmark program change if you do this?
    • (harder) Modify the free list and memory allocation routines so that blocks can be added to the free list and combined with adjacent blocks in constant time. One way to do this is the following, known as the boundary tag method. In addition to the header information at the beginning of each block containing its size, every block, both allocated and on the free list, should contain an extra few bytes at the end with length information and/or extra pointers and/or "free/allocated" bits. The idea is that when a block is being freed, we can look at the adjacent storage in the heap to find the end and beginning of the previous and next blocks, and from there we can determine whether they are free or allocated and how big they are without having to search the free list.
DO NOT ATTEMPT ANY OF THIS until you have completed the basic assignment and turned it in.
For more information, in addition to Google and Wikipedia, an authoritative discussion is in Sec. 2.5, Dynamic Storage Allocation, in The Art of Computer Programming, Vol. I: Fundamental Algorithms, by Donald Knuth. Doug Lea's web site (http://g.oswego.edu/dl/html/malloc.html) has good information about the allocator that he wrote that was basis of the malloc/free implementations in many C distributions.
What to Turn In
For this assignment, you will "turn in" the project by committing and pushing files to your group's GitLab repository, then pushing a git "tag" to indicate which version of the files in your repository are the ones you wish us to grade for each part. 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 having a complete set of header files and skeleton implementations of everything required for the assignment, including the basic Makefile, 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 or return 0 statement if needed. These files should be complete enough to compile without errors when your repository is copied to a directory on klaatu or the 64-bit CSE Linux VM and a make command is executed there after checking out the proper hw6-part1 git tag (see details below). 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 that has #includes for the necessary headers and contains a skeleton main function (return EXIT_SUCCESS is perfectly fine). All files must contain appropriate comments, particularly heading comments on functions and interfaces, and information in each file to identify your team and the project.
For part 1, the git log will probably have fairly little activity, but it must show at least one commit operation done by each partner in the group. That is to ensure that both people in the group have a proper git setup, and have been able to clone the repository, make changes, and commit and push those change to GitLab.
Part 2: Final code. This contains the complete project, including the README file and everything else requested above. Your files need to be committed and pushed to your repository, and marked with a hw6-final tag. If you do any of the extra credit parts, be sure to commit and push the basic project using the hw6-final tag, then, after you have committed and push the extra credit parts, mark those by pushing a hw6-extra tag to indicate those files.
"Turning In" hw6
As indicated above, submitting this assignment basically means having the final files pushed to your group's GitLab repository. Once you're ready, "turning in" the assignment is simple -- create an appropriate tag in your git repository to designate the git revision (commit) that the course staff should examine for grading. But there are multiple ways to get this wrong, so you should carefully follow the following steps in this order. The idea is:
    1. Tidy up and be sure that everything is properly committed and pushed to your GitLab repository.
    2. Add a tag to your repository to specify the commit that corresponds to the finished assignment, after you have pushed all of your files.
    3. Check out a fresh copy of the repository and verify that everything has been done properly.
1. Tidy up and be sure everything is properly stored in Gitlab. Commit and push all of your changes to your repository (see the course web pages for links to git information if you need a refresher on how to do this). Then in the top-level repository directory (i.e., in cse374-18sp-xy, where xy is your group's code) do this:
            bash% git pull
            bash% make clean
            bash$ git status
            On branch master
            Your branch is up-to-date with 'origin/master'.
            nothing to commit, working directory clean
If you see any messages about uncommitted changes or any other indications that the latest version of your code has not been pushed to the GitLab repository, fix those problems and push any unsaved changes before going on. Then repeat the above steps to verify that all is well.
2. Tag your repository and push the tag information to GitLab to indicate that the current commit is the version of the assignment that you are submitting for grading. For part 1, this would be:
              bash% git tag hw6-part1
              bash% git push --tags 
Do not do this until after you have committed and pushed all parts of your hw6 part 1 solution to GitLab.
You will do the same thing for the second part of the assignment, only using the tag hw6-final instead of hw6-part1.
3. Check your work! Verify that everything is properly stored and tagged in your repository. To be sure that you really have updated and tagged everything properly, create a brand new, empty directory that is nowhere near your regular working directory, clone the repository into the new location, and verify that everything works as expected. It is really, really, REALLY important that this not be nested anywhere inside your regular, working repository directory. Do this:
              bash% cd <somewhere-completely-different>
              bash% git clone git@gitlab.cs.washington.edu:cse374-18sp-students/cse374-18sp-xy.git
              bash% cd cse374-18sp-xy
              bash% git checkout hw6-part1
              bash% ls
              ...  
Use your group's 2-letter code instead of xy, of course. The commands after git clone change to the newly cloned directory, then cause git to switch to the tagged commit you created in step 2, above. We will do the same when we examine your files for grading.
At this point you should see your hw6 part 1 files. Run make, then run any tests that you want. If there are any problems, immediately erase this newly cloned copy of your repository (rm -rf cse374-18sp-xy), go back to the regular repository copy where you've been doing your work, and fix whatever is wrong. It may be as simple as running a missed git push --tags command if the tag was not found in the repository. If it requires more substantive changes, you may need to do a little voodoo to get rid of the original hw6-part1 tag from your repository and re-tag after making, committing, and pushing your repairs. To eliminate the hw6-part1 tag, do this (this should not normally be necessary):
              bash% git tag -d hw6-part1
              bash% git push origin :refs/tags/hw6-part1 
Once you have made your repairs, and only after all the changes are committed and pushed, repeat the tag and tag push commands from step 2. And then repeat this verification step to be sure that the updated version is actually correct.
Once again: if you discover that repairs are needed when you check your work, it is crucial that you delete the newly cloned copy and make the repairs back in your regular working repository. If you modify files in the cloned copy you may wind up pushing changes to GitLab that leave your repository in a strange state, and files may appear to mysteriously vanish. Please follow the instructions precisely.
Follow the same instructions to verify your work after you've finished part 2 of the assignment, but using the tag hw6-final instead of hw6-part1.