For this lab, you are welcome to get technical help from another student on how to use or install any of the tools involved. You may also get syntax help on C.
For this week's exercise, you are will need to file lldbtutorial.c and a Makefile for compiling it with -g (to enable interactive debugging), and an executable name lldb_tut. (Please note that this lab omits -Wall, only to assist in learning lldb. Ordinarily, we shall not omit -Wall.) I would also suggest copying the original lldbtutorial.c file to another name (e.g. lldb_orig.c) so that you can eaisly look back at the original code at any time.
Create a blank lldbtutorial.c file, then copy and paste from the above link. Do the same with the Makefile. Then you can copy the lldbtutorial.c file using the cp command:
$ cp lldbtutorial.c lldb_orig.c
The source code file has a selection of functions, each of which contains at least one bug. Although you will fix these functions as you work through this exercise, the purpose of this tutorial is not in itself to fix these broken functions. By now, this far along in the sequence, we expect that you can do that, one way or another. The purpose of this lab is to learn to use lldb (the "Low Level Debugger"). Please view the exercise as an opportunity to acquaint yourself with a well-designed tool that is sure to help you negotiate common difficulties in your work as a programmer. Strong familiarity with a sophisticated debugger like lldb will make your programming a good deal more pleasant, once you've learned to use the tool well.
The first function in lldbtutorial.c is a naive algorithm to compute the nth Fibonacci number. We assume that the 0th member of the Fibonacci sequence is 0, the next is 1, and every subsequent member of the sequence is the sum of its two predecessors.
/* === fib === */
unsigned int fib(unsigned int n)
{
if (n==0) {
return 0;
} else if (n==1) {
return 1;
} else {
return fib(n-1) + fib(n);
}
}
int main(int argc, char *argv[])
{
/*** testing fib ****/
unsigned int f0 = fib(0);
unsigned int f1 = fib(1);
unsigned int f2 = fib(2);
printf("/*** fib ***/\n");
printf("fib(0)\t%d\n",f0);
printf("fib(1)\t%d\n",f1);
printf("fib(2)\t%d\n",f2);
By writing Segmentation fault: 11 to the terminal, the runtime system is telling you here that something went wrong in the program, and you tried to read or write memory somewhere you shouldn't have. From a debugging standpoint, this information is quite unhelpful, as it is entirely vague.$ make clang -g -o lldb_tut lldbtutorial.c $ ./lldb_tut /*** fib ***/ Segmentation fault: 11
Assuming you cannot locate the problem with fib by reading the source code, there are several approaches you can take. One approach is to pepper the source code with diagnostic printf messages like so:
/* === fib === */
unsigned int fib(unsigned int n)
{
printf("fib: called with n %d\n", n);
if (n==0) {
printf("fib: n==0 branch\n");
return 0;
} else if (n==1) {
printf("fib: n==1 branch\n");
return 1;
} else {
printf("fib: else branch\n");
return fib(n-1) + fib(n);
}
}
This leads to the following infinite output, which is more helpful than the unqualified Segmentation fault we had before:
After typing Ctrl-c to stop this endless flow of messages, we might (correctly) conclude there is something in the call to fib(2) that leads to infinitely many recursive calls.$ ./lldb_tut fib: called with n 0 fib: n==0 branch fib: called with n 1 fib: n==1 branch fib: called with n 2 fib: else branch fib: called with n 1 fib: n==1 branch fib: called with n 2 fib: else branch fib: called with n 1 fib: n==1 branch fib: called with n 2 fib: else branch (...and on and on...)
If you want to be able to look at it as it goes, then you can use the more command. This allows you to control the volume of printfs. It will show you one screen of output. Then press the space bar to get the next screen of printfs. Use Ctrl-c to stop.:
$ ./lldb_tut | more fib: called with n 0 fib: n==0 branch fib: called with n 1 fib: n==1 branch fib: called with n 2 fib: else branch fib: called with n 1 fib: n==1 branch fib: called with n 2 fib: else branch fib: called with n 1 fib: n==1 branch fib: called with n 2
Assuming this leads us to fix the problem, we now have to go back to the original code, fix the problem, remove all the debugging messages we introduced to discover the problem, and go on. If that seems like a toilsome process, that's because it is. Furthermore, speaking from bitter experience, the more thorny one's problem is, and the more messages one needs to insert in a labyrinth of functions to uncover a deep problem, the more painful and difficult it is to go through the code to remove all such messages. In other words, this debugging approach scales poorly. That is, it seems like a good idea and works well on small problems, but it is very inefficient for large problems. Therefore, we will teach you a better approach that will be far superior on large problems, though we'll start out using it on problems for which printfs would have worked just as well. This tutorial is about process, not solution (which is why you do not need to turn anything in). Using an interactive debugger such as lldb will give you another, much cleaner, way to go about finding and solving problems in your code.
The compiler flag -g tells the compiler to generate supplementary information about your program to be used by lldb in interactive debugging. As such, you can and should make it a habit to compile with -g, at least during software development (as opposed to deployment).
Let's revisit the problematic fib above, this time with the assistance lldb. (This assumes your copy of fib has no debugging messages in it, so if you have inserted any, remove them now.) We compile lldb_tut, run it and see a segmentation fault, and then begin an lldb session to debug it, as follows:
Your output might differ slightly from this, but your terminal should display the lldb prompt (lldb), waiting for input.$ make clang -g -o lldb_tut lldbtutorial.c $ ./lldb_tut /*** fib ***/ Segmentation fault: 11 $ lldb lldb_tut (lldb) target create "lldb_tut" Current executable set to 'lldb_tut' (x86_64). (lldb)
Typing run will run the lldb_tut program. It will fail, as it did before, but it an informative rather than opaque way. (Please note; you may be asked to type your password at this step.)
(lldb) run
Process 18103 launched: '/Users/adamshaw/Desktop/lldb_tut' (x86_64)
/*** fib ***/
Process 18103 stopped
* thread #1: tid = 0x14e67, 0x0000000100000ae7 lldb_tut`fib(n=2) + 71 at lldbtutorial.c:18, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, address=0x7fff5f3ffff8)
frame #0: 0x0000000100000ae7 lldb_tut`fib(n=2) + 71 at lldbtutorial.c:18
15 else if (n==1)
16 return 1;
17 else
-> 18 return fib(n-1) + fib(n);
19 }
20
21 /* === fact === */
(lldb)
(lldb) list 18
18 return fib(n-1) + fib(n);
19 }
20
21 /* === fact === */
22 /* compute n factorial */
23 unsigned int fact(unsigned int n)
24 {
25 int i=n;
26 int result=1;
27 while (i-->0)
To spoil whatever suspense is left about the failure of fib, it's that, in its else branch, fib calls itself with argument n unchanged, which leads to infinitely many recursive calls. As such, we should expect the stack to be a gigantic pile of stack frames for called to fib. We can view a representation of the function call stack within lldb by typing bt (for "backtrace"). Take a deep breath and type bt; be patient -- this take a while. What you will see eventually is a representation of the function call stack at the time of failure. Look closely and you'll be able to read it as many, many calls to fib(2).
Type quit to exit the lldb session. (Confirm that you do want to quit.) We'll start another session in a moment.
We now restart lldb as follows:
We know the problem in the program is around line 18; set a breakpoint at line 18 by typing b lldbtutorial.c:18 at the lldb prompt. Now when you run the program, execution will pause at line 18, and wait for further interaction.$ lldb lldb_tut (lldb) target create "lldb_tut" Current executable set to 'lldb_tut' (x86_64). (lldb)
Assuming you have set a breakpoint at line 18, type these instructions in sequence:
(lldb) bt
* thread #1: tid = 0x1584e, 0x0000000100000add lldb_tut`fib(n=2) + 61 at lldbtutorial.c:18, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
* frame #0: 0x0000000100000add lldb_tut`fib(n=2) + 61 at lldbtutorial:18
frame #1: 0x0000000100000af7 lldb_tut`fib(n=2) + 87 at lldbtutorial:18
frame #2: 0x0000000100000af7 lldb_tut`fib(n=2) + 87 at lldbtutorial:18
frame #3: 0x0000000100000af7 lldb_tut`fib(n=2) + 87 at lldbtutorial:18
frame #4: 0x0000000100000af7 lldb_tut`fib(n=2) + 87 at lldbtutorial:18
frame #5: 0x0000000100000af7 lldb_tut`fib(n=2) + 87 at lldbtutorial:18
frame #6: 0x0000000100000af7 lldb_tut`fib(n=2) + 87 at lldbtutorial:18
frame #7: 0x0000000100000c9e lldb_tut`main(argc=1, argv=0x00007fff5fbffb20) + 78 at lldbtutorial:80
frame #8: 0x00007fff8d6585ad libdyld.dylib`start + 1
Now (at last!) go ahead and repair the fib function in the source code itself, compile and run, and move on to the next problem when done.
The rest of the functions in the source file also contain bugs. Work through each function with lldb, setting breakpoints, looking at stack frames, printing the values of variables, and stepping through code. There are various ways of moving through code line by line. From within an lldb session, type help continue, help next and help step to read about three of them.
You may actually need lldb's help to figure out what the problems with these functions are, in which case, great! Use lldb for real. If, on the other hand, you know immediately how to fix each function, even without the assistance of the interactive debugger, impersonate someone who needs its help, and use your lab time to learn as much about lldb as you can. Talk to your neighbors and ask lots of questions. The official documentation is here:
http://lldb.llvm.org/index.html
There is a bug, of sorts, in main that lldb won't catch. Nor is it easy to observe, since the program runs correctly even in its presence. (This is the sort of bug that functional programmers are especially likely to overlook.) Can you find it?