source: doc/theses/lynn_tran_SE499/Chapters/Extensions.tex @ b4b63e8

\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.