CS520
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

#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);

    gc_shutdown();
    return to_return;
}

• gc_lib.h: a header file containing stubs used by the garbage collector. The comments in the header file specify what the function is expected to do.

First Fit Policy

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

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.

Grading

• 20 points will be awarded for creating gc system that can allocate memory.
• 5 points will be awarded for also making the gc system capable of freeing memory manually.
• 25 points will be awarded for also making the gc system capable of coalescing free memory.
• 30 points will be awarded for creating a gc system that can identify the roots. This will be evaluated by using the gc system and calling the "print_roots" function.
• 15 points will be awarded for creating a gc system that can collect garbage.
• 5 points will be awarded for creating a testing main and posting that testing main on the piazza thread. Note that it is highly important that the post NOT be anonymous, so I can give you credit for doing this. It is also important that the post be in the correct thread, so I will find it when I go to see who made what testing main. See the thread on piazza for more precise instructions regarding this, and how points will be awarded.

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!

Submission

% ~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