Index: doc/theses/lynn_tran_SE499/Chapters/CFA.tex =================================================================== --- doc/theses/lynn_tran_SE499/Chapters/CFA.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) +++ doc/theses/lynn_tran_SE499/Chapters/CFA.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) @@ -0,0 +1,100 @@ +\chapter{\CFA} \label{CFA} + +\section{Introduction} +Similar to \CC, C is a popular programming language especially in systems +programming. For example, the Windows NT and Linux kernel are written in C, and they are the foundation of many higher level +and popular projects. Therefore, it is unlikely that the programming language C is +going to disappear any time soon. + +However, C has inherent problems in syntax, semantics and many +more \cite{Reference2}. Even though \CC is meant to fix these problems, \CC has many +irreversible legacy design choices, and newer versions of \CC require significantly more effort to convert C-based projects into \CC. + +To solve this problem, the programming language \CFA is being created at the University of Waterloo. The goal +of the language is to extend C with modern language features that many new +languages have, such as Rust and Go. Hence, the \CFA extension provides a +backward-compatible version of C, while fixing existing problems known in C and +modernizing the language at the same time. + +\section{Overloading} +Overloading is when a compiler permits a name to have multiple meanings. All +programming languages allow simple overloading of operators on basic types such +as the \verb|+| operator (add) on integer and floating-point types. Most programming languages extend +overloading of operators to user-defined types and/or general function +overloading. \CFA also supports overloading of variables and the literals \verb|0/1|. + +\subsection{Variable} +Variables in the same block are allowed to have the same name but different +types. An assignment to a new variable uses that variable's type to infer the +required type, and that type is used to select a variable containing the appropriate type. + +\begin{lstlisting}[numbers=left, xleftmargin=3.0ex, style=C++nokeyword, caption={Overloading variables in \CFA}, label={CFA-overload-var}] +short int MAX = SHRT_MAX; +int MAX = INT_MAX; +double MAX = DBL_MAX; + +// select variable MAX based on its left-hand type +short int s = MAX; // s = SHRT_MAX +int s = MAX; // s = INT_MAX +double s = MAX; // s = DBL_MAX +\end{lstlisting} + +The listing \ref{CFA-overload-var} shows that when variable overloading exists +in the same scope, the variable is selected based on the left side of +initialization/assignment and operands of the right side of the expression. For +instance, the first assignment to variable \verb|s| at line 6, which is type short int, +selects the MAX with the same type. + +\subsection{Function} +Functions in the same block can be overloaded depending on the number and type of +parameters and returns. + +\begin{lstlisting}[numbers=left, xleftmargin=3.0ex, style=C++nokeyword, caption={Overloading routines in \CFA}, +label={CFA-overload-func}] +void f(<@\textcolor{red}{void}@>); // (1) +void f(<@\textcolor{red}{char}@>); // (2) +<@\textcolor{red}{char}@> f(void); // (3) +<@\textcolor{red}{[int,double]}@> f(); // (4) + +f(); // pick (1) +f('a'); // pick (2) +char s = f('a'); // pick (3) +[int, double] s = f(); // pick (4) +\end{lstlisting} + +The listing \ref{CFA-overload-func} shows that when many functions are overloaded in +the same scope, a function is selected based on the combination of its return type and its +arguments. For instance, from line 1-4, four different types of a function called +\verb|f| are declared. For the call \verb|f('a')|, the function selected is the +one on line 2, if the call voids the result. However, if the call assigns to a +char, then the routine on line 3 is selected. This example can be seen on lines +7-8. + +\subsection{Operator} +An operator name is denoted with \verb|?| for the operand and any standard C +operator. Operator names within the same block can be overloaded depending on +the number and type of parameters and returns. However, operators \verb|&&|, +\verb-||-, \verb|?:| cannot be overloaded because short-circuit semantics +cannot be preserved. + + +\begin{lstlisting}[style=C++nokeyword, caption={Overloading operators in \CFA}, +label={CFA-overload-ops}] +int <@\textcolor{red}{++?}@>(int op); // unary prefix increment +int <@\textcolor{red}{?++}@>(int op); // unary postfix increment +int <@\textcolor{red}{?+?}@>(int op1, int op2); // unary postfix increment + +struct S { double x, double y } + +// overload operator plus-assignment +S <@\textcolor{red}{?+?}@>(S a, S b) { + return (S) {a.x + b.x, a.y + b.y}; +} + +S a, b, c; +a + b + c; +\end{lstlisting} + +The listing \ref{CFA-overload-ops} shows that operator overloading is permitted +similar to \CC. However, the difference is that the operator name is +denoted with \verb|?| instead, and operator selection uses the return type. Index: doc/theses/lynn_tran_SE499/Chapters/Conclusion.tex =================================================================== --- doc/theses/lynn_tran_SE499/Chapters/Conclusion.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) +++ doc/theses/lynn_tran_SE499/Chapters/Conclusion.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) @@ -0,0 +1,10 @@ +\chapter{Conclusion} +New GDB extensions are created to support information display and touring among +\uC user tasks, and new hooks are added to the GNU Debugger to support a +\CFA demangler. The GDB extensions are implemented using the Python API, and +the hooks to add debugging support for \CFA are implemented using \uC. For +the GDB extensions, writing Python extensions is easier and more robust. +Furthermore, GDB provides sufficient hooks to make it possible for a new +language to leverage existing infrastructure and codebase to add debugging +support. The result provides significantly new capabilities for examining and +debugging both \uC and \CFA programs. Index: doc/theses/lynn_tran_SE499/Chapters/Demangler.tex =================================================================== --- doc/theses/lynn_tran_SE499/Chapters/Demangler.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) +++ doc/theses/lynn_tran_SE499/Chapters/Demangler.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) @@ -0,0 +1,195 @@ +\chapter{\CFA Demangler} \label{demangler} + +\section{Introduction} +While \CFA is a translator for additional features that C does not support, +all the extensions compiled down to C code. As a result, the executable file +marks the DWARF tag \verb|DW_AT_language| with the fixed hexadecimal value for +the C language. Because it is possible to have one frame in C code and another +frame in Assembly code, GDB encodes a language flag for each frame. \CFA adds +to this list, as it is essential to know when a stack frame contains mangled +names versus C and assembler unmangled names. Thus, GDB must be told \CFA is a +distinct source-language. + +\section{Design Constraints} +Most GDB targets use the DWARF format. The GDB DWARF reader initializes all +the appropriate information read from the DIE structures in object or +executable files, as mentioned in Chapter \ref{GDB}. However, GDB currently +does not understand the new DWARF language-code assigned to the language \CFA, +so the DWARF reader must be updated to recognize \CFA. + +Additionally, when a user enters a name into GDB, GDB needs to lookup if the +name exists in the program. However, different languages may have different +hierarchical structure for dynamic scope, so an implementation for nonlocal +symbol lookup is required, so an appropriate name lookup routine must be added. + +\section{Implementation} +Most of the implementation work discussed below is from reading GDB's internals +wiki page and understanding how other languages are supported in GDB \cite{Reference5}. + +A new entry is added to GDB's list of language definition in +\verb|gdb/defs.h|. Hence, a new instance of type \verb|struct language_def| +must be created to add a language definition for \CFA. This instance is the +entry point for new functions that are only applicable to \CFA. These new +functions are invoked by GDB during debugging if there are operations that are +applicable specifically to \CFA. For instance, \CFA can implement its own +symbol lookup function for non-local variables because \CFA can have a +different scope hierarchy. The final step for registering \CFA in GDB, as a +new source language, is adding the instance of type \verb|struct language_def| +into the list of language definitions, which is found in +\verb|gdb/language.h|. This setup is shown in listing \ref{cfa-lang-def}. + +\begin{figure} +\begin{lstlisting}[style=C++, caption={Language definition declaration for +\CFA}, label={cfa-lang-def}, basicstyle=\small] +// In gdb/language.h +extern const struct language_defn cforall_language_defn; + +// In gdb/language.c +static const struct language_defn *languages[] = { + &unknown_language_defn, + &auto_language_defn, + &c_language_defn, + ... + &cforall_language_defn, + ... + } + +// In gdb/cforall-lang.c +extern const struct language_defn cforall_language_defn = { + "cforall", /* Language name */ + "CForAll", /* Natural name */ + language_cforall, + range_check_off, + case_sensitive_on, + ... + cp_lookup_symbol_nonlocal, /* lookup_symbol_nonlocal */ + ... + cforall_demangle, /* Language specific demangler */ + cforall_sniff_from_mangled_name, + .. +} +\end{lstlisting} +\end{figure} + +The next step is updating the DWARF reader, so the reader can translate the +DWARF code to an enum value defined above. However, this assumes that the +language has an assigned language code. The language code is a hexadecimal +literal value assigned to a particular language, which is maintained by +GCC. For \CFA, the hexadecimal value \verb|0x0025| is added to +\verb|include/dwarf2.h| to denote \CFA, which is shown in listing +\ref{cfa-dwarf}. +\begin{lstlisting}[style=C++, caption={DWARF language code for \CFA}, +label={cfa-dwarf}, basicstyle=\small] +// In include/dwarf2.h +enum dwarf_source_language { // Source language names and codes. + DW_LANG_C89 = 0x0001, + ... + DW_LANG_CForAll = 0x0025, +} +\end{lstlisting} + +Once the demangler implementation goes into the \verb|libiberty| directory +along with other demanglers, the demangler can be called by updating the +language definition defined in listing \ref{cfa-lang-def} with the entry point +of the \CFA demangler, and adding a check if the current demangling style is +\verb|CFORALL_DEMANGLING| as seen in listing \ref{cfa-demangler}. GDB then +automatically invokes this \CFA demangler when GDB detects the source language +is \CFA. In addition to the automatic invocation of the demangler, GDB provides +an option to manually set which demangling style to use in the command line +interface. This option can be turned on for \CFA in GDB by adding a new enum +value for \CFA in the list of demangling styles along with setting the +appropriate mask for this style in \verb|include/demangle.h|. After doing this +step, users can now choose if they want to use the \CFA demangler in GDB by +calling \verb|set demangle-style |, where the language name is +defined by the preprocessor macro \verb|CFORALL_DEMANGLING_STYLE_STRING| in +listing \ref{cfa-demangler-style}. + +\begin{figure} +\begin{lstlisting}[style=C++, caption={libiberty setup for the \CFA demangler}, +label={cfa-demangler}, basicstyle=\small] +// In libiberty/cplus-dem.c +const struct demangler_engine libiberty_demanglers[] = { + { + NO_DEMANGLING_STYLE_STRING, + no_demangling, + "Demangling disabled" + }, + ... + { + CFORALL_DEMANGLING_STYLE_STRING, + cforall_demangling, + "Cforall style demangling" + }, +} +... +char * cplus_demangle(const char *mangled, int options) { + ... + /* The V3 ABI demangling is implemented elsewhere. */ + if (GNU_V3_DEMANGLING || RUST_DEMANGLING || AUTO_DEMANGLING) { ... } + ... + if (CFORALL_DEMANGLING) { + ret = cforall_demangle (mangled, options); + if (ret) { return ret; } + } +} +\end{lstlisting} + +\begin{lstlisting}[style=C++, caption={Setup \CFA demangler style}, +label={cfa-demangler-style}, basicstyle=\small] +// In gdb/demangle.h +#define DMGL_CFORALL (1 << 18) +... +/* If none are set, use 'current_demangling_style' as the default. */ +#define DMGL_STYLE_MASK +(DMGL_AUTO|DMGL_GNU|DMGL_LUCID|DMGL_ARM|DMGL_HP|DMGL_EDG|DMGL_GNU_V3 +|DMGL_JAVA|DMGL_GNAT|DMGL_DLANG|DMGL_RUST|DMGL_CFORALL) +... +extern enum demangling_styles { + no_demangling = -1, + unknown_demangling = 0, + ... + cforall_demangling = DMGL_CFORALL +} current_demangling_style; +... +#define CFORALL_DEMANGLING_STYLE_STRING "cforall" +... +#define CFORALL_DEMANGLING (((int)CURRENT_DEMANGLING_STYLE)&DMGL_CFORALL) +\end{lstlisting} +\end{figure} + +However, the setup for the \CFA demangler above does not demangle mangled +symbols during symbol-table lookup while the program is in progress. Therefore, +additional work needs to be done in \verb|gdb/symtab.c|. Prior to looking up +the symbol, GDB attempts to demangle the name of the symbol, which can either +be a mangled or unmangled name, to see if it can detect the language, and select +the appropriate demangler to demangle the symbol. This work enables invocation +of the \CFA demangler during symbol lookup. +\begin{lstlisting}[style=C++, caption={\CFA demangler setup for symbol lookup}, +label={cfa-symstab-setup}, basicstyle=\small] +// In gdb/symtab.c +const char * demangle_for_lookup ( const char *name, enum language lang, + demangle_result_storage &storage ) { + /* When using C++, D, or Go, demangle the name before doing a + lookup to use the binary search. */ + if (lang == language_cplus) { + char *demangled_name = gdb_demangle(name, DMGL_ANSI|DMGL_PARAMS); + if (demangled_name != NULL) + return storage.set_malloc_ptr (demangled_name); + } + ... + else if (lang == language_cforall) { + char *demangled_name = cforall_demangle (name, 0); + if (demangled_name != NULL) + return storage.set_malloc_ptr (demangled_name); + } + ... +} +\end{lstlisting} + +\section{Result} +The addition of hooks throughout GDB enables the invocation of the new \CFA +demangler during symbol lookup and during the usage of \verb|binutils| tools +such as \verb|objdump| and \verb|nm|. Additionally, these \verb|binutils| tools +also understand \CFA because of the addition of the \CFA language code. +However, as the language develops, symbol lookup for non-local variables must +be implemented to produce the correct output. 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 +#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 +#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. Index: doc/theses/lynn_tran_SE499/Chapters/GDB.tex =================================================================== --- doc/theses/lynn_tran_SE499/Chapters/GDB.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) +++ doc/theses/lynn_tran_SE499/Chapters/GDB.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) @@ -0,0 +1,73 @@ +\chapter{GNU Debugger} \label{GDB} + +\section{Introduction} +The GNU Project Debugger is a program that allows examination of what is going on +inside another program while it executes, or examines the state of a program +after it crashed \cite{Reference3}. + +\section{Debug Information} +In order to allow effective inspection of program state, the +debugger requires debugging information for a program. Debugging +information is a collection of data generated by a compiler and/or an assembler +program. This information is optional as it is only required for compilation, +and hence, it is normally not present during program execution when debugging +occurs. When requested, debugging information is stored in an object file, and it describes +information such as the type of each variable or function and +the correspondence between source line numbers and addresses in the executable +code \cite{Reference6}. Debugging information is requested via the \verb|-g| +flag during the compilation stage of the +program. + +The debugging information must be written out in a canonical format for +debuggers to read. DWARF is one of the supported debugging data formats, and its architecture is +independent and applicable to any language, operating system, or processor \cite{Reference7}. This format uses a data structure called DIE to represent +each variable, type, function, etc. A DIE is a pair: tag +and its attribute \cite{Reference8}. + +\section{Stack-Frame Information} +A stack frame, or frame for short, is a collection of all data associated with +one function call. A frame consists of parameters received from the function call, local variables declared in that +function, and the address where the +function returns. The frame-pointer register stores the address of a frame, +during execution of a call. A call stack can have many frames \cite{Reference12}. + +\section{Extending GDB} +GDB provides three mechanisms for extending itself. The first is +composition of GDB commands, the second is using the Python GDB API, and the third is defining new aliases for existing commands. + +\section{Symbol Handling} +Symbols are a key part of GDB's operation. Symbols can be variables, functions and +types. GDB has three kinds of symbol tables: +\begin{itemize} + \item \textcolor{ForestGreen}{Full symbol-tables (symtabs)}: These contain the main information + about symbols and addresses + \item \textcolor{ForestGreen} {Partial symbol-tables (psymtabs)}: These contain enough information to + know when to read the corresponding part of the full symbol-table. + \item \textcolor{ForestGreen}{Minimal symbol-tables (msymtabs)}: These + contain information extracted from non-debugging symbols. +\end{itemize} + +Debugging information for a large program can be very large, and reading all of +these symbols can be a performance bottleneck in GDB, affecting the user +experience. The solution is to lazily construct partial symbol-tables consisting of +only selected symbols, and then eagerly expand them to full symbol-tables when +necessary. +The psymtabs is constructed by doing a quick pass over the executable file's +debugging information. + +\section{Name Demangling in GDB} +The library \verb|libiberty| provides many functions and features that can be +divided into three groups: +\begin{itemize} + \item \textcolor{ForestGreen}{Supplemental functions}: additional functions + that may be missing in + the underlying operating system. + \item \textcolor{ForestGreen}{Replacement functions}: simple and unified equivalent functions for + commonly used standard functions. + \item \textcolor{ForestGreen}{Extensions}: additional functions beyond the standard. +\end{itemize} + +In particular, this library provides the \CC demangler that is used in GDB and +by \uC. A new +demangler can also be added in this library, which is what Rust did, and what +is necessary for \CFA. Index: doc/theses/lynn_tran_SE499/Chapters/Introduction.tex =================================================================== --- doc/theses/lynn_tran_SE499/Chapters/Introduction.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) +++ doc/theses/lynn_tran_SE499/Chapters/Introduction.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) @@ -0,0 +1,67 @@ +\chapter{Introduction} \label{introduction} +Computer programming languages provide humans a means to instruct computers to +perform a particular task. New programming languages are +invented to simplify the task, or provide additional features, enhance +performance, and improve developer productivity. + +A crucial companion tool to a programming language is a debugger. A debugger is a productivity tool to aid developers in testing +and finding bugs in a program. By definition, a debugger executes +any program written in one of a supported set of languages and allows developers +to stop, monitor and examine state in the program for further investigation. + +Specifically, this report talks about how to add GNU Debugger (GDB) support for the +concurrent programming-languages \uC and \CFA. +Both languages provide an $M$:$N$ concurrency model, where $M$ user-level threads +execute on $N$ kernel-level threads. +Often debuggers either do not know about concurrency or only provide a simple +understanding of concurrency provided by the operating system (kernel threads). +For \CFA, new hooks are also added to allow GDB to understand that +\CFA is a new source language that requires invocation of a demangler for +variable and function names. + +Because \uC is a translator, all the code written in \uC is eventually +compiled down to \CC code. This transformation gives \uC an advantage with +GDB because GDB already understands \CC. However, since \uC introduced new objects +and high-level execution constructs into the language, GDB does not understand +these objects or the runtime environment. One objective of this +project is to write new GDB extensions to understand concurrency among tasks, a new high-level execution construct that is discussed more in Chapter \ref{uC}. + +Additionally, if a programming language provides overloading functionality, +which allows functions or variables in the same scope with the +same identifier, then each of these entities must be assigned a unique name, otherwise, +there are name collisions. + +However, uniquely numbering (naming) overloads is impossible with separate +compilation, because the compiler does not have access to all translation +units. Therefore, it is necessary to adopt a scheme related to the overloading +mechanism for unique naming. For example, if a language uses the number and +types of function parameters to disambiguate function names, than the number +and parameter types are encoded into the name: +\begin{lstlisting}[basicstyle=\normalfont\tt] +void f( int i, double d, char c ); // f_3_i_d_c +void f( int i, char c ); // f_2_i_c +\end{lstlisting} +Here, the mangled names for \lstinline@f@ contain the number of parameters and a code for +each parameter type. For a complex type-system, the type codes become +correspondingly complex, e.g., a generic structure. These names are now unique +across all translation units. + +Unfortunately, a debugger only has access to the mangled names in a compiled +translation units, versus the unmangled names in the program. Therefore, the +debugger can only look up mangled names versus original program names, which +makes debugging extremely difficult for programmers. To solve this program, the +language must provide the debugger with a "demangled" so it can convert +mangled names back to program names, and correspondingly retrieve the type of +the name~\cite{Reference9}. + +\CFA, a new language being developed at the University of Waterloo, has +overloading, so names resolved by the debugger are mangled names. Therefore, +another objective of this project is to add a \CFA demangler to GDB. + +% Name mangling is a technique used in compilers to resolve this +% problem. This technique provides a mechanism to encode additional information in the +% name of a function, or a variable to supply more semantic information from +% compiler to debugger \cite{Reference9}. \CFA, a new language being developed at the University of +% Waterloo, has overloading, so names resolved from +% the debugger are mangled names. As with early versions of \CC, it is not user-friendly to debug a program using +% mangled names. Therefore, another objective of this project is to add a \CFA demangler in GDB. Index: doc/theses/lynn_tran_SE499/Chapters/uCPP.tex =================================================================== --- doc/theses/lynn_tran_SE499/Chapters/uCPP.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) +++ doc/theses/lynn_tran_SE499/Chapters/uCPP.tex (revision 1b34b87a9432a5a2b3a787f7ef8ccb7e2dcc7c16) @@ -0,0 +1,46 @@ +\chapter{\uC} \label{uC} + +\section{Introduction} +\uC \cite{Reference10} extends the \CC programming language with new +mechanisms to +facilitate control flow, and adds new objects to enable lightweight concurrency +on uniprocessor and parallel execution on multiprocessor computers. Concurrency has tasks +that can context switch, which is a control transfer from one execution state to +another that is different from a function call. Tasks are selected to run on a +processor from a ready queue of available tasks, and tasks may need to wait for an occurrence of an event. + +\section{Tasks} +A \textcolor{ForestGreen}{task} behaves like a class object, but it maintains its own +thread and execution state, which is the state information required to allow +independent execution. A task provides mutual exclusion by default for calls to its +public members. Public members allow communication among tasks. + +\section{\uC Runtime Structure} +\uC introduces two new runtime entities for controlling concurrent execution: +\begin{itemize} + \item Cluster + \item Virtual processor +\end{itemize} + +\subsection{Cluster} +A cluster is a group of tasks and virtual processors (discussed next) that +execute tasks. The objective of a cluster is to control the amount of possible +parallelism among tasks, which is only feasible if there are multiple +hardware processors (cores). + +At the start of a \uC program, two clusters are created. One is the system +cluster and the other is the user cluster. The system cluster has a processor +that only performs management work such as error detection and correction from +user clusters, if an execution in a user cluster results in errors, and cleans +up at shutdown. The user cluster manages and executes user tasks on its +processors. The benefits of clusters are maximizing utilization of processors +and minimizing runtime through a scheduler that is appropriate for a particular +workload. Tasks and virtual processors may be migrated among clusters. + +\subsection{Virtual Processor} +A virtual processor is a software emulation of a processor that executes +threads. Kernel threads are used to implement a virtual processor, which are +scheduled for execution on a hardware processor by the underlying operating +system. The operating system distributes kernel threads across a number of +processors assuming that the program runs on a multiprocessor architecture. The +usage of kernel threads enables parallel execution in \uC.