Mini Valgrind Edit on Github

Learning Objectives

The learning objectives for Mini Valgrind are:

  • Using Metadata to Bookkeep segments of memory
  • Memory Management and Linked Lists
  • Prepartion for the Malloc MP
  • malloc(), free(), realloc()
  • Learning what Valgrind Does

Suggested Readings

Overview

For this lab, you will be implementing a small version of Valgrind. Valgrind is a great tool for monitoring 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 there.

Main Concepts

The main concept of this lab is using some extra memory for each allocation (called metadata) to track each block of allocated memory. We have provided you with a struct _meta_data in 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.

Here’s a simple illustration:

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 six functions in total you must be writing.

mini_malloc

Here you are to write a wrapper function for malloc that will not only allocate 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 malloc using 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 that the two macros __FILE__ and __LINE__ are standard predefined macros which are available with all compilers. A macro is just a fragment of code replaced by the contents of the macro when it is called, so __FILE__ will expand to the name of the current input file and __LINE__ will expand to current input line number when they are called in a program. If you want to learn more about macros and how they work, here are two useful links:

mini_realloc

Now you are to implement realloc, which resizes memory. The basic logic for realloc is if the pointer is not NULL, then you will need to either grow or shrink the block of memory it points to. If the size increases, you should increase total_usage; if it decreases, you should increase total_free. If the given pointer is NULL, then realloc is the same as malloc.

insert_meta_data

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.

mini_free

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 NULL pointer.

Take a look at the #define statements in mini_valgrind.h to understand how this is being used.

remove_meta_data

Remove your metadata passed in as a parameter from the linked list here. Ensure that you update total_free or 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.

destroy

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.

Testing

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.
  • Notice 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_name is bounded by MAX_FILENAME_LENGTH.

Reference Executable

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 that you must run make each time you would like to test with the reference after you change test.c.

Submission Instructions

Please fully read details on Academic Integrity . These are shared between all MPs in CS 241.

We will be using Subversion as our hand-in system this semester. Our grading system will checkout your most recent (pre-deadline) commit for grading. Therefore, to hand in your code, all you have to do is commit it to your Subversion repository.

To check out the provided code for mini_valgrind from the class repository, go to your cs241 directory (the one you checked out for "know your tools") and run:

svn up

If you run ls you will now see a mini_valgrind folder, where you can find this assignment! To commit your changes (send them to us) type:

svn ci -m "mini_valgrind submission"

Your repository directory can be viewed from a web browser from the following URL: https://subversion.ews.illinois.edu/svn/fa16-cs241/NETID/mini_valgrind where NETID is your University NetID. It is important to check that the files you expect to be graded are present and up to date in your SVN copy.