Fall 2013
Program 6
Due Sunday November 17

Garbage Collector for C

Program Specifications

Write a small library that is able to provide chunks of memory from the heap on demand, just as the standard library function malloc does. The library should be able to have the programmer explicitly release memory, just as the standard library function free does. Your library should also be able to inspect the stack and its own section of the heap to do automatic garbage collection.

Note that the garbage collector will not be able to handle global variables.

Source Files

The functions your garbage collector will need to implement are in the header file gc_lib.h. All of the functionality in that file should be implemented in a file called gc_lib.c. All functions introduced in that file that are not a part of the header file should be marked static, as should any global variables.

Any source that includes gc_lib.h and includes gc_lib.c in the build should compile and work. For example:

gcc test.c gc_lib.c -o simple -std=gnu99
should produce an executable, if test.c is as follows:
#include "gc_lib.h"
int main(int argc, char** argv){
    register void* base asm("ebp");
    gc_init(100, base, false);
    void* x = gc_malloc(4);
    *((int*) x) = 0;
    int to_return = *((int*) x);

    return to_return;
Note that you will need to use -std=gnu99 instead of the usual -std=c99 in order to use the asm("ebp") call.

First Fit Policy

One important aspect of how a memory allocation system works is how it decides to divide up the memory when given a request. While a first-fit policy is clearly not optimal, figuring out an intelligent memory allocation policy is well beyond the scope of this assignment.

You are to follow a first-fit policy, meaning you are to assign pieces of memory to the first location you find that will fit, even if there is a piece of memory that may be a better fit elsewhere.

The reason for this is to enable more precise testing of how your program works. If you use the first-fit policy, I will know exactly where to expect a hole, and what the heap should look like at all times.

Error Handling

The header file contains information about how to handle the situation where someone tries to make a heap that is enormously large, or request an amount of memory that is larger than the largest contiguous chunk of memory available.

It is possible that the gc_free function will be handed a completely invalid pointer. If this happens, I expect your program to handle it the way the free in stdlib.h does: by printing an error and exiting. I expect you to allow gc_free(NULL) to do nothing, just like free does.


For this program, you must achieve the different point levels strictly in order, with the exception of the last item about posting a testing main on piazza. In addition, remember, you may lose points if your program is not properly structured or adequately documented. Coding guidelines are given on the course overview webpage.

In addition to that, it is important that your program not print anything out to either standard out or standard error unless specifically called for in the specifications. Programs that have extra or otherwise incorrect output will lose points.

Your programs will be graded using agate.cs.unh.edu so be sure to test in that environment.

Remember: as always you are expected to do your own work on this assignment. Copying code from another student or from sites on the internet is explicitly forbidden!


Your programs should be submitted for grading from agate.cs.unh.edu. In order to turn in the program, first make sure you are SSH'd in to agate. To turn in this program, type:
% ~cs520/bin/DoSubmission.py prog6 gc_lib.c

This submission script is new. It passed what testing I have done on it, but it may still have issues. If there are any problems, please contact me via email and I will do my best to assist you. If I cannot be reached, please send me a copy of your assignment via email, and we will deal with the submission script later.

Due Date

This assignment is due Sunday November 17. The standard late policy concerning late submissions will be in effect.

Last modified: Sun Nov 3 08:00:00 EDT 2013