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
mkdir ~/lab03
cp -r ~cs61c/labs/03 ./lab03
malloc has some friends that you might find useful for this lab. man malloc to read their manual pages. In particular, realloc is often useful (though you are by no means required to use it).
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 vector-test' and then './vector-test'.
You can also run the program along with Valgrind Memcheck by typing 'make vector-memcheck'.
The errors that initially pop up in Memcheck should make sense given the code in vector_test.c
and vector.c's unimplemented vector_delete function.
Feel free to also
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.
./vector-test and 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
./ll-test
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
or by typing 'make ll-memcheck'
(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).)
The command will take a little while to run.
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 ('make ll-memcheck'
adds this by default).
Fix these memory leaks in ll.c.