COS 371: Programming Languages
Spring 2022
proj2: Talloc
Due: Wednesday, 03/30 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
- 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.
- 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. - 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.
- 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
- Download and add the contents of the starter archive to the same Git repository you used for the previous assignment.
As before, simply place files in the root of your repository, not in a
proj2
subdirectory. Yes, some new files will overwrite old ones. Fear not. You can typegit diff
to ask Git to report what changed. - 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 ofcleanup
and a change in the documentation ofreverse
to indicate that data is not to be copied.talloc_test.c
: a tester, likelinkedlist_test.c
from the previous assignment.value.h
,Makefile
: lightly modified from the previous assignment.
talloc.c
, which you'll need to create yourself in order to implement everything listed intalloc.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 thetalloc
functions. - Finally, modify
linkedlist.c
to usetalloc
and also make the other changes as described.
6. Notes
-
As described above, you will likely want to copy in a lot of your
linkedlist.c
code totalloc.c
. You likely need to change the names of the functions slightly to avoid confusing Clang. -
Your code should have no memory leaks or memory errors when run on any input (correct or incorrect) using Valgrind.
We will be checking this during grading.
Look back to the notes from the previous assignment if you forgot how to use Valgrind (hint:
make memtest
at the command line). -
As before, when we grade, we will use the distributed header files (so don't change those) and the distributed
talloc_test.c
and a fanciertalloc_test.c
. You may changetalloc_test.c
andMakefile
to facilitate your testing.
7. Submission
Follow the instructions from the previous assignment. That is:- Append (without deleting previous content) to your
credits.txt
file by writing "proj2" and either declaring "We didn't get any help" or listing anyone who helped you with the assignment (including lab assistants and classmates), and any websites, books or other sources you used for reference. Also briefly describe how you were helped. Please be thorough. - Add, commit, and push regularly.
- When you are done, double check to make sure you have committed the version you want graded;
tag and push the tag:
git tag proj2 git push --tags
(Recall that a normalgit push
does not push tags. Be sure to check on GitHub to make sure that it received your final submission.)
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.