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
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
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 (
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.
vector-testand show it your TA.
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
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
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
Fix these memory leaks in ll.c.