Goals
This lab will introduce you to the C debugger gdb (and its cousin, cgdb). You will gain some practical experience using the gdb to debug a buggy C program, and then you'll write a few C programs that gdb will be helpful in debugging if you don't get it right on the first try.
Setup
Copy the contents of ~cs61c/labs/03 to a suitable location in your home directory.
$ cp -R ~cs61c/labs/03/ ~/lab03
Exercises
Exercise 1: Debugger
For this exercise, you will find the GDB reference card useful. Compile hello.c with the "-g" flag:
$ gcc -g -o hello hello.c
This causes gcc to store information in the executable program for gdb to make sense of it. Now start the debugger, (c)gdb:
$ cgdb hello
If cgdb does not work, you can also use gdb to complete the following exercises (start gdb with gdb hello
). The cgdb debugger is only installed on your cs61c-XXX accounts. Please use the hive machines or one of the computers in 271, 273, 275, or 277 soda to run cgdb, since our version of cgdb was built for Ubuntu.
Step through the whole program by:
- setting a breakpoint at main
- giving gdb's run command
- using gdb's single-step command
Type help
from within gdb to find out the commands to do these things, or use the reference card.
cgdb vs gdb
In this exercise, we use cgdb to debug our programs. cgdb is identical to gdb, except it provides some extra nice features that make it more pleasant to use in practice. All of the commands on the reference sheet work in gdb. In cgdb, you can press ESC to go to the code window (top) and i to return to the command window (bottom) — similar to vim. The bottom command window is where you'll enter your gdb commands.
More gdb commands
Learning these commands will prove useful for the rest of this lab, and your C programming career in general. Create a text file containing answers to the following questions:
- How do you pass command line arguments to a program when using gdb?
- How do you set a breakpoint which only occurs when a set of conditions is true (e.g. when certain variables are a certain value)?
- How do you execute the next line of C code in the program after stopping at a breakpoint?
- If the next line of code is a function call, you'll execute the whole function call at once if you use your answer to #3. How do you tell GDB that you want to debug the code inside the function instead?
- How do you resume the program after stopping at a breakpoint?
- How can you see the value of a variable (or even an expression like
1+2
) in gdb? - How do you configure gdb so it prints the value of a variable after every step?
- How do you print a list of all variables and their values in the current function?
- How do you exit out of gdb?
Checkoff
- Set the breakpoint at main, and show your TA how you run up to that breakpoint. Show your TA your text document containing the additional gdb commands.
Exercise 2: Debugging a buggy C program
You will now use your newly acquired gdb knowledge to debug a short C program! Consider the program ll_equal.c. Compile and run the program, and experiment with it. It will give you the following result:
$ gcc -g -o ll_equal ll_equal.c $ ./ll_equal equal test 1 result = 1 Segmentation fault
Now, start gdb on the program, following the instructions in exercise 1. Set a breakpoint in the ll_equal() function, and run the program. When the debugger returns at the breakpoint, step through the instructions in the function line by line, and examine the values of the variables. Pay attention to the pointers a
and b
in the function. Are they always pointed to the right address? Find the bug and fix it.
Checkoff
- Explain the bug and your fix to the function.
Exercise 3: Pointers and Structures in C
Here's one to help you in your interviews. In ll_cycle.c, complete the function ll_has_cycle()
to implement the following algorithm for checking if a singly-linked list has a cycle.
- Start with two pointers at the head of the list. We'll call the first one
tortoise
and the second onehare
. - Advance
hare
by two nodes. If this is not possible because of a null pointer, we have found the end of the list, and therefore the list is acyclic. - Advance
tortoise
by one node. (A null pointer check is unnecessary. Why?) - If tortoise and hare point to the same node, the list is cyclic. Otherwise, go back to step 2.
After you have correctly implemented ll_has_cycle()
, the program you get when you compile ll_cycle.c
will tell you that ll_has_cycle()
agrees with what the program expected it to output.
Checkoff
- Show your
ll_has_cycle()
function to the TA.
Exercise 4: Linear feedback shift register
In this exercise, you will implement a lfsr_calculate()
function to compute the next iteration of a linear feedback shift register (LFSR). Applications that use LFSRs are: Digital TV, CDMA cellphones, Ethernet, USB 3.0, and more! This function will generate pseudo-random numbers using bitwise operators. For some more background, read the Wikipedia article on Linear feedback shift registers. In lfsr.c, fill in the function lfsr_calculate()
so that it does the following:
Hardware diagram (see explanation below)
Explanation of the above diagram
- On each call to
lfsr_calculate
, you will shift the contents of the register 1 bit to the right. - This shift is neither a logical shift or an arithmetic shift. On the left side, you will shift in a single bit equal to the Exclusive Or (XOR) of the bits originally in position 11, 13, 14, and 16.
- The curved head-light shaped object is an XOR, which takes two inputs (a, b) and outputs a^b.
- If you implemented
lfsr_calculate()
correctly, it should output all 65535 positive 16-bit integers before cycling back to the starting number.
After you have correctly implemented lfsr_calculate()
, compile lfsr
and run it. Your output should be similar to the following:
$ make $ ./lfsr My number is: 1 My number is: 5185 My number is: 38801 My number is: 52819 My number is: 21116 My number is: 54726 My number is: 26552 My number is: 46916 My number is: 41728 My number is: 26004 My number is: 62850 My number is: 40625 My number is: 647 My number is: 12837 My number is: 7043 My number is: 26003 My number is: 35845 My number is: 61398 My number is: 42863 My number is: 57133 My number is: 59156 My number is: 13312 My number is: 16285 ... etc etc ... Got 65535 numbers before cycling! Congratulations! It works!
Checkoff
- Show your
lfsr_calculate
function and the result for running lfsr.c to the TA.