\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage[a4paper, margin=0.75in]{geometry}

% set up hyperlink coloring
\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,
    urlcolor=cyan
}

\setlength{\parindent}{0pt} % no indentation

\renewcommand{\familydefault}{\sfdefault} % default to sans serif

% code support: listings and fancy verbatim
\usepackage{listings}
\lstset{basicstyle=\ttfamily\footnotesize}
\usepackage{fancyvrb}

\renewcommand{\familydefault}{\sfdefault} % default to sans serif

\usepackage{xcolor}
\newcommand{\code}[1]{\colorbox{lightgray}{\texttt{#1}}}
\newcommand{\prompt}[1]{\code{\$ #1}}
\newcommand{\gdb}[1]{\code{(gdb) #1}}

%%%%%%%%%%%%%%%%
\begin{document}

\title{Homework 8\\Debugging}
\author{EECS 201 Winter 2020}
\date{}
\maketitle

\section*{Submission Instructions}
This homework will be submitted as a repository on the UMich GitLab server.
The repository you submit will be a \textbf{private} project called \code{eecs201-hw8}.

\section*{Preface}
In this homework you'll be provided yet another zipped archive containing some starter files.

\begin{Verbatim}[fontsize=\footnotesize]
  curl -O https://www.eecs.umich.edu/courses/eecs201/files/assignments/hw8-files.tar.gz
  tar xzf hw8-files.tar.gz
  cd hw8-files
\end{Verbatim}

Initialize a Git repository in the extracted \code{hw8-files} directory.
Create a file called \code{REPORT} in this directory.
Add all of the present files and commit them.
\\\\
Create a \textbf{private} project named \code{eecs201-hw8} on the UMich GitLab (\url{gitlab.umich.edu})
and add the instructor \code{brng} as a \textbf{Reporter}.
Set this UMich GitLab project as your remote: you'll be pushing to it in order to submit.
\\\\
For this assignment you're going to need GDB and Valgrind.
The package names for Ubuntu are \code{gdb} and \code{valgrind}.
If you haven't already installed \code{g++}, the GNU C++ compiler,
you can install the \code{g++} package.

\section{Debugging with GDB}
\begin{enumerate}
  \item \code{cd} into the \code{1} directory.
  \item Use \code{make} to build the \code{seqmean} program.
        What this program does is take the average of a sequence
        of integers from 1 to \textit{n}, where \textit{n} is an
        argument.
  \item Run \prompt{./seqmean 3}. Note that a segfault occurs.
  \item Run \prompt{gdb seqmean}. You will be prompted by GDB.
  \item Look at the line above the prompt: notice how it mentions
        that there are no debugging symbols.
        Debugging symbols are what GDB uses to be able to have
        a sense of what code "lines" and other things are.
  \item Let's get some debugging symbols: exit GDB with \gdb{quit} or \gdb{q}.
  \item Open the \code{Makefile} in an editor.
        Set the \code{CFLAGS} variable so that it contains \code{-g}.
        The \code{-g} flag will cause \code{gcc} to compile with debugging symbols.
  \item Use \code{make} to clean and rebuild the program, and then open the program in GDB again.
  \item To run the program, run \gdb{run 3} or \gdb{r 3}.
  \item GDB will catch the program at the segfault,
        allowing us to investigate the state of the program.
        It's kind enough to tell us what line of what file it happened at.
  \item With \gdb{backtrace} or \gdb{bt} (or \gdb{where}) we
        can get a backtrace, which shows the function calls and
        their stack frames that lead up to the current place.
        Frame \#0 represents the current function and
        frame \#1 represents the caller of that function
        (and frame \#2 would be its caller and so on).
  \item \gdb{frame} or \gdb{f} will show the current frame
        and the line of code it's at.
  \item Segfaults ("segmentation faults") come about due to accessing
        memory that doesn't ``exist'' (or unmapped for you OS folks ;))
        or if there is a permission access violation (e.g. writing to a read-only spot).
        In this line, the only operation that performs a risky memory
        operation is the struct pointer member access operation (\code{->}).
  \item That operation looks risky: let's print out the value of 
        the pointer variable (which is the argument of the function):
        \gdb{print d} or \gdb{p d}.
        (Note: \gdb{frame} also shows the arguments
        and their values that passed into the function).
  \item Note that the value of \code{d} is \code{0x0}, a null pointer.
        Null pointer dereferences are some common ways a segfault can happen.
        But where did it come from? Look at your backtrace again.
  \item Let's switch to the frame of the calling function:
        run \gdb{frame 1} to investigate it.
  \item \code{frame} conveniently prints out the line of code:
        we can see that at line 31 of \code{main.c},
        a \code{NULL} (i.e. null pointer) is passed into
        the function instead of a pointer to a \code{data} structure.
  \item Now that we've identified the bug, let's fix it.
        Exit GDB and open \code{main.c} for editing.
        Fix line 31 so that \code{data\_calc\_stats} takes
        in a pointer to the \code{d} variable, which is
        an instance of the \code{data} structure.
  \item Rebuild the program and run \prompt{./seqmean 3} again.
        There should not be a segfault this time.
  \item Add and commit the \code{main.c} file.
\end{enumerate}

Note how the result is incorrect:
\(\frac{1 + 2 + 3}{3}\) should equal $2$, not $1$.
Let's figure out what's wrong and fix the bug.
\begin{enumerate}
  \item Open the program in GDB again, and run \gdb{run 3} or \gdb{r 3}.
  \item You'll see that GDB will run the program to completion.
        GDB will remember the arguments you pass along with the run:
        \gdb{run} will cause it to run with \code{3} as the argument again.
  \item It's not particularly interesting if it runs to completion.
        Let's set a breakpoint at \code{main()} to have it stop there:
        Run \gdb{break main} or \gdb{b main}.
        You can list out the breakpoints with
        \gdb{info breakpoint} or \gdb{info b}.
  \item Run the program again. It should stop at \code{main()}.
  \item Let step through the code: run \gdb{next} or \gdb{n}
        to step over a line.
  \item Hit Enter/Return without typing out any command.
        Entering an empty command will run the previously
        entered command.
  \item Place a breakpoint at line 31 with \gdb{break 31} or \gdb{b 31}.
        Implicitly, without specifying a file,
        the current file that the current line is in will be referred
        to when it comes to line numbers and function names.
        \gdb{break main.c:31} and \gdb{break main.c:main} are
        examples of explicitly referring to a file.
  \item Continue execution with \gdb{continue} or \gdb{c}.
  \item This is line that calls the function that calculates the mean.
        Step \textit{into} the function with \gdb{step} or \gdb{s}.
  \item Let's see if the sum is calculated properly: place a breakpoint
        at line 24. Continue so that this breakpoint gets triggered.
  \item Print out the \code{sum} variable. It's 3! $1 + 2 + 3 \neq 3$!
  \item That's curious: maybe the data was bad. Let's investigate
        the \code{buffer} member of \code{d}:
        try \gdb{p d->buffer}.
  \item Unsurprisingly, GDB prints out the actual pointer value that
        \code{buffer} holds. We can dereference it: \gdb{p *d->buffer}.
  \item Well, that gives us only the 0th element.
        We can get \gdb{print} to give us elements after it as well:
        \gdb{p *d->buffer@3} (or if we're being really fancy
        \gdb{p *d->buffer@d->size}).
  \item Now we can see the issue. The buffer should
        be a sequence of 3 integers starting at 1, not 0:
        the buffer's contents should be \code{\{1, 2, 3\}}.
  \item I'll let you figure out the fix for this :)
        Investigate the C source and header files,
        and take advantage of whatever debugging knowledge you have.
  \item When you're done with the fix, add and commit the files
        associated with the fix.
\end{enumerate}

\section{Finding memory issues with Valgrind}
\begin{enumerate}
  \item \code{cd} into the \code{2} directory.
  \item Build and run the program.
        You should see \code{n = 5} and \code{0.2 0.4 0.6 0.4 0.2}.
        (Some people's systems may result in a segfault; we'll deal with it soon :) ).
  \item While it may be functionally correct, there may be bad memory usage
        lurking about which may cause issues if this were a more complicated program.
  \item We can use Valgrind (more specifically it's Memcheck utility) to analyze
        the memory usage and access of your program.
        It's easy: just run \prompt{valgrind ./conv}.
  \item You'll see a lot printed out (which by default goes to \code{stderr}).
        There is a lot of good info here: we get info about bad writes and reads
        and there's a memory leak summary as well.
  \item First, let's deal with the memory leaks since those can be fairly easy to deal with.
        Take a note of the message that says ``Rerun with --leak-check=full to see details of leaked memory'',
        and do that.
  \item Now the heap summary will list out where memory is being lost an dis nice enough
        to tell us the function call stack that associated with the allocations.
        We can see that the buffer allocated by Signal constructor is never getting deallocated.
  \item Fix this memory leak by adding the necessary \code{delete[]} to \code{Signal}'s destructor.
  \item Rebuild and rerun the program with Valgrind. The memory leak should be gone.
        Now onto the invalid write and read.
  \item First, let's look at the invalid write which occurs in \code{main.cpp}.
        Note how in the \code{for} loop, \code{x[3]} is written to due to the \code{for} loop condition,
        writing past the end of the allocated buffer.
        Change the \code{for} loop's condition to fix this.
  \item Rebuild and rerun with Valgrind. The invalid write should be gone now.
        The invalid read is still there, however.
        Let's look at the associated line in \code{conv.cpp}.
  \item The line points to an accumulation: \code{sum += x[xI] * h[hI]}.
        The culprits of this invalid read would either be the \code{x[xI]} or \code{h[hI]},
        as we could be indexing out of the bounds of the buffers for these \code{Signal}s.
  \item If we investigate the code a bit, the \code{for} loop that immediately contains
        the \code{if} statement checks that \code{xI} is less than \code{xN}, the
        size of \code{x}'s buffer. Since in C/C++ indexing is 0-indexed
        (unless I'm mean and had overloaded the subscript operator (\code{[]}) to add 1 to the index)
        the indexing is correct for \code{x} since the last element is at index \code{xN - 1}.
  \item If we look at the \code{if} that controls the accumulation, we can see that
        it's checking if \code{hI} is in the bounds of \code{h}. Notice anything wrong here?
  \item Fix that issue in the \code{if} condition.
        When you rebuild and rerun, you should get a clean report from Valgrind.
  \item Now that it's leak and memory error free, add and commit the files that you made fixes for.
\end{enumerate}

\section{Conclusion}
\begin{enumerate}
  \item Add and commit any changes you intend to submit.
  \item Fill out the \code{REPORT} file in the following steps:
  \item On the first line provide an integer time in minutes of how long it took
        for you to complete this assignment. It should just be an integer: no letters or words.
  \item On the second line and beyond, write down what you learned while doing this assignment.
        If you already knew how to do all of this, put down ``N/A''.
  \item Commit your \code{REPORT} file and push your commits to your remote.
\end{enumerate}

\end{document}
