« Back to the main CS 300 website

Lab 2: Debugging

Due February 15, 2022, at 8:00PM EST

Assignment

Assignment Installation

First, ensure that your repository has a handout remote. Type:

$ git remote show handout

If this reports an error, run:

$ git remote add handout https://github.com/csci0300/cs300-s22-labs.git

Then run:

$ git pull
$ git pull handout master

This will merge our Lab 2 stencil code with your previous work. If you have any “conflicts” from Lab 1, resolve them before continuing further. Run git push to save your work back to your personal repository.

Assignment Overview

The purpose of this lab is to introduce to you a handy tool to debug C (and C++) programs called GDB (GNU debugger). You will be debugging a partially implemented linked list program with some of the most commonly encountered bugs in systems programming. After debugging, you will write a couple of linked list functions.

After you have set up the lab, within your lab folder, you should find the following files:

• linked_list.c
• linked_list.h
• linked_list_test.c

Using GDB

As with many other programming languages, in C, programmers frequently make use of print statements to look at the state of their program (you may have done this in the last lab by using printf). Often you may wish, however, that you could stop your program right before executing a line of code or a function and interactively inspect its state! This is what debugger tools like GDB are for.

As explained on the GNU website, GDB can do four main things (plus other things) to help you catch bugs in the act:

1. Start your program, specifying anything that might affect its behavior.
2. Make your program stop on specified conditions.
3. Examine what has happened, when your program has stopped.
4. Change things in your program, so you can experiment with correcting the effects of one bug and go on to learn about another.

Here is a quick video walking through how to debug a sample program:

If you have any questions while debugging, we suggest checking out the GDB guide that we compiled. As always, feel free to ask on EdStem if you have questions not answered there!

Linked List

In this part of the assignment, you will be debugging a doubly-linked list program. In the file linked_list.c, you can find the implementation of some common doubly-linked list functions (you will be implementing some functions in the next part of the lab). And in the file, linked_list_tests.c, you can find tests testing the functions.

This doubly-linked list is not circular. This means that the first element in the doubly-linked list has a previous pointer that is NULL, and the last element in the list has a NULL next pointer. If you had a linked list with a single element, its previous and next pointer would both be NULL.

The nodes of the list are represented by circles, and we have a node variable that indicates the start or head of the list. Each node is represented by a struct node_t, which has three members, a void* pointer for its data, a previous pointer, and a next pointer (you can find the definition in linked_list.h).

/**
 * Returns the number of nodes in the linked list given a pointer to
 * the first element in the linked list. 
 */
int length_list(node_t* head_list); 

/**
 * Returns the void* value of the first element in the linked list. 
 */ 
void* get_first(node_t* head_list); 

/**
 * Returns the void* value of the last element in the linked list. 
 */ 
void* get_last(node_t* head_list); 

/**
 * Given a double pointer to the first element in the list, a void* 
 * of the value to be added, and the size of the element to be added, 
 * this function will create a new node and add it to the front of the 
 * list. 
 */ 
void insert_first(node_t** head_list, void* to_add, size_t size); 

/**
* Given a double pointer to the first element in the list, a void* 
 * of the value to be added, and the size of the element to be added, 
 * this function will create a new node and add it to the end of the 
 * list.
 */ 
void insert_last(node_t** head_list, void* to_add, size_t size); 

/**
 * Given a pointer to the first element of the linked list, return the void*
 * value at the index value. The linked list is zero indexed. 
 */ 
void* get(node_t* head_list, int index); 

/**
 * Given a double pointer to the first element in the list, a void* of
 * the value to be removed, and the size of the element, this function 
 * will delete the node with the value of to_remove. 
 */ 
int remove_element(node_t** head_list, void* to_remove, size_t size); 

/**
 * Given a double pointer to the first element of the list, reverses
 * the linked list in place. 
 */ 
void reverse(node_t** head_list); 

/**
 * Given a double pointer to the first element in the list, this function will
 * remove the first node. 
 */ 
void* remove_first(node_t** head_list) 

/**
 * Given a double pointer to the first element in the list, this function
 * will remove the last node. 
 */ 
void* remove_last(node_t** head_list); 

Compile, Run, and Test

The Makefile

The Makefile provided already includes the -g flag to enable debugging information.

If you run make or make clean all or make all, it will compile your code and produce an executable called linked_list.

Review lab 1 if you need a refresher on Makefiles.

Testing your work

Run ./linked_list all will run all the tests, including the already-implemented functions (that may have bugs), and the tests testing your implementation of additional functions.

Run ./linked_list existing will run only the already implemented functions. You should run this command for the first part of the lab.

Run ./linked_list student will only run the tests that test the functions that you write. You should run this command for the second part of the lab.

Or, you can run make check, which will compile your code and run all the tests (both existing implementations and student implementations).

Assignment Part I: Debugging a Linked List

Introduction

We have written functions length_list, get_first, get_last, insert_last, remove_element, reverse, and remove_first for you. But, some of these implementations are incorrect and buggy! In this part of the lab, your task is to debug and fix these implementations.

Let’s start debugging!

$ ./linked_list existing

You can see that running this program causes the program to hang. You can stop execution with Ctrl-C. To debug this, because we aren’t sure where it’s coming from, we can run the program in GDB and backtrace to find out which function is causing this.

$ gdb linked_list # run gdb on the existing executable 
(gdb) r existing # this will run the program within the debugger

We can see that the program hangs in GDB; we can then use Ctrl-C to interrupt execution.

$ (gdb) bt # this will print out a stack trace 

And we are currently in the function length_list, which is found in linked_list.c. We can set a breakpoint at length_list to monitor execution.

(gdb) b length_list 

And we can step through the execution of the function by using the n command, and you can print out the value of current and its fields by doing

(gdb) p current->data 

or

(gdb) p current->next

And we see that in the while loop that it increments the variable length, and it goes to the next iteration and checks to see if current is not NULL, but it never updates the value of current to iterate to the next node in the linked list! Why might be this be a problem? And how might we change this so that we can update current to be the next node?

Once you have made that change, now you can see that the program no longer hangs, but it has causes a segmentation fault. To debug this segmentation fault, we can do something similar as the last bug, in which we first run the program in GDB and run a stack backtrace (bt) to see where the segmentation fault is coming from. From doing so, we can see that it’s from the function get_first. We now know where to set the breakpoint. We can then rerun the program and step through the execution of get_first. We can print the value of head_list, which turns out to be NULL or 0x0. In short, we are trying to dereference a NULL pointer and to access its fields. If the linked list is empty, you would want to return NULL to indicate that there isn’t a first element.

The next couple of bugs will be a lot easier to find if you have address sanitizers enabled. To do so, edit the Makefile to include the -fsanitize=address flag. As a review, address sanitizers can detect bugs such as out-of-bounds access to heap and stack, global variables, and dangling pointers (using a pointer after the object being pointed to is freed). In practice, this flag also adds another sanitizer, the LeakSanitizer, which detects memory leaks.

As you can see, now running the linked_list program yields and address sanitizer error message. It can be overwhelming at first, but the error message offers a lot of helpful debugging information. Let’s break it down!

ERROR: AddressSanitizer: heap-use-after-free on address 0x603000000010 at pc 0x560b7a7df56d bp 0x7ffc4cdc0a80 sp 0x7ffc4cdc0a70

We can see that there was a heap-use-after-free, meaning that you are trying to access memory previously allocated on the heap (and has since been freed).

READ of size 8 at 0x603000000010 thread T0

This tells us that it was a read access (as opposed to a write access) to this address of 8 bytes, and it gives a stack trace, of which we can see that that this read happens in remove_first on line 211 in linked_list.c.

0x603000000010 is located 0 bytes inside of 24-byte region [0x603000000010,0x603000000028)
freed by thread T0 here

This part of the message tells us that this address that you tried to access was located in a 24 byte region from the heap address 0x603000000010 to 0x603000000028 (non inclusive) which was freed in the function remove_first on line 209 in linked_list.c.

previously allocated by thread T0 here

And this region was allocated in the function test_linked_list on line 99.

Because we know that this use after free error is happening in remove_first, we can take a look at the remove_first function. As you can see we free curr->data and curr, but we still return curr->data even though it’s been freed. How might we get around this issue?

Use GDB (make sure to check out this guide for helpful commands) and the address sanitizer to help you find the next couple of bugs. Once all the tests pass without any issues and warnings from the address sanitizer, you are ready to move on!

Running and Testing

When you have found and fixed all the bugs, after running the command

./linked_list existing 

you should see a printed message with “ALL EXISTING TESTS PASSED!”.

Assignment Part II: Implementing Linked List Functions

Introduction

In this part of the lab, you will be writing some linked list functions to become more familiar with coding with pointers and structs.

Assignment Specifications

/**
 * Given a pointer to the first element of the linked list,
 * return the void* value at the index value.
 * The linked list is zero indexed. 
 */ 
void* get(node_t* head_list, int index); 

/**
 * Given a double pointer to the first element in the list, a void* 
 * of the value to be added, and the size of the element to be added, 
 * this function will create a new node and add it to the front of the 
 * list. 
 */ 
void insert_first(node_t** head_list, void* to_add, size_t size); 

/**
 * Given a double pointer to the first element in the list, this function
 * will remove the last node. 
 */ 
void* remove_last(node_t** head_list); 

Running and Testing

Once you are done writing the functions, you will now be able to run the full test suite by running make check or compiling and then running:

$ ./linked_list all

Or, if you just want to run the tests for your new functions’ implementation, you can compile your code and run:

$ ./linked_list student

Use GDB and the address sanitizer to debug your implementation. You should see “ALL TESTS PASSED!” if you run all (both existing and student) tests, and if you just run the student tests, you should see “ALL STUDENT TESTS PASSED!” once you have successfully implemented the linked list functions.

Handin instructions

Turn in your code by pushing your git repository to csci0300-s22-labs-YOURUSERNAME.git.

Then, head to the grading server. On the “Labs” page, use the “Lab 2 checkoff” button to check off your lab.