Goals
- Practice working with the malloc family of functions and memory management.
Setup
Copy the lab files by creating a git repo for lab12 and then run:
$ git pull ~cs61c/labs/fa13/12 master
Memory Management
The following exercises deal with memory. To help you to find memory bugs, we have installed a copy of Valgrind Memcheck. Valgrind is ONLY on the lab machines in the Hive, Orchard, and 273 Soda labs. This program will run an executable while keeping track of what registers and regions of memory contain allocated and/or initialized values. The program will run much slower (by a factor of about 10 to 50) so that this information can be collected, but Valgrind Memcheck can identify many memory errors automatically at the point at which they are produced. You will need to learn the basics of how to parse the Valgrind output.
You can finish this lab without ever directly calling Valgrind, but for those interested, the Makefile calls Valgrind as follows:
$ valgrind --tool=memcheck --leak-check=full --track-origins=yes [OS SPECIFIC ARGS] ./<executable>
The --track-origins flag attempts to identify the sources of unitialized values. The --leak-check=full option tries to identify memory leaks. [OS SPECIFIC ARGS] are simply a set of arguments to Valgrind that differ across operating systems (in our case, Ubuntu (Linux) and OS X (Darwin)). If you are interested in learning more about these, see the Makefile.
The last line in the Valgrind output is the line that will indicate at a glance if things have gone wrong. Here's a sample output from a buggy program:
==47132== ERROR SUMMARY: 1200039 errors from 24 contexts (suppressed: 18 from 18)
If your program has errors, you can scroll up in the command line output to view details for each one. For our purposes, you can safely ignore all output that refers to suppressed errors. In a leak-free program, your output will look like this:
==44144== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 18 from 18)
Again, any number of suppressed errors is fine; they do not affect us.
IMPORTANT: Valgrind will NOT run on the Solaris servers (e.g. star, cory, nova)! You MUST work on either the Hive machines, Orchard machines, or 273 Soda machines.
Exercise 1: variable-length array (vector)
This exercise uses vector.h, vector-test.c, and vector.c, where we provide you with a framework for implementing a variable-length array. This exercise is designed to help familiarize you with C structs and memory management in C.
Your task is to fill in the functions vector_delete() and vector_set() in vector.c so that our test code vector-test.c runs without any memory management errors. Comments in the code describe how the functions should work. Look at the functions we've filled in to see how the data structures should be used. For consistency, it is assumed that all entries in the vector are 0 unless set by the user. Keep this in mind as malloc() does not zero out the memory it allocates.
You can test your code in the following two ways:
// 1) to check functionality: $ make vector-test $ ./vector-test // 2) to check memory management using Valgrind: $ make vector-memcheck
Feel free to also use a debugger or add printf statements to vector.c and vector-test.c to debug your code.
Check-off
- Run ./vector-test and show it to your TA.
- Show your TA your modifications to vector.c
Exercise 2: linked list (ll)
This exercise uses ll.h, ll-test.c, and ll.c, which contains a buggy implementation of a doubly-linked circular list. The bugs are memory management errors that only occassionally cause problems.
Again there are two options for testing:
// 1) to check functionality: $ make ll-test $ ./ll-test // 2) to check memory management using Valgrind: $ make ll-memcheck
The first set of tests appears to work perfectly and while exercising almost all the functionality of the linked list implementation. On the lab machines, the next test may give the wrong answer due to memory corruption and the last test may segfault due to a memory error in ll.c. Whether or not the above errors or segfaults occur, memcheck should find several instances where ll.c has memory errors, including ones which do not appear to cause ll-test to behave incorrectly.
Fix the memory errors and memory leaks in ll.c. Use whatever debugging tools you want. (We recommend working from the Valgrind messages, but you can also add printfs to the test program and ll.c, use GDB, set environment variables described by man malloc, etc.). When you are done, ll-test should not crash and Memcheck should not report any invalid reads, writes, or leaks.
Check-off
- Tell your TA what you changed in ll.c
- Show your TA that Memcheck no longer reports that ll-test leaks memory or has other memory errors.