Princeton University
COS 217: Introduction to Programming Systems

Assignment 6: A Heap Manager Module


Purpose

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/Linux programming tools, especially bash, emacs, gcc217, gdb, and make.

Students from past semesters reported taking, on average, 14 hours (each) to complete this assignment.


Rules

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!

Accounting for the (ostensibly incredible) performance of the heapmgrgnu.c implemenation is the "extra challenge" part of the assignment. Details are provided later in this document. 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 5 percent of the 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 95 percent.


Background

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.


Your Tasks

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 CourseLab 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 Given Files

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


The testheapmgr Client

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


The Procedure

Develop on CourseLab, using emacs to create source code and gdb to debug. Perform these steps:


Step 0: Create a Project Directory and Study the Given Makefile

The CourseLab /u/cos217/Assignment6 directory contains the given files that are described previously in this document. Create a project directory, and copy all files from the /u/cos217/Assignment6 directory to your project directory.

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


Step 1: Compose checker1.c

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 20000
./test1badb RandomRandom 1000 20000
./test1badc RandomRandom 1000 20000
./test1badd RandomRandom 1000 20000
./test1bade RandomRandom 1000 20000
./test1badf RandomRandom 1000 20000
./test1badg RandomRandom 1000 20000

If (and only if) each program writes a reasonable 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.


Step 2: Compose heapmgr1.c

Compose 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 commands gcc to optimize the machine language code that it produces. When given the -O argument, gcc spends more time compiling your code so, subsequently, the computer spends less time executing your code. The -D NDEBUG argument commands 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 (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.


Step 3: Critique your First Implementation Code

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 checker1.c and heapmgr1.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.

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

Step 4: Compose checker2.c

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 20000
./test2badb RandomRandom 1000 20000
./test2badc RandomRandom 1000 20000
./test2badd RandomRandom 1000 20000
./test2bade RandomRandom 1000 20000
./test2badf RandomRandom 1000 20000
./test2badg RandomRandom 1000 20000
./test2badh RandomRandom 1000 20000

If (and only if) each program writes a reasonable 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.


Step 5: Compose heapmgr2.c

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


Step 6: Critique your Second Implementation Code

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 checker2.c and heapmgr2.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.


Step 7: Build Using the GNU and Baseline Implementations

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

Step 8: Compose a readme File

Edit your copy of the given readme file by answering each question that is expressed therein.

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.

You will notice that in many cases the heapmgrgnu.c implementation consumes substantially less heap memory than the heapmgrbase.c, heapmgr1.c, and heapmgr2.c implementations do. In fact, in many cases the heapmgrgnu.c implementation consumes less heap memory than the total amount of memory that the testheapmgr.c client requests. Sometimes it consumes no heap memory at all! Some examples:

./testgnu LifoFixed 1000 100000
       ./testgnu    LifoFixed    1000 100000   0.00     135168
./testgnu LifoFixed 1000 10000000
       ./testgnu    LifoFixed    1000 1000000   0.00          0

In your readme file, explain how the heapmgrgnu.c implementation can consume so little heap memory.


Step 9: Provide Feedback

Provide the instructors with your feedback on the assignment. To do that, issue this command:

FeedbackCOS217.py 6

and answer the questions that it asks. (When answering the numeric questions, please enter the average of the responses that you and your partner would provide individually.) That command stores its questions and your answers in a file named feedback in your working directory.


Step 10: Submit

Submit your work electronically on CourseLab. If you worked with a partner, then one of the partners must submit all of your team's files, and the other partner must submit none of your team's files. Your readme file and your source code files must contain both your name and your partner's name. Use these commands to submit:

submit 6 checker1.c heapmgr1.c
submit 6 checker2.c heapmgr2.c
submit 6 readme feedback

Program Style

In part, good program 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, as does this one: your heapmgr1.c and heapmgr2.c implementations must have good function-level modularity.


Grading

We will grade your work on two kinds of quality:

The thoroughness of your Checker_isValid functions will be a prominent part of your grade.

To encourage good coding practices, we will deduct points if gcc217 generates warning messages.


Keys to Success

There are three keys to success for this assignment:

(1) Function Modularity

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.

(2) Internal Testing

Your code must check invariants thoroughly. That is, for each implementation you must define a thorough Checker_isValid function. The Checker_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 Checker_isValid function at the leading and trailing edges of your HeapMgr_malloc and HeapMgr_free functions.

The Checker_isValid function for the heapmgrbase implementation defines several checks of invariants. Some of them apply to your implementations; some of them do not. Your implementations must use more complex data structures, so the Checker_isValid functions for your implementations must define more checks of invariants.

It would be a mistake to develop your Checker_isValid functions after developing your heapmgr1.c and heapmgr2.c implementations. That is, it would be a mistake to proceed to Step 2 before doing a thorough job on Step 1, or to proceed to Step 5 before doing a thorough job on Step 4. After all, your Checker_isValid functions will help you to develop your heapmgr1.c and heapmgr2.c implementations.

(3) External Testing

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.