Index: doc/theses/lynn_tran_SE499/Chapters/Extensions.tex
===================================================================
--- doc/theses/lynn_tran_SE499/Chapters/Extensions.tex	(revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16)
+++ doc/theses/lynn_tran_SE499/Chapters/Extensions.tex	(revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16)
@@ -0,0 +1,368 @@
+\chapter{Extending GDB for \uC}
+
+\section{Introduction}
+A sequential program has a single call stack. A debugger knows about this call stack and provides
+commands to walk up/down the call frames to examine the values of local variables, as well as global
+variables. A concurrent program has multiple call stacks (for coroutines/tasks), so a debugger must
+be extended to locate these stacks for examination, similar to a sequential stack.  For example,
+when a concurrent program deadlocks, looking at the task's call stack can locate the resource and
+the blocking cycle that resulted in the deadlock. Hence, it is very useful to display the call stack
+of each task to know where it is executing and what values it is currently computing. Because each
+programming language's concurrency is different, GDB has to be specifically extended for \uC.
+
+\section{Design Constraints}
+As mentioned in Chapter \ref{GDB}, there are several ways to extend GDB. However, there are a few
+design constraints on the selected mechanism. All the functions implemented should maintain similar
+functionality to existing GDB commands. In addition to functional requirements, usability and
+flexibility are requirements for this project. These final requirements enable developers to be
+productive quickly and do more with the extensions. The extensions created for \uC are simple to use
+and versatile.
+
+The following new GDB command are all implemented through the Python API for GDB.  Python is a
+scripting language with built-in data structures and functions that enables the development of more
+complex operations and saves time on development.
+
+\section{\uC source-code example}
+Listing \ref{uC-src-code} shows a \uC program that implicitly creates two clusters, system and user,
+which implicitly have a processor (kernel thread) and processor task. The program explicitly creates
+three additional processors and ten tasks on the user cluster.
+
+\begin{figure}
+\begin{lstlisting}[numbers=left, xleftmargin=4.0ex, style=C++, caption={\uC source code used for GDB commands},label={uC-src-code}, basicstyle=\small]
+_Task T {
+    const int tid;
+    std::string name;
+
+    void f(int param) {
+        if ( param != 0 ) f( param - 1 );	// recursion
+	for ( volatile size_t i = 0; i < 100000000; i += 1 ); // delay
+        int x = 3;
+        std::string y = "example";
+    }						// breakpoint
+    void main() {
+	if ( tid != 0 )				// T0 goes first
+	    for ( volatile size_t i = 0; i < 1000000000; i += 1 ) // delay
+		if ( i % 10000000 == 0 ) yield(); // execute other tasks
+        f(3);
+    }
+  public:
+    T(const int tid) : tid( tid ) {
+        name = "T" + std::to_string(tid);
+        setName(name.c_str());
+    }
+};
+int main() {
+    uProcessor procs[3];			// extra processors
+    const int numTasks = 10;
+    T * tasks[numTasks];			// extra tasks
+    // allocate tasks with different names
+    for (int id = 0; id < numTasks; id += 1) {
+        tasks[id] = new T(id);
+    }
+    // deallocate tasks
+    for (int id = 0; id < numTasks; id += 1) {
+        delete tasks[id];
+    }
+}
+\end{lstlisting}
+\end{figure}
+
+\section{Existing User-defined GDB Commands}
+Listing \ref{uC-callstack} shows the GDB output at the base case of the recursion for one of the
+tasks created in the \uC program in listing \ref{uC-src-code}.  The task is stopped at line 10. The
+backtrace shows the three calls to function \verb|f|, started in the task's \verb|main|. The top two
+frames (5 and 6) are administrative frames from \uC. The values of the argument and local variables
+are printed.
+\begin{lstlisting}[caption={Call stack of function \texttt{a} in the \uC
+program from listing \ref{uC-src-code}}, label={uC-callstack}, basicstyle=\small\tt]
+(gdb) backtrace
+#0  T::f (this=0xa4f950, param=0) at test.cc:10
+#1  0x000000000041e509 in T::f (this=0xa4f950, param=1) at test.cc:6
+#2  0x000000000041e509 in T::f (this=0xa4f950, param=2) at test.cc:6
+#3  0x000000000041e509 in T::f (this=0xa4f950, param=3) at test.cc:6
+#4  0x000000000041e654 in T::main (this=0xa4f950) at test.cc:15
+#5  0x0000000000428de2 in ...::invokeTask (This=...) at ...
+#6  0x0000000000000000 in ?? ()
+(gdb) info args
+this = 0xa4f950
+param = 0
+(gdb) info locals
+x = 3
+y = "example"
+\end{lstlisting}
+
+\subsection{Listing all clusters in a \uC program}
+Listing \ref{clusters-command} shows the new command \verb|clusters| to list all program clusters
+along with their associated address.  The output shows the two \uC implicitly created clusters.
+\begin{lstlisting}[caption={clusters command}, label={clusters-command}, basicstyle=\small\tt]
+(gdb) clusters
+                Name           Address
+       systemCluster          0x65a300
+         userCluster          0x7ca300
+\end{lstlisting}
+
+\subsection{Listing all processors in a cluster}
+Listing \ref{cluster-procs} shows the new command \verb|processors|, which requires a cluster
+argument to show all the processors in that cluster. In particular, this example shows that there
+are four processors in the \verb|userCluster|, with their associated address, PID, preemption and
+spin.
+\begin{lstlisting}[caption={processors command}, label={cluster-procs}, basicstyle=\small\tt]
+(gdb) processors
+           Address                 PID          Preemption                Spin
+          0x7ccc30             8421504                  10                1000
+          0x8c9b50             9478272                  10                1000
+          0x8c9d10            10002560                  10                1000
+          0x8c9ed0            10530944                  10                1000
+\end{lstlisting}
+
+\subsection{Listing all tasks in all clusters}
+Listing \ref{tasks} shows the new command \verb|task| with the \verb|all| argument to list all the
+tasks in a \uC program at this point in the execution snapshot.  The internal \uC threads
+(implicitly created) are numbered with negative identifiers, while those created by the application
+are numbered with zero/positive. The \verb|*| indicates the \uC thread (\verb|T0|) that encountered
+the breakpoint at line 10. GDB stops all execution and the states of the other threads are ready,
+running, or blocked. If the argument \verb|all| is removed, only internal information about the
+\verb|userCluster| and its implicitly created threads is printed, which is sufficient for most
+applications.
+\begin{lstlisting}[caption={task command for displaying all tasks for all clusters}, label={tasks}, basicstyle=\footnotesize\tt]
+(gdb) task all
+        Cluster Name           Address
+       systemCluster          0x65a300
+  ID           Task Name           Address                    State
+  -1      uProcessorTask          0x6c99c0       uBaseTask::Blocked
+  -2         uSystemTask          0x789f40       uBaseTask::Blocked
+         userCluster          0x7ca300
+  ID           Task Name           Address                    State
+  -1      uProcessorTask          0x80ced0       uBaseTask::Blocked
+  -2           uBootTask          0x659dd0       uBaseTask::Blocked
+   0                main    0x7fffffffe490       uBaseTask::Blocked
+  -3      uProcessorTask          0x90e810       uBaseTask::Blocked
+  -4      uProcessorTask          0x98ee00       uBaseTask::Blocked
+  -5      uProcessorTask          0xa0f3f0       uBaseTask::Blocked
+ * 1                  T0          0xa4f950       uBaseTask::Running
+   2                  T1          0xa8fce0       uBaseTask::Running
+   3                  T2          0xad0070       uBaseTask::Running
+   4                  T3          0xb10400         uBaseTask::Ready
+   5                  T4          0xb50790         uBaseTask::Ready
+   6                  T5          0xb90b20         uBaseTask::Ready
+   7                  T6          0xbd0eb0         uBaseTask::Ready
+   8                  T7          0xc11240         uBaseTask::Ready
+   9                  T8          0xc515d0       uBaseTask::Running
+  10                  T9          0xc91960         uBaseTask::Ready
+\end{lstlisting}
+
+\subsection{Listing all tasks in a cluster}
+Listing \ref{cluster-tasks} shows the new command \verb|task| with a cluster argument to list only
+the names of the tasks on that cluster.  In this version of the command \verb|task|, the associated
+address for each task and its state is displayed.
+\begin{lstlisting}[caption={task command for displaying all tasks in a cluster}, label={cluster-tasks}, basicstyle=\small\tt]
+(gdb) task systemCluster
+  ID           Task Name           Address                    State
+  -1      uProcessorTask          0x6c99c0       uBaseTask::Blocked
+  -2         uSystemTask          0x789f40       uBaseTask::Blocked
+\end{lstlisting}
+
+\section{Changing Stacks}
+The next extension for displaying information is writing new commands that allow stepping from one
+\uC task to another. Each switching remembers the task tour in a LIFO way. This semantics means push
+and pop commands are needed. The push is performed by the \verb|task| command with a task argument.
+The pop is performed by the new command \verb|prevtask| or shorthand \verb|prev|.
+
+\subsection{Task Switching}
+The task argument for pushing is a relative id within a cluster or absolute address on any
+cluster. For instance, to switch from any task to task \verb|T2| seen in listing \ref{tasks}, the
+first command in listing \ref{task-addr-arguments} uses relative id (3) implicitly from the
+\verb|userCluster|, the second command uses an absolute address (\verb|0xad0070|), and the third
+command uses relative id (3) with the explicit \verb|userCluster|. Core functionality of these
+approaches is the same. Finally, the \verb|prevtask| command is used to unwind the stack until it is
+empty.
+\begin{lstlisting}[caption={task command arguments}, label={task-addr-arguments}, basicstyle=\small\tt]
+(gdb) task 3
+(gdb) task 0xad0070
+(gdb) task 3 userCluster
+(gdb) prevtask
+...
+(gdb) prev
+...
+(gdb) prev
+...
+(gdb) prev
+empty stack
+\end{lstlisting}
+
+
+\subsection{Switching Implementation}
+To implement the task tour, it is necessary to store the context information for every context
+switching. This requirement means the \verb|task| command needs to store this information every time
+it is invoked.
+
+\begin{figure}
+    \centering
+    \includegraphics[width=8cm]{uContext_stack}
+    \caption{Machine context (uMachContext) for each task}
+    \label{machine-context}
+
+\vspace*{0.5in}
+
+\begin{lstlisting}[style=Python, caption={Abridged \texttt{push\_task} source code}, label={pushtask-code}, basicstyle=\small\tt]
+# get GDB type of uContext_t *
+uContext_t_ptr_type = gdb.lookup_type('UPP::uMachContext::uContext_t').pointer()
+
+# retrieve the context object from a task and cast it to the type uContext_t *
+task_context = task['context'].cast(uContext_t_ptr_type)
+
+# the offset where sp would be starting from uSwitch function
+sp_address_offset = 48
+# lookup the value of stack pointer (sp), frame pointer (fp),
+# program counter (pc)
+xsp = task_context['SP'] + sp_address_offset
+xfp = task_context['FP']
+if not gdb.lookup_symbol('uSwitch'):
+    print('uSwitch symbol is unavailable')
+    return
+
+# This value is calculated here because we always here when the task is in
+# blocked state
+xpc = get_addr(gdb.parse_and_eval('uSwitch').address + 28)
+# must switch back to frame-0 to set 'pc' register with the value of xpc
+gdb.execute('select-frame 0')
+
+# retrieve register values and push sp, fp, pc into a global stack
+global STACK
+sp = gdb.parse_and_eval('$sp')
+fp = gdb.parse_and_eval('$fp')
+pc = gdb.parse_and_eval('$pc')
+stack_info = StackInfo(sp = sp, fp = fp, pc = pc)
+STACK.append(stack_info)
+
+# update registers for new task
+gdb.execute('set $rsp={}'.format(xsp))
+gdb.execute('set $rbp={}'.format(xfp))
+gdb.execute('set $pc={}'.format(xpc))
+\end{lstlisting}
+\end{figure}
+
+Figure \ref{machine-context} shows a task points to a structure containing a \verb|uContext_t| data
+structure, storing the stack and frame pointer, and the stack pointer. Listing \ref{pushtask-code}
+shows these pointers are copied into an instance of the Python tuple \verb|StackInfo| for every
+level of task switching. This tuple also stores information about the program counter that is
+calculated from the address of the \verb|uSwitch| assembly function because a task always stops in
+\verb|uSwitch| when its state is blocked.  Similarly, switching commands retrieve this context
+information but from the task that a user wants to switch to, and sets the equivalent registers to
+the new values.
+
+To push using the \verb|task| command, the value of the hardware stack pointer \verb|rsp| register,
+frame pointer \verb|rbp| register, and program counter register \verb|pc| are copied from the
+blocked task's save-area to the Python stack.  To pop using the \verb|prevtask| command, the three
+registers are moved from the Python stack to the appropriate hardware registers. Popping an empty
+stack prints a warning.
+
+Note, for tasks running when a breakpoint is encountered, the task's save-area is out-of-date; i.e.,
+the save area is only updated on a context switch, and a running task's stack represents the current
+unstored state for that task, which will be stored at the next context switch. Hence, to examine
+running tasks, it is necessary to use the GDB \verb|info threads| and \verb|thread| commands to
+examine and then step onto running tasks.
+
+Listing \ref{rr-tasks} shows how to examine ready and running tasks. Task \verb|T3| is ready (see
+Listing \ref{tasks}) because it was forced to context switch because of a time-slice preemption.
+Switching to \verb|T3|, which is relative id 4, and listing its the backtrace (stack frames) shows
+frames 0--6, which are the execution sequence for a time-slice preemption (and can be ignored), and
+frames 7--9, which are the frames at the point of preemption.  Frame 7 shows \verb|T3| is at line 14
+in the test program (see Listing \ref{uC-src-code}). Switching to running task \verb|T1|, which is
+relative id 2 (see Listing \ref{tasks}), and listing its backtrace shows a similar backtrace to
+ready task \verb|T3|. However, this backtrace contains stale information.  The GDB command
+\verb|info threads| shows the status of each kernel thread in the application, which represents the
+true location of each running thread. By observation, it can be seen that thread 2 is executing task
+\verb|0xa8fce0|, which is task \verb|T1|. Switching to kernel thread 2 via GDB command
+\verb|thread 2| and listing its backtrace show that task \verb|T1| is current executing at line 13
+in the test program.
+
+\begin{figure}
+\begin{lstlisting}[numbers=left, xleftmargin=3.0ex, caption={Examine ready/running tasks}, label={rr-tasks}, basicstyle=\footnotesize\tt]
+(gdb) task 4
+#0  T::f (this=0xa4f950, param=0) at test.cc:10
+(gdb) backtrace
+#0  uSwitch () at /u0/usystem/software/u++-7.0.0/src/kernel/uSwitch-x86_64.S:64
+#1  0x000000000042bd5c in uBaseCoroutine::taskCxtSw (this=0x8c9d28) ...
+#2  0x000000000042fff4 in UPP::uProcessorKernel::scheduleInternal ...
+#3  0x000000000042d4b6 in uBaseTask::uYieldInvoluntary ...
+#4  0x000000000042172f in uKernelModule::rollForward ...
+#5  0x000000000042f4fe in UPP::uSigHandlerModule::sigAlrmHandler ...
+#6  <signal handler called>
+#7  0x000000000041e620 in T::main (`this=0xb10400`) at test.cc:14
+#8  0x0000000000428de2 in UPP::uMachContext::invokeTask (This=...) ...
+#9  0x0000000000000000 in ?? ()
+(gdb) task 2
+(gdb) backtrace
+#0  uSwitch () at /u0/usystem/software/u++-7.0.0/src/kernel/uSwitch-x86_64.S:64
+#1  0x000000000042bd70 in uBaseCoroutine::taskCxtSw (this=0x8c9b68) ...
+#2  0x000000000042fff4 in UPP::uProcessorKernel::scheduleInternal ...
+#3  0x000000000042d4b6 in uBaseTask::uYieldInvoluntary ...
+#4  0x000000000042172f in uKernelModule::rollForward ...
+#5  0x000000000042f50c in UPP::uSigHandlerModule::sigAlrmHandler ...
+#6  <signal handler called>
+#7  0x000000000041e620 in T::main (`this=0xa8fce0`) at test.cc:14
+#8  0x0000000000428de2 in UPP::uMachContext::invokeTask (This=...) ...
+#9  0x0000000000000000 in ?? ()
+(gdb) info threads
+  Id Target Id                           Frame 
+  1  Thread 0x7ffff7fc8780 (LWP 7425) "a.out" 0x00007ffff6d74826 in ...
+  2  Thread 0x808080 (LWP 7923) "a.out"  0x41e5fc in T::main `(this=0xa8fce0`) at test.cc:13
+* 3  Thread 0x90a080 (LWP 7926) "a.out"  uSwitch () ...
+  4  Thread 0x98a080 (LWP 7929) "a.out"  T::main (this=0xad0070) at test.cc:14
+  5  Thread 0xa0b080 (LWP 7931) "a.out"  0x41e629 in T::main (this=0xc515d0) at test.cc:14
+(gdb) thread 2
+#1  0x000000000041e509 in T::f (this=0xa4f950, param=1) at test.cc:6
+6	        if ( param != 0 ) f( param - 1 );	// recursion
+[Switching to thread 2 (Thread 0x808080 (LWP 7923))]
+#0  0x000000000041e5fc in T::main (`this=0xa8fce0`) at test.cc:13
+13		    for ( volatile size_t i = 0; i < 1000000000; i += 1 ) // delay
+(gdb) backtrace
+#0  0x000000000041e5fc in T::main (`this=0xa8fce0`) at test.cc:13
+#1  0x0000000000428de2 in UPP::uMachContext::invokeTask (This=...) ...
+#2  0x0000000000000000 in ?? ()
+\end{lstlisting}
+\end{figure}
+
+\subsection{Continuing Implementation}
+When a breakpoint or error is encountered, all concurrent execution stops.  The state of the program
+can now be examined and changed; after which the program may be continued. Continuation must always
+occur from the top of the stack (current call) for each task, and at the specific task where GDB
+stopped execution.
+
+However, during a task tour, the new GDB commands change the notion of the task where execution
+stopped to make it possible to walk other stacks.  Hence, it is a requirement for continuation that
+the task walk always return to frame-0 of the original stopped task before any program continuation
+\cite{Reference11}.
+
+% For every new function call, a new stack frame is created and the values of all the registers are
+% changed for that frame. Therefore, in order to see the true value of hardware registers, innermost
+% frame that is frame-0 must be selected \cite{Reference11}. However, it is possible to not be in
+% frame-0, so prior to setting these values, the command must switch back to the innermost
+% (currently executing) frame first.
+
+To provide for this requirement, the original stop task is implicitly remembered, and there is a new
+\verb|reset| command that \emph{must} be explicitly executed before any continuation to restore the
+locate state.  To prevent errors from forgetting to call the \verb|reset| command, additional hooks
+are added to the existing built-in GDB continuation commands to implicitly call \verb|reset|. The
+following list of these commands results from GDB documentation \cite{Reference15} and similar work
+done for KOS \cite{Reference14}.
+\begin{lstlisting}[caption={Built-in GDB commands that allow continuation of a program}, label={continue-cmds}, basicstyle=\small\tt]
+continue,next,nexti,step,stepi,finish,advance,jump,signal,until,run,thread,
+reverse-next,reverse-step,reverse-stepi,reverse-continue,reverse-finish
+\end{lstlisting}
+
+% These hooks call a new command called \verb|reset| prior to executing the command to enable
+% continuation of a program to ensure that the program's context is automatically switched back to
+% the context of the task that initiates the first context switch. The \verb|reset| command behaves
+% as same as the command \verb|prevtask|, however, it goes back directly to where the task is when
+% the program last stops, which is the first task in the task tour.
+
+\section{Result}
+The current implementation successfully allows users to display a snapshot of \uC execution with
+respect to clusters, processors, and tasks. With this information it is possible to tour the call
+stacks of the tasks to see execution locations and data values. Additionally, users are allowed to
+continue the execution where the program last pauses assuming that the program has not crashed. The
+continuation of execution is done by automatically reversing the task walk from any existing GDB
+commands such as \verb|continue|, or a user can manually reverse the task walk using the command
+\verb|prevtask| and then continue.
