<style> summary { //font-weight: bolder; } summary:hover { text-decoration: underline; } blockquote { font-size: 16px; } .todo { color: #ff00ff; border: 2px dashed #ff00ff; padding: 0em 1em; border-radius: 5px; margin-top: 1em; margin-bottom: 1em; //display: none; // UNCOMMENT TO HIDE TODOs } </style> **[&laquo; Back to the main CS 300 website](https://csci0300.github.io/)** # Lab 2: Debugging ### Due Tuesday, February 11th at 8:00 PM EST --- # Assignment ## Assignment Installation First, ensure that your repository has a `handout` remote. Type: ```bash $ git remote show handout ``` If this reports an error, run: ```bash $ git remote add handout https://github.com/csci0300/cs300-s25-labs.git ``` Then run: ```bash $ git pull $ git pull handout main ``` 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](https://www.gnu.org/software/gdb/), 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](https://youtu.be/8kU35Rbquzc) walking through how to debug a sample program: {%youtube 8kU35Rbquzc %} If you have any questions while debugging, we suggest checking out the [GDB guide](https://docs.google.com/document/d/15tqnbCcs3QH-vPzYbJNJOgZm1PQfZywp4gf2o5wey34/preview?usp=sharing) 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`. 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`). ::::info <details> > ```c! /** * 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); ``` > ```c! /** * Returns the void* value of the first element in the linked list. */ void* get_first(node_t* head_list); ``` > ```c! /** * Returns the void* value of the last element in the linked list. */ void* get_last(node_t* head_list); ``` > ```c! /** * 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); ``` > ```c! /** * 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); ``` > ```c! /** * 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); ``` > ```c! /** * 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); ``` > ```c! /** * Given a double pointer to the first element of the list, reverses * the linked list in place. */ void reverse(node_t** head_list); ``` > ```c! /** * 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) ``` > ```c! /** * 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); ``` </details> :::: ## 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! :::success **Task**: Compile your code and run the command ```bash $ ./linked_list existing ``` to run the tests. Figure out and fix the issues that arise using GDB. **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. ```bash $ 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. ```bash $ (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. ```bash (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 ```bash (gdb) p current->data ``` or ```bash (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? :::info **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`. ::: :::success **Task:** 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. :::success **Task:** 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!  <span style="color:#b42419">**ERROR: AddressSanitizer: heap-use-after-free on address 0x603000000010 at pc 0x560b7a7df56d bp 0x7ffc4cdc0a80 sp 0x7ffc4cdc0a70**</span> > 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. <span style="color:#400bd9">**READ of size 8 at 0x603000000010 thread T0** </span> > 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`. <span style="color:#2fb41d">**0x603000000010 is located 0 bytes inside of 24-byte region [0x603000000010,0x603000000028)**</span> <span style="color:#c814c9">**freed by thread T0 here**</span> > 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`. <span style="color:#c814c9">**previously allocated by thread T0 here**</span> > 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? :::success **Task:** Correct the `remove_first` function. ::: Use GDB (make sure to check out this [guide](https://docs.google.com/document/d/15tqnbCcs3QH-vPzYbJNJOgZm1PQfZywp4gf2o5wey34/preview?usp=sharing) 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! :::success **Task:** Correct the remaining implemented linked list functions so that all of the tests pass without any sanitizer warnings. \ **Hint:** 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! Typically, the buggy code is located somewhere before the error is raised rather than at the erroring line. ::: ### Running and Testing When you have found and fixed all the bugs, after running the command ```bash ./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 :::success **Task:** you will be writing three functions in the file `linked_list.c`: 1. `get` ```c! /** * 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); ``` 3. `insert_first` ```c! /** * 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); ``` 5. `remove_last` ```c! /** * 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: ```bash $ ./linked_list all ``` Or, if you just want to run the tests for your new functions' implementation, you can compile your code and run: ``` bash $ ./linked_list student ``` :::info **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. # Handin instructions Turn in your code by pushing your git repository to `csci0300-s25-labs-YOURUSERNAME.git`. Then, head to the [grading server](https://cs300.cs.brown.edu/grade/2025). On the "Labs" page, use the **"Lab 2 checkoff"** button to check off your lab.