Princeton University
COS 217: Introduction to Programming Systems

Purpose

Background

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 by many C programs.

Section 8.7 of the book The C Programming Environment (Kernighan and Ritchie) shows an implementation of the malloc() and free() functions. The key data structure 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 a baseline 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.

Your Task

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:

• heapmgrlinux.c: an implementation that simply calls the standard malloc() and free() functions.
• heapmgrkr.c: the Kernighan and Ritchie implementation.
• heapmgrbase.c: 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:

• heapmgr1.c should enhance heapmgrbase.c so the HeapMgr_free() function is more efficient. To do that, it should use a single doubly-linked list, and chunks that contain headers and footers (as described above, in lectures, and in precepts).
• heapmgr2.c should enhance heapmgrbase.c so the HeapMgr_malloc() function is more efficient. To do that, it should use multiple doubly-linked lists, alias "bins" (as described above, in lectures, and in precepts).

Your HeapMgr implementations should:

• Use "design by contract," that is, thoroughly validate all parameters by calling the standard assert() macro.
• Check the consistency of the HeapMgr implementation thoroughly by calling assert(HeapMgr_isValid()) at both the leading and trailing edges of the HeapMgr_malloc() and HeapMgr_free() functions.
• Not call the standard malloc(), free(), calloc(), or realloc() functions.

Logistics

You may work with one partner on this assignment. You need not work with a partner, but we prefer that you do. If you work with a partner, then only one of the partners should submit work.  The readme file should contain your name and your partner's name.

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:

• heapmgr.h, heapmgrlinux.c, heapmgrkr.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 may use in both implementations of your HeapMgr module.
• testheapmgr.c: a client program that tests the HeapMgr module, and reports timing statistics.
• grade4: a bash shell script that automates testing. The script assumes the existence of executable files named testheapmgrlinux, testheapmgrkr, testheapmgrbaseline, testheapmgr1, and testheapmgr2 (as described below).

The testheapmgr program requires two command-line arguments:

• The number of calls of HeapMgr_malloc() and HeapMgr_free() that the program should execute, and
• The maximum size, in bytes, of each memory chunk that the program should allocate and free.

The testheapmgr program calls HeapMgr_malloc() and HeapMgr_free() repeatedly, in random order, with random size chunks. Immediately before termination it prints to stdout an indication of how much CPU time it consumed..

To test your HeapMgr implementations, you should build two programs using "ordinary" gcc commands:

gcc -Wall -ansi -pedantic -o testheapmgr1 testheapmgr.c heapmgr1.c chunk.c
gcc -Wall -ansi -pedantic -o testheapmgr2 testheapmgr.c heapmgr2.c chunk.c

To collect timing statistics, you should build five programs using gcc commands with two extra command-line arguments:

gcc -O3 -DNDEBUG -Wall -ansi -pedantic -o testheapmgrlinux testheapmgr.c heapmgrlinux.c
gcc -O3 -DNDEBUG -Wall -ansi -pedantic -o testheapmgrkr testheapmgr.c heapmgrkr.c
gcc -O3 -DNDEBUG -Wall -ansi -pedantic -o testheapmgrbase testheapmgr.c heapmgrbase.c chunkbase.c
gcc -O3 -DNDEBUG -Wall -ansi -pedantic -o testheapmgr1 testheapmgr.c heapmgr1.c chunk.c
gcc -O3 -DNDEBUG -Wall -ansi -pedantic -o testheapmgr2 testheapmgr.c heapmgr2.c chunk.c

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

Your makefile should:

• Maintain object (.o) files to allow for partial builds.
• Encode the dependencies among the files that comprise your program.
• Build using the -O3 and -DNDEBUG options.

Create a "readme" text file that contains:

• Your name.
• A description of whatever help (if any) you received from others while doing the assignment, and the names of any individuals with whom you collaborated, as prescribed by the course "Policies" web page.
• The CPU times consumed by testheapmgr using heapmgrlinux.c, heapmgrkr.c, heapmgrbase.c, heapmgr1.c, and heapmgr2.c with these combinations of call counts and chunk sizes: 100000 and 1000, 100000 and 10000, and 1000000 and 1000. If the time consumed is more than 5 minutes, you may abort execution and report "Greater than 5 minutes."
• (Optionally) An indication of how much time you spent doing the assignment.
• (Optionally) Your assessment of the assignment.
• (Optionally) Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.

Submit your work electronically on hats via the command:

/u/cos217/bin/i686/submit 4 heapmgr1.c heapmgr2.c readme makefile

Grading