The Heinsenburg Debugging Technology

The Implementation of Introspect

In embedded systems development, the debugger and the program being debugged are often separated by a relatively slow serial channel. In this case it is especially important to have a trace collection agent that is separate from the debugger, and resides on the target side's of the serial channel. The debugger handles interactive requests --- creating tracepoints, examining trace events --- while the trace collection agent handles the actual runtime collection of the trace data.

This target-side agent needs its own local tables describing the tracepoints (code locations, what to collect, and so on), and its own local buffers in which to store the collected data, so that it does not need to interact with the debugger in any way while the trace experiment is running. It isis is desirable to consume as little target memory and interrupt the user program for as short a time as possible, so the agent should not parse source language expressions or look up symbols. Therefore, we make the debugger download a highly simplified version of the trace experiment to the target-side agent, with all symbols replaced by addresses, registers and offsets, and all expressions compiled into a compact and efficient bytecode language.

The trace buffer itself is organized as a log of tracepoint events; each log entry records the data collected when the program reached a tracepoint. When the user selects a tracepoint event to examine, the target-side agent acts as a server, feeding the collected data back to the debugger on request.

In this example, each time the program reaches the tracepoint at the beginning of the 'find' function, the GDB agent must record the contents of the tree node, and then evaluate the expression:

tree->vector.p[tree->vector.n - 1]

to find the element of the vector to record.

Evaluating this expression is a non-trivial task. In order to find the expression's value, one needs to know:

• The syntax of C expressions, to parse our expression
• The list of arguments and local variables for 'find', to help us associate the identifier 'tree' with a specific variable in the program
• The location of the argument 'tree', whether in a register or on the stack,
• The types of 'tree', 'tree->vector', 'tree->vector.p', and so on, so one can find the offsets of members within their structures, scale integer values appropriately for pointer arithmetic, and so on
• Knowledge of C expression semantics, to help us execute the various operators.

Representing this sort of information requires relatively large and complex data structures, and code for lexical analysis and parsing can be bulky. Although GDB has all this information readily available, since it is a source-level debugger, such complexity is

usually beyond the scope of the GDB agent, which must execute on a target machine with limited resources.

So, the critical question is: How can Introspect accept arbitrary source-level expressions from user at debug time, and evaluate them on the target system using only a small amount of code and as quickly as possible?

The solution is to make the agent responsible for carrying out only machine-level operations --- loads, register references, two's-complement arithmetic, and so on --- and to isolate all symbolic processing in the debugger, which has the necessary information and resources. When the user gives GDB a tracepoint expression, GDB compiles it to a simple machine-independent bytecode language, and sends the bytecode to the agent for evaluation.

The vocabulary of machine-level operations needed to evaluate C expressions is rather small. The current bytecode interpreter understands around forty bytecodes, each of which is implemented by a line or two of C code. The interpreter, including error checking code, occupies three kilobytes of code on the target machine.

Consider the first expression collected in the example above:

*tree

In the 'find' function, 'tree' is the first argument. For the SPARC, GDB might compile this expression to the following bytecode sequence:

reg 8

const8 16

trace

end

The bytecode engine maintains a stack of values, which is empty when evaluation begins. Most instructions pop an argument or two off the stack, perform some operation on them, and push the result back on the stack, where the next instruction can find it. Taking each of the instructions above in turn:

reg 8

This bytecode pushes the value of register number eight on the stack. (Each stack element is as wide as the largest value the processor directly supports.) In our example, GDB knows that 'tree' lives in register eight, so this instruction pushes the value of 'tree' on the stack.

const8 16

This bytecode pushes the constant value 16 on the stack. The '8' in the instruction's name indicates that its operand is a single byte long; there are bytecode instructions named 'const16' and 'const32', for pushing larger instructions. In our example, GDB

knows that the structure is sixteen bytes long, so this instruction pushes the size of '*tree' on the stack.

trace

This bytecode pops an address and a length from the stack, and records that memory in the tracepoint event log. In our example, the stack contains the 'tree' pointer, and the size of the node to which it points, so this instruction will record the full contents of that node. The trace instruction does not assume that the address is valid; if the interpreter gets a memory access fault when it attempts to record the value, it aborts execution of that expression.

end

This instruction tells the engine to stop executing, marking the end of the bytecode expression.

In addition to the bytecode expression, GDB also sends the agent a mask of the registers the expression uses. When the agent hits a tracepoint, it records all the specified registers, in addition to running the bytecode expressions.

Thus, after evaluating this expression, the agent will have saved the value of register eight and the contents of the tree node in the event log. This gives us both the value of the pointer "tree", and the value of the node that it points to. Later, if the user selects this tracepoint event and asks GDB to "print *tree", GDB will:

1) Ask the target agent for the value of register 8 (the pointer "tree"), and then

2) Ask the target agent for the contents of memory at the address pointed to by the value it just fetched (the tree node).

Since both values are in the trace buffer, both requests will succeed, and the expression "*tree" will be printed successfully.

Let's consider a more complex example:

tree->vector.p[tree->vector.n - 1]

GDB will compile this expression to the bytecode:

reg 8

const8 8

These instructions push the value of 'tree' on the stack, followed by the constant value 8.

add

The 'add' instruction pops the top two values off the stack (in this case, 'tree' and 8), adds them, and pushes the sum on the stack. This computes the address of 'tree->vector', since 'offsetof (struct tree, vector)' is eight.

trace_quick 4

This bytecode logs the value of the 'n' bytes whose address is on the top of the stack, without disturbing the stack. In our case, the top of the stack is the address of 'tree->vector', which is a pointer; since pointers are four bytes long on our target architecture, this records the value of 'tree->vector' in the event log. Like 'trace', it aborts evaluation of the expression if the address is invalid.

ref32

This bytecode pops an address off the stack, and pushes the contents of the 32-bit word it points to. Thus, the stack now contains the value of 'tree->vector', which is the address of the node's 'struct vector'. (Naturally, there are analogous instructions, 'ref16' and 'ref8', for fetching values of other sizes.)

const8 4

add

trace_quick 4

ref32

These instructions compute the address of 'tree->vector.p', record its contents in the event log, and leave its value on the top of the stack. At this point, the value of 'tree->vector.p' is the only thing on the stack.

reg 8

const8 8

add

trace_quick 4

ref32

trace_quick 4

ref32

These instructions do the same for 'tree->vector.n'; since 'n' is the first element of a 'struct vector', its offset is zero, and we do not need to generate an 'add' bytecode. At this point, the stack contains 'tree->vector.p' (on the bottom) and 'tree->vector.n' (on top).

const8 1

sub

The 'sub' instruction pops the top two values off the stack, subtracts the first from the second, and pushes their difference back on the stack. Thus, these instructions subtract one from the top of the stack, yielding 'tree->vector.n - 1'.

const8 16

mul

add

The C language's rules for pointer arithmetic state that, when we add a pointer to an integer, we must first multiply the integer by the size of the object pointed to. These bytecodes carry out that scaling operation, and then perform the addition.

The top of the stack now contains the address of 'tree->vector.p[tree->vector.n - 1]', which is a 'struct point'.

const8 16

trace

end

A 'struct point' is sixteen bytes long, containing two doubles. We record the value of the 'struct point' whose address is on the top of the stack, and exit.

There are several things to note about this example.

• Information implicit in the source code (the size of a 'struct tree'; the offset of 'p' within a 'struct vector') is made explicit in the bytecode. This means the agent does not need information about the expression's context --- types, scopes, etc. --- in order to evaluate it.
• The expression records not just the final value of the expression, but any data touched in the process of evaluating it. Thus, when GDB evaluates the same expression itself, everything it needs is sure to be in the agent's buffer.
• The expression only records the values it actually touches. For example, since this expression does not reference 'tree->left' or 'tree->right', those values will not be in the trace buffer. (In the example session above, we actually collected '*tree' as well, so tree->left and tree->right were available.)
• There are bytecodes available for manipulating 64-bit values, on those targets that support them. This example was created on a 32-bit machine, so the 64-bit instructions do not appear.