Memory management: talloc

You'll be creating your own replacement for malloc, which we'll call talloc (for "track 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 function called tfree, which will free up all memory associated with pointers accumulated do to calls to talloc. 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. 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. (This is actually an option for the leJOS system for programming LEGO Mindstorms in Java; ask me in class as to why a real system would implement such a crazy-seeming idea.)

You'll also write the function texit, which is a simple replacement for the built-in function exit. 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.

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 sounds ugly. This is an occasion where 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.

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 make this work in some complex mutually dependent structure, my recommendation is to break the circularity. In your talloc code, the single linked list that you use to store allocated pointers 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.

After you clone your repository, you should be able to see that you get the following starting files:

• value.h: this defines the Value structure again
• linkedlist.h: this is a modification form the previous assignment that removes the function cleanup, and also changes the documentation on reverse to indicate that data is not to be copied.
• talloc.h: this defines the functions that you'll need to write from scratch for this assignment.
• main.c: this is a tester function.
• Makefile: contains instructions for the command make, which will compile and test your code

The missing files here are linkedlist.c and talloc.c. You should create talloc.c from scratch yourself. For linkedlist.c, you should copy in code from your previous assignment, and then modify it accordingly. To compile your code, issue the command make at the command prompt. This will follow the instructions in the Makefile for building your project in order to produce an executable called linkedlist. At first, it won't build at all because your talloc.c and linkedlist.c files aren't there. To get started, copy in linkedlist.c (remove the cleanup function), and for now, within talloc.c just create every function that you need with no code inside it so that you can get everything to build. Once you have done that, you can begin implementing your functions, and testing appropriately.

The tester code creates an executable that you can run by typing ./talloc. However, if you find it more convenient, you can type make test which will compile your code and run the tests all in one shot.

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. To run your code through valgrind, I have added to the Makefile a section to do this. You can compile your code and run the tests through valgrind by typing make valgrind at the terminal prompt.

Work in this section is 100% optional, and not worth any points. Nonetheless, if you're looking for an extra challenge, these are fun additional exercises to try.

Write a function that that can report a count, in bytes, of how much memory is being used in total by this talloc technique. It should include both all of the memory that the user asked for when calling talloc, but also all of the additional overhead in Value structs that talloc creates for assembling a linked list. Here is a signature for that function. You can add it to your talloc.h file:

int tallocMemoryCount();

Add all of your files into your Git repository and push to GitHub. Your submitted files should be exactly what you checked out, but also with files named linkedlist.c and talloc.c. (You can leave out your compiled executables as well as the .o object files if you wish.)

The graders and I need to know which commit is the one that we should use for grading. This is handled well in Git with tags. You did this back in the original clab. If you've forgotten how to tag in Git, look at the end of part 1 of the C lab. Name your tag talloc-done.

Good luck, and have fun!