In this post I’ll continue with the development of the rusty_trap debugger by developing a formal state machine to improve the way breakpoint handling is implemented. This post parallels the debugger state machine in C post.

This post is part my larger series on writing a debugger in C and Rust. If you haven’t read the earlier posts you may want to go back and start from the beginning.

The Ideal Form

In the C version of this post I looked over the proposed features on the roadmap:

  • Add support for debugging multiple threads.
  • Use the debugger hook for dynamic library loading.
  • Add watch points.

All of these events, and breakpoints, cause execution of the inferior to stop so that rusty_trap can respond. That means that all of these events will need to be processed by trap_inferior_continue(). This function will, in practice, become the main event loop. The current implementation of trap_inferior_continue() looks like this:

pub fn trap_inferior_continue<F>(inferior: TrapInferior, callback: &mut F) -> i8
    where F: FnMut(TrapInferior, TrapBreakpoint) -> () {

    let pid = inferior;

    loop {
        ptrace_util::cont(pid);

        match waitpid(pid, None) {
            Ok(WaitStatus::Exited(_pid, code)) => return code,
            Ok(WaitStatus::Stopped(_pid, signal::SIGTRAP)) =>
                handle_breakpoint(inferior, callback),
            Ok(_) => panic!("Unexpected stop in trap_inferior_continue"),
            Err(_) => panic!("Unhandled error in trap_inferior_continue")
        }
    }
}

In C we wanted to achieve something like this:

void trap_inferior_continue(trap_inferior_t inferior)
{
  pid_t pid = inferior;

  ptrace_util_continue(pid);
  while(1) {
    int status;
    waitpid(pid, &status, 0);

    if (is_breakpoint()) {
      breakpoint_handle(inferior);
    } else if (is_watchpoint()) {
      watchpoint_handle(inferior)
    } else if (is_thread_event()) {
      thread_handle(inferior);
    } else if (is_library_load()) {
      symbol_manager_handle(inferior);
    } else if (is_exit()) {
      return;
    } else {
      error_handle(inferior);
    }
  }
}

We actually ended up with

void trap_inferior_continue(trap_inferior_t inferior)
{
  inferior_t *inf = inferior_resolve(inferior);

  inf->state = INFERIOR_RUNNING;
  ptrace_util_continue(inf->pid);
  while(1) {
    int status;
    waitpid(inf->pid, &status, 0);

    if (WIFSTOPPED(status) && WSTOPSIG(status) == SIGTRAP) {
      inf->state = breakpoint_handle(inferior, inf->state);
    } else if (WIFEXITED(status)) {
      return;
    } else {
      fprintf(stderr, "Unexpected stop in trap_inferior_continue: 0x%x\n", status);
      abort();
    }
  }
}

The Rust already version does most of this except for encapsulating an Inferior object. Also, Rust’s powerful pattern matching helps simplify the if/else tree a bit. That means we want to achieve something like this:

pub fn trap_inferior_continue<F>(inferior: TrapInferior, callback: &mut F) -> i8
    where F: FnMut(TrapInferior, TrapBreakpoint) -> () {

    let inf = inferior::resolve(inferior);
    ptrace_util::cont(inf.pid);

    loop {
        inf.state = match waitpid(pid, None) {
            Ok(WaitStatus::Exited(_pid, code)) => return code,
            Ok(WaitStatus::Stopped(_pid, signal::SIGTRAP)) =>
                handle_breakpoint(inferior, callback),
            Ok(_) => panic!("Unexpected stop in trap_inferior_continue"),
            Err(_) => panic!("Unhandled error in trap_inferior_continue")
        }
    }
}

Now that we have explored what we think we want, we need to go back to the motivation for the entire execise: handle hitting the same breakpoint more than once. Before beginning the implementation we will write a test:

Write a test that hits the same breakpoint more than once.

We need an inferior

// tests/inferior/loop.rs
pub fn foo() -> i32 {
    5
}

pub fn main() {
    for _x in 0..10 {
      foo();
    }
}

and a corresponding test:

// tests/lib.rs

#[test]
fn it_can_handle_a_breakpoint_more_than_once () {
    let mut breakpoint_count: i32 = 0;

    let inferior = rusty_trap::trap_inferior_exec(Path::new("./target/debug/loop"), &[])
        .unwrap();
    let bp = rusty_trap::trap_inferior_set_breakpoint(inferior, 0x555555558ff0);
    rusty_trap::trap_inferior_continue(inferior, &mut |passed_inferior, passed_bp| {
        assert_eq!(passed_inferior, inferior);
        assert_eq!(passed_bp, bp);
        breakpoint_count += 1;
    });

    assert_eq!(breakpoint_count, 5);
}

This is a straightforward port of the tests from the C debugger. This test fails:

failures:

---- it_can_handle_a_breakpoint_more_than_once stdout ----
	thread 'it_can_handle_a_breakpoint_more_than_once' panicked at 'assertion failed: `(left == right)` (left: `1`, right: `5`)', tests/lib.rs:40

which is expected. We don’t yet handle removing the breakpoint and single stepping over it. Let’s add support for that now. We need to update handle_breakpoint to use the state machine. But that means first we need to build up the state machine.

Build the state machine for the inferior process

These are the data structures that I will use

#[derive(Copy, Clone)]
enum InferiorState {
    Running,
    Stopped,
    SingleStepping
}

#[derive(Copy, Clone)]
struct Inferior {
    pid: pid_t,
    state: InferiorState
};

and they parallel those used in the C version. I’ve derived the copy trait as I expect to copy these around (using a global for now).

Next I need to put the Inferior struct to use.

-fn attach_inferior(pid: pid_t) -> Result<TrapInferior, Error> {
+fn attach_inferior(pid: pid_t) -> Result<Inferior, Error> {
     match waitpid(pid, None) {
-        Ok(WaitStatus::Stopped(pid, signal::SIGTRAP)) => return Ok(pid),
+        Ok(WaitStatus::Stopped(pid, signal::SIGTRAP)) =>
+            return Ok(Inferior {pid: pid, state: InferiorState::Running}),
         Ok(_) => panic!("Unexpected stop in attach_inferior"),
         Err(e) => return Err(e)
     }
@@ -56,7 +69,10 @@ pub fn trap_inferior_exec(filename: &Path, args: &[&str])
     loop {
         match fork() {
             Ok(Child)                      => exec_inferior(filename, args),
-            Ok(Parent(pid))                => return attach_inferior(pid),
+            Ok(Parent(pid))                => {
+                unsafe { global_inferior = attach_inferior(pid).ok().unwrap(
+                return Ok(pid)
+            },
             Err(Error::Sys(errno::EAGAIN)) => continue,
             Err(e)                         => return Err(e)
         }

This change updates attach_inferior to build the initial Inferior. Then, trap_inferior_exec saves that Inferior in a newly introducted global variable called global_inferior. So we end up with more unsafe code and sadness :(. But, hopefully we will be able to fix that in a future post. Finally, trap_inferior_exec now builds Ok(pid) and returns it to the caller.

Now that the Inferior is being built we need to use it in trap_inferior_continue and handle_breakpoint. Here’s what I ended up with for trap_inferior_continue:

pub fn trap_inferior_continue<F>(inferior: TrapInferior, callback: &mut F) -> i8
    where F: FnMut(TrapInferior, TrapBreakpoint) -> () {

    ptrace_util::cont(inf.pid);
    let mut inf = unsafe { global_inferior };
    loop {

        inf.state = match waitpid(inf.pid, None) {
            Ok(WaitStatus::Exited(_pid, code)) => return code,
            Ok(WaitStatus::Stopped(_pid, signal::SIGTRAP)) =>
                handle_breakpoint(inferior, callback),
            Ok(_) => panic!("Unexpected stop in trap_inferior_continue"),
            Err(_) => panic!("Unhandled error in trap_inferior_continue")
        };

        unsafe { global_inferior = inf };
    }
}

It is close to the ideal that I proposed above but with a little extra ugliness due to unsafe references to global_inferior. Note, that there is a warning generated by this change:

src/lib.rs:84:34: 84:42 warning: unused variable: `inferior`, #[warn(unused_variables)] on by default
src/lib.rs:84 pub fn trap_inferior_continue<F>(inferior: TrapInferior, callback: &mut F) -> i8

which I will keep in order to remind myself to improve this code later. The C version uses a function called inferior_resolve. I started writing a similar function for rusty_trap and then decided it would just hide the ugliness. As long as I believe that the ugliness is fixable I will keep it front and center so that I am motivated to fix it. Similarly, I could rename the parametter _inferior to suppress the warning but again, I want the warning so that I remember to fix this problem properly.

I needed to build a small structure to hold information about breakpoints:

#[derive(Copy, Clone)]
struct Breakpoint {
    shift : u64,
    target_address  : inferior::Pointer,
    aligned_address : inferior::Pointer,
    original_breakpoint_word : i64
}

This makes maintaining all of the data a little simpler, as well as makes the global data (now a global Breakpoint) a little more compact and easier to manage. I updated trap_inferior_set_breakpoint to create a new Breakpoint and assign it to the global:

pub fn trap_inferior_set_breakpoint(inferior: TrapInferior, location: u64) ->
    TrapBreakpoint {

    let aligned_address = location & !0x7u64;
    let bp = Breakpoint {
        shift : (location - aligned_address) * 8,
        aligned_address: inferior::Pointer(aligned_address),
        target_address: inferior::Pointer(location),
        original_breakpoint_word: peek_text(inferior,
                                            inferior::Pointer(aligned_address))
    };

    set(inferior, bp);

    unsafe {
        global_breakpoint = bp;
    }

    0
}

This has the same logic as the previous version of the function, it just stores the data in the new struct.

The final step is to update handle_breakpoint. I wrote it up along with a few helper functions:

fn step_over_breakpoint(inferior: TrapInferior, bp: Breakpoint) -> () {
    ptrace_util::poke_text(inferior, bp.aligned_address,
                           bp.original_breakpoint_word);
    ptrace_util::set_instruction_pointer(inferior, bp.target_address);
    ptrace_util::single_step(inferior);
}

fn set_breakpoint(inferior: TrapInferior, bp: Breakpoint) -> () {
    let mut modified = bp.original_breakpoint_word;
    modified &= !0xFFi64 << bp.shift;
    modified |= 0xCCi64 << bp.shift;
    ptrace_util::poke_text(inferior, bp.aligned_address, modified);
}

pub fn handle_breakpoint<F>(inf: Inferior,  mut callback: &mut F) ->
    InferiorState  where F: FnMut(TrapInferior, TrapBreakpoint) -> () {
    let inferior = inf.pid;

    let bp = unsafe { global_breakpoint };
    match inf.state {
        InferiorState::Running => {
            callback(inferior, 0);
            step_over_breakpoint(inferior, bp);
            InferiorState::SingleStepping
        },
        InferiorState::SingleStepping => {
            set_breakpoint(inferior, bp);
            ptrace_util::cont(inferior);
            InferiorState::Running
        },
        _ => panic!("Unsupported breakpoint encountered during supported inferior state")
    }
}

Debugging

I thought that this would work but it crashes with SIGSEGV in the inferior when running the tests. Occasionally I would see a few other types of errors that seemed a bit confusing. Also, there was some inconsistency. Sometimes the test “it_can_set_breakpoints” would SIGSEGV, other times it was “it_can_handle_a_breakpoint_more_than_once”. At least one of the two tests would pass. My first instinct was there was some non-deterministic behavior in the tests. This can be caused by the fact that the tests are run from multiple threads and therefore multiple tests can run concurrently. Currently, rusty_trap is not thread safe due to its unsafe use of global variables.

Based on a web search, I set the environment variable RUST_TEST_TASKS=1 to run the tests serially. But, the problem persisted.

With the C version I found that SIGSEGV’s would occur when I screwed up the setting or removing of the breakpoint. I decided to explore to see if this was the same problem I was having with rusty_trap. Here are the things I tried and the things that I found on my way to a solution.

I added debug printouts to describe when the SIGSEGV was caught by rusty_trap and I printed out the state. I found that the SIGSEGV occured in state SingleStepping. This means that the SIGSEGV occurs while single stepping the one instruction that was replaced with INT3. There are two possibilities:

  1. We resumed execution using the wrong instruction pointer
  2. We restored the original instruction word incorrectly

I started by looking at the instruction pointer. The new Breakpoint struct tracks the target address in the target_address field. Previously, I would read back the instruction pointer from the inferior and subtract 1 to get the address of the INT3. Perhaps I implemented the new code incorrectly.

I added some debug code to step_over_breakpoint to read back the instruction pointer, using ptrace_util::get_instruction_pointer and added a panic if the two target addresses didn’t match. The panic tripped and reported:

Breakpoint targets don't match:
RIP-1: 555555558ff0
bp:    555555559040

These targets are crossed between the two tests:

  • 555555558ff0 is the hardcoded breakpoint for it_can_handle_a_breakpoint_more_than_once
  • 555555559040 is the hardcoded breakpoint for it_can_set_breakpoints

which suggests that there is a race for global_breakpoint while running the tests. This reinforces my instinct that there is a threading problem. But, for this to be possible there must be multiple threads running in rusty_trap!

Another web search unconvered that the environment variable RUST_TEST_TASKS=1 was changed to RUST_TEST_THREADS=1. After I updated my environment the tests passed.

Some of the debug code I think will be generally useful and remains in rusty_trap. Other code was too specific to this problem and I’ve thrown it away.

Refactor

Now that the tests are passing again I need to refactor the code bit. I’ve created some duplication between set_breakpoint and trap_inferior_set_breakpoint. To clean this up I can just call set_breakpoint from trap_inferior_set_breakpoint after creating the Breakpoint structure like this:

pub fn trap_inferior_set_breakpoint(inferior: TrapInferior, location: u64) ->
    TrapBreakpoint {

    let aligned_address = location & !0x7u64;
    let original = ptrace_util::peek_text(inferior,
                                          InferiorPointer(aligned_address));
    let shift = (location - aligned_address) * 8;
    let bp = Breakpoint {
        shift : shift,
        aligned_address: InferiorPointer(aligned_address),
        target_address: InferiorPointer(location),
        original_breakpoint_word: original
    };

    set_breakpoint(inferior, bp);

    unsafe {
        global_breakpoint = bp;
    }

    0
}

I can clean this up just a bit by removing some of the temporary variables. At one point they served as explaining variables but I think the Breakpoint field names are clear enough. So I can collapse down to this:

pub fn trap_inferior_set_breakpoint(inferior: TrapInferior, location: u64) ->
    TrapBreakpoint {

    let aligned_address = location & !0x7u64;
    let bp = Breakpoint {
        shift : (location - aligned_address) * 8,
        aligned_address: InferiorPointer(aligned_address),
        target_address: InferiorPointer(location),
        original_breakpoint_word: ptrace_util::peek_text(inferior,
                                               InferiorPointer(aligned_address))
    };

    set_breakpoint(inferior, bp);

    unsafe {
        global_breakpoint = bp;
    }

    0
}

Extract Breakpoint Module

There are now many functions related to breakpoint functionality, all with the word “breakpoint” in their name. These functions are:

  • fn step_over_breakpoint
  • fn set_breakpoint
  • fn handle_breakpoint<F>
  • pub fn trap_inferior_set_breakpoint

I want to move all the non-public functions to their own module. I also have to decide how to handle the public function trap_inferior_set_breakpoint. I have to decide if I want to move it and if I do move it decide if I should export it as is or wrap it in an API function? That is, should there be new trap_inferior_set_breakpoint that just calls breakpoint::set_breakpoint_in_inferior like this:

pub fn trap_inferior_set_breakpoint(inferior: TrapInferior, location: u64) -> TrapBreakpoint {
  // API stuff

  breakpoint::set_breakpoint_in_inferior(TrapInferior, location)
}

where breakpoint::set_breakpoint_in_inferior has the existing functionality from trap_inferior_set_breakpoint.

This pattern of having a high-level API function that calls into a module specific function is sometimes a useful form or code organization. However, at this stage of development I don’t think it buys us much. The value from the pattern comes when there is interesting “API stuff” to do. This could include a common way to resolve inferior into some internal data structure or do API level error checking. rusty_trap may need these things in the future but we haven’t defined them yet. For now, I’ll just move trap_inferior_set_breakpoint into a new breakpoint module as is. I’ll save any more involved organization until we have a better idea of what kind of “API stuff” we would want.

I’ll extract the new module in steps.

The first step is to just cut and paste all the breakpoint related stuff into src/breakpoint/mod.rs. This includes the functions above as well as TrapInferior, the Breakpoint struct and global_breakpoint. I’ll also need to make breakpoint::handle_breakpoint public since it is called from trap_inferior_continue.

This isn’t enough to get things working. Both lib.rs (the core debugger) and breakpoint/mod.rs need access to the Inferior struct. I’ll need to break this out into its own module. I’ll do this as a new step. I’ll back out the work I’ve done to extract breakpoint and will first extract inferior. The steps to extract inferior are

  • Move TrapInferior, InferiorState and Inferior to inferior/mod.rs
  • Declare the module from lib.rs with mod inferior;
  • Use everything from inferior from lib.rs with use inferior::*;
  • Make everything public in inferior including the fields of Inferior. I should probably add accessors to keep things cleaner but for now this will do.
  • Run the tests and see that they pass.

You might wonder why I backed out the work I’d done to move code to the breakpoint module. I’m loosely following The Mikado Method which helps me make a cleaner more reproducible changes. When I backed out the changes I lost very little as I had already written down the steps I’d taken here in this blog post. Recreating the work cost very little. And following this method bought me a lot. The method made sure that the changes to create the inferior module could stand on their own, that is they don’t depend on any work in progress toward a breakpoint module.

Now, I can try again at extracting breakpoint

  • Move code to breakpoint/mod.rs
  • Make breakpoint::handle_breakpoint public
  • Also move TrapBreakpoint
  • Declare the module from lib.rs with mod breakpoint; and use it.
  • Use ptrace_util::* from breakpoint and remove ptrace_util:: qualifiers from all calls.
  • Export trap_inferior_set_breakpoint as part of the API using pub use self::breakpoint::trap_inferior_set_breakpoint;

With these changes the tests pass!

Some of the use directives and namespacing of functions seems a little off to me. I need to read up on module and crates and hope to improve some of this in the future.

The next major step of refactoring is to simplify the names of the functions in the breakpoint module. Aside from trap_inferior_set_breakpoint there is no good reason to have “breakpoint” in the name. The fact that they are in the breakpoint modules means they are related to breakpoints. From lib.rs I will call them using the breakpoint:: prefix so it will be clear that they are breakpoint related. The name changes are:

  • step_over_breakpoint -> step_over
  • set_breakpoint -> set
  • handle_breakpoint -> breakpoint::handle (qualified since it is called externally)

Conclusion

At this point we have a working state machine that handles breakpoint events and that should be able to serve us for upcoming events like thread attach, library load, and watchpoints.

We accomplished a lot but also left ourselves with a few TODO items:

  1. Fix warnings
  2. use inferior in trap_inferior_continue with some sort of inferior_resolve mechanism
  3. Support multiple threads in rusty_trap
  4. Consider adding accessors to Inferior and making the fields private.
  5. Clean up use and namespacing between modules

Items 1 and 2, will improve as we get rid of globals and handle multiple breakpoints which I hope to do in the next post. Item 3, is a pretty large task and seems absent from the rusty_trap roadmap and I’m not sure if its is necessary or not. Note, item 3 is different than supporting multiple threads in the inferior. Items 4 and 5 are largely cosmetic and I may clean them up between posts.