The purpose of this assignment is to help you understand how dynamic memory management works in C. It also will give you more opportunity to use the GNU/Unix programming tools, especially bash, emacs, gcc217, gdb, and make.
You may work with one partner on this assignment. You need not work with a partner, but we prefer that you do. Your preceptor will help you with your partner search, if you so desire.
Your partner must be from your precept. Sorry, no exceptions. So make sure you find a partner as soon as you can. After all, if your precept has an odd number of students, then someone must work alone; don't let that person be you!
If you work with a partner, then exactly one of the partners must submit files. Your readme file, your Makefile, and your source code files must contain both your name and your partner's name.
"Checking invariants" (as described below) is the "extra challenge" part of this assignment. While doing the "extra challenge" part of the assignment, you are bound to observe the course policies regarding assignment conduct as given in the course Policies web page, plus one additional policy: you may not use any "human" sources of information. That is, you may not consult with the course's staff members, the lab teaching assistants, other current students via Piazza, or any other people while working on the "extra challenge" part of an assignment, except for clarification of requirements. However you may consult with your partner, with no limitations.
The "extra challenge" part is worth 15 percent of this assignment. So if you don't do any of the "extra challenge" part and all other parts of your assignment solution are perfect and submitted on time, then your grade for the assignment will be 85 percent.
A standard C programming environment contains four functions that allow management of the runtime heap: malloc, free, calloc, and realloc. Those heap management functions are used heavily in many C programs.
Section 8.7 of the book The C Programming Language (Kernighan and Ritchie) shows an implementation of the malloc and free functions. That book section is on electronic reserve at Princeton's library; you can access it through Princeton's Blackboard system (http://blackboard.princeton.edu) by selecting the COS 217 course and clicking on E-Reserves. The key data structure in that implementation is a circular singly-linked list; each free memory "chunk" is stored in that list. Each memory chunk contains a header which specifies its size and, if free, the address of the next chunk in the list. Although elegant in its simplicity, that implementation can be inefficient.
The web page http://gee.cs.oswego.edu/dl/html/malloc.html (Doug Lea) describes how one can enhance such an implementation so it is more efficient. (Here is a copy of that web page, just in case the original is unavailable.) The key data structure is an array of non-circular doubly-linked lists, that is, an array of "bins." Each bin contains all free chunks of a prescribed size. The use of multiple bins instead of a single linked list allows malloc to be more efficient.
Moreover, each memory chunk contains both a header and a footer. The header contains three fields: the size of the chunk, an indication of whether the chunk is free, and, if free, a pointer to the next free chunk in its bin. The footer contains two fields: the size of the chunk, and, if free, a pointer to the previous free chunk in its bin. That chunk structure allows free to be more efficient.
A more thorough description of the pertinent data structures and algorithms will be provided in lectures and precepts.
You are given the interface of a HeapMgr (heap manager) module in a file named heapmgr.h. It declares two functions:
void *HeapMgr_malloc(size_t uiSize); void HeapMgr_free(void *pv);
You also are given two implementations of the HeapMgr module:
heapmgrgnu.c is an implementation that simply calls the GNU malloc and free functions provided with our nobel development environment.
heapmgrbase.c is an implementation that you will find useful as a baseline for your implementations.
Your task is to create two additional implementations of the HeapMgr module. Your first implementation, heapmgr1.c, must enhance heapmgrbase.c so it is reasonably efficient. To do that it must use a single doubly-linked list and chunks that contains headers and footers (as described above, in lectures, and in precepts).
If designed properly, heapmgr1.c will be reasonably efficient in most cases. However, heapmgr1.c is subject to poor worst-case behavior. Your second implementation, heapmgr2.c, must enhance heapmgr1.c so the worst-case behavior is not poor. To do that it must use multiple doubly-linked lists, alias bins (as described above, in lectures, and in precepts).
Your HeapMgr implementations must not call the standard malloc, free, calloc, or realloc functions.
Your HeapMgr implementations must thoroughly validate function parameters by calling the standard assert macro.
Your HeapMgr implementations must check invariants by:
Defining a thorough HeapMgr_isValid function, and
Calling assert(HeapMgr_isValid()) at the leading and trailing edges of the HeapMgr_malloc and HeapMgr_free functions.
The directory /u/cos217/Assignment6 contains files that you will find useful:
heapmgr.h, heapmgrgnu.c, and heapmgrbase.c: as described above.
chunkbase.h and chunkbase.c: a Chunk module used by heapmgrbase.c.
chunk.h and chunk.c: a Chunk module that you should use in both implementations of your HeapMgr module.
testheapmgr.c: a client program that tests the HeapMgr module, and reports timing and memory usage statistics.
testheap and testheapimp: bash shell scripts that automate testing. The testheap script assumes the existence of executable files named testheapmgrgnu, testheapmgrbase, testheapmgr1, and testheapmgr2 (as described below).
sampletestheapmgr1 and sampletestheapmgr2: executable binary files that were built from the testheapmgr.c client and correct heapmgr1.c and heapmgr2.c implementations using the -O3 and -D NDEBUG options. You can compare the output of those programs with the output of your programs to get a good sense of whether your implementations are correct.
The testheapmgr program requires three command-line arguments. The first can be any one of seven strings, as shown in the following table, indicating which of seven tests the program should run:
Argument Test Performed LifoFixedLIFO with fixed size chunks FifoFixedFIFO with fixed size chunks LifoRandomLIFO with random size chunks FifoRandomFIFO with random size chunks RandomFixedRandom order with fixed size chunks RandomRandomRandom order with random size chunks WorstWorst case order for a heap manager implemented using a single linked list
The second command-line argument is the number of calls of HeapMgr_malloc and HeapMgr_free that the program should execute. The third command-line argument is the (maximum) size, in bytes, of each memory chunk that the program should allocate and free.
Immediately before termination testheapmgr writes to stdout an indication of how much CPU time and heap memory it consumed. See the testheapmgr.c file for more details.
Develop on nobel, using emacs to create source code and gdb to debug. Perform these steps:
Decide upon the checks of invariants that you intend to place in your HeapMgr_isValid function for your heapmgr1.c implementation.
Compose your heapmgr1.c implementation. Make sure you compose your HeapMgr_isValid function before (or at least at the same time as) you compose your HeapMgr_malloc and HeapMgr_free functions. After all, you will need your HeapMgr_isValid function to test the other two. Also make sure that you factor your code well. The given heapmgrbase.c implementation defines two functions besides HeapMgr_isValid, HeapMgr_malloc, and HeapMgr_free; your implementation must define more. A well-factored implementation will be much easier to debug than an ill-factored one.
Test your heapmgr1.c implementation. To do that, build a program using this command:
gcc217 testheapmgr.c heapmgr1.c chunk.c -o testheapmgr1
Run the resulting testheapmgr1 program with various command-line arguments, systematically progressing from simple tests to complex, from small malloc/free chunk counts to large, and from small chunk sizes to large.
Collect timing and memory consumption statistics. To do that, build a program using this command:
gcc217 -O3 -D NDEBUG testheapmgr.c heapmgr1.c chunk.c -o testheapmgr1
The -O3 (that's uppercase "oh", followed by the number "3") argument tells gcc to optimize the machine language code that it produces. When given the -O3 argument, gcc spends more time compiling your code so, subsequently, the computer spends less time executing your code. The -D NDEBUG argument tells gcc to define the NDEBUG macro, just as if the preprocessor directive #define NDEBUG appeared in the specified .c file(s). Defining the NDEBUG macro disables the calls of the assert macro within the HeapMgr implementations. Doing so also disables code within testheapmgr.c that performs (time consuming) checks of memory contents.
Run the testheapmgr1 and sampletestheapmgr1 programs specifying various command-line arguments. You'll discover that the the "CPU time" written by the programs will be inconsistent; that is, the CPU time consumed by any given program (with any given command-line arguments) will vary, sometimes significantly, based upon the current system load. However you'll discover that the "memory consumption" written by the programs will be consistent; that is, the memory consumed by any given program (with any given command-line arguments) will be the same each time you run the program. If the testheapmgr1 program consumes exactly the same amount of memory as the sampletestheapmgr1 program does, and the two programs sometimes consume approximately the same amount of time, then you can be reasonably sure that your heapmgr1.c implementation is correct.
Perform steps 1, 2, 3, and 4 for your heapmgr2.c implementation.
Critique your code using the splint tool. Each time splint generates a warning on your code, you must either (1) edit your code to eliminate the warning, or (2) explain your disagreement with the warning in your readme file.
Similarly, critique your code using the critTer tool. Each time critTer generates a warning on your code, you must either (1) edit your code to eliminate the warning, or (2) explain your disagreement with the warning in your readme file.
Compose a Makefile. The first dependency rule of your Makefile must be:
all: testheapmgrgnu testheapmgrbase testheapmgr1 testheapmgr2
Thereby executing the make command with no command-line arguments must cause make to build four executable binary files:
testheapmgrgnu which uses the testheapmgr client and the GNU implementation.
testheapmgrbase which uses the testheapmgr client and the baseline implementation.
testheapmgr1 which uses the testheapmgr client and your heapmgr1 implementation.
testheapmgr2 which uses the testheapmgr client and your heapmgr2 implementation.
The Makefile that you submit must:
Maintain object (.o) files to allow for partial builds of all four executable binary files.
Encode the dependencies among the files that comprise your program.
Build using the -O3 and -D NDEBUG options.
We recommend that you create your Makefile early in your development process. Doing so will allow you to use and test your Makefile during development.
Compose a readme file by copying the file /u/cos217/Assignment6/readme to your project directory, and editing the copy by replacing each area marked "<Complete this section.>" as appropriate.
One of the sections of the readme file requires you to list the authorized sources of information that you used to complete the assignment. Another section requires you to list the unauthorized sources of information that you used to complete the assignment. Your grader will not grade your submission unless you have completed those sections. To complete the "authorized sources" section of your readme file, copy the list of authorized sources given in the "Policies" web page to that section, and edit it as appropriate.
In your readme file record the CPU times and heap memory consumed by testheapmgr using heapmgrgnu.c, heapmgrbase.c, heapmgr1.c, and heapmgr2.c, with tests RandomRandom and Worst, with call count 100000, and with maximum chunk sizes 1000 and 10000. Note that if the CPU time consumed is more than 5 minutes, testheapmgr will abort execution. To report the time and memory consumption, it is sufficient to paste the output of the testheap script into your readme file.
Submit your work using this command:
submit 6 readme Makefile heapmgr1.c heapmgr2.c
Minimal requirement to receive credit for your heapmgr1.c implementation:
The heapmgr1.c implementation must build with the testheapmgr.c client using chunk.c. The program must build with and without the -D NDEBUG and -O3 options.
Minimal requirement to receive credit for your heapmgr2.c implementation
:
The heapmgr2.c implementation must build with the testheapmgr.c client using chunk.c. The program must build with and without the -D NDEBUG and -O3 options.
We will grade your work on quality from the user's and programmer's points of view. From the user's point of view, your program has quality if it behaves as it must. The correct behavior of your program is defined by the previous sections of this assignment specification.
From the programmer's point of view, your code has quality if it is well styled and thereby easy to maintain. In part, good style is defined by the splint and critTer tools, and by the rules given in The Practice of Programming (Kernighan and Pike) as summarized by the Rules of Programming Style document. The more course-specific style rules listed in the previous assignment specifications also apply. Proper function-level modularity will be a prominent part of your grade. To encourage good coding practices, we will deduct points if gcc217 generates warning messages.
critTer Warnings on Given CodeWhen critTer critiques the testheapmgr.c file, it generates warnings about the use of "magic numbers," the length of some loops, and the length of the file. We judged that using magic numbers, defining deeply nested code, and defining long loops in testheapmgr.c was clearer than the alternative. And splitting testheapmgr.c into multiple files would have complicated the build process unnecessarily. So please ignore those warnings.
Similarly, when critTer critiques the heapmgrbase.c file, it generates a warning which suggests that the HeapMgr_free function validate its pv parameter through an assert. In fact the HeapMgr_free function must not validate its pv parameter through an assert, so please ignore that warning.
There are three keys to success on this assignment:
Your code must have proper function modularity. The heapmgrbase implementation defines functions HeapMgr_malloc, HeapMgr_free, HeapMgr_useChunk, HeapMgr_getMoreMemory, and HeapMgr_isValid. In your heapmgr1.c and heapmgr2.c implementations you must define additional functions that help make your code easier to read and maintain.
We can't suggest the specific additional functions you should define; part of the assignment is that you determine what they should be. We suggest that you study the pseudocode given in precepts. Some candidates for additional functions probably will be obvious.
Your code must check invariants thoroughly. That is, for each implementation you must define a HeapMgr_isValid function. The HeapMgr_isValid function must check the HeapMgr object's data structures, making sure that those aspects of the data structures that must not vary indeed have not varied. You must call the HeapMgr_isValid function at the leading and trailing edges of your HeapMgr_malloc and HeapMgr_free functions.
The heapmgrbase implementation defines several checks of invariants. Your implementations will use more complex data structures, and so must define many more checks of invariants.
It would be a mistake to develop your HeapMgr_isValid function after developing the rest of your code. Instead you should develop your HeapMgr_isValid early in your development process, and use it to help you to debug your code.
Use the given testheapmgr.c client properly. Build a program using the testheapmgr.c client and your heapmgr1.c (or heapmgr2.c) implementation. Then run that program and sampletestheapmgr1 (or sampletestheapmgr2) repeatedly, progressing from simple tests (e.g., LifoFixed) to more complex ones (e.g., RandomRandom), from small numbers of calls of HeapMgr_malloc and HeapMgr_free to large number of calls, and from small (maximum) chunk sizes to large (maximum) chunk sizes. At each stage compare the performance -- especially the memory consumption -- of your implementation vs. the given one.
This assignment was written by Robert M. Dondero, Jr.