Lab 6 — CS61C Fall 2010

CS61C Fall 2010 Lab 6


This lab will give you practice working with the malloc family of functions.




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


Copy the lab files with

cp -r ~cs61c/labs/06 ./lab6

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 a debugger or add printf statements to vector.c or the test code (vector-test.c) to debug your code.

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.


Exercise 2: ll.c

ll.h contains 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


The first set of tests appears to work perfectly and while exersizing almost all the functionality of the linked list implementation. On the lab machines, the next test gives the wrong answer due to memory corruption and the last test segfaults due to a memory error in ll.c.

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 ll-test under Memcheck using:

valgrind --dsymutil=yes --track-origins=yes ./ll-test

(Valgrind is only installed on the lab machines and instructional Linux machines. On Linux machines, omit --dsymutil=yes. The track-origins option has valgrind attempt to identify the sources of uninitialized values. The above command will not work at all if you are logged into one of the Solaris servers (e.g. star, cory).)

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 in ll.c. Use whatever debugging tools you want. (We think working from the Valgrind messages will be easiest, 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 or writes when running ll-test.

Memcheck can also attempt to identify memory leaks. To have it check for memory leaks on ll-test, add the --leak-check=full option to the valgrind comamnd. Fix these memory leaks in ll.c.