One of the more useful features of kdb is its ability to print the
arguments to functions, unlike the kernel which only prints an
approximation of the function backtrace. The current kdb backtrace
does not cope with i386 parameters in registers (i386 built with
-mregparm=3), nor does it cope with x86_64 where the ABI mandates that
the first 6 parameters are passed in registers. I will be rewriting
the backtrace code for i386/x86_64 to cope with parameters in
kdb cannot rely on unwind data in the .eh_frame section. i386 has only
just added that data (2.6.17-rc1), not all kernels are built with
CONFIG_UNWIND_INFO but worst of all, CONFIG_UNWIND_INFO=y does not
actually track where parameters are stored.
gcc can copy arguments between registers, it can store arguments in
local stack space and it can restore them to other registers later.
gcc can even reuse argument registers when the argument is no longer
required, printing such registers as arguments can lead to some very
ambiguous backtraces and great user confusion.
To track the parameters, you have to compile the entire kernel with -g,
and load that data for kdb to use. Compiling with -g increases the
kernel size by a factor of 5. Without -g, a reasonably small i386
vmlinux is 6760001, with -g it is 33209257, too much wasted space for
my liking. Not to mention that there is no useful debugging data for
assembler routines such as interrupt handlers, nor for the out of line
spinlock contention paths.
The current kdb backtrace routines already do partial code analysis at
run time to work out stack sizes, to validate the guesses at where
the return address is stored on stack and to handle all the special
case hand crafted assembler code that we have in the kernel. The
rewrite will go one stage further and do full code analysis, including
tracking parameters as gcc moves them around.
For each function in the backtrace, kdb will break it down into basic
blocks and calculate the state on entry to and exit from each basic
block. kdb will then use that state to locate the arguments, or to
report that they have been overwritten. The state is also used to
track the size of the stack, as a nice side effect this guarantees that
we find the correct return address on stack and do not get fooled by
stale kernel pointers on stack.
A basic block (BB) starts at the beginning of the function or at any
instruction that is the target of a branch instruction within the
current function. A call to another function does not affect the
current BB, except to invalidate some registers. A branch to an
instruction outside the current function is ignored, these occur for
tail recursion and for the out of line spinlock contention paths,
neither of which affect the state of the current BB.
A BB ends with an unconditional branch, a RET, LEAVE or UD2
instruction, or by dropping through to the next BB (the next line is
the target of a branch instruction). A BB can also exit sideways via a
A state record contains data such as :-
The offset of the current stack pointer from the original value on
Where the original stack pointer was saved. This is preferred to the
adjusted stack pointer, but only if the kernel is compiled with frame
pointers and we have actually executed the instruction that saves the
original stack pointer.
For each argument, where it is currently held or a note that it has
been overwritten. An argument can exist in multiple locations at the
same time, the status of all of these locations must be tracked
because kdb does not know which will be used later and which will be
Phase 1 runs the current function to identify the basic blocks and the
branch instructions that link them together. This forms a directed
graph, which may or may not have cycles. For each BB, count the number
of ways that it can be entered and reserve enough space to point to the
state records for each of those entries, plus one more.
Phase 2 runs the directed graph, doing backtracking as cycles are
detected. kdb starts off by assuming that i386 routines are compiled
with -mregparm=3, and that x86_64 routines follow the ABI and pass 6
parameters in registers. Each BB is disassembled and the effect of
each instruction is reflected in the state record, but only if the
instruction changes any of the state that kdb cares about. At each
exit point from the BB, the current state record is saved to form the
input to the next BB in the graph.
Phase 3 reconciles the input state when a BB has more than one entry
point. One path to a BB may overwrite an argument, another path to the
same BB may leave the argument alone. Reconciliation takes the lowest
state for that argument and says that the argument is not valid on
entry to the BB. Compiler theory 101, if two paths to a BB have an
argument in an inconsistent state then the BB cannot be using the
argument. It should be possible to fold the state reconciliation into
the phase 2 processing, but treat it as a separate phase for clarity.
Phase 4 calculates the number of arguments and works out how they are
passed to this function. kdb does not know how many parameters are
passed, it does not even know whether arguments to this function are in
registers or on stack, some functions always get parameters on stack
even when the kernel is compiled with -mregparm=3. If any BB reads
from an argument register without first writing to that register then
it must contain an argument, and all preceding argument registers are
also in use. If a BB reads from the stack above the location
containing the return address then it is reading an argument that was
passed on stack, all locations between that address and the return
address also contain arguments. This algorithm is not perfect,
function(a, b, c, d) compiled with -mregparm=3 and where only d is
used, will appear to have one argument that was passed on stack.
Fortunately we do not write code that bad.
Finally identify the starting state of the BB containing the current
instruction pointer and calculate the argument state at the instruction
pointer. Print the function and all arguments that kdb is confident
Extract the return pointer from the stack. With full code analysis kdb
knows exactly where this is stored, which removes any ambiguity caused
by stale kernel pointers that are still on stack. This return address
becomes the starting point for decoding the next function up the call
tree, back to phase 1.
Even with this algorithm, kdb will still need special case code for
some of the assembler routines and for out of line code. No big deal,
it is a Kernel DeBugger after all :).
Use http://oss.sgi.com/ecartis to modify your settings or to unsubscribe.