Termbank
  1. A
    1. API
    2. ASAN
    3. Access specifiers
  2. C
    1. Constructor
    2. const
  3. G
    1. GDB
    2. g++
  4. M
    1. Make
    2. Memory Leak
  5. P
    1. Pointer
  6. R
    1. Recursion
  7. S
    1. std
  8. V
    1. Valgrind
Completed: / exercises

LAB_GDB: Debugging Linked Lists with GDB

Due date: 2024-05-09 23:59.

Assignment Description

You are working on a card game program and have chosen to represent the deck of cards using a singly linked list. You have written two functions to manipulate the deck, shuffle and reverse. After struggling with compiler errors for hours, you have finally managed to successfully compile the program. Excited to test it out, you decide to run some simple simulations, but to your disappointment, you receive the following message in the terminal:
  Segmentation Fault
Ouch. What do you do now? You may have to debug your code.
You have a few options to do this. You could open up your code and try to manually spot the errors, but that can be a challenging task, especially with segmentation faults. Another option is to add cout statements to your code, but this requires a lot of adding and removing of lines of code for each bug. Alternatively, you could try using ASAN or Valgrind, but these tools are most useful for memory errors and may not provide much information about logical bugs. Another option is to learn about debugging tools, such as GDB.
GDB stands for GNU Debugger, which is a popular debugger used in software development. It allows developers to analyze and debug their programs by examining and manipulating their internal state, such as variables and memory locations. With GDB, developers can set breakpoints, step through their code line by line, inspect variables, and examine the call stack. It is a command-line tool, which means that it is operated by entering commands into a terminal window. GDB is open-source software and is available for a wide range of platforms and programming languages.

Download The Provided Files

Just like you already did it in previous labs, start with downloading and unzipping the provided files from here: lab_gdb.zip.
There will be many files in your lab_gdb directory, but you will only need to modify list.cpp to complete this lab. All other files including any testing files you might add will not be used for grading.

Understanding the Provided Code

To understand how the executable for this lab is built and executed, take a look at the main function in the main.cpp file. Once compiled and linked, the file generates an executable named lab_gdb. If you run the executable, you will receive the following output:
  ./lab_gdb
  [main]: testInsertFront()
  [testInsertFront]: < >
  [testInsertFront]: size: 0
  [testInsertFront]: Incorrect size
  [main]: testInsertBack()
  [testInserts]: < 1 >
  [testInserts]: size: 9
  [testInserts]: Incorrect size
  [main]: testReverse()
  Segmentation fault
In addition, you can run the executable by typing ./lab_gdb in the terminal and specifying one of the four available options: front, back, reverse, and shuffle. All of the output produced by these options is incorrect. For instance, running the shuffle option results in a segmentation fault error that you will fix by the end of this lab:
  ./lab_gdb shuffle
  [main]: testShuffle()
  [testShuffle]: before < >
  Segmentation fault

Getting Started with GDB

Now we will walk you through the basics of GDB. To launch your program using GDB, run the following command:
  gdb lab_gdb
To run your program with optional command line arguments (that is, front, back, reverse, or shuffle arguments), type :
  (gdb) run (arguments)
Note: Throughout the lab, we'll use the notation
  (gdb) command...
to indicate that the command should be run from within GDB.
GDB provides several helpful features. First, it outputs similar debugging information as Valgrind in cases of errors like segmentation faults. Second, and more importantly, it enables you to stop program execution, move around, and view the state of the running program at any point in time.
Note: If you're already familiar with GDB, you can skip ahead to the Linked Lists Exercises. However, it may still be useful to refer to the next two sections for a quick reference on GDB commands when working on this and following labs.

Walking Through Your Code with GDB

The following are the features of GDB that allow you to navigate through your code:

Viewing the State of Your Code

The next set of GDB features enables you to view the state of your running program in greater detail. At each breakpoint, you can inspect the values of variables, including their current values and any changes that occurred during program execution. You can also print out the values of expressions and view the contents of memory locations.

Additional Resources

A more comprehensive guide to GDB can be found here: Quick guide to GDB .

Linked Lists Exercises

In this lab, we will be using singly linked lists, very similar to the doubly linked lists in MP_LISTS. You will need to adjust insertFront to work for a singly linked list and implement clear.

Fixing insertFront

You can use the implementation of List<T>::insertFront from MP_LISTS as the basis. Make sure your inserted code works for a singly linked list!
To test this function, run these commands:
  make
  ./lab_gdb front

Testing insertFront Function

The output of the ./lab_gdb front will look like follows:
./lab_gdb front
[main]: testInsertFront()
.....
[testInsertFront]: size: 10
Copy and paste the missing (third) line in the box below:

Warning: You have not logged in. You cannot answer.

Testing clear Function

Before you fix the List<T>::clear function, please run the following commands:
make
valgrind ./lab_gdb front
Observe the output of the valgrind ./lab_gdb front. How many definitely lost bytes are reported in the LEAK SUMMARY of the output?
Type the number below:

Warning: You have not logged in. You cannot answer.

Fixing clear Function

Now, implement the List<T>::clear function in list.cpp. Make sure Valgrind does not report any memory leaks anymore.
Note: In order to test this function, insertFront must be working correctly!

GDB Exercises

The following exercises are designed to help you practice using GDB to navigate through code execution. Do these AFTER completing the insertFront function.

Print/Display

One of the most useful aspects of GDB is the ability to view variable values. In order to do that, you must stop code execution; here, we will use a breakpoint.
Compile the code and start GDB:
  make
  gdb lab_gdb
Insert a breakpoint in the print function in list_given.cpp.
  (gdb) break List::print
Run the command with the argument front.
  (gdb) run front
Display both the value of curr and the data held in that node:
  (gdb) display curr->data
  (gdb) display curr
Now, step through the code with the next command once:
  (gdb) next

Inspect the Output After Using next

Proceed with 'next' command until the terminal output looks something like this:
81		while (curr != NULL)
...
2: curr = (List::ListNode *) (memory_address)
Copy and paste the missing (second) line in the box below:

Warning: You have not logged in. You cannot answer.
Now you can keep stepping through the code until you see the node with a value that you are interested in, while taking note of the memory address given by the curr variable.

Backtrace

Another valuable command in GDB is backtrace. This shows you the function stack at the current execution time. We will use this to find out how many recursive calls it takes to get to a node with value 42 in the reverse function.
Note: This task may be done before fixing the bugs in reverse.
Compile the code and start GDB:
  make
  gdb lab_gdb
Insert a breakpoint in the reverse helper function in list.cpp. Type all of this in one line:
(gdb) break List::reverse(List::ListNode*, List::ListNode*, int)
Run the executable with the argument reverse.
  (gdb) run reverse
Condition the breakpoint to only stop if the current node has an alpha value of 42.
  (gdb) condition 1 curr->data.alpha == 42
Continue execution. The code should stop again at your breakpoint.
  (gdb) continue
Use backtrace to find the stack frame number of the first call to the reverse helper function!
  (gdb) backtrace

Inspect the Output After Using reverse

The output in your terminal should consist of multiple lines. Make sure you press Return to display all of the output. Once you reach the first call to reverse() helper function, please type the frame # in the box below.
Note: type only the number, no other special characters.

Warning: You have not logged in. You cannot answer.

Debugging the Rest of the Code

The most challenging part of the lab is still ahead, as you now must fix the remaining functions in list.cpp by detecting and correcting the logical errors in them. Successfully completing this task will require a keen eye for detail, diligent pointer tracing, and some GDB for debugging when necessary.
To make and run the code, type the following into your terminal:
  make
  ./lab_gdb

Bug 1: Fixing insertBack Function

As you can see, the code does not work! The first error is logical, the insertBack function does not seem to work properly. insertBack should walk to the end of the list and then add the new node there.
Try running the code with GDB to find out what's going wrong. Use the following commands to set up a helpful breakpoint.
  make
  gdb lab_gdb
  (gdb) break List::insertBack
  (gdb) run back
  (gdb) display this->length
  (gdb) display this->head
    
  // If head is not NULL
  (gdb) print this->head->data
You should see the code stop just before it starts to insert new nodes. Step through the code and watch how the length and head->data change. Once you have a good idea of what's going wrong, change a few lines of code and run the program again. If you've successfully fixed the bug, you can move on to bug number 2!
To test the insertBack function, run the following commands:
  make
  ./lab_gdb back
The correct output should look like this:
  ./lab_gdb back
  [main]: testInsertBack()
  [testInserts]: < 1 2 3 4 5 6 7 8 9 10 >
  [testInserts]: size: 10

Bug 2: Fixing reverse Function

Once you've fixed the first bug, you'll get a segfault. Running the code through GDB will identify the faulting line as in the reverse helper function. Usually, the first thing to do when you hit a segfault is to use backtrace. However, this is one example of a misleading stack trace. If you look closely, you'll see that this is not an instance of infinite recursion!
Walk through the code again with breakpoints, and watch how different variables change to fix the recursive reverse function.
Test the reverse function with the following commands: 
  make
  ./lab_gdb reverse
If you fixed the reverse function correctly, the images in reverse.png and soln_reverse.png should match.

Bug 3: Fixing shuffle Function

Only one more bug to go! This time, we've got another strange logical bug. The shuffle function should cut the deck (or list) in half, and then interleave the cards (or nodes). Again, this function is not working properly. Use GDB to step through the code and see what is broken.
Test the shuffle function with the following commands: 
  make
  ./lab_gdb shuffle
If you fix the function, the correct output of the shuffle should be: 
  ./lab_gdb shuffle
  [main]: testShuffle()
  [testShuffle]: before < 1 2 3 4 5 6 7 8 9 10 >
  [testShuffle]: after < 1 6 2 7 3 8 4 9 5 10 >

Submitting Your Work

GDB

Fix the bugs presented above and submit your code.

Allowed filenames: list.cpp

Warning: You have not logged in. You cannot answer.

Acknowledgments

We would like to express our gratitude to prof. Cinda Heeren and the student staff of the UIUC CS Data Structures course for creating and sharing the programming exercise materials that have served as the basis for the labs used in this course.
Revised by: Elmeri Uotila and Anna LaValle
?
API stands for Application Programming Interface. In the context of this course, you can consider the header files to be such interfaces, as they determine what class functions and properties are public and thus accessible from anywhere.
AddressSanitizer (ASAN) is a memory error detector for C/C++. In this course, the makefiles will typically compile an executable that uses ASAN, with "-asan" at the end of its name.
The two notable access specifiers are:
  • public: class members defined after the public keyword are accessible from outside the class.
  • private: class members are generally private by default and thus not accessible from the outside
Constructor is a special non-static member function of a class that is used to initialize objects of its class type. A constructor is called upon initialization of an object. A constructor without arguments is a default constructor, but constructors that take arguments can be defined.
GDB, the GNU Project debugger, allows you to see what is going on `inside' another program while it executes -- or what another program was doing at the moment it crashed.
GDB can do four main kinds of things (plus other things in support of these) to help you catch bugs in the act:
  • Start your program, specifying anything that might affect its behavior.
  • Make your program stop on specified conditions.
  • Examine what has happened, when your program has stopped.
  • Change things in your program, so you can experiment with correcting the effects of one bug and go on to learn about another.
GNU Make is a tool which controls the generation of executables and other non-source files of a program from the program's source files. Make gets its knowledge of how to build your program from a file called the makefile, which lists each of the non-source files and how to compute it from other files. When you write a program, you should write a makefile for it, so that it is possible to use Make to build and install the program.
Memory leak means that the program is not freeing up memory it reserves. The memory will be freed when the program terminates, but if a program keeps leaking more and more memory without terminating, it can become a huge issue!
A typical way for memory leaks to occur is reserving memory with new and not calling delete before the pointer goes out of scope.
Pointer variables store a memory address as their value. In other words, they point to some data. The data can be accessed by dereferencing the pointer. (Either like *p or p->...)
A recursive function calls itself from within it. The recursion call must be conditional or it would lead to an infinite loop.
Valgrind is another tool besides ASAN that you can use in this course. It can detect many memory-related errors that are common in C and C++ programs and that can lead to crashes and unpredictable behaviour.
const is a keyword meant to mark something as immutable
  • A const object cannot be modified: attempt to do so directly is a compile-time error, and attempt to do so indirectly (e.g., by modifying the const object through a reference or pointer to non-const type) results in undefined behavior.
  • const keyword on an object's member function prevents the object from being modified in the function
  • Pointer declarations can have 2 const keywords, one to make the data that's pointed at unable to be modified and one to make the pointer itself unable to be modified
Using const improves code readability and prevents accidental modification of objects.
g++ is a C++ compiler that we primarily use for this course. It is the C++ compiler for the GNU compiler collection. You may sometimes see gcc being used instead of g++, which was originally the GNU C compiler, but calling gcc generally also compiles .cpp files as C++. However, calling g++ is preferred.
In C++, std stands for Standard Library, which is a collection of commonly useful classes and functions. Typically, these are defined in the std namespace.