CS61C Summer 2013 Lab 3 - Malloc and Assembly

Since there is no lab on Thursday, July 4th, this lab is due within the first 10 minutes of your lab on Tuesday, July 9th.

Goals

WARNING! This lab is MUCH LONGER than normal labs and will be worth more. It is HIGHLY RECOMMENDED that you start before your lab section in order to finish it on time.

Reading

Setup

Copy the lab files with

$ mkdir ~/lab03 
$ cp ~cs61c/labs/03/* ~/lab03/. 

Lab 3-1: Memory Management

The following exercises deal with memory. To help you to find memory bugs, we have installed a copy of Valgrind Memcheck. Valgrind is ONLY on the lab machines in the Hive and the Orchard. This program will run an executable while keeping track of what registers and regions of memory contain allocated and/or initialized values. The program will run much slower (by a factor of about 10 to 50) so that this information can be collected, but Valgrind Memcheck can identify many memory errors automatically at the point at which they are produced. You will need to learn the basics of how to parse the Valgrind output.

You can finish this lab without ever directly calling Valgrind, but for those interested, the Makefile calls Valgrind as follows:

$ valgrind --tool=memcheck --leak-check=full --track-origins=yes [OS SPECIFIC ARGS] ./<executable>

The --track-origins flag attempts to identify the sources of unitialized values. The --leak-check=full option tries to identify memory leaks. [OS SPECIFIC ARGS] are simply a set of arguments to Valgrind that differ across operating systems (in our case, Ubuntu (Linux) and OS X (Darwin)). If you are interested in learning more about these, see the Makefile.

The last line in the Valgrind output is the line that will indicate at a glance if things have gone wrong. Here's a sample output from a buggy program:

==47132== ERROR SUMMARY: 1200039 errors from 24 contexts (suppressed: 18 from 18)

If your program has errors, you can scroll up in the command line output to view details for each one. For our purposes, you can safely ignore all output that refers to suppressed errors. In a leak-free program, your output will look like this:

==44144== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 18 from 18)

Again, any number of suppressed errors is fine; they do not affect us.

IMPORTANT: Valgrind will NOT run on the Solaris servers (e.g. star, cory, nova)! You MUST work on either the Hive machines or the Orchard machines.

Exercise 1: variable-length array (vector)

This exercise uses vector.h, vector-test.c, and vector.c, where 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.

Your task is to fill in the functions vector_delete() and vector_set() in vector.c so that our test code vector-test.c runs without any memory management errors. 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.

You can test your code in the following two ways:

// 1) to check functionality:
$ make vector-test
$ ./vector-test

// 2) to check memory management using Valgrind:
$ make vector-memcheck

Feel free to also use a debugger or add printf statements to vector.c and vector-test.c to debug your code.

Check-off

Exercise 2: linked list (ll)

This exercise uses ll.h, ll-test.c, and ll.c, which contains a buggy implementation of a doubly-linked circular list. The bugs are memory management errors that only occassionally cause problems.

Again there are two options for testing:

// 1) to check functionality:
$ make ll-test
$ ./ll-test

// 2) to check memory management using Valgrind:
$ make ll-memcheck

The first set of tests appears to work perfectly and while exercising almost all the functionality of the linked list implementation. On the lab machines, the next test may give the wrong answer due to memory corruption and the last test may segfault due to a memory error in ll.c. Whether or not the above errors or segfaults occur, 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. Use whatever debugging tools you want. (We recommend working from the Valgrind messages, 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, writes, or leaks.

Check-off

Lab 3-2: Intro to Assembly and MARS

The following exercises use a MIPS simulator called MARS, which provides a rich debugging GUI. You can run MARS on your home computer by downloading the jar file from the Internet or by copying it from ~cs61c/bin/Mars4_3.jar on the instructional machines. You will need Java J2SE 1.5.0 (or later) SDK installed on your computer, which can be obtained from Sun. If your home computer is a Mac, you can also follow the instructions here to install MARS as an app in one step.

You can run MARS in lab by typing 'mars &' at the command line. The ampersand is optional but will allow you to continue using that terminal window (on the Macs however, you'll need to run it in it's own terminal tab by pressing command-t first). To run the program remotely, you may either run via an instructional server (but NOT one of the Orchard machines), or through a local installation (recommended). When on an instructional server, you will need to be running an X-Server (like XMing), and enabling X11 tunneling.

Tip: Although it is possible, you should avoid running MARS remotely at all costs - it will be painfully slow to use and will overwhelm the servers if many students attempt to do so. It is in your best interest to setup/run a local copy of MARS.

Assembly Basics:

WARNING: MARS comes with a 'completion suggestion' feature that will show you lots of different ways/formats to complete the instruction you are currently typing. This includes numerous pseudo-instructions that allow very bizarre combinations of arguments. To avoid confusing yourself on syntax (especially for loads and stores), we HIGHLY RECOMMEND you use ONLY what's found on the Green Sheet and the pseudo-instructions la, li, and move.

Exercise 3: Familiarizing yourself with MARS

Getting started:

  1. Run MARS.
  2. Load lab3_ex3.s using File-->Open.
  3. View and edit your code in the "Edit" tab. Notice the code highlighting and 'completion suggestion' features.
  4. When ready, assemble your code using Run-->Assemble (or press F3).
  5. This will take you automatically to the "Execute" tab, which is where you can run and debug your program.
  6. Step through the program using Run-->Step (or press F7).
  7. You should take the time to familiarize yourself with everything in the Run menu (and the keyboard shortcuts).

For this exercise, we calculate the Fibonacci numbers using fib[0] = 0; fib[1] = 1; fib[n] = fib[n-1] + fib[n-2].
Follow the steps below and record your answers to the questions. The Help menu (F1) may come in handy.

  1. What do the .data, .word, .text directives mean (i.e. what do you put in each section)?
  2. Find the Text Segment in the "Execute" tab. What happened to the pseudo-instruction la (line 9)?
  3. How do you set a breakpoint in MARS? Set a breakpoint on line 14 and run to it. What is the instruction address? Has line 14 executed yet?
  4. Once at a breakpoint, how do you continue to execute your code? How do you step through your code? Run the code to completion.
  5. Find the "Run I/O" window. What number did the program output? Which fib number is this?
  6. At what address is n stored in memory? Try finding this by (1) looking at the Data Segment and (2) looking at the machine code (Code column in the Text Segment).
  7. Without using the "Edit" tab, have the program calculate the 13th fib number by manually modifying this memory location before execution. You may find it helpful to uncheck the "Hexadecimal Values" box at the bottom of the Data Segment.
  8. How do you view and modify the contents of a register? Reset the simulation (Run-->Reset or F12) and now calculate the 13th fib number by (1) breaking at a well-chosen spot, (2) modifying a single register, and then (3) unsetting the breakpoint.
  9. Lines 19 and 21 use the syscall instruction. What is it and how do you use it? (Hint: look in Help)

Check-off

Exercise 4: A short MIPS program

Write a piece of MIPS code from scratch that, given values in $s0 and $s1, accomplishes 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, store the sum of the previous two $t# register values. The $s0 and $s1 registers contain the initial values. Set the values of $s0 and $s1 manually with MARS instead of in your code. Finally, have your code print out the final value of $t7 as an integer (Hint: syscall).

Save your code in a file called lab3_ex4.s. Don't forget the "main:" label and to end your program with a "syscall 10"!

Check-off

Exercise 5: Debugging a MIPS program

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

Hint: you should describe the bug(s) in a file lab3_ex5.txt so you don't forget for check-off!

While you're here, you might find it interesting to see how this program created "integer arrays" and strings for the final output message.

Check-off

Exercise 6: Compiling from C to MIPS

For this exercise we need to use a program called mips-gcc (a cross-compiler for MIPS) that allows us to compile programs for the MIPS architecture on our x86 machines.

The file lab3_ex6.c is a C version of Exercise 5! (excluding the print syscall). 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

The -O2 option (capital 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.

Check-off