From breakpoint addresses to source line stepping

From breakpoint addresses to source line stepping

[Mark Wielaard]

Hi,

This is an incomplete overview of all the issues/tasks remaining to go
from the simple (single threaded) breakpoint address support we have now
towards full source line stepping for Frysk. Not everything has the same
priority and some are just listed as ideas that would be nice to work on
when we had infinite time :) And some issues are only listed because I
was thinking in the past that we would use breakpoint addresses to
implement them, but on further thought that might be the wrong
mechanism to use. Comments on how to prioritize issues and what else
can be or is being worked on very welcome. And since it is a pretty
long list of issues I am sure I got some things wrong, so please
correct me where I am wrong. Especially my knowledge about the higher
level runtime/language model and the mapping to/from the low level
task/addresses is not yet complete.

= Current breakpoint address support implemented.

  - Proc shares breakpoints between Tasks. TaskState makes sure that
    running Task gets suspended when a new Code TaskObserver is added
    for an address that doesn't have a breakpoint set yet in the Proc
    and resumes immediately (unless already blocked).
    Code: frysk.proc.Proc, frysk.proc.Task, frysk.proc.TaskState
    frysk.proc.BreakpointAddresses

  - Supported through int3 on x86 and x86_64 and through trapping on
    an illegal instruction on ppc64. ppc isn't supported at this moment.
    A simple instruction replacement is done on the original addresses
    which gets reset when stepping (not multi-task safe, see below).
    Code: frysk.proc.BreakPoint,
    frysk.proc.Isa[IA32|EMT64|PPC64].getBreakpointInstruction().

  - Code observers can be set. Code observer can monitor multiple
    (related) addresses from multiple Tasks. Get updateHit() called.
    Code: frysk.proc.TaskObserver.Code,
    frysk.proc.Task,requestAddCodeObserver()

= Bugs and Extensions (low level work to do)

  - exec call should clears all breakpoints
    We forget to clear and delete the Code observer in this case.
    http://sourceware.org/bugzilla/show_bug.cgi?id=3255

  - traps can be used by applications
    Some applications install their own trap handlers and might
    generate trap events themselves. Our sanity checks are to strict
    and crash and burn in such cases.
    http://sourceware.org/bugzilla/show_bug.cgi?id=3256

  - system call vs breakpoint stepping.  When setting a breakpoint on
    a system call entry point we cannot easily use ptrace for a single
    step (since it will 'disappear' into the system call). Solution is
    to monitor syscall exit or set another breakpoint after return.
    Or maybe utrace will give us a more flexible interface.
    Needs test.

  - Unsafe locations/instructions
    Some locations or instructions mightbe unsafe for setting an
    breakpoint since they interfere with the instruction semantics. In
    particular ppc lwarx/stwcx pairs, see
    http://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=207287 for an
    example. Question are there similar instruction (pairs) on other
    architectures?
    Needs test.

  - Multiple tasks
    The current setup is not multi-task safe. When an breakpoint
    address is hit and we can to continue or step over it the original
    instruction stream is put back, a step is taking in the Task and
    the breakpoint instructions are put back. When other Tasks are
    running this means those Task might miss the breakpoint since they
    are seeing the original instruction stream. Or worse, they might
    see an invalid instruction stream with partial breakpoint and
    partial original instructions in place. This is a problem on
    architectures that have multibyte breakpoint instruction
    sequences, like on ppc.
    There are basically 2 ways to solve this issue:
    - Stop the world, step, resume world.
      Whenever an breakpoint address is updated all Tasks of the Proc
      are suspended first. The original instruction stream is
      restored. The Task that hit the breakpoint is stepped. The
      breakpoint instruction is put back. And all Tasks are restarted.
      This is mostly architecture independent.
    - Out of instruction stream stepping.
      To keep the other Tasks running (suspending/resuming has a lot
      of overhead) we can try to use 'out of instruction stream'
      stepping. A per Task local memory location is found to put the
      original instruction(s) on. We set the PC to this location, a
      step is performed and the PC is set back. On architectures that
      support different lenght instructions we need to parse the
      original instruction stream. And for (jump, load or branch)
      instructions that are relative to the PC after the step we need
      to 'fixup' some of the registers before or after the step. The
      kprobe code in the linux kernel is an example of this approach.
      This is highly architecture dependent.

  - Hardware breakpoints

    When available (often there are not many hardware breakpoint
    registers) we should use an hardware breakpoint to speed things up
    and simplify things (no code patching needed!). As an extension an
    analysis of which breakpoints are hit the most can be done so we
    use them for those and switch others to less used addresses.

= Even more stuff that would be nice (low level)

  - Alternative for simple function call tracing
    Often users will be interested in just function calls being
    hit. This can be build upon the low level breakpoint
    addresses. But a simpler way to add this might be to patch the PLT
    elf entries of libraries loaded. This is what strace does for
    example. For languages with alternative linking strategies (gcj)
    other entry point triggers might be used. This ties in with the
    runtime/language model used.

  - Pushing observers/trigger logic into tracee
    It would reduce overhead a lot if some of the observer logic could
    be pushed in the tracee so a trap event is only generated when
    some simple condition holds.  This would require elaborate code
    patching and/or loading of a support library in the
    executable. Very invasive. Would also need an overview of "simple
    logic" that is useful. Note that systemtap does something like
    this in kernel space through loading a kernel module that
    interacts with kprobes.

  - Better kernel support.
    Both utrace and user-kprobes will hopefully become available in
    the future and might ease some of the issues outlined above.
    utrace: http://people.redhat.com/roland/utrace/
    user-kprobes: http://lwn.net/Articles/176281/
    http://lwn.net/Articles/182910/

= Instruction stepping (work items)

  - Stopping the Task (BlockObserver)
    There are multiple TaskObserver to stop a Task, most appropriate
    in this case the Code observer which you can give an address. But
    there isn't a simple way to just stop the Task where it is
    currently executing. So a BlockObserver should be introduced which
    only function is to put the Task in a suspended state. From there
    on you could inspect the Task and possibly initiate instruction
    stepping.
    Code: frysk.proc.TaskObserver.Block
          - Action blocked(Task);

  - Stepping the Task (StepObserver)

    This would enable instruction single stepping. On each step the
    observer would be called with the current pc value. The
    implementation would need to add a stepping flag to the running
    and blocked task states which indicate that instead of
    task.sendContinue() a task.sendStepInstruction() should be done.
    Note that it is the responsibility of higher level code to decide
    whether to instruction step of put a breakpoint when using source
    line stepping.
    Code: frysk.proc.TaskObserver.Step
          - Action stepped(Task,long);

= Mapping addresses to lines and back

  - Mapping addresses to source lines
    Done through lib.dw (Dwlf,DwflLine). This uses dwarf information,
    so can only be done when debug info is available. In theory an
    address could belong to different source lines (when different
    contexts are optimized into common code). But in practise this
    seems to be ignore (unavailable?).

  - TagSets
    Maintained in frysk.gui.srcwin.tags are the set of source line
    tags that the gui is interested in. Currently there isn't a way to
    define them (except loading them from the preferences). The
    concept seems useful outside the gui/srcwin package.

  - Mapping TagSets to Task addresses
    Given a TagSet we need a mechanism for mapping them to breakpoint
    addresses for each Proc we are interested in. Given the whole
    system approach that frysk we need a way to map these whenever a
    new Proc is being observered. Map any core code mapped in to
    sources which can be mapped against the TagSets. We also need a
    way to monitor the loading (and unloading) of dynamic libraries

= source line stepping, step into, step out off...

  Given all of the above we can finally implement the functions a user
  would be interested in given a language model view of the sources.

Re: From breakpoint addresses to source line stepping

[Mark Wielaard]

Hi,

We are well into 2007 now, so it seems appropriate to give a little
high-level overview of low-level breakpoints and stepping as we have now
in frysk-core. Comments and suggestions for priorities are very welcome.

On Thu, 2006-09-28 at 16:26 +0200, Mark Wielaard wrote:
>   - Proc shares breakpoints between Tasks. TaskState makes sure that
>     running Task gets suspended when a new Code TaskObserver is added
>     for an address that doesn't have a breakpoint set yet in the Proc
>     and resumes immediately (unless already blocked).
>     Code: frysk.proc.Proc, frysk.proc.Task, frysk.proc.TaskState
>     frysk.proc.BreakpointAddresses

This is in place and has been extended to support generic suspension
through TaskObservation.needsSuspendedAction(). This is how stepping is
started also. It makes sure the Task is first stopped so, started from
that point the Instruction observer can fire updateExecuted() after each
instruction step. Suspension is done by sending the process a SIGSTOP.
There are still some corner cases where the stop event is send at the
wrong time. See for example bug 
http://sourceware.org/bugzilla/show_bug.cgi?id=3878 

>   - Supported through int3 on x86 and x86_64 and through trapping on
>     an illegal instruction on ppc64. ppc isn't supported at this moment.

PPC and PPC64 share the same 'illegal instruction' now. But I don't have
access and tested on PPC myself. There is one extra requirement now for
supporting breakpointing and stepping at the same time that doesn't have
PPC support at the moment (see below).

>     A simple instruction replacement is done on the original addresses
>     which gets reset when stepping (not multi-task safe, see below).
>     Code: frysk.proc.BreakPoint,
>     frysk.proc.Isa[IA32|EMT64|PPC64].getBreakpointInstruction().
> 
>   - Code observers can be set. Code observer can monitor multiple
>     (related) addresses from multiple Tasks. Get updateHit() called.
>     Code: frysk.proc.TaskObserver.Code,
>     frysk.proc.Task,requestAddCodeObserver()

This now all works (still not multi-task safe though).

>   - exec call should clears all breakpoints
>     We forget to clear and delete the Code observer in this case.
>     http://sourceware.org/bugzilla/show_bug.cgi?id=3255

Tests added and fixed.

>   - traps can be used by applications
>     Some applications install their own trap handlers and might
>     generate trap events themselves. Our sanity checks are to strict
>     and crash and burn in such cases.
>     http://sourceware.org/bugzilla/show_bug.cgi?id=3256

Likewise.

>   - system call vs breakpoint stepping.  When setting a breakpoint on
>     a system call entry point we cannot easily use ptrace for a single
>     step (since it will 'disappear' into the system call). Solution is
>     to monitor syscall exit or set another breakpoint after return.
>     Or maybe utrace will give us a more flexible interface.
>     Needs test.

This is still open. ptrace doesn't seem to support tracking both
stepping and syscalls at the same time. But the biggest issue here is
that the syscall tracking code still has a lot of open bugs and is
fragile. One design issue not solved yet is how to keep track of the
actual syscall and/or arguments for observers.

>   - Unsafe locations/instructions
>     Some locations or instructions mightbe unsafe for setting an
>     breakpoint since they interfere with the instruction semantics. In
>     particular ppc lwarx/stwcx pairs, see
>     http://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=207287 for an
>     example. Question are there similar instruction (pairs) on other
>     architectures?
>     Needs test.

Still open. But consensus seems to be that stepping through such
sequences is just not supported. This does mean that fstep for example
is unusable on ppc (because glibc uses such constructs). Since this is
more of a high-level issue, can the rt package help here?

>   - Multiple tasks
>     The current setup is not multi-task safe. When an breakpoint
>     address is hit and we can to continue or step over it the original
>     instruction stream is put back, a step is taking in the Task and
>     the breakpoint instructions are put back. When other Tasks are
>     running this means those Task might miss the breakpoint since they
>     are seeing the original instruction stream. Or worse, they might
>     see an invalid instruction stream with partial breakpoint and
>     partial original instructions in place. This is a problem on
>     architectures that have multibyte breakpoint instruction
>     sequences, like on ppc.
>     There are basically 2 ways to solve this issue:
>     - Stop the world, step, resume world.
>       Whenever an breakpoint address is updated all Tasks of the Proc
>       are suspended first. The original instruction stream is
>       restored. The Task that hit the breakpoint is stepped. The
>       breakpoint instruction is put back. And all Tasks are restarted.
>       This is mostly architecture independent.
>     - Out of instruction stream stepping.
>       To keep the other Tasks running (suspending/resuming has a lot
>       of overhead) we can try to use 'out of instruction stream'
>       stepping. A per Task local memory location is found to put the
>       original instruction(s) on. We set the PC to this location, a
>       step is performed and the PC is set back. On architectures that
>       support different lenght instructions we need to parse the
>       original instruction stream. And for (jump, load or branch)
>       instructions that are relative to the PC after the step we need
>       to 'fixup' some of the registers before or after the step. The
>       kprobe code in the linux kernel is an example of this approach.
>       This is highly architecture dependent.

This is the big open task still to do. The first approach seems the way
to go for now.

>   - Hardware breakpoints
> 
>     When available (often there are not many hardware breakpoint
>     registers) we should use an hardware breakpoint to speed things up
>     and simplify things (no code patching needed!). As an extension an
>     analysis of which breakpoints are hit the most can be done so we
>     use them for those and switch others to less used addresses.

Access to debug and status registers has been added to the x86 and
x86_64 Isas. Using this to provide hardware breakpoints shouldn't be too
hard. This could also be used as simple way to solve the multi-task
issue above when there are just a small number of breakpoints.

> = Even more stuff that would be nice (low level)
> 
>   - Alternative for simple function call tracing
>     Often users will be interested in just function calls being
>     hit. This can be build upon the low level breakpoint
>     addresses. But a simpler way to add this might be to patch the PLT
>     elf entries of libraries loaded. This is what strace does for
>     example. For languages with alternative linking strategies (gcj)
>     other entry point triggers might be used. This ties in with the
>     runtime/language model used.
> 
>   - Pushing observers/trigger logic into tracee
>     It would reduce overhead a lot if some of the observer logic could
>     be pushed in the tracee so a trap event is only generated when
>     some simple condition holds.  This would require elaborate code
>     patching and/or loading of a support library in the
>     executable. Very invasive. Would also need an overview of "simple
>     logic" that is useful. Note that systemtap does something like
>     this in kernel space through loading a kernel module that
>     interacts with kprobes.
> 
>   - Better kernel support.
>     Both utrace and user-kprobes will hopefully become available in
>     the future and might ease some of the issues outlined above.
>     utrace: http://people.redhat.com/roland/utrace/
>     user-kprobes: http://lwn.net/Articles/176281/
>     http://lwn.net/Articles/182910/

All this is still nice to have, but no work has been put into it yet.
Except for the fact that Roland has been working on making utrace
support better (it is in the FC kernels now in some form).

>   - Stopping the Task (BlockObserver)
>     There are multiple TaskObserver to stop a Task, most appropriate
>     in this case the Code observer which you can give an address. But
>     there isn't a simple way to just stop the Task where it is
>     currently executing. So a BlockObserver should be introduced which
>     only function is to put the Task in a suspended state. From there
>     on you could inspect the Task and possibly initiate instruction
>     stepping.
>     Code: frysk.proc.TaskObserver.Block
>           - Action blocked(Task);
> 
>   - Stepping the Task (StepObserver)
> 
>     This would enable instruction single stepping. On each step the
>     observer would be called with the current pc value. The
>     implementation would need to add a stepping flag to the running
>     and blocked task states which indicate that instead of
>     task.sendContinue() a task.sendStepInstruction() should be done.
>     Note that it is the responsibility of higher level code to decide
>     whether to instruction step of put a breakpoint when using source
>     line stepping.
>     Code: frysk.proc.TaskObserver.Step
>           - Action stepped(Task,long);

These two have been combined into the TaskObserver.Instruction. When an
Instruction observer has been requested to be added to a Task that Task
will be stopped and Instruction.updateExecuted() will be called. The
Task will remain in 'stepping mode' as long as this observer is
installed and continues in 'running mode' when all Instruction observers
are removed.

> = Mapping addresses to lines and back
> 
>   - Mapping addresses to source lines
>     Done through lib.dw (Dwlf,DwflLine). This uses dwarf information,
>     so can only be done when debug info is available. In theory an
>     address could belong to different source lines (when different
>     contexts are optimized into common code). But in practise this
>     seems to be ignore (unavailable?).
> 
>   - TagSets
>     Maintained in frysk.gui.srcwin.tags are the set of source line
>     tags that the gui is interested in. Currently there isn't a way to
>     define them (except loading them from the preferences). The
>     concept seems useful outside the gui/srcwin package.
> 
>   - Mapping TagSets to Task addresses
>     Given a TagSet we need a mechanism for mapping them to breakpoint
>     addresses for each Proc we are interested in. Given the whole
>     system approach that frysk we need a way to map these whenever a
>     new Proc is being observered. Map any core code mapped in to
>     sources which can be mapped against the TagSets. We also need a
>     way to monitor the loading (and unloading) of dynamic libraries
> 
> = source line stepping, step into, step out off...
> 
>   Given all of the above we can finally implement the functions a user
>   would be interested in given a language model view of the sources.

Mapping and runtime/language level views are not done in the frysk-core
proc package but is done in the rt package.

Looking back the most time consuming is adapting the TaskState mechanism
and creating reliable test cases.

TaskState is already a complex piece of code and it did contain lots of
latent issues that poped up when adding the breakpoint/stepping trap
handling. The testsuite did help a lot though. And it is often difficult
to find a balance between state-explosion (which often means having to
fix some issue in lots of different states) and keeping separate flags
in Task or Proc to act upon. I am leaning towards keeping the number of
different states minimal.

Bugs are often reported with examples from the gui. Since they are not
always deterministic the real work is creating something that is
deterministic. Often that only works when the bug is fully understood.
An assembly level tests framework would help. There are a couple of
scenarios described in bug #3500 that would be could to have. The
current tests do stepping onto existing breakpoints and syscalls, but
not deterministically which can make them succeed sometimes when they
should. Mike made a start of this in funit-asm.h

Cheers,

Mark