\chapter{Background}

\epigraph{Sometimes the journey of a thousand steps begins by learning to walk}{}

\section{Systems Architecture}

This section is a short review of System Architecture topics that you'll need for System Programming.

\subsection{Assembly}

What is assembly? Assembly is the lowest that you'll get to machine language without writing 1's and 0's.
Each computer has an architecture, and that architecture has an associated assembly language.
Each assembly command has a 1:1 mapping to a set of 1's and 0's that tell the computer exactly what to do.
For example, the following in the widely used x86 Assembly language add one to the memory address 20 \cite{wiki:xxx} -- you can also look in \cite{guide2011intel} Section 2A under the add instruction though it is more verbose.

\begin{lstlisting}[language={[x86masm]Assembler}]
add BYTE PTR [0x20], 1
\end{lstlisting}

Why do we mention this? Because it is important that although you are going to be doing most of this class in C, that this is what the code is translated into.
Serious implications arise for race conditions and atomic operations.

\subsection{Atomic Operations}

An operation is atomic if no other processor should interrupt it. Take for example the above assembly code to add one to a register.
In the architecture, it may actually have a few different steps on the circuit.
The operation may start by fetching the value of the memory from the stick of ram, then storing it in the cache or a register, and then finally writing back \cite{schweizer2015evaluating} -- under the description for \textit{fetch-and-add} though your micro-architecture may vary.
Or depending on performance operations, it may keep that value in cache or in a register which is local to that process -- try dumping the \keyword{-O2} optimized assembly of incrementing a variable.
The problem comes in if two processors try to do it at the same time.
The two processors could at the same time copy the value of the memory address, add one, and store the same result back, resulting in the value only being incremented once.
That is why we have a special set of instructions on modern systems called atomic operations.
If an instruction is atomic, it makes sure that only one processor or thread performs any intermediate step at a time.
With x86 this is done by the \keyword{lock} prefix \cite[p. 1120]{guide2011intel}.

\begin{lstlisting}
lock add BYTE PTR [0x20], 1
\end{lstlisting}

Why don't we do this for everything?
It makes commands slower! If every time a computer does something it has to make sure that the other cores or processors aren't doing anything, it'll be much slower.
Most of the time we differentiate these with special consideration.
Meaning, we will tell you when we use something like this.
Most of the time you can assume the instructions are unlocked.

\subsection{Caching}

Ah yes, Caching.
One of computer science's greatest problems.
The caching that we are referring to is processor caching.
If a particular address is already in the cache when reading or writing, the processor will perform the operation on the cache, such as adding and update the actual memory, later because updating memory is slow \cite[Section 3.4]{intel2015improving}.
If it isn't, the processor requests a chunk of memory from the memory chip and stores it in the cache, kicking out the least recently used page -- this depends on caching policy, but Intel's does use this.
This is done because the l3 processor cache is roughly three times faster to reach than the memory in terms of time \cite[p. 22]{levinthal2009performance} though exact speeds will vary based on the clock speed and architecture.
Naturally, this leads to problems because there are two different copies of the same value, in the cited paper this refers to an unshared line.
This isn't a class about caching, but you should know how this could impact your code.
A short but non-complete list could be

\begin{enumerate}
\item Race Conditions! If a value is stored in two different processor caches, then that value should be accessed by a single thread.
\item Speed. With a cache, your program may look faster mysteriously. Just assume that reads and writes that either happened recently or are next to each other in memory are fast.
\item Side effects. Every read or write affects the cache state. While most of the time this doesn't help or hurt, it is important to know. Check the Intel programmer guide on the lock prefix for more information.
\end{enumerate}

\subsection{Interrupts}

Interrupts are an important part of system programming.
An interrupt is internally an electrical signal that is delivered to the processor when something happens -- this is a hardware interrupt \cite{redhat_hardware_int}.
Then the hardware decides if this is something that it should handle (e.g., handling keyboard or mouse input for older keyboard and mouses) or it should pass to the operating system.
The operating system then decides if this is something that it should handle (e.g., paging a memory table from disk) or something the application should handle (e.g., a SEGFAULT).
If the operating system decides that this is something that the process or program should take care of, it sends a \textbf{software fault} and that software fault is then propagated.
The application then decides if it is an error (SEGFAULT) or not (SIGPIPE for example) and reports to the user.
Applications can also send signals to the kernel and to the hardware as well.
This is an oversimplification because there are certain hardware faults that can't be ignored or masked away, but this class isn't about teaching you to build an operating system.

An important application of this is how system calls are served!
There is a well-established set of registers that the arguments go in according to the kernel as well as a system call ``number'' again defined by the kernel.
Then the operating system triggers an interrupt which the kernel catches and serves the system call \cite{garg_2006}.

Operating system developers and instruction set developers alike didn't like the overhead of causing an interrupt on a system call. Now, systems use \keyword{SYSENTER} and \keyword{SYSEXIT} which has a cleaner way of transferring control safely to the kernel and safely back.
What safely means is obvious out of the scope for this class, but it persists.
\subsection{Optional: Hyperthreading}

Hyperthreading is a new technology and is in no way shape or form multithreading.
Hyperthreading allows one physical core to appear as many virtual cores to the operating system \cite[P.51]{guide2011intel}.
The operating system can then schedule processes on these virtual cores and one core will execute them.
Each core interleaves processes or threads.
While the core is waiting for one memory access to complete, it may perform a few instructions of another process thread.
The overall result is more instructions executed in a shorter time.
This potentially means that you can divide the number of cores you need to power smaller devices.

There be dragons here, though.
With hyperthreading, you must be wary of optimizations.
A famous hyperthreading bug caused programs to crash if at least two processes were scheduled on a physical core, using specific registers, in a tight loop.
The actual problem is better explained through an architecture lens.
But, the actual application was found through systems programmers working on OCaml's mainline \cite{leroy_2017}.

\section{Debugging and Environments}

I'm going to tell you a secret about this course: it is about working smarter \textit{not} harder.
The course can be time-consuming but the reason that so many people see it as such (and why so many students don't see it as such) is the relative familiarity of people with their tools.
Let's go through some of the common tools that you'll be working on and need to be familiar with.

\subsection{ssh}

\keyword{ssh} is short for the Secure Shell \cite{openbsd_ssh}.
It is a network protocol that allows you to spawn a shell on a remote machine.
Most of the times in this class you will need to ssh into your VM like this

\begin{lstlisting}[language=bash]
$ ssh netid@sem-cs341-VM.cs.illinois.edu
\end{lstlisting}

If you don't want to type your password out every time, you can generate an ssh key that uniquely identifies your machine. If you already have a key pair, you can skip to the copy id stage.

\begin{lstlisting}[language=bash]
> ssh-keygen -t rsa -b 4096
# Do whatever keygen tells you
# Don't feel like you need a passcode if your login password is secure
> ssh-copy-id netid@sem-cs341-VM.cs.illinois.edu
# Enter your password for maybe the final time
> ssh  netid@sem-cs341-VM.cs.illinois.edu
\end{lstlisting}

If you still think that that is too much typing, you can always alias hosts.
You may need to restart your VM or reload sshd for this to take effect.
The config file is available on Linux and Mac distros.
For Windows, you'll have to use the Windows Linux Subsystem or configure any aliases in PuTTY

\begin{lstlisting}[language=bash]
> cat ~/.ssh/config
Host vm
  User          netid
  HostName      sem-cs341-VM.cs.illinois.edu
> ssh vm
\end{lstlisting}

\subsection{git}

What is `git`? Git is a version control system. What that means is git stores the entire history of a directory. We refer to the directory as a repository. So what do you need to know is a few things. First, create your repository with the repo creator. If you haven't already signed into enterprise GitHub, make sure to do so otherwise your repository won't be created for you. After that, your repository is created on the server. Git is a decentralized version control system, meaning that you'll need to get a repository onto your VM. We can do this with a clone. Whatever you do, \textbf{do not go through the README.md tutorial}.

\begin{lstlisting}[language=bash]
$ git clone https://github.com/illinois-cs-coursework/fa23_cs341_<netid>
\end{lstlisting}

This will create a local repository. The workflow is you make a change on your local repository, add the changes to a current commit, actually commit, and push the changes to the server.

\begin{lstlisting}[language=bash]
$ # edit the file, maybe using vim
$ git add <file>
$ git commit -m "Committing my file"
$ git push origin master
\end{lstlisting}

Now to explain git well, you need to understand that git for our purposes will look like a linked list.
You will always be at the head of master, and you will do the edit-add-commit-push loop. We have a separate branch on Github that we push feedback to under a specific branch which you can view on Github website. The markdown file will have information on the test cases and results (like standard out).

Every so often git can break. Here is a list of commands you probably won't need to fix your repo

\begin{enumerate}
\item git-cherry-pick
\item git-pack
\item git-gc
\item git-clean
\item git-rebase
\item git-stash/git-apply/git-pop
\item git-branch
\end{enumerate}

If you are currently on a branch, and you don't see either

\begin{lstlisting}[language=bash]
$ git status
On branch master
Your branch is up-to-date with 'origin/master'.
nothing to commit, working directory clean
\end{lstlisting}

or

\begin{lstlisting}[language=bash]
$ git status
On branch master
Your branch is up-to-date with 'origin/master'.
Changes not staged for commit:
  (use "git add <file>..." to update what will be committed)
  (use "git checkout -- <file>..." to discard changes in working directory)

        modified:   <FILE>
        ...

no changes added to commit (use "git add" and/or "git commit -a")
\end{lstlisting}

And something like

\begin{lstlisting}[language=bash]
$ git status
HEAD detached at 4bc4426
nothing to commit, working directory clean
\end{lstlisting}

Don't panic, but your repository may be in an unworkable state.
If you aren't nearing a deadline, come to office hours or ask your question on Edstem, and we'd be happy to help.
In an emergency scenario, delete your repository and re-clone (you'll have to add the \keyword{release} as above).
\textbf{This will lose any local uncommitted changes. Make sure to copy any files you were working on outside the directory, remove and copy them back in}

If you want to learn more about git, there are all but an endless number of tutorials and resources online that can help you.
Here are some links that can help you out

\begin{enumerate}
\item \url{https://git-scm.com/docs/gittutorial}
\item \url{https://www.atlassian.com/git/tutorials/what-is-version-control}
\item \url{https://thenewstack.io/tutorial-git-for-absolutely-everyone/}
\end{enumerate}

\subsection{Editors}

Some people take this as an opportunity to learn a new editor, others not so much. The first part is those of you who want to learn a new editor. In the editor war that spans decades, we have come to the battle of vim vs emacs.

Vim is a text editor and a Unix-like utility.
You enter vim by typing \keyword{vim [file]}, which takes you into the editor.
There are three most commonly used modes: normal mode, insert mode, and command mode.
You start off in normal mode.
In this mode, you can move around with many keys with the most common ones being \keyword{hjkl} (corresponding to left, down, up, and right, respectively).
To run commands in vim, you can first type \keyword{:} and then a command after it.
For instance, to quit vim, simply type \keyword{:q} (q stands for quit).
If you have any unsaved edits, you must either save them \keyword{:w}, save and quit \keyword{:wq}, or quit and discard changes \keyword{:q!}.
To make edits you can either type \keyword{i} to change you into insert mode or \keyword{a} to change to insert mode \textbf{a}fter the cursor.
This is the basics when it comes to vim.
In addition to the countless great resources out there on the internet, vim also has its own built-in tutorials set up for beginners.
To access the interactive tutorial, enter \keyword{vimtutor} in the command line (not inside of vim), and you are all set!

Emacs is more of a way of life, and I don't mean that figuratively.
A lot of people say that emacs is a powerful operating system lacking a decent text editor.
This means emacs can house a terminal, gdb session, ssh session, code and a whole lot more.
It would not be fitting any other way to introduce you to the gnu-emacs any other way than the gnu-docs \url{https://www.gnu.org/software/emacs/tour/}.
Just note that emacs is \textit{insanely} powerful.
You can do almost anything with it.
There are a fair number of students who like the IDE-aspect of other programming languages.
Know that you can set up emacs to be an IDE, but you have to learn a bit of Lisp \url{http://martinsosic.com/development/emacs/2017/12/09/emacs-cpp-ide.html}.

Then there are those of you who like to use your own editors. That is completely fine.
For this, we require sshfs which has ports on many different machines.

\begin{enumerate}
\item Windows \url{https://github.com/billziss-gh/sshfs-win}
\item Mac \url{https://github.com/osxfuse/osxfuse/wiki/SSHFS}
\item Linux \url{https://help.ubuntu.com/community/SSHFS}
\end{enumerate}

At that point, the files on your VM are synced with the files on your machine and edits can be made and will be synced.

At the time of writing, an author likes to use spacemacs \url{http://spacemacs.org/} which marries both vim and emacs and both of their difficulties.
I'll give my soapbox for why I like it, but be warned that if you are starting from absolutely no vim or emacs experience the learning curve along with this course may be too much.
\begin{enumerate}
\item Extensible. Spacemacs has a clean design written in lisp. There are 100s of packages ready to be installed by editing your spacemacs config and reloading that do everything from syntax checking, automatic static analyzing, etc.
\item Most of the good parts from vim and emacs. Emacs is good at doing everything by being a fast editor. Vim is good at making fast edits and moving around. Spacemacs is the best of both worlds allowing vim keybindings to all the emacs goodness underneath.
\item Lots of preconfiguration done. As opposed with a fresh emacs install, a lot of the configurations with language and projects are done for you like neotree, helm, various language layers. All that you have to do is navigate neotree to the base of your project and emacs will turn into an IDE for that programming language.
\end{enumerate}

But obviously to each his or her own.
Many people will argue that editor gurus spend more time editing their editors and actually editing.

\subsection{Clean Code}

Make your code modular using helper functions. If there is a repeated task (getting the pointers to contiguous blocks in the malloc MP, for example), make them helper functions.
And make sure each function does one thing well so that you don't have to debug twice.
Let's say that we are doing selection sort by finding the minimum element each iteration like so,

\begin{lstlisting}[language=C]
void selection_sort(int *a, long len){
     for(long i = len-1; i > 0; --i){
         long max_index = i;
         for(long j = len-1; j >= 0; --j){
             if(a[max_index] < a[j]){
                  max_index = j;
             }
         }
         int temp = a[i];
         a[i] = a[max_index];
         a[max_index] = temp;
     }

}
\end{lstlisting}

Many can see the bug in the code, but it can help to refactor the above method into

\begin{lstlisting}[language=C]
long max_index(int *a, long start, long end);
void swap(int *a, long idx1, long idx2);
void selection_sort(int *a, long len);
\end{lstlisting}

And the error is specifically in one function.
In the end, this class is about writing system programs, not a class about refactoring/debugging your code.
In fact, most kernel code is so atrocious that you don't want to read it -- the defense there is that it needs to be.
But for the sake of debugging, it may benefit you in the long run to adopt some of these practices.

\subsection{Asserts}

Use assertions to make sure your code works up to a certain point -- and importantly, to make sure you don't break it later.
For example, if your data structure is a doubly-linked list, you can do something like \keyword{assert(node == node->next->prev)} to assert that the next node has a pointer to the current node.
You can also check the pointer is pointing to an expected range of memory address, non-null, -\textgreater{}size is reasonable, etc.
The \keyword{DEBUG} macro will disable all assertions, so don't forget to set that once you finish debugging \cite{cplusplus_assert}.

Here is a quick example with an assert.
Let's say that we are writing code using memcpy.
We would want to put an assert before that checks whether my two memory regions overlap.
If they do overlap, memcpy runs into undefined behavior, so we want to discover that problem sooner rather than later.

\begin{lstlisting}[language=C]
assert( src+n < dest || src >= dest + n); // source should finish before the destination or the source starts after the end of destination
memcpy(dest, src, n);
\end{lstlisting}

This check can be turned off at compile-time, but will save you \textbf{tons} of trouble debugging!

\section{Valgrind}

Valgrind is a suite of tools designed to provide debugging and profiling tools to make your programs more correct and detect some runtime issues \cite{valgrind}.
The most used of these tools is Memcheck, which can detect many memory-related errors that are common in C and C++ programs and that can lead to crashes and unpredictable behavior (for example, unfreed memory buffers).
To run Valgrind on your program:

\begin{lstlisting}[language=C]
valgrind --leak-check=full --show-leak-kinds=all myprogram arg1 arg2
\end{lstlisting}

Arguments are optional and the default tool that will run is Memcheck.
The output will be presented in the form: the number of allocations, frees, and errors.
Suppose we have a simple program like this:

\begin{lstlisting}[language=C]
#include <stdlib.h>

void dummy_function() {
	int* x = malloc(10 * sizeof(int));
	x[10] = 0;        // error 1: Out of bounds write, as you can see here we write to an out of bound memory address.
}                    // error 2: Memory Leak, x is allocated at function exit.

int main(void) {
	dummy_function();
	return 0;
}
\end{lstlisting}

This program compiles and runs with no errors.
Let's see what Valgrind will output.

\begin{lstlisting}[language=C]
==29515== Memcheck, a memory error detector
==29515== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==29515== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==29515== Command: ./a
==29515==
==29515== Invalid write of size 4
==29515==    at 0x400544: dummy_function (in /home/rafi/projects/exocpp/a)
==29515==    by 0x40055A: main (in /home/rafi/projects/exocpp/a)
==29515==  Address 0x5203068 is 0 bytes after a block of size 40 alloc'd
==29515==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==29515==    by 0x400537: dummy_function (in /home/rafi/projects/exocpp/a)
==29515==    by 0x40055A: main (in /home/rafi/projects/exocpp/a)
==29515==
==29515==
==29515== HEAP SUMMARY:
==29515==     in use at exit: 40 bytes in 1 blocks
==29515==   total heap usage: 1 allocs, 0 frees, 40 bytes allocated
==29515==
==29515== LEAK SUMMARY:
==29515==    definitely lost: 40 bytes in 1 blocks
==29515==    indirectly lost: 0 bytes in 0 blocks
==29515==      possibly lost: 0 bytes in 0 blocks
==29515==    still reachable: 0 bytes in 0 blocks
==29515==         suppressed: 0 bytes in 0 blocks
==29515== Rerun with --leak-check=full to see details of leaked memory
==29515==
==29515== For counts of detected and suppressed errors, rerun with: -v
==29515== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
\end{lstlisting}

\textbf{Invalid write}: It detected our heap block overrun, writing outside of an allocated block.

\textbf{Definitely lost}: Memory leak --- you probably forgot to free a memory block.

Valgrind is a effective tool to check for errors at runtime. C is special when it comes to such behavior, so after compiling your program you can use Valgrind to fix errors that your compiler may miss and that usually happens when your program is running.

For more information, you can refer to the manual \cite{valgrind}

\subsection{TSAN}

ThreadSanitizer is a tool from Google, built into clang and gcc, to help you detect race conditions in your code \cite{threadsanitizercppmanual_2018}.
Note, that running with tsan will slow your code down a bit. Consider the following code.

\begin{lstlisting}[language=C]
#include <pthread.h>
#include <stdio.h>

int global;

void *Thread1(void *x) {
    global++;
    return NULL;
}

int main() {
    pthread_t t[2];
    pthread_create(&t[0], NULL, Thread1, NULL);
    global = 100;
    pthread_join(t[0], NULL);
}
// compile with gcc -fsanitize=thread -pie -fPIC -ltsan -g simple_race.c
\end{lstlisting}

We can see that there is a race condition on the variable \keyword{global}.
Both the main thread and created thread will try to change the value at the same time.
But, does ThreadSantizer catch it?

\begin{lstlisting}[language=bash]
$ ./a.out
==================
WARNING: ThreadSanitizer: data race (pid=28888)
  Read of size 4 at 0x7f73ed91c078 by thread T1:
    #0 Thread1 /home/zmick2/simple_race.c:7 (exe+0x000000000a50)
    #1  :0 (libtsan.so.0+0x00000001b459)

  Previous write of size 4 at 0x7f73ed91c078 by main thread:
    #0 main /home/zmick2/simple_race.c:14 (exe+0x000000000ac8)

  Thread T1 (tid=28889, running) created by main thread at:
    #0  :0 (libtsan.so.0+0x00000001f6ab)
    #1 main /home/zmick2/simple_race.c:13 (exe+0x000000000ab8)

SUMMARY: ThreadSanitizer: data race /home/zmick2/simple_race.c:7 Thread1
==================
ThreadSanitizer: reported 1 warnings
\end{lstlisting}

If we compiled with the debug flag, then it would give us the variable name as well.

\section{GDB}

GDB is short for the GNU Debugger. GDB is a program that helps you track down errors by interactively debugging them \cite{gdb}. It can start and stop your program, look around, and put in ad hoc constraints and checks. Here are a few examples.

\paragraph{Setting breakpoints programmatically}

A breakpoint is a line of code where you want the execution to stop and give control back to the debugger.
A useful trick when debugging complex C programs with GDB is setting breakpoints in the source code.

\begin{lstlisting}[language=C]
int main() {
    int val = 1;
    val = 42;
    asm("int $3"); // set a breakpoint here
    val = 7;
}
\end{lstlisting}

\begin{lstlisting}[language=bash]
$ gcc main.c -g -o main
$ gdb --args ./main
(gdb) r
[...]
Program received signal SIGTRAP, Trace/breakpoint trap.
main () at main.c:6
6     val = 7;
(gdb) p val
$1 = 42
\end{lstlisting}

You can also set breakpoints programmatically.
Assume that we have no optimization and the line numbers are as follows

\begin{lstlisting}[language=bash]
1. int main() {
2.     int val = 1;
3.     val = 42;
4.     val = 7;
5. }
\end{lstlisting}

We can now set the breakpoint before the program starts.

\begin{lstlisting}[language=bash]
$ gcc main.c -g -o main
$ gdb --args ./main
(gdb) break main.c:4
[...]
(gdb) p val
$1 = 42
\end{lstlisting}

\paragraph{Checking memory content}


We can also use gdb to check the content of different pieces of memory.
For example,

\begin{lstlisting}[language=C]
int main() {
    char bad_string[3] = {'C', 'a', 't'};
    printf("%s", bad_string);
}
\end{lstlisting}

Compiled we get

\begin{lstlisting}[language=bash]
$ gcc main.c -g -o main && ./main
$ Cat ZVQ� $
\end{lstlisting}


We can now use gdb to look at specific bytes of the string and reason about when the program should've stopped running

\begin{lstlisting}[language=bash]
(gdb) l
1 #include <stdio.h>
2 int main() {
3     char bad_string[3] = {'C', 'a', 't'};
4     printf("%s", bad_string);
5 }
(gdb) b 4
Breakpoint 1 at 0x100000f57: file main.c, line 4.
(gdb) r
[...]
Breakpoint 1, main () at main.c:4
4     printf("%s", bad_string);
(gdb) x/16xb bad_string
0x7fff5fbff9cd: 0x63  0x61  0x74  0xe0  0xf9  0xbf  0x5f  0xff
0x7fff5fbff9d5: 0x7f  0x00  0x00  0xfd  0xb5  0x23  0x89  0xff
(gdb)
\end{lstlisting}

Here, by using the \keyword{x} command with parameters \keyword{16xb}, we can see that starting at memory address \keyword{0x7fff5fbff9c} (value of \keyword{bad\_string}), \keyword{printf} would actually see the following sequence of bytes as a string because we provided a malformed string without a null terminator.

\subsection{Involved gdb example}

Here is how one of your TAs would go through and debug a simple program that is going wrong.
First, the source code of the program.
If you can see the error immediately, please bear with us.

\begin{lstlisting}[language=C]
#include <stdio.h>

double convert_to_radians(int deg);

int main(){
	for (int deg = 0; deg > 360; ++deg){
		double radians = convert_to_radians(deg);
		printf("%d. %f\n", deg, radians);
	}
	return 0;
}

double convert_to_radians(int deg){
	return ( 31415 / 1000 ) * deg / 180;
}
\end{lstlisting}

How can we use gdb to debug? First we ought to load GDB.

\begin{lstlisting}[language=bash]
$ gdb --args ./main
(gdb) layout src; # If you want a GUI type
(gdb) run
(gdb)
\end{lstlisting}

Want to take a look at the source?

\begin{lstlisting}[language=bash]
(gdb) l
1	#include <stdio.h>
2	
3	double convert_to_radians(int deg);
4	
5	int main(){
6		for (int deg = 0; deg > 360; ++deg){
7			double radians = convert_to_radians(deg);
8			printf("%d. %f\n", deg, radians);
9		}
10	    return 0;
(gdb) break 7 # break <file>:line or break <file>:function
(gdb) run
(gdb)
\end{lstlisting}

From running the code, the breakpoint didn't even trigger, meaning the code never got to that point.
That’s because of the comparison!
Okay, flip the sign it should work now right?

\begin{lstlisting}[language=bash]
(gdb) run
350. 60.000000
351. 60.000000
352. 60.000000
353. 60.000000
354. 60.000000
355. 61.000000
356. 61.000000
357. 61.000000
358. 61.000000
359. 61.000000

\end{lstlisting}

\begin{lstlisting}[language=bash]
(gdb) break 14 if deg == 359 # Let's check the last iteration only
(gdb) run
...
(gdb) print/x deg # print the hex value of degree
$1 = 0x167
(gdb) print (31415/1000)
$2 = 0x31
(gdb) print (31415/1000.0)
$3 = 201.749
(gdb) print (31415.0/10000.0)
$4 = 3.1414999999999999

\end{lstlisting}

That was only the bare minimum, though most of you will get by with that.
There are a whole load more resources on the web, here are a few specific ones that can help you get started.

\begin{enumerate}
\item \href{http://www.cs.cmu.edu/~gilpin/tutorial/}{Introduction to gdb}
\item \href{https://ftp.gnu.org/old-gnu/Manuals/gdb/html_node/gdb_toc.html}{GDB Manual}
\item \href{https://www.youtube.com/watch?v=PorfLSr3DDI}{CppCon 2015: Greg Law “Give me 15 minutes & I'll change your view of GDB”}
\end{enumerate}

\subsection{Shell}

What do you actually use to run your program? A shell! A shell is a programming language that is running inside your terminal. A terminal is merely a window to input commands. Now, on POSIX we usually have one shell called \keyword{sh} that is linked to a POSIX compliant shell called \keyword{dash}. Most of the time, you use a shell called \keyword{bash} that is somewhat POSIX compliant but has some nifty built-in features. If you want to be even more advanced, \keyword{zsh} has some more powerful features like tab complete on programs and fuzzy patterns.

\subsection{Undefined Behavior Sanitizer}

The undefined behavior sanitizer is a wonderful tool provided by the llvm project.
It allows you to compile code with a runtime checker to make sure that you don't do undefined behavior for various categories.
We will try to include it into our projects, but requires support form all the external libraries that we use so we may not get around to all of them.
\url{https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html}

\subsubsection{Undefined behavior - why we can't solve it in general}

Also please please read Chris Lattner's 3 Part blog post on undefined behavior. It can shed light on debug builds and the mystery of compiler optimization.

\url{http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html}


\subsection{Clang Static Build Tools}

Clang provides a great drop-in replacement tools for compiling programs.
If you want to see if there is an error that may cause a race condition, casting error, etc, all you need to do is the following.

\begin{lstlisting}[language=bash]
$ scan-build make
\end{lstlisting}

And in addition to the make output, you will get static build warnings.

\subsection{strace and ltrace}

strace and ltrace are two programs that trace the system calls and library calls, respectively, of a running program or command.
These may be missing on your system, so to install, run the following:

\begin{lstlisting}[language=bash]
$ sudo apt install strace ltrace
\end{lstlisting}

Debugging with ltrace can be as simple as figuring out what was the return call of the last library call that failed.

\begin{lstlisting}[language=C]
int main() {
    FILE *fp = fopen("I don't exist", "r");
    fprintf(fp, "a");
    fclose(fp);
    return 0;
}
\end{lstlisting}

\begin{lstlisting}[language=bash]
> ltrace ./a.out
 __libc_start_main(0x8048454, 1, 0xbfc19db4, 0x80484c0, 0x8048530 <unfinished ...>
 fopen("I don't exist", "r")                          = 0x0
 fwrite("Invalid Write\n", 1, 14, 0x0 <unfinished ...>
 --- SIGSEGV (Segmentation fault) ---
 +++ killed by SIGSEGV +++

\end{lstlisting}

ltrace output can clue you in to weird things your program is doing live.
Unfortunately, ltrace can’t be used to inject faults, meaning that ltrace can tell you what is happening, but it can't tamper with what is already happening.

strace on the other hand could modify your program.
Debugging with strace is amazing.
The basic usage is running strace with a program, and it’ll get you a complete list of system call parameters.

\begin{lstlisting}[language=bash]
$ strace head README.md
execve("/usr/bin/head", ["head", "README.md"], 0x7ffff28c8fa8 /* 60 vars */) = 0
brk(NULL)                               = 0x7ffff5719000
access("/etc/ld.so.nohwcap", F_OK)      = -1 ENOENT (No such file or directory)
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=32804, ...}) = 0
...
\end{lstlisting}

If the output is too verbose, you can use trace= with a command delimited list of syscalls to filter all but those calls.

\begin{lstlisting}[language=bash]
$ strace -e trace=read,write head README.md
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\260\34\2\0\0\0\0\0"..., 832) = 832
read(3, "# Locale name alias data base.\n#"..., 4096) = 2995
read(3, "", 4096)                       = 0
read(3, "# C Datastructures\n\n[![Build Sta"..., 8192) = 1250
write(1, "# C Datastructures\n", 19# C Datastructures
\end{lstlisting}

You can also trace files or targets.

\begin{lstlisting}[language=bash]
$ strace -e trace=read,write -P README.md head README.md
strace: Requested path 'README.md' resolved into '/mnt/c/Users/user/personal/libds/README.md'
read(3, "# C Datastructures\n\n[![Build Sta"..., 8192) = 1250

\end{lstlisting}

Newer versions of strace can actually inject faults into your program.
This is useful when you want to occasionally make reads and writes fail for example in a networking application, which your program should handle.
The problem is as of early 2019, that version is missing from Ubuntu repositories.
Meaning that you'll have to install it from the source.

\subsection{printfs}

When all else fails, print! Each of your functions should have an idea of what it is going to do.
You want to test that each of your functions is doing what it set out to do and see exactly where your code breaks.
In the case with race conditions, tsan may be able to help, but having each thread print out data at certain times could help you identify the race condition.

To make printfs useful, try to have a macro that fills in the context by which the printf was called -- a log statement if you will. A simple useful but untested log statement could be as follows.
Try to make a test and figure out something that is going wrong, then log the state of your variables.

\begin{lstlisting}[language=C]
  #include <execinfo.h>
  #include <stdio.h>
  #include <stdlib.h>
  #include <stdarg.h>
  #include <unistd.h>

  // bt is print backtrace
  const int num_stack = 10;
  int __log(int line, const char *file, int bt, const char *fmt, ...) {
    if (bt) {
      void *raw_trace[num_stack];
      size_t size = backtrace(raw_trace, sizeof(raw_trace) / sizeof(raw_trace[0]));
      char **syms = backtrace_symbols(raw_trace, size);

      for(ssize_t i = 0; i < size; i++) {
        fprintf(stderr, "|%s:%d| %s\n", file, line, syms[i]);
      }
      free(syms);
    }
    int ret = fprintf(stderr, "|%s:%d| ", file, line);
    va_list args;
    va_start(args, fmt);
    ret += vfprintf(stderr, fmt, args);
    va_end(args);
    ret += fprintf(stderr, "\n");
    return ret;
  }

  #ifdef DEBUG
  #define log(...) __log(__LINE__, __FILE__, 0, __VA_ARGS__)
  #define bt(...) __log(__LINE__, __FILE__, 1, __VA_ARGS__)
  #else
  #define log(...)
  #define bt(...)
  #endif

  //Use as log(args like printf) or bt(args like printf) to either log or get backtrace

  int main() {
    log("Hello Log");
    bt("Hello Backtrace");
  }
\end{lstlisting}

And then use as appropriately. Check out the compiling and linking section in the appendix if you have any questions on how a C program gets translated to machine code.

\newpage

\section{Homework 0}

\begin{lstlisting}[language=C]
// First, can you guess which lyrics have been transformed into this C-like system code?
char q[] = "Do you wanna build a C99 program?";
#define or "go debugging with gdb?"
static unsigned int i = sizeof(or) != strlen(or);
char* ptr = "lathe";
size_t come = fprintf(stdout,"%s door", ptr+2);
int away = ! (int) * "";

int* shared = mmap(NULL, sizeof(int*), PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANONYMOUS, -1, 0);
munmap(shared,sizeof(int*));

if(!fork()) {
    execlp("man","man","-3","ftell", (char*)0); perror("failed");
}

if(!fork()) {
    execlp("make","make", "snowman", (char*)0); execlp("make","make", (char*)0));
}

exit(0);
\end{lstlisting}

\subsection{So you want to master System Programming? And get a better grade than B?}

\begin{minted}{C}
int main(int argc, char** argv) {
	puts("Great! We have plenty of useful resources for you, but it's up to you to");
	puts(" be an active learner and learn how to solve problems and debug code.");
	puts("Bring your near-completed answers the problems below");
	puts(" to the first lab to show that you've been working on this.");
	printf("A few \"don't knows\" or \"unsure\" is fine for lab 1.\n");
	puts("Warning: you and your peers will work hard in this class.");
	puts("This is not CS225; you will be pushed much harder to");
	puts(" work things out on your own.");
	fprintf(stdout,"This homework is a stepping stone to all future assignments.\n");
	char p[] = "So, you will want to clear up any confusions or misconceptions.\n";
	write(1, p, strlen(p) );
	char buffer[1024];
	sprintf(buffer,"For grading purposes, this homework 0 will be graded as part of your lab %d work.\n", 1);
	write(1, buffer, strlen(buffer));
	printf("Press Return to continue\n");
	read(0, buffer, sizeof(buffer));
	return 0;
}
\end{minted}

\subsection{Watch the videos and write up your answers to the following questions}

\textbf{Important!}

The virtual machine-in-your-browser and the videos you need for HW0 are here:

\url{http://cs-education.github.io/sys/}

Questions? Comments? Use the current semester's CS341 Edstem:
\url{https://edstem.org/us/courses/61021/discussion/}

The in-browser virtual machine runs entirely in JavaScript and is fastest in Chrome.
Note the VM and any code you write is reset when you reload the page, \textbf{so copy your code to a separate document.}
The post-video challenges are not part of homework 0, but you learn the most by doing rather than passively watching.
You have some fun with each end-of-video challenge.

HW0 questions are below. Copy your answers into a text document because you'll need to submit them later in the course.

\subsection{Chapter 1}

In which our intrepid hero battles standard out, standard error, file descriptors and writing to files

\begin{enumerate}
\item \textbf{Hello, World! (system call style)} Write a program that uses \keyword{write()} to print out "Hi! My name is <Your Name>".
\item \textbf{Hello, Standard Error Stream!} Write a function to print out a triangle of height \keyword{n} to standard error.
Your function should have the signature \keyword{void write\_triangle(int n)} and should use \keyword{write()}.
The triangle should look like this, for n = 3:
\begin{lstlisting}[language=C]
*
**
***
\end{lstlisting}
\item \textbf{Writing to files} Take your program from "Hello, World!" modify it write to a file called \keyword{hello\_world.txt}. Make sure to use correct flags and a correct mode for \keyword{open()} (\keyword{man 2 open} is your friend).
\item \textbf{Not everything is a system call} Take your program from "Writing to files" and replace \keyword{write()} with \keyword{printf()}. \textit{Make sure to print to the file instead of standard out!}
\item What are some differences between \keyword{write()} and \keyword{printf()}?
\end{enumerate}

\subsection{Chapter 2}

Sizing up C types and their limits, \keyword{int} and \keyword{char} arrays, and incrementing pointers

\begin{enumerate}
\item How many bits are there in a byte?
\item How many bytes are there in a \keyword{char}?
\item How many bytes the following are on your machine? \keyword{int}, \keyword{double}, \keyword{float}, \keyword{long}, and \keyword{long long}
\item On a machine with 8 byte integers, the declaration for the variable \keyword{data} is \keyword{int data[8]}.
If the address of data is \keyword{0x7fbd9d40}, then what is the address of \keyword{data+2}?
\item What is \keyword{data[3]} equivalent to in C? Hint: what does C convert \keyword{data[3]} to before dereferencing the address?
Remember, the type of a string constant \keyword{"abc"} is an array.
\item Why does this SEGFAULT?
\begin{lstlisting}[language=C]
char *ptr = "hello";
*ptr = 'J';
\end{lstlisting}

\item What is the value of the variable \keyword{str\_size}?
\begin{lstlisting}[language=C]
ssize_t str_size = sizeof("Hello\0World")
\end{lstlisting}
\item What is the value of the variable \keyword{str\_len}
\begin{lstlisting}[language=C]
ssize_t str_len = strlen("Hello\0World")
\end{lstlisting}
\item Give an example of X such that \keyword{sizeof(X)} is 3.
\item Give an example of Y such that \keyword{sizeof(Y)} might be 4 or 8 depending on the machine.
\end{enumerate}

\subsection{Chapter 3}

Program arguments, environment variables, and working with character arrays (strings)

\begin{enumerate}
\item What are at least two ways to find the length of \keyword{argv}?
\item What does \keyword{argv[0]} represent?
\item Where are the pointers to environment variables stored (on the stack, the heap, somewhere else)?
\item On a machine where pointers are 8 bytes, and with the following code:
\begin{lstlisting}[language=C]
char *ptr = "Hello";
char array[] = "Hello";
\end{lstlisting}
What are the values of \keyword{sizeof(ptr)} and \keyword{sizeof(array)}? Why?
\item What data structure manages the lifetime of automatic variables?
\end{enumerate}

\subsection{Chapter 4}

Heap and stack memory, and working with structs

\begin{enumerate}
\item If I want to use data after the lifetime of the function it was created in ends, where should I put it? How do I put it there?
\item What are the differences between heap and stack memory?
\item Are there other kinds of memory in a process?
\item Fill in the blank: "In a good C program, for every malloc, there is a \_\_\_".
\item What is one reason \keyword{malloc} can fail?
\item What are some differences between \keyword{time()} and \keyword{ctime()}?
\item What is wrong with this code snippet?
\begin{lstlisting}[language=C]
free(ptr);
free(ptr);
\end{lstlisting}
\item What is wrong with this code snippet?
\begin{lstlisting}[language=C]
free(ptr);
printf("%s\n", ptr);
\end{lstlisting}
\item How can one avoid the previous two mistakes?
\item Create a \keyword{struct} that represents a \keyword{Person}.
  Then make a \keyword{typedef}, so that \keyword{struct Person} can be replaced with a single word.
  A person should contain the following information: their name (a string), their age (an integer), and a list of their friends (stored as a pointer to an array of pointers to \keyword{Person}s).
\item Now, make two persons on the heap, "Agent Smith" and "Sonny Moore", who are 128 and 256 years old respectively and are friends with each other.
Create functions to create and destroy a Person (Person's and their names should live on the heap).
\item \keyword{create()} should take a name and age.
  The name should be copied onto the heap.
  Use malloc to reserve sufficient memory for everyone having up to ten friends.
  Be sure initialize all fields (why?).
\item \keyword{destroy()} should free up both the memory of the person struct and all of its attributes that are stored on the heap. Destroying one person keeps other people in tact any other.
\end{enumerate}

\subsection{Chapter 5}

Text input and output and parsing using \keyword{getchar}, \keyword{gets}, and \keyword{getline}.

\begin{enumerate}
\item What functions can be used for getting characters from \keyword{stdin} and writing them to \keyword{stdout}?
\item Name one issue with \keyword{gets()}.
\item Write code that parses the string "Hello 5 World" and initializes 3 variables to "Hello", 5, and "World".
\item What does one need to define before including \keyword{getline()}?
\item Write a C program to print out the content of a file line-by-line using \keyword{getline()}.
\end{enumerate}

\subsection{C Development}

These are general tips for compiling and developing using a compiler and git.
Some web searches will be useful here

\begin{enumerate}
\item What compiler flag is used to generate a debug build?
\item You fix a problem in the Makefile and type \keyword{make} again.
Explain why this may be insufficient to generate a new build.
\item Are tabs or spaces used to indent the commands after the rule in a Makefile?
\item What does \keyword{git commit} do? What's a \keyword{sha} in the context of git?
\item What does \keyword{git log} show you?
\item What does \keyword{git status} tell you and how would the contents of \keyword{.gitignore} change its output?
\item What does \keyword{git push} do? Why is it insufficient to commit with \keyword{git commit -m 'fixed all bugs' }?
\item What does a non-fast-forward error \keyword{git push} reject mean? What is the most common way of dealing with this?
\end{enumerate}

\subsection{Optional: Just for fun}

\begin{itemize}
\item Convert a song lyrics into System Programming and C code covered in this wiki book and share on the class forum.
\item Find, in your opinion, the best and worst C code on the web and post the link to the class forum.
\item Write a short C program with a deliberate subtle C bug and post it on the class forum to see if others can spot your bug.
\item Do you have any cool/disastrous system programming bugs you've heard about? Feel free to share with your peers and the course staff on the class forum.
\end{itemize}

\section{University of Illinois Specific Guidelines}

\subsection{The class forum}

TAs and student assistants get a ton of questions.
Some are well-researched, and some are not.
This is a handy guide that'll help you move away from the latter and towards the former.
Oh, and did I mention that this is an easy way to score points with your internship managers? Ask yourself...

\begin{enumerate}
\item Am I running on my Virtual Machine?
\item \textbf{Did I check the man pages?}
\item Have I searched for similar questions/followups on the class forum?
\item Have I read the MP/Lab specification completely?
\item Have I watched all of the videos?
\item Did I Google the error message and a few permutations thereof if necessary? How about StackOverflow.
\item Did I try commenting out, printing, and/or stepping through parts of the code bit by bit to find out precisely where the error occurs?
\item \textbf{Did I commit my code to git in case the TAs need more context?}
\item Did I include the console/GDB/Valgrind output **AND** code surrounding the bug in my the class forum post?
\item Have I fixed other segmentation faults unrelated to the issue I'm having?
\item Am I following good programming practice? (i.e. encapsulation, functions to limit repetition, etc)
\end{enumerate}

The biggest tip that we can give you when asking a question on the class forum if you want a swift answer is to \textbf{ask your question like you were trying to answer it}. Like before you ask a question, try to answer it yourself. If you are thinking about posting

\begin{quote}
Hi, My code got a 50% on the autograder. I tried testing it a lot, but couldn't get it to fail. Can you give me some hints as to the test cases
\end{quote}

Sounds good and courteous, but course staff would much much prefer a post resembling the following

\begin{quote}
Hi, I recently failed test X, Y, Z which is about half the tests on this current assignment. I noticed that they all have something to do with networking and epoll, but couldn't figure out what was linking them together, or I may be completely off track. So to test my idea, I tried spawning 1000 clients with various get and put requests and verifying the files matched their originals. I couldn't get it to fail while running normally, the debug build, or valgrind or tsan. I have no warnings and none of the pre-syntax checks showed me anything. Could you tell me if my understanding of the failure is correct and what I could do to modify my tests to better reflect X, Y, Z? netid: bvenkat2
\end{quote}

You don't need to be as courteous, though we'd appreciate it, this will get a faster response time hand over foot. If you were trying to answer this question, you'd have everything you need in the question body.

\bibliographystyle{plainnat}
\bibliography{background/background}
