<style> summary { //font-weight: bolder; } summary:hover { text-decoration: underline; } blockquote { font-size: 16px; } section { padding: 0em 1em; padding-bottom: 1em; padding-top: 1em; border-radius: 4px; background-color: #f7f7f7; border: 1px solid #ccc; } .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, September 23 at 8:00 PM~~ **extended to Wednesday, September 24 at 8:00 PM** :::success **Update (9/19)**: Please see **[this Ed post](https://edstem.org/us/courses/83443/discussion/6985356)** for some important information about working with structs in C, which should be helpful as you get started on this lab! ::: --- # Assignment ## Assignment Installation Start with the `cs300-f25-labs-YOURNAME` repository you used for Lab 0. You likely would have cloned this to a folder called `labs` inside your container. First, open a terminal in your container environment and `cd` into your `labs` folder, then 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-f25-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. :::warning **You may get a warning about "divergent branches"** like shown below:  This means you need to set your Git configuration to merge our code by default. To do so, run (within the same directory in your labs repository workspace): ```console $ git config pull.rebase false $ git pull handout main ``` ::: :::danger **If your terminal window changes to something like this**:  <details> <summary><b>Expand for instructions</b> </summary> Your terminal has asked you to add a commit message to explain what code was merged in, and opened a text editor so you can write the message. The top line is a default message, which you can use as-is. To use the message and finish the commit, do the following: - **If your terminal looks like the image above**, press `Ctrl+s` to save, then `Ctrl+q` to quit. (These are shortcuts for the text editor `micro`, which is the program that is running now) - **If your terminal instead has a bar at the top that says `GNU nano`**, you are using a text editor called `nano`. To save your commit and exit, press `Ctrl+x`, then press `y`, and then press `Enter`. </details> ::: ## 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 %} :::info **Hint: If you want to print a `void*` variable in GDB you may need to cast it first.** ::: 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 ll_length(node_t* head_list); ``` > ```c! /** * Returns the void* value of the first element in the linked list. */ void* ll_get_first(node_t* head_list); ``` > ```c! /** * Returns the void* value of the last element in the linked list. */ void* ll_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 ll_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 ll_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* ll_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. * Returns NULL on error. */ int ll_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 ll_reverse(node_t** head_list); ``` > ```c! /** * Given a double pointer to the first element in the list, this function * will remove the first node. * * Returns: pointer to the element removed; NULL if the list is empty */ void* ll_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. * * Returns: pointer to the element removed; NULL if the list is empty */ void* ll_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 `ll_length`, `ll_get_first`, `ll_get_last`, `ll_insert_last`, `ll_remove_element`, `ll_reverse`, and `ll_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. ::: When running the program, you will notice that it hangs--this is a bug! To stop execution, press **Ctrl-C**, which is a standard signal to use in your terminal (or in GDB) to ask the current program to stop. Since we aren't sure where the bug is coming from, we can run the program in GDB and backtrace to find out which function is causing the program to hang. Here's how : ```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; then, press **Ctrl-C** to interrupt execution. ```bash $ (gdb) bt # this will print out a stack trace ``` And we are currently in the function `ll_length`, which is found in `linked_list.c`. We can set a breakpoint at `ll_length` to monitor execution. ```bash (gdb) b ll_length ``` 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. How can we update which node we are currently looking at? ::: :::success **Task:** Correct the `ll_length` 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 `ll_get_first`. We now know where to set the breakpoint. We can then rerun the program and step through the execution of `ll_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 `ll_get_first` function. ::: ## Debugging with sanitizers 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. :::success **Task**: Update your `Makefile` to turn on sanitizers by adding the flag `-fsanitize=address` to the compilation flags. Then, rebuild the program by running `make clean`, followed by `make`, and run the program again. Once you re-run the program, you should now see a sanitizer error, which we'll break down in the next section! ::: <section> #### Deconstructing a sanitizer error 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 `ll_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 `ll_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. **Putting it all together**: Because we know that this use after free error is happening in `ll_remove_first`, we can take a look at the `ll_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? </section> <br /> :::success **Task:** Based on what you learned from the sanitizer error, correct the `ll_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, keep in mind that **bugs may 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. `ll_get` ```c! /** * ll_get: gets an element from the linked list, given its index. If * the index is negative or invalid (i.e., out ot bounds), this * function should return NULL. * * Arguments: * - head_list: pointer to the head of the list * - index: Index to get * * Returns: pointer to element of the list given by index, NULL if * index is invalid */ void* ll_get(node_t* head_list, int index); ``` 3. `ll_insert_first` ```c! /** * ll_insert_first: Insert a new element at the beginning of the list * * Warning: the user of this function is responsible for making sure that * the data for the list element remains valid while it is in the * list. If the data is freed or goes out of scope while the list * still refers to it, this will result in undefined behavior! * * Arguments: * - head_list: Pointer to a pointer that refers to the head node of the list * - to_add: void pointer representing data to be added * * Returns: nothing */ void ll_insert_first(node_t** head_list, void* to_add); ``` 5. `ll_remove_last` ```c! /** * ll_remove_last: Remove the last element of the list, given a * pointer to the head of the list * * Returns: pointer to the element removed; NULL if the list is empty */ void* ll_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-f25-labs-YOURUSERNAME.git`. Then, head to the [grading server](https://cs300.cs.brown.edu/grade/f25). On the "Labs" page, use the **"Lab 2 checkoff"** button to check off your lab.