The purpose of this assignment is to help you understand how dynamic memory management works in C. The assignment also will give you the opportunity to gain more experience with the "design by contract" style of modular programming. Finally it will give you more opportunity to use the GNU/UNIX programming tools, especially xemacs, gcc, gdb, and make.
A standard C programming environment contains four functions that allow management of the runtime heap: malloc(), free(), calloc(), and realloc(). The malloc() and free() functions are the most fundamental of the four. 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 by selecting the COS 217 course and clicking on "E-Reserves." Hardcopy will be distributed in precepts.) 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. 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 uiBytes); /* Return a pointer to space for an object of size uiBytes. Return NULL if uiBytes is 0 or the request cannot be satisfied. The space is uninitialized. */ void HeapMgr_free(void *pvBytes); /* Deallocate the space pointed to by pvBytes. Do nothing if pvBytes is NULL. It is an unchecked runtime error for pvBytes to be a a pointer to space that was not previously allocated by HeapMgr_malloc(). */
You also are given three implementations of the HeapMgr module:
Your task is to create two additional implementations of the HeapMgr module. The first should be named heapmgr1.c. heapmgr1.c should enhance heapmgrbase.c so it is reasonably efficient. To do that, it should 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, should enhance heapmgr1.c so the worst-case behavior is not poor. To do that, it should use multiple doubly-linked lists, alias "bins" (as described above, in lectures, and in precepts).
Your HeapMgr implementations should:
You may work with one partner on this assignment. You need not work with a partner, but we strongly prefer that you do. If you work with a partner, then only one of the partners should submit work. The readme file and the source code files should contain your name and your partner's name.
Your partner should be from your precept. However, we can make exceptions to that rule. To request an exception, send an e-mail to all preceptors at cos217@princeton.edu before beginning your work on the assignment.
Develop on hats, using xemacs to create source code and gdb to debug.
The directory /u/cos217/Assignment4 contains files that you will find useful:
The testheapmgr program requires three command-line arguments. The first should be an integer in the range 0 to 6, indicating which of seven tests the program should run:
Argument Test Performed 0 LIFO with fixed size chunks 1 FIFO with fixed size chunks 2 LIFO with random size chunks 3 FIFO with random size chunks 4 Random order with fixed size chunks 5 Random order with random size chunks 6 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 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 prints to stdout an indication of how much CPU time and heap memory it consumed. See the testheapmgr source code for more details.
To test your HeapMgr implementations, you should build two programs using "ordinary" gcc commands:
gcc -Wall -ansi -pedantic testheapmgr.c heapmgr1.c chunk.c -o testheapmgr1 gcc -Wall -ansi -pedantic testheapmgr.c heapmgr2.c chunk.c -o testheapmgr2
To collect timing statistics, you should build five programs using gcc commands with two extra command-line arguments:
gcc -O3 -DNDEBUG -Wall -ansi -pedantic testheapmgr.c heapmgrlinux.c -o testheapmgrlinux gcc -O3 -DNDEBUG -Wall -ansi -pedantic testheapmgr.c heapmgrkr.c -o testheapmgrkr gcc -O3 -DNDEBUG -Wall -ansi -pedantic testheapmgr.c heapmgrbase.c chunkbase.c -o testheapmgrbase gcc -O3 -DNDEBUG -Wall -ansi -pedantic testheapmgr.c heapmgr1.c chunk.c -o testheapmgr1 gcc -O3 -DNDEBUG -Wall -ansi -pedantic testheapmgr.c heapmgr2.c chunk.c -o testheapmgr2
The -O3 (that's uppercase "oh", followed by the number "3") argument commands 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 -DNDEBUG argument commands gcc to define the NDEBUG macro -- just as if the preprocessor directive "#define NDEBUG" appeared in every .c file. Defining the NDEBUG macro disables the (very time consuming) calls of the assert() macro within the HeapMgr implementations. It also disables code within testheapmgr.c that performs (very time consuming) checks of memory contents.
Create additional test programs as you deem necessary. You need not submit your additional test programs.
Create a makefile. The first dependency rule of the makefile should build five executable files: testheapmgrlinux, testheapmgrkr, testheapmgrbase, testheapmgr1, and testheapmgr2. That is, the first dependency rule of your makefile should be:
all: testheapmgrlinux testheapmgrkr testheapmgrbase testheapmgr1 testheapmgr2
The makefile that you submit should:
We strongly recommend that you create your makefile early in your development process. Doing so will allow you to use and test your makefile during development.
Create a "readme" text file that contains:
Submit your work electronically on hats via the command:
submit 4 heapmgr1.c heapmgr2.c readme makefile
We will grade your work on quality from the user's point of view and from the programmer's point of view. From the user's point of view, your module has quality if it behaves as it should. The correct behavior of the HeapMgr module is defined by the previous sections of this assignment specification. From the programmer's point of view, your module has quality if it is well styled and thereby simple to maintain. See the specifications of previous assignments for guidelines concerning style. To encourage good coding practices, we will compile using the "-Wall -ansi -pedantic" options, and penalize for warning messages. Your "checks for invariants" will be a prominent part of your grade.