Your section leaders will attempt to demo a implementation of a working Mini Valgrind. Please do also make an effort to read over the code that is provided for you.
- Review of memory management and linked lists
- Preparation for the Malloc MP
For this lab, you will be implementing a small version of Valgrind. Valgrind is a great tool which monitors your memory usage which you have likely used already. Your version will print out a summary of the memory leaks in a particular C program This lab is meant in part as preparation for your Malloc MP, introducing some topics and techniques which you will find helpful when approaching Malloc soon.
The main concept of this lab is using some extra memory for each allocation (which we will call metadata) to track each block of allocated memory. We have provided you with a struct
mini_valgrind.h. The metadata is set up as a node of a linked list (remember 125 and 225?) which should store information for each allocated block of the requested size. This includes the memory address of the actual block, line number it was allocated at, the size, filename, and a pointer to the next allocated block.
If you do feel that you need a refresher on linked lists or other prerequisite concepts, feel free to ask a CA/TA one-on-one.
mini_valgrind.c and .h
There are five functions in total you must be writing.
Here you are to write a wrapper function for malloc that will not only allocating the required space but also allocate and set up metadata to track each requested block allocated by the standard
malloc. A call to
insert_meta_data should be made to insert into the linked list of allocated blocks. NOTE: you do not have to write your own implementation of
sbrk or related system calls. You will call the standard
malloc, simply allocating more space than normally due to the metadata. Return null if
malloc fails, otherwise return the pointer to the allocated block of memory NOT the metadata.
Take a look at the
#define statements in
mini_valgrind.h to understand how this is being used. Note the two macros
Here you are passed a pointer to your metadata, the size of the block without metadata, the filename, and the line number from which the allocation was made in the .c file being run. You should ensure your metadata is set up here, and insert into the linked list at the head in constant time. You should be adding new nodes to the head of your linked list defined in the
mini_valgrind.h file. Ensure that you update the
total_usage here and deal with insertion into a linked list just as you have in 125/225.
Here you are passed a pointer to a block of previously allocated memory. To implement this function, use
remove_meta_data properly, and also consider what happens when you free a
Take a look at the
#define statements in
mini_valgrind.h to understand how this is being used.
Remove your metadata passed in as a parameter from the linked list here. Ensure that you update
bad_frees (depending on whether the block pointed to was previously allocated, not already freed, etc.) here and deal with removal from a linked list just as you have in 125/225, keeping in mind the different cases that might come about (such as removal of the head node, etc.). You should free the metadata and requested block.
Here you must delete all nodes of the linked list that have been created. Ensure that you DO NOT add to
total_free here. This is called when the program has finished executing and so any blocks that have not been deallocated should be counted as memory leaks.
You will be given a reference executable as usual for this lab. As usual, please direct as many “What should my code do in case X” questions as you can to the reference implementation first, but do feel free to ask us after checking. NOTE: You must run make each time you would like to test with the reference when you change
If you would like to check your program, you may write tests within
test.c. We recommend checking your program on a variety of inputs.
Helpful Hints and Notes
- DO NOT EDIT print_report! You risk failing the autograder if you do! No one wants that!
- A review of pointer arithmetic might be useful here.
char file_name[MAX_FILENAME_LENGTH]; within the struct in
mini_valgrind.h. Ensure that you write the filename over properly as the length of
file_nameis bounded by