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 only one of the partners must submit files. Your readme file and your source code files must contain both your name and your partner's name.
"Checking invariants," that is, composing the checker1.c and checker2.c files 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 run-time 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 available through Blackboard in the Course Materials section. 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 is provided in lectures and precepts.
You are given the interface of a HeapMgr (heap manager) module. It declares two functions:
void *HeapMgr_malloc(size_t uSize); void HeapMgr_free(void *pv);
You also are given two implementations of the HeapMgr module. The GNU implementation simply calls the GNU malloc and free functions provided with our FC010 development environment. The second given implementation, the baseline implementation, is a variant of the Kernighan & Ritchie implementation. You will find it to be useful as a baseline for your implementations.
Your task is to create two additional implementations of the HeapMgr module. Your first implementation must enhance the baseline implementation so the HeapMgr_free function is efficient. To do that it must use a doubly-linked list and chunks that contain headers and footers (as described above, in lectures, and in precepts).
If designed properly, your first implementation's HeapMgr_free function will be efficient in all cases. However, its HeapMgr_malloc function will be subject to poor worst-case behavior. Your second implementation must enhance your first implementation so the worst-case behavior of its HeapMgr_malloc function 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.
Each of your HeapMgr implementations must check invariants by defining a thorough Checker_isValid function, and calling assert(Checker_isValid(...)) at the leading and trailing edges of the HeapMgr_malloc and HeapMgr_free functions.
The FC010 directory /u/cos217/Assignment6 contains files that support the assignment. For reference, we list and briefly describe them here. The following sections of this document describe how to use them.
Makefile: a minimal makefile that automates building of programs using the given code and your code.heapmgr.h: the HeapMgr interface.heapmgrgnu.c: the GNU HeapMgr implementation.heapmgrbase.c: the baseline HeapMgr implementation.checkerbase.h and checkerbase.c: a Checker module used by the baseline HeapMgr implementation.chunkbase.h and chunkbase.c: a Chunk module used by the baseline HeapMgr implementation.chunk.h and chunk.c: a Chunk module used by both of your HeapMgr implementations.checker1.h: the interface of a Checker module used by your first HeapMgr implementation.heapmgr1bad*.o: buggy versions of a first HeapMgr implementation.heapmgr1good.o: a correct first HeapMgr implementation.checker2.h: the interface of a Checker module used by your second HeapMgr implementation.heapmgr2bad*.o: buggy versions of a second HeapMgr implementation.heapmgr2good.o: a correct second HeapMgr implementation.testheapmgr.c: a client module that tests any HeapMgr implementation, and reports timing and memory usage statistics.testheap and testheapimp: bash shell scripts that automate testing.readme: a template readme file.testheapmgr ClientThe testheapmgr.c client requires three command-line arguments. The first must be any one of seven strings, as shown in the following table, indicating which of seven tests the client should run:
| Argument | Test Performed |
LifoFixed |
LIFO with fixed size chunks |
FifoFixed |
FIFO with fixed size chunks |
LifoRandom |
LIFO with random size chunks |
FifoRandom |
FIFO with random size chunks |
RandomFixed |
Random order with fixed size chunks |
RandomRandom |
Random order with random size chunks |
Worst |
Worst 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 client should execute. The third command-line argument is the (maximum) size, in bytes, of each memory chunk that the client should allocate and free.
Immediately before termination testheapmgr.c writes to stdout an indication of how much CPU time and heap memory it consumed. See the testheapmgr.c file for more information.
Develop on FC010, using emacs to create source code and gdb to debug.
Perform these steps:
MakefileStudy the given Makefile. It is not a proper one: it does not maintain .o files to allow for partial builds, but instead builds directly from .c files (or given .o files) to executable binary files. Nevertheless, you will find it helpful. Using it will allow you to avoid much typing.
checker1.cAs noted in the Rules section of this document, this is an "extra challenge" part of the assignment.
Compose your checker1.c implementation. Then issue these commands to build programs with buggy heapmgr1 implementations:
gcc217 -g testheapmgr.c heapmgr1bada.o checker1.c chunk.c -o test1bada gcc217 -g testheapmgr.c heapmgr1badb.o checker1.c chunk.c -o test1badb gcc217 -g testheapmgr.c heapmgr1badc.o checker1.c chunk.c -o test1badc gcc217 -g testheapmgr.c heapmgr1badd.o checker1.c chunk.c -o test1badd gcc217 -g testheapmgr.c heapmgr1bade.o checker1.c chunk.c -o test1bade gcc217 -g testheapmgr.c heapmgr1badf.o checker1.c chunk.c -o test1badf gcc217 -g testheapmgr.c heapmgr1badg.o checker1.c chunk.c -o test1badg
Then run those programs using these commands:
test1bada RandomRandom 1000 1000 test1badb RandomRandom 1000 1000 test1badc RandomRandom 1000 1000 test1badd RandomRandom 1000 1000 test1bade RandomRandom 1000 1000 test1badf RandomRandom 1000 1000 test1badg RandomRandom 1000 1000
If (and only if) each program writes a descriptive error message and aborts via an assert, then your checker1.c implementation is working properly.
It will be challenging to compose a checker1.c implementation that detects the errors in all of the given heapmgr1bad*.o files. But your checker1.c implementation should detect the errors in many of the given heapmgr1bad*.o files before you proceed to the next step.
heapmgr1.cCompose your heapmgr1.c implementation. Then issue this command:
gcc217 -g testheapmgr.c heapmgr1.c checker1.c chunk.c -o test1d
to build a debug version of a testing program. Run the program with various command-line arguments to make sure your heapmgr1.c implementation passes all tests defined in your checker1.c implementation.
Then issue these commands:
gcc217 -D NDEBUG -O testheapmgr.c heapmgr1.c chunk.c -o test1 gcc217 -D NDEBUG -O testheapmgr.c heapmgr1good.o chunk.c -o test1good
The-O(that's uppercase "oh") argument commandsgccto optimize the machine language code that it produces. When given the-Oargument,gccspends more time compiling your code so, subsequently, the computer spends less time executing your code. The-D NDEBUGargument commandsgccto define theNDEBUGmacro, just as if the preprocessor directive#define NDEBUGappeared in the specified.cfile(s). Defining theNDEBUGmacro disables the calls of theassertmacro within theHeapMgrimplementations. Doing so also disables code withintestheapmgr.cthat performs (very time consuming) checks of memory contents.
Those commands build a release version of a testing program using your heapmgr1.c implementation and a release version of a testing program using the given heapmgr1good.o implementation. Run the two programs with various command-line arguments. If your test1 program consumes exactly the same amount of memory as the test1good program does, and the two sometimes consume approximately the same amount of time, then you can be reasonably sure that your heapmgr1.c implementation is correct.
Critique your testheapmgr.c/heapmgr1.c/checker1.c/chunk.c program using splint. 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 heapmgr1.c and checker1.c code using critTer. 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.
checker2.cAs noted in the Rules section of this document, this is an "extra challenge" part of the assignment.
Compose your checker2.c implementation. Then issue these commands to build programs with buggy heapmgr2 implementations:
gcc217 -g testheapmgr.c heapmgr2bada.o checker2.c chunk.c -o test2bada gcc217 -g testheapmgr.c heapmgr2badb.o checker2.c chunk.c -o test2badb gcc217 -g testheapmgr.c heapmgr2badc.o checker2.c chunk.c -o test2badc gcc217 -g testheapmgr.c heapmgr2badd.o checker2.c chunk.c -o test2badd gcc217 -g testheapmgr.c heapmgr2bade.o checker2.c chunk.c -o test2bade gcc217 -g testheapmgr.c heapmgr2badf.o checker2.c chunk.c -o test2badf gcc217 -g testheapmgr.c heapmgr2badg.o checker2.c chunk.c -o test2badg gcc217 -g testheapmgr.c heapmgr2badh.o checker2.c chunk.c -o test2badh
Then run those programs using these commands:
test2bada RandomRandom 1000 1000 test2badb RandomRandom 1000 1000 test2badc RandomRandom 1000 1000 test2badd RandomRandom 1000 1000 test2bade RandomRandom 1000 1000 test2badf RandomRandom 1000 1000 test2badg RandomRandom 1000 1000 test2badh RandomRandom 1000 1000
If (and only if) each program writes a descriptive error message and aborts via an assert, then your checker2.c implementation is working properly.
It will be challenging to compose a checker2.c implementation that detects the errors in all of the given heapmgr2bad*.o files. But your checker2.c implementation should detect the errors in many of the given heapmgr2bad*.o files before you proceed to the next step.
heapmgr2.cCompose your heapmgr2.c implementation. Then issue this command:
gcc217 -g testheapmgr.c heapmgr2.c checker2.c chunk.c -o test2d
to build a debug version of a testing program. Run the program with various command-line arguments to make sure your heapmgr2.c implementation passes all tests defined in your checker2.c implementation.
Then issue these commands:
gcc217 -D NDEBUG -O testheapmgr.c heapmgr2.c chunk.c -o test2 gcc217 -D NDEBUG -O testheapmgr.c heapmgr2good.o chunk.c -o test2good
Those commands build a release version of a testing program using your heapmgr2.c implementation and a release version of a testing program using the given heapmgr2good.o implementation. Run the two programs with various command-line arguments. If your test2 program consumes exactly the same amount of memory as the test2good program does, and the two sometimes consume approximately the same amount of time, then you can be reasonably sure that your heapmgr2.c implementation is correct.
Critique your testheapmgr.c/heapmgr2.c/checker2.c/chunk.c program using splint. 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 heapmgr2.c and checker2.c code using critTer. 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.
Issue these commands to build programs using the GNU and baseline heap manager implementations:
gcc217 -D NDEBUG -O testheapmgr.c heapmgrgnu.c -o testgnu gcc217 -D NDEBUG -O testheapmgr.c heapmgrbase.c chunkbase.c -o testbase
readme FileCreate 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.
In particular, in your readme file record the CPU times and heap memory consumed by the testgnu, test1, test2, and testbase programs with tests RandomRandom and Worst, with call count 100000, and with maximum chunk sizes 2000 and 20000. Note that if the CPU time consumed is more than 5 minutes, testheapmgr will abort execution. To report the time and memory consumption, paste the output of the testheap script into your readme file.
Submit your work electronically on FC010 using these commands:
submit 6 heapmgr1.c checker1.c submit 6 heapmgr2.c checker2.c submit 6 readme
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 code has quality if it behaves as it must. The correct behavior of your code 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. The thoroughness of your Checker_isValid functions will be a prominent part of your grade. Proper function-level modularity in your heapmgr1.c and heapmgr2.c implementations also 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 must 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 two keys to success on this assignment:
Your code must have proper function modularity. The heapmgrbase.c implementation defines functions HeapMgr_malloc, HeapMgr_free, HeapMgr_useChunk, and HeapMgr_getMoreMemory. 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. Consider each important verb in the pseudocode. Some candidates for additional functions probably will be obvious.
Use the given testheapmgr.c client properly. Run the test1 and test1good programs 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. For each run compare the performance — especially the memory consumption — of the two programs. Do the same for test2 and test2good.
This assignment was written by Robert M. Dondero, Jr.