Re: [Libunwind-devel] Getting parameters on x86_64 as part of backtrace

[Keith Owens]

Bala Narasimhan (on Tue, 29 Apr 2008 08:34:27 -0700 (PDT)) wrote:
>Hi All,
>I have been trying to use libunwind to get a backtrace, along with
>parameters to the routines, on x86_64. I call unw_get_reg() to get the
>values of the registers RDI, RSI, RDX, RCX and R8 for each frame since
>these are the registers that are used to pass the parameters to the
>called routine. Since these registers values are not saved across
>calls, there is no gaurantee that they will contain the correct values
>when I call unw_get_reg(). Is there some other place to look for the
>parameters?

Depends how much work you are prepared to do.  The Linux Kernel
Debugger patch (kdb, ftp://oss.sgi.com/projects/kdb/download/v4.4/)
gets the arguments without _any_ help from the compiler, but it is
extremely tricky code.  Tracking arguments without compiler help
involves instruction analysis, basic block decomposition of the
assembler code from the start of the function to the current point and
finally register tracking over all possible paths from the start of the
function to the current point.

>From the comments in kdb-v4.4-2.6.24-x86-1, file kdba_bt.c.

  Tracking registers by decoding the instructions is quite a bit harder than
  doing the same tracking using compiler generated information.  Register
  contents can remain in the same register, they can be copied to other
  registers, they can be stored on stack or they can be modified/overwritten.
  At any one time, there are 0 or more copies of the original value that was
  supplied in each register on input to the current function.  If a register
  exists in multiple places, one copy of that register is the master version,
  the others are temporary copies which may or may not be destroyed before the
  end of the function.

  The compiler knows which copy of a register is the master and which are
  temporary copies, which makes it relatively easy to track register contents
  as they are saved and restored.  Without that compiler based knowledge, this
  code has to track _every_ possible copy of each register, simply because we
  do not know which is the master copy and which are temporary copies which
  may be destroyed later.

  It gets worse: registers that contain parameters can be copied to other
  registers which are then saved on stack in a lower level function.  Also the
  stack pointer may be held in multiple registers (typically RSP and RBP)
  which contain different offsets from the base of the stack on entry to this
  function.  All of which means that we have to track _all_ register
  movements, or at least as much as possible.

  Start with the basic block that contains the start of the function, by
  definition all registers contain their initial value.  Track each
  instruction's effect on register contents, this includes reading from a
  parameter register before any write to that register, IOW the register
  really does contain a parameter.  The register state is represented by a
  dynamically sized array with each entry containing :-

    Register name
    Location it is copied to (another register or stack + offset)

  Besides the register tracking array, we track which parameter registers are
  read before being written, to determine how many parameters are passed in
  registers.  We also track which registers contain stack pointers, including
  their offset from the original stack pointer on entry to the function.

  At each exit from the current basic block (via JMP instruction or drop
  through), the register state is cloned to form the state on input to the
  target basic block and the target is marked for processing using this state.
  When there are multiple ways to enter a basic block (e.g. several JMP
  instructions referencing the same target) then there will be multiple sets
  of register state to form the "input" for that basic block, there is no
  guarantee that all paths to that block will have the same register state.

  As each target block is processed, all the known sets of register state are
  merged to form a suitable subset of the state which agrees with all the
  inputs.  The most common case is where one path to this block copies a
  register to another register but another path does not, therefore the copy
  is only a temporary and should not be propogated into this block.

  If the target block already has an input state from the current transfer
  point and the new input state is identical to the previous input state then
  we have reached a steady state for the arc from the current location to the
  target block.  Therefore there is no need to process the target block again.

  The steps of "process a block, create state for target block(s), pick a new
  target block, merge state for target block, process target block" will
  continue until all the state changes have propogated all the way down the
  basic block tree, including round any cycles in the tree.  The merge step
  only deletes tracking entries from the input state(s), it never adds a
  tracking entry.  Therefore the overall algorithm is guaranteed to converge
  to a steady state, the worst possible case is that every tracking entry into
  a block is deleted, which will result in an empty output state.

  As each instruction is decoded, it is checked to see if this is the point at
  which execution left this function.  This can be a call to another function
  (actually the return address to this function) or is the instruction which
  was about to be executed when an interrupt occurred (including an oops).
  Save the register state at this point.

  We always know what the registers contain when execution left this function.
  For an interrupt, the registers are in struct pt_regs.  For a call to
  another function, we have already deduced the register state on entry to the
  other function by unwinding to the start of that function.  Given the
  register state on exit from this function plus the known register contents
  on entry to the next function, we can determine the stack pointer value on
  input to this function.  That in turn lets us calculate the address of input
  registers that have been stored on stack, giving us the input parameters.
  Finally the stack pointer gives us the return address which is the exit
  point from the calling function, repeat the unwind process on that function.

  The data that tracks which registers contain input parameters is function
  global, not local to any basic block.  To determine which input registers
  contain parameters, we have to decode the entire function.  Otherwise an
  exit early in the function might not have read any parameters yet.

  ...

  Pass 1, identify the start and end of each basic block

  ...

  Pass 2, record register changes in each basic block */

  For each opcode that we care about, indicate how it uses its operands.  Most
  opcodes can be handled generically because they completely specify their
  operands in the instruction, however many opcodes have side effects such as
  reading or writing rax or updating rsp.  Instructions that change registers
  that are not listed in the operands must be handled as special cases.  In
  addition, instructions that copy registers while preserving their contents
  (push, pop, mov) or change the contents in a well defined way (add with an
  immediate, lea) must be handled as special cases in order to track the
  register contents.


A lot of the code in kdba_bt.c for x86 is to handle special cases in
the Linux kernel.  Because bits of the kernel are written in assembler
and the coders sometimes chose (for good reasons) to use non standard
calling conventions, KDB has to know about any special case assembler
code.  Not to mention stack switching, interrupt handling etc.  Most of
that should not be an issue for plain C code.

I had "fun" writing the x86 backtrace code :-)