CS61C Summer 2012 Lab 3 - Malloc and Assembly

Goals

The first half of this lab will give you practice working with the malloc family of functions.

The second half of this lab will give you practice running and debugging assembly programs using the MARS simulator. You can also run MARS on your home computer by downloading the jar file from ~cs61c/bin/Mars_4_2.jar on the instructional machines. You also need Java J2SE 1.5.0 (or later) SDK installed on your computer, which can be obtained from Sun.

WARNING! THIS LAB IS TWICE LONGER THAN CONVENTIONAL LABS! TRY TO START THE LAB BEFORE YOUR LAB SECTION IN ORDER TO FINISH IT ON TIME

Reading

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

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).

Exercises

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 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.

Checkoff

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

$ ./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.

Checkoff

Running Assembly programs

Assembly programs go in text files with a .s extention. The program must contain a label "main:" (similar to the main function in C programs) and end with a "addi $v0,$0,10" followed by a "syscall". Unlike normal functions which use "jr $ra" to return main is special and must transfer control back to the operating system when it is done rather than just returning.

For this lab we will be running our code in MARS, a MIPS simulator which provides a rich debugging GUI, rather than trying to run on a bare processor. In general, assembly programmers prefer this mode of development when possible as it is far easier to debug and work with the code.

You can run MARS in the lab by typing the ~cs61c/bin/mars command.

To run the program remotely, you may either run via an instructional server (such as nova.cs.berkeley.edu, but not one of the macs), or through a local installation (recommended) . When on an instructional server, you will need to follow the usual steps of running an X-Server (like XMing), and enabling X11 tunneling. The mars command will run the program.

To run a local installation, you can download the file ~cs61c/bin/Mars_4_2.jar, which is an executable JAR file. To run it, simply open a command line, navigate to the directory containing Mars_4_2.jar and run java -jar Mars_4_2.jar. Of course this will only work if you have java installed properly and on your path.

If you are coding your .s file on the (non-mac) instructional computers with no intent of running or debugging it, please use another (non-java) editor such as emacs, vi or pico so that we don't overwhelm the servers, which may run slowly, as a result of the inefficiency of java and the old age of the servers.

After starting mars, you can load your .s file using File->Open. You can edit your code by clicking the "Edit" tab and run or debug your program by clicking the "Execute" tab. In order to be able to execute your program, you must assemble the code first using Run->Assemble (F3).

To debug your assembly code in MARS you can set breakpoints, step through instructions one by one, view what are in your registers or in memory, as well as initialize values in registers before your program starts.  You should spend some time before the lab getting familiar with MARS if possible.

Exercises

Exercise 3: Familiarizing yourself with MARS

Load lab3_ex3.s into MARS and assemble the code. Assume that fib[0] = 0; fib[1] = 1; fib[n] = fib[n-1] + fib[n-2]
Use Help (icon with the question mark) in order to answer the following questions about how to use MARS.

  1. What do the .data, .word, .text directives mean (i.e., what do you put in each section)?
  2. How do you set a breakpoint in MARS? Set breakpoint on line 15 and show this to your TA when you have answered all of these questions.
  3. After your program stops because of a breakpoint, how do you continue to execute your code? How do you step through your code?
  4. How can you find out the contents of a register? How do you modify the value of a register.
  5. At what address is n stored in memory? Calculate the 13th fib number by modifying this memory location.
  6. line 18 and 20 use syscall instruction. What is it and how do you use it? (hint: syscall inside Help!))

Checkoff

Exercise 4: A short MIPS program

Write a piece of MIPS code that, given values in $s0 and $s1, put into the $t? registers the following:

$t0 = $s0
$t1 = $s1
$t2 = $t0 + $t1
$t3 = $t1 + $t2
...
$t7 = $t5 + $t6

In other words, for each register from $t2 to $t7, it stores the sum of the previous two $t? register values. The $s0 and $s1 registers contain the initial values.

Don't set the value of $s0 and $s1 in your code. Instead, learn how to set it manually with MARS.

Save your code in a file called lab3_ex4.s

Checkoff

Exercise 5: Debugging a MIPS program

Debug the loop in the program in lab3_ex5.s. It is meant to copy integers from memory address $a0 to memory address $a1, until it reads a zero value. The number of integers copied (up to, but NOT including the zero value), should be stored in $v0.

Describe in a file lab3_ex5.txt the bug(s) of the code. Create a file lab3_ex5_ok.s that contains a bug fixed version of lab3_ex5.s. Show these both to your TA.

Exercise 6: Compiling from C to MIPS

The file lab3_ex6.c is a C version of the program in the previous part of the lab. If on one of the Sutardja Dai Macs, you will first have to ssh into hive1 (or another linux instructional machine), as follows:

$ ssh hive1
[...Type in your password and login...]

Compile this program into MIPS code using the command:

$ mips-gcc -S -O2 -fno-delayed-branch -I/usr/include lab3_ex6.c -o lab3_ex6.s

On the Macs, type exit to log out of the remote machine.

The -O2 option (letter "O" and 2) turns on a level of optimization. The -S option generates assembly code. Don't worry about the delayed branch option for now; we will revisit this topic again when we talk about pipelining. The above command should generate assembly language output for the C code. Please note that you will not be able to run this code through MARS.

Find the assembly code for the loop that copies sources values to destination values. Then, find where the source and dest pointers you see in lab3_ex6.c are originally stored in the assembly file. Finally, explain how these pointers are manipulated through the loop.

Find the section of code in lab3_ex6.s that corresponds to the copying loop and explain how each line is used in manipulating the pointer.