CS 3410 Fall 2018
Due: Make sure you understand each of the bugs, how to use GDB, and the string parsing from the lab. Credit will be given by attendance.
git pull in your CS 3410 Github repository.
Before we start with GDB, we need to create some test cases to try out our selection sort on. In the main function try creating some long arrays to test your selection_sort on. Ignore any file parsing code that is already there. Assuming our selection_sort is correct, compiling and executing the selection_sort on some long array should result in a completely sorted array. For example, try initializing the following array and running selection_sort on it:
long arr[5] = {1, 4, 2, 0, 3};
selection_sort(arr, 5);
** Note: The implementation of selection sort takes in an array of longs, not integers, so make sure to create your array with longs. Longs are a data type in C which have at least 32 bits. Most computers today represent longs with 64 bits, giving you the ability to represent bigger numbers easily.
In previous labs, we simply compiled the code, and ran it. Let's do this, hoping that that our code compiles and runs properly.
In order to compile buggy_sel_sort.c type
gcc -std=c99 -Wall -Werror buggy_sel_sort.c -o lab10. Usually to run the executable, you would type
./lab10. But this program takes the file data.txt as the first argument. So you would run the executable with:
./lab10 "data.txt" (Our gcc command included
-o lab10, which makes the program name in this case
lab10).
Oh snap! It doesn't work, it segfaulted! A segfault occurs when your program tries to access memory, either by reading or writing, which it is not allowed to. Let's use GDB to find out where this occurs.
Note: the first thing you should do is comment out the file parsing code in the main() function. Otherwise gdb will complain.
This time, compile the
buggy_sel_sort.c file with the
-g flag. This flag will add debugging symbols to the executable that will allow GDB to debug much more effectively. Do
this by running
gcc -g -std=c99 -Wall -Werror buggy_sel_sort.c -o lab10.
To begin debug with GDB type
gdb lab10. This will present you with the GDB Prompt.
To run your executable in GDB, type run. This command runs your program until a breakpoint or crash is encountered. You can also pause your program by pressing Control-C (useful for finding infinite loops). When one of these is encountered, you will be able to inspect the state of your program with any of the following commands.
When GDB reaches an error it will only tell you the line of code that it fails on. In order to see the whole backtrace, the
whole set of stack frames associated with the file at the time, type
backtrace. Use this to find the function that called the function that failed.
buggy_sel_sort.c:linenumber tells you the file and line number that the error occured it.
You should also see multiple lines that look like
swap (a=0x3, b=0x1) at buggy_sel_sort.c:29 which tell you the function, the line number, and its arguments, indicating that the function call occured.
Alternatively we can see the value of
a using the command
print a. This prints the value of expression or variable
a at the current line of execution.
Is something wrong with
a? In your text file, in the section called Bug 1:, explain the problem with
a's value, and what it should actually be. Then fix this bug in the file, and test that it doesn't segfault.
If we want to stop and see what is going on at a particular point in our program, we can use breakpoints. To do this in GDB, type break buggy_sel_sort.c:41, to set a breakpoint on line 41 of file buggy_sel_sort.c. To execute line by line from this point, we can step. Step executes one line of code, and will move into a function if that line is a function. next will execute one line of the current function, without stepping into other function calls.
If given:
functionB() {
int j = 2;
int k = 3;
return k;
}
functionA() {
int i = functionB();
return i;
}
If we are at line
int i = functionB(); , step will go to
int j = 2; whereas next will move to
return i;
Type next to progress to the next line, and type print swap_idx to look at its value. Type continue to go to the next time the breakpoint is hit, which will be the next iteration of the loop.
Notice how the value of swap_idx doesn't reflect that actual value that it should be. Continue using gdb to step through
the code until you know what the bug is, and fix the bug.
Is something wrong with swap_idx? In your text file, in the section called Bug 2:, explain the problem with swap_idx's value,
and what it should actually be in the code. After fixing the bug, test that the error doesn't appear again.
Using your newly acquired gdb debugging skills, use a combination of the gdb commands you've learned thus far to find and
fix the last bug. In your text file, in the section called Bug 3:, explain the bug, and fix it.
char *str. Strings
are delimited by the null character
\0 in an array. Therefore, string arrays are actually
char **arr, which is an array of character arrays. Keep in mind that you can instantiate a string in the following way:
char string[] = "dolphin";In the source files for this lab there is some information about what functions would be helpful for basic string parsing.
These functions are all defined in the
"string.h" library. Remember to check the man pages for these functions if their definitions or uses are confusing.
Note, specifically for students using strsep: You must pass an additional flag into gcc, namely -D_DEFAULT_SOURCE, otherwise gcc may not know how to find strsep.
In your lab10 directory there is a file called data.txt. This file contains an association list of letters to their correspondign indicies in the alphabet, indexed at 1. The file reading code that was given in function main reads the first 200 bytes of an input file and builds a character array holding all of the characters from the read in string. The read in string, is entered into char buff[200]. Your job in Part 5 is to take the string in buff[200] and by using string parsing functions (mentioned in the source code comments) build a long array with the number values in order. Ex. if char buff[200] = "a:1,b:2,d:4,c:3"; then we would need to parse the characters of the buffer and build the following array: long arr[4] = {1,2,4,3};. Our string parsing code should be generic and should accept any association string, where each key:value is of form "string:long".
Test your solution by sorting and printing the resultant long array after parsing the string. A working solution will look like this: printf("data.txt:%s\n", buff); should print out data.txt. After converting the string to a long array: print_array(long_arr, long_arr_length); should print out all of the letter indicies in order of where they are in "data.txt". And after sorting: print_array(selection_sort(long_arr, long_arr_len), long_arr_len); should print out a sorted long array with the numbers 1 through 26.
Be sure to demonstrate to your TA that you understand all the bugs in the code and the string library methods you are using by explaining your text file and source code.