Lab 12 — CS61C Fall 2012

CS61C Fall 2012 Lab 12

Goals

This lab will give you practice working with the malloc family of functions as well as a chance to try out Valgrind.

Exercises

Partners

Working with a partner is highly recommended. If you work with a partner, be sure both partners understand all aspects of your solution.

Setup

Pull the files

$ cd ~/work
$ git pull ~cs61c/labs/fa12/12 master

Exercise 1: vector.c

In vector.c, 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.

Fill in the missing code (you only need to modify vector.c), and test it by running 'make test-vector'. If the test breaks, feel free to use gdb or add printf statements to vector.c or the test code (vector-test.c) to debug your code. You may also find running vector-test under valgrind helpful (explained further in the next section).

$ valgrind --leak-check=full ./vector-test

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. Allocating memory using malloc() is sufficient though it doesn't zero out allocated memory. If you are interested, you can also look up calloc() and realloc().

Checkoff

Exercise 2: ll.c

We give you a buggy implementation of doubly-linked circular list. The bugs are memory management errors that only occassionally cause problems.

Compile a testing program using 'make ll-test'. Then run it using

$ ./ll-test

The first set of tests appears to have some errors while the last test segfaults due to a memory error in ll.c. (It actually didn't segfault on the hive machines but fails on some other machines. Some changes were made to replicate the effect.)

To help you to find memory bugs, we have installed a copy of Valgrind Memcheck on the lab machines. This program will run a binary while keeping track of what regions of memory and register contain allocated and/or initialized values. The program will run much slower so that this information can be collected, but using it, Valgrind Memcheck can identify many memory errors automatically at the point at which they are produced.

Run 'make test-list'. The following command will run: valgrind --tool=memcheck --leak-check=full --track-origins=yes ./ll-test

Valgrind is only installed on the lab machines. The track-origins option has Valgrind attempt to identify the sources of uninitialized values. The --leak-check=full option has Valgrind identify memory leaks.

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. When you are done, ll-test should not crash and Memcheck should not report any invalid reads or writes, or memory leaks when running ll-test.

Checkoff