CS 251: Programming Languages

Spring 2018

proj2: Talloc

Due: Wednesday, 05/02 at 22:00

1. Goals

To create a garbage collector to manage memory usage throughout the interpreter project.

2. Introduction

In the last assignment, you built a linked list, and wrote code that hopefully cleaned up the list appropriately. Perhaps you have been missing the convenience of using a language with a garbage collection system that spares you from having to remember to clean individual things up. For this assignment, we're going to build an exceedingly dumb but effective garbage collector. This garbage collector is so inefficient that this may bother some of you; if so, consider improving the garbage collector to be a possible extension in the final phase of the project.

3. Tasks

  1. You'll be creating your own replacement for malloc, which we'll call talloc (short for "tracked malloc"). For a user, talloc seems to work just like malloc, in that it allocates memory and returns a pointer to it. Inside your code for talloc, you'll need to call malloc to do exactly that. Additionally, talloc should store the pointer to that memory in a linked list that we'll call the active list for purposes of discussion. Every time talloc is called, another pointer to memory gets added to that active list.
  2. You'll then also create a companion function called tfree, which will free up all memory associated with pointers accumulated due to calls to talloc (i.e., pointers in the active list). Calling tfree at arbitrary points in your program would be a complete disaster, as it would free up memory that you may still be using. The idea is that we will be using talloc as a replacement for malloc, and then calling tfree at the very end of our main function to clean up everything. You'll then be able to program with the illusion of using a garbage collector, except that the garbage collector never actually kicks in until the program is about to end.
  3. You'll also write the function texit, which is a simple replacement for the built-in function exit, i.e., texit calls exit, but calls tfree first.
  4. Finally, you'll then modify your linked list from the previous assignment. The function cleanup that you wrote will be eliminated, as it is no longer necessary. You should also modify reverse so that it no longer duplicates data between the two linked lists. When you reverse a list, that should return a new list with a new set of CONS_TYPE Value nodes, but the actual data in that list should not be copied from the old list to the new. This would be a disaster to try to clean up manually, but tfree will handle it easily. This change will make some later aspects of the project much easier. Your linked list code should now exclusively use talloc, and should not use malloc at all.

4. Storing the active list

One issue you'll need to think through is where the variable for the head of the active list should be. In an object-oriented language, this would likely be a private static variable in a memory management class. Oops. You can't make the active list head a local variable in talloc, because tfree wouldn't be able to see it. We could make it a parameter to talloc and tfree, but then the programmer using talloc has to keep track of this, and could conceivably have multiple active lists, which isn't the idea. This is one of these rare occasions where a global variable makes sense, and so you should use one. A global variable in C is declared outside of any functions. Typically, it is placed near the top of your file, underneath the include statements. You should make your global variable static. This generally makes it inaccessible from another file. It has less to do with "static" memory and is more like Java's "private" keyword. (Try removing the static keyword from global.c and/or the extern keyword from extern.c and compiling the two files together to see what happens.)

There's one bit of circular logic you've got to untangle. talloc needs to store a pointer (returned by malloc) onto a linked list. Your linked list code, in turn, uses talloc. Rather than trying to get this to work in some complex mutually dependent structure, break the circularity. In your talloc code, the active list should be a linked list generated via malloc, instead of talloc. That means you'll need to duplicate some of your linked list code. Duplicated code is generally to be avoided, but avoiding this circular nightmare is worth it.

5. Instructions

  1. Download and add the contents of the starter archive to the same Git repository you used for the previous assignment.
  2. The files you get include:
    • talloc.h: prototypes all of the functions that you will need to write from scratch.
    • linkedlist.h: modified from the previous assignment with the removal of cleanup and a change in the documentation of reverse to indicate that data is not to be copied.
    • talloc_test.c: a tester, like linkedlist_test.c from the previous assignment.
    • value.h, Makefile: lightly modified from the previous assignment.
    The missing file here is talloc.c, which you'll need to create yourself in order to implement everything listed in talloc.h.

    As before, you should create stubs and get everything to build by issuing 

    make
    at the command line. Then, following an incremental development plan and testing as you go, implement all the talloc functions.
  3. Finally, modify linkedlist.c to use talloc and also make the other changes as described.

6. Notes

7. Submission

Follow the instructions from the previous assignment. That is:

This assignment was originally created by David Liben-Nowell and has since been updated by Dave Musicant, Laura Effinger-Dean, and Jed Yang.

Start early, have fun, and discuss questions on Moodle.