Deadline: EOL Monday, February 3rd
To get the starter files for this lab, run the following command in your
$ git pull starter master
If you get an error like the following:
fatal: 'starter' does not appear to be a git repository fatal: Could not read from remote repository.
make sure to set the starter remote as follows:
$ git remote add starter https://github.com/61c-teach/sp20-lab-starter.git
and run the original command again.
In this lab, we will be using the command line program gcc to compile programs in C. The simplest way to run gcc is as follows:
$ gcc program.c
This compiles program.c into an executable file named a.out. If you’ve taken CS61B or have experience with Java, you can kinda think of gcc as the C equivalent of javac. This file can be run with the following command:
The executable file is
a.out, so what the heck is the
./ for? Answer: when
you want to execute an executable, you need to prepend a file path in order to
distinguish your command from a command like python3. The dot refers to the “current
directory.” Incidentally, double dots (
..) would refer to the directory one
gcc has various command line options which you are encouraged to
explore. In this lab, however, we will only be using
-o, which is used to specify
the name of the executable file that
gcc creates. You can use the following
commands to compile
program.c into a program named program, and then run it.
This is helpful if you don’t want all of your executable files to be named
$ gcc -o program program.c $ ./program
In this exercise, we will see an example of preprocessor macro definitions. Macros
can be a messy topic, but in general the way they work is that before a C file is
define macro constant names are replaced exactly with the value
they refer to. In the scope of this exercise, we will be using macro definitions
exclusively as global constants. Here we define
CONSTANT_NAME to refer to
literal_value (an integer literal). Note that there is only a space separating
name from value.
#define CONSTANT_NAME literal_value
Now, look at the code contained in
eccentric.c. Notice the four different
examples of basic C control flow. (Think: What are they?) Also, do you recognize
these eccentric sayings and people from Berkeley? :)
First compile and run the program to see what it does. Play around with the constant values of the four macros: V0 through V3. See how changing each of them changes the program output.
Modifying only these four values, make the program produce the following output.
Berkeley eccentrics: ==================== Happy Happy Happy Yoshua Go BEARS!
There are actually several different combinations of macros that can give this output. Here’s the challenge for you in this exercise: consider what the minimum number of distinct values that V0 through V3 can have such that they still give this exact output. For example, the theoretical maximum is four, when they are all distinct from each other.
Stuck on how to run the program? Revisit the introduction. We’d like you to compile
the program into an executable called
eccentric; can you use the
-o flag to
A debugger, as the name suggests, is a program which is designed specifically to help you find bugs, or logical errors and mistakes in your code (side note: if you want to know why errors are called bugs, look here). Different debuggers have different features, but it is common for all debuggers to be able to do the following things:
For this exercise, you will find the GDB reference card useful.
GDB stands for “GNU De-Bugger.” Compile
hello.c with the
$ 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 our debugger, (c)gdb:
$ cgdb hello
Notice what this command does! You are running the program cgdb on the executable
file hello generated by gcc. Don’t try running cgdb on the source code in hello.c!
It won’t know what to do. 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 27x Soda to run cgdb, since our version of cgdb was built for Ubuntu.
Note: you’re welcome to install and run (c)gdb on your local computer, but be advised it will not install on (updated) MacOS machines. If this applies to you, you can use lldb which is another great debugger. The commands differ slightly, but there are great guides out there (like this one!) to help you get started. For this lab, though, use the lab machines and cgdb.
Step through the whole program by doing the following:
Type help from within gdb to find out the commands to do these things, or use the reference card.
Look here if you see an error message like printf.c: No such file or directory. You probably stepped into a printf function! If you keep stepping, you’ll feel like you’re going nowhere! CGDB is complaining because you don’t have the actual file where printf is defined. This is pretty annoying. To free yourself from this black hole, use the command finish to run the program until the current frame returns (in this case, until printf is finished). And NEXT time, use next to skip over the line which used printf.
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.
Learning these commands will prove useful for the rest of this lab, and your C
programming career in general. In the text file named
gdb.txt, answer the
Let’s see what happens if your program requires user input and you try to run GDB
on it. First, run the program defined by
interactive_hello.c to talk to an overly
$ gcc -g -o int_hello interactive_hello.c $ ./int_hello
Now, we’re going to try to debug it (even though there really are no bugs).
$ cgdb int_hello
What happens when you try to run the program to completion?
We’ll be learning about a tool to help us avoid this situation. The purpose of this
exercise is to make you unafraid of running the debugger even when your program
needs user input. It turns out that you can send text to
the file stream read by the function fgets in this silly program, with some
special characters right from the command line.
Take a look at “redirection” on this website, and see if you can figure out how to send some input to the program without explicitly providing it while it’s running (which, I hope you’ve realized, gets you stuck in CGDB). Look at this stackoverflow post for more inspiration.
Hint 1: If you’re creating a text file containing your input, you’re on the right track! Hint 2: Remember you can run things with command line args (including the redirection symbols) from CGDB as well!
Hopefully you’ll appreciate how redirection helps you avoid that nasty situation with CGDB. Don’t ever be afraid of the debugger! We know it looks kind of nasty, but it’s there to help you.
Even with a debugger, we might not be able to catch all bugs. Some bugs are what we refer to as “bohrbugs”, meaning they manifest reliably under a well-defined, but possibly unknown, set of conditions. Other bugs are what we call “heisenbugs”, and instead of being determinant, they’re known to disappear or alter their behavior when one attempts to study them. We can detect the first kind with debuggers, but the second kind may slip under our radar because they’re (at least in C) often due to mis-managed memory.
Remember that unlike other programming languages, C requires you (the programmer) to manually manage your memory. We’ll cover this more later this week, but this is all you’ll need to know for now.
To help catch these “heisenbugs” we will use a tool called Valgrind. Valgrind is a program which emulates your CPU and tracks your memory accesses. This slows down the process you’re running (which is why we don’t, for example, always run all executables inside Valgrind) but also can expose bugs that may only display visible incorrect behavior under a unique set of circumstances. Valgrind is installed by default on hive machines. Valgrind is available for local install on most platforms; however, a version for more recent versions of MacOS may not yet be available. While you are welcome to do this exercise on the hive it will likely be in your benefit to have Valgrind locally for project testing later on.
In this exercise we are going demonstrate two different examples of Valgrind outputs and walk through how each might be useful.
First try building two new executables,
no_segfault_ex.c (use the
-o flag from before!). At
this point you should be able to use
gcc to successfully build these executables.
Now let’s try running the executables. What outputs do you observe?
Let’s start with
segfault_ex. You should have observed a segmentation fault
(segfault), which occurs when a program crashes from trying to access memory that
is not available to it (more on this later in the course; This is actually an
artifact from early memory design. Today we work with ‘paged memory’ instead of
‘segmented memory’ but the error message remains!).
This C file is very small so you should be able to open the file and understand what is causing the segfault. Do so at this time, but do not change the file. Why does the segfault occur?
Now let’s understand what to do if we have a very large file and need to find a segfault. Here is where Valgrind is our new friend. To run the program in Valgrind use the command:
$ valgrind ./segfault_ex
This should cause Valgrind to output where the illegal access occurred. Compare
these results to what you determined by opening the file. How could Valgrind help
you address a segfault in the future?
Now try running Valgrind on
no_segfault_ex. The program should not have
crashed but there is still an issue with the file. Valgrind can help us find the
(seemingly invisible) problem.
Unfortunately here you will see that Valgrind seems to not be able to tell you exactly where the problem is occurring. Use the message provided by Valgrind to determine which variable has undefined behavior and then try to infer what must have happened (Hint: What is an uninitialized value?).
At this point we do not expect you to be familiar with
sizeof (that comes next
week!) so all we want you to get out of this section is some intuition around
where the problem likely occurred.
Hopefully after walking through this example you’ll be able to understand and answer the following:
We are introducing you to Valgrind now because it is an extremely important tool that you will want as soon as you start writing C. However to really appreciate it we will need to learn about C’s memory model, which we will do next week. After you have covered memory in lecture, come back to this lab and try answering the following questions:
no_segfault_exproduce inconsistent outputs?
sizeofincorrect? How could you still use
sizeofbut make the code correct?
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.
If you want to see the definition of the
node struct, open the
ll_has_cycle(). Once you’ve done so, you can execute the following
commands to run the tests for your code. If you make any changes, make sure
to run ALL of the following commands again, in order.
$ gcc -c ll_cycle.c $ gcc -c test_ll_cycle.c $ gcc -o test_ll_cycle test_ll_cycle.o ll_cycle.o $ ./test_ll_cycle
Hint: There are two common ways that students usually write this function. They differ in how they choose to encode the stopping criteria. If you do it one way, you’ll have to account for a special case in the beginning. If you do it another way, you’ll have some extra NULL checks, which is OK. The previous 2 sentences are meant to urge you to not stress over cleanliness. If they don’t help you, just ignore them. The point of this exercise is to make sure you know how to use pointers.
Here’s a Wikipedia article on the algorithm and why it works. Don’t worry about it if you don’t completely understand it. We won’t test you on this.
By the way, the pointers are called “tortoise” and “hare” because the tortoise pointer is incremented slowly (like a tortoise, which moves slowly) and the hare pointer is incremented quickly (twice as fast as the tortoise; like a hare, which moves quickly).
As a closing note, the story of the tortoise and the hare is always relevant, especially in CS61C. Writing your C programs slowly and steadily, using debugging programs like CGDB, is what will win you the race.
Here’s another exercise to help you in your interviews! For this exercise, you will fill in the functions
list.c. Don’t forget to look at
list.h to see the definition of the node struct and also to see the general format of a simple .h (header) file!
append_node(), you will append a node to the end of a linked list.
reverse_list(), you will reverse a linked list in place (i.e. without creating a new list). For example, the list
1->2->3->4->5 would become
HINT: In each iteration of your loop to traverse the linked list, think about what information you need to store in variables before reversing the link so that you can still successfully keep iterating through the list and reversing links.
This is a fairly difficult exercise in C; we recommend that you draw a picture if you get stuck because doing so tends to make double pointers seem less intimidating. Please write up what you think the algorithm should be before asking a TA for help. You can think of the double pointer as simply a pointer to a list of pointers to nodes.
Why do both of these functions take in a
node** and not a
node*? Think about memory management; if the input was a node*, would it be possible to modify the pointer that was passed into the function from, say, the main() function? Remember that C is pass-by-value!
ACTION ITEM: Finish implementing
Once you complete these functions, you can compile and run your code using the following commands. If you make any changes, make sure to run ALL of the following commands again, in order.
If you compile and run locally, the test may print out that the next attributes of your nodes are 0x0 and that your test failed. This is completely fine; your tests will pass the autograder. If you’d like to be completely sure that your test passes locally, compile and run your code on the hive machines.
$ gcc -c list.c $ gcc -c test_list.c $ gcc -g -o test_list test_list.o list.o # This will create an executable by linking test_list.o and list.o. $ ./test_list
This will print out the results of the test. To debug, you can run CGDB and step through the test in
Please submit to the Lab Autograder assignment (same as last week!).
Note that the autograder for the gdb answers is very simple. Make sure that:
gdb.txtfile start with the answer number (e.g.
command arg, only put