Course & Instructor Info

Course Name: CSE 4650 - Systems Programming Lab

Instructor: Imtiaj Ahmed Chowdhury, Lecturer, CSE, IUT
Lab Courtesy: CS300 - Fundamentals of Computer Systems (Brown University), adapted under CC BY
4.0

Lab 2 - Debugging
Submission
After you complete each task in the assignment, commit and push them to the respective lab folder
within your CS300 github repo. Make sure to complete all the tasks within the lab container. In the
commit message before your push , add the message "Completed Task X" where X is the task number.
You should complete the tasks in order by going through each section sequentially.
All of your commits must be made before the assignment deadline mentioned in the Google
Classroom. If there're any commits made after the assignment deadline, your marks will be deducted.
So make sure to complete the tasks and commit them before the deadline.
In the Google Classroom assignment, you have to submit 3 screenshots after you have run and tested
the given tasks. The required screenshots are mentioned in the Running and Testing section of
respective assignment parts.
Complete all the steps before deadline. Any delay will be heavily penalized.

Assignment
Setup
Start with the cs300-s23-labs-YOURNAME repository you used in Lab 1. As always, you need to do all these
steps inside your container. So, run your container first, attach to it from inside VS Code and use the VS Code
terminal.

Now, cd into the directory of cloned repo and ensure that your repository has a handout remote. Type:

bash
1 $ git remote show handout

If this reports an error, run:

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

Then run:

$ git pull
$ git pull handout main
This will merge the 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.

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 ( lab 2 ), 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.
Watch this video to get a walk through of how to debug a sample program:
https://youtu.be/8kU35Rbquzc. Also, If you have any questions while debugging, we suggest checking
out this GDB guide.

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 .
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 ).

Available functions

/**
* 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

Running ./linked_list all will run all the tests. It'll test the already-implemented functions (that may have
bugs), and the additional functions implemented by you.
Running ./linked_list existing will run only the already implemented functions. You should run this
command for the first part of the lab.
Running ./linked_list student will only run the tests that test the functions that you will 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 (same as ./linked_list all ,
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!

Compile your code (using make ) and run the command
 $ ./linked_list existing

to run the tests.

Note: You might get some warnings from the compiler initially, you can ignore these, because there are some
functions that are not yet implemented.
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.
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?
Hint: remember that within the fields of the node struct, we have a pointer to the next element in the linked
list. We can do something like current = current->next .

Task 1

Correct the length_list function.

Once you have made that change, now you can see that the program no longer hangs, but it now 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.
 Task 2

Correct the get_first function.

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 0x55b8b841fce9 bp

0x7ffc2b6344f0 sp 0x7ffc2b6344e0

We can see that there was a heap-use-after-free, meaning that you are trying to access memory
previously allocated on the heap that 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 238
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 236 in linked_list.c .

previously allocated by thread T0 here

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

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?

Task 3
 Correct the remove_first function.
Hint: You should copy the data being removed/freed to somewhere else.

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!

Task 4

Correct the remaining implemented linked list functions so that all of the tests pass without any sanitizer
warnings. When you fix a function to remove a bug, there should be a comment beside the
modified lines explaining what you fixed.

Hint 1: You will not have to change the logic or general algorithm of any function – the changes that you
make to the implementation of the functions will be minimal. However, bugs may well be located in
functions other than the one that causes a crash!
Hint 2: There are 3 more functions which need fixing :)

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!”. Take a screenshot of this
message and upload in Google Classroom assignment.

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
You will be writing three functions in the file linked_list.c in Tasks 5, 6 & 7.

Task 5

get
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);

 Task 6

insert_first
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);

Task 7

remove_last
Given a double pointer to the first element in the list, this function will remove the last node and return
the void* of the element removed.

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

Hint: The test suite relies on using assert statements. If an assert statement fails, take a look at the
function call within the assert statement or the call to a linked list function above the assert statement and
set a breakpoint either at that line number or on that function.

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. Take screenshots of these
two messages and upload in Google Classroom assignment.